当你老了

Eclat算法实现

基本原理

Eclat是挖掘频繁项集的一种算法，相比较而言远，它远没有另外两种算法Apriori和FP-Growth那么出名，一个直接的证明就是以前读书的时候课本都没有介绍。

不过这个算法也有它自身的特点，基本原理和Apriori算法很相似，也是通过频繁K项集连接生成频繁K+1项集，但是比Apriori速度快很多，因为引入了倒排机制，保留了每个频繁项集对应的所有记录。这样，在连接生成频繁K+1项集的过程中，两个频繁K项集对应记录集合求交，就得到了这个K+1项集对应的记录集合，这个集合的size就是K+1项集的出现频数，通过与支持度比较就可以判断新产生的K+1项集是不是频繁的。从这个过程可以看出，Eclat算法只需要扫描一次记录库，而Apriori算法每次判断候选K+1项集是不是频繁的时候都要扫描一次记录库，所以Eclat比Apriori快也就不奇怪了。不难看出，Eclat算法其实是用空间换取了时间，后续实验也证明了这个算法是比较耗费空间的。

举个例子（参考[1])： 有4条记录

tid item
1   A,B
2   B,C
3   A,C
4   A,B,C

设定最小支持度为2，第一边扫描记录库后，得到频繁1项集，其中每个item对应的记录集合也保留了，如下：

item  tids  freq
A     1,3,4 3
B     1,2,4 3
C     2,3,4 3

由频繁1项集连接生成候选2项集，都是频繁的：

item tids freq
A,B  1,4  2
A,C  3,4  2
B,C  2,4  2

由频繁2项集连接生成候选3项集，只有一个候选并且不是频繁的，算法结束：

item    tids freq
A,B,C   4    1

注意：在最后一步中，只有A,B和A,C前缀相同，可以连接

实现思路

尝试用C++进行了基本的实现。这里总结几个要点：

  1. 所有item都转换为整数表示，项集用存储item的有序vector表示，这样连接生成K+1项集的时候方便快速比较前缀
  2. 每个频繁项集和记录集合的映射关系用map，记录集合用set
  3. 连接过程关键是比较前缀，比如有两个K项集，那么比较前k-1项是否相同，相同就把其中一个K项集最后一项追加到另一个最后，构成K+1项集，追加后要保证K+1项集是有序的。

从算法过程中还可以看出：频繁K项集的计算，需要把前面频繁1,2，.., k-1项集都计算后才能进行。此外，频繁1项集和频繁2项集的计算需要特殊处理，不用比较前缀。

具体实现参考代码：https://github.com/lostfish/eclat

实验结果

测试数据采用和[2]相同的mushroom.dat，该数据集下载地址为[3]，下载后需要去掉每行最后的空格。

机器配置为：Intel(R) Xeon(R) CPU E5606 @ 2.13GHz (8核，32G内存)

测试结果如下：

最小支持度  频繁项集数  运行时间
812(0.1)    574513  29.219
1218(0.15)  98575   4.593
1624(0.2)   53663   2.632
2031(0.25)  5545    0.603

当支持度为812时，挖掘的各频繁项集数目如下：

valid_num: 8124 8124
uniq id num: 119
frequent 1-itemset size:    56
frequent 2-itemset size:    763
frequent 3-itemset size:    4599
frequent 4-itemset size:    16171
frequent 5-itemset size:    38829
frequent 6-itemset size:    69854
frequent 7-itemset size:    98852
frequent 8-itemset size:    111787
frequent 9-itemset size:    100660
frequent 10-itemset size:   71342
frequent 11-itemset size:   39171
frequent 12-itemset size:   16292
frequent 13-itemset size:   4956
frequent 14-itemset size:   1039
frequent 15-itemset size:   134
frequent 16-itemset size:   8

同时还观察了下空间消耗，占用内存达到了将近9G，比较惊人。当然这是因为在计算的过程中，保留了所有频繁集，如果每次计算完就直接输出，会节省很多空间。另外，这个数据集合本身频繁模式就比较多，平时应用中一般也不需要计算所有频繁项集，一般到频繁3项集或4项集就够了。

相关参考

Published

Category

Tech

Tags

Stay in Touch