数据挖掘（2）：关联规则FpGrowth算法

http://blog.jobbole.com/90125/

上一篇介绍了关联规则挖掘的一些基本概念和经典的Apriori算法&＃xff0c;Aprori算法利用频繁集的两个特性&＃xff0c;过滤了很多无关的集合&＃xff0c;效率提高不少&＃xff0c;但是我们发现Apriori算法是一个候选消除算法&＃xff0c;每一次消除都需要扫描一次所有数据记录&＃xff0c;造成整个算法在面临大数据集时显得无能为力。今天我们介绍一个新的算法挖掘频繁项集&＃xff0c;效率比Aprori算法高很多。

FpGrowth算法通过构造一个树结构来压缩数据记录&＃xff0c;使得挖掘频繁项集只需要扫描两次数据记录&＃xff0c;而且该算法不需要生成候选集合&＃xff0c;所以效率会比较高。我们还是以上一篇中用的数据集为例&＃xff1a;

一、构造FpTree

FpTree是一种树结构&＃xff0c;树结构定义如下&＃xff1a;

树的每一个结点代表一个项&＃xff0c;这里我们先不着急看树的结构&＃xff0c;我们演示一下FpTree的构造过程&＃xff0c;FpTree构造好后自然明白了树的结构。假设我们的最小绝对支持度是3。

Step 1&＃xff1a;扫描数据记录&＃xff0c;生成一级频繁项集&＃xff0c;并按出现次数由多到少排序&＃xff0c;如下所示&＃xff1a;

可以看到&＃xff0c;鸡蛋和可乐没有出现在上表中&＃xff0c;因为可乐只出现2次&＃xff0c;鸡蛋只出现1次&＃xff0c;小于最小支持度&＃xff0c;因此不是频繁项集&＃xff0c;根据Apriori定理&＃xff0c;非频繁项集的超集一定不是频繁项集&＃xff0c;所以可乐和鸡蛋不需要再考虑。

Step 2&＃xff1a;再次扫描数据记录&＃xff0c;对每条记录中出现在Step 1产生的表中的项&＃xff0c;按表中的顺序排序。初始时&＃xff0c;新建一个根结点&＃xff0c;标记为null&＃xff1b;

1&＃xff09;第一条记录&＃xff1a;{牛奶,面包}&＃xff0c;按Step 1表过滤排序得到依然为{牛奶,面包}&＃xff0c;新建一个结点&＃xff0c;idName为{牛奶}&＃xff0c;将其插入到根节点下&＃xff0c;并设置count为1&＃xff0c;然后新建一个{面包}结点&＃xff0c;插入到{牛奶}结点下面&＃xff0c;插入后如下所示&＃xff1a;

2&＃xff09;第二条记录&＃xff1a;{面包,尿布,啤酒,鸡蛋}&＃xff0c;过滤并排序后为&＃xff1a;{面包,尿布,啤酒}&＃xff0c;发现根结点没有包含{面包}的儿子&＃xff08;有一个{面包}孙子但不是儿子&＃xff09;&＃xff0c;因此新建一个{面包}结点&＃xff0c;插在根结点下面&＃xff0c;这样根结点就有了两个孩子&＃xff0c;随后新建{尿布}结点插在{面包}结点下面&＃xff0c;新建{啤酒}结点插在{尿布}下面&＃xff0c;插入后如下所示&＃xff1a;

3&＃xff09;第三条记录&＃xff1a;{牛奶,尿布,啤酒,可乐}&＃xff0c;过滤并排序后为&＃xff1a;{牛奶,尿布,啤酒}&＃xff0c;这时候发现根结点有儿子{牛奶}&＃xff0c;因此不需要新建结点&＃xff0c;只需将原来的{牛奶}结点的count加1即可&＃xff0c;往下发现{牛奶}结点有一个儿子{尿布}&＃xff0c;于是新建{尿布}结点&＃xff0c;并插入到{牛奶}结点下面&＃xff0c;随后新建{啤酒}结点插入到{尿布}结点后面。插入后如下图所示&＃xff1a;

