关联规则挖掘算法之Apriori算法

沃尔玛一家分店的营销经理对超市的销售数量进行设定跟踪，他发现了一个很奇怪的现象：啤酒与尿不湿的销量在周末总会出现成比例增长。他们立即对这个现象进行了分析和讨论，并且派出专门的人员在卖场内进行全天候的观察。他们发现这些顾客有几个共同的特点：

一般是周末出现这种情况
购买者以已婚男士为主
他们家中有孩子且不到两岁，有尿不湿的刚需
他们喜欢看体育比赛节目，并且喜欢边喝啤酒边看，顾客有喝啤酒的需求
周末是体育比赛扎堆的日子，所以出现这种关联销售多在周末的时候

这位营销经理从中受到启发，他对超市的物品摆放进行了调整，将卖场内原来相隔很远的妇婴用品区与酒类饮料区的空间距离拉近，减少顾客的行走时间，将啤酒与尿不湿摆放在一起，同时将牛肉干等一些简便的下酒食品也摆放在一起，这样全年下来，营业额增加了几百万美元。
我们先不管这个故事的真实性与否，我们关心的是，是否能有一种较为通用的办法，从一份资料库中（如销售记录）中发现某些特征（如商品种类）之间的联系？这就是本文分享的内容——关联规则算法，它是从数据背后发现事物之间可能存在的关联或者联系。

一．关联规则挖掘中的几个基本概念

(1)事务数据库：存储着二维结构的记录集。设I={i1，i，…，im}是一个全局项的集合，事务数据库D={t1,t2,…tn}是若干事务的集合，每个事务ti(1≤i≤n)都对应I上的一个子集，例如t1={Bread,Milk}。

（2）项集：包含0个或者多个项的集合称为项集。
（3）关联规则：表示项集之间的关系，是形如X->Y的蕴含表达式，其中X和Y是不相交的项集，X称为规则的前件，Y称为规则的后件。例如{Beer}->{Diaper}关联规则表示买啤酒的人也会购买尿布。项集和项集之间组合可以产生很多规则，但不是每个规则都是有用的，我们需要一些限定条件来帮助我们找到强度高的规则。
（4）支持度(support)：表示关联数据在数据集中出现的次数或所占比例。

（5）置信度（confidence）:表示X和Y同时出现的概率占Y出现概率的比值。

（6）频繁项集：在项集中频繁出现并满足最小支持度阈值的集合，例如{Milk，Bread}等。
（7）强关联规则：满足最小置信度的频繁项集。关联规则挖掘的目的就是找出强关联规则。
目前关联规则的挖掘过程大致可以总结为两步：

找出所有的频繁项集；
由频繁项集产生规则，从中提取满足最小置信度的强关联规则。

二．Apriori关联规则算法

apriori 英['eɪprɑɪ’ɔ:rɪ] 美['eɪprɪ’ɔ:rɪ] adj. 先验的; <拉>由原因推及结果的; 演绎的; 推测的;
根据上面对于关联规则的定义，发现可以通过遍历所有组合能找到所有的频繁项集，但遍历所有组合花的时间太多、效率太低，假设有N个物品，那么一共需要计算2^(N-1)次。Apriori算法使用了基于***支持度的剪枝技术***来控制候选项集的指数级增长。原理是：

如果某个项集是频繁的，那么它的所有子集也是频繁的。
如果某个项集是非频繁的，那么它所有的超集也是非频繁的。

1.找出所有的频繁项集

Apriori算法采用了逐层迭代的方法，先搜索出候选1项集及对应的支持度，剪枝去掉低于支持度的1项集，得到频繁1项集。然后对剩下的频繁1项集进行连接，得到候选2项集，筛选去掉低于支持度的候选2项集，得到频繁项集，以此类推，迭代下去，直到无法找到频繁k+1项集为止，对应的频繁k项集的集合即为算法的输出结果。
可见这个算法还是很简洁的，第i次的迭代过程包括扫描计算候选i项集的支持度，剪枝得到频繁i项集和连接生成候选i+1项集三步。

代码如下：

def loadDataSet():
return [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]
#输入数据集
#输出候选项集列表C1
def createC1(dataSet):
    C1 = []
    for transaction in dataSet:
        for item in transaction:
            if not [item] in C1:
                C1.append([item])
    C1.sort()
    return list(map(frozenset, C1))  #对C1中每个项构建一个不变集合

#输入数据集，候选项集列表Ck，最小支持度
#输出频繁项集列表Lk，Ck各项的支持度
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
    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

#输入频繁项集列表Lk、项集元素个数
#输出下一个候选项集Ck
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

