关联规则Apriori算法_关联规则算法

参考《【机器学习实战-python3】使用Apriori算法进行关联 分析》,《 使用Apriori进行关联分析（一）》,《使用Apriori进行关联分析（二）》,《关于apriori算法中置信度、支持度怎么理解的问题》

关联规则的目的在于分析出经常出现在一起的物品的集合之间的关系。Apriori算法本质由两部分组成，分别是

1. 频繁项集(frequent item sets)。包括计算：频繁项集的支持度（support）
2. 关联规则(association rules)。包括计算：关联规则的置信度(confidence)

接下来分别对这几个名词进行讲解，同时串通整个Apriori算法。

1. 频繁项集(frequent item sets)

假设下表为一个超市的交易记录，其中交易ID可以看作每个前来购物的顾客，商品列表就是每个顾客购买的商品。

表1

单是肉眼去观察的话，似乎顾客经常购买P1, P2这样的组合。这种的购物中出现的经常的组合，就是我们要找的频繁项集了。项集可以由一个商品组成，也可以由多个商品组成。比如{P1}是一个项集，{P1, P2}也是一个项集。

现实生活中的数据肯定比这更加庞大，因此需要使用算法来帮助我们筛选出来哪些是频繁项集。

1.1 频繁项集的支持度(support)和阈值

一个项集的支持度被定义为数据集中包含该项集的记录所占的比例，比如在上表中，9个顾客中有4个购买了P1商品和P2商品，项集{P1, P2}的支持度就是$4/9=0.44$，支持项就是4项.

通常来说，我们会手动设置支持度的阈值。比如设置阈值为50%，这样支持度小于该阈值的时候，就认为该项集并不频繁，也就没有挖掘关联规则的意义，因此不会进行后续的计算。

1.2 频繁项集的特点

频繁项集拥有如下特点：**如果某个项集是频繁的，那么它的所有子集也是频繁的。**比如项集{P1, P2}是频繁的，那么项集{P1}和{P2}也是频繁的。该原理倒过来推并不成立，也就是说当我们 只发现{P1}和{P2}是频繁的的时候，是无法推出项集{P1, P2}是频繁的，因为有可能他们的频繁是依靠和别的商品一起购买组合而成的。该原理可以用下图表示

图1

已知阴影项集{2，3}是非频繁的。利用这个知识，我们就知道项集{0,2,3} ，{1,2,3}以及{0,1,2,3}也是非频繁的。该特点的最大用处是帮助我们减少计算，一旦计算出了{2,3}的支持度，知道它是非频繁的之后，就不需要再计算{0,2,3}、{1,2,3}和{0,1,2,3}的支持度，因为我们知道这些集合不会满足我们的要求。使用该原理就可以避免项集数目的指数增长，从而在合理时间内计算出频繁项集。

1.3 频繁项集支持度计算方法

频繁项集的计算方法并不复杂，主要就是三步的不断循环。

1. 计算当前频繁项的所有并集，得到新的频繁项候选集
2. 对得到的所有频繁项候选集进行支持项/支持度的计算
3. 使用阈值过滤掉不符合要求的频繁项，最终剩下的成为新的频繁项

图2（这里和下面的代码有一些出入：代码中loadDataSet有9个数据，对应图2计算支持度时分母应该除以9，而不是除以8。）

具体代码如下

# 数据集中有九个顾客
def loadDataSet():
    return [[1,2,5],[2,4],[2,3],[1,2,4],[1,3],[2,3],[1,3],[1,2,3,5],[1,2,3]]
#1.构建候选1项集C1
def createC1(dataSet):
    C1 = []
    for transaction in dataSet:
        for item in transaction:
            if not [item] in C1:
                C1.append([item])

    C1.sort()
    return list(map(frozenset, C1))

#将候选集Ck转换为频繁项集Lk
#D：原始数据集
#Cn: 候选集项Ck
#minSupport:支持度的最小值
def scanD(D, Ck, minSupport):
    #候选集计数
    ssCnt = {}
    for tid in D:
        for can in Ck:
            if can.issubset(tid):
                if can not in ssCnt.keys(): ssCnt[can] = 1
                else: ssCnt[can] += 1

    numItems = float(len(D))
    Lk= []     # 候选集项Cn生成的频繁项集Lk
    supportData = {}    #候选集项Cn的支持度字典
    #计算候选项集的支持度, supportData key:候选项， value:支持度
    for key in ssCnt:
        support = ssCnt[key] / numItems
        if support >= minSupport:
            Lk.append(key)
        supportData[key] = support
    return Lk, supportData

