20 Python 关联分析：数据量大了，Apriori 太慢怎么办？一文入门 FP-Growth 算法

Python 数据分析入门数据量大了Apriori 太慢怎么办一文入门 FP-Growth 算法适合人群Python 初学者 / 数据分析入门 / 数据挖掘入门 / 教学案例分享在前面的学习里我们已经知道可以通过关联分析找出商品之间的关系可以用 Apriori 挖掘频繁项集还可以从频繁项集生成真正可用的关联规则但是当数据量越来越大时一个很现实的问题就来了Apriori 太慢了怎么办这不是算法“不会用”而是因为 Apriori 本身就存在明显的效率瓶颈候选项集太多数据库要反复扫描数据一大运行就会明显变慢这时候就需要一种更高效的方法来替代它。这就是本文要介绍的内容FP-Growth 算法它是频繁项集挖掘中的经典方法之一最大的特点是不生成候选项集直接发现频繁模式。本文继续沿用“校园超市购物小票分析”这个案例带你理解为什么 Apriori 会慢FP-Growth 改进了什么FP 树到底是干什么的Apriori 和 FP-Growth 有什么区别如何用 Python 完成 FP-Growth 挖掘摘要在频繁项集挖掘中Apriori 是最经典的入门算法但当数据量增大时容易出现候选项集过多、数据库反复扫描等效率问题。FP-Growth 通过“不生成候选项集”的方式结合 FP 树实现频繁模式增长通常能更高效地完成挖掘任务。本文以校园超市购物小票为案例介绍 Apriori 的效率瓶颈、FP-Growth 的核心思想、FP 树的基本作用以及如何使用 Python 完成 FP-Growth 频繁项集挖掘帮助初学者建立对关联分析方法体系的整体认识。一、导语频繁项集已经会找了为什么还要学 FP-Growth前面我们已经可以使用 Apriori 找出高频商品组合比如{面包, 牛奶}{尿布, 啤酒}{面包, 牛奶, 尿布}对于小规模数据来说这已经足够完成很多基础分析任务。但如果把场景换成真实超市就会出现新问题每天的小票不再是 5 张而是几千张、几万张商品不再只有几个而是上百种、上千种组合数量会快速膨胀这时候很多初学者会发现同样的 Apriori 代码数据一大就跑得很慢。所以问题不再是“能不能找出频繁项集”而是能不能更高效地找出频繁项集这正是 FP-Growth 要解决的问题。二、先回顾一下Apriori 为什么会慢Apriori 的基本思路是一种很典型的“逐层搜索”先找频繁 1 项集再找频繁 2 项集再找频繁 3 项集一层一层向上扩展这种思路很适合教学因为逻辑清晰便于理解。但它的性能问题也很明显。1候选项集太多Apriori 在每一层都要先生成一批候选项集再检查它们是否满足支持度要求。问题在于商品种类一多候选组合数量会增长得非常快。比如商品只有 5 种时组合还比较有限但如果商品有 100 种、1000 种候选项集数量就会变得非常惊人。2数据库需要反复扫描Apriori 每产生一层候选项集就要去数据库里重新统计一次支持度。也就是说找 1 项集扫一遍数据库找 2 项集再扫一遍找 3 项集还要继续扫当数据量很大时这种“反复扫描数据库”的成本会非常高。3真正影响性能的是“找频繁项集”这一步在关联分析任务中性能开销最大的部分往往就是频繁项集挖掘本身。一旦候选项集过多或者扫描次数过多算法效率就会明显下降。所以你可以把 Apriori 的问题简单记成一句话候选太多扫描太勤所以数据一大就容易变慢。三、有没有办法改进这就轮到 FP-Growth 出场了面对 Apriori 的效率问题FP-Growth 给出的核心改进思路是不生成候选项集直接发现频繁模式。这句话非常关键也是 FP-Growth 最核心的优势。和 Apriori 相比Apriori先生成候选再筛选频繁项集FP-Growth不大量生成候选而是先压缩数据再从压缩结构中挖掘结果也就是说FP-Growth 的思路不是“枚举越来越多的组合”而是把原始事务数据压缩保存起来再从压缩后的结构中逐步挖掘频繁模式。这也是它效率更高的根本原因。四、FP-Growth 的核心结构FP 树到底是什么FP-Growth 中最关键的结构叫做FP 树Frequent Pattern Tree很多同学第一次看到“树”就会紧张其实在入门阶段你可以先把它理解成一句话FP 树是一种用来压缩事务数据的树形结构。它的核心作用不是“好看”而是“省事”把重复出现的交易前缀合并起来减少数据冗余为后续挖掘频繁模式做准备为什么可以压缩因为很多购物记录之间其实会有相同部分。还是用这组校园超市数据transactions[[面包,牛奶],[面包,尿布,啤酒,鸡蛋],[牛奶,尿布,啤酒,可乐],[面包,牛奶,尿布,啤酒],[面包,牛奶,尿布,可乐]]这几张小票里很容易发现面包经常出现牛奶经常出现尿布也经常出现[2]如果一条条原样存储会有很多重复信息。FP 树就是把这些重复路径尽量合并从而达到“压缩数据”的效果。五、FP-Growth 的基本思路怎么理解最简单FP-Growth 的过程可以先粗略理解成 4 步第一步先找出频繁 1 项集先统计每个商品出现的次数筛掉不满足最小支持度的商品。这一点和前面 Apriori 的开始阶段是相似的。第二步按频率重新排序事务把每张小票中的商品按“全局频率从高到低”排序。这样做的好处是高频项更容易形成公共前缀更利于压缩进 FP 树。第三步构建 FP 树把排好序的事务逐条插入树中相同路径共用节点不同路径再分叉。这样就可以把大量重复信息压缩到一棵树里。第四步从 FP 树中挖掘频繁模式接下来就不是靠生成候选集了而是通过条件模式基条件 FP 树模式增长一步步把频繁项集挖掘出来这一部分在初学阶段会稍微抽象一点但你不必一开始就把树的递归过程全吃透。先记住核心思想就够了Apriori 靠候选生成找频繁项集FP-Growth 靠树结构和模式增长找频繁项集。六、条件模式基、条件 FP 树初学者怎么理解这两个概念往往是 FP-Growth 里最抽象的地方。如果你是第一次学不必追求特别严格的形式化定义可以先这样理解1条件模式基它可以理解为某个目标项在原 FP 树中出现时它前面路径的集合。也就是为了研究“某个项”经常和谁一起出现我们把和它有关的前缀路径收集起来。2条件 FP 树把这些前缀路径再压缩一下就会形成这个目标项对应的“条件 FP 树”。然后算法继续在这棵更小的树上递归挖掘。初学阶段怎么记你可以先不用死抠定义先记这句话条件模式基是“和某个项相关的路径集合”条件 FP 树是“把这些路径再压缩后得到的子树”。理解到这个程度已经足够建立入门认识了。七、Apriori 和 FP-Growth到底有什么区别这是这一课最重要的比较点之一。下面直接用表格总结对比维度AprioriFP-Growth核心思路逐层搜索、连接剪枝压缩存储、模式增长是否生成候选项集是否数据扫描次数多次更少适合什么场景小数据、教学入门大数据、效率要求高理解难度较低略高核心结构候选项集FP 树你可以把它们的区别浓缩成两句话Apriori一层一层找边生成边筛选FP-Growth先压缩数据再从树里往外长模式八、继续用校园超市案例为什么超市更想要 FP-Growth假设校园超市刚开始只有很少的交易记录Apriori 完全可以胜任。但随着时间推移数据量不断增加一天几十条交易一天几千条交易一学期累计上万条交易这时候超市最关心的不只是“能不能分析”而是能不能分析得更快。Apriori 在这种情况下容易遇到的问题就是候选项集暴增数据库反复扫描运行时间变长而 FP-Growth 通过 FP 树压缩事务数据又避免了大规模候选生成所以更适合这类大数据场景。也就是说当数据规模变大时FP-Growth 往往比 Apriori 更有优势。九、Python 实操用 FP-Growth 挖掘频繁项集如果你的 Python 环境支持mlxtend那么可以直接使用fpgrowth来完成挖掘。1准备数据importpandasaspdfrommlxtend.preprocessingimportTransactionEncoderfrommlxtend.frequent_patternsimportfpgrowth transactions[[面包,牛奶],[面包,尿布,啤酒,鸡蛋],[牛奶,尿布,啤酒,可乐],[面包,牛奶,尿布,啤酒],[面包,牛奶,尿布,可乐]]这组数据和前面 Apriori、关联规则部分使用的是同一组校园超市购物小票数据[2][3]。2先做 One-Hot 编码和 Apriori 一样先把交易数据转换成布尔矩阵。也就是一张“商品勾选表”每一行是一张购物小票每一列是一个商品买了记True没买记False代码如下teTransactionEncoder()te_arrayte.fit(transactions).transform(transactions)dfpd.DataFrame(te_array,columnste.columns_)print(df)3使用 FP-Growth 挖掘频繁项集freq_items_fpfpgrowth(df,min_support0.6,use_colnamesTrue)print(FP-Growth挖掘结果)print(freq_items_fp)这里min_support0.6表示最小支持度为 0.6总共 5 条交易记录所以支持度 0.6 表示至少出现在 3 条交易中4结果怎么理解输出结果通常会包含两列supportitemsets例如可能看到类似结果support itemsets00.8(面包)10.8(牛奶)20.8(尿布)30.6(啤酒)40.6(面包,牛奶)50.6(尿布,牛奶)60.6(面包,尿布)70.6(尿布,啤酒)80.6(面包,尿布,牛奶)这说明面包、牛奶、尿布是高频单项尿布和啤酒经常一起出现面包、牛奶、尿布三者组合也比较常见也就是说FP-Growth 挖掘出的目标和 Apriori 是一样的都是找频繁项集。只不过实现方式更高效[4]。十、可选对比用 Apriori 和 FP-Growth 跑同一份数据为了更直观地比较两者我们可以在同一份数据上同时运行 Apriori 和 FP-Growthfrommlxtend.frequent_patternsimportapriori,fpgrowth freq_aprioriapriori(df,min_support0.6,use_colnamesTrue)freq_fpfpgrowth(df,min_support0.6,use_colnamesTrue)print(Apriori结果)print(freq_apriori)print(\nFP-Growth结果)print(freq_fp)在这组很小的样例数据上你通常会发现两者结果基本一致性能差异不一定明显这是很正常的。因为数据太小的时候Apriori 的效率问题还不明显。真正体现 FP-Growth 优势的是交易记录很多商品种类很多候选项集数量很大也就是说小数据看结果大数据看效率。十一、支持度阈值一改FP-Growth 的结果也会变这一点和 Apriori 是完全一致的。如果你把最小支持度调低比如freq_items_fpfpgrowth(df,min_support0.4,use_colnamesTrue)那么你会发现结果变多一些原本不够频繁的组合也被保留下来如果把支持度调高比如freq_items_fpfpgrowth(df,min_support0.8,use_colnamesTrue)那么你会发现结果明显变少只有特别常见的项集才会留下来所以这条规律要继续记住支持度阈值越低频繁项集越多支持度阈值越高筛选越严格十二、除了换成 FP-GrowthApriori 还能怎么优化如果你暂时还不能切换算法其实 Apriori 本身也有一些常见优化思路比如hash 表计数事务压缩抽样动态项集计数不过从整体思想上说这些优化更多是在“尽量补救 Apriori 的效率问题”而 FP-Growth 则是从方法设计上直接绕开了“大量候选生成”这个瓶颈。所以从教学理解角度学 Apriori能建立基本原理学 FP-Growth能理解效率改进方向十三、这一课最核心要记住什么学完 FP-Growth至少要把下面几件事想清楚1Apriori 为什么慢因为它会生成大量候选项集反复扫描数据库2FP-Growth 改进了什么最核心的一点就是不生成候选项集直接发现频繁模式。3FP 树是干什么的FP 树是用来压缩事务数据保存高频路径结构为后续模式增长提供基础4Apriori 和 FP-Growth 怎么选如果是教学入门小规模数据希望理解逐层生成过程可以优先用 Apriori如果是数据量更大更看重运行效率候选项集已经很多那么 FP-Growth 更合适十四、结尾总结这一课主要解决的是一个非常现实的问题数据量大了Apriori 太慢怎么办答案就是使用 FP-Growth。通过校园超市购物小票案例我们可以建立以下几个核心认识Apriori 的主要问题是候选项集太多、数据库反复扫描FP-Growth 的核心优势是不生成候选项集FP-Growth 通过 FP 树压缩数据再通过模式增长挖掘频繁项集在小数据上Apriori 和 FP-Growth 结果可能差不多在大数据场景下FP-Growth 往往更高效对于初学者来说这一课最重要的不是一开始就把 FP 树的递归细节全部吃透而是先建立这样一个整体认识关联分析不只有一种方法Apriori 适合入门理解FP-Growth 更适合解决效率问题。十五、课后思考建议你自己完成一个总结表整理下面三个问题Apriori 适合什么情况FP-Growth 改进了什么两种方法各自的特点是什么如果这三个问题你能说清楚那么你对关联分析的方法体系就已经建立起比较完整的认识了。十六、完整代码汇总importpandasaspdfrommlxtend.preprocessingimportTransactionEncoderfrommlxtend.frequent_patternsimportapriori,fpgrowth transactions[[面包,牛奶],[面包,尿布,啤酒,鸡蛋],[牛奶,尿布,啤酒,可乐],[面包,牛奶,尿布,啤酒],[面包,牛奶,尿布,可乐]]# One-Hot 编码teTransactionEncoder()te_arrayte.fit(transactions).transform(transactions)dfpd.DataFrame(te_array,columnste.columns_)# Apriorifreq_aprioriapriori(df,min_support0.6,use_colnamesTrue)print(Apriori结果)print(freq_apriori)# FP-Growthfreq_fpfpgrowth(df,min_support0.6,use_colnamesTrue)print(\nFP-Growth结果)print(freq_fp)写在最后如果这篇文章对你有帮助欢迎点赞、收藏、评论支持一下。你在学习 FP-Growth 的时候最容易卡住的是哪一部分Apriori 为什么慢FP 树到底怎么构建条件模式基和条件 FP 树怎么理解还是代码能跑通但原理不够清楚欢迎在评论区交流。