使用Apriori算法进行关联规则分析（2）

使用Apriori算法进行关联分析

关联分析

Apriori算法

优点:易编码实现。

缺点:在大数据集上可能较慢。

适用数据类型:数值型或者标称型数据。

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

集或者关联规则。频繁项集(frequent item sets)是经常出现在一块的物品的集合，关联规则

( association rules)暗示两种物品之间可能存在很强的关系。

一个项集的支持度(support)被定义为数据集中包含该项集的记录所占的比例。从图11-1中

可以得到，{豆奶}的支持度为4/5。而在5条交易记录中有3条包含{豆奶，尿布}，因此王豆奶，尿

布}的支持度为3/5。支持度是针对项集来说的，因此可以定义一个最小支持度，而只保留满足最

小支持度的项集。

可信度或置信度(confidence)是针对一条诸如{尿布}‘{葡萄酒}的关联规则来定义的。这

条规则的可信度被定义为“支持度({尿布，葡萄酒”伎持度({尿布””。从图11-1中可以看到，由

于{尿布，葡萄酒}的支持度为3/5，尿布的支持度为4/5，所以“尿布‘葡萄酒”的可信度为3/4=0.75 0

这意味着对于包含“尿布”的所有记录，我们的规则对其中75%的记录都适用。

总结：

关联分析是用于发现大数据集中元素间有趣关系的一个工具集，可以采用两种方式来量化这

些有趣的关系。第一种方式是使用频繁项集，它会给出经常在一起出现的元素项。第二种方式是

关联规则，每条关联规则意味着元素项之间的“如果……那么”关系。

发现元素项间不同的组合是个十分耗时的任务，不可避免需要大量昂贵的计算资源，这就需

要一些更智能的方法在合理的时间范围内找到频繁项集。能够实现这一目标的一个方法是Apriori算法

它使用Apriori原理来减少在数据库上进行检查的集合的数目。Apriori原理是说如果一个元

素项是不频繁的

过组合满足最小

现的频率。

，那么那些包含该元素的超集也是不频繁的。Apriori算法从单元素项集开始，通

支持度要求的项集来形成更大的集合。支持度用来度量一个集合在原始数据中出

关联分析可以用在许多不同物品上。

商店中的商品以及网站的访问页面是其中比较常见的例

子。关联分析也曾用于查看选举人及法官的投票历史。

每次增加频繁项集的大小，Apriori算法都会重新扫描整个数据集。当数据集很大时，这会显

著降低频繁项集发现的速度。下一章会介绍FPgrowth算法①，和Apriori算法相比，该算法只需要

对数据库进行两次遍历，能够显著加快发现繁项集的速度。

”’

from numpy import *

”’

Apriori算法的一般流程

(1)收集数据:使用任意方法。

(2)准备数据:任何数据类型都可以，因为我们只保存集合。

(3)分析数据:使用任意方法。

(4)训练算法:使用Apriori算法来找到频繁项集。

(5)刚试算法:不需要测试过程。

(6)使用算法:用于发现频繁项集以及物品之间的关联规则。

Apriori原理是说如果某个项集是频繁的，那么它的所有子集也是频繁的。

对于图11-2给出的例子，这意味着如果{{0,1 }是频繁的，那么{0}, {1}也一定是频繁的。这个原理

直观上并没有什么帮助，但是如果反过来看就有用了，也就是说如果一个项集是非频繁集，那么

它的所有超集也是非频繁的

11.1节提到，关联分析的目标包括两项:发现频繁项集和发现关联规则。首先需要找到频繁

项集，然后才能获得关联规则。本节将只关注于发现频繁项集。

Apriori算法是发现频繁项集的一种方法。Apriori}法的两个输人参数分别是最小支持度和数

据集。该算法首先会生成所有单个物品的项集列表。接着扫描交易记录来查看哪些项集满足最小

支持度要求，那些不满足最小支持度的集合会被去掉。然后，对剩下来的集合进行组合以生成包

含两个元素的项集。接下来，再重新扫描交易记录，去掉不满足最小支持度的项集。该过程重复

进行直到所有项集都被去掉。

生成候选集

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

对每个候选项集can:

检查一下can是否是tran的子集:

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

对每个候选项集:

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

返回所有频繁项集列表

上述程序包含三个函数。第一个函数loadDataSet()创建了一个用于测试的简单数据集，

另外两个函数分别是createCl()和scanD ( )。

不言自名，函数createCl()将构建集合C1o C1是大小为1的所有候选项集的集合。Apriori

算法首先构建集合C1，然后扫描数据集来判断这些只有一个元素的项集是否满足最小支持度的要

求。那些满足最低要求的项集构成集合L1。而L1中的元素相互组合构成C2, C2再进一步过滤变

为L2。到这里，我想读者应该明白了该算法的主要思路。

因此算法需要一个函数createCl()来构建第一个候选项集的列表C1。由于算法一开始是从输

人数据中提取候选项集列表，所以这里需要一个特殊的函数来处理，而后续的项集列表则是按一定

的格式存放的。这里使用的格式就是Python中的frozense淡型。frozense提指被“冰冻”的集合，就

是说它们是不可改变的，即用户不能修改它们。这里必须要使用frozensetf}TJ不是se璞型，因为之后

必须要将这些集合作为字典键值使用，使用frozense呵以实现这一点，而set}[1做不到。

首先创建一个空列表c1，它用来存储所有不重复的项值。接下来遍历数据集中的所有交易记

录。对每一条记录，遍历记录中的每一个项。如果某个物品项没有在c1中出现，则将其添加到

C1中。这里并不是简单地添加每个物品项，而是添加只包含该物品项的一个列表①。这样做的目

的是为每个物品项构建一个集合。因为在Apriori算法的后续处理中，需要做集合操作。Python不

能创建只有一个整数的集合，因此这里实现必须使用列表(有兴趣的读者可以试一下)。这就是

我们使用一个由单物品列表组成的大列表的原因。最后，对大列表进行排序并将其中的每个单元

素列表映射到frozenset()，最后返回frozenset的列表Do

程序清单11-1中的第二个函数是scanD ( )，它有三个参数，分别是数据集Ck、包含候选集合

的列表以及感兴趣项集的最小支持度minSupport。该函数用于从C1生成L1。另外，该函数会返

回一个包含支持度值的字典以备后用。scanD ( )函数首先创建一个空字典ssCn七，然后遍历数据

集中的所有交易记录以及C1中的所有候选集。如果C1中的集合是记录的一部分，那么增加字典

中对应的计数值。这里字典的键就是集合。当扫描完数据集中的所有项以及所有候选集时，就需

要计算支持度。不满足最小支持度要求的集合不会输出。函数也会先构建一个空列表，该列表包

含满足最小支持度要求的集合。下一个循环遍历字典中的每个元素并且计算支持度.。如果支持

度满足最小支持度要求，则将字典元素添加到retList中。可以使用语句retL乒st.

insert (0 , key)在列表的首部插人任意新的集合。当然也不一定非要在首部插人，这只是为了

让列表看起来有组织。函数最后返回最频繁项集的支持度supportData

”’

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.sort()

return map(frozenset, C1)#use frozen set so we

#can use it as a key in a dict

def scanD(D, Ck, minSupport):

ssCnt = {}

for tid in D:

for can in Ck:

if can.issubset(tid):

if not ssCnt.has_key(can): 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

”’

整个Aprior滇法的伪代码如下:

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

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

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

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

程序清单11-2包含两个函数aprioriGen()与apriori(),其中主函数是apriori()，它会

调用aprioriGen()来创建候选项集Ck,函数aprioriGen()

的输人参数为频繁项集列表Lk与项集元素个数k,输出为Ck,首先创建一个

空列表，然后计算Lk中的元素数目。接下来，’比较Lk中的每一个元素与其他元素，

这可以通过两个for循环来实现。紧接着，取列表中的两个集合进行比较。如果这两个集合的前面k-2个元

素都相等，那么就将这两个集合合成一个大小为k的集合.。这里使用集合的并操作来完成，在

Python中对应操作符|。

上面所有的操作都被封装在apriori()函数中。给该函数传递一个数据集以及一个支持度，

函数会生成候选项集的列表，这通过首先创建C1然后读人数据集将其转化为D(集合列表)来完

成。程序中使用map函数将set()映射到da七aSet列表中的每一项。接下来，使用程序清单11-1

中的scanD ( )函数来创建L1，并将L1放人列表L中。L会包含L1 } L2 , L3 …。现在有了L1，后面

会继续找L2, L3…，这可以通过 while循环来完成，它创建包含更大项集的更大列表，直到下一

个大的项集为空。如果这听起来让人有点困惑的话，那么等一下你会看到它的工作流程。首先使

用aprioriGen()来创建Ck，然后使用scanD()基于Ck来创建Lko Ck是一个候选项集列表，然

后scanD()会遍历Ck，丢掉不满足最小支持度要求的项集)a Lk列表被添加到L，同时增加k的

值，重复上述过程。最后，当Lk为空时，程序返回L并退出。

”’

def aprioriGen(Lk, k): #creates Ck

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: #if first k-2 elements are equal

retList.append(Lk[i] | Lk[j]) #set union

return retList

def apriori(dataSet, minSupport = 0.5):

C1 = createC1(dataSet)

D = 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)#scan DB to get Lk

