Apriori算法核心逻辑代码实现

Love The Way You Lie 2022-03-07 07:14 188阅读 0赞

**概述**

Apriori算法是生成频繁集的一种算法。Apriori原理有个重要假设，如果某个项集是频繁的，那么它的所有子集势必也是频繁的。如果一个项集是非频繁项集，那么它所对应的超集就全都是非频繁项集。

**实现**

从大规模数据集中寻找物品间的隐含关系被称作关联关系，而寻找物品间的不同组合是一项十分耗时的工作，所需计算代价很高，对于包含N种物品的数据集共有2的n次方-1种项集组合，蛮力搜索并不能解决这个问题。
    Apriori能解决这个问题，Apriori算法是生成频繁集的一种算法。Apriori原理有个重要假设，如果某个项集是频繁的，那么它的所有子集势必也是频繁的。如果一个项集是非频繁项集，那么它所对应的超集就全都是非频繁项集。如果一个项集是非频繁项集，那么它所对应的超集就全都是非频繁项集，如何实现呢。

代码(部分伪代码) ：

#L指的是数据集len L[1] 表示的是{x} L2表示的是{x，y} 类似这种数据集 ，先构建L1 ,在构建L2,一次类推，通过while循环实现
    #Apriori的原理体现在scan方法会将不满足可信度的数据集删掉，保留满足的，这样如果一个项集是非频繁项集，那么它所对应的超集就全都是非频繁项集。 
    #代码实现参考自机器学习实战
        while (len(L[k-2]) > 0):
            Lk, supK = scanD(x,y,z)
            supportData.update(supK)
            L.append(Lk)
            k += 1
        return L, supportData
        
        #minSupport最小支持度 
        #Ck 候选数据集列表
        def scan(D, Ck, minSupport):
        ssCnt = {}
        #增加字典对应计数器
        for tid in D:
            for can in Ck:
                if can.issubset(tid):
                    if not ssCnt.has_key(can): ssCnt[can]=1
                    else: ssCnt[can] += 1
        numItems = float(len(D))
        retList = []
        supportData = {}
        #计算可信度，过滤不满足可信度的数据集
        for key in ssCnt:
            support = ssCnt[key]/numItems
            if support >= minSupport:
                retList.insert(0,key)
            supportData[key] = support
        return retList, supportData