?

?

主要內容：

一.關聯分析

二.Apriori原理

三.使用Apriori算法生成頻繁項集

四.從頻繁項集中生成關聯規則

?

?

一.關聯分析

1.關聯分析是一種在大規模數據集中尋找有趣關系的任務。這些關系可以有兩種形式：頻繁項集和關聯規則。

2.頻繁項集是經常出現在一起的元素的集合。

3.關聯規則暗示兩個元素集合之間可能存在很強的關系。形式為：A——>B，就是“如果A，則B”。

4.支持度：數據集中包含該項集的數據所占的比例，支持度高的項集就為頻繁項集。

5.可信度（置信度）：衡量關聯規則可信程度的標準，假設A出現的概率為P（A），AB出現的概率為P（AB），則可信度為P（B|A） = P（AB）/ P（A）。

?

?

二.Apriori原理

1.Apriori原理是說如果某個項集是頻繁的，那么它的所有子集也是頻繁的。p --> q? ==>? ?!q --> !p ，所以：如果一個項集是非頻繁項集，那么它的所有超集也是非頻繁項集。

2.Apriori原理可以幫我們去除掉很多非頻繁項集。因為我們可以在項集規模還是很小的時候，假如能確定他是非頻繁的，那么就可以直接去除掉那些含有該項集的更大的項集了，從而減少了運算的規模。

3.例子如下：

?

?

三.使用Apriori算法生成頻繁項集

1.算法步驟：

1）根據數據集，生成單位項集C1，然后計算項集C1的支持度，并從中挑選出頻繁項集構成L1（頻繁項集的劃分邊界為一個閾值 Mini support）。

2）設已經完成的最新一層的頻繁項集的項數為k，而這一層可稱為第k層，可知k初始化為1。判斷這一層頻繁項集的個數是否大于1：如果大于1，則表明至少存在兩個頻繁項集可以兩兩合并成一個新的項集Ck+1，然后計算其支持度并過濾出頻繁項集，生成第k+1層。

3）重復執行第2）步，直到最新一層的頻繁項集的個數少于等于1。

注：兩個頻繁項集合并時，需要限定：兩者有k-1個元素是相同的，然后兩者合并之后，就形成了一個k+1的集合。假如兩個頻繁項集的相同元素少于k-1個，那他們合并后的新項集的項數必定大于k+1，對于此種情況就直接忽略掉，讓它在往后的那些層再重新被考慮。這樣就能夠保證每一層的頻繁項集的項數是相同的。

?

2算法流程圖：

?

3.Python代碼：

1 def createC1(dataSet): #生成單位項集 2 C1 = [] 3 for transaction in dataSet: #枚舉每一條數據 4 for item in transaction: #枚舉每條數據中的每個元素 5 if not [item] in C1: 6 C1.append([item]) #將素有元素加入列表中 7 C1.sort() #必要的排序 8 return map(frozenset, C1) # use frozen set so we can use it as a key in a dict 9 10 def scanD(D, Ck, minSupport): #計算項集的支持度，并過濾掉支持度低于閾值的項集，從而形成頻繁項集。Ck的k代表項集的項數 11 ssCnt = {} 12 for tid in D: #統計項集在數據中的出現次數 13 for can in Ck: 14 if can.issubset(tid): 15 if not ssCnt.has_key(can): 16 ssCnt[can] = 1 17 else: 18 ssCnt[can] += 1 19 numItems = float(len(D)) 20 retList = [] #頻繁項集列表 21 supportData = {} #保存項集的支持度，是一個字典。注意：非頻繁項集也保存。 22 for key in ssCnt: 23 support = ssCnt[key] / numItems #支持度 24 if support >= minSupport: 25 retList.insert(0, key) #頻繁項集 26 supportData[key] = support #保存支持度 27 return retList, supportData 28 29 def aprioriGen(Lk, k): # 用于生成下一層的頻繁項集（即項數是當前一次的項數+1狼，即k） 30 retList = [] 31 lenLk = len(Lk) 32 for i in range(lenLk): #O(n^2)組合生成新項集 33 for j in range(i + 1, lenLk): 34 L1 = list(Lk[i])[:k - 2]; L2 = list(Lk[j])[:k - 2] #去除兩者的前k-2個項 35 L1.sort(); L2.sort() 36 if L1 == L2: # 如果前k-2個項相等，那么將Lk[i]和Lk[j]并在一起，就形成了k+1個項的項集 37 retList.append(Lk[i] | Lk[j]) # set union 38 return retList 39 40 def apriori(dataSet, minSupport=0.5): #Apriori算法 41 D = map(set, dataSet) #set形式數據集（即去除重復的數據） 42 C1 = createC1(dataSet) #單位項集 43 L1, supportData = scanD(D, C1, minSupport) #單位頻繁項集 44 L = [L1] 45 k = 2 46 while (len(L[k - 2]) > 1): #如果當層的頻繁項集的個數大于1，那么就可以根據當層的頻繁項集生成下一層的頻繁項集 47 Ck = aprioriGen(L[k - 2], k) #生成下一層的項集 48 Lk, supK = scanD(D, Ck, minSupport) # 生成下一層的頻繁項集，同時得到項集的支持度 49 supportData.update(supK) #更新支持度庫 50 L.append(Lk) #把下一層的頻繁項集加入到“層疊”里面 51 k += 1 #將下一層作為當層 52 return L, supportData

