FP_growth算法

来自http://blog.sina.com.cn/s/blog_6e85bf420100ogp8.html 

FP_growth算法是韩家炜老师在2000年提出的关联分析算法，该算法和Apriori算法最大的不同有两点：第一，不产生候选集，第二，只需要两次遍历数据库，大大提高了效率，用31646条测试记录，最小支持度是2%，用Apriori算法要半个小时但是用FP_growth算法只要6分钟就可以了，效率非常明显。它的核心是FP_tree，一种树型数据结构，特点是尽量把相同元素用一个节点表示，这样就大大减少了空间，和birch算法有类似的思想。还是以如下数据为例。

每一行表示一条交易，共有9行，既9笔交易，左边表示交易ID，右边表示商品名称。最小支持度是22%，那么每件商品至少要出现9*22%=2次才算频繁。第一次扫描数据库，统计每件商品出现的次数，按次数对各个商品递减排序，有：。然后第二次扫描数据库，在每条交易中按此种顺序给商品排序，如果有某个商品出现的次数小于阈值2，则删除该商品，有：

剩下的就是构造FP_tree了，这是核心，树的每个节点的结构体如下：

//FP-tree的存储结构
typedef struct CSNode{
//商品编号
int item;
//次数
int count;
//父节点，孩子节点，兄弟节点
CSNode *parent,*firstchild,*nextsibling;
//相同商品的前驱，后继节点，方便将相同商品的节点连接起来,根节点的直接孩子节点的这两个指针都是空
CSNode *pre,*next;
}*CSTree;
其中item,*firstchild,*nextsibling是树这个结构体常用的属性。count记录商品item出现的次数，*parent是为了方便从叶子节点逆向访问根节点而设置的。*pre,*next的注释已经很清楚了。构造树的原则是：将每条记录看做一个从根节点到叶子节点的路径，如果某个商品在节点中已经存在了，则对应count计数器加1，相当于所有的前缀都要加1,如果不存在则在该条记录的后面商品开辟一条新的路径。下面一条一条记录演示怎么构造FP_tree。

   第三次访问数据库，构造FP_tree。第一条记录：I2,I1,I5，有：

父节点没有表示出来，根节点是空节点。2:1表示商品2出现了1次，其他表示类推。左边的数组按照商品顺序递减排列，保存了各个商品的当前指针，目的是为了在后面找到相同的后缀，将相同的商品用单项箭头虚线连起来，实际是双向链表链接的，并且将此时的节点商品1和节点商品5保存为商品1和商品5的当前指针，而对于商品2，商品3，商品4的当前指针还在左边的数组中保存。注意根节点的直接孩子不用连起来，后面会讲理由。第二条记录：I2,I4，有：

该记录和第一条记录共用前缀I2,所以商品2的次数要加1，而商品4则作为商品2的一个新孩子节点，这里没有把兄弟节点画出来。并且左边商品4要指向该节点，此时商品4的当前指针指向节点商品4。第三条记录：I2,I3,类似，结果是：

第四条记录：I2,I1,I4有：

当添加完商品4后，商品4的当前指针要指向新的节点商品4，此时两条红色的虚线就把以商品4为后缀的节点连起来了。第5条记录：I1,I3,有：

商品1由于和根节点的所有直接子孩子（这里只有商品2这个子孩子）不同，因此要另外开辟一条路径。商品3的当前指针要指向新的节点商品3，如图中的黄色虚线所指，到这里体现了构造FP_tree的一般性了。再把剩下的记录都加进来，最终的FP_tree是：

这颗FP_tree最大程度的把相同的商品放在用同一个节点保存，最大限度的节省了空间。剩下的工作就是挖掘这颗FP_tree了。

   挖掘的目的是找出FP_tree的各个路径中相同的集合，有两中方式，方式一，从根节点朝叶子节点顺着遍历树，方式二，从叶子节点朝根节点逆着遍历树。想想方式一挺麻烦的，幸亏我们设置了*parent指针，通过它就可以很方便的用方式二。我们从商品出现次数由少到多的顺序开始遍历树，先从商品5开始，由于有*pre,*next指针分方便将所有以商品5做为叶子节点的路径全找出来，然后再根据*parent指针找到父节点，根节点是空不用找。以I5做元素的条件模式基是：{(I2 I1:1),(I2 I1 I3:1)}。后面的1表示出现商品I2,I1,I5同时出现的次数。现在解释为什么：根节点的直接孩子不用*pre,*next指针连起来，因为假如连起来的话，那么以它为后缀时，将没有前缀，也就是说它的频繁项集是1，这在大多数情况下没意义。由它构造出条件FP_tree，注意由于开始按照商品名称排序了，那么条件模式基中的每一项也会按照这种方式排序。如果条件模式基中某项A是另外一项B的子集那么在算B时，要将A出现的次数加上，实现这个功能最简单明了的方法就是一一匹配，假如条件模式基共有N项，则时间复杂度是N的平方，若先按照条件模式基的长度递增排序得到：{(I2 I1:1),(I2 I1 I3:1)}，排序的时间复杂度是N*log(N),那么只有可能是长度短的项是长度长的项的子集，此时总匹配次数是：N-1 + N-2 + ,,, + 1 = N*(N-1)/2,和前面的排序时间加起来是：N*log(N) + N*(N-1)/2当N大于时4时，该值小于N的平方。在实际中N一般会大于4。最终我们得到以I5作为后缀的频繁项集是：{I2 I5:2},{I1 I5:2},{I2 I1 I5:2}他们出现的次数都大于等于最小支持度。类似可以得到其它后缀的频繁项集。

   FP_growth算法不产生候选序列，并且只需要3次遍历数据库，对比Apriori算法而言有了很大的改进。其实想想这也符合历史发展的规律，Apriori在1993年才提出来的，那是数据挖掘才刚起步，而到2000年时，已经有了一定的发展，FP_growth是站在Apriori的肩膀上发明的，这种现象具有普遍性。