Prune candidate itemsets that are not frequent. The goal of pruning is to filter out candidate itemsets that are not frequent. This is done by checking if all the (k-1) subsets of a candidate itemset are present in the frequent itemsets of the previous iteration (valid subsequences
(itemset: list, candidates: list, length: int)
| 26 | |
| 27 | |
| 28 | def prune(itemset: list, candidates: list, length: int) -> list: |
| 29 | """ |
| 30 | Prune candidate itemsets that are not frequent. |
| 31 | The goal of pruning is to filter out candidate itemsets that are not frequent. This |
| 32 | is done by checking if all the (k-1) subsets of a candidate itemset are present in |
| 33 | the frequent itemsets of the previous iteration (valid subsequences of the frequent |
| 34 | itemsets from the previous iteration). |
| 35 | |
| 36 | Prunes candidate itemsets that are not frequent. |
| 37 | |
| 38 | >>> itemset = ['X', 'Y', 'Z'] |
| 39 | >>> candidates = [['X', 'Y'], ['X', 'Z'], ['Y', 'Z']] |
| 40 | >>> prune(itemset, candidates, 2) |
| 41 | [['X', 'Y'], ['X', 'Z'], ['Y', 'Z']] |
| 42 | |
| 43 | >>> itemset = ['1', '2', '3', '4'] |
| 44 | >>> candidates = ['1', '2', '4'] |
| 45 | >>> prune(itemset, candidates, 3) |
| 46 | [] |
| 47 | """ |
| 48 | itemset_counter = Counter(tuple(item) for item in itemset) |
| 49 | pruned = [] |
| 50 | for candidate in candidates: |
| 51 | is_subsequence = True |
| 52 | for item in candidate: |
| 53 | item_tuple = tuple(item) |
| 54 | if ( |
| 55 | item_tuple not in itemset_counter |
| 56 | or itemset_counter[item_tuple] < length - 1 |
| 57 | ): |
| 58 | is_subsequence = False |
| 59 | break |
| 60 | if is_subsequence: |
| 61 | pruned.append(candidate) |
| 62 | return pruned |
| 63 | |
| 64 | |
| 65 | def apriori(data: list[list[str]], min_support: int) -> list[tuple[list[str], int]]: |