★ FEATURED ARTICLE 简介这份资源面向数据挖掘与机器学习初学者及需要落地关联规则分析的开发者围绕FP-growth频繁模式增长算法提供Python实现与FP树可视化工具可用于购物篮分析、频繁项集挖掘与大型数据库中的频繁模式发现。压缩包共11个文件约480KB包含py主程序与whl依赖包、csv交易样例数据、png可视化输出图、md与txt说明文档及docx附赠资料覆盖从代码运行到结果解读的完整链路。已有76人学习下载。读者可借助FPTree.py理解FP树构建与递归挖掘流程结合购物篮分析示例数据复现频繁项集发现过程并通过生成的树结构图直观观察模式组织方式同时对照说明文档排查环境依赖与运行问题适合作为课程实验、算法对比研究或商业场景原型验证的参考素材。1. FP-growth 到底解决了什么问题从 Apriori 的两遍扫描说起购物篮分析里最经典的场景是超市想知道“买了啤酒的人有多大比例会顺手拿尿布”。这件事在数据挖掘里叫关联规则学习核心是先从交易流水里挖出频繁项集再据此生成规则。Apriori 是最早普及的算法但它的痛点很致命——每生成一个候选集就要重新扫一遍数据库交易表一大I/O 直接爆炸。FP-growth频繁模式增长换了个思路只扫两遍数据库把事务压缩进一棵 FP 树之后所有挖掘都在内存里的树上做不再反复读盘。这篇笔记就围绕 FP-growth 的 Python 实现与可视化工具展开把 FP 树结构怎么建、条件模式基怎么递归、树怎么画出来讲透适合已经会写 Python、想真正把频繁项集挖掘跑在大型数据库上的从业者。热词里的关联规则学习、频繁项集挖掘、数据挖掘本质都是这一条链路。2. FP 树构建两遍扫描与节点结构设计2.1 为什么第一遍扫描只数频率FP-growth 的第一遍扫描不做任何挖掘只统计每个单品在所有事务中出现的次数。这一步的目的是拿到每个项的全局支持度计数然后按支持度降序排列得到一个“头指针表”header table。为什么要排序因为 FP 树是一棵前缀树事务里的项按支持度从高到低插入能让高频项尽量靠近根节点树的分支更少、压缩率更高后续递归时条件模式基也更短。如果顺序乱了同一批事务可能长出大量重复路径树会膨胀内存和递归深度都会失控。这一步的产出有两个一个是频繁 1 项集支持度低于 min_support 的项直接丢掉另一个是排序后的频繁项列表。注意低于阈值的项在插入树之前就要过滤掉否则它们会污染树结构让后面挖出来的条件模式基包含大量无意义节点。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} # 按支持度降序排列得到头指针表的顺序 sorted_items sorted(freq.items(), keylambda x: x[1], reverseTrue) header {item: [count, None] for item, count in sorted_items} return header逻辑说明freq字典记录原始计数过滤后只保留频繁项。header的 value 是一个列表第一个元素是计数第二个元素是节点链表的头指针初始为 None。参数min_support是绝对支持度计数不是比例如果你习惯用比例要在调用前乘以事务总数。2.2 第二遍扫描把事务压进树里第二遍扫描才真正建树。对每条事务先按头指针表的顺序重排项然后从根节点开始逐项往下走如果当前节点已有该子节点计数加一没有就新建节点并把它挂到对应项的头指针链表上。头指针链表的作用是后面找某个项的所有出现位置时不用遍历整棵树顺着链表就能拿到所有节点再往上回溯得到条件模式基。节点结构至少要存四个东西项名、计数、父节点引用、子节点字典。父节点引用是必须的因为回溯条件模式基时要一路往根走。子节点用字典而不是列表是为了 O(1) 判断某个项是否已经是子节点。class FPNode: def __init__(self, name, count, parent): self.name name self.count count self.parent parent self.children {} self.node_link None # 指向同项的下一个节点 def insert_tree(trans, header, root): # 事务已按头指针表顺序排好 node root for item in trans: if item in node.children: node.children[item].count 1 else: new_node FPNode(item, 1, node) node.children[item] new_node # 挂到头指针链表 if header[item][1] is None: header[item][1] new_node else: cur header[item][1] while cur.node_link: cur cur.node_link cur.node_link new_node node node.children[item]逻辑说明insert_tree接收一条已排序事务从根往下走。node_link串起所有同名节点方便后续find_prefix_path回溯。参数root是空根节点名字通常设为 None 或 null。这里挂链表用的是尾插实际工程里如果链表很长可以维护一个尾指针数组避免每次 O(n) 遍历。2.3 头指针表与节点链表的配合头指针表不是装饰品它是 FP-growth 递归挖掘的入口。挖掘时从支持度最低的项开始头指针表从后往前对每个项顺着它的 node_link 链表找到所有节点每个节点往上回溯到根就得到一条条件模式基前缀路径。这些路径的计数取该节点的计数因为节点计数代表这条路径被多少事务共享。把所有前缀路径收集起来就构成了这个项的“条件 FP 树”的输入事务集然后递归建树、递归挖掘。这里有个容易翻车的点回溯时不要把当前项自己算进去条件模式基是“前缀”不含后缀项。另外路径计数不是简单累加而是取路径末端节点的计数因为一条路径可能被多个事务共享节点计数已经代表了共享次数。3. 递归挖掘频繁项集条件模式基怎么取3.1 从叶子往上为什么从低频项开始挖FP-growth 的挖掘顺序是从头指针表的尾部支持度最低的频繁项往头部走。原因是低频项的条件模式基更短、更集中递归深度小先挖它能把长频繁项集逐步拆解。如果从高频项开始条件树会很大递归分支爆炸。这个顺序不是随便定的是 FP-growth 能比 Apriori 快的关键之一。对每个项拿到它的所有前缀路径后把这些路径当成新的事务集重新统计频率、过滤、建一棵条件 FP 树。如果条件 FP 树只有单条路径直接枚举这条路径上所有子集与当前项组合就是频繁项集如果有多条分支继续递归。def mine_tree(header, min_support, prefix, freq_items): # 按支持度升序处理即从头指针表尾部开始 sorted_items sorted(header.items(), keylambda x: x[1][0]) for item, (count, node) in sorted_items: new_prefix prefix.copy() new_prefix.add(item) freq_items.append((new_prefix, count)) # 收集条件模式基 cond_paths [] cur node while cur: path [] parent cur.parent while parent and parent.name is not None: path.append(parent.name) parent parent.parent if path: cond_paths.append((path, cur.count)) cur cur.node_link # 用条件模式基建条件 FP 树 cond_header build_header_table( [p for p, c in cond_paths for _ in range(c)], min_support) if cond_header: cond_root FPNode(None, 0, None) for p, c in cond_paths: # 按条件头表顺序重排 ordered [i for i in sorted(cond_header, keylambda x: cond_header[x][0], reverseTrue) if i in p] insert_tree(ordered, cond_header, cond_root) mine_tree(cond_header, min_support, new_prefix, freq_items)逻辑说明mine_tree递归处理每个项。cond_paths收集前缀路径和对应计数。建条件树时事务要按条件头表顺序重排这一步不能省否则树结构会乱。freq_items累积所有频繁项集及其支持度。参数prefix是当前已选中的项集合递归时不断扩展。3.2 单路径优化能省一次递归就省当条件 FP 树只有一条路径时不需要再递归建树。直接枚举这条路径上所有非空子集与当前前缀组合每个组合的支持度取路径上最小的节点计数。这个优化在稀疏数据集上效果明显能砍掉大量无意义的递归调用。判断单路径的方法很简单从根往下走如果每个节点只有一个子节点直到叶子就是单路径。def is_single_path(root): node root while node: if len(node.children) 1: return False if not node.children: return True node next(iter(node.children.values())) return True逻辑说明is_single_path从根往下遇到分支就返回 False走到叶子返回 True。单路径枚举时路径上的项按从头到尾的顺序支持度取路径上各节点计数的最小值因为组合的支持度受最弱环节限制。3.3 支持度与置信度规则生成的两个阈值频繁项集挖出来后生成关联规则还要算置信度。对每个频繁项集枚举它的非空真子集作为前件剩余部分作为后件置信度 项集支持度 / 前件支持度。只有置信度不低于 min_conf 的规则才保留。注意前件支持度必须从频繁项集结果里查不能重新扫数据库否则又退化成 Apriori 了。参数含义常用取值影响min_support最小支持度计数2~5小数据集越低项集越多树越大min_conf最小置信度0.5~0.8越高规则越少越可靠max_len最大项集长度3~5限制递归深度防爆炸提示min_support 用绝对计数比用比例更直观尤其在事务数变化时不用反复换算。如果数据量很大先跑一遍频率分布再定阈值。4. FP 树可视化把黑匣子画出来4.1 用 Graphviz 画树结构FP 树不画出来调试时就是黑匣子。常见做法是用 Graphviz 的 Python 绑定把每个节点画成带项名和计数的框父子关系画成有向边头指针链表用虚线连起来。这样一眼就能看出哪些分支被压缩了、哪些项计数异常。from graphviz import Digraph def visualize_tree(root, header, filenamefp_tree): dot Digraph(commentFP Tree) dot.attr(node, shapebox) def add_nodes(node, parent_idNone): if node.name is None: node_id root dot.node(node_id, root) else: node_id f{node.name}_{id(node)} dot.node(node_id, f{node.name}:{node.count}) if parent_id: dot.edge(parent_id, node_id) for child in node.children.values(): add_nodes(child, node_id) add_nodes(root) # 画头指针链表 for item, (count, node) in header.items(): prev None cur node while cur: cur_id f{cur.name}_{id(cur)} if prev: dot.edge(prev, cur_id, styledashed, colorred) prev cur_id cur cur.node_link dot.render(filename, formatpng, cleanupTrue)逻辑说明add_nodes递归遍历树节点 ID 用项名加id(node)保证唯一。头指针链表用红色虚线连接和树边区分开。参数filename是输出文件名cleanupTrue会删掉中间文件只留 png。如果树很大Graphviz 布局会挤可以只画前几层或者用rankdirLR改成横向。4.2 交互式可视化用 Pyecharts 做可缩放树Graphviz 适合静态图树一大就糊。交互式场景可以用 Pyecharts 的 Tree 图支持缩放和折叠。把 FP 树转成嵌套字典每个节点带 name 和 value计数Pyecharts 会自动布局。这样在浏览器里能逐层展开适合给非技术同事看。from pyecharts.charts import Tree from pyecharts import options as opts def tree_to_dict(node): if node.name is None: name root else: name f{node.name}({node.count}) children [tree_to_dict(c) for c in node.children.values()] return {name: name, children: children} def render_interactive(root, filenamefp_tree.html): data [tree_to_dict(root)] tree Tree() tree.add(, data, collapse_interval2) tree.set_global_opts(title_optsopts.TitleOpts(titleFP Tree)) tree.render(filename)逻辑说明tree_to_dict把节点转成 Pyecharts 需要的嵌套结构collapse_interval2表示默认展开两层。参数filename是输出 HTML 路径。这种方式不依赖本地 Graphviz但节点多了浏览器会卡建议先剪枝再画。4.3 频繁项集的支持度分布图除了树还值得画一张频繁项集的支持度分布图横轴是项集长度纵轴是支持度用散点或箱线图看分布。这样能快速判断 min_support 设得合不合理——如果大部分项集支持度都贴着阈值说明阈值偏高漏掉了长尾模式如果支持度分布很散说明数据本身模式丰富。import matplotlib.pyplot as plt def plot_support_dist(freq_items): lengths [len(items) for items, _ in freq_items] supports [sup for _, sup in freq_items] plt.scatter(lengths, supports, alpha0.5) plt.xlabel(Itemset Length) plt.ylabel(Support) plt.title(Support Distribution of Frequent Itemsets) plt.savefig(support_dist.png)逻辑说明freq_items是(set, support)列表。散点图能看出长项集的支持度是否骤降。参数alpha控制透明度点重叠时能看出密度。如果支持度取了对数记得在纵轴标注。5. 避坑与排查FP-growth 落地时的五个血泪经验5.1 现象树节点数远超事务数内存爆了原因插入事务前没有按头指针表顺序重排导致同一批项在不同事务里顺序不一致树无法共享前缀每个事务几乎长出一条独立路径。解决在insert_tree之前对每条事务执行ordered [i for i in header_order if i in trans]确保全局顺序一致。5.2 现象递归深度过大Python 报 RecursionError原因数据集里存在大量长事务且 min_support 设得太低条件树分支多、递归层数深。解决设置sys.setrecursionlimit(10000)只是临时手段根本办法是提高 min_support 或加max_len限制项集长度。另外可以把递归改成显式栈避免爆栈。5.3 现象挖出来的规则置信度算错原因前件支持度没有从频繁项集结果里查而是重新扫库统计导致计数口径不一致。解决把频繁项集存成字典{frozenset: support}生成规则时直接查字典。注意项集用 frozenset 做 key普通 set 不可哈希。5.4 现象头指针链表断了漏挖项集原因挂链表时只挂了第一个节点后续节点没接上或者多线程建树时链表被并发修改。解决单线程建树挂链表时用尾插并维护尾指针。如果必须并发每个项独立加锁或者先分片建树再合并。5.5 现象可视化图节点重叠根本看不清原因树太深或太宽Graphviz 默认布局挤在一起。解决只画支持度 top-N 的子树或者用dot.attr(ranksep1.5, nodesep0.5)加大间距。交互式图用collapse_interval控制默认展开层数让用户自己点开。6. 进阶技巧把 FP-growth 用在真实购物篮数据上真实交易数据往往是稀疏的而且存在大量一次性商品。直接跑 FP-growth 会被这些低频项拖慢。我一般会先做一步预处理统计每个商品的出现次数把低于某个绝对阈值的商品直接过滤掉再跑 FP-growth。这一步和算法内部的第一遍扫描不冲突但能大幅减小输入规模。另一个技巧是分块挖掘把交易按时间或门店分片每片单独挖再合并频繁项集。合并时注意支持度要按全局事务数重新折算不能直接相加。验证挖掘结果是否靠谱我习惯用两个手段一是抽几条规则人工核对看前件后件在业务上是否说得通二是把 min_support 调高一档再跑看高频规则是否稳定。如果两次结果差异很大说明阈值卡在了模式分布的陡坡上需要重新选点。参数上购物篮数据通常 min_support 取总事务数的 0.5%~2%min_conf 取 0.5~0.7max_len 限制在 4 以内避免组合爆炸。最后说个我踩过的坑有次为了追求“全量挖掘”把 min_support 设成 1结果树大到内存扛不住跑了一夜没出结果。后来改成先按商品频次过滤再设 min_support3十分钟就跑完了规则质量反而更高。频繁项集挖掘不是越多越好阈值选对了长尾模式自己会浮出来。希望帮到你。本文还有配套的精品资源点击获取
阅读完成 · 觉得有帮助？
