Apriori算法核心逻辑代码实现

wuxiaosi0 2019-07-01

概述

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

相关推荐