?

?

四.從頻繁項集中生成關聯規則

1.為何要從頻繁項集中生成關聯規則？因為頻繁項集意味著出現的頻率更高，從中得到的規則更能讓人信服（這里不是指可信度）。舉個反例，如果A和B只出現過一次，且兩者一起出現即AB，我們就可以得到結論A-->B的可信度為100%，但AB的出現可能就是一個噪音，貿貿然下定論并非合理。所以要從頻繁項集中生成關聯規則。

2.如何從頻繁項集中生成關聯規則？簡而言之就是挑選一個頻繁項集，如{ABCD}，首先把它作為規則的前件，然后逐漸把元素往后件移，如A-->BCD、B-->ACD、C-->ABD、D-->ABC、AB-->CD……等等。但具體又如何操作呢？難道要用數學中組合的方式？這樣計算量太大了。這里有個事實：如果某條規則并不滿足最小可信度要求，那么該規則的所有子集也不會滿足最小可信度要求。如下：

可知{0,1,2}-->{3}的可信度為?P（{3}）/ P（{0,1,2}），如果{0,1,2}-->{3}是低可信度規則，那么{0,1}-->{2,3}?、{2}-->{0,1,3}等等3在后件的那些規則，統統都為低可信度規則。原因就在于可信度的計算公式：對于{0,1,2}-->{3}，其可信度為P（{3}）/ P（{0,1,2}），此時如果把0從前件移到后件，那么就成了{1,2}-->{0,3}，其可信度為P（{0,3}）/ P（{1,2}），較之于P（{3}）/ P（{0,1,2}），其分子減小了，其分母增大了，所以P（{0,3}）/ P（{1,2}）<?P（{3}）/ P（{0,1,2}）。所以：如果{0,1,2}-->{3}是低可信度規則，那么{1,2}-->{0,3}也是低可信度規則。

簡而言之：對于在同一個頻繁項集內形成的關聯規則，假如某規則為低可信度規則，那么規則后件是該低可信度規則后件的超集的規則，都是低可信度規則。因此可以直接去掉。

?

3.算法流程：

1）枚舉每一層的每一個頻繁項集，將其作為生成關聯規則的當前項集freSet，同時將freSet的單個元素作為單位項集以作為關聯規則后件H。

2）如果關聯規則后件的項數小于當前項集freSet的項數，則前件后件都不為空，此時：枚舉關聯后件H，將freSet-H作為前件，將H作為后件，然后計算其可信度，并篩選出可信度高的關聯規則，同時篩選出能生成高可信度規則的后件H（大大簡化計算量）。

3）如果篩選過后的后件H的個數大于1，則表明可以生成當前后件項數+1的后件，那么就調用Apriori算法生成新一層的后件Hnext，將Hnext作為H，然后重復第2）步。

?

4.Python代碼：

1 def calcConf(freqSet, H, supportData, brl, minConf=0.7): #計算關聯規則的可信度，關聯規則的右端的元素個數是固定的 2 prunedH = [] # create new list to return 3 for conseq in H: #conseq作為關聯規則的右端 4 conf = supportData[freqSet] / supportData[freqSet - conseq] # 計算可信度 5 if conf >= minConf: #可信度大于等于閾值，則將關聯規則存儲起來 6 print freqSet - conseq, '-->', conseq, 'conf:', conf 7 brl.append((freqSet - conseq, conseq, conf)) #將關聯規則存儲起來 8 prunedH.append(conseq) #將能生成關聯規則的頻繁項集存起來 9 return prunedH 10 11 def rulesFromConseq(freqSet, H, supportData, brl, minConf=0.7): 12 m = len(H[0]) #關聯規則的右端的元素個數 13 if (len(freqSet) > m): #如果總的元素個數大于關聯規則的右端的元素個數，則繼續生成關聯規則 14 Hitem = calcConf(freqSet, H, supportData, brl, minConf) #生成關聯規則， 同時過濾出有用的頻發項集 15 if (len(Hitem) > 1): # 頻繁項集的個數超過一個，則可以生成下一層的項集（即關聯規則的元素個數右端加一，對應地左端減一） 16 Hnext = aprioriGen(Hitem, m + 1) # create Hm+1 new candidates 17 rulesFromConseq(freqSet, Hnext, supportData, brl, minConf) 18 19 def generateRules(L, supportData, minConf=0.7): # 生成關聯規則 20 bigRuleList = [] #關聯規則列表 21 for i in range(1, len(L)): # 枚舉每一層（也可以說枚舉長度，從第二層開始，因為關聯最少要有兩個元素） 22 for freqSet in L[i]: #枚舉這一層中所有的頻繁項集，用于生成關聯規則 23 H1 = [frozenset([item]) for item in freqSet] #將頻繁項集中的元素單獨作為一個集合，然后這些集合構成一個列表 24 rulesFromConseq(freqSet, H1, supportData, bigRuleList, minConf) #遞歸地將freqSet中的元素移到關聯規則的右端，從而生成關聯規則 25 return bigRuleList

?

轉載于:https://www.cnblogs.com/DOLFAMINGO/p/9521941.html

總結

以上是生活随笔為你收集整理的《机器学习实战》学习笔记第十一章 —— Apriori算法的全部內容，希望文章能夠幫你解決所遇到的問題。

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