《机器学习实战》学习笔记第十一章 —— Apriori算法
主要內(nèi)容：
一.關(guān)聯(lián)分析
二.Apriori原理
三.使用Apriori算法生成頻繁項(xiàng)集
四.從頻繁項(xiàng)集中生成關(guān)聯(lián)規(guī)則
一.關(guān)聯(lián)分析
1.關(guān)聯(lián)分析是一種在大規(guī)模數(shù)據(jù)集中尋找有趣關(guān)系的任務(wù)。這些關(guān)系可以有兩種形式：頻繁項(xiàng)集和關(guān)聯(lián)規(guī)則。
2.頻繁項(xiàng)集是經(jīng)常出現(xiàn)在一起的元素的集合。
3.關(guān)聯(lián)規(guī)則暗示兩個元素集合之間可能存在很強(qiáng)的關(guān)系。形式為：A——>B，就是“如果A，則B”。
4.支持度：數(shù)據(jù)集中包含該項(xiàng)集的數(shù)據(jù)所占的比例，支持度高的項(xiàng)集就為頻繁項(xiàng)集。
5.可信度（置信度）：衡量關(guān)聯(lián)規(guī)則可信程度的標(biāo)準(zhǔn)，假設(shè)A出現(xiàn)的概率為P（A），AB出現(xiàn)的概率為P（AB），則可信度為P（B|A） = P（AB）/ P（A）。
二.Apriori原理
1.Apriori原理是說如果某個項(xiàng)集是頻繁的，那么它的所有子集也是頻繁的。p --> q ==> !q --> !p ，所以：如果一個項(xiàng)集是非頻繁項(xiàng)集，那么它的所有超集也是非頻繁項(xiàng)集。
2.Apriori原理可以幫我們?nèi)コ艉芏喾穷l繁項(xiàng)集。因?yàn)槲覀兛梢栽陧?xiàng)集規(guī)模還是很小的時候，假如能確定他是非頻繁的，那么就可以直接去除掉那些含有該項(xiàng)集的更大的項(xiàng)集了，從而減少了運(yùn)算的規(guī)模。
3.例子如下：
三.使用Apriori算法生成頻繁項(xiàng)集
1.算法步驟：
1）根據(jù)數(shù)據(jù)集，生成單位項(xiàng)集C1，然后計算項(xiàng)集C1的支持度，并從中挑選出頻繁項(xiàng)集構(gòu)成L1（頻繁項(xiàng)集的劃分邊界為一個閾值 Mini support）。
2）設(shè)已經(jīng)完成的最新一層的頻繁項(xiàng)集的項(xiàng)數(shù)為k，而這一層可稱為第k層，可知k初始化為1。判斷這一層頻繁項(xiàng)集的個數(shù)是否大于1：如果大于1，則表明至少存在兩個頻繁項(xiàng)集可以兩兩合并成一個新的項(xiàng)集Ck+1，然后計算其支持度并過濾出頻繁項(xiàng)集，生成第k+1層。
3）重復(fù)執(zhí)行第2）步，直到最新一層的頻繁項(xiàng)集的個數(shù)少于等于1。
注：兩個頻繁項(xiàng)集合并時，需要限定：兩者有k-1個元素是相同的，然后兩者合并之后，就形成了一個k+1的集合。假如兩個頻繁項(xiàng)集的相同元素少于k-1個，那他們合并后的新項(xiàng)集的項(xiàng)數(shù)必定大于k+1，對于此種情況就直接忽略掉，讓它在往后的那些層再重新被考慮。這樣就能夠保證每一層的頻繁項(xiàng)集的項(xiàng)數(shù)是相同的。
2算法流程圖：
3.Python代碼：
1 def createC1(dataSet): #生成單位項(xiàng)集
2 C1 = []
3 for transaction in dataSet: #枚舉每一條數(shù)據(jù)
4 for item in transaction: #枚舉每條數(shù)據(jù)中的每個元素
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): #計算項(xiàng)集的支持度，并過濾掉支持度低于閾值的項(xiàng)集，從而形成頻繁項(xiàng)集。Ck的k代表項(xiàng)集的項(xiàng)數(shù)
11 ssCnt = {}
12 for tid in D: #統(tǒng)計項(xiàng)集在數(shù)據(jù)中的出現(xiàn)次數(shù)
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 = [] #頻繁項(xiàng)集列表
21 supportData = {} #保存項(xiàng)集的支持度，是一個字典。注意：非頻繁項(xiàng)集也保存。
22 for key in ssCnt:
23 support = ssCnt[key] / numItems #支持度
24 if support >= minSupport:
25 retList.insert(0, key) #頻繁項(xiàng)集
26 supportData[key] = support #保存支持度
27 return retList, supportData
28
29 def aprioriGen(Lk, k): # 用于生成下一層的頻繁項(xiàng)集（即項(xiàng)數(shù)是當(dāng)前一次的項(xiàng)數(shù)+1狼，即k）
30 retList = []
31 lenLk = len(Lk)
32 for i in range(lenLk): #O(n^2)組合生成新項(xiàng)集
33 for j in range(i + 1, lenLk):
34 L1 = list(Lk[i])[:k - 2]; L2 = list(Lk[j])[:k - 2] #去除兩者的前k-2個項(xiàng)
35 L1.sort(); L2.sort()
36 if L1 == L2: # 如果前k-2個項(xiàng)相等，那么將Lk[i]和Lk[j]并在一起，就形成了k+1個項(xiàng)的項(xiàng)集
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形式數(shù)據(jù)集（即去除重復(fù)的數(shù)據(jù)）
42 C1 = createC1(dataSet) #單位項(xiàng)集
43 L1, supportData = scanD(D, C1, minSupport) #單位頻繁項(xiàng)集
44 L = [L1]
45 k = 2
46 while (len(L[k - 2]) > 1): #如果當(dāng)層的頻繁項(xiàng)集的個數(shù)大于1，那么就可以根據(jù)當(dāng)層的頻繁項(xiàng)集生成下一層的頻繁項(xiàng)集
47 Ck = aprioriGen(L[k - 2], k) #生成下一層的項(xiàng)集
48 Lk, supK = scanD(D, Ck, minSupport) # 生成下一層的頻繁項(xiàng)集，同時得到項(xiàng)集的支持度
49 supportData.update(supK) #更新支持度庫
50 L.append(Lk) #把下一層的頻繁項(xiàng)集加入到“層疊”里面
51 k += 1 #將下一層作為當(dāng)層
52 return L, supportData
四.從頻繁項(xiàng)集中生成關(guān)聯(lián)規(guī)則
1.為何要從頻繁項(xiàng)集中生成關(guān)聯(lián)規(guī)則？因?yàn)轭l繁項(xiàng)集意味著出現(xiàn)的頻率更高，從中得到的規(guī)則更能讓人信服（這里不是指可信度）。舉個反例，如果A和B只出現(xiàn)過一次，且兩者一起出現(xiàn)即AB，我們就可以得到結(jié)論A-->B的可信度為100%，但AB的出現(xiàn)可能就是一個噪音，貿(mào)貿(mào)然下定論并非合理。所以要從頻繁項(xiàng)集中生成關(guān)聯(lián)規(guī)則。
2.如何從頻繁項(xiàng)集中生成關(guān)聯(lián)規(guī)則？簡而言之就是挑選一個頻繁項(xiàng)集，如{ABCD}，首先把它作為規(guī)則的前件，然后逐漸把元素往后件移，如A-->BCD、B-->ACD、C-->ABD、D-->ABC、AB-->CD……等等。但具體又如何操作呢？難道要用數(shù)學(xué)中組合的方式？這樣計算量太大了。這里有個事實(shí)：如果某條規(guī)則并不滿足最小可信度要求，那么該規(guī)則的所有子集也不會滿足最小可信度要求。如下：
可知{0,1,2}-->{3}的可信度為P（{3}）/ P（{0,1,2}），如果{0,1,2}-->{3}是低可信度規(guī)則，那么{0,1}-->{2,3}、{2}-->{0,1,3}等等3在后件的那些規(guī)則，統(tǒng)統(tǒng)都為低可信度規(guī)則。原因就在于可信度的計算公式：對于{0,1,2}-->{3}，其可信度為P（{3}）/ P（{0,1,2}），此時如果把0從前件移到后件，那么就成了{(lán)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}是低可信度規(guī)則，那么{1,2}-->{0,3}也是低可信度規(guī)則。
簡而言之：對于在同一個頻繁項(xiàng)集內(nèi)形成的關(guān)聯(lián)規(guī)則，假如某規(guī)則為低可信度規(guī)則，那么規(guī)則后件是該低可信度規(guī)則后件的超集的規(guī)則，都是低可信度規(guī)則。因此可以直接去掉。
3.算法流程：
1）枚舉每一層的每一個頻繁項(xiàng)集，將其作為生成關(guān)聯(lián)規(guī)則的當(dāng)前項(xiàng)集freSet，同時將freSet的單個元素作為單位項(xiàng)集以作為關(guān)聯(lián)規(guī)則后件H。
2）如果關(guān)聯(lián)規(guī)則后件的項(xiàng)數(shù)小于當(dāng)前項(xiàng)集freSet的項(xiàng)數(shù)，則前件后件都不為空，此時：枚舉關(guān)聯(lián)后件H，將freSet-H作為前件，將H作為后件，然后計算其可信度，并篩選出可信度高的關(guān)聯(lián)規(guī)則，同時篩選出能生成高可信度規(guī)則的后件H（大大簡化計算量）。
3）如果篩選過后的后件H的個數(shù)大于1，則表明可以生成當(dāng)前后件項(xiàng)數(shù)+1的后件，那么就調(diào)用Apriori算法生成新一層的后件Hnext，將Hnext作為H，然后重復(fù)第2）步。
4.Python代碼：
1 def calcConf(freqSet, H, supportData, brl, minConf=0.7): #計算關(guān)聯(lián)規(guī)則的可信度，關(guān)聯(lián)規(guī)則的右端的元素個數(shù)是固定的 2 prunedH = [] # create new list to return 3 for conseq in H: #conseq作為關(guān)聯(lián)規(guī)則的右端 4 conf = supportData[freqSet] / supportData[freqSet - conseq] # 計算可信度 5 if conf >= minConf: #可信度大于等于閾值，則將關(guān)聯(lián)規(guī)則存儲起來 6 print freqSet - conseq, '-->', conseq, 'conf:', conf 7 brl.append((freqSet - conseq, conseq, conf)) #將關(guān)聯(lián)規(guī)則存儲起來 8 prunedH.append(conseq) #將能生成關(guān)聯(lián)規(guī)則的頻繁項(xiàng)集存起來 9 return prunedH 10 11 def rulesFromConseq(freqSet, H, supportData, brl, minConf=0.7): 12 m = len(H[0]) #關(guān)聯(lián)規(guī)則的右端的元素個數(shù) 13 if (len(freqSet) > m): #如果總的元素個數(shù)大于關(guān)聯(lián)規(guī)則的右端的元素個數(shù)，則繼續(xù)生成關(guān)聯(lián)規(guī)則 14 Hitem = calcConf(freqSet, H, supportData, brl, minConf) #生成關(guān)聯(lián)規(guī)則， 同時過濾出有用的頻發(fā)項(xiàng)集 15 if (len(Hitem) > 1): # 頻繁項(xiàng)集的個數(shù)超過一個，則可以生成下一層的項(xiàng)集（即關(guān)聯(lián)規(guī)則的元素個數(shù)右端加一，對應(yīng)地左端減一） 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): # 生成關(guān)聯(lián)規(guī)則 20 bigRuleList = [] #關(guān)聯(lián)規(guī)則列表 21 for i in range(1, len(L)): # 枚舉每一層（也可以說枚舉長度，從第二層開始，因?yàn)殛P(guān)聯(lián)最少要有兩個元素） 22 for freqSet in L[i]: #枚舉這一層中所有的頻繁項(xiàng)集，用于生成關(guān)聯(lián)規(guī)則 23 H1 = [frozenset([item]) for item in freqSet] #將頻繁項(xiàng)集中的元素單獨(dú)作為一個集合，然后這些集合構(gòu)成一個列表 24 rulesFromConseq(freqSet, H1, supportData, bigRuleList, minConf) #遞歸地將freqSet中的元素移到關(guān)聯(lián)規(guī)則的右端，從而生成關(guān)聯(lián)規(guī)則 25 return bigRuleList
總結(jié)
以上是生活随笔為你收集整理的《机器学习实战》学习笔记第十一章 —— Apriori算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 刘怎么读（劉怎么读）
- 下一篇： 关于理性思考