使用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算法發現頻繁項集的過程如下：

　　具體代碼：

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] = 1else: ssCnt[can] += 1numItems = float(len(D))Lk= [] # 候選集項Cn生成的頻繁項集LksupportData = {} #候選集項Cn的支持度字典#計算候選項集的支持度, supportData key:候選項， value:支持度for key in ssCnt:support = ssCnt[key] / numItemsif support >= minSupport:Lk.append(key)supportData[key] = supportreturn 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 Ckdef apriori(dataSet, minSupport = 0.5):C1 = createC1(dataSet)L1, supportData = scanD(dataSet, C1, minSupport)L = [L1]k = 2while (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 += 1return L, supportDatadataset = loadDataSet() L, supportData = apriori(dataset, minSupport=0.2)

控制臺信息：

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

def scanD(D, Ck, minSupport):#候選集計數ssCnt = {}#數據集過濾D2 = [item for item in D if len(item) >= len(Ck[0])]for tid in D2:for can in Ck:if can.issubset(tid):if can not in ssCnt.keys(): ssCnt[can] = 1else: ssCnt[can] += 1……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

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

　　書接上文（使用Apriori進行關聯分析（一）），介紹如何挖掘關聯規則。

發現關聯規則

　　我們的目標是通過頻繁項集挖掘到隱藏的關聯規則。

　　所謂關聯規則，指通過某個元素集推導出另一個元素集。比如有一個頻繁項集{底板,膠皮,膠水}，那么一個可能的關聯規則是{底板,膠皮}→{膠水}，即如果客戶購買了底板和膠皮，則該客戶有較大概率購買膠水。這個頻繁項集可以推導出6個關聯規則：

　　{底板,膠水}→{膠皮},

　　{底板,膠皮}→{膠水},

　　{膠皮,膠水}→{底板},

　　{底板}→{膠水, 膠皮},

　　{膠水}→{底板, 膠皮},

　　{膠皮}→{底板, 膠水}

　　箭頭左邊的集合稱為“前件”，右邊集合稱為“后件”，根據前件會有較大概率推導出后件，這個概率就是之前提到的置信度。需要注意的是，如果A→B成立，B→A不一定成立。

　　一個具有N個元素的頻繁項集，共有M個可能的關聯規則：

　　下圖是一個頻繁4項集的所有關聯規則網格示意圖，?

　　上圖中深色區域表示低可信度規則，如果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)。由此可以對關聯規則做剪枝處理。

　　還是以上篇的超市交易數據為例，我們發現了如下的頻繁項集：

　　對于尋找關聯規則來說，頻繁1項集L1沒有用處，因為L1中的每個集合僅有一個數據項，至少有兩個數據項才能生成A→B這樣的關聯規則。

　　當最小置信度取0.5時，L2最終能夠挖掘出9條關聯規則：

　　從頻繁3項集開始，挖掘的過程就較為復雜。

　　假設有一個頻繁4項集（這是杜撰的，文中的數據不能生成L4），其挖掘過程如下：

　　因為書中的代碼假設購買商品是有順序的，所以在生成3后件時，{P2,P4}和{P3,P4}并不能生成{P2,P23,P4}，如果想去掉假設，需要使用上篇中改進后的代碼。

　　發掘關聯規則的代碼如下：

#生成關聯規則 #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)

由此可以看到，apriori算法需要經常掃描全表，效率并不算高。

?

---

FP-growth算法發現頻繁項集（一）——構建FP樹

　　常見的挖掘頻繁項集算法有兩類，一類是Apriori算法，另一類是FP-growth。Apriori通過不斷的構造候選集、篩選候選集挖掘出頻繁項集，需要多次掃描原始數據，當原始數據較大時，磁盤I/O次數太多，效率比較低下。FPGrowth不同于Apriori的“試探”策略，算法只需掃描原始數據兩遍，通過FP-tree數據結構對原始數據進行壓縮，效率較高。

　　FP代表頻繁模式（Frequent Pattern)?，算法主要分為兩個步驟：FP-tree構建、挖掘頻繁項集。

FP樹表示法

　　FP樹通過逐個讀入事務，并把事務映射到FP樹中的一條路徑來構造。由于不同的事務可能會有若干個相同的項，因此它們的路徑可能部分重疊。路徑相互重疊越多，使用FP樹結構獲得的壓縮效果越好；如果FP樹足夠小，能夠存放在內存中，就可以直接從這個內存中的結構提取頻繁項集，而不必重復地掃描存放在硬盤上的數據。

　　一顆FP樹如下圖所示：

　　通常，FP樹的大小比未壓縮的數據小，因為數據的事務常常共享一些共同項，在最好的情況下，所有的事務都具有相同的項集，FP樹只包含一條節點路徑；當每個事務都具有唯一項集時，導致最壞情況發生，由于事務不包含任何共同項，FP樹的大小實際上與原數據的大小一樣。

　　FP樹的根節點用φ表示，其余節點包括一個數據項和該數據項在本路徑上的支持度；每條路徑都是一條訓練數據中滿足最小支持度的數據項集；FP樹還將所有相同項連接成鏈表，上圖中用藍色連線表示。

