【機(jī)器學(xué)習(xí)】關(guān)聯(lián)規(guī)則代碼練習(xí)

本課程是中國大學(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

代碼修改并注釋：黃海廣，[email protected]

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

import?numpy?as?np

def?loadDataSet():
????return?[[1,?3,?4],?[2,?3,?5],?[1,?2,?3,?5],?[2,?5]]

#?獲取候選1項(xiàng)集，dataSet為事務(wù)集。返回一個list，每個元素都是set集合
def?createC1(dataSet):
????C1?=?[]???#?元素個數(shù)為1的項(xiàng)集（非頻繁項(xiàng)集，因?yàn)檫€沒有同最小支持度比較）
????for?transaction?in?dataSet:
????????for?item?in?transaction:
????????????if?not?[item]?in?C1:
????????????????C1.append([item])
????C1.sort()??#?這里排序是為了，生成新的候選集時可以直接認(rèn)為兩個n項(xiàng)候選集前面的部分相同
????#?因?yàn)槌撕蜻x1項(xiàng)集外其他的候選n項(xiàng)集都是以二維列表的形式存在，所以要將候選1項(xiàng)集的每一個元素都轉(zhuǎn)化為一個單獨(dú)的集合。
????return?list(map(frozenset,?C1))???#map(frozenset,?C1)的語義是將C1由Python列表轉(zhuǎn)換為不變集合（frozenset，Python中的數(shù)據(jù)結(jié)構(gòu)）

#?找出候選集中的頻繁項(xiàng)集
#?dataSet為全部數(shù)據(jù)集，Ck為大小為k（包含k個元素）的候選項(xiàng)集，minSupport為設(shè)定的最小支持度
def?scanD(dataSet,?Ck,?minSupport):
????ssCnt?=?{}???#?記錄每個候選項(xiàng)的個數(shù)
????for?tid?in?dataSet:
????????for?can?in?Ck:
????????????if?can.issubset(tid):
????????????????ssCnt[can]?=?ssCnt.get(can,?0)?+?1???#?計(jì)算每一個項(xiàng)集出現(xiàn)的頻率
????numItems?=?float(len(dataSet))
????retList?=?[]
????supportData?=?{}
????for?key?in?ssCnt:
????????support?=?ssCnt[key]?/?numItems
????????if?support?>=?minSupport:
????????????retList.insert(0,?key)??#將頻繁項(xiàng)集插入返回列表的首部
????????supportData[key]?=?support
????return?retList,?supportData???#retList為在Ck中找出的頻繁項(xiàng)集（支持度大于minSupport的），supportData記錄各頻繁項(xiàng)集的支持度

#?通過頻繁項(xiàng)集列表Lk和項(xiàng)集個數(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)相同時，才將兩個集合合并，合并后才能生成k+1項(xiàng)
????????????L1?=?list(Lk[i])[:k-2];?L2?=?list(Lk[j])[:k-2]???#?取出兩個集合的前k-1個元素
????????????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通過createC1()函數(shù)生成。Lk表示項(xiàng)數(shù)為k的頻繁項(xiàng)集，supK為其支持度，Lk和supK由scanD()函數(shù)通過Ck計(jì)算而來。
def?apriori(dataSet,?minSupport=0.5):
????C1?=?createC1(dataSet)??#?從事務(wù)集中獲取候選1項(xiàng)集
????D?=?list(map(set,?dataSet))??#?將事務(wù)集的每個元素轉(zhuǎn)化為集合
????L1,?supportData?=?scanD(D,?C1,?minSupport)??#?獲取頻繁1項(xiàng)集和對應(yīng)的支持度
????L?=?[L1]??#?L用來存儲所有的頻繁項(xiàng)集
????k?=?2
????while?(len(L[k-2])?>?0):?#?一直迭代到項(xiàng)集數(shù)目過大而在事務(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?+=?1
????return?L,?supportData

dataSet?=?loadDataSet()??#?獲取事務(wù)集。每個元素都是列表
#?C1?=?createC1(dataSet)??#?獲取候選1項(xiàng)集。每個元素都是集合
#?D?=?list(map(set,?dataSet))??#?轉(zhuǎn)化事務(wù)集的形式，每個元素都轉(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樹

#?FP樹類
class?treeNode:
????def?__init__(self,?nameValue,?numOccur,?parentNode):
????????self.name?=?nameValue??#節(jié)點(diǎn)元素名稱，在構(gòu)造時初始化為給定值
????????self.count?=?numOccur???#?出現(xiàn)次數(shù)，在構(gòu)造時初始化為給定值
????????self.nodeLink?=?None???#?指向下一個相似節(jié)點(diǎn)的指針，默認(rèn)為None
????????self.parent?=?parentNode???#?指向父節(jié)點(diǎn)的指針，在構(gòu)造時初始化為給定值
????????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樹結(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樹==================================================

#?對不是第一個出現(xiàn)的節(jié)點(diǎn)，更新頭指針塊。就是添加到相似元素鏈表的尾部
def?updateHeader(nodeToTest,?targetNode):
????while?(nodeToTest.nodeLink?!=?None):
????????nodeToTest?=?nodeToTest.nodeLink
????nodeToTest.nodeLink?=?targetNode

#?根據(jù)一個排序過濾后的頻繁項(xiàng)更新FP樹
def?updateTree(items,?inTree,?headerTable,?count):
????if?items[0]?in?inTree.children:
????????#?有該元素項(xiàng)時計(jì)數(shù)值+1
????????inTree.children[items[0]].inc(count)
????else:
????????#?沒有這個元素項(xiàng)時創(chuàng)建一個新節(jié)點(diǎn)
????????inTree.children[items[0]]?=?treeNode(items[0],?count,?inTree)
????????#?更新頭指針表或前一個相似元素項(xiàng)節(jié)點(diǎn)的指針指向新節(jié)點(diǎn)
????????if?headerTable[items[0]][1]?==?None:??#?如果是第一次出現(xiàn)，則在頭指針表中增加對該節(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:
????????#?對剩下的元素項(xiàng)迭代調(diào)用updateTree函數(shù)
????????updateTree(items[1::],?inTree.children[items[0]],?headerTable,?count)

#?主程序。創(chuàng)建FP樹。dataSet為事務(wù)集，為一個字典，鍵為每個事物，值為該事物出現(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)樽值湟笤诘胁荒苄薷?，所以轉(zhuǎn)化為列表
????for?k?in?keys:
????????if?headerTable[k]?????????????del(headerTable[k])
????#?空元素集，返回空
????freqItemSet?=?set(headerTable.keys())
????if?len(freqItemSet)?==?0:
????????return?None,?None
????#?增加一個數(shù)據(jù)項(xiàng)，用于存放指向相似元素項(xiàng)指針
????for?k?in?headerTable:
????????headerTable[k]?=?[headerTable[k],?None]??#?每個鍵的值，第一個為個數(shù)，第二個為下一個節(jié)點(diǎn)的位置
????retTree?=?treeNode('Null?Set',?1,?None)?#?根節(jié)點(diǎn)
????#?第二次遍歷數(shù)據(jù)集，創(chuàng)建FP樹
????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]?#?注意這個[0]，因?yàn)橹凹舆^一個數(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樹
????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)生成一個條件模式基（前綴路徑）。basePet表示輸入的頻繁項(xiàng)，treeNode為當(dāng)前FP樹中對應(yīng)的第一個節(jié)點(diǎn)
#?函數(shù)返回值即為條件模式基condPats，用一個字典表示，鍵為前綴路徑，值為計(jì)數(shù)值。
def?findPrefixPath(basePat,?treeNode):
????condPats?=?{}??#?存儲條件模式基
????while?treeNode?!=?None:
????????prefixPath?=?[]??#?用于存儲前綴路徑
????????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??#?遍歷下一個相同元素
????return?condPats

