目錄
#第一關(guān)：頭表建設(shè)
任務(wù)描述
本關(guān)任務(wù)：認(rèn)識(shí) FPgrowth 算法及FP樹的頭表構(gòu)建。
相關(guān)知識(shí)
為了完成本關(guān)任務(wù)，你需要掌握：FP 樹表示法及頭表構(gòu)建。
本節(jié)我們開始介紹一種稱作 FP增長的算法。該算法采用完全不同的方法來發(fā)現(xiàn)頻繁項(xiàng)集。該算法不同于 Apriori 算法的“產(chǎn)生測(cè)試”范型，而是使用一種稱作 FP 樹的緊湊數(shù)據(jù)結(jié)構(gòu)組織數(shù)據(jù)，并直接從該結(jié)構(gòu)中提取頻繁項(xiàng)集。下面詳細(xì)說明該方法。
FP樹表示法及頭表構(gòu)建
FP 樹是一種輸入數(shù)據(jù)的壓縮表示，它通過逐個(gè)讀入事務(wù)，并把每個(gè)事務(wù)映射到 FP 樹中的一條路徑來構(gòu)造。由于不同的事務(wù)可能會(huì)有若千個(gè)相同的項(xiàng)，因此它們的路徑可能部分重疊。路徑相互重疊越多，使用 FP 樹結(jié)構(gòu)獲得的壓縮的效果越好。如果 FP 樹足夠小，能夠存放在內(nèi)存中，就可以直接從這個(gè)內(nèi)存中的結(jié)構(gòu)提取頻繁項(xiàng)集，而不必重復(fù)地掃描存放在硬盤上的數(shù)據(jù)。
圖一 構(gòu)建的FP樹
上圖顯示了一個(gè)數(shù)據(jù)集，它包含 10 個(gè)事務(wù)和 5 個(gè)項(xiàng)。圖中還繪制了讀入前 3 個(gè)事務(wù)之后FP樹的結(jié)構(gòu)。樹中每一個(gè)結(jié)點(diǎn)都包括一個(gè)項(xiàng)的標(biāo)記和一個(gè)計(jì)數(shù)，計(jì)數(shù)顯示映射到給定路徑的事務(wù)個(gè)數(shù)。初始，F(xiàn)P 樹僅包含一個(gè)根結(jié)點(diǎn)，用符號(hào)null標(biāo)記。隨后，用如下方法擴(kuò)充 FP 樹: (1) 掃描一次數(shù)據(jù)集，確定每個(gè)項(xiàng)的支持度計(jì)數(shù)。丟棄非頻繁項(xiàng)，而將頻繁項(xiàng)按照支持度的遞減排序。對(duì)于上圖中的數(shù)據(jù)集，a是最頻繁的項(xiàng)，接下來依次是b,c, d,e。
該過程是頭表的構(gòu)建過程，主要的代碼實(shí)現(xiàn)如下：
# 統(tǒng)計(jì)各項(xiàng)出現(xiàn)次數(shù)# 第一次遍歷，得到頻繁一項(xiàng)集headerTable = {} #頭表構(gòu)建for k in item_count: # 剔除不滿足最小支持度的項(xiàng)if item_count[k] >= min_support:headerTable[k] = item_count[k]freqItemSet = set(headerTable.keys()) # 滿足最小支持度的頻繁項(xiàng)集
編程要求
根據(jù)提示，在右側(cè)編輯器Begin和End之間補(bǔ)充代碼，完成 頭表構(gòu)建的過程。
測(cè)試說明
點(diǎn)擊評(píng)測(cè)，平臺(tái)會(huì)對(duì)你編寫的代碼進(jìn)行測(cè)試。 如程序無誤，運(yùn)行程序后提示程序執(zhí)行成功，結(jié)果見文檔輸出。，輸出會(huì)展示在文檔中； 如程序有誤，無法通過評(píng)測(cè)，且提示程序執(zhí)行出錯(cuò)。文章來源：http://www.zghlxwxcb.cn/news/detail-853409.html
import os
import time
from tqdm import tqdm
class Node():
def __init__(self, node_name, count, parentNode):
self.name = node_name
self.count = count
self.nodeLink = None # 根據(jù)nideLink可以找到整棵樹中所有nodename一樣的節(jié)點(diǎn)
self.parent = parentNode # 父親節(jié)點(diǎn)
self.children = {} # 子節(jié)點(diǎn){節(jié)點(diǎn)名字:節(jié)點(diǎn)地址}
class Fp_tree():
def update_header(self, node, targetNode): # 更新headertable中的node節(jié)點(diǎn)形成的鏈表
while node.nodeLink != None:
node = node.nodeLink
node.nodeLink = targetNode
def update_fptree(self, items, node, headerTable): # 用于更新fptree
if items[0] in node.children:
# 判斷items的第一個(gè)結(jié)點(diǎn)是否已作為子結(jié)點(diǎn)
node.children[items[0]].count += 1
else:
# 創(chuàng)建新的分支
node.children[items[0]] = Node(items[0], 1, node)
# 更新相應(yīng)頻繁項(xiàng)集的鏈表，往后添加
if headerTable[items[0]][1] == None:
headerTable[items[0]][1] = node.children[items[0]]
else:
self.update_header(headerTable[items[0]][1], node.children[items[0]])
# 遞歸
if len(items) > 1:
self.update_fptree(items[1:], node.children[items[0]], headerTable)
def create_fptree(self, data_set, min_support, flag=False): # FPTree構(gòu)建, 建樹主函數(shù)
'''
根據(jù)data_set創(chuàng)建fp樹
header_table結(jié)構(gòu)為
{"nodename":[num,node],..} 根據(jù)node.nodelink可以找到整個(gè)樹中的所有nodename
'''
###########Begin##########
###########End###########
if flag:
ite = tqdm(data_set)
else:
ite = data_set
for t in ite: # 第二次遍歷，建樹
localD = {}
for item in t:
if item in freqItemSet: # 過濾，只取該樣本中滿足最小支持度的頻繁項(xiàng)
localD[item] = headerTable[item][0] # element : count
if len(localD) > 0:
# 根據(jù)全局頻數(shù)從大到小對(duì)單樣本排序
order_item = [v[0] for v in sorted(localD.items(), key=lambda x: x[1], reverse=True)]
# 用過濾且排序后的樣本更新樹
self.update_fptree(order_item, tree_header, headerTable)
return tree_header, headerTable第一關(guān)通關(guān)代碼
###########Begin##########
# 頭表構(gòu)建
item_count = {} # 統(tǒng)計(jì)各項(xiàng)出現(xiàn)次數(shù)
for t in data_set: # 第一次遍歷，得到頻繁一項(xiàng)集
for item in t:
if item not in item_count:
item_count[item] = 1
else:
item_count[item] += 1
headerTable = {} #頭表構(gòu)建
for k in item_count: # 剔除不滿足最小支持度的項(xiàng)
if item_count[k] >= min_support:
headerTable[k] = [item_count[k], None] # element: [count, node]
freqItemSet = set(headerTable.keys()) # 滿足最小支持度的頻繁項(xiàng)集
tree_header = Node('head node', 1, None)
###########End###########第二關(guān)：FPtree構(gòu)建
任務(wù)描述
本關(guān)任務(wù)：完成FPtree的構(gòu)建。
相關(guān)知識(shí)
為了完成本關(guān)任務(wù)，你需要掌握：1. FP 樹表示法，2.FPtree的構(gòu)建。
圖一 構(gòu)建的FP樹 上節(jié)我們對(duì)FPtree做了基本認(rèn)識(shí)并構(gòu)建的頭表，下面我們來看它整體的構(gòu)造過程。初始，F(xiàn)P 樹僅包含一個(gè)根結(jié)點(diǎn)，用符號(hào)null標(biāo)記。隨后，用如下方法擴(kuò)充 FP 樹: (1) 掃描一次數(shù)據(jù)集，確定每個(gè)項(xiàng)的支持度計(jì)數(shù)。丟棄非頻繁項(xiàng)，而將頻繁項(xiàng)按照支持度的遞減排序。對(duì)于上圖中的數(shù)據(jù)集，a是最頻繁的項(xiàng)，接下來依次是b,c, d,e。
(2) 算法第二次掃描數(shù)據(jù)集，構(gòu)建 FP 樹。讀入第一個(gè)事務(wù){a, b}之后，創(chuàng)建標(biāo)記為 a 和 b 的結(jié)點(diǎn)。然后形成null→a→b路徑，對(duì)該事務(wù)編碼。該路徑上的所有結(jié)點(diǎn)的頻度計(jì)數(shù)為 1 。
(3) 讀入第二個(gè)事務(wù){b, c, d}之后，為項(xiàng) b, c 和 d 創(chuàng)建新的結(jié)點(diǎn)集。然后，連接結(jié)點(diǎn)null→b→c→d,形成一條代表該事務(wù)的路徑。該路徑上的每個(gè)結(jié)點(diǎn)的頻度計(jì)數(shù)也等于1。盡管前兩個(gè)事務(wù)具有一個(gè)共同項(xiàng) b ，但是它們的路徑不相交，因?yàn)檫@兩個(gè)事務(wù)沒有共同的前綴。
(4) 第三個(gè)事務(wù){a, c, d, e}與第一個(gè)事務(wù)共享一個(gè)共同前綴項(xiàng) a ，所以第三個(gè)事務(wù)的路徑null→a→c→d→e與第-個(gè)事務(wù)的路徑null→a→b部分重疊。因?yàn)樗鼈兊穆窂街丿B，所以結(jié)點(diǎn) a 的頻度計(jì)數(shù)增加為 2 ，而新創(chuàng)建的結(jié)點(diǎn) c , d 和 e 的頻度計(jì)數(shù)等于 1 。
(5) 繼續(xù)該過程,直到每個(gè)事務(wù)都映射到 FP 樹的一條路徑。讀入所有的事務(wù)后即可形成的 FP 樹。
整個(gè)FP樹構(gòu)建的代碼實(shí)現(xiàn)如下：
for t in ite: # 第二次遍歷，建樹
localD = {}
for item in t:
if item in freqItemSet: # 過濾，只取該樣本中滿足最小支持度的頻繁項(xiàng)
localD[item] = headerTable[item][0] # element : count
if len(localD) > 0:
# 根據(jù)全局頻數(shù)從大到小對(duì)單樣本排序
order_item = [v[0] for v in sorted(localD.items(), key=lambda x: x[1], reverse=True)]
# 用過濾且排序后的樣本更新樹
self.update_fptree(order_item, tree_header, headerTable)上圖構(gòu)建的 FP 樹還包含一個(gè)連接具有相同項(xiàng)的結(jié)點(diǎn)的指針列表。這些指針用虛線表示，有助于方便快速地訪問樹中的項(xiàng)。之后將使用FP樹和它的相應(yīng)指針產(chǎn)生頻繁項(xiàng)集。
編程要求
根據(jù)提示，在右側(cè)編輯器Begin和End之間補(bǔ)充代碼，完成 FPtree的構(gòu)建過程。
測(cè)試說明
點(diǎn)擊評(píng)測(cè)，平臺(tái)會(huì)對(duì)你編寫的代碼進(jìn)行測(cè)試。 如程序無誤，運(yùn)行程序后提示程序執(zhí)行成功，結(jié)果見文檔輸出。，輸出會(huì)展示在文檔中； 如程序有誤，無法通過評(píng)測(cè)，且提示程序執(zhí)行出錯(cuò)。
源代碼
import os
import time
from tqdm import tqdm
class Node():
def __init__(self, node_name, count, parentNode):
self.name = node_name
self.count = count
self.nodeLink = None # 根據(jù)nideLink可以找到整棵樹中所有nodename一樣的節(jié)點(diǎn)
self.parent = parentNode # 父親節(jié)點(diǎn)
self.children = {} # 子節(jié)點(diǎn){節(jié)點(diǎn)名字:節(jié)點(diǎn)地址}
class Fp_tree():
def update_header(self, node, targetNode): # 更新headertable中的node節(jié)點(diǎn)形成的鏈表
while node.nodeLink != None:
node = node.nodeLink
node.nodeLink = targetNode
def update_fptree(self, items, node, headerTable): # 用于更新fptree
if items[0] in node.children:
# 判斷items的第一個(gè)結(jié)點(diǎn)是否已作為子結(jié)點(diǎn)
node.children[items[0]].count += 1
else:
# 創(chuàng)建新的分支
node.children[items[0]] = Node(items[0], 1, node)
# 更新相應(yīng)頻繁項(xiàng)集的鏈表，往后添加
if headerTable[items[0]][1] == None:
headerTable[items[0]][1] = node.children[items[0]]
else:
self.update_header(headerTable[items[0]][1], node.children[items[0]])
# 遞歸
if len(items) > 1:
self.update_fptree(items[1:], node.children[items[0]], headerTable)
def create_fptree(self, data_set, min_support, flag=False): # FPTree構(gòu)建, 建樹主函數(shù)
'''
根據(jù)data_set創(chuàng)建fp樹
header_table結(jié)構(gòu)為
{"nodename":[num,node],..} 根據(jù)node.nodelink可以找到整個(gè)樹中的所有nodename
'''
###########Begin##########
###########End##########
return tree_header, headerTable通關(guān)代碼
###########Begin##########
# 頭表構(gòu)建
item_count = {} # 統(tǒng)計(jì)各項(xiàng)出現(xiàn)次數(shù)
for t in data_set: # 第一次遍歷，得到頻繁一項(xiàng)集
for item in t:
if item not in item_count:
item_count[item] = 1
else:
item_count[item] += 1
headerTable = {} #頭表構(gòu)建
for k in item_count: # 剔除不滿足最小支持度的項(xiàng)
if item_count[k] >= min_support:
headerTable[k] = [item_count[k], None] # element: [count, node]
freqItemSet = set(headerTable.keys()) # 滿足最小支持度的頻繁項(xiàng)集
tree_header = Node('head node', 1, None)
# 建樹
if flag:
ite = tqdm(data_set)
else:
ite = data_set
for t in ite: # 第二次遍歷，建樹
localD = {}
for item in t:
if item in freqItemSet: # 過濾，只取該樣本中滿足最小支持度的頻繁項(xiàng)
localD[item] = headerTable[item][0] # element : count
if len(localD) > 0:
# 根據(jù)全局頻數(shù)從大到小對(duì)單樣本排序
order_item = [v[0] for v in sorted(localD.items(), key=lambda x: x[1], reverse=True)]
# 用過濾且排序后的樣本更新樹
self.update_fptree(order_item, tree_header, headerTable)
###########End##########第三關(guān)：{e)的條件FPtree構(gòu)建
任務(wù)描述
本關(guān)任務(wù)：認(rèn)識(shí) FP 增長算法的頻繁項(xiàng)集產(chǎn)生。
相關(guān)知識(shí)
為了完成本關(guān)任務(wù)，你需要掌握：FP 增長算法的頻繁項(xiàng)集產(chǎn)生及條件FPtree構(gòu)建。
FP 增長算法的頻繁項(xiàng)集產(chǎn)生
FP 增長(FP-growth)是一種以自底向上方式探索樹，由FP 樹產(chǎn)生頻繁項(xiàng)集的算法。給定圖一產(chǎn)生的樹，算法首先查找以 e 結(jié)尾的頻繁項(xiàng)集，接下來依次是d,c,b,最后是a。由于每一個(gè)事務(wù)都映射到FP樹中的一條路徑，因而通過僅考察包含特定結(jié)點(diǎn)(例如e)的路徑，就可以發(fā)現(xiàn)以e結(jié)尾的頻繁項(xiàng)集.使用與結(jié)點(diǎn)e相關(guān)聯(lián)的指針,可以快速訪問這些路徑。下圖a顯示了所提取的路徑。之后我們便可以處理這些路徑，以得到頻繁項(xiàng)集。
圖一 包含各結(jié)點(diǎn)的路徑
發(fā)現(xiàn)以 e 結(jié)尾的頻繁項(xiàng)集之后，算法通過處理與結(jié)點(diǎn)d相關(guān)聯(lián)的路徑，進(jìn)一步尋找以 d 結(jié)尾的頻繁項(xiàng)集。上圖 b 顯示了對(duì)應(yīng)的路徑。繼續(xù)該過程，直到處理了所有與結(jié)點(diǎn) c, b 和 a 相關(guān)聯(lián)的路徑為止。上圖c、d、e分別顯示了這些項(xiàng)的路徑，而它們對(duì)應(yīng)的頻繁項(xiàng)集匯總?cè)缦拢?/p>
| 后綴 | 頻繁項(xiàng)集 |
|---|---|
| e | {e},{d.e},{a,d,e},{c,e},{a,e} |
| d | n5n3t3z,{c,d},{b,c,d},{a,c,d},{b,d},{a,b,d},{a,d} |
| c | {c],{b,c},{a,b,c},{a,c} |
| b | ,{a,b} |
| a | {a} |
FP 增長采用分治策略將一個(gè)問題分解為較小的子問題，從而發(fā)現(xiàn)以某個(gè)特定后綴結(jié)尾的所有頻繁項(xiàng)集。例如，假設(shè)對(duì)發(fā)現(xiàn)所有以e結(jié)尾的頻繁項(xiàng)集感興趣。為了實(shí)現(xiàn)這個(gè)目的，必須首先檢查項(xiàng)集{e}本身是否頻繁。如果它是頻繁的，則考慮發(fā)現(xiàn)以de結(jié)尾的頻繁項(xiàng)集子問題，接下來是ce和ae。依次,每一個(gè)子問題可以進(jìn)一步劃分為更小的子問題。通過合并這些子問題得到的結(jié)果，就可以找到所有以 e 結(jié)尾的頻繁項(xiàng)集。這種分治策略是FP增長算法采用的關(guān)鍵策略。
為了更具體地說明如何解決這些子問題，考慮發(fā)現(xiàn)所有以e結(jié)尾的頻繁項(xiàng)集的任務(wù):
(1) 第一步收集包含e結(jié)點(diǎn)的所有路徑。這些初始的路徑稱為前綴路徑(prefix path)，如圖二 a 所示。
圖二 使用FP增長算法發(fā)現(xiàn)以e結(jié)尾的頻繁項(xiàng)集
(2) 由圖二a中所顯示的前綴路徑，通過把與結(jié)點(diǎn)e相關(guān)聯(lián)的支持度計(jì)數(shù)相加得到 e 的支持度計(jì)數(shù)。假定最小支持度為 2 ,因?yàn)?code>{e}的支持度是 3 ，所以它是頻繁項(xiàng)集。
(3) 由于{e}是頻繁的，因此算法必須解決發(fā)現(xiàn)以de、ce、 be 和ae結(jié)尾的頻繁項(xiàng)集的子問題。在解決這些子問題之前，必須先將前綴路徑轉(zhuǎn)化為條件 FP 樹(conditional FP-tree)。除了用于發(fā)現(xiàn)以某特定后綴結(jié)尾的頻繁項(xiàng)集之外,條件 FP 樹的結(jié)構(gòu)與FP樹類似。 條件FP樹通過以下步驟得到： (a) 首先，必須更新前綴路徑上的支持度計(jì)數(shù)，因?yàn)槟承┯?jì)數(shù)包括那些不含項(xiàng)e的事務(wù)。例如，圖二 a 中的最右邊路徑null→b:2→c:2→e:1,包括并不含項(xiàng) e 的事務(wù){b,c}.因此，必須將該前綴路徑上的計(jì)數(shù)調(diào)整為 1 ,以反映包含{b, c, e}的事務(wù)的實(shí)際個(gè)數(shù)。 (b) 刪除 e 的結(jié)點(diǎn)，修剪前綴路徑。刪除這些結(jié)點(diǎn)是因?yàn)?，沿這些前綴路徑的支持度計(jì)數(shù)已經(jīng)更新，以反映包含e的那些事務(wù)，并且發(fā)現(xiàn)以de, ce, be和ae結(jié)尾的頻繁項(xiàng)集的子問題不再需要結(jié)點(diǎn)e的信息。 (c) 更新沿前綴路徑上的支持度計(jì)數(shù)之后，某些項(xiàng)可能不再是頻繁的。例如，結(jié)點(diǎn)b只出現(xiàn)了 1 次，它的支持度計(jì)數(shù)等于 1 ,這就意味著只有一個(gè)事務(wù)同時(shí)包含b和e。因?yàn)樗幸?code>be結(jié)尾的項(xiàng)集一定都是非頻繁的，所以在其后的分析中可以安全地忽略 b。 創(chuàng)建{e}條件模式樹過程的實(shí)現(xiàn)代碼為：
cond_pat_base = fp.find_cond_pattern_base('e', headerTable)cond_pat_dataset = [] # 將條件模式基字典轉(zhuǎn)化為數(shù)組for item in cond_pat_base:item_temp = list(item)item_temp.sort()for i in range(cond_pat_base[item]):cond_pat_dataset.append(item_temp)# 創(chuàng)建條件模式樹cond_tree, cur_headtable = fp.create_fptree(cond_pat_dataset, min_support)
編程要求
根據(jù)提示，在右側(cè)編輯器Begin和End之間補(bǔ)充代碼，完成 FP條件樹的構(gòu)建過程。
測(cè)試說明
點(diǎn)擊評(píng)測(cè)，平臺(tái)會(huì)對(duì)你編寫的代碼進(jìn)行測(cè)試。 如程序無誤，運(yùn)行程序后提示程序執(zhí)行成功，結(jié)果見文檔輸出。，輸出會(huì)展示在文檔中； 如程序有誤，無法通過評(píng)測(cè)，且提示程序執(zhí)行出錯(cuò)。
源代碼
import os
import time
from tqdm import tqdm
class Node:
def __init__(self, node_name, count, parentNode):
self.name = node_name
self.count = count
self.nodeLink = None # 根據(jù)nideLink可以找到整棵樹中所有nodename一樣的節(jié)點(diǎn)
self.parent = parentNode # 父親節(jié)點(diǎn)
self.children = {} # 子節(jié)點(diǎn){節(jié)點(diǎn)名字:節(jié)點(diǎn)地址}
class Base():
def update_header(self, node, targetNode): # 更新headertable中的node節(jié)點(diǎn)形成的鏈表
while node.nodeLink != None:
node = node.nodeLink
node.nodeLink = targetNode
def update_fptree(self, items, node, headerTable): # 用于更新fptree
if items[0] in node.children:
# 判斷items的第一個(gè)結(jié)點(diǎn)是否已作為子結(jié)點(diǎn)
node.children[items[0]].count += 1
else:
# 創(chuàng)建新的分支
node.children[items[0]] = Node(items[0], 1, node)
# 更新相應(yīng)頻繁項(xiàng)集的鏈表，往后添加
if headerTable[items[0]][1] == None:
headerTable[items[0]][1] = node.children[items[0]]
else:
self.update_header(headerTable[items[0]][1], node.children[items[0]])
# 遞歸
if len(items) > 1:
self.update_fptree(items[1:], node.children[items[0]], headerTable)
def create_fptree(self, data_set, min_support, flag=False): # FPTree構(gòu)建, 建樹主函數(shù)
'''
根據(jù)data_set創(chuàng)建fp樹
header_table結(jié)構(gòu)為
{"nodename":[num,node],..} 根據(jù)node.nodelink可以找到整個(gè)樹中的所有nodename
'''
item_count = {} # 統(tǒng)計(jì)各項(xiàng)出現(xiàn)次數(shù)
for t in data_set: # 第一次遍歷，得到頻繁一項(xiàng)集
for item in t:
if item not in item_count:
item_count[item] = 1
else:
item_count[item] += 1
headerTable = {} #頭表構(gòu)建
for k in item_count: # 剔除不滿足最小支持度的項(xiàng)
if item_count[k] >= min_support:
headerTable[k] = item_count[k]
freqItemSet = set(headerTable.keys()) # 滿足最小支持度的頻繁項(xiàng)集
if len(freqItemSet) == 0:
return None, None
for k in headerTable:
headerTable[k] = [headerTable[k], None] # element: [count, node]
tree_header = Node('head node', 1, None)
if flag:
ite = tqdm(data_set)
else:
ite = data_set
for t in ite: # 第二次遍歷，建樹
localD = {}
for item in t:
if item in freqItemSet: # 過濾，只取該樣本中滿足最小支持度的頻繁項(xiàng)
localD[item] = headerTable[item][0] # element : count
if len(localD) > 0:
# 根據(jù)全局頻數(shù)從大到小對(duì)單樣本排序
order_item = [v[0] for v in sorted(localD.items(), key=lambda x: x[1], reverse=True)]
# 用過濾且排序后的樣本更新樹
self.update_fptree(order_item, tree_header, headerTable)
return tree_header, headerTable
def find_path(self, node, nodepath):
'''
遞歸將node的父節(jié)點(diǎn)添加到路徑
'''
if node.parent != None:
nodepath.append(node.parent.name)
self.find_path(node.parent, nodepath)
def find_cond_pattern_base(self, node_name, headerTable):
'''
根據(jù)節(jié)點(diǎn)名字，找出所有條件模式基
'''
treeNode = headerTable[node_name][1]
cond_pat_base = {} # 保存所有條件模式基
while treeNode != None:
nodepath = []
self.find_path(treeNode, nodepath)
if len(nodepath) > 1:
cond_pat_base[frozenset(nodepath[:-1])] = treeNode.count
treeNode = treeNode.nodeLink
return cond_pat_base
def create_cond_fptree(self, headerTable, min_support, temp, freq_items, support_data):
'''
條件樹建立的過程
'''
##########Begin##########
############End##########
return cur_headtable
通關(guān)代碼
##########Begin##########
freqs = [v[0] for v in sorted(headerTable.items(), key=lambda p: p[1][0])] # 根據(jù)頻繁項(xiàng)的總頻次排序
for freq in freqs: # 對(duì)每個(gè)頻繁項(xiàng)
freq_set = temp.copy()
freq_set.add(freq)
freq_items.add(frozenset(freq_set))
if frozenset(freq_set) not in support_data: # 檢查該頻繁項(xiàng)是否在support_data中
support_data[frozenset(freq_set)] = headerTable[freq][0]
else:
support_data[frozenset(freq_set)] += headerTable[freq][0]
cond_pat_base = self.find_cond_pattern_base(freq, headerTable) # 尋找到所有條件模式基
cond_pat_dataset = [] # 將條件模式基字典轉(zhuǎn)化為數(shù)組
for item in cond_pat_base:
item_temp = list(item)
item_temp.sort()
for i in range(cond_pat_base[item]):
cond_pat_dataset.append(item_temp)
cond_tree, cur_headtable = self.create_fptree(cond_pat_dataset, min_support)
if cur_headtable != None:
self.create_cond_fptree(cur_headtable, min_support, freq_set, freq_items, support_data) # 遞歸挖掘條件FP樹
return cur_headtable
############End##########第四關(guān)：根據(jù)由{e)結(jié)尾的條件FPtree樹計(jì)算由(e)結(jié)尾的頻繁2項(xiàng)集
任務(wù)描述
本關(guān)任務(wù)：認(rèn)識(shí) FPgrowth 算法計(jì)算頻繁項(xiàng)集。
相關(guān)知識(shí)
為了完成本關(guān)任務(wù)，你需要掌握：根據(jù)由{e)結(jié)尾的條件FPtree樹計(jì)算由(e)結(jié)尾的頻繁2項(xiàng)集。
FP 增長算法的頻繁項(xiàng)集產(chǎn)生
上一個(gè)關(guān)卡中，我們通過（1）（2）（3）步驟已經(jīng)完成了{(lán)e}條件下的FPtree構(gòu)建，下面我們接著來看如何通過該條件樹計(jì)算由(e)結(jié)尾的頻繁2項(xiàng)集。
(4) FP 增長使用 e 的條件FP樹來解決發(fā)現(xiàn)以de, ce, be和ae結(jié)尾的頻繁項(xiàng)集的子問題。為了發(fā)現(xiàn)以 de 結(jié)尾的頻繁項(xiàng)集，從項(xiàng)e的條件FP樹收集d的所有前綴路徑.通過將與結(jié)點(diǎn) d 相關(guān)聯(lián)的頻度計(jì)數(shù)求和，得到項(xiàng)集{d, e}的支持度計(jì)數(shù)。因?yàn)轫?xiàng)集{d, e}的支持度計(jì)數(shù)等于 2 ，所以它是頻繁項(xiàng)集。接下來，算法采用第 3 步介紹的方法構(gòu)建de的條件FP樹。更新了支持度計(jì)數(shù)并刪除了非頻繁項(xiàng)c之后，de 的條件FP樹顯示在圖三d中。因?yàn)樵摋l件FP樹只包含一個(gè)支持度等于最小支持度的項(xiàng)a,算法提取出頻繁項(xiàng)集{a, d, e}并轉(zhuǎn)到下一-個(gè)子問題，產(chǎn)生以ce結(jié)尾的頻繁項(xiàng)集。處理c的前綴路徑后，只發(fā)現(xiàn)項(xiàng)集{c, e}是頻繁的。接下來，算法繼續(xù)解決下一個(gè)子問題并發(fā)現(xiàn)項(xiàng)集{a, e}是剩下唯一的頻繁項(xiàng)集。 使用e的條件FP樹來計(jì)算以{e}結(jié)尾的頻繁2項(xiàng)集的過程的實(shí)現(xiàn)如下：
# 將條件模式基字典轉(zhuǎn)化為數(shù)組# 創(chuàng)建條件模式樹cond_tree, cur_headtable = fp.create_fptree(cond_pat_dataset, min_support)freqItemSet = set()support_data = {}if cur_headtable != None:fp.create_cond_fptree(cur_headtable, min_support, set(), freqItemSet, support_data) # 遞歸挖掘條件FP樹print(cur_headtable)#根據(jù)e的條件FP樹計(jì)算以e為結(jié)尾的頻繁二項(xiàng)集
FP 增長是一一個(gè)有趣的算法，它展示了如何使用事務(wù)數(shù)據(jù)集的壓縮表示來有效地產(chǎn)生頻繁項(xiàng)集。此外，對(duì)于某些事務(wù)數(shù)據(jù)集，F(xiàn)P增長算法比標(biāo)準(zhǔn)的 Apriori 算法要快幾個(gè)數(shù)量級(jí)。FP增長算法的運(yùn)行性能依賴于數(shù)據(jù)集的壓縮因子(compaction factor)。如果生成的條件P樹非常茂盛(在最壞情形下，是一棵滿前綴樹)，則算法的性能顯著下降，因?yàn)樗惴ū仨毊a(chǎn)生大量的子問題，并且需要合并每個(gè)子問題返回的結(jié)果。
編程要求
根據(jù)提示，在右側(cè)編輯器Begin和End之間補(bǔ)充代碼，完成 FP 增長算法尋找頻繁二項(xiàng)集的過程。
測(cè)試說明
點(diǎn)擊評(píng)測(cè)，平臺(tái)會(huì)對(duì)你編寫的代碼進(jìn)行測(cè)試。 如程序無誤，運(yùn)行程序后提示程序執(zhí)行成功，結(jié)果見文檔輸出。，輸出會(huì)展示在文檔中； 如程序有誤，無法通過評(píng)測(cè)，且提示程序執(zhí)行出錯(cuò)。
通關(guān)代碼（我在最后面print那里加了else，也能通關(guān)）文章來源地址http://www.zghlxwxcb.cn/news/detail-853409.html
import os
import time
from tqdm import tqdm
class Node:
def __init__(self, node_name, count, parentNode):
self.name = node_name
self.count = count
self.nodeLink = None # 根據(jù)nideLink可以找到整棵樹中所有nodename一樣的節(jié)點(diǎn)
self.parent = parentNode # 父親節(jié)點(diǎn)
self.children = {} # 子節(jié)點(diǎn){節(jié)點(diǎn)名字:節(jié)點(diǎn)地址}
class Fp_growth():
def update_header(self, node, targetNode): # 更新headertable中的node節(jié)點(diǎn)形成的鏈表
while node.nodeLink != None:
node = node.nodeLink
node.nodeLink = targetNode
def update_fptree(self, items, node, headerTable): # 用于更新fptree
if items[0] in node.children:
# 判斷items的第一個(gè)結(jié)點(diǎn)是否已作為子結(jié)點(diǎn)
node.children[items[0]].count += 1
else:
# 創(chuàng)建新的分支
node.children[items[0]] = Node(items[0], 1, node)
# 更新相應(yīng)頻繁項(xiàng)集的鏈表，往后添加
if headerTable[items[0]][1] == None:
headerTable[items[0]][1] = node.children[items[0]]
else:
self.update_header(headerTable[items[0]][1], node.children[items[0]])
# 遞歸
if len(items) > 1:
self.update_fptree(items[1:], node.children[items[0]], headerTable)
def create_fptree(self, data_set, min_support, flag=False): # FPTree構(gòu)建, 建樹主函數(shù)
'''
根據(jù)data_set創(chuàng)建fp樹
header_table結(jié)構(gòu)為
{"nodename":[num,node],..} 根據(jù)node.nodelink可以找到整個(gè)樹中的所有nodename
'''
item_count = {} # 統(tǒng)計(jì)各項(xiàng)出現(xiàn)次數(shù)
for t in data_set: # 第一次遍歷，得到頻繁一項(xiàng)集
for item in t:
if item not in item_count:
item_count[item] = 1
else:
item_count[item] += 1
headerTable = {} #頭表構(gòu)建
for k in item_count: # 剔除不滿足最小支持度的項(xiàng)
if item_count[k] >= min_support:
headerTable[k] = item_count[k]
freqItemSet = set(headerTable.keys()) # 滿足最小支持度的頻繁項(xiàng)集
if len(freqItemSet) == 0:
return None, None
for k in headerTable:
headerTable[k] = [headerTable[k], None] # element: [count, node]
tree_header = Node('head node', 1, None)
if flag:
ite = tqdm(data_set)
else:
ite = data_set
for t in ite: # 第二次遍歷，建樹
localD = {}
for item in t:
if item in freqItemSet: # 過濾，只取該樣本中滿足最小支持度的頻繁項(xiàng)
localD[item] = headerTable[item][0] # element : count
if len(localD) > 0:
# 根據(jù)全局頻數(shù)從大到小對(duì)單樣本排序
order_item = [v[0] for v in sorted(localD.items(), key=lambda x: x[1], reverse=True)]
# 用過濾且排序后的樣本更新樹
self.update_fptree(order_item, tree_header, headerTable)
return tree_header, headerTable
def find_path(self, node, nodepath):
'''
遞歸將node的父節(jié)點(diǎn)添加到路徑
'''
if node.parent != None:
nodepath.append(node.parent.name)
self.find_path(node.parent, nodepath)
def find_cond_pattern_base(self, node_name, headerTable):
'''
根據(jù)節(jié)點(diǎn)名字，找出所有條件模式基
'''
treeNode = headerTable[node_name][1]
cond_pat_base = {} # 保存所有條件模式基
while treeNode != None:
nodepath = []
self.find_path(treeNode, nodepath)
if len(nodepath) > 1:
cond_pat_base[frozenset(nodepath[:-1])] = treeNode.count
treeNode = treeNode.nodeLink
return cond_pat_base
def create_cond_fptree(self, headerTable, min_support, temp, freq_items, support_data):
'''
# 創(chuàng)建條件樹
'''
# 最開始的頻繁項(xiàng)集是headerTable中的各元素
freqs = [v[0] for v in sorted(headerTable.items(), key=lambda p: p[1][0])] # 根據(jù)頻繁項(xiàng)的總頻次排序
for freq in freqs: # 對(duì)每個(gè)頻繁項(xiàng)
freq_set = temp.copy()
freq_set.add(freq)
freq_items.add(frozenset(freq_set))
if frozenset(freq_set) not in support_data: # 檢查該頻繁項(xiàng)是否在support_data中
support_data[frozenset(freq_set)] = headerTable[freq][0]
else:
support_data[frozenset(freq_set)] += headerTable[freq][0]
cond_pat_base = self.find_cond_pattern_base(freq, headerTable) # 尋找到所有條件模式基
cond_pat_dataset = [] # 將條件模式基字典轉(zhuǎn)化為數(shù)組
for item in cond_pat_base:
item_temp = list(item)
item_temp.sort()
for i in range(cond_pat_base[item]):
cond_pat_dataset.append(item_temp)
# 創(chuàng)建條件模式樹
cond_tree, cur_headtable = self.create_fptree(cond_pat_dataset, min_support)
if cur_headtable != None:
self.create_cond_fptree(cur_headtable, min_support, freq_set, freq_items, support_data) # 遞歸挖掘條件FP樹
def generate_L(self, data_set, min_support):
freqItemSet = set()
support_data = {}
tree_header, headerTable = self.create_fptree(data_set, min_support, flag=True) # 創(chuàng)建數(shù)據(jù)集的fptree
# 創(chuàng)建各頻繁一項(xiàng)的fptree，并挖掘頻繁項(xiàng)并保存支持度計(jì)數(shù)
self.create_cond_fptree(headerTable, min_support, set(), freqItemSet, support_data)
max_l = 0
for i in freqItemSet: # 將頻繁項(xiàng)根據(jù)大小保存到指定的容器L中
if len(i) > max_l: max_l = len(i)
L = [set() for _ in range(max_l)]
for i in freqItemSet:
L[len(i) - 1].add(i)
for i in range(len(L)):
print("frequent item {}:{}".format(i + 1, len(L[i])))
return L, support_data
def generate_R(self, data_set, min_support, min_conf):
L, support_data = self.generate_L(data_set, min_support)
rule_list = []
sub_set_list = []
for i in range(0, len(L)):
for freq_set in L[i]:
for sub_set in sub_set_list:
if sub_set.issubset(
freq_set) and freq_set - sub_set in support_data: # and freq_set-sub_set in support_data
conf = support_data[freq_set] / support_data[freq_set - sub_set]
big_rule = (freq_set - sub_set, sub_set, conf)
if conf >= min_conf and big_rule not in rule_list:
# print freq_set-sub_set, " => ", sub_set, "conf: ", conf
rule_list.append(big_rule)
sub_set_list.append(freq_set)
rule_list = sorted(rule_list, key=lambda x: (x[2]), reverse=True)
return rule_list
if __name__ == "__main__":
min_support = 2 # 最小支持度
min_conf = 0.5 # 最小置信度
data_set = [['a', 'b'], ['b', 'c', 'd'], ['a','c', 'd','e'], ['a', 'd', 'e'], ['a', 'b','c'], ['b', 'c'], ['a', 'b','c','d'],
['a', 'b', 'd'], ['a', 'b', 'c'], ['b', 'c', 'e']]
#根據(jù)dataset獲得規(guī)則
fp = Fp_growth()
rule_list = fp.generate_R(data_set, min_support, min_conf)
print(rule_list)
##############Begin##################
# 根據(jù)由{e}結(jié)尾的條件FPtree樹計(jì)算由{e}結(jié)尾的頻繁2項(xiàng)集
# 創(chuàng)建Fptree
e_condition_tree, e_header_table = fp.create_fptree([['e']], min_support)
if e_condition_tree is not None and e_header_table is not None: # 檢查結(jié)果是否為空
cond_pattern_base = fp.find_cond_pattern_base('e', e_header_table)
cond_pattern_dataset = []
for item in cond_pattern_base:
item_temp = list(item)
item_temp.sort()
for i in range(cond_pattern_base[item]):
cond_pattern_dataset.append(item_temp)
e_cond_tree, cur_headtable = fp.create_fptree(cond_pattern_dataset, min_support)
print(cur_headtable) # 在這里打印 cur_headtable
else:
print("No frequent itemsets found for the given condition.")
到了這里，關(guān)于頭歌實(shí)踐教學(xué)平臺(tái)-FPgrowth算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
