简介这份资源是面向数据挖掘初学者与MATLAB使用者的FP-Growth关联规则挖掘实现包用于在交易数据中高效发现频繁项集并提取关联规则可应用于市场篮子分析、网络行为分析等场景。压缩包共8个文件以7个.m脚本文件和1个.mat数据集为主脚本分别承担主流程调度、FP树构建、幂集与子集生成、规则展示及树结构可视化等职责mydata数据集用于演示算法运行整体约5KB轻量易读。已有191人学习下载。读者可借此理解FP-Growth通过FP树存储频繁项集、减少数据扫描次数的核心思路掌握从预处理、构造FP树、生成条件模式基到递归挖掘与规则提取的完整流程并可通过修改数据集与支持度阈值迁移到自己的应用场景为后续复杂数据挖掘任务打下基础。1. 从一份 FP-Growth 关联规则挖掘压缩包说起它到底能解决什么问题你手上有一份名为FP-Growth Assiciation Rule Mining.rar的压缩包名字里两个关键词已经把技术路线钉死了FP-Growth 和 Association Rule Mining。前者是频繁模式树的构建与挖掘算法后者是关联规则挖掘这个任务本身。很多人第一次接触它是在购物篮分析、推荐系统召回、日志共现分析或者故障根因定位这类场景里——手里有一堆事务型数据想知道“买了 A 的人还会买什么”“出现告警 X 之后通常跟着告警 Y”。Apriori 能算但候选集爆炸和多次扫库会让它在中等规模数据上就喘不过气FP-Growth 用一棵压缩前缀树把事务压进去只扫两遍数据库再递归挖条件模式基这就是它值得单独打包一份代码来跑的原因。这份压缩包适合两类人一类是要快速跑通关联规则、拿到可解释规则集的算法工程师另一类是想搞懂 FP-Tree 到底怎么建、怎么挖而不满足于调库的开发者。下面我按“先立住原理、再动手复现、最后讲坑”的顺序把它拆开。2. FP-Growth 的算法骨架为什么它比 Apriori 少扫库2.1 从频繁项集到关联规则的两段式任务关联规则挖掘的标准定义是给定事务集合 $D$每条事务是若干项的集合我们要找出所有满足最小支持度min_sup的频繁项集再从频繁项集里生成满足最小置信度min_conf的规则 $X \rightarrow Y$。支持度是 $X \cup Y$ 出现的比例置信度是 $P(Y|X)$。这里有两个必须记住的边界支持度是“同时出现”的频次占比置信度是条件概率两者不能混。很多人第一次翻车就是把置信度当成支持度去筛结果规则数量爆炸还全是噪声。Apriori 的做法是逐层生成候选集每层都要重新扫一遍数据库来验证支持度数据库一大I/O 就是瓶颈。FP-Growth 换了个思路先把整个数据库压进一棵 FP-Tree树上的每个节点记录项和计数共享前缀的事务会合并到同一条路径上这样数据库的共现结构被一次性编码进内存。之后挖掘频繁项集不再扫库而是在树上递归地构造条件模式基和条件 FP-Tree。这就是它“只扫两遍库”的由来第一遍统计每个项的支持度并过滤掉低于min_sup的项第二遍按支持度降序把每条事务插入树。2.2 FP-Tree 的构建排序、过滤、插入三步构建 FP-Tree 的核心动作只有三步但每一步都有参数和顺序讲究。第一步扫库统计单项频次丢弃低于min_sup的项这叫“过滤低频项”。第二步对每条事务里的项按全局支持度降序排列这一步是 FP-Tree 能共享前缀的前提顺序不一致树就退化成普通前缀树压缩效果大打折扣。第三步逐条插入遇到相同前缀就复用节点并累加计数遇到新项就开分支同时维护一个头表header table把每个项的所有节点用链表串起来方便后续从底向上挖条件模式基。下面这段 Python 用纯字典和列表实现 FP-Tree 的构建不依赖任何第三方库方便你直接对照压缩包里的实现看差异# fp_tree_build.py # 纯 Python 实现 FP-Tree 构建便于理解压缩包内算法的数据结构 class FPNode: def __init__(self, name, count, parent): self.name name # 项名 self.count count # 计数 self.parent parent # 父节点 self.children {} # 子节点字典 self.node_link None # 头表链表指针 def increment(self, cnt): self.count cnt def build_fp_tree(transactions, min_sup): # 第一遍统计单项支持度 header {} for trans in transactions: for item in trans: header[item] header.get(item, 0) 1 # 过滤低频项保留满足 min_sup 的项 header {k: v for k, v in header.items() if v min_sup} if not header: return None, None # 头表项 - [计数, 链表头节点] header_table {k: [v, None] for k, v in header.items()} root FPNode(Null Set, 1, None) # 第二遍按支持度降序插入每条事务 for trans in transactions: # 只保留频繁项并按全局支持度降序排序 filtered [item for item in trans if item in header] filtered.sort(keylambda x: header[x], reverseTrue) cur root for item in filtered: if item in cur.children: cur.children[item].increment(1) else: new_node FPNode(item, 1, cur) cur.children[item] new_node # 更新头表链表 if header_table[item][1] is None: header_table[item][1] new_node else: node header_table[item][1] while node.node_link: node node.node_link node.node_link new_node cur cur.children[item] return root, header_table逻辑说明header先做全局频次统计min_sup是绝对计数还是比例取决于你传入的数值压缩包里常见做法是传比例再乘以事务总数换算成计数。filtered.sort的排序键是全局支持度不是事务内顺序这一点如果写反树会变得又宽又深。头表链表用尾插法维护保证从任意节点都能顺着node_link找到同项的所有出现位置这是后续挖掘条件模式基的入口。参数上min_sup设得越高树越小、规则越少设得越低树越稠密、递归越深内存和时间都会上去。2.3 条件模式基与递归挖掘从叶子往上找前缀路径树建好之后挖掘从支持度最低的项开始因为它在头表链表里对应的路径最短。对每个项沿着node_link找到所有节点从每个节点往父节点回溯得到一条前缀路径路径上每个节点的计数取该节点的计数这些路径合起来就是“条件模式基”。把条件模式基当成新的事务集合重新统计频次、过滤、建一棵条件 FP-Tree然后递归下去。递归的终止条件是条件 FP-Tree 只剩单条路径这时直接枚举这条路径上所有子集与当前后缀的组合即可。# fp_growth_mine.py # 递归挖掘频繁项集 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(tree_node): # 收集某个项的所有条件模式基 paths {} while tree_node is not None: path ascend_tree(tree_node) if path: paths[tuple(path)] paths.get(tuple(path), 0) tree_node.count tree_node tree_node.node_link return paths def mine_tree(header_table, min_sup, prefix, freq_items): # 按支持度升序处理头表项 sorted_items sorted(header_table.items(), keylambda x: x[1][0]) for item, (count, node) in sorted_items: new_prefix prefix [item] freq_items.append((new_prefix, count)) # 构造条件模式基 cond_paths find_prefix_paths(node) # 用条件模式基重建事务列表 cond_trans [] for path, cnt in cond_paths.items(): cond_trans.extend([list(path)] * cnt) # 递归建条件 FP-Tree cond_root, cond_header build_fp_tree(cond_trans, min_sup) if cond_header: mine_tree(cond_header, min_sup, new_prefix, freq_items)逻辑说明ascend_tree返回的是从根到当前节点的项序列find_prefix_paths把同项所有节点的前缀路径按计数累加得到条件模式基。mine_tree里对头表按计数升序排序是为了先挖支持度低的项减少后续递归的搜索空间。cond_trans.extend([list(path)] * cnt)是把路径按计数展开成事务这一步在数据量大时是内存热点压缩包里如果做了优化通常会用生成器或直接传计数而不是展开。参数上递归深度受最长事务长度限制min_sup在递归中保持不变但条件 FP-Tree 的规模会逐层缩小。3. 把压缩包跑起来环境、入口与最小复现路径3.1 解压后的目录结构与入口判断拿到FP-Growth Assiciation Rule Mining.rar第一步不是急着跑而是先看清里面是什么。常见做法是先解压到一个干净目录用tree或find列出文件判断它是纯脚本、带 notebook还是带数据集和配置。典型的关联规则挖掘包会有这么几类文件算法实现fp_growth.py或fp_tree.py、数据加载与预处理脚本、一个main或run入口、示例数据集.txt/.csv/.dat以及依赖说明。如果压缩包里只有算法文件没有入口你就得自己写一个最小驱动脚本把数据读进来、调算法、输出规则。# 解压并查看结构 mkdir -p fp_growth_work cd fp_growth_work # 假设压缩包在当前目录的上一级 unrar x ../FP-Growth\ Assiciation\ Rule\ Mining.rar # 或者用 7z / unzip 视实际格式而定 find . -maxdepth 3 -type f | sort逻辑说明unrar x保留目录结构解压find列出三层以内的文件先确认有没有requirements.txt、README或入口脚本。如果压缩包里是.py文件直接看文件头的 import 判断依赖如果是 notebook注意单元格执行顺序notebook 最容易出现“跳着跑就报未定义”的问题。参数上解压路径不要带空格和中文很多老脚本对路径编码处理不干净带空格会直接报文件找不到。3.2 数据格式与最小可跑数据集关联规则挖掘的输入是事务集合常见格式有两种一种是每行一条事务、项之间用空格或逗号分隔比如bread milk beer另一种是稀疏矩阵或 one-hot 编码的 CSV。压缩包里的示例数据大概率是第一种因为 FP-Growth 天然吃这种格式。如果你要换成自己的数据先做一件事确认每行的项没有重复重复项会导致计数虚高。下面是一个最小数据集和读取脚本# load_data.py # 读取空格分隔的事务数据返回列表的列表 def load_transactions(path): transactions [] with open(path, r, encodingutf-8) as f: for line in f: line line.strip() if not line: continue # 按空格切分过滤空项 items [x for x in line.split() if x] # 去重避免同一事务内重复项干扰计数 items list(dict.fromkeys(items)) transactions.append(items) return transactions if __name__ __main__: trans load_transactions(sample.dat) print(事务数:, len(trans)) print(首条事务:, trans[0] if trans else 空)逻辑说明dict.fromkeys在保持顺序的前提下去重比set更安全因为后续排序依赖项的顺序稳定性。encodingutf-8要显式写Windows 默认编码读中文项名会乱码。参数上如果你的数据项本身包含空格就不能用空格切分得换成制表符或逗号并在读取时对应调整split的分隔符。3.3 跑通一次完整挖掘支持度、置信度与规则输出最小复现路径是加载数据 → 建 FP-Tree → 挖频繁项集 → 生成关联规则 → 输出。生成规则时对每个频繁项集枚举它的非空真子集作为前件剩余部分作为后件计算置信度过滤掉低于min_conf的规则。下面这段把前面的构建和挖掘串起来并加上规则生成# run_mining.py from fp_tree_build import build_fp_tree from fp_growth_mine import mine_tree from load_data import load_transactions from itertools import combinations def generate_rules(freq_items, min_conf): rules [] for itemset, support in freq_items: if len(itemset) 2: continue for i in range(1, len(itemset)): for antecedent in combinations(itemset, i): consequent tuple(x for x in itemset if x not in antecedent) # 计算前件支持度 ant_support None for s, sup in freq_items: if set(s) set(antecedent): ant_support sup break if ant_support and support / ant_support min_conf: rules.append((antecedent, consequent, support, support / ant_support)) return rules if __name__ __main__: transactions load_transactions(sample.dat) min_sup_count 2 # 绝对支持度计数 min_conf 0.6 # 最小置信度 root, header build_fp_tree(transactions, min_sup_count) freq_items [] if header: mine_tree(header, min_sup_count, [], freq_items) rules generate_rules(freq_items, min_conf) for ant, con, sup, conf in sorted(rules, keylambda x: -x[3])[:20]: print(f{ant} - {con} 支持度{sup} 置信度{conf:.2f})逻辑说明min_sup_count这里用绝对计数和build_fp_tree里的过滤逻辑对应如果你习惯用比例就在加载后乘以事务总数换算。generate_rules里对每个频繁项集枚举前件combinations保证不重复ant_support从前件对应的频繁项集里取取不到就跳过。参数上min_conf设 0.6 到 0.8 之间通常能得到可读性较好的规则设太低会输出大量弱关联设太高可能一条规则都没有。输出按置信度降序取前 20 条方便快速看效果。4. 参数调优与性能边界支持度、置信度和内存怎么权衡4.1 min_sup 的设定从数据分布反推而不是拍脑袋min_sup是 FP-Growth 里最敏感的参数它直接决定树的大小和递归深度。设得太高频繁项集少、规则少可能漏掉有价值的弱关联设得太低树会变得极稠密内存和时间都飙升甚至递归爆栈。我的习惯是先做一次单项频次统计看支持度的分布再选一个能过滤掉长尾但保留头部共现的值。比如事务总数 10 万你希望一个项至少出现 500 次才参与挖掘那min_sup就是 0.005 或绝对计数 500。下面这段帮你快速看分布# sup_distribution.py from collections import Counter from load_data import load_transactions trans load_transactions(sample.dat) counter Counter() for t in trans: counter.update(t) total len(trans) print(事务总数:, total) for item, cnt in counter.most_common(20): print(f{item}: 计数{cnt} 支持度{cnt/total:.4f})逻辑说明Counter.update累加所有事务的项频次most_common(20)看头部项的分布。如果头部项支持度都在 0.1 以上而长尾项低于 0.001min_sup取 0.01 左右通常能兼顾效果和性能。参数上这个脚本只做诊断不参与挖掘但它是你定min_sup的依据比反复试错快得多。4.2 置信度与提升度别只看置信度选规则置信度高不代表规则有价值因为后件本身可能就很频繁。比如“买牛奶 → 买面包”置信度 0.9但如果面包本身在 90% 的事务里都出现这条规则等于没说。这时候要看提升度lift定义是置信度 / 后件支持度大于 1 才说明前件对后件有正向提升。压缩包里如果只输出支持度和置信度建议自己补一列提升度。下面是在规则生成里加提升度的改法# 在 generate_rules 中补充后件支持度查询 def consequent_support(consequent, freq_items): for s, sup in freq_items: if set(s) set(consequent): return sup return None # 计算 lift conf / (consequent_support / total_transactions)逻辑说明后件支持度同样从频繁项集里查查不到说明后件不是频繁项规则本身也不该保留。lift 1表示正相关lift 1表示独立lift 1表示负相关。参数上我一般会同时卡min_conf 0.6和lift 1.2这样输出的规则既有强度又有增量价值。4.3 大数据下的内存控制条件模式基展开是热点前面提到cond_trans.extend([list(path)] * cnt)在数据量大时会吃内存因为一条路径按计数展开可能变成几千条事务。优化方向有两个一是用生成器惰性产出事务二是在建条件 FP-Tree 时直接传“路径 计数”而不是展开。压缩包里如果没做这层优化你在百万级事务上跑就会看到内存曲线陡增。另一个边界是递归深度Python 默认递归限制 1000长事务数据可能触发RecursionError可以通过sys.setrecursionlimit临时放宽但更稳的做法是把递归改成显式栈。参数上如果单条事务平均长度超过 50就要警惕递归深度和条件模式基的规模。5. 避坑与排查FP-Growth 落地时最容易翻车的 5 个点5.1 现象规则数量为 0但数据明明有共现原因通常是min_sup设成了比例却按绝对计数传或者反过来。比如事务总数 1000你传min_sup0.01给按计数过滤的函数等于要求项出现至少 0.01 次所有项都通过树巨大反过来传min_sup100给按比例过滤的函数等于要求支持度 100一条规则都出不来。解决在入口处统一单位打印一次min_sup的实际值和事务总数确认量纲一致。5.2 现象同一事务内重复项导致支持度虚高原因是你没去重一条事务里milk milk bread被当成两个 milk计数比实际多。解决加载数据时用dict.fromkeys或set去重但注意set会打乱顺序如果后续依赖顺序用保序去重。这个坑在日志共现分析里特别常见因为日志里同一条消息可能重复出现。5.3 现象树建好了但挖掘结果和 Apriori 对不上原因多半是排序键写错。FP-Tree 要求按全局支持度降序插入如果你按项名字母序或事务内顺序排树的结构会变虽然理论上频繁项集不变但条件模式基的构造会受影响某些实现下会漏项。解决确认filtered.sort(keylambda x: header[x], reverseTrue)这一行没被改且header是过滤后的频次表。5.4 现象递归挖掘报 RecursionError 或跑很久不结束原因是min_sup太低导致条件 FP-Tree 一直有分支递归深度超过 Python 限制或者条件模式基展开后事务数爆炸。解决先提高min_sup看是否缓解如果业务上不能提高就把递归改成显式栈或者对条件模式基做采样。另一个检查点是头表链表是否有环链表维护写错会导致find_prefix_paths死循环。5.5 现象规则里出现单一项的前件或后件原因是生成规则时没有过滤len(itemset) 2或者枚举子集时允许了空集。解决在generate_rules开头加if len(itemset) 2: continue并确保combinations的i从 1 到len(itemset)-1这样前件和后件都非空。这个坑不致命但会让输出很难看评审时容易被质疑。6. 进阶技巧用规则做召回排序与增量更新跑通基础挖掘之后真正体现价值的是把规则用起来。我一般会把规则按lift和confidence加权打分用于推荐召回对用户已购项匹配所有前件包含这些项的规则把后件作为候选分数用confidence * lift排序。这样比单纯按置信度排更能压掉热门项的干扰。另一个进阶点是增量更新数据每天新增全量重建 FP-Tree 成本高可以维护一个增量事务缓冲定期合并后重建或者对新增数据单独挖规则再和旧规则做并集去重。下面是一个规则打分的片段# rule_scoring.py def score_rules(rules, user_items): # rules: [(antecedent, consequent, support, confidence, lift)] candidates {} user_set set(user_items) for ant, con, sup, conf, lift in rules: if set(ant).issubset(user_set): for item in con: score conf * lift if item not in candidates or score candidates[item]: candidates[item] score return sorted(candidates.items(), keylambda x: -x[1])逻辑说明set(ant).issubset(user_set)判断用户已购项是否覆盖规则前件覆盖则后件进候选分数取conf * lift同一后件保留最高分。参数上lift建议在规则生成阶段就算好并存入规则元组避免打分时重复查表。这个打分函数可以直接接在召回层后面作为一路特征。最后说个我自己的习惯每次跑完 FP-Growth我都会把规则按前件长度分组看一遍长度 1 的前件规则用于冷启动召回长度 2 以上的用于精细化推荐如果某一组数量异常少或异常多先回去查min_sup和去重逻辑而不是急着调模型。这套流程我踩过不少坑希望帮到你。本文还有配套的精品资源点击获取