大数据/分布式系统

机器学习笔记（Chapter 11 - Apriori算法）

商店通过会员卡等忠诚度计划，可以获取顾客所购买商品的组合信息，从而更好地安排商品定价、市场促销等。从大规模数据集中寻找物品间的隐含关系被称作关联分析或者关联规则学习。Apriori算法可以解决计算代价极高的物品组合问题，从而在合理的时间范围内找到频繁项集和关联规则。

关联分析

  • 关联分析是一种在大规模数据集中寻找关系的任务，这些关系可以有两种形式：频繁项集或者关联规则。频繁项集是经常出现在一起的物品的集合，关联规则暗示两种物品之间存在很强的因果关系。经典的例子如“啤酒与尿布”。
  • 定义“频繁”和“关联”：一个项集的支持度被定义为数据集中包含该项集的记录所占的比例。可信度或置信度是针对一条例如{尿布}→{啤酒}的关联规则定义的，这条规则的可信度被定义为支持度({尿布，啤酒})/支持度({尿布})。假设这条规则的置信度是75%，那么对于所有包含“尿布”的记录，这条规则对其中的75%都适用。

Apriori原理

  • Apriori算法易于编写，但在大数据集上效率不高。适用于数值型或者标称型数据。
  • 假设现在有n件商品，不考虑购买的数量重叠，消费者购买的可能组合就有2^n-1种。这2^N-1种项集组合无法全部遍历，因此通过Apriori原理过滤到不可能“频繁”出现的项集。Apriori原理指如果某个项集是频繁的，那么它的所有子集也是频繁的。实际应用时，通常对原理取反：如果一个项集是非频繁集，那么它的所有超集也都是非频繁的。Apriori意指“来自以前”，即定义问题时通常使用先验知识或者假设，例如在贝叶斯统计中使用先验知识作为条件进行推断，这些先验知识可能来自领域知识、先前的测量结果等。
  • Apriori算法通过已经得到的支持度达标的项集来构造更复杂的项集，因此可以看作迭代的过程。初始状态每个项集仅包含一个物品，通过统计这些长度为1的项集的支持度，筛选掉不达标的项集，再用达标项集生成长度为2的项集。过程不断重复直到所有的项集筛选完成。

Apriori算法寻找频繁集

生成候选项集

  • 函数createC1()用于构建集合C1。Ck是大小为k的所有候选项集集合，注意生成的C1通过map冰冻，意味着每个值都无法改变。scanD函数用于从Ck中筛选出支持度符合要求的项集，构成集合Lk。loadDataSet初始化一个数据集。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
from numpy import *

def loadDataSet():
    return [[1,3,4], [2,3,5], [1,2,3,5], [2,5]]

def createC1(dataSet):
    C1 = []
    for transcation in dataSet:
        for item in transcation:
            if not [item] in C1:
                C1.append([item])
    C1.sort()
    return map(frozenset, C1)

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
  • 对原始数据集初始化后的C1，L1如下。
1
2
3
4
5
6
7
8
9
10
>>> import apriori
>>> dataSet=  apriori.loadDataSet()
[[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]
>>> C1 = apriori.createC1(dataSet)
[frozenset([1]), frozenset([2]), frozenset([3]), frozenset([4]), frozenset([5])]
>>> D = map(set, dataSet)
[set([1, 3, 4]), set([2, 3, 5]), set([1, 2, 3, 5]), set([2, 5])]
>>> L1, supportData0 = apriori.scanD(D, C1, 0.5)
[frozenset([1]), frozenset([3]), frozenset([2]), frozenset([5])]
{frozenset([4]): 0.25, frozenset([5]): 0.75, frozenset([2]): 0.75, frozenset([3]): 0.75, frozenset([1]): 0.5}

组织完整的Apriori算法

  • Apriori整个算法流程如下：当当前集合Lk中的筛选出的频繁项集数大于0，则生成Ck+1，直到所有可能的组合都筛选完成。函数aprioriGen取频繁项集列表Lk和k作为参数，生成Ck，具体实现是对Lk中的每个元素，比较这个元素和其他元素，如果两个元素有k-1个项相同，就可以将两个元素合并成Ck+1中的一个。apriori函数取数据集、支持度作为参数，首先用createC1创建C1，用scanD筛选出L1，之后迭代生成Lk。apriori函数返回所有的频繁项集和项集的支持度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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

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)
        supportData.update(supK)
        L.append(Lk)
        k += 1
    return L, supportData
  • 执行效果。