#连接操作，将频繁Lk-1项集通过拼接转换为候选k项集
def aprioriGen(Lk_1, k):
    Ck = []
    lenLk = len(Lk_1)
    for i in range(lenLk):
        L1 = list(Lk_1[i])[:k - 2]
        L1.sort()
        for j in range(i + 1, lenLk):
            #前k-2个项相同时，将两个集合合并
            L2 = list(Lk_1[j])[:k - 2]
            L2.sort()
            if L1 == L2:
                Ck.append(Lk_1[i] | Lk_1[j])

    return Ck

def apriori(dataSet, minSupport = 0.5):
    C1 = createC1(dataSet)
    L1, supportData = scanD(dataSet, C1, minSupport)
    L = [L1]
    k = 2
    while (len(L[k-2]) > 0):
        Lk_1 = L[k-2]
        Ck = aprioriGen(Lk_1, k)
        print("ck:",Ck)
        Lk, supK = scanD(dataSet, Ck, minSupport)
        supportData.update(supK)
        print("lk:", Lk)
        L.append(Lk)
        k += 1

    return L, supportData

dataset = loadDataSet()
L, supportData = apriori(dataset, minSupport=0.2)
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
'
运行
运行

最终输出如下，其中ck就是频繁项候选集，lk就是经过阈值筛选后得到的新的频繁项候选集。该结果与上图一致。

ck: [frozenset({1, 2}), frozenset({1, 5}), frozenset({1, 4}), frozenset({1, 3}), frozenset({2, 5}), frozenset({2, 4}), frozenset({2, 3}), frozenset({4, 5}), frozenset({3, 5}), frozenset({3, 4})]
lk: [frozenset({1, 2}), frozenset({1, 5}), frozenset({2, 5}), frozenset({2, 4}), frozenset({2, 3}), frozenset({1, 3})]
ck: [frozenset({1, 2, 5}), frozenset({1, 2, 3}), frozenset({1, 3, 5}), frozenset({2, 4, 5}), frozenset({2, 3, 5}), frozenset({2, 3, 4})]
lk: [frozenset({1, 2, 5}), frozenset({1, 2, 3})]
ck: [frozenset({1, 2, 3, 5})]
lk: []
1
2
3
4
5
6

需要注意的是，在上述代码的aprioriGen方法中，假定购买商品是有顺序的，可以通过频繁2项集{P1,P2},{P1,P3}推导出频繁项{P1,P2,P3}，但是不能通过频繁2项集{P3,P4},{P1,P3}推导出频繁项{P1,P3,P4}。如果去掉假设，则需要修改aprioriGen的代码：

#将频繁Lk-1项集转换为候选k项集
def aprioriGen(Lk_1, k):
    Ck = []
    lenLk = len(Lk_1)
    for i in range(lenLk):
        L1 = Lk_1[i]
        for j in range(i + 1, lenLk):
            L2 = Lk_1[j]
            if len(L1 & L2) == k - 2:
                L1_2 = L1 | L2
                if L1_2 not in Ck:
                    Ck.append(L1 | L2)
    return Ck
1
2
3
4
5
6
7
8
9
10
11
12
13
'
运行
运行

2. 关联规则挖掘(association rules)

2.1 关联规则的置信度(confidence)

我们的目的是根据频繁项集挖掘出关联规则。关联规则的意思就是通过某个项集可以推导出另一个项集。比如一个频繁项集{P1, P2, P3}，就可以推导出六个可能的关联规则。其中置信度最高的就是最有可能的关联规则。

• {P1} → {P2, P3}
• {P2} → {P1, P3}
• {P3} → {P1, P2}
• {P1, P2} → {P3}
• {P2, P3} → {P1}
• {P1, P3} → {P2}

箭头左边的集合称为“前件”，右边集合称为“后件”，根据前件会有较大概率推导出后件，这个概率就是之前提到的置信度(confidence)。需要注意的是，如果A→B成立，B→A不一定成立。

一个具有N个元素的频繁项集，共有M个可能的关联规则：
$$M=\sum _{N-1}^{i=1}{C}_N^i$$
图3是一个频繁4项集的所有关联规则网格示意图
$$M=C_4^1+C_4^2+C_4^3=14$$

