FP-growth算法

迷南。 2022-05-27 12:36 121阅读 0赞

> 相较于Apriori 算法：FP-growth算法对于挖掘长的短的频繁模式，都是有效和可以伸缩的，并比Apriopri算法快了1 个数量级；但当数据库很大时，构造基于内存的FP-tree 是不太现实的。

关于关联分析算法有一个非常有名的故事：”尿布和啤酒”。故事是这样的：美国的妇女们经常会嘱咐她们的丈夫下班后为孩子买尿布，而丈夫在买完尿布后又要顺手买回自己爱喝的啤酒，因此啤酒和尿布在一起被购买的机会很多。这个举措使尿布和啤酒的销量双双增加，并一直为众商家所津津乐道。

起初Apriori算法的提出有效的能发现这种物品间的关联规则，但是Apriori算法频繁的扫描数据集，造成效率低下，在大的数据集上执行的会非常缓慢。后来FP-Growth算法的提出有效的解决了这个缺点。

**FP-Growth**(Frequent Pattern Tree，频繁模式树)算法是韩家炜老师提出的关联分析算法，巧妙的将树型结构引入算法中，它采取如下分治策略：提供频繁项集的数据库压缩到一棵频繁模式树（FP-Tree），但仍保留项集关联信息；该算法和Apriori算法最大的不同有两点：  
第一，不产生候选集。  
第二，只需要两次遍历数据库，大大提高了效率。

**流程如下：**  
1：先扫描一遍数据集，得到频繁项为1的项目集，定义最小支持度（项目出现最少次数），删除那些小于最小支持度的项目，然后将原始数据集中的条目按项目集中降序进行排列。  
2：第二次扫描，创建项头表（从上往下降序），以及FP树。  
3：对于每个项目（可以按照从下往上的顺序）找到其条件模式基（CPB，conditional patten base）,递归调用树结构，删除小于最小支持度的项。如果最终呈现单一路径的树结构，则直接列举所有组合；非单一路径的则继续调用树结构，直到形成单一路径即可。

**如果上述不是很明白的话，以下用图进行展示**：  
如下图所示数据清单（第一列为购买id，第二列为物品项目）：  
![这里写图片描述][20160628135215681]

**第一步：构造FP树**  
1：扫描事务数据库对每个物品进行记数:  
![这里写图片描述][20160628123746936]  
2：定义minsup=20%，即最小支持度（物品最少出现的次数）为2。  
3：按照降序排列重新排列物品集。  
![这里写图片描述][20160628123805383]  
（如果出现小于2的物品则需要删除）  
4：按照项目出现次数重新调整数据库中的物品清单。  
![这里写图片描述][20160628124106848]  
5：进行FP树的构建：  
加入第一条清单（I2,I1,I5）：  
![这里写图片描述][20160628124233303]  
加入第二条（I2,I4）：  
![这里写图片描述][20160628124255275]  
出现相同的节点要进行累加（I2）。  
加入第三条（I2,I3）：  
![这里写图片描述][20160628124358479]  
加入第四条（I2,I1,I4）：  
![这里写图片描述][20160628124417182]  
加入第五条（I1,I3）：  
![这里写图片描述][20160628124433744]  
加入第六条（I2,I3）：  
![这里写图片描述][20160628124451776]  
加入第七条（I1,I3）：  
![这里写图片描述][20160628124511995]  
加入第八条（I2,I1,I3,I5）：  
![这里写图片描述][20160628124537620]  
加入第九条（I2,I1,I3）：  
![这里写图片描述][20160628124555027]

这样FP树建立起来。

**第二步：挖掘频繁项集**  
可以按照从下往上的顺序: 先考虑I5：  
得到条件模式基<(I2,I1:1)>,<(I2,I1,I3:1)>,构造FP树：  
（条件模式基：顺着I5的链表，找出所有包含I5的前缀路径，这些前缀路径就是I5的条件模式基）。  
![这里写图片描述][20160628125306264]  
删除小于支持度的节点。  
形成单条路径后进行组合。得到I5频繁项集：\{ \{I2,I5:2\},\{I1,I5:2\},\{I2,I1,I5:2\}\}。  
接着考虑I4，得到条件模式基<(I2,I1:1)>、<(I2:1)>,构造条件FP树：  
![这里写图片描述][20160628125841357]  
得到I4频繁项集：\{ \{I2,I4:2\}\}。  
然后考虑I3，得到条件模式基<(I2,I1:2)>、<(I2:2)>、<(I1:2)>构造条件FP树：  
![这里写图片描述][20160628125939501]  
由于此树不是单一路径，因此需要递归挖掘I3。  
递归考虑I3，此时得到I1条件模式基<(I2:2)>,即I1I3的条件模式基为<(I2:2)>构造条件FP树：  
![这里写图片描述][20160628130041267]  
得到I3的频繁项目集\{ \{I2,I3:4\},\{I1,I3:4\},\{I2,I1,I3:2\}\}。  
最后考虑I1，得到条件模式基<(I2:4)>构造条件FP树：  
![这里写图片描述][20160628130131392]  
得到I1的频繁项目集\{ \{I2,I1:4\}。

**总结：FP-growth通过两次扫描数据库，将原始数据压缩在一个树形结构上，该树优点为路径共用，压缩数据，接着通过数找到每个item条件模式基，递归挖掘频繁项集，但不能用于发现关联规则。**

### 项目推荐： ###

**[2000多G的计算机各行业电子资源分享（持续更新）][2000_G]**

**[2020年微信小程序全栈项目之喵喵交友【附课件和源码】][2020]**

**[Spring Boot开发小而美的个人博客【附课件和源码】][Spring Boot]**

**[Java微服务实战296集大型视频-谷粒商城【附代码和课件】][Java_296_-]**

**[Java开发微服务畅购商城实战【全357集大项目】-附代码和课件][Java_357_-]**

**[最全最详细数据结构与算法视频-【附课件和源码】][-]**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNTg3NTc1_size_16_color_FFFFFF_t_70_pic_center]

