沃尔玛一家分店的营销经理对超市的销售数量进行设定跟踪，他发现了一个很奇怪的现象：啤酒与尿不湿的销量在周末总会出现成比例增长。他们立即对这个现象进行了分析和讨论，并且派出专门的人员在卖场内进行全天候的观察。他们发现这些顾客有几个共同的特点：
一般是周末出现这种情况购买者以已婚男士为主他们家中有孩子且不到两岁，有尿不湿的刚需他们喜欢看体育比赛节目，并且喜欢边喝啤酒边看，顾客有喝啤酒的需求周末是体育比赛扎堆的日子，所以出现这种关联销售多在周末的时候这位营销经理从中受到启发，他对超市的物品摆放进行了调整，将卖场内原来相隔很远的妇婴用品区与酒类饮料区的空间距离拉近，减少顾客的行走时间，将啤酒与尿不湿摆放在一起，同时将牛肉干等一些简便的下酒食品也摆放在一起，这样全年下来，营业额增加了几百万美元。 我们先不管这个故事的真实性与否，我们关心的是，是否能有一种较为通用的办法，从一份资料库中（如销售记录）中发现某些特征（如商品种类）之间的联系？这就是本文分享的内容——关联规则算法，它是从数据背后发现事物之间可能存在的关联或者联系。
(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 英['eɪprɑɪ’ɔ:rɪ] 美['eɪprɪ’ɔ:rɪ] adj. 先验的; <拉>由原因推及结果的; 演绎的; 推测的; 根据上面对于关联规则的定义，发现可以通过遍历所有组合能找到所有的频繁项集，但遍历所有组合花的时间太多、效率太低，假设有N个物品，那么一共需要计算2^(N-1)次。Apriori算法使用了基于***支持度的剪枝技术***来控制候选项集的指数级增长。原理是：
如果某个项集是频繁的，那么它的所有子集也是频繁的。如果某个项集是非频繁的，那么它所有的超集也是非频繁的。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)
一条规则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算法构建模型的全部内容，该算法不仅适用于零售行业，同样适用于穿衣搭配推荐、气象关联分析、交通事故成因分析、基于兴趣的时事新闻推荐、银行营销方案推荐等。
