数据挖掘中的模式发现（三）FpGrowth算法

迈不过友情╰ 2022-07-11 13:49 295阅读 0赞

## 简介 ##

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

今天我们介绍一个新的算法，FpGrowth算法，来挖掘频繁项集，它的效率比Aprori算法高很多。

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

## 基本结构与基本概念 ##

FPTree算法的基本数据结构，包含一个一棵FP树和一个项头表，每个项通过一个结点链指向它在树中出现的位置。基本结构如下所示。需要注意的是项头表需要按照支持度递减排序，在FPTree中高支持度的节点只能是低支持度节点的祖先节点。

![图一][SouthEast]

### FP-Tree ###

就是上面的那棵树，是把事务数据表中的各个事务数据项按照支持度排序后，把每个事务中的数据项按降序依次插入到一棵以NULL为根结点的树中，同时在每个结点处记录该结点出现的支持度。

### 条件模式基 ###

包含FP-Tree中与后缀模式一起出现的前缀路径的集合。也就是同一个频繁项在PF树中的所有节点的祖先路径的集合。比如I3在FP树中一共出现了3次，其祖先路径分别是\{I2,I1:2\}，\{I2:2\}和\{I1:2\}，其中冒号后面的数字表示频度。这3个祖先路径的集合就是频繁项I3的条件模式基。

### 条件树 ###

将条件模式基按照FP-Tree的构造原则形成的一个新的FP-Tree。比如上图中I3的条件树就是：

![图二][SouthEast 1]

## 实例 ##

我们演示一下FpTree的构造过程。

现有Table如下：

<table> 
 <thead> 
  <tr> 
   <th>TID</th> 
   <th>Items</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>T1</td> 
   <td>{牛奶,面包}</td> 
  </tr> 
  <tr> 
   <td>T2</td> 
   <td>{面包,尿布,啤酒,鸡蛋}</td> 
  </tr> 
  <tr> 
   <td>T3</td> 
   <td>{牛奶,尿布,啤酒,可乐}</td> 
  </tr> 
  <tr> 
   <td>T4</td> 
   <td>{面包,牛奶,尿布,啤酒}</td> 
  </tr> 
  <tr> 
   <td>T5</td> 
   <td>{面包,牛奶,尿布,可乐}</td> 
  </tr> 
 </tbody> 
</table>

假设我们的最小绝对支持度是3。

### Step 1 ###

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

<table> 
 <thead> 
  <tr> 
   <th>Item</th> 
   <th>Count</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>牛奶</td> 
   <td>4</td> 
  </tr> 
  <tr> 
   <td>面包</td> 
   <td>4</td> 
  </tr> 
  <tr> 
   <td>尿布</td> 
   <td>4</td> 
  </tr> 
  <tr> 
   <td>啤酒</td> 
   <td>3</td> 
  </tr> 
 </tbody> 
</table>

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

### Step 2 ###

再次扫描数据记录，对每条记录中出现在Step 1产生的表中的项，按表中的顺序排序。

初始时，新建一个根结点，标记为null；

1.  第一条记录：\{牛奶,面包\}，按Step 1表过滤排序得到依然为\{牛奶,面包\}，新建一个结点，idName为\{牛奶\}，将其插入到根节点下，并设置count为1，然后新建一个\{面包\}结点，插入到\{牛奶\}结点下面，插入后如下所示：
    
    ![图三][SouthEast 2]
2.  第二条记录：\{面包,尿布,啤酒,鸡蛋\}，过滤并排序后为：\{面包,尿布,啤酒\}，发现根结点没有包含\{面包\}的儿子（有一个\{面包\}孙子但不是儿子），因此新建一个\{面包\}结点，插在根结点下面，这样根结点就有了两个孩子，随后新建\{尿布\}结点插在\{面包\}结点下面，新建\{啤酒\}结点插在\{尿布\}下面，插入后如下所示：
    
    ![图四][SouthEast 3]
3.  第三条记录：\{牛奶,尿布,啤酒,可乐\}，过滤并排序后为：\{牛奶,尿布,啤酒\}，这时候发现根结点有儿子\{牛奶\}，因此不需要新建结点，只需将原来的\{牛奶\}结点的count加1即可，往下发现\{牛奶\}结点有一个儿子\{尿布\}，于是新建\{尿布\}结点，并插入到\{牛奶\}结点下面，随后新建\{啤酒\}结点插入到\{尿布\}结点后面。插入后如下图所示：
    
    ![图五][SouthEast 4]
