Returns a list of frequent itemsets and their support counts. >>> data = [['A', 'B', 'C'], ['A', 'B'], ['A', 'C'], ['A', 'D'], ['B', 'C']] >>> apriori(data, 2) [(['A', 'B'], 1), (['A', 'C'], 2), (['B', 'C'], 2)] >>> data = [['1', '2', '3'], ['1', '2'], ['1', '3'], ['1', '4'],
(data: list[list[str]], min_support: int)
| 63 | |
| 64 | |
| 65 | def apriori(data: list[list[str]], min_support: int) -> list[tuple[list[str], int]]: |
| 66 | """ |
| 67 | Returns a list of frequent itemsets and their support counts. |
| 68 | |
| 69 | >>> data = [['A', 'B', 'C'], ['A', 'B'], ['A', 'C'], ['A', 'D'], ['B', 'C']] |
| 70 | >>> apriori(data, 2) |
| 71 | [(['A', 'B'], 1), (['A', 'C'], 2), (['B', 'C'], 2)] |
| 72 | |
| 73 | >>> data = [['1', '2', '3'], ['1', '2'], ['1', '3'], ['1', '4'], ['2', '3']] |
| 74 | >>> apriori(data, 3) |
| 75 | [] |
| 76 | """ |
| 77 | itemset = [list(transaction) for transaction in data] |
| 78 | frequent_itemsets = [] |
| 79 | length = 1 |
| 80 | |
| 81 | while itemset: |
| 82 | # Count itemset support |
| 83 | counts = [0] * len(itemset) |
| 84 | for transaction in data: |
| 85 | for j, candidate in enumerate(itemset): |
| 86 | if all(item in transaction for item in candidate): |
| 87 | counts[j] += 1 |
| 88 | |
| 89 | # Prune infrequent itemsets |
| 90 | itemset = [item for i, item in enumerate(itemset) if counts[i] >= min_support] |
| 91 | |
| 92 | # Append frequent itemsets (as a list to maintain order) |
| 93 | for i, item in enumerate(itemset): |
| 94 | frequent_itemsets.append((sorted(item), counts[i])) |
| 95 | |
| 96 | length += 1 |
| 97 | itemset = prune(itemset, list(combinations(itemset, length)), length) |
| 98 | |
| 99 | return frequent_itemsets |
| 100 | |
| 101 | |
| 102 | if __name__ == "__main__": |
no test coverage detected