《机器学习实战》之十一——使用Apriori算法进行关联分析机器学习

Apriori算法目录

一、前言
二、关联分析
三、Apriori原理
四、利用Apriori算法来发现频繁集

1、Apriori算法及实例描述
2、生成候选项集
2、组织完整的Apriori算法

五、从频繁项集中挖掘关联规则
六、示例1：发现国会投票中的模式
七、示例2：发现毒蘑菇的相似特征
八、总结
参考文献

一、前言 【《机器学习实战》之十一——使用Apriori算法进行关联分析】??Apriori算法是一种用于关联规则挖掘（Association rule mining）的代表性算法，它同样位居十大数据挖掘算法之列。关联规则挖掘是数据挖掘中的一个非常重要的研究方向，也是一个由来已久的话题，它的主要任务就是设法发现事物之间的内在联系。
??机器学习和数据挖掘二者之间右相当多重合的内容，比如：决策树、SVM、k-means、KNN、Apriori等。我们都知道数据挖掘是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。而机器学习是以数据为基础、设法构建或训练出一个模型，进而利用这个模型来实现数据分析的一类技术。因此，数据挖掘可视为数据库、机器学习和统计学三者的交叉。数据库提供了数据管理技术，而机器学习和统计学提供了数据分析技术。
二、关联分析 ??许多商业企业在日复一日的运营中积累了大量的交易数据。例如，超市的收银台每天都收集大量的顾客购物数据。例如，下表给出了一个这种数据集的例子，我们通常称其为 购物篮交易（market basket transaction)。表中每一行对应一个交易，包含一个唯一标识 TID 和特定顾客购买的商品集合。零售商对分析这些数据很感兴趣，以便了解其顾客的购买行为。可以使用这种有价值的信息来支持各种商业中的实际应用，如市场促销，库存管理和顾客关系管理等等。

关联分析是一种大规模数据集中寻找有趣关系的任务。这些关系可以有两种形式：频繁项集或者关联规则。

- 频繁项集（frequent item sets）是经常出现在一块的物品的集合

- 关联规则（association rules）暗示两种物品之间可能存在很强的关系。

下面用购物篮交易来进行概念的说明：

文章图片

??令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 \ kk 个项，则称它为k \ kk 项集。显然，每个交易t i \mathit{t_{i}} ti? 包含的项集都是I \ II 的子集。
??关联规则是形如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 threshold
confidence ≥ minconf threshold

因此，大多数关联规则挖掘算法通常采用的一种策略是，将关联规则挖掘任务分解为如下两个主要的子任务。

频繁项集产生：其目标是发现满足最小支持度阈值的所有项集，这些项集称作频繁项集（frequent itemset）。
规则的产生：其目标是从上一步发现的频繁项集中提取所有高置信度的规则，这些规则称作强规则（strong rule）。
通常，频繁项集产生所需的计算开销远大于产生规则所需的计算开销。

最容易想到、也最直接的进行关联关系挖掘的方法或许就是暴力搜索（Brute-force）的方法：

List all possible association rules
Compute the support and confidence for each rule
Prune 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=1
Generate frequent itemsets of length kk
Repeat until no new frequent itemsets are identified
- Generate length (kk+1) candidate itemsets from length kk frequent itemsets
- Prune candidate itemsets containing subsets of length kk+1 that are infrequent
- Count the support of each candidate by scanning the DB
- Eliminate 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-1k?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的所有候选项集的集合C1 Parameters： dataSet：数据集 Returns：项集C1的列表 """ def createC1(dataSet): C1 = []#初始化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中的每项构建一个被"冰冻"的集合，用户不能修改他们""" 函数说明：将C1生成L1 Parameters： 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] = 1 else: ssCnt[can] += 1 numItems = float(len(D)) retList = [] supportData = https://www.it610.com/article/{} 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文件中，加入如下代码：

""" 函数说明：创建候选项集Ck Parameters： 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)#创建候选项集C1 D = list(map(set, dataSet))#构建集合表示的数据集 L1, supportData = https://www.it610.com/article/scanD(D, C1, minSupport)#生成频繁项集L1，以及对应的支持数据 L = [L1]#频繁项集列表化 k = 2 while (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 += 1 return L, supportDataif __name__ == '__main__': dataSet = loadDataSet() L, suppData = https://www.it610.com/article/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 merging Hmp1 = 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 merge rulesFromConseq(freqSet, Hmp1, supportData, br1, minConf)if __name__ == '__main__': dataSet = loadDataSet() L, suppData = https://www.it610.com/article/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 = https://www.it610.com/article/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., 2008. 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-family.com/papers/vldb94apriori.pdf)
【3】Pang-Ning Tan, Micheale Steinbach, Vipin Kumar. 数据挖掘导论，范明，等译. 人民邮电出版社，2011
【4】《机器学习实战》第十一章利用Apriori算法来发现频繁集
【5】博客：https://blog.csdn.net/baimafujinji/article/details/53456931