《python数据挖掘入门与实践》apriori算法代码优化：避免频繁项集重复计数
本文针对《Python数据挖掘入门与实践》一书中Apriori算法代码片段中存在的重复计数问题，提出改进方案。原代码在寻找频繁2-项集时，由于遍历所有可能的1-项集，导致相同的2-项集被多次计算。
问题描述:
原代码片段如下：
<code class="python">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])</code>
当用户评论集合为 {a, b} 时，算法会分别以 {a} 和 {b} 作为 itemset 进行计算，分别生成 {a, b} 和 {b, a}，由于 frozenset({a, b}) == frozenset({b, a})，导致 {a, b} 被重复计数。
立即学习“Python免费学习笔记（深入）”；
改进方案:
为了避免重复计数，可以采用以下两种方法：
方法一：计数前检查
在 counts[current_superset] += 1 之前，检查 current_superset 是否已存在于 counts 中。如果存在，则直接累加计数；否则，新增计数。
<code class="python">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,))
counts[current_superset] +=1 #直接计数，避免重复
return dict([(itemset, frequency) for itemset, frequency in counts.items() if frequency >= min_support])</code>
方法二：排序后生成项集
在生成 current_superset 之前，对 itemset 和 other_reviewed_movie 进行排序，确保所有项集的元素顺序一致。这样可以保证相同的项集只会被计算一次。
<code class="python">from collections import defaultdict
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 k_1_itemsets:
if itemset.issubset(reviews):
for other_reviewed_movie in sorted(list(reviews - itemset)): #排序
current_superset = frozenset(sorted(list(itemset | frozenset((other_reviewed_movie,))))) #排序
counts[current_superset] += 1
return dict([(itemset, frequency) for itemset, frequency in counts.items() if frequency >= min_support])</code>
总结:
方法二比方法一效率更高，因为它避免了重复的计数检查。 两种方法都能有效解决原代码中频繁项集重复计数的问题，得到正确的频繁2-项集。 选择哪种方法取决于具体的性能需求和代码风格偏好。 建议读者在学习Apriori算法时，理解其原理，并尝试改进代码以提高效率和准确性。
