Apriori算法中基于k阶频繁项集生成k+1阶候选项集的高效实现
问题根因定位
之前的实现跑不动、触发IOPub数据率超限,本质是完全偏离Apriori的候选项集生成规则:
- 代码把Lk里所有项集的元素拆出来拼成一个大元组,无差别做全局k阶组合,既没有生成目标k+1长度项集的逻辑,也没有任何剪枝。当涉及的item规模到几百上千时,组合数会指数级膨胀,直接撑爆输出缓冲区。
- 没有用到Apriori的核心约束:候选项集只能从已有的k阶频繁项集的内在连接关系生成,根本不需要把所有出现过的item拿出来做无意义的全组合。
符合Apriori规则的高效实现逻辑
候选项集生成严格分两步走,从一开始就砍掉没用的计算:
- 连接步:把所有k阶频繁项集按“长度为k-1的公共前缀”分组,只对同组内的项集做两两拼接,生成初始的k+1长度候选。
- 所有存入的项集元组预先做排序,避免因为元素顺序不一样,把同一个项集当成两个、或者前缀匹配失效的问题。
- 同组判定很简单:两个k阶项集,前k-1个元素完全一样的时候才允许拼接,把两个项集最后那个不一样的元素拼上,就得到长度为k+1的新项集。
- 相比全局组合的方式,分组能直接跳过大量根本不满足连接条件的项集对,计算量能压下来几个量级。
- 剪枝步:对连接步生成的初始候选,严格卡Apriori的规则:
- 对每个k+1长度的候选,提取它所有长度为k的子集,只要有一个k阶子集不在输入的Lk频繁项集里,就直接把这个候选删掉,不纳入最终输出。
适配数据规模的代码实现
import itertools as it from collections import defaultdict def generateItemsets(Lk, k): # 空输入直接返回空集合 if not Lk: return set() # 提前把Lk的项集转成排序后的元组集合,子集校验时O(1)查找 lk_set = set() # 按长度为k-1的前缀做分组,存每个前缀对应的后缀元素列表 prefix_groups = defaultdict(list) for item in Lk.keys(): # 统一给项集排序,避免顺序差异导致匹配失效 sorted_item = tuple(sorted(item)) lk_set.add(sorted_item) # 截取长度为k-1的部分当分组前缀 prefix = sorted_item[:k-1] # 把当前项集的最后一个元素存到对应分组里 suffix = sorted_item[-1] prefix_groups[prefix].append(suffix) candidate_set = set() # 遍历每个前缀组做连接拼接 for prefix, suffix_list in prefix_groups.items(): # 后缀数少于2的话,没法两两拼出新的k+1阶项集,直接跳过 if len(suffix_list) < 2: continue # 给后缀排序后做两两组合,保证生成的新项集是有序的 for s1, s2 in it.combinations(sorted(suffix_list), 2): candidate = prefix + (s1, s2) candidate_set.add(candidate) # 执行Apriori剪枝:检查候选的所有k阶子集是否都存在于Lk中 pruned_candidates = set() for cand in candidate_set: # 生成当前候选的所有k阶子集(相当于从k+1个元素里去掉任意一个) all_k_subsets = set(it.combinations(cand, k)) # 所有子集都在Lk里,才保留这个候选 if all(subset in lk_set for subset in all_k_subsets): pruned_candidates.add(cand) return pruned_candidates
效果验证
用题目给的测试样例跑的时候,输入Lk = {(150,): 2, (160,): 3, (170,): 3, (180,): 3},k=1,输出和要求的集合完全一致。
针对16000条交易记录、item范围0-999的场景,这个实现完全适配:
- 前缀分组机制直接跳过无意义的跨组项集对比
- 集合式的存在性校验把剪枝环节的查找效率拉满
- 严格按Apriori规则过滤无效候选,最终生成的候选项集规模可控,不会出现数据量超限的问题
内容的提问来源于stack exchange,提问作者Ashar
相关产品推荐
相关产品推荐

