一、FP-growth介紹
從大規(guī)模的數(shù)據(jù)集中矿瘦,尋找不同特征或者物品之間的隱含關(guān)系镰吆,稱為關(guān)聯(lián)分析(association analysis),或者關(guān)聯(lián)規(guī)則學(xué)習(xí)(association rule learning)堂湖。
在 Apriori 算法中,尋找頻繁項(xiàng)集状土,需要對(duì)每一個(gè)可能的頻繁項(xiàng)掃描一遍數(shù)據(jù)集計(jì)算支持度无蜂,計(jì)算量龐大。
在 FP-growth 算法中蒙谓,尋找頻繁項(xiàng)集斥季,只需要掃描兩遍數(shù)據(jù)集,將數(shù)據(jù)存儲(chǔ)在FP樹的結(jié)構(gòu)上累驮,然后在FP樹上挖掘頻繁項(xiàng)集酣倾。
- 優(yōu)點(diǎn):速度一般要快于 Apriori。
- 缺點(diǎn):實(shí)現(xiàn)比較困難慰照,在某些數(shù)據(jù)集上性能會(huì)下降。
- 適用數(shù)據(jù)類型:標(biāo)稱型數(shù)據(jù)琉朽。
例如在下述例子中毒租,下圖是一顆FP樹:
FP代表頻繁模式(Frequent Pattern),一個(gè)元素項(xiàng)
可以在一顆FP樹上出現(xiàn)多次箱叁。
樹節(jié)點(diǎn)上給出了當(dāng)前節(jié)點(diǎn)的路徑在數(shù)據(jù)集中的出現(xiàn)次數(shù)墅垮,例如{z:5}表示元素{z}在數(shù)據(jù)集中出現(xiàn)了5次;{y:3}表示路徑{y, x, z}在數(shù)據(jù)集中出現(xiàn)了3次耕漱;{s:2}表示路徑{s, y, x, z}在數(shù)據(jù)集中出現(xiàn)了2次算色。
左側(cè)為頭指針表,給出了每個(gè)元素在數(shù)據(jù)集中出現(xiàn)的次數(shù)螟够,并由鏈表通過節(jié)點(diǎn)鏈接(node link)依次鏈接每個(gè)元素灾梦。部分元素因?yàn)椴粷M足最小支持度的要求,所以不儲(chǔ)存在FP樹中妓笙。
在 FP-growth 算法中若河,同樣采用了 Apriori 算法的思想,如果某個(gè)項(xiàng)是非頻繁的寞宫,那么這個(gè)項(xiàng)的所有超集也是非頻繁的萧福。
二、構(gòu)建FP樹
構(gòu)建FP樹的過程只需要掃描兩遍
數(shù)據(jù)集辈赋。
第一遍掃描鲫忍,計(jì)算每個(gè)單個(gè)元素的頻率膏燕,并根據(jù)最小支持度,濾除不滿足的元素悟民。
第二遍掃描坝辫,首先對(duì)數(shù)據(jù)集進(jìn)行處理,每一條數(shù)據(jù)按照元素的絕對(duì)出現(xiàn)頻率排序逾雄,并濾除不滿足最小支持度的元素阀溶。
例如根據(jù)上述的頭指針表,元素排序?yàn)椋鹺:5, x:4, y:3, s:3, r:3, t:3}鸦泳,所以處理后的數(shù)據(jù)為:
處理后银锻,遍歷數(shù)據(jù)集,將每一條數(shù)據(jù)插入FP樹中做鹰,從根節(jié)點(diǎn)開始遞歸添加路徑击纬,存在則將數(shù)值增加,不存在則創(chuàng)建新的節(jié)點(diǎn)钾麸。
例如下圖所示更振,① 根節(jié)點(diǎn)不存在子節(jié)點(diǎn){z},所以創(chuàng)建新的子節(jié)點(diǎn){z}饭尝,遞歸節(jié)點(diǎn){z}肯腕,因不存在子節(jié)點(diǎn){r},所以創(chuàng)建新的子節(jié)點(diǎn){r}钥平,② 根節(jié)點(diǎn)存在子節(jié)點(diǎn){z}实撒,所以數(shù)值增加,遞歸節(jié)點(diǎn){z}涉瘾,因不存在子節(jié)點(diǎn){x}知态,所以創(chuàng)建新的子節(jié)點(diǎn){x},遞歸節(jié)點(diǎn){x}立叛,......负敏,如此遞歸。
三秘蛇、從FP樹中挖掘頻繁項(xiàng)集
全文代碼:
from numpy import *
from time import *
def load_simple_data():
"""
Function:
創(chuàng)建加載簡(jiǎn)單數(shù)據(jù)集
Parameters:
無
Returns:
simple_data - 簡(jiǎn)單數(shù)據(jù)集
Modify:
2018-12-27
"""
simple_data = [['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 simple_data
def create_init_set(data_set):
"""
Function:
計(jì)算項(xiàng)集在數(shù)據(jù)集的出現(xiàn)次數(shù)
Parameters:
data_set - 數(shù)據(jù)集
Returns:
ret_dict - 包含出現(xiàn)次數(shù)的項(xiàng)集字典
Modify:
2018-12-27
"""
ret_dict = {}
for trans in data_set:
ret_dict[frozenset(trans)] = 1
return ret_dict
def update_tree(items, in_tree, header_table, count):
"""
Function:
更新樹節(jié)點(diǎn)其做,讓FP樹生長(zhǎng)
Parameters:
items - 項(xiàng)集
in_tree - 當(dāng)前FP樹
header_table - 頭指針表
count - 次數(shù)
Returns:
無
Modify:
2018-12-27
"""
# 判斷排序后列表的第一個(gè)元素是否已經(jīng)是根節(jié)點(diǎn)的子節(jié)點(diǎn)
if items[0] in in_tree.children:
# 添加出現(xiàn)次數(shù)
# children = {}
in_tree.children[items[0]].inc(count)
else:
# 創(chuàng)建根節(jié)點(diǎn)的子節(jié)點(diǎn)
in_tree.children[items[0]] = TreeNode(items[0], count, in_tree)
# 如果該元素的后繼節(jié)點(diǎn)不存在,則直接加入赁还。如果有后繼節(jié)點(diǎn)庶柿,則遍歷鏈表尾部將其加入
if header_table[items[0]][1] == None:
header_table[items[0]][1] = in_tree.children[items[0]]
else:
update_header(header_table[items[0]][1], in_tree.children[items[0]])
# 列表元素長(zhǎng)度大于1,遞歸調(diào)用更新FP樹函數(shù)
if len(items) > 1:
update_tree(items[1::], in_tree.children[items[0]], header_table, count)
def update_header(node_to_test, target_node):
"""
Function:
更新頭指針表的節(jié)點(diǎn)鏈接
Parameters:
node_to_test - 遍歷節(jié)點(diǎn)
target_node - 目標(biāo)節(jié)點(diǎn)
Returns:
無
Modify:
2018-12-27
"""
# 遍歷到鏈表尾節(jié)點(diǎn)
while (node_to_test.node_link != None):
node_to_test = node_to_test.node_link
# 將剛添加的樹節(jié)點(diǎn)加入鏈表的尾部
node_to_test.node_link = target_node
def create_tree(data_set, min_sup=1):
"""
Function:
遍歷數(shù)據(jù)集兩次構(gòu)建FP樹
Parameters:
data_set - 包含項(xiàng)集出現(xiàn)次數(shù)的數(shù)據(jù)集字典
min_sup - 最小支持度
Returns:
ret_tree - FP樹
hearder_table - 頭指針表
Modify:
2018-12-27
"""
hearder_table = {}
# 第一次遍歷數(shù)據(jù)集秽浇,獲取單個(gè)元素的次數(shù)
for trans in data_set:
for item in trans:
hearder_table[item] = hearder_table.get(item, 0) + data_set[trans]
# 去除不滿足最小支持度的單個(gè)元素
for k in list(hearder_table.keys()):
if hearder_table[k] < min_sup:
del (hearder_table[k])
freq_item_set = set(hearder_table.keys())
# 無頻繁項(xiàng)就直接返回
if len(freq_item_set) == 0:
return None, None
# 擴(kuò)展頭指針表浮庐,添加指向每種類型第一個(gè)元素的指針(節(jié)點(diǎn)鏈接)
for k in hearder_table:
hearder_table[k] = [hearder_table[k], None]
# 創(chuàng)建根節(jié)點(diǎn)
ret_tree = TreeNode('Null Set', 1, None)
# 第二次遍歷數(shù)據(jù)集,構(gòu)建FP樹
for tran_set, count in data_set.items():
# tran_set: frozenset({'h', 'p', 'z', 'j', 'r'})
# count: 1
local_d = {}
# 如果單個(gè)元素是頻繁項(xiàng),則加入localD列表
for item in tran_set:
if item in freq_item_set:
# hearder_table:{'b': [3, None]}
local_d[item] = hearder_table[item][0]
# localD: {'r': 3, 'j': 1, 'z': 5, 'h': 1, 'p': 2}
if len(local_d) > 0:
# 元素按出現(xiàn)次數(shù)排序
ordered_items = [v[0] for v in sorted(local_d.items(), key=lambda p: p[1], reverse=True)]
# 更新FP樹审残,讓FP樹生長(zhǎng)
update_tree(ordered_items, ret_tree, hearder_table, count)
return ret_tree, hearder_table
class TreeNode:
# name:節(jié)點(diǎn)元素名稱梭域,在構(gòu)造時(shí)初始化為給定值
# count:出現(xiàn)次數(shù),在構(gòu)造時(shí)初始化為給定值
# node_link:指向下一個(gè)相似節(jié)點(diǎn)的指針搅轿,默認(rèn)為None
# parent:指向父節(jié)點(diǎn)的指針病涨,在構(gòu)造時(shí)初始化為給定值
# children:指向子節(jié)點(diǎn)的字典,以子節(jié)點(diǎn)的元素名稱為鍵璧坟,指向子節(jié)點(diǎn)的指針為值既穆,初始化為空字典
def __init__(self, name_value, num_occur, parent_node):
self.name = name_value
self.count = num_occur
self.node_link = None
self.parent = parent_node
self.children = {}
def inc(self, num_occur):
# 增加節(jié)點(diǎn)出現(xiàn)次數(shù)
self.count += num_occur
def disp(self, ind=1):
# 用于將樹以文本形式顯示
print(' ' * ind, self.name, ' ', self.count)
for child in self.children.values():
child.disp(ind + 1)
def ascend_tree(leaf_node, prefix_path):
"""
Function:
根據(jù)當(dāng)前節(jié)點(diǎn)向前追溯至根節(jié)點(diǎn),記錄前綴路徑
Parameters:
leaf_node - 給定元素項(xiàng)節(jié)點(diǎn)
prefix_path - 前綴路徑列表
Returns:
無
Modify:
2019-1-6
"""
# 如果節(jié)點(diǎn)有父節(jié)點(diǎn)雀鹃,則將當(dāng)前節(jié)點(diǎn)添加至前綴路徑中幻工,之后再遞歸向上追溯
if leaf_node.parent != None:
prefix_path.append(leaf_node.name)
ascend_tree(leaf_node.parent, prefix_path)
def find_prefix_path(base_pat, tree_node):
"""
Function:
發(fā)現(xiàn)以給定元素項(xiàng)結(jié)尾的所有前綴路徑
Parameters:
base_pat - 元素項(xiàng)
tree_node - 需遍歷節(jié)點(diǎn)
Returns:
cond_pats - 所有條件模式基字典
Modify:
2019-1-6
"""
# 所有條件模式基字典
cond_pats = {}
# 遍歷該節(jié)點(diǎn)的整個(gè)鏈表節(jié)點(diǎn),記錄每個(gè)節(jié)點(diǎn)的前綴路徑黎茎,并將其添加至條件模式基當(dāng)中
while tree_node != None:
prefix_path = []
ascend_tree(tree_node, prefix_path)
# 因?yàn)樵摴?jié)點(diǎn)也被加進(jìn)了路徑當(dāng)中囊颅,所以需要路徑的長(zhǎng)度大于1
if len(prefix_path) > 1:
# 如果有前綴路徑,則將前綴路徑加入條件模式基集合中傅瞻,并且將該元素在該前綴路徑中出現(xiàn)的次數(shù)也添加進(jìn)去
cond_pats[frozenset(prefix_path[1:])] = tree_node.count
# 當(dāng)前節(jié)點(diǎn)的條件模式基查找完畢后踢代,繼續(xù)查找頭指針鏈表中下一個(gè)節(jié)點(diǎn)的條件模式基
tree_node = tree_node.node_link
return cond_pats
def mine_tree(in_tree, header_table, min_sup, pre_fix, freq_item_list):
"""
Function:
創(chuàng)建條件模式樹
Parameters:
in_tree - FP樹
header_table - 頭指針表
min_sup - 最小支持度
pre_fix - 上一次遞歸的頻繁項(xiàng)集合的前綴
freq_item_list - 頻繁項(xiàng)集列表
Returns:
無
Modify:
2019-1-6
"""
# 對(duì)頭指針表中的元素項(xiàng)按照其出現(xiàn)頻率從小到大進(jìn)行排序
big_l = [v[0] for v in sorted(header_table.items(), key=lambda p:p[1][0])]
# 遍歷單元素頻繁集
for base_pat in big_l:
new_freq_set = pre_fix.copy()
new_freq_set.add(base_pat)
freq_item_list.append(new_freq_set)
# 獲得該元素的所有條件模式基,相當(dāng)于一個(gè)事務(wù)集合
cond_patt_bases = find_prefix_path(base_pat, header_table[base_pat][1])
# 根據(jù)所有條件模式基集合來構(gòu)建條件模式樹
my_cond_tree, my_head = create_tree(cond_patt_bases, min_sup)
# 如果條件模式樹的頭指針表不空(每次建樹時(shí)對(duì)元素支持度有要求
# 如果小于支持度則該元素不參與建樹過程嗅骄,所以在建樹時(shí)胳挎,條件模式基中的元素會(huì)越來越少,最后會(huì)是空樹)溺森,則遞歸建樹
if my_head != None:
print('conditional tree for:', new_freq_set)
my_cond_tree.disp(1)
mine_tree(my_cond_tree, my_head, min_sup, new_freq_set, freq_item_list)
if __name__ == '__main__':
# simple_data = load_simple_data()
# init_data = create_init_set(simple_data)
# print(simple_data)
# print(init_data)
# simple_data = load_simple_data()
# init_data = create_init_set(simple_data)
# my_fp_tree, my_header_tab = create_tree(init_data, 3)
# my_fp_tree.disp()
# simple_data = load_simple_data()
# init_data = create_init_set(simple_data)
# my_fp_tree, my_header_tab = create_tree(init_data, 3)
# cond_pats_1 = find_prefix_path('x', my_header_tab['x'][1])
# print(cond_pats_1)
# cond_pats_2 = find_prefix_path('z', my_header_tab['z'][1])
# print(cond_pats_2)
# cond_pats_3 = find_prefix_path('r', my_header_tab['r'][1])
# print(cond_pats_3)
# simple_data = load_simple_data()
# init_data = create_init_set(simple_data)
# my_fp_tree, my_header_tab = create_tree(init_data, 3)
# freq_items = []
# mine_tree(my_fp_tree, my_header_tab, 3, set([]), freq_items)
# print(freq_items)
start_time = time()
parse_dat = [line.split() for line in open('./machinelearninginaction/Ch12/kosarak.dat').readlines()]
init_set = create_init_set(parse_dat)
my_fp_tree, my_header_tab = create_tree(init_set, 100000)
my_freq_list = []
mine_tree(my_fp_tree, my_header_tab, 100000, set([]), my_freq_list)
end_time = time()
print('被10萬或者更多人瀏覽過的新聞報(bào)道或報(bào)道集合數(shù):', len(my_freq_list))
print('被10萬或者更多人瀏覽過的新聞報(bào)道或報(bào)道集合:', my_freq_list)
print('總共執(zhí)行時(shí)間:', end_time - start_time)
一個(gè)元素的條件模式基(conditional pattern base)慕爬,是這個(gè)元素所有前綴路徑(prefix path)的集合。
前綴路徑(prefix path)儿惫,是當(dāng)前元素到根節(jié)點(diǎn)之間的路徑(不包括當(dāng)前元素和根節(jié)點(diǎn))澡罚。
例如下圖伸但,{r}的條件模式基是{{z}{z, x, y}{x, s}}:
從FP樹挖掘頻繁項(xiàng)集的過程可描述為:
- 對(duì)于頭指針表中的每一個(gè)元素肾请,獲取其條件模式基
- 根據(jù)條件模式基,構(gòu)建條件FP樹(即更胖,將條件模式基當(dāng)作新的數(shù)據(jù)集铛铁,按照建樹的流程,重新構(gòu)建一棵FP樹)
- 繼續(xù)對(duì)于條件FP樹的頭指針表中的每一個(gè)元素却妨,獲取其條件模式基
- 繼續(xù)根據(jù)條件模式基饵逐,構(gòu)建條件FP樹
- 如此遞歸過程,直到無法構(gòu)建出FP樹為止
記錄頻繁項(xiàng)集的過程在創(chuàng)建一棵新的FP樹時(shí)記錄彪标,偽代碼如下表示:
關(guān)于此處的理解:
首先構(gòu)建了一棵FP樹倍权,此時(shí)FP樹中的單個(gè)元素均滿足最小支持度(假設(shè)有{a}{b}{c}{d}{e}5個(gè)元素),遍歷其中的每一個(gè)元素(假設(shè)此時(shí)遍歷{a})捞烟,先將元素{a}加入總的頻繁項(xiàng)集薄声,再尋找元素{a}的條件模式基(假設(shè)有{c, b}{b, d}{b, c, e, d})当船,根據(jù)這些前綴路徑遞歸構(gòu)建一棵條件FP樹(若這棵樹能夠構(gòu)建的起來,說明樹中的單個(gè)元素也是滿足最小支持度的默辨,假設(shè)條件FP樹中有{b}{c}{d}3個(gè)元素德频,{e}不滿足最小支持度),說明{b}{c}{d}這三個(gè)元素滿足最小支持度缩幸,遍歷其中的每一個(gè)元素(假設(shè)此時(shí)遍歷{b})壹置,復(fù)制上一層遞歸的頻繁項(xiàng)集(即,{a})表谊,將當(dāng)前遍歷元素{b}加入復(fù)制的頻繁項(xiàng)集中(即钞护,構(gòu)成{a, b}),然后再將{a, b}加入總的頻繁項(xiàng)集铃肯,再在條件FP樹中尋找元素{b}的條件模式基患亿,繼續(xù)遞歸構(gòu)建。因?yàn)樯弦粚舆f歸中的頻繁項(xiàng)集{a}是一定滿足最小支持度的押逼,由這個(gè)元素{a}搜尋得到的條件模式基步藕,一定是在數(shù)據(jù)集中跟{a}有組合的,若能據(jù)此構(gòu)建一棵條件FP樹挑格,說明這棵樹中的元素{b}{c}{d}也一定滿足最小支持度咙冗,因這元素{b}與{a}在原始數(shù)據(jù)集中有組合,且這元素{b}與上一層遞歸頻繁項(xiàng)集{a}均滿足最小支持度漂彤,所以這元素{b}和{a}的組合{a, b}一定滿足最小支持度雾消,且存在在原始數(shù)據(jù)集中,所以加入總的頻繁項(xiàng)集挫望。
四立润、實(shí)例:從新聞網(wǎng)站點(diǎn)擊流中挖掘
現(xiàn)有一個(gè)kosarak.dat文件,它包含將近100萬條記錄媳板。該文件中的每一行包含某個(gè)用戶瀏覽過的新聞報(bào)道桑腮。一些用戶只看過一篇報(bào)道,而有些用戶看過2498篇報(bào)道蛉幸。因?yàn)橛脩艉蛨?bào)道被編碼成整數(shù)破讨,所以查看頻繁項(xiàng)集很難得到更多的東西,但是該數(shù)據(jù)對(duì)于展示FP-growth算法的速度十分有效奕纫。
從上圖可以看出提陶,構(gòu)建樹以及掃描100萬行找出頻繁項(xiàng)集只要不到8秒鐘,這展示了FP-growth算法的強(qiáng)大威力匹层。
五隙笆、小結(jié)
FP-growth算法是一種用于發(fā)現(xiàn)數(shù)據(jù)集中頻繁模式的有效方法。FP-growth算法利用了Apriori原則,并且只對(duì)數(shù)據(jù)集掃描兩次撑柔,所以執(zhí)行更快煤率。Apriori算法產(chǎn)生候選項(xiàng)集,然后掃描數(shù)據(jù)集來檢查它們是否頻繁乏冀。在FP-growth算法中蝶糯,數(shù)據(jù)集存儲(chǔ)在一個(gè)稱為FP樹的結(jié)構(gòu)中。
FP樹構(gòu)建完成后辆沦,可以通過查找元素項(xiàng)的條件基及構(gòu)建條件FP樹來發(fā)現(xiàn)頻繁項(xiàng)集昼捍。該過程不斷以更多元素作為條件重復(fù)進(jìn)行,直到FP樹只包含一個(gè)元素為止肢扯。