DataMining-Apriori

发表于 | 分类于

DataMining-Apriori

标签：DataMining 人工智能

算法概述

  Apriori算法是数据挖掘中一个比较著名的关联分析算法。在较大数据集上采进行关联分析的时候，直接使用暴力搜索显然是不可取的，采用Apriori算法则可以在一定程度上降低计算成本。

算法准备

关联规则

  关联规则是形如“A->B”的蕴含表达式，其中A和B是不相交的项集，关联规则的强度可由支持度和置信度度量。

支持度和置信度

  支持度（support）和置信度（confidence）是数据挖掘在关联分析中两个比较基础的概念，在一个项集中，支持度定义为数据集中包含该项集的记录所占的比例，置信度的定义是基于支持度之上建立的。两者用公式表述如下：
           Markdown
  支持度和置信度是用来量化关联分析是否成功的方法。

关联规则算法的一般策略

  大多数关联规则挖掘算法采用的策略是，将关联挖掘任务分为如下两个子任务：
   1.频繁项集的产生：目标是发现满足最小支持度阈值的所有项集，成为频繁项集
   2.规则的产生：目标是从上一步发现的频繁项集中提取所有高置信度的规则，称之为强规则
  此处需要说明的是，之所以不能直接将频繁项集作为关联规则，是因为如果有这样一个项集（尿布，啤酒），那么有可能有一条关联规则“啤酒->尿布”成立，即买啤酒的人也会同时购买尿布，但是反过来可能并不成立，所以关联规则需要在频繁项集中进一步进行筛选。
  量化筛选频繁项集的指标是支持度，而量化筛选关联规则的指标是置信度。其中置信度计算公式为：
     Markdown

算法思路

引入定理

  Apriori算法是对于关联规则算法一般策略的改进，更具体的说Apriori算法是一种优化的搜索频繁项集的算法。其优化方式是引入了一条定律对于搜索过程进行剪枝处理，以减少不必要的计算。引入的Apriori定理内容如下：
   定理：如果一个集合是频繁项集，则它的所有子集都是频繁项集。
   引理：如果一个集合不是频繁项集，则它的所有超集都不是频繁项集。
  引理可以由定理简单推导得到。
  算法的剪枝过程主要应用引理，即如果发现（A，B）不是频繁项集，则其超集必定不是频繁项集，可以直接减掉。

算法介绍

  参考《IntroductionToDataMining》一书，Apriori的伪代码如下：
Markdown
  其中第一步是计算得到项数为1的频繁项集，其过程如下：
Markdown
  第二步到第八步是利用L(k-1)获得Ck,以便产生Lk，具体过程的解释可以参考原书。

算法实现

频繁项集生成

  首先利用Apriori定理进行频繁项集的生成，实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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

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)#scan DB to get Lk
        supportData.update(supK)
        L.append(Lk)
        k += 1
    return L, supportData

关联规则生成

  在频繁项集的基础上进行关联规则的筛选，实现代码如下：

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
31
32
33
34
35
36
37
38
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)#create Hm+1 new candidates
        Hmp1 = calcConf(freqSet, Hmp1, supportData, brl, minConf)
        if (len(Hmp1) > 1):    
            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

def generateRules(L, supportData, minConf=0.7):  
    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

测试结果

测试结果如下：
当可信度阈值为0.7时：

1
2
3
4
5
6
7
8
9
10
11
12
13
$ python run.py 
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
[(frozenset([3]), frozenset([1]), 0.6666666666666666), (frozenset([1]), frozenset([3]), 1.0), (frozenset([5]), frozenset([2]), 1.0), (frozenset([2]), frozenset([5]), 1.0), (frozenset([3]), frozenset([2]), 0.6666666666666666), (frozenset([2]), frozenset([3]), 0.6666666666666666), (frozenset([5]), frozenset([3]), 0.6666666666666666), (frozenset([3]), frozenset([5]), 0.6666666666666666), (frozenset([5]), frozenset([2, 3]), 0.6666666666666666), (frozenset([3]), frozenset([2, 5]), 0.6666666666666666), (frozenset([2]), frozenset([3, 5]), 0.6666666666666666)]

当可信度阈值为0.7时：

1
2
3
4
5
$ python run.py 
frozenset([1]) --> frozenset([3]) conf: 1.0
frozenset([5]) --> frozenset([2]) conf: 1.0
frozenset([2]) --> frozenset([5]) conf: 1.0
[(frozenset([1]), frozenset([3]), 1.0), (frozenset([5]), frozenset([2]), 1.0), (frozenset([2]), frozenset([5]), 1.0)]

算法拓展

  Apriori的优化方法可以参考《IntroductionToDataMining》一书。