基于FP-tree的关联规则挖掘FP-growth算法基本思想

算法分析：
转载地址：http://hi.baidu.com/shirdrn/blog/category/Data%20Minning

在挖掘关联规则的过程中，无可避免要处理海量的数据，也就是事务数据库如此之大，如果采用Apriori算法来挖掘，每次生成频繁k-项集的时候，可能都需要扫描事务数据库一遍，这是非常耗时的操作。那么，可以想尽办法来减少扫描事务数据库的次数，来改进挖掘频繁关联规则的效率。

FP-tree是频繁模式树，它是将整个事务数据库压缩到一棵频繁模式树上。而且，在构造整个事务数据库的的FP-tree的过程中，只需要扫描一次事务数据库就能生成。比AproriGen算法生成候选频繁项集要节省很多时间。

关联规则挖掘FP-growth算法，是通过遍历上面构造的整个事务数据库的频繁模式树来生成频繁项集。FP-growth算法基本思想描述如下：

第一步：构造整个事务数据库的FP-tree

关于FP-tree的构造可以参考前面的文章 FP- tree的数据结构及其构造 。这里假设已经能够构造出FP-tree，接着就是在整个事务数据库对应的FP-tree的基础上挖掘频繁项集。在下面的步骤中，需要对FP-tree的结构及其内容熟悉。

第二步：挖掘条件模式基

在构造的整个事务数据库的频繁模式树上进行条件模式基的挖掘。

条件模式基，就是选定一个基于支持计数降序排序的频繁1-项集项目，假设为Item，也就是FP-tree的头表中的频繁1-项集项目（已经知道，头表中频繁1-项集项目是按照降序排列的），此时，称该频繁1-项集项目Item为后缀。

纵向沿着头表向上，也就是按照头表中频繁1-项集支持计数的升序方向，优先遍历头表；在遍历头表的过程中同时横向遍历每个频繁1-项集对应的链表域。

通过横向遍历该频繁1-项集项目Item对应的链表域——每个链表中的FPTNode结点都具有一个直接父亲结点的nodeParent指针，纵向向上遍历直到根结点停止，就得到了一个序列（不包含Item对应的横向链表中的结点），这个序列就是条件模式基。

在遍历的过程中，每个条件模式序列中每个FPTNode结点肯定出现一次；以Item频繁1-项集项目横向遍历得到的序列，都是以Item为后缀的。

最后，整棵FP-tree遍历完毕，得到全部的条件模式基。

第三步：根据条件模式基建立局部FP-tree

对上面得到的条件模式基，对每个头表中的频繁1-项集对应的条件模式，作为数据输入源来构造局部FP-tree，也就是条件模式基的FP- tree。因为每个条件模式基的数据量与整个事务数据库相比，显得非常小，建树不会消耗太多时间；而全部的条件模式基就相当于整个事务数据库，所以大约需要扫描两次事务数据库。

建立条件模式基的局部FP-tree，分为单个分支和多个分支两种情况，大体过程是这样的：

（1）对于单个分支：

扫描每个条件模式基，统计在每个单个分支中FPTNode结点中1-项集的支持计数，如果一个头表中的项目Item对应的条件模式基扫描完成，最终的计数不能满足最小支持计数，需要将该结点删除掉，因为它与其他结点组合以后，每个含有该结点的项集一定不满足最小支持计数。

根据上面得到的满足最小支持计数的序列来构造局部FP-tree，因为得到的FPtree是单个分支的，遍历该FP-tree能够得到一个Item 的全部满足最小支持计数的序列，从而将该序列中的全部项目进行组合计算，得到全部组合序列，对于每个序列都将当前头表中Item加入到其中，就得到了包含 Item的全部频繁项集。

（2）对于多个分支：

如果存在分支的，需要递归挖掘频繁项集。因为对于多个分支，递归到出口一定是对应着单个分支的，可以类似上一种情况，处理单个分支，得到频繁项集。

第四步：挖掘频繁关联规则

在上面的步骤中，已经得到了全部的频繁项集，这时挖掘频繁关联规则与Apriori算法的频繁关联规则挖掘的步骤相同。

通过上面的步骤，就完成了频繁关联规则的挖掘。我认为，该算法的思想还是非常清晰的。在基于FP-tree的关联规则挖掘FP-growth算法中，构造整个事务数据库的FP-tree是一个难点，需要保证在构造的过程中不丢失数据结点；另一个难点就是在处理得到的条件模式基的时候，对于具有多个分支的情况，采用递归的思想挖掘，保证不漏掉任何频繁项集。

算法实现：
http://ikeycn.iteye.com/blog/700616

评论

1 楼 di1984HIT 2014-06-01  

写的不错！！！