机器学习|频繁项集挖掘之Eclat算法

一. Eclat 是一种使用垂直数据出发得到频繁项集的算法

Apriori 算法和FP-growth 都是从水平数据格式出发,获得频繁项集的方法, 本文将介绍一种从垂直数据出发得到频繁项集的算法 Eclat(Equivalence Class Transformation), Eclat的优势是只需扫描一遍完整的数据库, 劣势是,频繁项较多时的集合的交集运算会比较花费时间,且对计算资源需求较大
本文采用《数据挖掘概念与技术》中的数据集,并使用该书中的结果验证代码结果的准确性 .
可以在我们的 "数据臭皮匠" 中输入"第六章4" 拿到

1.手动输入书中的数据

data_ls ={'T100':['I1','I2','I5'],
    'T200':['I2','I4'],
    'T300':['I2','I3'],
    'T400':['I1','I2','I4'],
    'T500':['I1','I3'],
    'T600':['I2','I3'],
    'T700':['I1','I3'],
    'T800':['I1','I2','I3','I5'],
    'T900':['I1','I2','I3']}

2.将水平数据格式转换为垂直数据格式

def convert(data):
    """将水平数据格式转换为垂直数据格式"""
    data_vert = {}
    for tid,items in data_ls.items():
        for item in items:
            if frozenset({item}) not in data_vert:
                data_vert[frozenset({item})] = {tid}
            else :
                data_vert[frozenset({item})].add(tid)
    return data_vert


# convert(data_ls)

只需一次扫描, 就可以将水平数据格式转换为垂直数据

image.png

3.根据最小支持度阈值, 删除不满足最小支持度的项

(书中设置的最小支持度为2,所有所有项都是频繁的)

def drop_data(data):
    """根据阈值删除掉不频繁的项"""
    res = data.copy()
    for key in data :
        if len(data[key])<threshold_val:
            del res[key]
    return res

# 删除不满足最小支持度的项
# data_vert = drop_data(data_vert)
# 得到频繁一项集 L1
# L1 = [frozenset(key) for key in data_vert.keys()]
# print('L1:',L1)

4.根据频繁一项集得到候选2项集

看过'Apriori 算法'的读者应该很熟悉上面这个函数, 这里和'Apriori 算法' 中使用的aprioriGen 是逻辑是一致的, 只是返回值的形式有所改变

def aprioriGen(Lk_1, k):  # creates Ck
    """ 根据k-1项集产生候选k项集
    Lk_1: k-1项集的列表
    k: k项集的k
    """
    res = {}
    lenLk_1 = len(Lk_1)  # k-1项集的长度
    for i in range(lenLk_1):
        for j in range(i + 1, lenLk_1):
            L1 = sorted(list(Lk_1[i]))  # k等于2时, 1项集取空, k等于3时,2项集取第一个元素, k等于4时,3项集取前两个元素
            L2 = sorted(list(Lk_1[j]))  # k等于2时, 1项集取空, k等于3时,2项集取第一个元素, k等于4时,3项集取前两个元素

            if L1[:k - 2] == L2[:k - 2]:  # 如果前k减2个元素相等 , 就将两几何求并
                res[Lk_1[i]|Lk_1[j]]=[Lk_1[i],Lk_1[j]]  # set union

    return res

# candidate = aprioriGen(L1, k=2)

5.通过求交集计算每个候选2项集的支持度

得到候选2项集以后, 需要通过求交集计算每个候选2项集的支持度,我们这里的候选2项集有10个元素, 分别求交集获得支持度后发现, 有8个元素的支持度是大于0的, 其中{I1,I4},{I3,I5} 的支持度为1

def get_support(candidate_k_1,vert):
    """通过求交集获得候选k项集的支持度,并因此获得k项集"""
    res = {}
    for key,items in candidate_k_1.items():
        item1,item2 = items
        ss = vert[item1]&vert[item2]

        res[key] = ss
    return res



# data_vert = get_support(candidate,data_vert)

6.通过循环计算频繁k项集

通过循环计算频繁K项集,候选K+1项集, 候选K+1项集每个项的支持度,可以得到所有的频繁项集, 频繁3项集的结果如下图

threshold_val = 2
# 将水平数据格式转换为垂直数据格式
data_vert = convert(data_ls)
# 删除不满足最小支持度的项
data_vert = drop_data(data_vert)
# 得到频繁一项集 L1
L1 = [frozenset(key) for key in data_vert.keys()]
print('L1:',L1)

res = []
res.append(L1)
# 获得候选2项集
candidate = aprioriGen(L1, k=2)
i=1
while len(candidate):
    print(f'data_vert{i}:', data_vert)
    i+=1
    # 对候选2项集通过求交集计算支持度
    data_vert = get_support(candidate,data_vert)
    # 删除不满足支持度的项, 得到频繁2项集
    data_vert = drop_data(data_vert)
    if len(data_vert):
        L = [frozenset(key) for key in data_vert.keys()]
        res.append(L)
        print(f'L{i}:',L)
        candidate = aprioriGen(L, k=2)
    else:
        break

二. Eclat算法的总体流程

Eclat算法的总体流程是比较简单且清晰的,首先通过扫描一次数据集, 把水平格式的数据转换为垂直格式.这个过程顺便也就把每个项的支持度计算出来了, 从k=1开始,可以根据先验性质,使用频繁k项集来构造k+1项集, 且可以通过取频繁k项集的交集计算对应k+1项集的支持度, 重复该过程,每次k增加1, 直到不能再找到频繁项集或候选项集.