本課程是中國(guó)大學(xué)慕課《機(jī)器學(xué)習(xí)》的“關(guān)聯(lián)規(guī)則”章節(jié)的課后代碼。

課程地址：

https://www.icourse163.org/course/WZU-1464096179

課程完整代碼：

https://github.com/fengdu78/WZU-machine-learning-course

代碼修改并注釋：黃海廣，haiguang2000@wzu.edu.cn

Apriori算法實(shí)現(xiàn)

import?numpy?as?npdef?loadDataSet():return?[[1,?3,?4],?[2,?3,?5],?[1,?2,?3,?5],?[2,?5]]#?獲取候選1項(xiàng)集，dataSet為事務(wù)集。返回一個(gè)list，每個(gè)元素都是set集合 def?createC1(dataSet):C1?=?[]???#?元素個(gè)數(shù)為1的項(xiàng)集（非頻繁項(xiàng)集，因?yàn)檫€沒(méi)有同最小支持度比較）for?transaction?in?dataSet:for?item?in?transaction:if?not?[item]?in?C1:C1.append([item])C1.sort()??#?這里排序是為了，生成新的候選集時(shí)可以直接認(rèn)為兩個(gè)n項(xiàng)候選集前面的部分相同#?因?yàn)槌撕蜻x1項(xiàng)集外其他的候選n項(xiàng)集都是以二維列表的形式存在，所以要將候選1項(xiàng)集的每一個(gè)元素都轉(zhuǎn)化為一個(gè)單獨(dú)的集合。return?list(map(frozenset,?C1))???#map(frozenset,?C1)的語(yǔ)義是將C1由Python列表轉(zhuǎn)換為不變集合（frozenset，Python中的數(shù)據(jù)結(jié)構(gòu)）#?找出候選集中的頻繁項(xiàng)集 #?dataSet為全部數(shù)據(jù)集，Ck為大小為k（包含k個(gè)元素）的候選項(xiàng)集，minSupport為設(shè)定的最小支持度 def?scanD(dataSet,?Ck,?minSupport):ssCnt?=?{}???#?記錄每個(gè)候選項(xiàng)的個(gè)數(shù)for?tid?in?dataSet:for?can?in?Ck:if?can.issubset(tid):ssCnt[can]?=?ssCnt.get(can,?0)?+?1???#?計(jì)算每一個(gè)項(xiàng)集出現(xiàn)的頻率numItems?=?float(len(dataSet))retList?=?[]supportData?=?{}for?key?in?ssCnt:support?=?ssCnt[key]?/?numItemsif?support?>=?minSupport:retList.insert(0,?key)??#將頻繁項(xiàng)集插入返回列表的首部supportData[key]?=?supportreturn?retList,?supportData???#retList為在Ck中找出的頻繁項(xiàng)集（支持度大于minSupport的），supportData記錄各頻繁項(xiàng)集的支持度#?通過(guò)頻繁項(xiàng)集列表Lk和項(xiàng)集個(gè)數(shù)k生成候選項(xiàng)集C(k+1)。 def?aprioriGen(Lk,?k):retList?=?[]lenLk?=?len(Lk)for?i?in?range(lenLk):for?j?in?range(i?+?1,?lenLk):#?前k-1項(xiàng)相同時(shí)，才將兩個(gè)集合合并，合并后才能生成k+1項(xiàng)L1?=?list(Lk[i])[:k-2];?L2?=?list(Lk[j])[:k-2]???#?取出兩個(gè)集合的前k-1個(gè)元素L1.sort();?L2.sort()if?L1?==?L2:retList.append(Lk[i]?|?Lk[j])return?retList#?獲取事務(wù)集中的所有的頻繁項(xiàng)集 #?Ck表示項(xiàng)數(shù)為k的候選項(xiàng)集，最初的C1通過(guò)createC1()函數(shù)生成。Lk表示項(xiàng)數(shù)為k的頻繁項(xiàng)集，supK為其支持度，Lk和supK由scanD()函數(shù)通過(guò)Ck計(jì)算而來(lái)。 def?apriori(dataSet,?minSupport=0.5):C1?=?createC1(dataSet)??#?從事務(wù)集中獲取候選1項(xiàng)集D?=?list(map(set,?dataSet))??#?將事務(wù)集的每個(gè)元素轉(zhuǎn)化為集合L1,?supportData?=?scanD(D,?C1,?minSupport)??#?獲取頻繁1項(xiàng)集和對(duì)應(yīng)的支持度L?=?[L1]??#?L用來(lái)存儲(chǔ)所有的頻繁項(xiàng)集k?=?2while?(len(L[k-2])?>?0):?#?一直迭代到項(xiàng)集數(shù)目過(guò)大而在事務(wù)集中不存在這種n項(xiàng)集Ck?=?aprioriGen(L[k-2],?k)???#?根據(jù)頻繁項(xiàng)集生成新的候選項(xiàng)集。Ck表示項(xiàng)數(shù)為k的候選項(xiàng)集Lk,?supK?=?scanD(D,?Ck,?minSupport)??#?Lk表示項(xiàng)數(shù)為k的頻繁項(xiàng)集，supK為其支持度L.append(Lk);supportData.update(supK)??#?添加新頻繁項(xiàng)集和他們的支持度k?+=?1return?L,?supportDatadataSet?=?loadDataSet()??#?獲取事務(wù)集。每個(gè)元素都是列表 #?C1?=?createC1(dataSet)??#?獲取候選1項(xiàng)集。每個(gè)元素都是集合 #?D?=?list(map(set,?dataSet))??#?轉(zhuǎn)化事務(wù)集的形式，每個(gè)元素都轉(zhuǎn)化為集合。 #?L1,?suppDat?=?scanD(D,?C1,?0.5) #?print(L1,suppDat)L,?suppData?=?apriori(dataSet,minSupport=0.7) print(L,suppData)[[frozenset({5}), frozenset({2}), frozenset({3})], [frozenset({2, 5})], []] {frozenset({1}): 0.5, frozenset({3}): 0.75, frozenset({4}): 0.25, frozenset({2}): 0.75, frozenset({5}): 0.75, frozenset({2, 5}): 0.75, frozenset({3, 5}): 0.5, frozenset({2, 3}): 0.5}

