Apriori算法如何避免频繁项集重复计数？

《Python数据挖掘入门与实践》中Apriori算法代码改进：避免频繁项集重复计数

本文针对《Python数据挖掘入门与实践》一书中Apriori算法代码片段中频繁项集重复计数的问题，提出改进方案。原代码片段如下：

from collections import defaultdict

def find_frequent_itemsets(favorable_reviews_by_users, k_1_itemsets, min_support):
    counts = defaultdict(int)
    for user, reviews in favorable_reviews_by_users.items():
        for itemset in k_1_itemsets:
            if itemset.issubset(reviews):
                for other_reviewed_movie in reviews - itemset:
                    current_superset = itemset | frozenset((other_reviewed_movie,))
                    counts[current_superset] += 1
    return dict([(itemset, frequency) for itemset, frequency in counts.items() if frequency >= min_support])

问题在于，由于集合无序性，{a, b} 和 {b, a} 被视为相同集合，但原代码会重复计数。

改进方案一：排序后作为键

此方案在生成 current_superset 后，对其进行排序，再将其作为字典的键。 这确保了即使顺序不同，相同的项集也会被识别为相同的键。

from collections import defaultdict

def find_frequent_itemsets_improved1(favorable_reviews_by_users, k_1_itemsets, min_support):
    counts = defaultdict(int)
    for user, reviews in favorable_reviews_by_users.items():
        for itemset in k_1_itemsets:
            if itemset.issubset(reviews):
                for other_reviewed_movie in reviews - itemset:
                    current_superset = itemset | frozenset((other_reviewed_movie,))
                    # Sort the frozenset for consistent key
                    sorted_superset = frozenset(sorted(list(current_superset))) 
                    counts[sorted_superset] += 1
    return dict([(itemset, frequency) for itemset, frequency in counts.items() if frequency >= min_support])

改进方案二：使用itertools.combinations避免重复

此方案利用 itertools.combinations 直接生成所有可能的k-项集组合，避免了重复计算。

from collections import defaultdict
from itertools import combinations

def find_frequent_itemsets_improved2(favorable_reviews_by_users, k_1_itemsets, min_support):
    counts = defaultdict(int)
    for user, reviews in favorable_reviews_by_users.items():
        for itemset in combinations(reviews, 2): #Generate all 2-item combinations
            counts[frozenset(itemset)] += 1
    return dict([(itemset, frequency) for itemset, frequency in counts.items() if frequency >= min_support])

选择合适的改进方案：

方案一修改了原代码的逻辑，保持了原算法的整体结构，只是增加了排序步骤，相对容易理解和维护。方案二则采用了更简洁高效的算法，直接生成所有组合，避免了重复计算，效率更高，但需要理解itertools.combinations 的用法。 选择哪个方案取决于对代码可读性和效率的要求。

需要注意的是，以上代码片段只处理了从k=1到k=2的情况。 完整的Apriori算法需要递归处理更高阶的频繁项集生成。 改进后的代码也需要相应地调整以适应完整的算法流程。