4&＃xff09;第四条记录&＃xff1a;{面包,牛奶,尿布,啤酒}&＃xff0c;过滤并排序后为&＃xff1a;{牛奶&＃xff0c;面包,尿布,啤酒}&＃xff0c;这时候发现根结点有儿子{牛奶}&＃xff0c;因此不需要新建结点&＃xff0c;只需将原来的{牛奶}结点的count加1即可&＃xff0c;往下发现{牛奶}结点有一个儿子{面包}&＃xff0c;于是也不需要新建{面包}结点&＃xff0c;只需将原来{面包}结点的count加1&＃xff0c;由于这个{面包}结点没有儿子&＃xff0c;此时需新建{尿布}结点&＃xff0c;插在{面包}结点下面&＃xff0c;随后新建{啤酒}结点&＃xff0c;插在{尿布}结点下面&＃xff0c;插入后如下图所示&＃xff1a;

5&＃xff09;第五条记录&＃xff1a;{面包,牛奶,尿布,可乐}&＃xff0c;过滤并排序后为&＃xff1a;{牛奶&＃xff0c;面包,尿布}&＃xff0c;检查发现根结点有{牛奶}儿子&＃xff0c;{牛奶}结点有{面包}儿子&＃xff0c;{面包}结点有{尿布}儿子&＃xff0c;本次插入不需要新建结点只需更新count即可&＃xff0c;示意图如下&＃xff1a;

按照上面的步骤&＃xff0c;我们已经基本构造了一棵FpTree&＃xff08;Frequent Pattern Tree&＃xff09;&＃xff0c;树中每天路径代表一个项集&＃xff0c;因为许多项集有公共项&＃xff0c;而且出现次数越多的项越可能是公公项&＃xff0c;因此按出现次数由多到少的顺序可以节省空间&＃xff0c;实现压缩存储&＃xff0c;另外我们需要一个表头和对每一个idName相同的结点做一个线索&＃xff0c;方便后面使用&＃xff0c;线索的构造也是在建树过程形成的&＃xff0c;但为了简化FpTree的生成过程&＃xff0c;我没有在上面提到&＃xff0c;这个在代码有体现的&＃xff0c;添加线索和表头的Fptree如下&＃xff1a;

至此&＃xff0c;整个FpTree就构造好了&＃xff0c;在下面的挖掘过程中我们会看到表头和线索的作用。

二、利用FpTree挖掘频繁项集

FpTree建好后&＃xff0c;就可以进行频繁项集的挖掘&＃xff0c;挖掘算法称为FpGrowth&＃xff08;Frequent Pattern Growth&＃xff09;算法&＃xff0c;挖掘从表头header的最后一个项开始。

1&＃xff09;此处即从{啤酒}开始&＃xff0c;根据{啤酒}的线索链找到所有{啤酒}结点&＃xff0c;然后找出每个{啤酒}结点的分支&＃xff1a;{牛奶&＃xff0c;面包&＃xff0c;尿布&＃xff0c;啤酒&＃xff1a;1}&＃xff0c;{牛奶&＃xff0c;尿布&＃xff0c;啤酒:1}&＃xff0c;{面包&＃xff0c;尿布&＃xff0c;啤酒:1}&＃xff0c;其中的“1”表示出现1次&＃xff0c;注意&＃xff0c;虽然{牛奶}出现4次&＃xff0c;但{牛奶&＃xff0c;面包&＃xff0c;尿布&＃xff0c;啤酒}只同时出现1次&＃xff0c;因此分支的count是由后缀结点{啤酒}的count决定的&＃xff0c;除去{啤酒}&＃xff0c;我们得到对应的前缀路径{牛奶&＃xff0c;面包&＃xff0c;尿布&＃xff1a;1}&＃xff0c;{牛奶&＃xff0c;尿布:1}&＃xff0c;{面包&＃xff0c;尿布:1}&＃xff0c;根据前缀路径我们可以生成一颗条件FpTree&＃xff0c;构造方式跟之前一样&＃xff0c;此处的数据记录变为&＃xff1a;

