关联规则算法---Eclat算法

时间:2022-01-28 18:09:42

Eclat算法

与fp-growth 和apriori算法不同,Eclat算法加入了倒排的思想,具体就是将事务数据中的项作为key,每个项对应的事务ID作为value。

原输入数据为

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

转换后为:

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

通过转换后的倒排表可以加快频繁集生成速度。 其算法思想是 由频繁k项集求交集,生成候选k+1项集 。对候选k+1项集做裁剪,生成频繁k+1项集,再求交集生成候选k+2项集。如此迭代,直到项集归一。 根据上述数据的情况,具体计算过程为

   算法过程:

1.计算频繁1项集,结果为:

item freq
A 3
B 3
C 3

2.由频繁1项集生成频繁2项集

item freq
A,B 2
A,C 2
B,C 2

3.由频繁2项集生成频繁3项集

item freq
A,B,C 1

频繁k项集生成频繁k+1项集的过程与由1项集生成2项集的过程完全一致。

这里有个隐含的条件是,两个频繁k项集生成k+1项集时,前k-1项是一致的,A,B+A,C==>A,B,C

Eclat算法实现[编辑]

eclat的核心思想就是倒排,这种数据处理方式很适合用关系型数据表示和实现。 具体可参考用关系型数据结构实现Eclat算法——Hiv

转载自:http://zh.wikipedia.org/wiki/%E5%85%B3%E8%81%94%E5%BC%8F%E8%A7%84%E5%88%99