寫在前面 筆者新人，查看了各個關于fp-tree的原理與實現后的一點小小的總結
本文參考鏈接：
添加鏈接描述
添加鏈接描述

思想概括

• 先將數據掃描得到c1
• 處理c1得到f1（修剪枝葉和apriori是一樣的過程）
• 根據f1得到的支持度將數據中的每一項集的項進行項之間的重新排列（即為f）
• 之后對數據進行二次掃描（也是最后一次），將數據加入樹中。
• 得到一棵樹
• 對這棵樹進行挖掘頻繁模式

偽代碼

挖掘頻繁模式前首先要構造FP-Tree，算法偽碼如下： 輸入:一個交易數據庫DB和一個最小支持度threshold. 輸出:它的FP-tree. 步驟: 1.掃描數據庫DB一遍.得到頻繁項的集合F和每個頻繁項的支持度.把F按支持度遞降排序,結果記為L. 2.創建FP-tree的根節點,記為T,并且標記為’null’.然后對DB中的每個事務Trans做如下的步驟. 根據L中的順序,選出并排序Trans中的事務項.把Trans中排好序的事務項列表記為[p|P],其中p是第一個元素,P是列表的剩余部分.調用insert_tree([p|P],T). 函數insert_tree([p|P],T)的運行如下. 如果T有一個子結點N,其中N.item-name=p.item-name,則將N的count域值增加1;否則,創建一個新節點N,使它的count為1,使它的父節點為T,并且使它的node_link和那些具有相同item_name域串起來.如果P非空,則遞歸調用insert_tree(P,N).對FP-Tree進行挖掘，算法如下： 輸入:一棵用算法一建立的樹Tree 輸出:所有的頻繁集 步驟: 調用FP-growth(Tree,null). procedure FP-Growth ( Tree, x) { (1)if (Tree只包含單路徑P) then (2) 對路徑P中節點的每個組合（記為B） (3) 生成模式B并x，支持數=B中所有節點的最小支持度 (4) else 對Tree頭上的每個ai，do { (5) 生成模式B= ai 并 x，支持度=ai.support； (6) 構造B的條件模式庫和B的條件FP樹TreeB； (7)if TreeB != 空集 (8)**then **call FP-Growth ( TreeB , B ) } }

代碼實現（python）具體過程見鏈接1