1
2
3
4
5
>>> reload(apriori)
>>> L, suppData = apriori.apriori(dataSet)
[[frozenset([1]), frozenset([3]), frozenset([2]), frozenset([5])], [frozenset([1, 3]), frozenset([2, 5]), frozenset([2, 3]), frozenset([3, 5])], [frozenset([2, 3, 5])], []]
>>> apriori.aprioriGen(L[0], 2)
[frozenset([1, 3]), frozenset([1, 2]), frozenset([1, 5]), frozenset([2, 3]), frozenset([3, 5]), frozenset([2, 5])]

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

  • 关联规则不一定是可逆的，{尿布}→{啤酒}不意味着{啤酒}→{牛奶}。对于一个频繁项，可以将其中包含的元素划分为两部分，左端称为前件，如{尿布}→{啤酒}中的尿布，右端称为后件。对于一个固定的频繁项，前件与后件的元素个数之和固定，但前件后件数目可以调配。为了减少产生的规则数目，可以发现，如果某条规则并不满足最小可信度要求，那么这条规则的所有子集也不满足最小可信度要求。例如，{0，1，2}→{3}的规则不满足可信度，则所有前件是{0，1，2}子集的规则都不满足可信度。
  • 构造方法如下：首先从一个频繁项集开始，创建一个规则列表，其中规则右部只包含一个元素，然后对这些规则测试，接下来合并所有剩余规则来创建一个新的规则列表，此时右部包含两个元素，以此类推，称为分级法。函数generateRules取频繁项集列表L、项集支持度supportData和最小可信阈值minConf作为参数，遍历L中的每一个频繁项集并对每个频繁项集创建只包含单个元素集合的列表H1。注意因为无法从单个元素的项集中构建关联规则，所以从包含两个或者更多元素的项集开始。如果频繁项集的元素数目大于2，则考虑对其做进一步合并，产生其他规则，通过rulesFromConseq完成，否则直接calcConf计算可信值。rulesFromConseq中的if (len(freqSet)>(m+1))的判断目的在于确定当前的频繁项是否大到可以移除长为m的子集。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def generateRules(L, supportData, minConf = 0.7):
    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.7):
    prunedH = []
    for conseq in H:
        conf = supportData[freqSet]/supportData[freqSet-conseq]
        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)):
        Hmp1 = aprioriGen(H, m+1)
        Hmp1 = calcConf(freqSet, Hmp1, supportData, brl, minConf)
        if (len(Hmp1) > 1):
            rulesFromConseq(freqSet, Hmp1, supportData, brl, minConf)
  • 执行结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
>>> reload(apriori)
>>> L, suppData = apriori.apriori(dataSet, minSupport = 0.5)
>>> rules = apriori.generateRules(L, suppData, minConf = 0.7)
frozenset([1]) --> frozenset([3]) conf: 1.0
frozenset([5]) --> frozenset([2]) conf: 1.0
frozenset([2]) --> frozenset([5]) conf: 1.0
>>> rules = apriori.generateRules(L, suppData, minConf = 0.5)
frozenset([3]) --> frozenset([1]) conf: 0.666666666667
frozenset([1]) --> frozenset([3]) conf: 1.0
frozenset([5]) --> frozenset([2]) conf: 1.0
frozenset([2]) --> frozenset([5]) conf: 1.0
frozenset([3]) --> frozenset([2]) conf: 0.666666666667
frozenset([2]) --> frozenset([3]) conf: 0.666666666667
frozenset([5]) --> frozenset([3]) conf: 0.666666666667
frozenset([3]) --> frozenset([5]) conf: 0.666666666667
frozenset([5]) --> frozenset([2, 3]) conf: 0.666666666667
frozenset([3]) --> frozenset([2, 5]) conf: 0.666666666667
frozenset([2]) --> frozenset([3, 5]) conf: 0.666666666667

发现国会投票中的模式和毒蘑菇的相似特征

国会投票

  • 智能投票工程提供了公共API来访问国会投票记录，Sunlight实验室写了一个python-votesmart用于访问该API。需要先注册一个API key。需要一个工作日左右来处理申请API请求，成功后的API授权代码会发送到注册邮箱。时差关系大概晚上注册会比较好。通过votesmart.apikey来告知votesmart库你的api授权代码，通过votesmart.votes.getBillsByStateRecent()来获取最近的100条议案，对于返回结果中的每条bill，可以查看bill.title和bill.billId。例如某条议案的ID是11820，可以通过votesmart.votes.getBill(11820)来获取详细信息。对于某个议案bill的投票行为，可以通过for action in bill.actions and action.stage=='Passage'来获得每个投票action。action.actionId可以得到这个投票行为的ID，例如某个投票action是31670，可以通过votesmart.votes.getBillActionVotes(31670)来获得详细信息。下面代码是Peter Harrington给出的，里面的api代码已经过期了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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
  • 下面的代码生成食物数据库，对每个actionId，抓取不同政客的投票。关系不大，不予讨论。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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

毒蘑菇相似特征

  • 文件mushroom.dat的每一行第一个特征用1或者2表示可食用或有毒，其余列都是某种蘑菇的特征。通过apriori算法寻找包含特征值为2的频繁项集。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
>>> mushDatSet = [line.split() for line in open('mushroom.dat').readlines()]
>>> L, suppData = apriori.apriori(mushDatSet, minSupport = 0.3)
>>> for item in L[1]:
...     if item.intersection('2'): print item
frozenset(['2', '59'])
frozenset(['39', '2'])
frozenset(['2', '67'])
frozenset(['2', '34'])
frozenset(['2', '23'])
....
>>> for item in L[3]:
...     if item.intersection('2'): print item
frozenset(['63', '59', '2', '93'])
frozenset(['39', '2', '53', '34'])
frozenset(['2', '59', '23', '85'])
frozenset(['2', '59', '90', '85'])
frozenset(['39', '2', '36', '34'])
....

Apriori算法总结

关联分析适用于发现大数据集中元素间关系的一个工具集，可以通过频繁项集给出经常在一起出现的元素项或者关联规则给出元素项之间的因果关系来量化。Apriori算法减少了在数据库上检查的集合的数目，如果一个元素项是不频繁的，那么它的超集也都是不频繁的。关联分析可以用在许多不同物品上，商店商品购买和网站访问历史都是常见的例子。每次增加频繁项集的大小，Apriori算法都要重新扫描整个数据集，当数据集很大，这会掀桌降低频繁项集发现的速度。

参考文献： 《机器学习实战 - 美Peter Harrington》

原创作品，允许转载，转载时无需告知，但请务必以超链接形式标明文章原始出处(https://forec.github.io/2016/02/22/machinelearning11/) 、作者信息（Forec）和本声明。

分享到