关联规则挖掘算法-ECLAT

ECLAT-等价类转换（Equivalent CLAss Transformation）
ECLAT使用垂直数据格式挖掘频繁项集。

垂直数据

apriori算法和fp-growth算法都从TID项集格式（即{TID：itemset}）的事务集中挖掘频繁模式，其中TID是事务标识符，而itemset是事务TID中购买的商品。这个格式的数据称为水平数据格式。或者，数据也可以用项-TID集的格式（即{item：TID_set}）表示，item是项的名称，而TID_set是包含item的事务的标识符集合。这种格式数据称为垂直数据格式。

ECLAT

eclat算法的一个示例：（）（别人的博客）

代码如下：

def createVerticalSet(inDataSet):
    ''' 创建倒排的数据集，即item-TID集。

    :param inDataSet:
    :return: item-TID数据集
    '''
    verticalSet = {}
    for tid,trans in inDataSet.items():
        for item in trans:
            if not item in verticalSet.keys():
                verticalSet[item] = set([])
            verticalSet[item].add(tid)

    return verticalSet


def eclatInner(prefix, verticalSet, freqItems, minSupport=1):
    ''' 真正的eclat算法实现

    :param prefix: 函数内部使用，用于递归
    :param verticalSet: 倒排的数据集
    :param freqItems: 用于保存频繁项集的列表
    :param minSupport: 最小支持度
    :return: 
    '''
    #先过滤掉不满足最小支持度的项
    innerVeticalSet = [item for item in verticalSet.items() if len(item[1]) >= minSupport]
    while innerVeticalSet:
        item,tidSet = innerVeticalSet.pop()
        freqItems.append(prefix+[item])

        newKSet = {}
        for i,tidSetI in innerVeticalSet:
            joinSet = tidSet & tidSetI
            if len(joinSet) >= minSupport:
                newKSet[i] = joinSet
        if len(newKSet) > 0:
            eclatInner(prefix+[item], newKSet, freqItems, minSupport)


def eclat(dataSet, minSupport=1):
    ''' 堆外的eclat算法接口

    :param dataSet: 倒排的数据集
    :param minSupport: 最小支持度
    :return: 频繁项集
    '''
    freqItems = []
    prefix = []
    eclatInner(prefix, dataSet, freqItems, minSupport)
    return freqItems

参考文档：


改进：
参考文档：

改进的思路：
对垂直表示的数据集直接进行广度优先搜索和交叉计数来计算候选项集的支持度，同时对频繁项集中的项按字典顺序排序，在频繁项集连接时采用如下性质进行优化：
性质：将每个事务及事务中的项集按字典顺序排序，对于两个频繁（k-1）项集Ix,Iy，如果Ix和Iy不能连接，则Ix与Iy之后的所有项集都不能满足连接条件，不需要进行连接判断。
伪代码见上述文档。