supportData.update(supK)

L.append(Lk)

k += 1

return L, supportData

”’

关联规则生成函数

可以首先从一个频繁项集开始，接着创建一个规则列表，其中规则右部只包含一个

元素，然后对这些规则进行测试。

接下来合并所有剩余规则来创建一个新的规则列表，其中规则

右部包含两个元素。这种方法也被称作分级法。

上述程序中包含三个函数。第一个函数generateRules()是主函数，它调用其他两个函数。

其他两个函数是rulesFromConseq()和calcConf()，分别用于生成候选规则集合以及对规则

进行评估。

函数generateRules()有3个参数:频繁项集列表、包含那些频繁项集支持数据的字典、最

小可信度阑值。函数最后要生成一个包含可信度的规则列表，后面可以基于可信度对它们进行排

序。这些规则存放在bigRuleList中。如果事先没有给定最小可信度的闽值，那么默认值设为

0.7o generateRules)的另两个输入参数正好是程序清单11-2中函数apriori()的输出结果。

该函数遍历L中的每一个频繁项集并对每个频繁项集创建只包含单个元素集合的列表H1。因为无

法从单元素项集中构建关联规则，所以要从包含两个或者更多元素的项集开始规则构建过程Oo

如果从集合{{0,1,2}开始，那么H1应该是〔{0},{1},{2}]。如果频繁项集的元素数目超过2，那么会考

