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

爱被打了一巴掌 2022-06-14 08:55 216阅读 0赞

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

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

<table style="margin:0px auto; padding:0px; border-collapse:collapse; border-spacing:0px; border:1px solid silver; word-break:break-word; color:rgb(0,0,0); font-family:Verdana,Arial,Helvetica,sans-serif; font-size:14px; line-height:21px; height:165px; width:209px"> 
 <tbody style="margin:0px; padding:0px"> 
  <tr style="margin:0px; padding:0px"> 
   <td style="margin:0px; padding:3px; border:1px solid silver; border-collapse:collapse; text-align:center; background-color:rgb(241,91,13)"> TID</td> 
   <td style="margin:0px; padding:3px; border:1px solid silver; border-collapse:collapse; text-align:center; background-color:rgb(241,91,13)"> Items</td> 
  </tr> 
  <tr style="margin:0px; padding:0px"> 
   <td style="margin:0px; padding:3px; border:1px solid silver; border-collapse:collapse; text-align:center"> T1</td> 
   <td style="margin:0px; padding:3px; border:1px solid silver; border-collapse:collapse; text-align:center"> {牛奶,面包}</td> 
  </tr> 
  <tr style="margin:0px; padding:0px"> 
   <td style="margin:0px; padding:3px; border:1px solid silver; border-collapse:collapse; text-align:center"> T2</td> 
   <td style="margin:0px; padding:3px; border:1px solid silver; border-collapse:collapse; text-align:center"> {面包,尿布,啤酒,鸡蛋}</td> 
  </tr> 
  <tr style="margin:0px; padding:0px"> 
   <td style="margin:0px; padding:3px; border:1px solid silver; border-collapse:collapse; text-align:center"> T3</td> 
   <td style="margin:0px; padding:3px; border:1px solid silver; border-collapse:collapse; text-align:center"> {牛奶,尿布,啤酒,可乐}</td> 
  </tr> 
  <tr style="margin:0px; padding:0px"> 
   <td style="margin:0px; padding:3px; border:1px solid silver; border-collapse:collapse; text-align:center"> T4</td> 
   <td style="margin:0px; padding:3px; border:1px solid silver; border-collapse:collapse; text-align:center"> {面包,牛奶,尿布,啤酒}</td> 
  </tr> 
  <tr style="margin:0px; padding:0px"> 
   <td style="margin:0px; padding:3px; border:1px solid silver; border-collapse:collapse; text-align:center"> T5</td> 
   <td style="margin:0px; padding:3px; border:1px solid silver; border-collapse:collapse; text-align:center"> {面包,牛奶,尿布,可乐}<br style="margin:0px; padding:0px"> <br style="margin:0px; padding:0px"> </td> 
  </tr> 
 </tbody> 
</table>

一、构造FpTree

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

![复制代码][copycode.gif]

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

![复制代码][copycode.gif]

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

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

<table style="margin:0px auto; padding:0px; border-collapse:collapse; border-spacing:0px; border:1px solid silver; word-break:break-word; color:rgb(0,0,0); font-family:Verdana,Arial,Helvetica,sans-serif; font-size:14px; line-height:21px; height:123px; width:81px"> 
 <tbody style="margin:0px; padding:0px"> 
  <tr style="margin:0px; padding:0px"> 
   <td style="margin:0px; padding:3px; border:1px solid silver; border-collapse:collapse; background-color:rgb(246,94,8)"> <span style="margin:0px; padding:0px">Item</span></td> 
   <td style="margin:0px; padding:3px; border:1px solid silver; border-collapse:collapse; background-color:rgb(246,94,8)"> Count</td> 
  </tr> 
  <tr style="margin:0px; padding:0px"> 
   <td style="margin:0px; padding:3px; border:1px solid silver; border-collapse:collapse; text-align:center"> <span style="margin:0px; padding:0px">牛奶</span></td> 
   <td style="margin:0px; padding:3px; border:1px solid silver; border-collapse:collapse; text-align:center"> 4</td> 
  </tr> 
  <tr style="margin:0px; padding:0px"> 
   <td style="margin:0px; padding:3px; border:1px solid silver; border-collapse:collapse; text-align:center"> <span style="margin:0px; padding:0px">面包</span></td> 
   <td style="margin:0px; padding:3px; border:1px solid silver; border-collapse:collapse; text-align:center"> 4</td> 
  </tr> 
  <tr style="margin:0px; padding:0px"> 
   <td style="margin:0px; padding:3px; border:1px solid silver; border-collapse:collapse; text-align:center"> <span style="margin:0px; padding:0px">尿布</span></td> 
   <td style="margin:0px; padding:3px; border:1px solid silver; border-collapse:collapse; text-align:center"> 4</td> 
  </tr> 
  <tr style="margin:0px; padding:0px"> 
   <td style="margin:0px; padding:3px; border:1px solid silver; border-collapse:collapse; text-align:center"> 啤酒</td> 
   <td style="margin:0px; padding:3px; border:1px solid silver; border-collapse:collapse; text-align:center"> 3</td> 
  </tr> 
 </tbody> 
</table>

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

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

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

![05213701-8bf8c8750dee440dbb110e6e514e8c74.jpg][]

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

![05213458-5fd67fd628434e1d936b3e58c907ce0b.jpg][]

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

![05214534-13b227b9dbb44d2983cc8406ff6e8588.jpg][]

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

![05214830-a9ce3707d5ae484885142ff5e8ded5bf.jpg][]

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

