频繁项集算法Eclat

Equivalence Class Transformation(Eclat)是频繁项挖掘和关联性分析的另外一种常用的算法，与Apriori和FP-growth不同的是，Eclat采用垂直数据格式。所谓的垂直数据格式，就是从对原有数据进行倒排。

Apriori算法和FP-Growth算法都是从TID项集格式（即｛TID：itemset｝）的事务集中挖掘频繁模式，其中TID是事务标识符，而itemset是事务TID中购买的商品。Eclat使用用项-TID集格式（即｛item：TID_set｝）表示，其中item是项的名称，而TID_set是包含item的事务的标识符集合。倒排索引并不是为了快速查找或搜索，而是进行数据统计。

Eclat算法原理

Eclat算法是一种深度优先算法，采用垂直数据表示形式在概念格理论的基础上利用基于前缀的等价关系将搜索空间(概念格)划分为较小的子空间(子概念格)。

垂直数据表示（倒排）

对于一般的检索方式我们是通过ID去寻找事务Item,这种数据格式称为水平数据格式。但是如果我们反过来，我们通过事务Item去寻找ID，这种水平格式称为垂直数据格式。把水平数据格式转为垂直数据格式的过程称为倒排。用熟悉的数据举个例子：

水平数据格式：

垂直数据格式：

垂直数据格式就是便利所有的Item并让其作为键，然后将包含该Item的ID作为值。倒排的代码如下先遍历一遍数据，得到倒排的数据。然后遍历倒排后的数据筛选出频繁项。

支持度计数(频繁项集)

使用倒排的好处在哪里呢？仔细看图就会发现，倒排后的数据频繁项直接可以通过Item对应多少个元素看出来。比如假设支持度为3，那么{z}, {x}, {y}, {r}它们都是频繁项。正是由于这种直接的数据表示形式，使得Eclat挖掘频繁项集更容易理解一些。频繁项获取的流程为：假设k代表每个频繁项内的元素数目，初始值为1，首先对k=1的频繁项取交集得到k+1的频繁项；然后对k+1的频繁集取交集得到k+2的频繁项，以此类推直到只有一个集合为止或者交集全为空。继续使用上面的数据举例，对上述数据取交集得到k+2的频繁项为如图所示。假如我们设最小支持度为3，那么{z,x}, {z,y}, {x,y}为频繁项。

Eclat的优缺点

• 优点：采用了与传统挖掘算法不同的垂直数据库结构，由于这样只要扫描两次数据库，大大减少了挖掘规则所需要的时间，从而提高了挖掘关联规则的效率。
• 缺点：该算法没有对产生的候选集进行删减操作，若项目出现的频率非常高,，频繁项集庞大, 进行交集操作时会消耗系统大量的内存, 影响算法的效率。

Eclat算法实现

Eclat算法流程：

• 通过扫描一次数据集，把水平格式的数据转换成垂直格式；
• 项集的支持度计数简单地等于项集的TID集的长度；
• 从k=1开始，可以根据先验性质，使用频繁k项集来构造候选（k+1）项集；
• 通过取频繁k项集的TID集的交，计算对应的（k+1）项集的TID集。
• 重复该过程，每次k增加1，直到不能再找到频繁项集或候选项集。

示例代码：

def eclat(prefix, items, min_support, freq_items):
    while items:
        # 初始遍历单个的元素是否是频繁
        key, item = items.pop()
        key_support = len(item)
        if key_support >= min_support:
            # print frozenset(sorted(prefix+[key]))
            freq_items[frozenset(sorted(prefix + [key]))] = key_support
            suffix = []  # 存储当前长度的项集
            for other_key, other_item in items:
                new_item = item & other_item  # 求和其他集合求交集
                if len(new_item) >= min_support:
                    suffix.append((other_key, new_item))
            eclat(prefix + [key], sorted(suffix, key=lambda item: len(item[1]), reverse=True), min_support, freq_items)
    return freq_items


def eclat_zc(data_set, min_support=1):
    """
    Eclat方法
    :param data_set:
    :param min_support:
    :return:
    """
    # 将数据倒排
    data = {}
    trans_num = 0
    for trans in data_set:
        trans_num += 1
        for item in trans:
            if item not in data:
                data[item] = set()
            data[item].add(trans_num)
    freq_items = {}
    freq_items = eclat([], sorted(data.items(), key=lambda item: len(item[1]), reverse=True), min_support, freq_items)
    return freq_items


if __name__ == '__main__':
    data_set = [['A', 'B', 'D', 'H'], ['A', 'B', 'E', 'I'], ['A', 'B', 'E', 'J'], ['A', 'C', 'F', 'G']]
    freq_items = eclat_zc(data_set, 2)
    print(freq_items)

参考链接：

• http://mlwiki.org/index.php/Eclat