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

本文主要是介绍《机器学习实战》笔记之十一——使用Apriori算法进行关联分析，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

第十一章 使用Apriori算法进行关联分析

• Apriori算法
• 频繁项集生成
• 关联规则生成

从大规模数据集中寻找物品间的隐含关系被称作为关联分析（association analysis）和关联规则学习（association rule learning）。

11.1 关联分析

关联分析有两种形式：频繁项集、关联规则。频繁项集（frequent item sets）是经常出现在一块的物品的集合，关联规则（association rules）暗示两种物品之间可能存在很强的关系。使用频繁项集和关联规则，商家可以更好地理解他们的顾客。

当寻找频繁项集时，有两个概念比较重要：支持度和可信度。

一个项集的支持度（support）被定义为数据集中包含该项集的记录所占的比例。由上图可以看出项集{豆奶}的支持度为4/5,项集{豆奶，尿布}的支持度为3/5。支持度是针对项集来说，因此可以定义一个最小支持度过滤较小支持度的项集。

可信度或置信度（confidence）是针对关联规则来定义的。可被定义为conf(B) = support({A,B})/support({A})。

支持度和置信度是用来量化关联分析是否成功的方法。

11.2 Apriori原理

上图显示了4种商品所有可能的组合。对给定的集合项集{0,3}，需要遍历每条记录并检查是否同时包含0和3,扫描完后除以记录总数即可得支持度。对于包含N种物品的数据集共有2的N次方-1种项集组合，即使100种，也会有1.26×10的30次方种可能的项集组成。

为降低计算时间，可用Apriori原理：如果某个项集是频繁的，那么它的所有子集也是频繁的。逆反：如果一个项集是非频繁集，那么它的所有超集也是非频繁的。

11.3 使用Apriori算法来发现频繁集

Apriori算法的两个输入参数分别是最小支持度和数据集。首先生成所有单个物品的项集列表，得到满足最小支持度的项集，将其进行组合生成包含两个元素的项集，继续剔除不满足最小支持度的项集，重复直到所有项集都被去掉。

数据集扫描的伪代码：

对数据集中的每条交易记录tran

每个候选集can

检查can是否是tran的子集

如果是，则增加can的计数值

对每个候选项集

如果其支持度不低于最小值，则保留该项集

返回所有频繁项集列表

整个Apriori算法的伪代码：

当集合中项集的个数大于0时

构建一个k个项集组成的候选项集列表

检查数据以确认每个项集都是频繁的

保留频繁项集并构建k+1项组成的候选项集的列表

coding:

<span style="font-size:18px;">#!/usr/bin/env python
# coding=utf-8
def  loadDataSet():return [[1,3,4],[2,3,5],[1,2,3,5],[2,5]]def createC1(dataSet):                  #构建所有候选项集的集合C1 = []for transaction in dataSet:for item in transaction:if not [item] in C1:C1.append([item])       #C1添加的是列表，对于每一项进行添加，{1},{3},{4},{2},{5}C1.sort()return map(frozenset, C1)           #使用frozenset，被“冰冻”的集合，为后续建立字典key-value使用。def scanD(D,Ck,minSupport):             #由候选项集生成符合最小支持度的项集L。参数分别为数据集、候选项集列表，最小支持度ssCnt = {}for tid in D:                       #对于数据集里的每一条记录for can in Ck:                  #每个候选项集canif can.issubset(tid):       #若是候选集can是作为记录的子集，那么其值+1,对其计数if not ssCnt.has_key(can):#ssCnt[can] = ssCnt.get(can,0)+1一句可破，没有的时候为0,加上1,有的时候用get取出，加1ssCnt[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] = supportreturn retList, supportDatadef aprioriGen(Lk, k):                  #创建符合置信度的项集Ck,retList = []lenLk   = len(Lk)for i in range(lenLk):for j in range(i+1, lenLk):     #k=3时，[:k-2]即取[0],对{0,1},{0,2},{1,2}这三个项集来说，L1=0，L2=0，将其合并得{0,1,2}，当L1=0,L2=1不添加，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 retListdef apriori(dataSet, minSupport = 0.5):C1 = createC1(dataSet)D  = map(set,dataSet)L1, supportData = scanD(D,C1,minSupport)L  = [L1]                           #L将包含满足最小支持度，即经过筛选的所有频繁n项集，这里添加频繁1项集k  = 2while (len(L[k-2])>0):              #k=2开始，由频繁1项集生成频繁2项集，直到下一个打的项集为空Ck = aprioriGen(L[k-2], k)Lk, supK = scanD(D, Ck, minSupport)supportData.update(supK)        #supportData为字典，存放每个项集的支持度，并以更新的方式加入新的supKL.append(Lk)k +=1return L,supportDatadataSet = loadDataSet()
C1 = createC1(dataSet)
print "所有候选1项集C1:\n",C1D = map(set, dataSet)
print "数据集D:\n",DL1, supportData0 = scanD(D,C1, 0.5)
print "符合最小支持度的频繁1项集L1:\n",L1L, suppData = apriori(dataSet)
print "所有符合最小支持度的项集L：\n",L
print "频繁2项集：\n",aprioriGen(L[0],2)
L, suppData = apriori(dataSet, minSupport=0.7)
print "所有符合最小支持度为0.7的项集L：\n",L
</span>

