第11章：使用Apriori算法进行关联分析（计算频繁项集）

98 阅读 0 评论 65 点赞

我是靠谱客的博主高贵鼠标，最近开发中收集的这篇文章主要介绍第11章：使用Apriori算法进行关联分析（计算频繁项集），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

目的：找到数据集中事务的关系，如超市中经常一起出现的物品集合，想找到支持度超过0.8的所有项集

概念：

频繁项集：指经常出现在一起的物品集合；

关联规则：指两个物品之间可能存在很强的关系，如一个人买了什么之后很大可能会买另一种东西；

支持度：数据集中包含该项集的记录所占的比例；保留满足最小支持度的项集即为频繁项集；

可信度：针对诸如{尿布}-{葡萄酒}这样的关联规则产生的，定义为支持度({尿布，葡萄酒})/支持度({尿布})

Apriori原理：

想找到支持度超过0.8的所有项集，一般做法是生成所有可能的组合，对每种组合统计其出现的频繁程度，当物品较多时，做法很慢。Apriori帮助减少可能感兴趣的项集数，原理是如果某个项集是频繁的，则它的所有子集也是频繁，但是反过来，如果一个项集是非频繁的，则它的所有超集也是非频繁的。因此该算法从最简单的一个元素开始，计算一个元素的支持度，如果支持度小于最小支持度，则去除该元素；然后将两个元素结合，计算两个元素的支持度，仍然小于最小支持度则去除，以此类推找到所有可能的大于最小支持度的元素组合。

代码：


def apriori(dataSet,minSupport=0.5):
    #创建单个元素列表
    C1=createC1(dataSet)

    #map必须转化为list才能使用
    D=list(map(set,dataSet))

    #去除支持度小于最小支持度的单个元素，返回大于支持度的单个元素列表以及所有元素的支持度
    L1,supportData=scanD(D,C1,minSupport)

    #L是一个列表存放单个元素，两个元素...的组合，L[0]单个元素组合，L[1]两个元素组合，以此类推
    L=[L1]
    #
    k=2
    while(len(L[k-2])>0):
        #对两个元素组合，如果两个元素的前几个元素相同，则组合，防止出现重复组合项
        CK=aprioriGen(L[k-2],k)
        LK,supK=scanD(D,CK,minSupport)
        supportData.update(supK)
        L.append(LK)
        k+=1
    return L,supportData

def createC1(dataset):
    C1=[]   #大小为1的所有候选项的集合
    for transaction in dataset:
        for item in transaction:
            if not [item] in C1:
                C1.append([item])
    C1.sort()
    return list(map(frozenset,C1))  #frozenset是个类型，表示使用者不能改变它


def scanD(D,CK,minSupport):
    ssCnt={}
    for tid in D:
        for can in CK:
            if can.issubset(tid):
                if not can in ssCnt:
                    ssCnt[can]=1
                else:
                    ssCnt[can]+=1
    #pdb.set_trace()
    numItems=float(len(D))
    retList=[]
    supportData={}
    for key in ssCnt:
        support=ssCnt[key]/numItems
        if support>=minSupport:
            retList.insert(0,key)   #在首位置插入key,retList代表大于最小支持度的元素
        supportData[key]=support  #supportData代表每个元素的支持度
    return retList,supportData

def aprioriGen(LK,K):
    retList=[]
    lenLK=len(LK)
    for i in range(lenLK):
        for j in range(i+1,lenLK):
            L1=list(LK[i])[:K-2]
            L2=list(LK[j])[:K-2]
            L1.sort()
            L2.sort()
            if L1==L2:
                retList.append(LK[i]|LK[j])
    return retList