虑对它做进一步的合并。具体合并可以通过函数rulesFromConseq()来完成，后面会详细讨论

合并过程。如果项集中只有两个元素，那么使用函数calcConf()来计算可信度值。

我们的目标是计算规则的可信度以及找到满足最小可信度要求的规则。所有这些可以使用函

数calcConf()来完成，而程序清单11-3中的其余代码都用来准备规则。函数会返回一个满足最

小可信度要求的规则列表，为了保存这些规则，需要创建一个空列表prunedH。接下来，遍历H

中的所有项集并计算它们的可信度值。可信度计算时使用。upportData中的支持度数据。通过

导人这些支持度数据，可以节省大量计算时间。如果某条规则满足最小可信度值，那么将这些规

则输出到屏幕显示。通过检查的规则也会被返回，并被用在下一个函数rulesFromConseq()中。

同时也需要对列表brl进行填充，而brl是前面通过检查的bigRuleListo

为从最初的项集中生成更多的关联规则，可以使用rulesFromConseq()函数。该函数有2

个参数:一个是频繁项集，另一个是可以出现在规则右部的元素列表H。函数先计算H中的频繁集

大小m)。接下来查看该频繁项集是否大到可以移除大小为m的子集。如果可以的话，则将其移

除。可以使用程序清单11-2中的函数aprioriGen()来生成H中元素的无重复组合O。该结果会

存储在Hmp1中，这也是下一次迭代的H列表。Hmp1包含所有可能的规则。可以利用calcConf ( )

来测试它们的可信度以确定规则是否满足要求。如果不止一条规则满足要求，那么使用Hmp1迭

