Apriori算法目录
一、前言二、关联分析三、Apriori原理四、利用Apriori算法来发现频繁集1、Apriori算法及实例描述2、生成候选项集2、组织完整的Apriori算法 五、从频繁项集中挖掘关联规则六、示例1：发现国会投票中的模式七、示例2：发现毒蘑菇的相似特征八、总结参考文献一、前言
Apriori算法是一种用于关联规则挖掘（Association rule mining）的代表性算法，它同样位居十大数据挖掘算法之列。关联规则挖掘是数据挖掘中的一个非常重要的研究方向，也是一个由来已久的话题，它的主要任务就是设法发现事物之间的内在联系。
机器学习和数据挖掘二者之间右相当多重合的内容，比如：决策树、SVM、k-means、KNN、Apriori等。我们都知道数据挖掘是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。而机器学习是以数据为基础、设法构建或训练出一个模型，进而利用这个模型来实现数据分析的一类技术。因此，数据挖掘可视为数据库、机器学习和统计学三者的交叉。数据库提供了数据管理技术，而机器学习和统计学提供了数据分析技术。
二、关联分析
许多商业企业在日复一日的运营中积累了大量的交易数据。例如，超市的收银台每天都收集大量的顾客购物数据。例如，下表给出了一个这种数据集的例子，我们通常称其为购物篮交易（market basket transaction)。表中每一行对应一个交易，包含一个唯一标识TID和特定顾客购买的商品集合。零售商对分析这些数据很感兴趣，以便了解其顾客的购买行为。可以使用这种有价值的信息来支持各种商业中的实际应用，如市场促销，库存管理和顾客关系管理等等。
下面用购物篮交易来进行概念的说明：
令 I = { i 1 , i 2 , . . . , i d } \mathbf{I=\left \{ i_{1}, i_{2},... ,i_{d} \right \}} I={i1,i2,...,id} 是购物篮数据中所有项的集合，而 T = { t 1 , t 2 , . . . , t N } \mathbf{T=\left \{ t_{1}, t_{2},... ,t_{N} \right \}} T={t1,t2,...,tN} 是所有交易的集合。
包含0个或多个项的集合被称为项集（itemset）。如果一个项集包含 k \ k k 个项，则称它为 k \ k k 项集。显然，每个交易 t i \mathit{t_{i}} ti 包含的项集都是 I \ I I 的子集。
关联规则是形如 X → Y \mathbf{X\rightarrow Y} X→Y 的蕴涵表达式，其中 X \mathbf{X} X 和 Y \mathbf{Y} Y是不相交的项集，即 X ∩ Y = Φ \mathbf{X\cap Y=\Phi } X∩Y=Φ。
关联规则的强度可以用它的支持度（support）和置信度（confidence）来度量。支持度确定规则可以用于给定数据集的频繁程度，而置信度确定 Y \mathbf{Y} Y 在包含 X \mathbf{X} X 的交易中出现的频繁程度。支持度（s：Fraction of transactions that contain both X and Y）和置信度（c：How often items in Y appear in transactions that contain X）这两种度量的形式定义如下：
例如考虑规则 { M i l k , D i a p e r } → { B e e r } \mathbf{\left \{ Milk,Diaper \right \}\rightarrow \left \{ Beer \right \}} {Milk,Diaper}→{Beer}，则易得：
三、Apriori原理
Association Rule Mining Task：Given a set of transactions T, the goal of association rule mining is to find all rules having
support ≥ minsup thresholdconfidence ≥ minconf threshold
因此，大多数关联规则挖掘算法通常采用的一种策略是，将关联规则挖掘任务分解为如下两个主要的子任务。
频繁项集产生：其目标是发现满足最小支持度阈值的所有项集，这些项集称作频繁项集（frequent itemset）。规则的产生：其目标是从上一步发现的频繁项集中提取所有高置信度的规则，这些规则称作强规则（strong rule）。
通常，频繁项集产生所需的计算开销远大于产生规则所需的计算开销。
最容易想到、也最直接的进行关联关系挖掘的方法或许就是暴力搜索（Brute-force）的方法：
List all possible association rulesCompute the support and confidence for each rulePrune rules that fail the minsup and minconf thresholds
然而，由于Brute-force的计算量过大，所以采用这种方法并不现实.格结构（Lattice structure）常被用来枚举所有可能的项集。如下图所示为 I = { a , b , c , d , e } \mathbf{ I=\left \{ a, b, c, d, e \right \}} I={a,b,c,d,e} 的项集格。一般来说，排除空集后，一个包含 k \mathbf{k} k 个项的数据集可能产生 2 k − 1 \mathbf{2^{k}-1} 2k−1 个频繁项集。由于在实际应用中 k \mathbf{k} k 的值可能非常大，需要探查的项集搜索空集可能是指数规模的。
发现频繁项集的一种原始方法是确定格结构中每个候选项集（candidate itemset）的支持度计数。为了完成这一任务，必须将每个候选项集与每个交易进行比较，如下图所示。如果候选项集包含在交易中，则候选项集的支持度计数增加。例如，由于项集 { B r e a d , M i l k } \mathbf{\left \{ Bread, Milk \right \}} {Bread,Milk} 出现在事务1、4 和5中，其支持度计数将增加3次。这种方法的开销可能非常大，因为它需要进行 O ( N M w ) \mathit{O\left ( NMw \right )} O(NMw) 次比 较，其中 N \mathit{N} N是交易数， M = 2 k − 1 \mathit{M=2^{k}-1} M=2k−1 是候选项集数，而 w \mathit{w} w 是交易的最大宽度（也就是交易中最大的项数）。
在上面，我们已经看到 Brute-force 在实际中并不可取。我们必须设法降低产生频繁项集的计算复杂度。此时我们可以利用支持度对候选项集进行剪枝，这也是Apriori所利用的第一条先验原理：
Apriori定律1：如果一个集合是频繁项集，则它的所有子集都是频繁项集。
例如：假设一个集合{A,B}是频繁项集，即A、B同时出现在一条记录的次数大于等于最小支持度min_support，则它的子集 {A},{B} 出现次数必定大于等于min_support，即它的子集都是频繁项集。
Apriori定律2：如果一个集合不是频繁项集，则它的所有超集都不是频繁项集。
举例：假设集合{A}不是频繁项集，即A出现的次数小于 min_support，则它的任何超集如{A,B}出现的次数必定小于min_support，因此其超集必定也不是频繁项集。
下图表示当我们发现{A,B}是非频繁集时，就代表所有包含它的超集也是非频繁的，即可以将它们都剪除。
四、利用Apriori算法来发现频繁集
1、Apriori算法及实例描述
R. Agrawal 和 R. Srikant于1994年在文献【2】中提出了Apriori算法，该算法的描述如下：
Let kk=1Generate frequent itemsets of length kkRepeat until no new frequent itemsets are identified Generate length (kk+1) candidate itemsets from length kk frequent itemsetsPrune candidate itemsets containing subsets of length kk+1 that are infrequentCount the support of each candidate by scanning the DBEliminate candidates that are infrequent, leaving only those that are frequent
或者在其他资料上更为常见的是下面这种形式化的描述（注意这跟前面的文字描述是一致的）：
下面是一个具体的例子，最开始数据库里有4条交易，{A、C、D}，{B、C、E}，{A、B、C、E}，{B、E}，使用min_support=2作为支持度阈值，最后我们筛选出来的频繁集为{B、C、E}。
上述例子中，最值得我们从 L 2 L_{2} L2到 C 3 C_{3} C3的这一步。这其实就是在执行伪代码中第一个蓝色框条所标注的地方： C k + 1 = G e n e r a t e C a n d i d a t e s ( L k ) C_{k+1}=GenerateCandidates(L_{k}) Ck+1=GenerateCandidates(Lk)，具体来说在Apriori算法中，它所使用的策略如下：
可见生成策略由两部分组成，首先是self-joining部分。例如，假设我们有一个 L 3 = { a b c , a b d , a c d , a c e , b c d } L3=\left \{ abc, abd, acd, ace, bcd \right \} L3={abc,abd,acd,ace,bcd}（注意这已经是排好序的}。选择两个itemsets，它们满足条件：前 k − 1 \ k-1 k−1 个 item 都相同，但最后一个item不同，把它们组成一个新的 C k + 1 C_{k+1} Ck+1 的项集 c。如下图所示，{abc} 和 {abd} 组成{abcd}，{acd}和{ace}组成{acde}。生成策略的第二部分是pruning。对于一个位于 C k + 1 C_{k+1} Ck+1 中的项集 c，s是c的大小为k的子集，如果s不存在于 L k L_{k} Lk 中，则将c从 C k + 1 C_{k+1} Ck+1 中删除。如下图所示，因为 {acde} 的子集{cde}并不存在于 L 3 L_{3} L3 中，所以我们将{acde}从 C 4 C_{4} C4 中删除。最后得到的 C 4 C_{4} C4 ，仅包含一个项集{abcd}。
回到之前的例子，从 L 2 L_{2} L2 到 C 3 C_{3} C3 的这一步，我们就只能获得{B、C、E}。以上便是Apriori算法的最核心思想。当然在具体实现的时候，如何Count Supports of Candidates也是需要考虑的问题，我们这里略去这部分内容的讨论，有兴趣读者可以参阅文献【3】以了解更多。
2、生成候选项集
在使用Python来对整个程序编码之前，需要创建一些辅助函数。下面会创建一个用于创建初始集合的函数，也会创建一个通过扫描数据集以寻找交易记录子集的函数。
新建一个apriori.py文件，并在其中写入如下代码：
# -*- coding: utf-8 -*-def loadDataSet():return [[1,3,4], [2,3,5], [1,2,3,5], [2,5]]"""函数说明：生成大小为1的所有候选项集的集合C1Parameters：dataSet：数据集Returns：项集C1的列表"""def createC1(dataSet):C1 = [] #初始化C1for transaction in dataSet: #循环数据集中的每项交易for item in transaction: #循环交易中的每项if not [item] in C1:C1.append([item])C1.sort()return list(map(frozenset, C1)) #C1中的每项构建一个被"冰冻"的集合，用户不能修改他们"""函数说明：将C1生成L1Parameters：D: 集合表示的数据集Ck: 候选项集列表minSupport: 最小支持度Returns：retList: 频繁项集的列表supportData: 频繁项集以及支持度的字典"""def scanD(D, Ck, minSupport):ssCnt = {}for tid in D:for can in Ck:if can.issubset(tid):if can not in ssCnt:ssCnt[can] = 1else:ssCnt[can] += 1numItems = float(len(D))retList = []supportData = {}for key in ssCnt:support = ssCnt[key]/numItems #计算支持度if support >= minSupport: #将满足最小支持度的项集保存retList.insert(0, key)supportData[key] = support #添加到字典supportData中return retList, supportDataif __name__ == '__main__':dataSet = loadDataSet()print("dataSet:",dataSet)C1 = createC1(dataSet)print("C1",C1)D = list(map(set, dataSet)) #构建集合表示的数据集print("D:",D)L1, supportData0 = scanD(D, C1, 0.5)print("L1:",L1)
运行结果如下：
从上面的运行结果我们可以看出C1是只包含1个元素的项集。D是构建的集合表示的数据集。生成的频繁项集列表L1，该列表中的每个项集至少出现在50%以上的记录中，由于物品4并没有达到最小支持度，所以没有包含在L1中。
2、组织完整的Apriori算法
整个Apriori算法的伪代码如下：
在集合中项的个数大于0时：
构建一个k个项组成的候选项集的列表
检查数据以确认每个项集都是频繁的
保留频繁项集并构建k+1项组成的候选项集的列表
在apriori.py文件中，加入如下代码：
"""函数说明：创建候选项集CkParameters：Lk：频繁项集列表k： 项集元素个数Returns：retList: 候选项集列表"""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和L2分别为对应的前k-2个项L1.sort(); L2.sort()if L1 == L2: #前k-2个项相同时，将两个集合合并retList.append(Lk[i] | Lk[j])return retList"""函数说明： Apriori算法Parameters：dataSet：数据集minSupport：最小支持度Returns：L：频繁项集列表supprotData：支持数据集"""def apriori(dataSet, minSupport=0.5):C1 = createC1(dataSet) #创建候选项集C1D = list(map(set, dataSet)) #构建集合表示的数据集L1, supportData = scanD(D, C1, minSupport) #生成频繁项集L1，以及对应的支持数据L = [L1] #频繁项集列表化k = 2while (len(L[k-2]) > 0):Ck = aprioriGen(L[k-2], k) #生成候选项集C2、C3、C4……Lk, supK = scanD(D, Ck, minSupport) #生成频繁项集L2、L3、L4……以及对应的支持数据supportData.update(supK) #更新支持数据集L.append(Lk)k += 1return L, supportDataif __name__ == '__main__':dataSet = loadDataSet()L, suppData = apriori(dataSet, 0.5)print("L:\n",L)print("L0:\n",L[0])print("L1:\n",L[1])print("L2:\n",L[2])print("L3:\n",L[3])
运行结果如下：
上述结果是在最小支持度为50%的情况下得到的，其中的变量suppData是一个字典，它包含我们项集的支持度值。其实我们也可以尝试一下70%的支持度。看看哪些项出现在70%以上的记录中。
另外，我们要重点看一下L2是怎么得到的。首先输出看一下C3是什么？打印输出一下：
根据上面候选项集的生成方法的介绍，我们确实能够很容易得到C3就是应该是 {2,3,5}
还有一个要理解的代码中的 k-2。这里重点要看的是C2的生成步骤，首先L=[L1]， 这样L[0]=L1， 因为 L1中的每个项集都是一个元素，而 list( L1[0])[:0] 得到的是 [ ]，同样的， list( L1[1])[:0] 得到的也是 [ ]， 由于前面的k-2项相同，合并L1和L2
五、从频繁项集中挖掘关联规则
人们最常寻找的两个目标是频繁项集与关联规则，上面我们已经介绍了如何使用Apriori算法来发现频繁项集，现在需要解决的问题是如何找出关联规则。
要找到关联规则，我们首先从一个频繁项集开始。我们知道集合中的元素是不重复的，但我们项知道基于这些元素能否获得其他内容。某个元素或者某个元素的集合可能会推导出另一个元素。从杂货店的例子可以得到，如果右一个频繁项集 {豆奶，莴苣} ， 那么就可能有一条关联规则 “豆奶→莴苣”。这意味着如果有人购买了豆奶，那么在统计上他会购买莴苣的概率较大。但是，这一条反过来并不总是成立。也就是说，即使“豆奶→莴苣” 统计上显著，那么“莴苣→豆奶”也不一定成立。（从逻辑研究上来讲，箭头左边的集合称作前件， 箭头右边的集合称作后件。）
频繁项集的量化定义，即它得满足最小支持度要求。对于关联规则，我们也有类似的量化方法，这种量化指标称为可信度。
类似于前面的频繁项集的生成，我们可以为每个频繁项集产生许多关联规则。如果能够减少规则数目来确保问题的可解性，那么计算起来就会好很多。从下面的图，可以观察到，如果某个规则并不满足最小可信度要求，那么该规则的所有子集也不会满足最小可信度要求。可以利用这个规则来 减少需要测试的规则数目。利用Apriori算法，可以首先从一个频繁项集合开始，创建一个规则列表。规则右部包含一个元素，然后对这些规则测试。接下来合并所有剩余 规则来创建一个新的规则列表，其中规则的右部包含两个元素。这种方法称为分级法 。
打开apriori.py文件，在其中加入如下代码：
"""函数说明： 生成关联规则Parameters：L：频繁项集列表supportData：支持数据字典minConf：最小置信度Returns：bigRuleList：关联规则列表"""def generateRules(L, supportData, minConf=0.7):bigRuleList = []for i in range(1, len(L)): #只获取两个或者更多的频繁项集合,L0是频繁1项集，没关联规则 for freqSet in L[i]:#H1存放频繁i项集的某个频繁项集的单个元素集合，频繁3项集的{0,1,2}的{{0},{1},{2}}# print("Li:",L[i])H1 = [frozenset([item]) for item in freqSet] #将每个元素拆出来这个是右边被推出的项集 # print("H1：:",H1)if (i>1):#从频繁3项集开始，从置信度算出关联规则rulesFromConseq(freqSet, H1, supportData, bigRuleList, minConf)else:#对频繁2项集，计算置信度calcConf(freqSet, H1, supportData, bigRuleList, minConf)return bigRuleList"""函数说明：计算置信度Parameters：freqSet：频繁项集H：对频繁项集创建的单个元素集合的列表supportData：支持数据字典br1：关联规则列表minConf：最小可信度Returns：prunedH：被剪枝的满足最小可信度要求的可以出现在规则右部的元素列表"""def calcConf(freqSet, H, supportData, br1, minConf=0.7):prunedH = []for conseq in H:#conf({2}) = s({{0},{1},{2}})/s({{0},{1},{2}}-{2})conf = supportData[freqSet]/supportData[freqSet-conseq]if conf >= minConf:print(freqSet-conseq, "-->", conseq, 'conf:', conf) #那么有{{0},{1}}——>{{2}}br1.append((freqSet-conseq, conseq, conf))prunedH.append(conseq)return prunedH"""函数说明：从置信度算出关联规则Parameters：freqSet：频繁项集H：对频繁项集创建的可以出现在规则右部的元素列表supportData：支持数据字典br1：关联规则列表minConf：最小可信度Returns：无"""def rulesFromConseq(freqSet, H, supportData, br1, minConf=0.7):m = len(H[0]) #m,频繁m项集if (len(freqSet) > (m+1)): #try further mergingHmp1 = aprioriGen(H, m+1) #由H，创建m+1候选项集# print("生成的候选Hmp1:", Hmp1)Hmp1 = calcConf(freqSet, Hmp1, supportData, br1, minConf) #保留符合置信度的m+1项集# print("剪枝之后的Hmp1:",Hmp1)if (len(Hmp1)>1): #need at least two sets to mergerulesFromConseq(freqSet, Hmp1, supportData, br1, minConf)if __name__ == '__main__':dataSet = loadDataSet()L, suppData = apriori(dataSet, 0.5)print("L:\n",L)print("L0:\n",L[0])print("L1:\n",L[1])print("L2:\n",L[2])print("L3:\n",L[3])print("supportData:", suppData)rules = generateRules(L, suppData, minConf=0.5)print(rules)
上述代码中包含三个函数。其中generateRules()是主函数，它调用其他两个函数。其他两个函数rulesFromConseq()和calcConf()，分别用于生成候选规则集合以及对规则进行置信度的计算与剪枝。
代码中注释掉了一些打印输出的项，如果你对上述程序不理解的话，可以打印出这些变量，然后手动推导一下程序的过程，会很好地加深对上述代码的理解。
另外，我们可以降低可信度阈值，一旦降低了可信度阈值，就可以获得更多的规则。到现在为止，我们看到上述程序能够在一个小数据集上正常运行，接下来将在一个更大的真实数据集上测试一下效果。
六、示例1：发现国会投票中的模式
前面我们已经发现频繁项集及关联规则，现在是时候把这些工具用在真实的数据上了。那么可以使用什么杨的数据呢？购物是一个很好的例子，但是前面已经用过了。另一个例子是搜索引擎中的查询词。这个示例听上去不错，不过下面看到的是一个更有趣的美国国会议员投票的例子。
可惜，书上提到的API在python3 上面无法工作，所以就不做更多的操作了。。。。。
七、示例2：发现毒蘑菇的相似特征
有时候我们并不想寻找所有频繁项集，而只对包含某个特定元素项的项集感兴趣。在本章这个最后的例子中，我们会寻找毒蘑菇中的一些公共特征，利用这些特征就能避免吃到那些有毒的蘑菇。UCI的机器学习数据集合中有一个关于肋形蘑菇的23种特征的数据集，每一个特征都包含一个标称数据值。我们必须将这些标称值转化为一个集合。幸运的是，已经有人做好了这种转换。Roberto Bayardo对UCI蘑菇数据集进行了解析，将每个蘑菇样本转换成一个特征集合。其中，枚举了每个特征的所有可能值，如果某个样本包含特征，那么该特征对应的整数值被包含数据集中。下面看一下该数据集。打开文件mushroom.dat
在上述数据中，第一个特征表示有毒或者可食用。如果某样本有毒，则值为2。如果可食用，则值为1.下一个特征是蘑菇伞的形状，有六种可能的值，分别用整数3-8来表示。
在apriori.py文件中写入如下的代码：
if __name__ == '__main__': mushDatSet = [line.split() for line in open("mushroom.dat").readlines()]print("共 %d 条数据："%len(mushDatSet))L, suppData = apriori(mushDatSet, minSupport=0.3)for item in L[1]:if item.intersection('2'):print(item)for item in L[3]:if item.intersection('2'):print(item)
在结果中搜索包含有毒特征值2的频繁项集，运行结果如下：
接下来你需要观察一下这些特征，以便知道了解野蘑菇的那些方面。如果看到其中任何一个特征，那么这些蘑菇就不要吃了。当然，最后还要声明一下：尽管上述这些特征在毒蘑菇中很普通，但是没有这些特征并不意味该蘑菇就是可食用的。如果吃错了蘑菇，你可能会因此丧命。
八、总结
1、关联分析是用于发现大数据中元素间有趣关系的一个工具集，可以采用两种方式来量化这些有趣的关系。第一种方式是使用频繁项集，它会给出经常在一起出现的元素项。第二种方式是关联规则，每条关联规则意味着元素项之间的“如果……那么”关系。
2、在频繁规则的发现和关联规则的发现过程中，都使用了Apriori原理来减少在数据库上进行检查的集合的数目。
3、关联分析可以用在许多不同物品上。商店中的商品以及网站的访问页面是其中比较常见的例子。
4、每次增加频繁项集的大小，Apriori算法都会重新扫描整个数据集。当数据集很大时，这会显著降低频繁项集发现的速度。下一章会介绍FP-growth算法，和Apriori算法相比，该算法只需要对数据库进行两次遍历，能够显著加快发现频繁项集的速度。
参考文献
【1】Wu, X., Kumar, V., Quinlan, J.R., Ghosh, J., Yang, Q., Motoda, H., McLachlan, G.J., Ng, A., Liu, B., Philip, S.Y. and Zhou, Z.H., . Top 10 algorithms in data mining. Knowledge and information systems, 14(1), pp.1-37.
【2】Rakesh Agrawal and Ramakrishnan Srikant Fast algorithms for mining association rules in large databases. Proceedings of the 20th International Conference on Very Large Data Bases, VLDB, pages 487-499, Santiago, Chile, September 1994. (http://rakesh.agrawal-/papers/vldb94apriori.pdf)
【3】Pang-Ning Tan, Micheale Steinbach, Vipin Kumar. 数据挖掘导论，范明，等译. 人民邮电出版社，
【4】《机器学习实战》第十一章 利用Apriori算法来发现频繁集
【5】博客：/baimafujinji/article/details/53456931
如果觉得《《机器学习实战》之十一——使用Apriori算法进行关联分析》对你有帮助，请点赞、收藏，并留下你的观点哦！