　　為了快速訪問樹中的相同項，還需要維護一個連接具有相同項的節點的指針列表（headTable），每個列表元素包括：數據項、該項的全局最小支持度、指向FP樹中該項鏈表的表頭的指針。

構建FP樹

　　現在有如下數據：

　　FP-growth算法需要對原始訓練集掃描兩遍以構建FP樹。

　　第一次掃描，過濾掉所有不滿足最小支持度的項；對于滿足最小支持度的項，按照全局最小支持度排序，在此基礎上，為了處理方便，也可以按照項的關鍵字再次排序。

第一次掃描的后的結果

　　第二次掃描，構造FP樹。

　　參與掃描的是過濾后的數據，如果某個數據項是第一次遇到，則創建該節點，并在headTable中添加一個指向該節點的指針；否則按路徑找到該項對應的節點，修改節點信息。具體過程如下所示：

事務001，{z,r}

事務002，{z,x,y,t,s}

事務003，{z}

事務004，{x,s,r}

?

事務005，{z,x,y,t,r}

事務006，{z,x,y,t,s}

　　從上面可以看出，headTable并不是隨著FPTree一起創建，而是在第一次掃描時就已經創建完畢，在創建FPTree時只需要將指針指向相應節點即可。從事務004開始，需要創建節點間的連接，使不同路徑上的相同項連接成鏈表。

　　代碼如下：

def loadSimpDat():simpDat = [['r', 'z', 'h', 'j', 'p'],['z', 'y', 'x', 'w', 'v', 'u', 't', 's'],['z'],['r', 'x', 'n', 'o', 's'],['y', 'r', 'x', 'z', 'q', 't', 'p'],['y', 'z', 'x', 'e', 'q', 's', 't', 'm']]return simpDatdef createInitSet(dataSet):retDict = {}for trans in dataSet:fset = frozenset(trans)retDict.setdefault(fset, 0)retDict[fset] += 1return retDictclass treeNode:def __init__(self, nameValue, numOccur, parentNode):self.name = nameValueself.count = numOccurself.nodeLink = Noneself.parent = parentNodeself.children = {}def inc(self, numOccur):self.count += numOccurdef disp(self, ind=1):print(' ' * ind, self.name, ' ', self.count)for child in self.children.values():child.disp(ind + 1)def createTree(dataSet, minSup=1):headerTable = {}#此一次遍歷數據集， 記錄每個數據項的支持度for trans in dataSet:for item in trans:headerTable[item] = headerTable.get(item, 0) + 1#根據最小支持度過濾lessThanMinsup = list(filter(lambda k:headerTable[k] < minSup, headerTable.keys()))for k in lessThanMinsup: del(headerTable[k])freqItemSet = set(headerTable.keys())#如果所有數據都不滿足最小支持度，返回None, Noneif len(freqItemSet) == 0:return None, Nonefor k in headerTable:headerTable[k] = [headerTable[k], None]retTree = treeNode('φ', 1, None)#第二次遍歷數據集，構建fp-treefor tranSet, count in dataSet.items():#根據最小支持度處理一條訓練樣本，key:樣本中的一個樣例，value:該樣例的的全局支持度localD = {}for item in tranSet:if item in freqItemSet:localD[item] = headerTable[item][0]if len(localD) > 0:#根據全局頻繁項對每個事務中的數據進行排序,等價于 order by p[1] desc, p[0] descorderedItems = [v[0] for v in sorted(localD.items(), key=lambda p: (p[1],p[0]), reverse=True)]updateTree(orderedItems, retTree, headerTable, count)return retTree, headerTabledef updateTree(items, inTree, headerTable, count):if items[0] in inTree.children: # check if orderedItems[0] in retTree.childreninTree.children[items[0]].inc(count) # incrament countelse: # add items[0] to inTree.childreninTree.children[items[0]] = treeNode(items[0], count, inTree)if headerTable[items[0]][1] == None: # update header tableheaderTable[items[0]][1] = inTree.children[items[0]]else:updateHeader(headerTable[items[0]][1], inTree.children[items[0]])if len(items) > 1: # call updateTree() with remaining ordered itemsupdateTree(items[1:], inTree.children[items[0]], headerTable, count)def updateHeader(nodeToTest, targetNode): # this version does not use recursionwhile (nodeToTest.nodeLink != None): # Do not use recursion to traverse a linked list!nodeToTest = nodeToTest.nodeLinknodeToTest.nodeLink = targetNodesimpDat = loadSimpDat() dictDat = createInitSet(simpDat) myFPTree,myheader = createTree(dictDat, 3) myFPTree.disp()

上面的代碼在第一次掃描后并沒有將每條訓練數據過濾后的項排序，而是將排序放在了第二次掃描時，這可以簡化代碼的復雜度。

　　控制臺信息：

?

項的順序對FP樹的影響