FP樹(shù)

#?FP樹(shù)類 class?treeNode:def?__init__(self,?nameValue,?numOccur,?parentNode):self.name?=?nameValue??#節(jié)點(diǎn)元素名稱，在構(gòu)造時(shí)初始化為給定值self.count?=?numOccur???#?出現(xiàn)次數(shù)，在構(gòu)造時(shí)初始化為給定值self.nodeLink?=?None???#?指向下一個(gè)相似節(jié)點(diǎn)的指針，默認(rèn)為Noneself.parent?=?parentNode???#?指向父節(jié)點(diǎn)的指針，在構(gòu)造時(shí)初始化為給定值self.children?=?{}??#?指向子節(jié)點(diǎn)的字典，以子節(jié)點(diǎn)的元素名稱為鍵，指向子節(jié)點(diǎn)的指針為值，初始化為空字典#?增加節(jié)點(diǎn)的出現(xiàn)次數(shù)值def?inc(self,?numOccur):self.count?+=?numOccur#?輸出節(jié)點(diǎn)和子節(jié)點(diǎn)的FP樹(shù)結(jié)構(gòu)def?disp(self,?ind=1):print('?'?*?ind,?self.name,?'?',?self.count)for?child?in?self.children.values():child.disp(ind?+?1)#?=======================================================構(gòu)建FP樹(shù)==================================================#?對(duì)不是第一個(gè)出現(xiàn)的節(jié)點(diǎn)，更新頭指針塊。就是添加到相似元素鏈表的尾部 def?updateHeader(nodeToTest,?targetNode):while?(nodeToTest.nodeLink?!=?None):nodeToTest?=?nodeToTest.nodeLinknodeToTest.nodeLink?=?targetNode#?根據(jù)一個(gè)排序過(guò)濾后的頻繁項(xiàng)更新FP樹(shù) def?updateTree(items,?inTree,?headerTable,?count):if?items[0]?in?inTree.children:#?有該元素項(xiàng)時(shí)計(jì)數(shù)值+1inTree.children[items[0]].inc(count)else:#?沒(méi)有這個(gè)元素項(xiàng)時(shí)創(chuàng)建一個(gè)新節(jié)點(diǎn)inTree.children[items[0]]?=?treeNode(items[0],?count,?inTree)#?更新頭指針表或前一個(gè)相似元素項(xiàng)節(jié)點(diǎn)的指針指向新節(jié)點(diǎn)if?headerTable[items[0]][1]?==?None:??#?如果是第一次出現(xiàn)，則在頭指針表中增加對(duì)該節(jié)點(diǎn)的指向headerTable[items[0]][1]?=?inTree.children[items[0]]else:updateHeader(headerTable[items[0]][1],?inTree.children[items[0]])if?len(items)?>?1:#?對(duì)剩下的元素項(xiàng)迭代調(diào)用updateTree函數(shù)updateTree(items[1::],?inTree.children[items[0]],?headerTable,?count)#?主程序。創(chuàng)建FP樹(shù)。dataSet為事務(wù)集，為一個(gè)字典，鍵為每個(gè)事物，值為該事物出現(xiàn)的次數(shù)。minSup為最低支持度 def?createTree(dataSet,?minSup=1):#?第一次遍歷數(shù)據(jù)集，創(chuàng)建頭指針表headerTable?=?{}for?trans?in?dataSet:for?item?in?trans:headerTable[item]?=?headerTable.get(item,?0)?+?dataSet[trans]#?移除不滿足最小支持度的元素項(xiàng)keys?=?list(headerTable.keys())?#?因?yàn)樽值湟笤诘胁荒苄薷?#xff0c;所以轉(zhuǎn)化為列表for?k?in?keys:if?headerTable[k]?<?minSup:del(headerTable[k])#?空元素集，返回空f(shuō)reqItemSet?=?set(headerTable.keys())if?len(freqItemSet)?==?0:return?None,?None#?增加一個(gè)數(shù)據(jù)項(xiàng)，用于存放指向相似元素項(xiàng)指針for?k?in?headerTable:headerTable[k]?=?[headerTable[k],?None]??#?每個(gè)鍵的值，第一個(gè)為個(gè)數(shù)，第二個(gè)為下一個(gè)節(jié)點(diǎn)的位置retTree?=?treeNode('Null?Set',?1,?None)?#?根節(jié)點(diǎn)#?第二次遍歷數(shù)據(jù)集，創(chuàng)建FP樹(shù)for?tranSet,?count?in?dataSet.items():localD?=?{}?#?記錄頻繁1項(xiàng)集的全局頻率，用于排序for?item?in?tranSet:if?item?in?freqItemSet:???#?只考慮頻繁項(xiàng)localD[item]?=?headerTable[item][0]?#?注意這個(gè)[0]，因?yàn)橹凹舆^(guò)一個(gè)數(shù)據(jù)項(xiàng)if?len(localD)?>?0:orderedItems?=?[v[0]?for?v?in?sorted(localD.items(),?key=lambda?p:?p[1],?reverse=True)]?#?排序updateTree(orderedItems,?retTree,?headerTable,?count)?#?更新FP樹(shù)return?retTree,?headerTable#?=================================================查找元素條件模式基===============================================#?直接修改prefixPath的值，將當(dāng)前節(jié)點(diǎn)leafNode添加到prefixPath的末尾，然后遞歸添加其父節(jié)點(diǎn)。 #?prefixPath就是一條從treeNode（包括treeNode）到根節(jié)點(diǎn)（不包括根節(jié)點(diǎn)）的路徑 def?ascendTree(leafNode,?prefixPath):if?leafNode.parent?!=?None:prefixPath.append(leafNode.name)ascendTree(leafNode.parent,?prefixPath)#?為給定元素項(xiàng)生成一個(gè)條件模式基（前綴路徑）。basePet表示輸入的頻繁項(xiàng)，treeNode為當(dāng)前FP樹(shù)中對(duì)應(yīng)的第一個(gè)節(jié)點(diǎn) #?函數(shù)返回值即為條件模式基condPats，用一個(gè)字典表示，鍵為前綴路徑，值為計(jì)數(shù)值。 def?findPrefixPath(basePat,?treeNode):condPats?=?{}??#?存儲(chǔ)條件模式基while?treeNode?!=?None:prefixPath?=?[]??#?用于存儲(chǔ)前綴路徑ascendTree(treeNode,?prefixPath)??#?生成前綴路徑if?len(prefixPath)?>?1:condPats[frozenset(prefixPath[1:])]?=?treeNode.count??#?出現(xiàn)的數(shù)量就是當(dāng)前葉子節(jié)點(diǎn)的數(shù)量treeNode?=?treeNode.nodeLink??#?遍歷下一個(gè)相同元素return?condPats#?=================================================遞歸查找頻繁項(xiàng)集=============================================== #?根據(jù)事務(wù)集獲取FP樹(shù)和頻繁項(xiàng)。 #?遍歷頻繁項(xiàng)，生成每個(gè)頻繁項(xiàng)的條件FP樹(shù)和條件FP樹(shù)的頻繁項(xiàng) #?這樣每個(gè)頻繁項(xiàng)與他條件FP樹(shù)的頻繁項(xiàng)都構(gòu)成了頻繁項(xiàng)集#?inTree和headerTable是由createTree()函數(shù)生成的事務(wù)集的FP樹(shù)。 #?minSup表示最小支持度。 #?preFix請(qǐng)傳入一個(gè)空集合（set([])），將在函數(shù)中用于保存當(dāng)前前綴。 #?freqItemList請(qǐng)傳入一個(gè)空列表（[]），將用來(lái)儲(chǔ)存生成的頻繁項(xiàng)集。 def?mineTree(inTree,?headerTable,?minSup,?preFix,?freqItemList):#?對(duì)頻繁項(xiàng)按出現(xiàn)的數(shù)量進(jìn)行排序進(jìn)行排序sorted_headerTable?=?sorted(headerTable.items(),?key=lambda?p:?p[1][0])??#返回重新排序的列表。每個(gè)元素是一個(gè)元組，[（key,[num,treeNode],()）bigL?=?[v[0]?for?v?in?sorted_headerTable]??#?獲取頻繁項(xiàng)for?basePat?in?bigL:newFreqSet?=?preFix.copy()??#?新的頻繁項(xiàng)集newFreqSet.add(basePat)?????#?當(dāng)前前綴添加一個(gè)新元素freqItemList.append(newFreqSet)??#?所有的頻繁項(xiàng)集列表condPattBases?=?findPrefixPath(basePat,?headerTable[basePat][1])??#?獲取條件模式基。就是basePat元素的所有前綴路徑。它像一個(gè)新的事務(wù)集myCondTree,?myHead?=?createTree(condPattBases,?minSup)??#?創(chuàng)建條件FP樹(shù)if?myHead?!=?None:#?用于測(cè)試print('conditional?tree?for:',?newFreqSet)myCondTree.disp()mineTree(myCondTree,?myHead,?minSup,?newFreqSet,?freqItemList)??#?遞歸直到不再有元素#?生成數(shù)據(jù)集 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?simpDat#?將數(shù)據(jù)集轉(zhuǎn)化為目標(biāo)格式 def?createInitSet(dataSet):retDict?=?{}for?trans?in?dataSet:retDict[frozenset(trans)]?=?1return?retDictminSup?=?3 simpDat?=?loadSimpDat()??#?加載數(shù)據(jù)集 initSet?=?createInitSet(simpDat)??#?轉(zhuǎn)化為符合格式的事務(wù)集 myFPtree,?myHeaderTab?=?createTree(initSet,?minSup)??#?形成FP樹(shù) #?myFPtree.disp()??#?打印樹(shù)freqItems?=?[]??#?用于存儲(chǔ)頻繁項(xiàng)集 mineTree(myFPtree,?myHeaderTab,?minSup,?set([]),?freqItems)??#?獲取頻繁項(xiàng)集 print(freqItems)??#?打印頻繁項(xiàng)集conditional tree for: {'y'}Null Set 1x 3z 3 conditional tree for: {'y', 'z'}Null Set 1x 3 conditional tree for: {'s'}Null Set 1x 3 conditional tree for: {'t'}Null Set 1y 3z 2x 2x 1z 1 conditional tree for: {'z', 't'}Null Set 1y 3 conditional tree for: {'x', 't'}Null Set 1y 3 conditional tree for: {'x'}Null Set 1z 3 [{'r'}, {'y'}, {'y', 'x'}, {'y', 'z'}, {'y', 'x', 'z'}, {'s'}, {'x', 's'}, {'t'}, {'y', 't'}, {'z', 't'}, {'y', 'z', 't'}, {'x', 't'}, {'y', 'x', 't'}, {'x'}, {'x', 'z'}, {'z'}]

參考

• https://www.cnblogs.com/lsqin/p/9342926.html

往期精彩回顧適合初學(xué)者入門人工智能的路線及資料下載機(jī)器學(xué)習(xí)及深度學(xué)習(xí)筆記等資料打印機(jī)器學(xué)習(xí)在線手冊(cè)深度學(xué)習(xí)筆記專輯《統(tǒng)計(jì)學(xué)習(xí)方法》的代碼復(fù)現(xiàn)專輯 AI基礎(chǔ)下載黃海廣老師《機(jī)器學(xué)習(xí)課程》視頻課黃海廣老師《機(jī)器學(xué)習(xí)課程》711頁(yè)完整版課件

本站qq群955171419，加入微信群請(qǐng)掃碼：

總結(jié)

以上是生活随笔為你收集整理的【机器学习】关联规则代码练习的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。