#?=================================================遞歸查找頻繁項(xiàng)集===============================================
#?根據(jù)事務(wù)集獲取FP樹和頻繁項(xiàng)。
#?遍歷頻繁項(xiàng)，生成每個頻繁項(xiàng)的條件FP樹和條件FP樹的頻繁項(xiàng)
#?這樣每個頻繁項(xiàng)與他條件FP樹的頻繁項(xiàng)都構(gòu)成了頻繁項(xiàng)集

#?inTree和headerTable是由createTree()函數(shù)生成的事務(wù)集的FP樹。
#?minSup表示最小支持度。
#?preFix請傳入一個空集合（set([])），將在函數(shù)中用于保存當(dāng)前前綴。
#?freqItemList請傳入一個空列表（[]），將用來儲存生成的頻繁項(xiàng)集。
def?mineTree(inTree,?headerTable,?minSup,?preFix,?freqItemList):
????#?對頻繁項(xiàng)按出現(xiàn)的數(shù)量進(jìn)行排序進(jìn)行排序
????sorted_headerTable?=?sorted(headerTable.items(),?key=lambda?p:?p[1][0])??#返回重新排序的列表。每個元素是一個元組，[（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)前前綴添加一個新元素
????????freqItemList.append(newFreqSet)??#?所有的頻繁項(xiàng)集列表
????????condPattBases?=?findPrefixPath(basePat,?headerTable[basePat][1])??#?獲取條件模式基。就是basePat元素的所有前綴路徑。它像一個新的事務(wù)集
????????myCondTree,?myHead?=?createTree(condPattBases,?minSup)??#?創(chuàng)建條件FP樹

????????if?myHead?!=?None:
????????????#?用于測試
????????????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)]?=?1
????return?retDict

minSup?=?3
simpDat?=?loadSimpDat()??#?加載數(shù)據(jù)集
initSet?=?createInitSet(simpDat)??#?轉(zhuǎn)化為符合格式的事務(wù)集
myFPtree,?myHeaderTab?=?createTree(initSet,?minSup)??#?形成FP樹
#?myFPtree.disp()??#?打印樹

freqItems?=?[]??#?用于存儲頻繁項(xiàng)集
mineTree(myFPtree,?myHeaderTab,?minSup,?set([]),?freqItems)??#?獲取頻繁項(xiàng)集
print(freqItems)??#?打印頻繁項(xiàng)集

conditional tree for: {'y'}
  Null Set   1
   x   3
    z   3
conditional tree for: {'y', 'z'}
  Null Set   1
   x   3
conditional tree for: {'s'}
  Null Set   1
   x   3
conditional tree for: {'t'}
  Null Set   1
   y   3
    z   2
     x   2
    x   1
     z   1
conditional tree for: {'z', 't'}
  Null Set   1
   y   3
conditional tree for: {'x', 't'}
  Null Set   1
   y   3
conditional tree for: {'x'}
  Null Set   1
   z   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