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

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

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

一、构造FpTree

FpTree是一种树结构，树结构定义如下：

public class FpNode { String idName;// id号List<FpNode> children;// 孩子结点FpNode parent;// 父结点FpNode next;// 下一个id号相同的结点long count;// 出现次数}

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

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

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

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

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