#输入数据集，候选项集Ck，最小支持度
#输出所有频繁项集列表，各项的支持度
def apriori(dataSet, minSupport = 0.5):
    C1 = createC1(dataSet)
    D = list(map(set, dataSet))
    L1, supportData = scanD(D, C1, minSupport)  #
    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)  #将supK的键值对添加到supportData
        L.append(Lk)
        k += 1
    return L, supportData

if __name__ == '__main__':
    dadaset = loadDataSet()
    L, supportData = apriori(dadaset, minSupport=0.5)
    print(L)
    for k in supportData:
        print(k, supportData[k])

在本例中，最小支持度为0.5，候选项集中所有支持度小于0.5的都去除构成频繁项集：
1-候选项集C1: ({1}：0.5、{2}：0.75、{3}：0.75、{4}：0.25、{5}：0.75)
1-频繁项集L1: ({1}：0.5、{2}：0.75、{3}：0.75、{5}：0.75)

2-候选项集C2: ({1,2}：0.25、{1,3}：0.5、{1,5}：0.25、{2,3}：0.5、{2,5}：0.75、{3,5}：0.5)
2-频繁项集L2：({1,3}：0.5、{2,3}：0.5、{2,5}：0.75、{3,5}：0.5)

3-候选项集C3：({2,3,5}：0.5)
注：{1,2,3}、{1,3,5}没有列入C3中是因为子集{1,2}、{1,5}不在2-频繁项集中
3-频繁项集L3：({2,3,5}：0.5)

2. 生成关联规则

一条规则A→B的置信度定义为在A发生的同时B发生的概率，计算公式为 p(AB)/P(A)，其中A称为前件，B称为后件。
关联规则的生成也是使用逐层迭代方法，初始提取规则后件只有一个项的所有高置信度规则，使用最小置信度对这些规则进行测试，接下来合并剩下的规则来创建一个新的规则列表，不断增加后件的项数，直到候选规则列表为空。
如果逐个计算置信度，所耗费的时间也非常多。通过计算可以发现：如果某条规则不满足最小置信度要求，那么该规则的所有前件的子集也不会满足最小置信度要求，这将大大降低计算难度。比如{012} →{3}不满足最小置信度要求，则前件{012} 的任意子集构成的规则，即图中灰色规则，都不满足最小置信度。

代码如下：

#输入频繁项集列表、频繁项集的支持度字典、最小置信度
#输出包含置信度的规则列表
def generateRules(L, supportData, minConf=0.5):
    bigRuleList = []
    for i in range(1, len(L)):
        for freqSet in L[i]:
            H1 = [frozenset([item]) for item in freqSet]   #规则后件集合
            if (i > 1):
                rulesFromConseq(freqSet, H1, supportData, bigRuleList, minConf)
            else:
                calcConf(freqSet, H1, supportData, bigRuleList, minConf)
    return bigRuleList

#置信度计算函数
def calcConf(freqSet, H, supportData, brl, minConf=0.5):
    prunedH = []
    for conseq in H:
        conf = supportData[freqSet]/supportData[freqSet-conseq]#集合相减
        if conf >= minConf:
            print(f'{freqSet-conseq} --> {conseq} conf:{conf}')
            brl.append((freqSet-conseq, conseq, conf))
            prunedH.append(conseq)
    return prunedH

#关联规则合并函数
def rulesFromConseq(freqSet, H, supportData, brl, minConf=0.5):
    m = len(H[0])
    if (len(freqSet) > (m + 1)):
        Hmp1 = aprioriGen(H, m+1)
        Hmp1 = calcConf(freqSet, Hmp1, supportData, brl, minConf)
        if (len(Hmp1) > 1):
            rulesFromConseq(freqSet, Hmp1, supportData, brl, minConf)

if __name__ == '__main__':
    dadaset = loadDataSet()
    L, supportData = apriori(dadaset, minSupport=0.5)
    print('----所有频繁项集----')
    print(L)
    print('----各项集的支持度----')
    for k in supportData:
        print(k, supportData[k])
    print('----满足最小置信度的关联规则----')
    generateRules(L, supportData, minConf=0.5)

本例中，对于所有的频繁项集{1}、{2}、{3}、{1,3}、{2,3}、{2,5}、{3,5}、{2,3,5}，可能的规则及置信度分别为：
1→3：1.0
3→1：0.6667
2→3：0.6667
3→2：0.6667
2→5：1.0
5→2：1.0
3→5：0.6667
5→3：0.6667
(2,3)→5：1.0
(2,5)→3：0.6667
(3,5)→2：1.0
2→(3,5): 0.6667
3→(2,5): 0.6667
5→(2,3): 0.6667

当先锋百科网

关联规则挖掘算法之Apriori算法