数据挖掘（2）：关联规则FpGrowth算法 - 文章 - 伯乐在线
& 数据挖掘（2）：关联规则FpGrowth算法
介绍了关联规则挖掘的一些基本概念和经典的Apriori算法，Aprori算法利用频繁集的两个特性，过滤了很多无关的集合，效率提高不少，但是我们发现Apriori算法是一个候选消除算法，每一次消除都需要扫描一次所有数据记录，造成整个算法在面临大数据集时显得无能为力。今天我们介绍一个新的算法挖掘频繁项集，效率比Aprori算法高很多。
FpGrowth算法通过构造一个树结构来压缩数据记录，使得挖掘频繁项集只需要扫描两次数据记录，而且该算法不需要生成候选集合，所以效率会比较高。我们还是以上一篇中用的数据集为例：
{牛奶,面包}
{面包,尿布,啤酒,鸡蛋}
{牛奶,尿布,啤酒,可乐}
{面包,牛奶,尿布,啤酒}
{面包,牛奶,尿布,可乐}
一、构造FpTree
FpTree是一种树结构，树结构定义如下：
public class FpNode {
String idN// id号
List&FpNode&// 孩子结点
FpN// 父结点
FpN// 下一个id号相同的结点
// 出现次数
树的每一个结点代表一个项，这里我们先不着急看树的结构，我们演示一下FpTree的构造过程，FpTree构造好后自然明白了树的结构。假设我们的最小绝对支持度是3。
Step 1：扫描数据记录，生成一级频繁项集，并按出现次数由多到少排序，如下所示：
可以看到，鸡蛋和可乐没有出现在上表中，因为可乐只出现2次，鸡蛋只出现1次，小于最小支持度，因此不是频繁项集，根据Apriori定理，非频繁项集的超集一定不是频繁项集，所以可乐和鸡蛋不需要再考虑。
Step 2：再次扫描数据记录，对每条记录中出现在Step 1产生的表中的项，按表中的顺序排序。初始时，新建一个根结点，标记为null；
1）第一条记录：{牛奶,面包}，按Step 1表过滤排序得到依然为{牛奶,面包}，新建一个结点，idName为{牛奶}，将其插入到根节点下，并设置count为1，然后新建一个{面包}结点，插入到{牛奶}结点下面，插入后如下所示：
2）第二条记录：{面包,尿布,啤酒,鸡蛋}，过滤并排序后为：{面包,尿布,啤酒}，发现根结点没有包含{面包}的儿子（有一个{面包}孙子但不是儿子），因此新建一个{面包}结点，插在根结点下面，这样根结点就有了两个孩子，随后新建{尿布}结点插在{面包}结点下面，新建{啤酒}结点插在{尿布}下面，插入后如下所示：
3）第三条记录：{牛奶,尿布,啤酒,可乐}，过滤并排序后为：{牛奶,尿布,啤酒}，这时候发现根结点有儿子{牛奶}，因此不需要新建结点，只需将原来的{牛奶}结点的count加1即可，往下发现{牛奶}结点有一个儿子{尿布}，于是新建{尿布}结点，并插入到{牛奶}结点下面，随后新建{啤酒}结点插入到{尿布}结点后面。插入后如下图所示：
4）第四条记录：{面包,牛奶,尿布,啤酒}，过滤并排序后为：{牛奶，面包,尿布,啤酒}，这时候发现根结点有儿子{牛奶}，因此不需要新建结点，只需将原来的{牛奶}结点的count加1即可，往下发现{牛奶}结点有一个儿子{面包}，于是也不需要新建{面包}结点，只需将原来{面包}结点的count加1，由于这个{面包}结点没有儿子，此时需新建{尿布}结点，插在{面包}结点下面，随后新建{啤酒}结点，插在{尿布}结点下面，插入后如下图所示：
5）第五条记录：{面包,牛奶,尿布,可乐}，过滤并排序后为：{牛奶，面包,尿布}，检查发现根结点有{牛奶}儿子，{牛奶}结点有{面包}儿子，{面包}结点有{尿布}儿子，本次插入不需要新建结点只需更新count即可，示意图如下：
按照上面的步骤，我们已经基本构造了一棵FpTree（Frequent Pattern Tree），树中每天路径代表一个项集，因为许多项集有公共项，而且出现次数越多的项越可能是公公项，因此按出现次数由多到少的顺序可以节省空间，实现压缩存储，另外我们需要一个表头和对每一个idName相同的结点做一个线索，方便后面使用，线索的构造也是在建树过程形成的，但为了简化FpTree的生成过程，我没有在上面提到，这个在代码有体现的，添加线索和表头的Fptree如下：
至此，整个FpTree就构造好了，在下面的挖掘过程中我们会看到表头和线索的作用。
二、利用FpTree挖掘频繁项集
FpTree建好后，就可以进行频繁项集的挖掘，挖掘算法称为FpGrowth（Frequent Pattern Growth）算法，挖掘从表头header的最后一个项开始。
1）此处即从{啤酒}开始，根据{啤酒}的线索链找到所有{啤酒}结点，然后找出每个{啤酒}结点的分支：{牛奶，面包，尿布，啤酒：1}，{牛奶，尿布，啤酒:1}，{面包，尿布，啤酒:1}，其中的“1”表示出现1次，注意，虽然{牛奶}出现4次，但{牛奶，面包，尿布，啤酒}只同时出现1次，因此分支的count是由后缀结点{啤酒}的count决定的，除去{啤酒}，我们得到对应的前缀路径{牛奶，面包，尿布：1}，{牛奶，尿布:1}，{面包，尿布:1}，根据前缀路径我们可以生成一颗条件FpTree，构造方式跟之前一样，此处的数据记录变为：
{牛奶，面包，尿布}
{牛奶，尿布}
{面包，尿布}
绝对支持度依然是3，构造得到的FpTree为：
构造好条件树后，对条件树进行递归挖掘，当条件树只有一条路径时，路径的所有组合即为条件频繁集，假设{啤酒}的条件频繁集为{S1,S2,S3}，则{啤酒}的频繁集为{S1+{啤酒},S2+{啤酒},S3+{啤酒}}，即{啤酒}的频繁集一定有相同的后缀{啤酒}，此处的条件频繁集为：{{}，{尿布}}，于是{啤酒}的频繁集为{{啤酒}{尿布，啤酒}}。
2）接下来找header表头的倒数第二个项{尿布}的频繁集，同上可以得到{尿布}的前缀路径为：{面包：1}，{牛奶：1}，{牛奶，面包：2}，条件FpTree的数据集为：
{牛奶，面包}
{牛奶，面包}
注意{牛奶，面包：2}，即{牛奶，面包}的count为2，所以在{牛奶，面包}重复了两次，这样做的目的是可以利用之前构造FpTree的算法来构造条件Fptree，不过这样效率会降低，试想如果{牛奶，面包}的count为20000，那么就需要展开成20000条记录，然后进行20000次count更新，而事实上只需要对count更新一次到20000即可。这是实现上的优化细节，实践中当注意。构造的条件FpTree为：
这颗条件树已经是单一路径，路径上的所有组合即为条件频繁集：{{}，{牛奶}，{面包}，{牛奶，面包}}，加上{尿布}后，又得到一组频繁项集{{尿布}，{牛奶，尿布}，{面包，尿布}，{牛奶，面包，尿布}}，这组频繁项集一定包含一个相同的后缀：{尿布}，并且不包含{啤酒}，因此这一组频繁项集与上一组不会重复。
重复以上步骤，对header表头的每个项进行挖掘，即可得到整个频繁项集，可以证明（严谨的算法和证明可见参考文献[1]），频繁项集即不重复也不遗漏。
程序的实现代码还是放在我的上，这里看一下运行结果：
绝对支持度： 3
频繁项集：
另外我下载了一个，数据量较大，测试了一下FpGrowth的效率还是不错的。FpGrowth算法的平均效率远高于Apriori算法，但是它并不能保证高效率，它的效率依赖于数据集，当数据集中的频繁项集的没有公共项时，所有的项集都挂在根结点上，不能实现压缩存储，而且Fptree还需要其他的开销，需要存储空间更大，使用FpGrowth算法前，对数据分析一下，看是否适合用FpGrowth算法。
下一篇将介绍，关联规则的评价标准，欢迎持续关注。
参考文献：
[1].Han jia wei, Pei Jan等 Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach.2004
可能感兴趣的话题
关于伯乐在线博客
在这个信息爆炸的时代，人们已然被大量、快速并且简短的信息所包围。然而，我们相信：过多“快餐”式的阅读只会令人“虚胖”，缺乏实质的内涵。伯乐在线内容团队正试图以我们微薄的力量，把优秀的原创文章和译文分享给读者，为“快餐”添加一些“营养”元素。
新浪微博：
推荐微信号
（加好友请注明来意）
– 好的话题、有启发的回复、值得信赖的圈子
– 分享和发现有价值的内容与观点
– 为IT单身男女服务的征婚传播平台
– 优秀的工具资源导航
– 翻译传播优秀的外文文章
– 国内外的精选文章
– UI,网页，交互和用户体验
– 专注iOS技术分享
– 专注Android技术分享
– JavaScript, HTML5, CSS
– 专注Java技术分享
– 专注Python技术分享
& 2016 伯乐在线
赞助云主机【图文】关联规则挖掘算法FP-growth的详细讲解_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
评价文档：
关联规则挖掘算法FP-growth的详细讲解
上传于||文档简介
&&关​联​规​则​挖​掘​算​法​​F​P​-​g​r​o​w​t​h​的​详​细​讲​解
大小：675.50KB
登录百度文库，专享文档复制特权，财富值每天免费拿！
你可能喜欢工具类服务
编辑部专用服务
作者专用服务
关联规则中FP-tree算法的应用
本文并着重介绍了关联规则及其主要算法。通过介绍关联规则模型和关联规则中提供了求频繁项集的FP-tree算法．并以图书馆读者借阅实例简述实现了该算法的基本功能。
作者单位：
福建商业高等专科学校图书馆技术部,福建福州,350012
年，卷(期)：
机标分类号：
在线出版日期：
本文读者也读过
相关检索词
万方数据知识服务平台--国家科技支撑计划资助项目（编号：2006BAH03B01）(C)北京万方数据股份有限公司
万方数据电子出版社君，已阅读到文档的结尾了呢~~
基于fp-tree的关联规则挖掘算法的研究,关联规则算法,fp tree算法,关联规则挖..
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
基于fp-tree的关联规则挖掘算法的研究
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口