FP-Growthアルゴリズムの理解
20822 ワード
FP-Growthアルゴリズムの理解
基本概念
Frequent Pattern Growth-頻繁モード成長は全アルゴリズム実行中で、データセットを2回遍歴するだけで、頻繁モードの発見を完了することができます.
FP-growthアルゴリズム概要
非常に良い発見の頻繁なセットのアルゴリズムは、アプリオリアルゴリズムに基づいて構築されますが、データ構造は異なり、FPツリーというデータ構造を使ってセットを記憶します.
アルゴリズムの核心思想
データに基づいてFPツリーを構築するステップ1:1.すべてのデータセットを巡回して、すべての項目のサポート度を計算します.非頻繁項3を破棄します.サポート度の降順に基づいてすべての項目を並べ替えます.すべてのデータセットは得られた順に再整理します.5.再整理が完了したら、各セットの終わりに頻繁でないものを捨てます. ステップ2:6.各セットを読み取り、FPツリーに挿入しながら、異なるセットの同じ項 をヘッドチェーンデータ構造で維持する.ステップ3:1.ヘッドチェーンを降順に並べ替えます.2.ヘッドチェーンノードを小さい時から大きな変数にして、条件モデルベースを得て、頻繁なセット を得ます.
FPツリー:データセットを符号化するための有効な方法FP代表:Frequent Pattern 1つのFPツリーはコンピュータ科学における他のツリーと類似しているように見えるが、それはリンク(link)を通して類似の要素を接続し、リンクされた要素項目はチェーンとして見られてもよい.
検索ツリーとは違って、1つの要素項目は、FPツリーに複数回出現してもよく、FPツリーは、セットの出現周波数を記憶してもよく、各イベントは、ツリーに経路で記憶されていて、似たような要素のセットは、ツリーの一部を共有してもよい.集合の間が完全に異なる場合のみ、ツリーは分岐し、ツリーノード上でセット内の単一の要素とシーケンス内の出現回数を与える.パスは、シーケンスの出現回数の類似項間のリンクをノードリンクと呼び、類似項の位置を素早く発見するために使用される.
コア思想は2回のデータセットを巡ります.初めて:データセットを遍歴して、最初のポインタ表を作成します.データセットを遍歴して、頭ポインタ表に基づいてFPツリーを作成します.(難点)
具体的には初めての遍歴を実現します.ヘッドポインタ、dict｛item、count｝の単一のセットはサポート度の第二次変数と比較して、それぞれの物事の中で同じセットとその対応するサポート度を探し出して、サポート度によって、一つずつ事務を並べ替えて、FPツリーの構築を行います.
FP tree—頻繁なエントリセットが次にFP treeから関連ルール概念を構築する必要があることがわかった.
条件パターンベース:ヘッドチェーンのある点のプレフィクスパスの組み合わせは、条件モードベース条件パターンベースの値が、エンドノードの値条件FPツリーに依存することである.条件モードベースでデータセット構造のFPツリーを条件FPツリーといい、FPツリーを取得した後に、頻繁なセットごとに、頻繁に掘り起こす必要がある.
具体的なプロセスは、最初に、頻繁なエントリのプレフィクスパスを取得し、次いでプレフィクスパスの条件FPツリーを構築するためのプレフィクスパスとしてプレフィクスパスを新しいデータセットとしてプレフィクスパスを利用し、条件FPツリーに1つの頻繁なエントリのみが含まれるまで、新しい条件FPツリーを構築するために反復することである.
全体として、3つのステップに分解して、FPツリーから頻繁なセット(1)を発掘し、FPツリーから条件付きモードベース(2)を取得し、条件付きモードベースを利用して、条件FPツリーを構築する(3)上記の2つのステップを繰り返し、ツリーが要素項目を含むまで、上記の2つのステップを繰り返す.
基本概念
Frequent Pattern Growth-頻繁モード成長は全アルゴリズム実行中で、データセットを2回遍歴するだけで、頻繁モードの発見を完了することができます.
FP-growthアルゴリズム概要
非常に良い発見の頻繁なセットのアルゴリズムは、アプリオリアルゴリズムに基づいて構築されますが、データ構造は異なり、FPツリーというデータ構造を使ってセットを記憶します.
アルゴリズムの核心思想
FP
FP
FP :
nodelink
データに基づいてFPツリーを構築する
FPツリー:データセットを符号化するための有効な方法FP代表:Frequent Pattern 1つのFPツリーはコンピュータ科学における他のツリーと類似しているように見えるが、それはリンク(link)を通して類似の要素を接続し、リンクされた要素項目はチェーンとして見られてもよい.
検索ツリーとは違って、1つの要素項目は、FPツリーに複数回出現してもよく、FPツリーは、セットの出現周波数を記憶してもよく、各イベントは、ツリーに経路で記憶されていて、似たような要素のセットは、ツリーの一部を共有してもよい.集合の間が完全に異なる場合のみ、ツリーは分岐し、ツリーノード上でセット内の単一の要素とシーケンス内の出現回数を与える.パスは、シーケンスの出現回数の類似項間のリンクをノードリンクと呼び、類似項の位置を素早く発見するために使用される.
コア思想は2回のデータセットを巡ります.初めて:データセットを遍歴して、最初のポインタ表を作成します.データセットを遍歴して、頭ポインタ表に基づいてFPツリーを作成します.(難点)
具体的には初めての遍歴を実現します.ヘッドポインタ、dict｛item、count｝の単一のセットはサポート度の第二次変数と比較して、それぞれの物事の中で同じセットとその対応するサポート度を探し出して、サポート度によって、一つずつ事務を並べ替えて、FPツリーの構築を行います.
class tree_node(object):
def __init__(self, name_value, num_occur, parent_node):
self.name = name_value #
self.count = num_occur #
self.node_link = None # node_link
# needs to be updated
self.parent = parent_node #
self.children = {} #
def increase(self, num_occur):
"""
increase count
:param num_occur:
:return:
"""
self.count += num_occur
def display(self, ind=1):
"""
display
:param ind:
:return:
"""
print(' '*ind, self.name, ' ', self.count)
for child in self.children.values():
child.display(ind+1)
def load_data():
data_set = [['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 data_set
def create_init_set(data_set):
"""
dic{ : }
:param data_set:
:return:
ret_dict
"""
ret_dict = dict()
for data in data_set:
if frozenset(data) not in ret_dict:
ret_dict[frozenset(data)] = ret_dict.get(frozenset(data), 0) + 1
return ret_dict
def update_header(node_to_test, target_node):
"""
, , : r r , ,
node_link , node link ,
:
:param node_to_test: min support { +(value, tree node)}
:param target_node: tree
:return:
"""
# , r r
while node_to_test.node_link is not None:
node_to_test = node_to_test.node_link
node_to_test.node_link = target_node
def update_tree(items, inTree, header_table, count):
"""
update tree ( FP-tree, )
:param items: min support key ( )
:param inTree: tree
:param header_table: min support { +(value, treeNone)}
:param count:
:return:
"""
# inTree.children ,
# inTree.children key,value tree_node
if items[0] in inTree.children:
# , tree node count
inTree.children[items[0]].increase(count)
else:
# , intree
inTree.children[items[0]] = tree_node(items[0], count, inTree)
# min support dict value null, tree
# null header
if header_table[items[0]][1] is None:
# header_table
header_table[items[0]][1] = inTree.children[items[0]]
else:
# header_table key tree node link
update_header(header_table[items[0]][1], inTree.children[items[0]])
if len(items) > 1:
# , items[0] , items[1] ,count ,
update_tree(items[1:], inTree.children[items[0]], header_table, count)
def create_tree(data_set, min_sup=1):
"""
FP
:param data_set: dict{ : }
:param min_sup:
:return:
tree FP-tree
headerTable
"""
# step1 ,
header_table = dict()
for trans in data_set:
for item in trans:
header_table[item] = header_table.get(item, 0) + data_set[trans]
print(' header_table', header_table)
#
less_than_min_sup = list(filter(lambda k: header_table[k] < min_sup, header_table.keys()))
print('less than min support', less_than_min_sup)
for k in less_than_min_sup:
del header_table[k]
print(' header table-- ', header_table)
# , None, None
frequent_item_set = set(header_table.keys())
if len(frequent_item_set) == 0:
return None, None
for k in header_table:
header_table[k] = [header_table[k], None]
print(' header_table', header_table)
# , FP-TREE
ret_tree = tree_node('NULL Set', 1, None)
# dic{ : }
for trans, count in data_set.items():
print('trans', trans, 'count', count)
# local_d = dict{ key: }
local_d = dict()
for item in trans:
# min support
if item in frequent_item_set:
print('header_table[item][0]=', header_table[item][0], header_table[item])
local_d[item] = header_table[item][0]
print('local_d', local_d)
# local_d dic
if len(local_d) > 0:
# p = key, value; value ,
# ordered_items key , ,
ordered_items = [v[0] for v in sorted(local_d.items(), key=lambda p: p[1], reverse=True)]
print('ordered_items', ordered_items)
# , orderItems , ,
update_tree(ordered_items, ret_tree, header_table, count)
return ret_tree, header_tableFP tree—頻繁なエントリセットが次にFP treeから関連ルール概念を構築する必要があることがわかった.
条件パターンベース:ヘッドチェーンのある点のプレフィクスパスの組み合わせは、条件モードベース条件パターンベースの値が、エンドノードの値条件FPツリーに依存することである.条件モードベースでデータセット構造のFPツリーを条件FPツリーといい、FPツリーを取得した後に、頻繁なセットごとに、頻繁に掘り起こす必要がある.
具体的なプロセスは、最初に、頻繁なエントリのプレフィクスパスを取得し、次いでプレフィクスパスの条件FPツリーを構築するためのプレフィクスパスとしてプレフィクスパスを新しいデータセットとしてプレフィクスパスを利用し、条件FPツリーに1つの頻繁なエントリのみが含まれるまで、新しい条件FPツリーを構築するために反復することである.
全体として、3つのステップに分解して、FPツリーから頻繁なセット(1)を発掘し、FPツリーから条件付きモードベース(2)を取得し、条件付きモードベースを利用して、条件FPツリーを構築する(3)上記の2つのステップを繰り返し、ツリーが要素項目を含むまで、上記の2つのステップを繰り返す.
def ascend_tree(leaf_node, prefix_path):
"""
ascend_tree name
:param leaf_node: node_tree
:param prefix_path:
:return:
prefix_path ( )
"""
if leaf_node.parent is not None:
prefix_path.append(leaf_node.name)
ascend_tree(leaf_node.parent, prefix_path)
def find_prefix_path(base_pat, tree_node):
"""
step1： FP tree ---->
step2： -----> Apriori
:param base_pat:
:param tree_node: node_tree
:return:
cond_pats base_pat key count
"""
cond_pats = dict()
while tree_node is not None:
prefix_path = list()
# ,
ascend_tree(tree_node, prefix_path)
print('prefix_path', prefix_path)
# 'z'
if len(prefix_path) > 1:
# base_pat key count
# prefix_path[1:] frozenset
print(prefix_path[1:])
cond_pats[frozenset(prefix_path[1:])] = tree_node.count
#
tree_node = tree_node.node_link
return cond_pats
def mine_tree(in_tree, header_table, min_sup, prefix, frequent_list):
"""
mine_tree FP tree
FP tree ----->
:param in_tree: FP TREE
:param header_table: { +{value, tree_node}}
:param min_sup:
:param prefix: prefix newFreqset myhead
:param frequent_list:
:return:
"""
# value key
# key list
# print('sorted header table', sorted(header_table.items()))
big_list = [v[0] for v in sorted(header_table.items(), key=lambda p:p[1][0])]
print()
print('big_list', big_list)
# key
for base_pat in big_list:
# prefix newFreqset myhead
new_frequent_set = prefix.copy()
new_frequent_set.add(base_pat)
print('new_frequent_set= ', new_frequent_set, prefix)
frequent_list.append(new_frequent_set)
print('frequent_list', frequent_list)
cond_pattern_bases = find_prefix_path(base_pat, header_table[base_pat][1])
print('cond_pattern_bases', base_pat, '*'*8, cond_pattern_bases)
# FP tree
cond_tree, cond_head = create_tree(cond_pattern_bases, min_sup)
print('cond_head', cond_head)
if cond_head is not None:
cond_tree.display(1)
print('
')
# cond_head
mine_tree(cond_tree, cond_head, min_sup, new_frequent_set, frequent_list)
print('
')
pass
def main():
data_set = load_data()
init_data_set = create_init_set(data_set)
print(init_data_set)
fp_tree, header_table = create_tree(init_data_set, min_sup=2)
print('header table', header_table)
fp_tree.display()
#
#
print('x --->', find_prefix_path('x', header_table['x'][1]))
print('z --->', find_prefix_path('z', header_table['z'][1]))
print('r --->', find_prefix_path('r', header_table['r'][1]))
#
frequent_list = []
mine_tree(fp_tree, header_table, 3, set([]), frequent_list)
print(frequent_list)
if __name__ == '__main__':
main()