![05215333-9e3232d0a81d46898ac058c9bcd4d002.jpg][]

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

![06083215-3a6581c951614c1d82d434bc9d9383d0.jpg][]

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

二、利用FpTree挖掘频繁项集

FpTree建好后，就可以进行频繁项集的挖掘，挖掘算法称为FpGrowth（Frequent Pattern Growth）算法，挖掘从表头header的最后一个项开始。

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

绝对支持度依然是3，构造得到的FpTree为：

![06091610-fcfd109d4baf4bbc953d450132c7425c.jpg][]

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

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

<table style="margin:0px auto; padding:0px; border-collapse:collapse; border-spacing:0px; border:1px solid silver; word-break:break-word; color:rgb(0,0,0); font-family:Verdana,Arial,Helvetica,sans-serif; font-size:14px; line-height:21px"> 
 <tbody style="margin:0px; padding:0px"> 
  <tr style="margin:0px; padding:0px"> 
   <td style="margin:0px; padding:3px; border:1px solid silver; border-collapse:collapse; background-color:rgb(242,86,12)"> TID</td> 
   <td style="margin:0px; padding:3px; border:1px solid silver; border-collapse:collapse; background-color:rgb(242,86,12)"> Items</td> 
  </tr> 
  <tr style="margin:0px; padding:0px"> 
   <td align="center" style="margin:0px; padding:3px; border:1px solid silver; border-collapse:collapse; text-align:center"> T1</td> 
   <td align="center" style="margin:0px; padding:3px; border:1px solid silver; border-collapse:collapse; text-align:center"> {面包}</td> 
  </tr> 
  <tr style="margin:0px; padding:0px"> 
   <td align="center" style="margin:0px; padding:3px; border:1px solid silver; border-collapse:collapse; text-align:center"> T2</td> 
   <td align="center" style="margin:0px; padding:3px; border:1px solid silver; border-collapse:collapse; text-align:center"> {牛奶}</td> 
  </tr> 
  <tr style="margin:0px; padding:0px"> 
   <td align="center" style="margin:0px; padding:3px; border:1px solid silver; border-collapse:collapse; text-align:center"> T3</td> 
   <td align="center" style="margin:0px; padding:3px; border:1px solid silver; border-collapse:collapse; text-align:center"> {牛奶，面包}</td> 
  </tr> 
  <tr style="margin:0px; padding:0px"> 
   <td align="center" style="margin:0px; padding:3px; border:1px solid silver; border-collapse:collapse; text-align:center"> T4</td> 
   <td align="center" style="margin:0px; padding:3px; border:1px solid silver; border-collapse:collapse; text-align:center"> {牛奶，面包}</td> 
  </tr> 
 </tbody> 
</table>

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

![06095928-e1d88d1ede204f3d949b7153287cd992.jpg][]  
 　　这颗条件树已经是单一路径，路径上的所有组合即为条件频繁集：\{ \{\}，\{牛奶\}，\{面包\}，\{牛奶，面包\}\}，加上\{尿布\}后，又得到一组频繁项集\{ \{尿布\}，\{牛奶，尿布\}，\{面包，尿布\}，\{牛奶，面包，尿布\}\}，这组频繁项集一定包含一个相同的后缀：\{尿布\}，并且不包含\{啤酒\}，因此这一组频繁项集与上一组不会重复。

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

程序的实现代码还是放在[我的github][github]上，这里看一下运行结果：

![复制代码][copycode.gif]

绝对支持度： 3
    频繁项集： 
    面包 尿布     3
    尿布 牛奶     3
    牛奶     4
    面包 牛奶     3
    尿布 啤酒     3
    面包     4

![复制代码][copycode.gif]

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

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

参考文献：

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

感谢关注，欢迎回帖交流!

转载请注明出处：[http://www.cnblogs.com/fengfenggirl][http_www.cnblogs.com_fengfenggirl]

[Link 1]: http://www.cnblogs.com/fengfenggirl/p/associate_apriori.html
[copycode.gif]: /images/20220614/deef20fdc2f54423904484a6636fab34.png
[05213701-8bf8c8750dee440dbb110e6e514e8c74.jpg]: /images/20220614/bd1f5b69a6274967a20c8045aea2abbc.png
[05213458-5fd67fd628434e1d936b3e58c907ce0b.jpg]: /images/20220614/c59d8a837dbb4b18b31f517c4ddbf0ce.png
[05214534-13b227b9dbb44d2983cc8406ff6e8588.jpg]: /images/20220614/1d6dc7716921413aacce27c56ad39111.png
[05214830-a9ce3707d5ae484885142ff5e8ded5bf.jpg]: /images/20220614/92b0026b50f84e74a802ba951cad3859.png
[05215333-9e3232d0a81d46898ac058c9bcd4d002.jpg]: /images/20220614/ff9a3c870e3b47d2b595e891b5f8d3a2.png
[06083215-3a6581c951614c1d82d434bc9d9383d0.jpg]: /images/20220614/39c7340cbc7b4b559b5a790b5f4becdc.png
[06091610-fcfd109d4baf4bbc953d450132c7425c.jpg]: /images/20220614/41140982c75344bea50861507ac625ba.png
[06095928-e1d88d1ede204f3d949b7153287cd992.jpg]: /images/20220614/207d66f543db402f81c3c86c72d6932e.png
[github]: https://github.com/BigPeng/FPtree
[Link 2]: http://fimi.ua.ac.be/data/retail.dat.gz
[http_www.cnblogs.com_fengfenggirl]: http://www.cnblogs.com/fengfenggirl