使用Apriori進行關聯分析（一）

　　大型超市有海量交易數據，我們可以通過聚類算法尋找購買相似物品的人群，從而為特定人群提供更具個性化的服務。但是對于超市來講，更有價值的是如何找出商品的隱藏關聯，從而打包促銷，以增加營業收入。其中最經典的案例就是關于尿不濕和啤酒的故事。怎樣在繁雜的數據中尋找到數據之間的隱藏關系？當然可以使用窮舉法，但代價高昂，所以需要使用更加智能的方法在合理時間內找到答案。Apriori就是其中的一種關聯分析算法。

基本概念

　　關聯分析是一種在大規模數據集中尋找有趣關系的非監督學習算法。這些關系可以有兩種形式：頻繁項集或者關聯規則。頻繁項集（frequent item sets)是經常出現在一塊的物品的集合，關聯規則(association rules)暗示兩種物品之間可能存在很強的關系。

　　下圖是一個乒乓球店的交易記錄，〇表示顧客購買了商品。其中{底板,膠皮,澆水}就是一個頻繁項集；從中可以找到底板->膠皮這樣的關聯規則：

支持度

　　怎樣有效定義頻繁和關聯？其中最重要的兩個概念是支持度和置信度。

　　支持度(support)從字面上理解就是支持的程度，一個項集的支持度(support)被定義為數據集中包含該項集的記錄所占的比例。上圖中{底板}的支持度=(5/6) * 100%。

　　這個概念其實經常在現實生活中出現，翻譯成支持率似乎更好理解，典型的例子就是投票，比如英國脫歐的支持率為51.89%。

　　用數學去解釋就是，設W 中有s％的事務同時支持物品集A和B，s％稱為{A，B}的支持度，即:

　　support({A,B}) = num(A∪B) / W = P(A∩B)

　　num(A∪B)表示含有物品集{A,B}的事務集的個數，不是數學中的并集。

置信度

　　置信度(confidence)揭示了A出現時B是否一定出現，如果出現，則出現的概率是多大。如果A->B的置信度是100%，則說明A出現時B一定會出現（返回來不一定）。上圖中底板共出現5次，其中4次同時購買了膠皮，底板->膠皮的置信度是80%。

　　用公式表示是，物品A->B的置信度=物品{A,B}的支持度 / 物品{A}的支持度：

　　Confidence(A->B) = support({A,B}) / support({A}) = P(B|A)

Apriori原理

　　本節摘自《機器學習實戰》

　　假設我們在經營一家商品種類并不多的雜貨店，我們對那些經常在一起被購買的商品非常感興趣。我們只有4種商品：商品0，商品1，商品2和商品3。那么所有可能被一起購買的商品組合都有哪些？這些商品組合可能只有一種商品，比如商品0，也可能包括兩種、三種或者所有四種商品。我們并不關心某人買了兩件商品0以及四件商品2的情況，我們只關心他購買了一種或多種商品。

　　下圖顯示了物品之間所有可能的組合。為了讓該圖更容易懂，圖中使用物品的編號0來取代物品0本身。另外，圖中從上往下的第一個集合是Ф，表示空集或不包含任何物品的集合。物品集合之間的連線表明兩個或者更多集合可以組合形成一個更大的集合。

　　前面說過，我們的目標是找到經常在一起購買的物品集合。我們使用集合的支持度來度量其出現的頻率。一個集合的支持度是指有多少比例的交易記錄包含該集合。如何對一個給定的集合，比如{0，3}，來計算其支持度？我們遍歷毎條記錄并檢查該記錄包含0和3，如果記錄確實同時包含這兩項，那么就增加總計數值。在掃描完所有數據之后，使用統計得到的總數除以總的交易記錄數，就可以得到支持度。上述過程和結果只是針對單個集合{0,3}。要獲得每種可能集合的支持度就需要多次重復上述過程。我們可以數一下上圖中的集合數目，會發現即使對于僅有4種物品的集合，也需要遍歷數據15次。而隨著物品數目的增加遍歷次數會急劇增長。對于包含— 物品的數據集共有2^N-1種項集組合。事實上，出售10000或更多種物品的商店并不少見。即使只出售100種商品的商店也會有1.26×10³⁰種可能的項集組合。對于現代的計算機而言，需要很長的時間才能完成運算。

