用关系型数据结构实现Eclat算法——Hive
接上一篇文章，讨论的都是数据挖掘中最常做的事情：频繁项挖掘。上篇文章中介绍的fp-growth是一种频繁项挖掘方式，其特点是对原始记录只扫描两次，将所有的频繁信息存储在fp-tree中，然后对tree做频繁项挖掘。
本文介绍另一种频繁项挖掘算法Eclat，并且用关系型的数据结构进行实现。
首先，简单介绍下eclat算法：
与fp-growth 和apriori算法不同，Eclat算法加入了倒排的思想，具体就是将事务数据中的项作为key，每个项对应的事务ID作为value。
原输入数据为
tiditem1A,B2B,C3A,C4A,B,C转换后为：
itemtidsA1,3,4B1,2,4C2,3,4通过转换后的倒排表可以加快频繁集生成速度。 其算法思想是 由频繁k项集求交集，生成候选k+1项集 。对候选k+1项集做裁剪，生成频繁k+1项集，再求交集生成候选k+2项集。如此迭代，直到项集归一。 根据上述数据的情况，具体计算过程为：
1.计算频繁1项集，结果为：
itemfreqA3B3C32.由频繁1项集生成频繁2项集
itemfreqA,B2A,C2B,C23.由频繁2项集生成频繁3项集
itemfreqA,B,C1频繁k项集生成频繁k+1项集的过程与由1项集生成2项集的过程完全一致。
这里有个隐含的条件是，两个频繁k项集生成k+1项集时，前k-1项是一致的,A,B+A,C==>A,B,C
接着，看下如何实现：
上述的计算过程也已经描述的很清楚了，需要的就是将逻辑过程转化成具体的数据表和代码：
先看下数据表的设计：
首先：
原始输入数据需要设计成竖表：
tid，item
1，A
1，B
2，B
2，C
3，A
3，C
4，A
4，B
4，C
由这个表计算频繁一项集很简单，对item字段做group by + count即可。
将count>=最小支持度的留下。
然后，频繁2项集
1. 将原始表做自关联。 关联条件为tid相同，item不同，并且左表的count>=右表的count，在count一样的情况，按照item字母顺序满足：左item>右item
2. 将关联结果的左item、左count、右item、右count做group by，再计算count，这个count就是频繁2项的支持度了，留下满足支持度的pair对，对关联结果做filter
结果如下： --将定A、B、C排序按照字母顺序排列
l_item,l_count,r_item,r_count,tid
A,3,B,3,1
A,3,B,3,4
A,3,C,3,3
A,3,C,3,4
B,3,C,3,2
B,3,C,3,4
页:
[1]