本部落格所用代碼來源:資料挖掘十大算法(四):Apriori(關聯分析算法)
在網上搜尋Apriori算法很多部落格裡用的代碼都是同一個,看介紹應該最初是來源《機器學習實戰》這本書
這篇部落格實質就是按運作順序對這個的代碼了解與分析,請務必結合完整代碼一塊閱讀!(完整代碼見本文第三部分,或點選來源連結)
一、擷取頻繁項集
1、擷取資料
擷取資料的步驟封裝在一個函數中,一方面看着思路清晰,另一面替換資料集也友善
dataSet = loadDataSet()
# 構造資料
def loadDataSet():
return [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]
2、調用apripri()函數,傳回頻繁項集及其對應支援度
L,suppData = apriori(dataSet)
# 封裝所有步驟的函數
# 傳回 所有滿足大于門檻值的組合 集合支援度清單
def apriori(dataSet, minSupport = 0.5):
3、将清單類型dataSet轉成集合型(set),并用清單表示後指派給D
(在代碼注釋中将D的類型了解成是字典型,個人感覺不準确,雖然集合型和字典型都是{}為标志,但這裡應該是借用map函數将清單類型轉成集合類型,最後用清單表示才對)
D = list(map(set, dataSet))
# 轉換清單記錄為字典 [{1, 3, 4}, {2, 3, 5}, {1, 2, 3, 5}, {2, 5}]
轉化前轉換後:
關于map函數的用法的簡單介紹教程
注意:Python 3.x 傳回是疊代器,是以要用list()表示
沒了解透徹也不要緊,記住組合資料類型之間的類型轉換可以采用這種方式就好了
4、将清單類型dataSet中出現的每個元素提取出來,并轉換成frozenset類型,最後用清單表示後指派給C1
個人認為,整個程式最核心也是最不好了解的就是:為什麼要轉換成frozenset()集合類型的!
C1 = createC1(dataSet) #将每個元素轉會為frozenset字典
# 将所有元素轉換為frozenset型字典,存放到清單中
def createC1(dataSet):
C1 = []
for transaction in dataSet:
for item in transaction:
if not [item] in C1:
C1.append([item])
C1.sort()
# 使用frozenset是為了後面可以将這些值作為字典的鍵
return list(map(frozenset, C1)) # frozenset一種不可變的集合,set可變集合
5、去除非頻繁的項集,并計算對應的支援度
進入函數前已有的資料:
函數運作後或許到的資料:
L1, supportData = scanD(D, C1, minSupport) # 過濾資料
# 過濾掉不符合支援度的集合
# 傳回 頻繁項集清單retList 所有元素的支援度字典
def scanD(D, Ck, minSupport):
ssCnt = {}
for tid in D:
for can in Ck:
if can.issubset(tid): # 判斷can是否是tid的《子集》 (這裡使用子集的方式來判斷兩者的關系)
if can not in ssCnt: # 統計該值在整個記錄中滿足子集的次數(以字典的形式記錄,frozenset為鍵)
ssCnt[can] = 1
else:
ssCnt[can] += 1
numItems = float(len(D))
retList = [] # 重新記錄滿足條件的資料值(即支援度大于門檻值的資料)
supportData = {} # 每個資料值的支援度
for key in ssCnt:
support = ssCnt[key] / numItems
if support >= minSupport:
retList.insert(0, key)
supportData[key] = support
return retList, supportData # 排除不符合支援度元素後的元素 每個元素支援度
6、通過組合函數aprioriGen(),組合多元素的頻繁項集。
# 生成所有可以組合的集合
# 頻繁項集清單Lk 項集元素個數k [frozenset({2, 3}), frozenset({3, 5})] -> [frozenset({2, 3, 5})]
def aprioriGen(Lk, k):
retList = []
lenLk = len(Lk)
for i in range(lenLk): # 兩層循環比較Lk中的每個元素與其它元素
for j in range(i+1, lenLk):
L1 = list(Lk[i])[:k-2] # 将集合轉為list後取值
L2 = list(Lk[j])[:k-2]
L1.sort(); L2.sort() # 這裡說明一下:該函數每次比較兩個list的前k-2個元素,如果相同則求并集得到k個元素的集合
if L1==L2:
retList.append(Lk[i] | Lk[j]) # 求并集
return retList # 傳回頻繁項集清單Ck
7、通過循環,找出所有滿足支援度的頻繁項集組合,并最終确定的頻繁項集集合和相關支援度
進入循環前的資料:
循環結束後,即函數apriori()結束後傳回的資料:
對應def apriori(dataSet, minSupport = 0.5):函數部分
L = [L1]
k = 2
while (len(L[k-2]) > 0): # 若仍有滿足支援度的集合則繼續做關聯分析
Ck = aprioriGen(L[k-2], k) # Ck候選頻繁項集
Lk, supK = scanD(D, Ck, minSupport) # Lk頻繁項集
supportData.update(supK) # 更新字典(把新出現的集合:支援度加入到supportData中)
L.append(Lk)
k += 1 # 每次新組合的元素都隻增加了一個,是以k也+1(k表示元素個數)
return L, supportData
二、關聯規則
1、函數調用部分(整個程式的主函數)
dataSet = loadDataSet() #加載資料集
L,suppData = apriori(dataSet,minSupport=0.5) #擷取頻繁項集L,對應支援度字典suppData
rules = generateRules(L,suppData,minConf=0.7)#求關聯規則,置信度設定為0.7
# rules = generateRules(L,suppData,minConf=0.5)
print(rules)
2、對集合元素等于2個和大于2個的關聯規則情況進行分别讨論
# 擷取關聯規則的封裝函數
def generateRules(L, supportData, minConf=0.7): # supportData 是一個字典
bigRuleList = []
for i in range(1, len(L)): # 從為2個元素的集合開始
for freqSet in L[i]:
# 隻包含單個元素的集合清單
H1 = [frozenset([item]) for item in freqSet] # frozenset({2, 3}) 轉換為 [frozenset({2}), frozenset({3})]
# 如果集合元素大于2個,則需要處理才能獲得規則
if (i > 1):
rulesFromConseq(freqSet, H1, supportData, bigRuleList, minConf) # 集合元素 集合拆分後的清單 。。。
else:
calcConf(freqSet, H1, supportData, bigRuleList, minConf)
return bigRuleList
元素集合元素為2個的:
直接用calcConf()函數計算出,兩兩之間的互相置信度,并判斷其是否為強關聯。
元素集合元素大于2個的:
采用rulesFromConseq()函數,将部分元素進行合并,之後再進行“一推二”,所謂“一推二”為:
bigRuleList用于記錄達到最小置信度的“強關聯”,也就是要輸出的最終結果。
3、 calcConf()函數主要用于計算集合元素之間互相的關聯置信度
這關于集合中有三個元素的情況隻考慮了一推二,沒有考慮二推一
對于二推一(多退一),這裡或許隻需要加個if-else即可。
# 對規則進行評估 獲得滿足最小可信度的關聯規則
def calcConf(freqSet, H, supportData, brl, minConf=0.7):
prunedH = [] # 建立一個新的清單去傳回
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
集合元素為2個的情況舉例:
一共有4種[{2,3},{3,5},{2,5},{1,3}],這裡舉例{2,3}
集合元素為3個的情況:
這裡可以看出,用于循環序列的變量conseq實際上是擁有的元素是占多的:conseq: frozenset({2, 3}),而集合全體freqSet: frozenset({2, 3, 5}),去減去循環序列conseq為:freqSet-conseq: frozenset({5}),反倒是隻會有一個元素。
4、rulesFromConseq()函數處理多元素集合關聯問題
# 生成候選規則集合
def rulesFromConseq(freqSet, H, supportData, brl, minConf=0.7):
m = len(H[0])
if (len(freqSet) > (m + 1)): # 嘗試進一步合并
Hmp1 = aprioriGen(H, m+1) # 将單個集合元素兩兩合并
Hmp1 = calcConf(freqSet, Hmp1, supportData, brl, minConf)
if (len(Hmp1) > 1): #need at least two sets to merge
rulesFromConseq(freqSet, Hmp1, supportData, brl, minConf)
這裡也就解釋了:為什麼置信度計算函數calcConf()會有傳回值。
這裡假設:frozenset({5}) --> frozenset({2, 3}) 為強關聯,那麼這時calcConf()函數的傳回值prunedH集合就不為空,那麼就有if (len(Hmp1) > 1)為True,進而進一步分析frozenset({2, 3}) 的關聯特性!
三、所謂的完整代碼
在這裡衷心的感謝這個代碼的原作者(雖然有點瑕疵,但确實寫的很好!)
from numpy import *
# 構造資料
def loadDataSet():
return [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]
# 将所有元素轉換為frozenset型字典,存放到清單中
def createC1(dataSet):
C1 = []
for transaction in dataSet:
for item in transaction:
if not [item] in C1:
C1.append([item])
C1.sort()
# 使用frozenset是為了後面可以将這些值作為字典的鍵
return list(map(frozenset, C1)) # frozenset一種不可變的集合,set可變集合
# 過濾掉不符合支援度的集合
# 傳回 頻繁項集清單retList 所有元素的支援度字典
def scanD(D, Ck, minSupport):
ssCnt = {}
for tid in D:
for can in Ck:
if can.issubset(tid): # 判斷can是否是tid的《子集》 (這裡使用子集的方式來判斷兩者的關系)
if can not in ssCnt: # 統計該值在整個記錄中滿足子集的次數(以字典的形式記錄,frozenset為鍵)
ssCnt[can] = 1
else:
ssCnt[can] += 1
numItems = float(len(D))
retList = [] # 重新記錄滿足條件的資料值(即支援度大于門檻值的資料)
supportData = {} # 每個資料值的支援度
for key in ssCnt:
support = ssCnt[key] / numItems
if support >= minSupport:
retList.insert(0, key)
supportData[key] = support
return retList, supportData # 排除不符合支援度元素後的元素 每個元素支援度
# 生成所有可以組合的集合
# 頻繁項集清單Lk 項集元素個數k [frozenset({2, 3}), frozenset({3, 5})] -> [frozenset({2, 3, 5})]
def aprioriGen(Lk, k):
retList = []
lenLk = len(Lk)
for i in range(lenLk): # 兩層循環比較Lk中的每個元素與其它元素
for j in range(i+1, lenLk):
L1 = list(Lk[i])[:k-2] # 将集合轉為list後取值
L2 = list(Lk[j])[:k-2]
L1.sort(); L2.sort() # 這裡說明一下:該函數每次比較兩個list的前k-2個元素,如果相同則求并集得到k個元素的集合
if L1==L2:
retList.append(Lk[i] | Lk[j]) # 求并集
return retList # 傳回頻繁項集清單Ck
# 封裝所有步驟的函數
# 傳回 所有滿足大于門檻值的組合 集合支援度清單
def apriori(dataSet, minSupport = 0.5):
D = list(map(set, dataSet)) # 轉換清單記錄為字典 [{1, 3, 4}, {2, 3, 5}, {1, 2, 3, 5}, {2, 5}]
C1 = createC1(dataSet) # 将每個元素轉會為frozenset字典 [frozenset({1}), frozenset({2}), frozenset({3}), frozenset({4}), frozenset({5})]
L1, supportData = scanD(D, C1, minSupport) # 過濾資料
L = [L1]
k = 2
while (len(L[k-2]) > 0): # 若仍有滿足支援度的集合則繼續做關聯分析
Ck = aprioriGen(L[k-2], k) # Ck候選頻繁項集
Lk, supK = scanD(D, Ck, minSupport) # Lk頻繁項集
supportData.update(supK) # 更新字典(把新出現的集合:支援度加入到supportData中)
L.append(Lk)
k += 1 # 每次新組合的元素都隻增加了一個,是以k也+1(k表示元素個數)
return L, supportData
# 擷取關聯規則的封裝函數
def generateRules(L, supportData, minConf=0.7): # supportData 是一個字典
bigRuleList = []
for i in range(1, len(L)): # 從為2個元素的集合開始
for freqSet in L[i]:
# 隻包含單個元素的集合清單
H1 = [frozenset([item]) for item in freqSet] # frozenset({2, 3}) 轉換為 [frozenset({2}), frozenset({3})]
# 如果集合元素大于2個,則需要處理才能獲得規則
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 = [] # 建立一個新的清單去傳回
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) # 将單個集合元素兩兩合并
Hmp1 = calcConf(freqSet, Hmp1, supportData, brl, minConf)
if (len(Hmp1) > 1): #need at least two sets to merge
rulesFromConseq(freqSet, Hmp1, supportData, brl, minConf)
dataSet = loadDataSet()
L,suppData = apriori(dataSet,minSupport=0.5)
rules = generateRules(L,suppData,minConf=0.7)
# rules = generateRules(L,suppData,minConf=0.5)
print("具有強關聯規則的項集為:",rules)
後記
本篇部落格很多細節是能講的更清楚的,可以繼續深究的東西實際上也有很多,但礙于時間有限,要做的事情太多,很多東西隻能是點到為止。
最後說明一下:這篇部落格本質就隻是我個人的學習筆記罷了。
突然很想推薦github上這個代碼(雖然我還沒有細看)(初學者不推薦)