fp树python代码
时间: 2023-05-25 17:06:29 浏览: 121
以下是一份用Python实现FP树的示例代码:
``` python
class TreeNode:
"""
FP树节点
"""
def __init__(self, name, count, parent):
self.name = name # 节点名称
self.count = count # 出现次数
self.parent = parent # 父节点
self.children = {} # 子节点
def inc(self, count):
self.count += count
def create_fp_tree(data_set, min_support=1):
"""
构建FP树
"""
header_table = {}
# 第一次遍历,统计各个元素项出现的频度
for transaction in data_set:
for item in transaction:
header_table[item] = header_table.get(item, 0) + data_set[transaction]
# 移除不满足最小支持度的元素项
for k in list(header_table.keys()):
if header_table[k] < min_support:
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]
# 第二次遍历,构建FP树
root = TreeNode('NULL', 0, None)
for transaction, count in data_set.items():
# 按照支持度从高到低排序所有元素项
ordered_items = [item for item in transaction if item in freq_item_set]
ordered_items.sort(key=lambda item: header_table[item][0], reverse=True)
# 用排好序的元素项序列填充FP树
curr_node = root
for item in ordered_items:
curr_node.children[item] = curr_node.children.get(item, TreeNode(item, 0, curr_node))
curr_node = curr_node.children[item]
curr_node.inc(count)
# 更新头指针表
if header_table[item][1] is None:
header_table[item][1] = curr_node
else:
update_header(header_table[item][1], curr_node)
return root, header_table
def update_header(node_to_test, target_node):
"""
更新指向相同类型的可以连接在一起的节点
"""
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 ascend_tree(leaf_node, 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_path, tree_node):
"""
发现以给定节点结尾的所有路径
"""
cond_pats = {}
while tree_node is not None:
prefix_path = []
ascend_tree(tree_node, prefix_path)
if len(prefix_path) > 1:
cond_pats[frozenset(prefix_path[1:])] = tree_node.count
tree_node = tree_node.node_link
return cond_pats
def mine_fp_tree(header_table, min_support, prefix, freq_item_list):
# 按照频度从小到大排序头指针表
items = list(header_table.keys())
items.sort(key=lambda item: header_table[item][0])
# 逆序遍历每个元素项
for item in items[::-1]:
new_freq_set = prefix.copy()
new_freq_set.add(item)
freq_item_list.append(new_freq_set)
cond_patt_bases = find_prefix_path(item, header_table[item][1])
# 递归构建条件模式基,生成条件模式树
cond_tree, cond_header_table = create_fp_tree(cond_patt_bases, min_support)
if cond_header_table is not None:
# 递归挖掘条件模式树
mine_fp_tree(cond_header_table, min_support, new_freq_set, freq_item_list)
def load_data():
"""
加载示例数据集
"""
data_set = {'bread': 2, 'milk': 2, 'diaper': 2, 'beer': 1, 'egg': 1}
return data_set
if __name__ == '__main__':
data_set = load_data()
root, header_table = create_fp_tree(data_set, min_support=2)
freq_item_list = []
mine_fp_tree(header_table, 2, set([]), freq_item_list)
for freq_item in freq_item_list:
print(freq_item)
```
该代码实现了FP树的构建以及基于FP树的频繁项集挖掘。代码实现过程中,需要注意的点有:
- FP树节点的定义:每个节点除了保存节点名称和出现次数之外,还需要保存父节点和子节点;FP树的根节点一般指定名称为'NULL',出现次数为0。
- 头指针表的使用:头指针表是指向同一个元素项的所有节点的指针列表,用于加速对同一类型元素项出现的查找。
- 构建FP树的过程:需要对数据集进行两次遍历,第一次遍历统计各个元素项的出现频度,第二次遍历用于构建FP树。
- 从叶节点向上迭代遍历整棵树的过程。
- 构建条件模式基和条件模式树,并在条件模式树中递归挖掘频繁项集的过程。
阅读全文