代调用函数rulesFromConseq(，来判断是否可以进一步组合这些规则

”’

def generateRules(L, supportData, minConf=0.7): #supportData is a dict coming from scanD

bigRuleList = []

for i in range(1, len(L)):#only get the sets with two or more items

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.7):

prunedH = [] #create new list to return

for conseq in H:

conf = supportData[freqSet]/supportData[freqSet-conseq] #calc confidence

if conf >= minConf:

print freqSet-conseq,’–>’,conseq,’conf:’,conf

brl.append((freqSet-conseq, conseq, conf))

prunedH.append(conseq)

return prunedH

def rulesFromConseq(freqSet, H, supportData, brl, minConf=0.7):

m = len(H[0])

if (len(freqSet) > (m + 1)): #try further merging

Hmp1 = aprioriGen(H, m+1)#create Hm+1 new candidates

Hmp1 = calcConf(freqSet, Hmp1, supportData, brl, minConf)

if (len(Hmp1) > 1): #need at least two sets to merge

rulesFromConseq(freqSet, Hmp1, supportData, brl, minConf)

def pntRules(ruleList, itemMeaning):

for ruleTup in ruleList:

for item in ruleTup[0]:

print itemMeaning[item]

print ” ——–>”

for item in ruleTup[1]:

print itemMeaning[item]

print “confidence: %f” % ruleTup[2]

print #print a blank line

”’

收集数据:构建美国国会投票记录的事务数据集

(1)收集数据:使用votesmart模块来访问投票记录。

(2)准备数据:构造一个函数来将投票转化为一串交易记录。

(3)分析数据:在Python提示符下查看准备的数据以确保其正确性。