4.  第四条记录：\{面包,牛奶,尿布,啤酒\}，过滤并排序后为：\{牛奶,面包,尿布,啤酒\}，这时候发现根结点有儿子\{牛奶\}，因此不需要新建结点，只需将原来的\{牛奶\}结点的count加1即可，往下发现\{牛奶\}结点有一个儿子\{面包\}，于是也不需要新建\{面包\}结点，只需将原来\{面包\}结点的count加1，由于这个\{面包\}结点没有儿子，此时需新建\{尿布\}结点，插在\{面包\}结点下面，随后新建\{啤酒\}结点，插在\{尿布\}结点下面，插入后如下图所示：
    
    ![图六][SouthEast 5]
5.  第五条记录：\{面包,牛奶,尿布,可乐\}，过滤并排序后为：\{牛奶,面包,尿布\}，检查发现根结点有\{牛奶\}儿子，\{牛奶\}结点有\{面包\}儿子，\{面包\}结点有\{尿布\}儿子，本次插入不需要新建结点只需更新count即可，示意图如下：
    
    ![图七][SouthEast 6]

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

![图八][SouthEast 7]

## 挖掘频繁项集 ##

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

1）此处即从\{啤酒\}开始，根据\{啤酒\}的线索链找到所有\{啤酒\}结点，然后找出每个\{啤酒\}结点的分支：\{牛奶，面包，尿布，啤酒：1\}，\{牛奶，尿布，啤酒:1\}，\{面包，尿布，啤酒:1\}。

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

<table> 
 <thead> 
  <tr> 
   <th>TID</th> 
   <th>Items</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>T1</td> 
   <td>{牛奶，面包，尿布}</td> 
  </tr> 
  <tr> 
   <td>T2</td> 
   <td>{牛奶，尿布}</td> 
  </tr> 
  <tr> 
   <td>T3</td> 
   <td>{面包，尿布}</td> 
  </tr> 
 </tbody> 
</table>

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

![这里写图片描述][SouthEast 8]

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

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

<table> 
 <thead> 
  <tr> 
   <th>TID</th> 
   <th>Items</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>T1</td> 
   <td>{面包}</td> 
  </tr> 
  <tr> 
   <td>T2</td> 
   <td>{牛奶}</td> 
  </tr> 
  <tr> 
   <td>T3</td> 
   <td>{牛奶，面包}</td> 
  </tr> 
  <tr> 
   <td>T4</td> 
   <td>{牛奶，面包}</td> 
  </tr> 
 </tbody> 
</table>

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

![这里写图片描述][SouthEast 9]

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

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

> 绝对支持度： 3  
> 频繁项集：
> 
> <table> 
>  <tbody> 
>   <tr> 
>    <td>面包 尿布</td> 
>    <td>3</td> 
>   </tr> 
>   <tr> 
>    <td>尿布 牛奶</td> 
>    <td>3</td> 
>   </tr> 
>   <tr> 
>    <td>牛奶</td> 
>    <td>4</td> 
>   </tr> 
>   <tr> 
>    <td>面包 牛奶</td> 
>    <td>3</td> 
>   </tr> 
>   <tr> 
>    <td>尿布 啤酒</td> 
>    <td>3</td> 
>   </tr> 
>   <tr> 
>    <td>面包</td> 
>    <td>4</td> 
>   </tr> 
>  </tbody> 
> </table>

## 代码 ##

差点就放弃写代码了…..

两个版本，点击[这里][Link 1]

[SouthEast]: /images/20220711/088ceacfa0674aac809b13f4dff8b708.png
[SouthEast 1]: /images/20220711/a491ae0c0e3044a5b60d81450d04a611.png
[SouthEast 2]: /images/20220711/0a36196dd31d4d728570d960cb2e7a66.png
[SouthEast 3]: /images/20220711/ced2091abd504ddea8bb463102933d0a.png
[SouthEast 4]: /images/20220711/ceca58b2e7ac4dfd80f020048c1f691b.png
[SouthEast 5]: /images/20220711/7834f8146e6440ceaf27f4f0a1d33018.png
[SouthEast 6]: /images/20220711/81c29a0d28ad4d6c8c83036d3fe2dd42.png
[SouthEast 7]: /images/20220711/ccf663fbf43742deadeecaac864d82f4.png
[SouthEast 8]: /images/20220711/2b7fed0a664f4883aea5d0530c5f0a83.png
[SouthEast 9]: /images/20220711/21f219e46b9449a09984896c397166fe.png
[Link 1]: https://github.com/Mr-Phoebe/ProgramDesign/tree/master/Pattern%20Discovery%20in%20Data%20Mining/FPGrowth