效果：

11.4 从频繁项集中挖掘关联规则

要找关联规则，从频繁项集开始，根据置信度算出频繁项集中出现的哪些商品必然可以推到出当中的另外一些商品，即找出频繁项集中各商品之间的关联规则。

每个频繁项集可以产生多个关联规则。如果某条规则并不满足最小可信度要求，那么该规则的所有子集也不会满足最小可信度要求。apriori算法，可以首先从一个频繁项集开始，接着创建一个规则列表，其中规则右部只包含一个元素，然后对这些规则进行测试，合并所有剩余规则来创建一个新的规则列表。

coding:

<span style="font-size:18px;">#===============关联规则生成函数==================
def generateRules(L, supportData, minConf = 0.7):bigRuleList = []                                                            #规则存放在bigRuleList列表中for i in range(1, len(L)):for freqSet in L[i]:                                                    #L0是频繁1项集，没关联规则H1 = [frozenset([item]) for item in freqSet]                        #H1存放频繁i项集的某个频繁项集的单个元素集合，频繁3项集的{0,1,2}的{{0},{1},{2}if i>1:rulesFromConseq(freqSet, H1, supportData, bigRuleList, minConf) #从频繁3项集开始，从置信度算出关联规则else:calcConf(freqSet, H1, supportData, bigRuleList, minConf)        #对频繁2项集，计算置信度return bigRuleListdef calcConf(freqSet, H, supportData, br1, minConf = 0.7):                      #计算置信度函数，prunedH = []for conseq in H:conf = supportData[freqSet]/supportData[freqSet - conseq]               #conf({2}) = s({{0},{1},{2}})/s({{0},{1},{2}}-{2})if conf >= minConf:print freqSet-conseq,"——>",conseq, "conf:",conf                     #那么有{{0},{1}}——>{{2}}br1.append((freqSet-conseq, conseq, conf))prunedH.append(conseq)return prunedHdef rulesFromConseq(freqSet, H, supportData, br1, minConf=0.7):m = len(H[0])                                                               #m,频繁m项集if (len(freqSet)) > (m+1):Hmp1 = aprioriGen(H, m+1)                                               #由H，创建m+1项集 Hmp1 = calcConf(freqSet, Hmp1, supportData, br1, minConf)               #保留符合置信度的m+1项集，Hmp1 = prunedHif (len(Hmp1)>1):rulesFromConseq(freqSet, Hmp1, supportData, br1, minConf)L,suppData = apriori(dataSet, minSupport=0.5)
rules      = generateRules(L,suppData, minConf=0.7)
print rulesrules      = generateRules(L,suppData, minConf=0.5)
print rules</span>

效果：

显然的，降低可信度阈值，获得更多的规则。

11.5 示例：发现毒蘑菇的相似特征

数据：

第一个特征表示有毒或者可食用，1为可食用，2为有毒。第二列为整数3-8的6种可能的蘑菇伞的形状。对所有频繁项集并不是那么感兴趣，而是对特定是否有毒这个元素项的项集感兴趣。可通过apriori找出所有跟是否有毒这个特征相关的项集。

coding:

mushDatSet  = [line.split() for line in open("mushroom.dat").readlines()]
L, suppData = apriori(mushDatSet, minSupport=0.3)
for item in L[1]:if item.intersection("2"):print itemfor item in L[3]:if item.intersection("2"):print item

效果：

11.6 小结

关联分析是用于发现大数据集中元素间有趣关系的agiel工具集，可用频繁项集和关联规则这两种方式度量。发现元素间的不同组合比较耗时，apriori算法显得比较高效。如果一个元素项是不频繁的，那么包含该元素的超集也是不频繁的。

每次增加频繁项集的大小，apriori算法都会重新扫描整个数据集，当数据集很大时，会降低频繁项集发现的速度。

python有数据挖掘的工具包pymining，里面实现了分词，聚类，关联分析等功能，可以参考

github：https://github.com/bartdag/pymining

博客：http://www.cnblogs.com/LeftNotEasy/archive/2011/02/27/py_mining_first_release.html

这篇关于《机器学习实战》笔记之十一——使用Apriori算法进行关联分析的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---