　　為了降低所需的計算時間，研究人員發現一種所謂的Apriori原理。Apriori原理可以幫我們減少可能感興趣的項集。Apriori原理是說如果某個項集是頻繁的，那么它的所有子集也是頻繁的。上圖給出的例子，這意味著如果{0,1}是頻繁的，那么{0}、{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}的支持度，因為我們知道這些集合不會滿足我們的要求。使用該原理就可以避免項集數目的指數增長，從而在合理時間內計算出頻繁項集。

Apriori算法過程

　　關聯分析的目標包括兩項：發現頻繁項集和發現關聯規則。首先需要找到頻繁項集，然后才能獲得關聯規則。

Apriori算法過程

　　發現頻繁項集的過程如上圖所示：

由數據集生成候選項集C1（1表示每個候選項僅有一個數據項）；再由C1通過支持度過濾，生成頻繁項集L1（1表示每個頻繁項僅有一個數據項）。
將L1的數據項兩兩拼接成C2。
從候選項集C2開始，通過支持度過濾生成L2。L2根據Apriori原理拼接成候選項集C3；C3通過支持度過濾生成L3……直到Lk中僅有一個或沒有數據項為止。

　　下面是一個超市的交易記錄：

　　Apriori算法發現頻繁項集的過程如下：

　　具體代碼：

 1 def loadDataSet():
 2     return [[1,2,5],[2,4],[2,3],[1,2,4],[1,3],[2,3],[1,3],[1,2,3,5],[1,2,3]]
 3 #1.構建候選1項集C1
 4 def createC1(dataSet):
 5     C1 = []
 6     for transaction in dataSet:
 7         for item in transaction:
 8             if not [item] in C1:
 9                 C1.append([item])
10 
11     C1.sort()
12     return list(map(frozenset, C1))
13 
14 #將候選集Ck轉換為頻繁項集Lk
15 #D：原始數據集
16 #Cn: 候選集項Ck
17 #minSupport:支持度的最小值
18 def scanD(D, Ck, minSupport):
19     #候選集計數
20     ssCnt = {}
21     for tid in D:
22         for can in Ck:
23             if can.issubset(tid):
24                 if can not in ssCnt.keys(): ssCnt[can] = 1
25                 else: ssCnt[can] += 1
26 
27     numItems = float(len(D))
28     Lk= []     # 候選集項Cn生成的頻繁項集Lk
29     supportData = {}    #候選集項Cn的支持度字典
30     #計算候選項集的支持度, supportData key:候選項， value:支持度
31     for key in ssCnt:
32         support = ssCnt[key] / numItems
33         if support >= minSupport:
34             Lk.append(key)
35         supportData[key] = support
36     return Lk, supportData
37 
38 #連接操作，將頻繁Lk-1項集通過拼接轉換為候選k項集
39 def aprioriGen(Lk_1, k):
40     Ck = []
41     lenLk = len(Lk_1)
42     for i in range(lenLk):
43         L1 = list(Lk_1[i])[:k - 2]
44         L1.sort()
45         for j in range(i + 1, lenLk):
46             #前k-2個項相同時，將兩個集合合并
47             L2 = list(Lk_1[j])[:k - 2]
48             L2.sort()
49             if L1 == L2:
50                 Ck.append(Lk_1[i] | Lk_1[j])
51 
52     return Ck
53 
54 def apriori(dataSet, minSupport = 0.5):
55     C1 = createC1(dataSet)
56     L1, supportData = scanD(dataSet, C1, minSupport)
57     L = [L1]
58     k = 2
59     while (len(L[k-2]) > 0):
60         Lk_1 = L[k-2]
61         Ck = aprioriGen(Lk_1, k)
62         print("ck:",Ck)
63         Lk, supK = scanD(dataSet, Ck, minSupport)
64         supportData.update(supK)
65         print("lk:", Lk)
66         L.append(Lk)
67         k += 1
68 
69     return L, supportData
70 
71 dataset = loadDataSet()
72 L, supportData = apriori(dataset, minSupport=0.2)

　　?控制臺信息：

　　代碼中的scanD方法可作一下修改：

 1 def scanD(D, Ck, minSupport):
 2     #候選集計數
 3     ssCnt = {}
 4     #數據集過濾
 5     D2 = [item for item in D if len(item) >= len(Ck[0])]
 6     for tid in D2:
 7         for can in Ck:
 8             if can.issubset(tid):
 9                 if can not in ssCnt.keys(): ssCnt[can] = 1
10                 else: ssCnt[can] += 1
11     ……
12 
13     return Lk, supportData

?　　需要注意的是，在上述代碼的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 | L2if L1_2 not in Ck:Ck.append(L1 | L2)return Ck