绝对支持度依然是3&＃xff0c;构造得到的FpTree为&＃xff1a;

构造好条件树后&＃xff0c;对条件树进行递归挖掘&＃xff0c;当条件树只有一条路径时&＃xff0c;路径的所有组合即为条件频繁集&＃xff0c;假设{啤酒}的条件频繁集为{S1,S2,S3}&＃xff0c;则{啤酒}的频繁集为{S1&＃43;{啤酒},S2&＃43;{啤酒},S3&＃43;{啤酒}}&＃xff0c;即{啤酒}的频繁集一定有相同的后缀{啤酒}&＃xff0c;此处的条件频繁集为&＃xff1a;{{}&＃xff0c;{尿布}}&＃xff0c;于是{啤酒}的频繁集为{{啤酒}{尿布&＃xff0c;啤酒}}。

2&＃xff09;接下来找header表头的倒数第二个项{尿布}的频繁集&＃xff0c;同上可以得到{尿布}的前缀路径为&＃xff1a;{面包&＃xff1a;1}&＃xff0c;{牛奶&＃xff1a;1}&＃xff0c;{牛奶&＃xff0c;面包&＃xff1a;2}&＃xff0c;条件FpTree的数据集为&＃xff1a;

注意{牛奶&＃xff0c;面包&＃xff1a;2}&＃xff0c;即{牛奶&＃xff0c;面包}的count为2&＃xff0c;所以在{牛奶&＃xff0c;面包}重复了两次&＃xff0c;这样做的目的是可以利用之前构造FpTree的算法来构造条件Fptree&＃xff0c;不过这样效率会降低&＃xff0c;试想如果{牛奶&＃xff0c;面包}的count为20000&＃xff0c;那么就需要展开成20000条记录&＃xff0c;然后进行20000次count更新&＃xff0c;而事实上只需要对count更新一次到20000即可。这是实现上的优化细节&＃xff0c;实践中当注意。构造的条件FpTree为&＃xff1a;

这颗条件树已经是单一路径&＃xff0c;路径上的所有组合即为条件频繁集&＃xff1a;{{}&＃xff0c;{牛奶}&＃xff0c;{面包}&＃xff0c;{牛奶&＃xff0c;面包}}&＃xff0c;加上{尿布}后&＃xff0c;又得到一组频繁项集{{尿布}&＃xff0c;{牛奶&＃xff0c;尿布}&＃xff0c;{面包&＃xff0c;尿布}&＃xff0c;{牛奶&＃xff0c;面包&＃xff0c;尿布}}&＃xff0c;这组频繁项集一定包含一个相同的后缀&＃xff1a;{尿布}&＃xff0c;并且不包含{啤酒}&＃xff0c;因此这一组频繁项集与上一组不会重复。

重复以上步骤&＃xff0c;对header表头的每个项进行挖掘&＃xff0c;即可得到整个频繁项集&＃xff0c;可以证明&＃xff08;严谨的算法和证明可见参考文献[1]&＃xff09;&＃xff0c;频繁项集即不重复也不遗漏。

程序的实现代码还是放在我的github上&＃xff0c;这里看一下运行结果&＃xff1a;

另外我下载了一个购物篮的数据集&＃xff0c;数据量较大&＃xff0c;测试了一下FpGrowth的效率还是不错的。FpGrowth算法的平均效率远高于Apriori算法&＃xff0c;但是它并不能保证高效率&＃xff0c;它的效率依赖于数据集&＃xff0c;当数据集中的频繁项集的没有公共项时&＃xff0c;所有的项集都挂在根结点上&＃xff0c;不能实现压缩存储&＃xff0c;而且Fptree还需要其他的开销&＃xff0c;需要存储空间更大&＃xff0c;使用FpGrowth算法前&＃xff0c;对数据分析一下&＃xff0c;看是否适合用FpGrowth算法。

下一篇将介绍&＃xff0c;关联规则的评价标准&＃xff0c;欢迎持续关注。

参考文献&＃xff1a;

[1].Han jia wei, Pei Jan等 Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach.2004