图3中红色区域表示低可信度规则，如果012→3是一条低可信度规则，则所有其它3为后件的规则都是低可信度。这需要从可信度的概念去理解

• Confidence(012→3) = P(3|0,1,2)
• Confidence(01→23) = P(2,3|0,1)
• P(3|0,1,2) >= P(2,3|0,1)

由此可以对关联规则做剪枝处理。

图3

2.2 关联规则置信度的计算过程

置信度的计算公式为
$$置信度=\frac{频繁项集的出现数量}{某可能规则的出现数量}$$
还是以上篇的超市交易数据为例，我们发现了如下的频繁项集：

图4

对于寻找关联规则来说，频繁1项集L1没有用处，因为L1中的每个集合仅有一个数据项，至少有两个数据项才能生成A→B这样的关联规则。

当最小置信度取0.5时，L2最终能够挖掘出9条关联规则：

图5

以P2->P1为例，在本文的表1中，P2出现了7次，频繁项集{P1, P2}的出现次数为4次，因此P2->P1的支持度就是4/7。同理，P1出现了6次，那么P1->P2的支持度就是4/6.

从频繁3项集开始，挖掘的过程就较为复杂，要计算如{P1, P2}这样的复合频繁项集后件，并分别计算置信度。

图6

假设有一个频繁4项集（这是杜撰的，文中的数据不能生成L4），其挖掘过程如下：

图7

发掘关联规则的代码如下

#生成关联规则
#L: 频繁项集列表
#supportData: 包含频繁项集支持数据的字典
#minConf 最小置信度
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 = []
    #用每个conseq作为后件
    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)
       # print(1,H, Hmp1)
        Hmp1 = calcConf(freqSet, Hmp1, supportData, brl, minConf)
        if (len(Hmp1) > 0):
            rulesFromConseq(freqSet, Hmp1, supportData, brl, minConf)

generateRules(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
39
40
41
42
43
44
45
46

得到的结果如下所示

frozenset({5}) --> frozenset({1}) conf: 1.0
frozenset({5}) --> frozenset({2}) conf: 1.0
frozenset({4}) --> frozenset({2}) conf: 1.0
frozenset({5}) --> frozenset({1, 2}) conf: 1.0
[(frozenset({5}), frozenset({1}), 1.0),
 (frozenset({5}), frozenset({2}), 1.0),
 (frozenset({4}), frozenset({2}), 1.0),
 (frozenset({5}), frozenset({1, 2}), 1.0)]
1
2
3
4
5
6
7
8

3. 为什么需要置信度和支持度同时确定关联规则

以超市购物为例。

TID是transaction ID 即交易编号，也就是有五个人在超市买了这样的东西（Iteams），现在我们统计一下，大家买的东西之间有没有什么规律，比如买面包的是不是很可能同时买牛奶这样的规律。

在这里，支持度的计算过程为
$$support=\frac{\sigma (Milk,Diaper,Beer)}{|T|}=\frac{2}{5}=0.4$$

支持度越大，说明同时买这三个东西的人多，说明这三者之间有关系.

但是当交易量特别大的时候，假如有一万个人买东西，只有10个人同时买了Milk、Diaper、Beer，但其他9990个人没有买这三者中的任何一个，那么此时S=10/10000=0.001。如果仅从这个0.001看，这三者之间没有任何关系，但是事实却不是这样，因为只有十个人这样买，并且同时买了这三种东西，所以他们之间应该是由关系的，而不是偶然。

引入置信度的概念后，比如我们想看{Milk, Diaper}→{Beer}的置信度，则计算过程为
$$confidence=\frac{\sigma (Milk,Diaper,Beer)}{\sigma (Milk,Diaper)}=\frac{2}{3}=0.67$$
和S支持度比较只有分母变了，变成了买了Milk和Diaper两种东西的人，这个式子是说买了Milk和Diaper两种东西的人里面又有多少人买了Beer这个东西！

在上面支持度为0.001的情况下，此时置信度=10/10=100%！足以说明两者之间的关联性。

但是只有置信度也是不可行的，比如10000个订单中，只有一个人同时购买了Milk，Diaper和Bear，那么此时的置信度为1/1=100%！可是支持度只有0.0001，非常的小。

所以正确的有关联的判定是：置信度和支持度都应该比较大才可以认为这些东西之间有关联！