(#)训练算法:使用本章早先的apriori()和generateRules()函数来发现投票记录中

的有趣信息。

(5)测试算法:不适用，即没有刚试过程。

(6)使用算法:这里只是出于娱乐的目的，不过也可以使用分析结果来为政治竞选活动服

务，或者预测选举官员会如何投票。

上述程序中导人了votesmart模块并通过引人sleep函数来延迟API调用。getActions工ds()

函数会返回存储在recent20bills.txt文件中议案的action工d。程序先导人API key，然后创建两个

空列表。这两个列表分别用来返回actionsId和标题。首先打开recent20bills.tx改件，对每一行内不

同元素使用tab进行分隔，之后进人try-excep七模块。由于在使用外部”I时可能会遇到错误，

并且也不想让错误占用数据获取的时间，上述try-except模块调用是一种非常可行的做法。所

以，首先尝试使用getBill()方法来获得一个billDetail对象。接下来遍历议案中的所有行为，

来寻找有投票数据的行为.。在Passage阶段与Amendment Vote(修正案投票)阶段都会有投票数

据，要找的就是它们。现在，在行政级别上也有一个Passage阶段，但那个阶段并不包含任何投票

数据，所以要确保这个阶段是发生在众议院.。如果确实如此，程序就会将actionId打印出来

并将它添加到action工dList中。同时，也会将议案的标题添加到billTitleList中。如果在

API调用时发生错误，就不会执行actionIdList的添加操作。一旦有错误就会执行except模块

并将错误信息输出。最后，程序会休眠1秒钟，以避免对Votesmart.org网站的过度频繁访问。程序

活行结束时，action工dList与billTitleLis七会被返回用于进一步的处理。

可以看到action工d显示了出来，它同时也被添加到action工dList中输出，以后我们可以使

用这些action工d了。如果程序运行错误，则尝试使用try..excep七代码来捕获错误。我自己就曾

经在获取所有actiondId时遇到一个错误。接下里可以继续来获取这些action工d的投票信息。

选举人可以投是或否的表决票，也可以弃权。需要一种方法来将这些上述信息转化为类似于

项集或者交易数据库之类的东西。前面提到过，一条交易记录数据只包含一个项的出现或不出现

信息，并不包含项出现的次数。基于上述投票数据，可以将投票是或否看成一个元素。

美国有两个主要政党:共和党与民主党。下面也会对这些信息进行编码并写到事务数据库中。

幸运的是，这些信息在投票数据中已经包括。下面给出构建事务数据库的流程:首先创建一个字

典，字典中使用政客的名字作为键值。当某政客首次出现时，将他及其所属政党(民主党或者共

和党)添加到字典中，这里使用。来代表民主党，1来代表共和党。下面介绍如何对投票进行编码。

对每条议案创建两个条目:bill+’Yea’以及bill十·Nay’。该方法允许在某个政客根本没有投

票时也能合理编码

”’

from time import sleep

from votesmart import votesmart

votesmart.apikey = ‘a7fa40adec6f4a77178799fae4441030’

#votesmart.apikey = ‘get your api key first’

def getActionIds():

actionIdList = []; billTitleList = []

fr = open(‘recent20bills.txt’)

for line in fr.readlines():

billNum = int(line.split(‘\t’)[0])

try:

billDetail = votesmart.votes.getBill(billNum) #api call

for action in billDetail.actions:

if action.level == ‘House’ and \

(action.stage == ‘Passage’ or action.stage == ‘Amendment Vote’):

actionId = int(action.actionId)

print ‘bill: %d has actionId: %d’ % (billNum, actionId)

actionIdList.append(actionId)

billTitleList.append(line.strip().split(‘\t’)[1])

except:

print “problem getting bill %d” % billNum

sleep(1) #delay to be polite

return actionIdList, billTitleList

”’

函数getTransList()会创建一个事务数据库.于是在此基础上可以使用前面的Apriori代码

来生成频繁项集与关联规则。该函数也会创建一个标题列表,所以很容易了解每个元素项的含义。

一开始使用前两个元素“Repbulican”和“Democratic” 创建一个含义列表itemMeaning。当想

知道某些元素项的具体含义时，需要做的是以元素项的编号作为索引访问itemMeaning即可。

接下来遍历所有议案，然后在议案标题后添加Nay(反对) 或者Yea(同意)并将它们放人

itemMeaning列表中,接下来创建一个空字典用于加人元素项，然后遍历函数getActionIds()

返回的每一个action工do遍历时要做的第一件事是休眠，即在for循环中一开始调用sleep ( )

函数来延迟访问，这样做可以避免过于频繁的API调用。接着将运行结果打印出来，以便知道程

序县否在正常工作。再接着通过try..except块来使用VotesmartAPI获取某个特定action工d

相关的所有投票信息。然后，遍历所有的投票信息(通常voteList会超过400个投票)。在遍历

时，使用政客的名字作为字典的键值来填充transDicto,如果之前没有遇到该政客，那么就要获

取他的政党信息。字典中的每个政客都有一个列表来存储他投票的元素项或者他的政党信息。接

下来会看到该政客是否对当前议案投了赞成(Yea )或反对(Nay)票。如果他们之前有投票，

那么不管是投赞成票还是反对票，

这些信息都将添加到列表中。如果API调用中发生了什么错误，

except模块中的程序就会被调用并将错误信息孰输出到屏幕上，之后函数仍然继续执行。最后，

程序返回事务字典transDict及元素项含义类表itemMeaningo

”’

def getTransList(actionIdList, billTitleList): #this will return a list of lists containing ints

itemMeaning = [‘Republican’, ‘Democratic’]#list of what each item stands for

for billTitle in billTitleList:#fill up itemMeaning list

itemMeaning.append(‘%s — Nay’ % billTitle)

itemMeaning.append(‘%s — Yea’ % billTitle)

transDict = {}#list of items in each transaction (politician)

voteCount = 2

for actionId in actionIdList:

sleep(3)

print ‘getting votes for actionId: %d’ % actionId

try:

voteList = votesmart.votes.getBillActionVotes(actionId)

for vote in voteList:

if not transDict.has_key(vote.candidateName):

transDict[vote.candidateName] = []

if vote.officeParties == ‘Democratic’:

transDict[vote.candidateName].append(1)

elif vote.officeParties == ‘Republican’:

transDict[vote.candidateName].append(0)

if vote.action == ‘Nay’:

transDict[vote.candidateName].append(voteCount)

elif vote.action == ‘Yea’:

transDict[vote.candidateName].append(voteCount + 1)

except:

print “problem getting actionId: %d” % actionId

voteCount += 2

return transDict, itemMeaning