频繁项集算法Eclat

EquivalenceClassTransformation (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