　　值得注意的是，對項的關鍵字排序將會影響FP樹的結構。下面兩圖是相同訓練集生成的FP樹，圖1除了按照最小支持度排序外，未對項做任何處理；圖2則將項按照關鍵字進行了降序排序。樹的結構也將影響后續發現頻繁項的結果。

圖1 未對項的關鍵字排序

圖2 對項的關鍵字降序排序

?

FP-growth算法發現頻繁項集（二）——發現頻繁項集

　　上篇介紹了如何構建FP樹，FP樹的每條路徑都滿足最小支持度，我們需要做的是在一條路徑上尋找到更多的關聯關系。

抽取條件模式基

　　首先從FP樹頭指針表中的單個頻繁元素項開始。對于每一個元素項，獲得其對應的條件模式基（conditional pattern base)，單個元素項的條件模式基也就是元素項的關鍵字。條件模式基是以所查找元素項為結尾的路徑集合。每一條路徑其實都是一條前輟路徑（perfix path）。簡而言之，一條前綴路徑是介于所査找元素項與樹根節點之間的所有內容。

　　下圖是以{s:2}或{r:1}為元素項的前綴路徑：

　　{s}的條件模式基，即前綴路徑集合共有兩個：{{z,x,y,t}, {x}}；{r}的條件模式基共三個：{{z}, {z,x,y,t}, {x,s}}。

　　尋找條件模式基的過程實際上是從FP樹的每個葉子節點回溯到根節點的過程。我們可以通過頭指針列表headTable開始，通過指針的連接快速訪問到所有根節點。下表是上圖FP樹的所有條件模式基：

創建條件FP樹

　　為了發現更多的頻繁項集，對于每一個頻繁項，都要創建一棵條件FP樹。可以使用剛才發現的條件模式基作為輸入數據，并通過相同的建樹代碼來構建這些樹。然后，遞歸地發現頻繁項、發現條件模式基，以及發現另外的條件樹。

　　以頻繁項r為例，構建關于r的條件FP樹。r的三個前綴路徑分別是{z},{z,x,y,t},{x,s}，設最小支持度minSupport=2，則y,t,s被過濾掉，剩下{z},{z,x},{x}。y,s,t雖然是條件模式基的一部分，但是并不屬于條件FP樹，即對于r來說，它們不是頻繁的。如下圖所示，y→t→r和s→r的全局支持度都為1，所以y,t,s對于r的條件樹來說是不頻繁的。

　　過濾后的r條件樹如下：

?

　　重復上面步驟，r的條件模式基是{z,x},{x}，已經沒有能夠滿足最小支持度的路徑， 所以r的條件樹僅有一個。需要注意的是，雖然{z,x},{x}中共存在兩個x，但{z,x}中，z是x的父節點，在構造條件FP樹時不能直接將父節點移除，僅能從子節點開始逐級移除。

　　代碼如下：

def ascendTree(leafNode, prefixPath):if leafNode.parent != None:prefixPath.append(leafNode.name)ascendTree(leafNode.parent, prefixPath)def findPrefixPath(basePat, headTable):condPats = {}treeNode = headTable[basePat][1]while treeNode != None:prefixPath = []ascendTree(treeNode, prefixPath)if len(prefixPath) > 1:condPats[frozenset(prefixPath[1:])] = treeNode.counttreeNode = treeNode.nodeLinkreturn condPatsdef mineTree(inTree, headerTable, minSup=1, preFix=set([]), freqItemList=[]):# order by minSup asc, value ascbigL = [v[0] for v in sorted(headerTable.items(), key=lambda p: (p[1][0],p[0]))]for basePat in bigL:newFreqSet = preFix.copy()newFreqSet.add(basePat)freqItemList.append(newFreqSet)# 通過條件模式基找到的頻繁項集condPattBases = findPrefixPath(basePat, headerTable)myCondTree, myHead = createTree(condPattBases, minSup)if myHead != None:print('condPattBases: ', basePat, condPattBases)myCondTree.disp()print('*' * 30)mineTree(myCondTree, myHead, minSup, newFreqSet, freqItemList)simpDat = loadSimpDat() dictDat = createInitSet(simpDat) myFPTree,myheader = createTree(dictDat, 3) myFPTree.disp() condPats = findPrefixPath('z', myheader) print('z', condPats) condPats = findPrefixPath('x', myheader) print('x', condPats) condPats = findPrefixPath('y', myheader) print('y', condPats) condPats = findPrefixPath('t', myheader) print('t', condPats) condPats = findPrefixPath('s', myheader) print('s', condPats) condPats = findPrefixPath('r', myheader) print('r', condPats)mineTree(myFPTree, myheader, 2)

控制臺信息：

　　本例可以發現兩個頻繁項集{z,x}和{x}。

　　取得頻繁項集后，可以根據置信度發現關聯規則，這一步較為簡單，可參考上篇的相關內容，不在贅述。

參考文獻：《機器學習實戰》

作者：我是8位的

出處：http://www.cnblogs.com/bigmonkey

總結

以上是生活随笔為你收集整理的Apriori FP-growth 详细介绍的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。