[20160628135215681]: /images/20220527/796ac54582e34a51983637aac1903ddd.png
[20160628123746936]: /images/20220527/f86b38f93305462e84138cf7735a4657.png
[20160628123805383]: /images/20220527/e3c760d20c1e480bb67a6cf982c8509b.png
[20160628124106848]: /images/20220527/8e8aa699b67246bcb6c27b05fcc2fed1.png
[20160628124233303]: /images/20220527/1e7bd86564ed4b48a39dc963a489a0cd.png
[20160628124255275]: /images/20220527/fbdcd665f3074925abcaaeeff96788a6.png
[20160628124358479]: /images/20220527/cba1bcdab980426ab16738d13281d48e.png
[20160628124417182]: /images/20220527/ae12a423ad154a8696b493c545d6bec2.png
[20160628124433744]: /images/20220527/4d6a9c8b8c964f049939a76660d51f63.png
[20160628124451776]: /images/20220527/6bd5c36e45fc41b685723a652d93778a.png
[20160628124511995]: /images/20220527/6cad767910df4ce7961ee74630819e7a.png
[20160628124537620]: /images/20220527/27a98b07b3c74bbaa6b18809bac565c4.png
[20160628124555027]: /images/20220527/b0667aad6c924401b0bc4a47372b9474.png
[20160628125306264]: /images/20220527/e39bd4b44ad04dc9a5bc7cbc34df3780.png
[20160628125841357]: /images/20220527/c2e57b81302442ed9c11201dd839ef34.png
[20160628125939501]: /images/20220527/94d1c8ad8ed04b06b38057b947ed6843.png
[20160628130041267]: /images/20220527/3b98c1d63870458a89650d8399b3cd1f.png
[20160628130131392]: /images/20220527/061948f2ce90451faf8a818d1cc53d38.png
[2000_G]: https://mp.weixin.qq.com/s/sP4JgGWkCzpgwKr9sAV2_Q
[2020]: https://mp.weixin.qq.com/s?__biz=MzIyNTI3NDQ4NQ==&mid=2247487704&idx=1&sn=5f4b2127c4d49fd07ae072a0721424a2&chksm=e8036fc2df74e6d489c4aa9b06f917ef7cee6027f13e150fca53cf79d5d188d4ccc1af49e098&scene=21#wechat_redirect
[Spring Boot]: https://mp.weixin.qq.com/s?__biz=MzIyNTI3NDQ4NQ==&mid=2247487798&idx=2&sn=ac0293b996521b872a9dba5fbb3e65e6&chksm=e8036e2cdf74e73aba104a9a994a5b2e31483e8dcbe0f1d9936f6d5173b887e1560f59d2819c&scene=21#wechat_redirect
[Java_296_-]: https://mp.weixin.qq.com/s?__biz=MzIyNTI3NDQ4NQ==&mid=2247487674&idx=1&sn=7aff0bdf2bb727303f3d3618995aef21&chksm=e8036fa0df74e6b6d872c7e6ece179c524ed463a4a6b74c96875475c9a3d5ddb903427dd993b&scene=21#wechat_redirect
[Java_357_-]: https://mp.weixin.qq.com/s?__biz=MzIyNTI3NDQ4NQ==&mid=2247486376&idx=1&sn=d1fef270c463ea8ac663f6fbfedd70a0&chksm=e80374b2df74fda4d3bafba878a106a19e18c5fcda266008f4f37975847a21bc612ffcd5ff39&scene=21#wechat_redirect
[-]: https://mp.weixin.qq.com/s?__biz=MzIyNTI3NDQ4NQ==&mid=2247487750&idx=1&sn=747bccbb5f5ea6b58915198de40da777&chksm=e8036e1cdf74e70ae97a5e8e265b49d7236d904d291203309159d07ba1724033062c0e370843&scene=21#wechat_redirect
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNTg3NTc1_size_16_color_FFFFFF_t_70_pic_center]: /images/20220527/d83a5761724d450da9e47396c31a4054.png