Python从零实现FP-growth算法：FP树构建、可视化与购物篮分析实战

简介这份资源面向数据挖掘与机器学习初学者及需要落地关联规则分析的开发者围绕FP-growth频繁模式增长算法提供Python实现与FP树可视化工具可用于购物篮分析、频繁项集挖掘与大型数据库模式发现等场景。压缩包共11个文件、约480KB包含Python主程序与依赖清单、购物篮示例数据CSV、FP树可视化输出PNG、说明文档与Markdown笔记以及pygraphviz安装包便于快速搭建实验环境并复现挖掘流程。已有76人学习下载。读者可据此理解FP树构建与递归挖掘频繁项集的完整思路借助可视化结果直观观察频繁模式的组织方式并对照示例数据完成从频繁项集到关联规则的实践适合作为课程实验、项目原型或算法自学的参考材料。1. 从一张购物小票说起FP-growth 到底在挖什么超市收银台每天吐出成千上万张小票每张小票就是一条交易记录{牛奶, 面包, 尿布}、{啤酒, 尿布, 薯片}……单看一张毫无价值但把几十万张叠在一起就能问出一个很值钱的问题——哪些商品总是成组出现这就是购物篮分析也是关联规则学习最经典的落地场景。而 FP-growth频繁模式增长算法就是干这件事的主力工具之一它和 Apriori 同属频繁项集挖掘家族但走了一条完全不同的路Apriori 靠反复扫描数据库、逐层生成候选集数据库一大就慢得让人想砸键盘FP-growth 只扫两遍数据库把数据压进一棵 FP 树再在树上递归挖频繁项集效率通常高出一个量级。这篇笔记讲的就是用 Python 把 FP-growth 从零实现出来并且把 FP 树结构可视化让你能亲眼看到数据是怎么被压缩成树的。适合两类人一类是做数据挖掘、想搞懂 FP 树内部到底长什么样的从业者另一类是拿它做购物篮分析、需要一套能直接跑在大型数据库上的可复现代码的工程师。下面从原理、实现、参数、可视化一路讲到踩坑代码都能直接抄。2. FP 树是怎么把数据库压小的原理与建树流程2.1 为什么 FP-growth 比 Apriori 快Apriori 的核心痛点是「候选集爆炸」。假设有 1 万个商品光是长度为 2 的候选集就有近 5000 万个组合每轮还要全表扫描一次数据库去数支持度I/O 成本随数据量线性上涨。FP-growth 换了个思路它不生成候选集而是把整个数据库的事务压缩成一棵前缀树FP 树共享相同前缀的事务走同一条路径节点上只存计数。这样数据库里重复的模式被合并扫描次数从「每层一次」降到「总共两次」。第一次扫描统计每个商品的出现频次丢掉低于最小支持度的项剩下的按频次降序排列得到一张头指针表header table。第二次扫描对每条事务按头指针表的顺序重排然后逐条插入 FP 树路径共享、计数累加。建完树之后挖掘过程从频次最低的项开始为每个项构造条件模式基conditional pattern base再递归建条件 FP 树一路挖出所有频繁项集。理解这一点很关键FP 树不是数据库的副本而是数据库的「压缩摘要」压缩率取决于事务之间的前缀重合度。购物篮数据前缀重合度高压缩效果就好如果每条事务商品都完全不同树会退化成接近原始数据量这时候 FP-growth 的优势就不明显了。2.2 建树的最小可运行实现先定义树节点和头指针表再写两次扫描的建树逻辑。下面这段是核心骨架可以直接跑。class FPNode: def __init__(self, name, count, parent): self.name name # 节点对应的项名 self.count count # 经过该节点的路径计数 self.parent parent # 父节点回溯条件模式基用 self.children {} # 子节点字典key 是项名 self.node_link None # 指向头指针表中同名项的下一个节点 def increment(self, count): self.count count # 路径复用时累加计数 def build_header_table(transactions, min_support): 第一次扫描统计频次过滤低频项按频次降序 freq {} for trans in transactions: for item in trans: freq[item] freq.get(item, 0) 1 # 只保留满足最小支持度的项 freq {k: v for k, v in freq.items() if v min_support} # 按频次降序频次相同按项名保证结果稳定 return dict(sorted(freq.items(), keylambda x: (-x[1], x[0]))) def build_fp_tree(transactions, header): 第二次扫描按头指针表顺序重排事务逐条插入树 root FPNode(Null Set, 1, None) for trans in transactions: # 过滤掉非频繁项并按全局频次降序重排 ordered [item for item in header if item in trans] cur root for item in ordered: if item in cur.children: cur.children[item].increment(1) # 路径已存在计数加一 else: node FPNode(item, 1, cur) cur.children[item] node # 挂到头指针表的链表上方便后续按项回溯 if header[item][1] is None: header[item] (header[item][0], node) else: walk header[item][1] while walk.node_link: walk walk.node_link walk.node_link node cur cur.children[item] return root逻辑说明build_header_table完成第一次扫描返回的是「项名 → 频次」的有序字典这个顺序就是后续所有事务重排的依据顺序必须全局一致否则树结构会乱。build_fp_tree完成第二次扫描ordered那行是关键——它保证每条事务都按同一套频次顺序插入前缀才能对齐、路径才能共享。node_link是头指针表的链表指针把树上所有同名节点串起来挖掘阶段从某个项出发时靠它快速找到所有出现位置。参数说明min_support是最小支持度计数不是比例比如 10 万条事务里你要求某组合至少出现 1000 次就传 1000。这个值直接决定树的大小和挖掘结果数量后面单独讲怎么调。2.3 从树上挖频繁项集建完树只是第一步真正出结果的是挖掘函数。对头指针表里每个项从频次最低的开始沿着node_link找到所有节点向上回溯到根收集条件模式基再递归建条件 FP 树。def ascend_tree(node): 从节点向上回溯到根返回路径上的项名列表 path [] while node.parent is not None: path.append(node.name) node node.parent return path[::-1] # 反转成从根到叶的顺序 def find_prefix_paths(header, item): 收集某个项的所有条件模式基路径 该路径的计数 patterns {} node header[item][1] while node: path ascend_tree(node) if path: patterns[tuple(path)] patterns.get(tuple(path), 0) node.count node node.node_link return patterns def mine_tree(header, min_support, prefix, freq_items): 递归挖掘从低频项开始构造条件树继续挖 # 按频次升序处理先挖低频项条件树更小 items sorted(header.items(), keylambda x: x[1][0]) for item, (count, _) in items: new_prefix prefix [item] freq_items.append((new_prefix, count)) # 构造该项的条件模式基 patterns find_prefix_paths(header, item) # 把条件模式基当成新的事务集递归建树 cond_trans [] for path, cnt in patterns.items(): cond_trans.extend([list(path)] * cnt) cond_header build_header_table(cond_trans, min_support) if cond_header: cond_root build_fp_tree(cond_trans, cond_header) mine_tree(cond_header, min_support, new_prefix, freq_items)逻辑说明ascend_tree负责回溯find_prefix_paths把某个项的所有出现路径汇总成条件模式基计数按路径累加。mine_tree是递归主体注意它按频次升序处理——先挖低频项因为低频项的条件树更小递归深度和内存占用都更友好。每挖到一个项就把它加进prefix同时记录(频繁项集, 支持度计数)。参数说明prefix是递归过程中累积的前缀项集初始传空列表freq_items是输出容器最终里面就是所有频繁项集及其支持度。min_support在递归中保持不变但条件模式基的规模会逐层缩小所以深层递归通常很快。3. 参数怎么调支持度、置信度与性能的三角关系3.1 最小支持度决定结果数量和树的大小min_support是 FP-growth 里最敏感的参数没有之一。它设得高树小、跑得快但只能挖出特别常见的组合设得低能挖出长尾模式但树会膨胀、递归变深、内存吃紧。经验做法是先跑一遍频次统计看看数据的分布再定一个能覆盖你关心商品的阈值。# 先看频次分布再决定 min_support from collections import Counter all_items Counter() for trans in transactions: all_items.update(trans) # 打印频次分位数帮你判断阈值该落在哪 import numpy as np counts np.array(list(all_items.values())) for q in [50, 70, 90, 95, 99]: print(f{q}分位频次: {np.percentile(counts, q):.0f})逻辑说明这段不参与挖掘只是帮你做决策。如果 90 分位的频次是 200说明大部分商品出现次数不高min_support设 100 可能就只剩头部商品设 20 能覆盖更多组合但要留意树规模。参数上min_support是绝对计数换算成比例就是「计数 / 总事务数」和 Apriori 里的 support 概念一致只是这里传计数更直观。3.2 置信度与提升度从频繁项集到关联规则频繁项集本身只是「经常一起出现」要变成可解释的规则还得算置信度和提升度。置信度衡量「买了 A 的人有多少也买了 B」提升度衡量「A 和 B 一起出现是不是比随机更频繁」。指标公式含义阈值建议支持度count(A∪B) / N组合出现的普遍程度按业务定通常 0.01~0.1置信度count(A∪B) / count(A)A 出现时 B 也出现的概率0.5 起步看业务提升度置信度 / (count(B)/N)比随机共现强多少倍 1 才有正相关 1.5 较可信def generate_rules(freq_items, total_trans, min_conf0.5): 从频繁项集生成关联规则过滤低置信度 rules [] for itemset, support in freq_items: if len(itemset) 2: continue for i in range(1, len(itemset)): from itertools import combinations for antecedent in combinations(itemset, i): antecedent set(antecedent) consequent set(itemset) - antecedent # 找前件的支持度 ant_support next((s for it, s in freq_items if set(it) antecedent), None) if not ant_support: continue conf support / ant_support if conf min_conf: # 提升度 置信度 / 后件支持度占比 cons_support next((s for it, s in freq_items if set(it) consequent), None) lift conf / (cons_support / total_trans) if cons_support else 0 rules.append((antecedent, consequent, support, conf, lift)) return rules逻辑说明generate_rules遍历每个频繁项集用combinations枚举所有可能的前件划分算置信度并过滤。提升度那行需要后件的支持度如果后件本身不是频繁项集理论上不会因为子集必频繁就跳过。参数min_conf是置信度下限total_trans是总事务数用于把计数换算成比例。3.3 大数据量下的内存控制FP-growth 的内存瓶颈在递归建条件树。数据量上到百万级事务时递归深度和临时事务列表会吃掉大量内存。常见做法是给递归加深度上限或者对条件模式基做采样。def mine_tree_limited(header, min_support, prefix, freq_items, max_depth50, depth0): 带深度限制的挖掘防止超大数据集递归爆栈 if depth max_depth: return items sorted(header.items(), keylambda x: x[1][0]) for item, (count, _) in items: new_prefix prefix [item] freq_items.append((new_prefix, count)) patterns find_prefix_paths(header, item) cond_trans [] for path, cnt in patterns.items(): cond_trans.extend([list(path)] * cnt) cond_header build_header_table(cond_trans, min_support) if cond_header: build_fp_tree(cond_trans, cond_header) mine_tree_limited(cond_header, min_support, new_prefix, freq_items, max_depth, depth 1)逻辑说明max_depth限制递归层数超过就停止避免在超长项集上无限深入。代价是可能漏掉一些超长频繁项集但实际业务里长度超过 10 的项集本来就很少见这个取舍通常划算。参数depth是当前递归深度初始为 0调用时不用手动传。4. 把 FP 树画出来可视化工具与调试技巧4.1 用 Graphviz 渲染树结构FP 树光看代码很难建立直觉画出来就一目了然。Graphviz 是最省事的方案把节点和边导出成 DOT 格式即可。def export_dot(root, filenamefp_tree.dot): 把 FP 树导出成 Graphviz DOT 文件 lines [digraph FP {, node [shapecircle];] def walk(node, parent_idNone): node_id fn{id(node)} # 节点标签显示项名和计数 lines.append(f {node_id} [label{node.name}\\n{node.count}];) if parent_id: lines.append(f {parent_id} - {node_id};) for child in node.children.values(): walk(child, node_id) walk(root) lines.append(}) with open(filename, w, encodingutf-8) as f: f.write(\n.join(lines)) return filename逻辑说明walk递归遍历树每个节点用id(node)生成唯一 ID标签里带上项名和计数。边从父指向子方向就是插入顺序。导出后用dot -Tpng fp_tree.dot -o fp_tree.png渲染成图片。参数filename是输出路径节点多的时候图会很大建议先在小数据集上验证。4.2 头指针表链表的可视化头指针表把同名节点串成链表这条链是挖掘阶段的关键单独画出来能帮你确认链表有没有挂错。def export_header_links(header, filenameheader_links.dot): 可视化头指针表的链表结构 lines [digraph Header {, rankdirLR;] for item, (count, node) in header.items(): lines.append(f h_{item} [label{item}:{count}, shapebox];) prev fh_{item} cur node idx 0 while cur: nid f{item}_{idx} lines.append(f {nid} [label{cur.count}];) lines.append(f {prev} - {nid};) prev nid cur cur.node_link idx 1 lines.append(}) with open(filename, w, encodingutf-8) as f: f.write(\n.join(lines)) return filename逻辑说明每个项对应一个方框节点显示项名和总频次后面跟着链表上的各个树节点用箭头串起来。rankdirLR让图横向排列链表方向更清楚。参数header就是建树时返回的头指针表node_link指针在build_fp_tree里已经挂好。4.3 用真实数据验证可视化结果拿一个经典的小数据集跑一遍对照图检查树结构对不对。# 经典测试数据集方便人工核对 transactions [ [牛奶, 面包, 尿布], [牛奶, 尿布, 啤酒, 鸡蛋], [面包, 尿布, 啤酒], [牛奶, 面包, 尿布, 啤酒], [牛奶, 面包, 尿布, 鸡蛋], ] header build_header_table(transactions, min_support2) root build_fp_tree(transactions, header) freq_items [] mine_tree(header, min_support2, prefix[], freq_itemsfreq_items) for itemset, cnt in sorted(freq_items, keylambda x: -x[1]): print(f{set(itemset)} 支持度: {cnt}) export_dot(root, fp_tree.dot) export_header_links(header, header_links.dot)逻辑说明这个数据集里尿布出现 5 次、牛奶 4 次、面包 4 次、啤酒 3 次、鸡蛋 2 次min_support2全部保留。跑完对照输出的频繁项集和 DOT 图能直观看到「尿布-牛奶-面包」这条高频路径是怎么共享的。参数上min_support2是这个小数据集的合理值真实数据要按 3.1 的方法重新定。5. 避坑与排查FP-growth 落地时最容易翻车的 5 个点5.1 现象挖掘结果里频繁项集数量爆炸内存直接打满原因min_support设得太低或者数据里存在大量高频短项导致条件树递归层数极深、临时事务列表膨胀。解决先用 3.1 的分位数脚本看频次分布把min_support提到能过滤掉长尾的位置同时给mine_tree加max_depth限制双保险。5.2 现象同一份数据跑两次频繁项集顺序不一样原因头指针表排序时只按频次降序频次相同的项顺序依赖字典插入顺序Python 3.7 之后字典有序但不同数据加载路径可能改变插入顺序。解决排序键加上项名做次级排序也就是keylambda x: (-x[1], x[0])保证结果稳定可复现。5.3 现象树建出来节点数远多于预期压缩率很差原因事务之间前缀重合度低比如每条事务的商品组合几乎不重复FP 树退化成接近原始数据。这不是 bug是数据特性。解决先算一下事务的平均长度和重复前缀比例如果重合度确实低FP-growth 相对 Apriori 的优势有限可以考虑先做商品聚类或降维把相似商品归并后再挖。5.4 现象置信度算出来大于 1 或者提升度为负原因generate_rules里前件支持度查找用了next如果频繁项集列表里没有精确匹配的子集会返回None被跳过但如果有重复项集或计数错误就可能拿到错误的支持度。解决确保freq_items里每个项集唯一建树阶段计数不要重复累加提升度为负说明后件支持度算错检查cons_support是否取到了正确的后件。5.5 现象Graphviz 渲染出来的图节点重叠、看不清原因节点太多、图太大默认布局挤在一起。解决只导出前 N 层节点做局部可视化或者用rankdirTB配合nodesep、ranksep调间距调试阶段建议先用 5.3 里的小数据集确认结构正确后再上真实数据。6. 进阶把 FP-growth 接到真实购物篮流水线上前面都是单机小数据验证真正落地时数据量和工程约束会复杂得多。我一般会按「预处理 → 分块挖掘 → 规则合并 → 可视化抽样」这条链路走。预处理阶段把订单明细聚合成事务列表过滤掉退货、赠品这类噪声项分块挖掘是因为单机内存扛不住全量数据按时间或门店切块每块单独跑 FP-growth再把各块的频繁项集按支持度合并规则合并时注意支持度要按全局事务数重新归一化不能直接相加。def merge_freq_items(block_results, total_trans, min_support): 合并多个数据块的频繁项集按全局支持度过滤 merged {} for itemset, cnt in block_results: key frozenset(itemset) merged[key] merged.get(key, 0) cnt # 按全局支持度重新过滤 return [(list(k), v) for k, v in merged.items() if v min_support]逻辑说明block_results是各块挖出的(项集, 计数)列表用frozenset做 key 保证无序项集能正确合并。合并后按全局min_support再过滤一次避免分块边界效应导致低频组合混进来。参数total_trans用于后续算支持度比例min_support是全局阈值。验证方法上我习惯留一个「后悔药」随机抽 1% 的原始事务用暴力枚举算真实频繁项集和 FP-growth 结果对比确认没有漏挖或错挖。这个对拍步骤在换数据集或调参后必做能挡住大部分玄学问题。可视化在真实数据上不要全量导出节点上万张图没法看。我的习惯是按支持度取 Top 50 的频繁项集只画这些项集涉及的子树配合头指针表链表图足够定位结构问题。最后一句血泪经验FP-growth 的坑八成不在算法本身而在数据预处理和参数选择上先把频次分布摸清楚比急着调代码有用得多。希望帮到你。本文还有配套的精品资源点击获取