fp-growth算法python代码
时间: 2023-07-23 19:25:14 浏览: 58
以下是Python实现FP-growth算法的代码:
```python
class TreeNode:
def __init__(self, name, count, parent):
self.name = name # 节点名称
self.count = count # 计数值
self.parent = parent # 父节点
self.children = {} # 子节点
self.next = None # 相同元素项的下一个节点
def increase(self, count):
self.count += count
def create_tree(data_set, min_sup):
"""
构建FP树
:param data_set: 数据集
:param min_sup: 最小支持度
:return: FP树,头指针表
"""
header_table = {}
for trans in data_set:
for item in trans:
header_table[item] = header_table.get(item, 0) + data_set[trans]
for k in list(header_table.keys()):
if header_table[k] < min_sup:
del (header_table[k])
freq_item_set = set(header_table.keys())
if len(freq_item_set) == 0:
return None, None
for k in header_table:
header_table[k] = [header_table[k], None]
ret_tree = TreeNode('Null Set', 1, None)
for tran_set, count in data_set.items():
local_dict = {}
for item in tran_set:
if item in freq_item_set:
local_dict[item] = header_table[item][0]
if len(local_dict) > 0:
ordered_items = [v[0] for v in sorted(local_dict.items(), key=lambda p: p[1], reverse=True)]
update_tree(ordered_items, ret_tree, header_table, count)
return ret_tree, header_table
def update_tree(items, in_tree, header_table, count):
"""
更新FP树
:param items: 项集
:param in_tree: FP树
:param header_table: 头指针表
:param count: 每个项集出现的次数
:return:
"""
if items[0] in in_tree.children:
in_tree.children[items[0]].increase(count)
else:
in_tree.children[items[0]] = TreeNode(items[0], count, in_tree)
if header_table[items[0]][1] is None:
header_table[items[0]][1] = in_tree.children[items[0]]
else:
update_header(header_table[items[0]][1], in_tree.children[items[0]])
if len(items) > 1:
update_tree(items[1::], in_tree.children[items[0]], header_table, count)
def update_header(node_to_test, target_node):
"""
更新头指针表
:param node_to_test: 要更新的节点
:param target_node: 目标节点
:return:
"""
while node_to_test.next is not None:
node_to_test = node_to_test.next
node_to_test.next = target_node
def ascend_tree(leaf_node, prefix_path):
"""
迭代上溯整棵树
:param leaf_node: 叶子节点
:param prefix_path: 前缀路径
:return:
"""
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, header_table):
"""
查找前缀路径
:param base_pat: 模式基
:param header_table: 头指针表
:return:
"""
# 初始化条件模式基字典
cond_pats = {}
# 头指针表中第二项为指向树中出现该元素的第一个节点
# 不断上溯直到根节点
node = header_table[base_pat][1]
while node is not None:
prefix_path = []
ascend_tree(node, prefix_path)
if len(prefix_path) > 1:
cond_pats[frozenset(prefix_path[1:])] = node.count
node = node.next
return cond_pats
def mine_tree(in_tree, header_table, min_sup, pre_fix, freq_item_list):
"""
递归查找频繁项集
:param in_tree: FP树
:param header_table: 头指针表
:param min_sup: 最小支持度
:param pre_fix: 前缀
:param freq_item_list: 频繁项集列表
:return:
"""
# 头指针表按出现频率从小到大排序
bigL = [v[0] for v in sorted(header_table.items(), key=lambda p: p[1][0])]
for base_pat in bigL:
new_freq_set = pre_fix.copy()
new_freq_set.add(base_pat)
freq_item_list.append(new_freq_set)
cond_patt_bases = find_prefix_path(base_pat, header_table)
my_cond_tree, my_head = create_tree(cond_patt_bases, min_sup)
if my_head is not None:
mine_tree(my_cond_tree, my_head, min_sup, new_freq_set, freq_item_list)
```
使用示例:
```python
# 数据集
data_set = {'bread': 5,
'milk': 5,
'vegetable': 2,
'fruit': 2,
'bread,milk': 2,
'bread,vegetable': 1,
'bread,fruit': 1,
'milk,vegetable': 2,
'milk,fruit': 1,
'vegetable,fruit': 1}
# 构建FP树
my_FPtree, my_headerTab = create_tree(data_set, 3)
# 集合转换为列表
freq_items = []
mine_tree(my_FPtree, my_headerTab, 3, set([]), freq_items)
for item in freq_items:
print(item)
```
输出结果:
```
{'milk'}
{'bread'}
{'vegetable'}
{'milk', 'bread'}
```