import re import collections import itertools data = []data = [['a','b','c','d','e','f','g','h'],['a','f','g'],['b','d','e','f','j'],['a','b','d','i','k'],['a','b','e','g'],['g','b']] #print(data) data = data support = 3 #統計item的頻率 #CountItem = collections.defaultdict(int)用法和list差不太多 CountItem = collections.defaultdict(int) for line in data:for item in line:CountItem[item] += 1#將dict按照頻率從大到小排序,并且刪除掉頻率過小的項 a = sorted(CountItem.items(),key = lambda x:x[1],reverse=True) for i in range(len(a)):if a[i][1] < support:a = a[:i]break#更新data中，每一筆交易的商品順序 for i in range(len(data)):data[i] = [char for char in data[i] if CountItem[char] >= support]data[i] = sorted(data[i],key = lambda x:CountItem[x],reverse=True)#定義好節點 class node:def __init__(self,val,char):self.val = val#用于定義當前的計數self.char = char#用于定義當前的字符是多少self.children = {}#用于存儲孩子self.next = None#用于鏈表，鏈接到另一個孩子處self.father = None#構建條件樹時向上搜索self.visit = 0#用于鏈表的時候觀察是否已經被訪問過了self.nodelink = collections.defaultdict()self.nodelink1 = collections.defaultdict()class FPTree():def __init__(self):self.root = node(-1,'root')self.FrequentItem = collections.defaultdict(int)#用來存儲頻繁項集self.res = []def BuildTree(self,data):#建立fp樹的函數,data應該以list[list[]]的形式，其中內部的list包含了商品的名稱，以字符串表示for line in data:#取出第一個list，用line來表示root = self.rootfor item in line:#對于列表中的每一項if item not in root.children.keys():#如果item不在dict中root.children[item] = node(1,item)#創建一個新的節點root.children[item].father = root#用于從下往上尋找else:root.children[item].val += 1#否則，計數加1root = root.children[item]#往下走一步#根據這個root創建鏈表if item in self.root.nodelink.keys():#如果這個item在nodelink中已經存在了if root.visit == 0:#如果這個點沒有被訪問過self.root.nodelink1[item].next = rootself.root.nodelink1[item] = self.root.nodelink1[item].nextroot.visit = 1#被訪問了else:#如果這個item在nodelink中不存在self.root.nodelink[item] = rootself.root.nodelink1[item] = rootroot.visit = 1print('樹建立完成')return self.rootdef IsSinglePath(self,root):#print('是否為單路徑')if not root: return Trueif not root.children: return Truea = list(root.children.values())if len(a) > 1: return Falseelse:for value in root.children.values():if self.IsSinglePath(value) == False: return Falsereturn Truedef FP_growth(self,Tree,a,HeadTable):#Tree表示樹的根節點，a用列表表示的頻繁項集,HeadTable用來表示頭表#我們首先需要判斷這個樹是不是單路徑的，創建一個單路徑函數IsSinglePath(root)if self.IsSinglePath(Tree):#如果是單路徑的#對于路徑中的每個組合，記作b，產生模式，b并a，support = b中節點的最小支持度root, temp = Tree, []#創建一個空列表來存儲while root.children:for child in root.children.values():temp.append((child.char,child.val))root = child#產生每個組合ans = []for i in range(1,len(temp)+1):ans += list(itertools.combinations(temp,i))#print('ans = ',ans)for item in ans:mychar = [char[0] for char in item] + amycount = min([count[1] for count in item])if mycount >= support:#print([mychar,mycount])self.res.append([mychar,mycount])#print(self.res)else:#不是單路徑，存在多個路徑root = Tree#print(Tree.char)#對于root頭表中的每一項進行操作HeadTable.reverse()#首先將頭表逆序for (child,count) in HeadTable:#child表示字符，count表示支持度b = [child] + a #新的頻繁模式#構造b的條件模式基#print(b)self.res.append([b,count])tmp = Tree.nodelink[child]#此時為第一個節點從這個節點開始找,tmp一直保持在鏈表當中 data = []#用來保存條件模式基#if b == ['sausage','cream']:# print(root.char)while tmp:#當tmp一直存在的時候tmpup = tmp#準備向上走res = [[],tmpup.val]#用來保存條件模式while tmpup.father:res[0].append(tmpup.char)tmpup = tmpup.fatherres[0] = res[0][::-1]#逆序 data.append(res)#條件模式基保存完畢tmp = tmp.next#if b == ['sausage','cream']: print(2)#條件模式基構造完畢，儲存在data中，下一步是建立b的fp-Tree#統計詞頻CountItem = collections.defaultdict(int)for [tmp,count] in data:for i in tmp[:-1]:CountItem[i] += countfor i in range(len(data)):data[i][0] = [char for char in data[i][0] if CountItem[char] >= support]#刪除掉不符合的項data[i][0] = sorted(data[i][0],key = lambda x:CountItem[x],reverse=True)#排序#print('2',data)#此時數據已經準備好了，我們需要做的就是構造條件樹#CountItem1 = collections.defaultdict(int)root = node(-1,'root')#創建根節點，值為-1，字符為rootfor [tmp,count] in data:#item 是 [list[],count] 的形式tmproot = root#定位到根節點for item in tmp:#對于tmp中的每一個商品#print('123',item)#CountItem1[item] += 1if item in tmproot.children.keys():#如果這個商品已經在tmproot的孩子中了tmproot.children[item].val += count#更新值else:#如果這個商品沒有在tmproot的孩子中tmproot.children[item] = node(count,item)#創建一個新的節點tmproot.children[item].father = tmproot#方便從下往上找tmproot = tmproot.children[item]#往下走一步#根據這個root創建鏈表if item in root.nodelink.keys():#這個item在nodelink中存在if tmproot.visit == 0:root.nodelink1[item].next = tmprootroot.nodelink1[item] = root.nodelink1[item].nexttmproot.visit = 1else:#這個item在nodelink中不存在root.nodelink[item] = tmprootroot.nodelink1[item] = tmproottmproot.visit = 1if root:#如果新的條件樹不為空NewHeadTable = sorted(CountItem.items(),key = lambda x:x[1],reverse=True)for i in range(len(NewHeadTable)):if NewHeadTable[i][1] < support:NewHeadTable = NewHeadTable[:i]breakself.FP_growth(root,b,NewHeadTable)#我們需要創建新的headtable#return root#成功返回條件樹 def PrintTree(self,root):#層次遍歷打印樹if not root: returnres = []if root.children:for (name,child) in root.children.items():res += [name+' '+str(child.val),self.PrintTree(child)]return reselse: return obj = FPTree() root = obj.BuildTree(data) #print(obj.PrintTree(root))obj.FP_growth(root,[],a) print(obj.res)

總結

以上是生活随笔為你收集整理的Aprior算法简化算法——FP-Tree思想与实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。