使用python实现FP-Growth算法

FP-Growth（Frequent Pattern Growth）是一种用于发现频繁项集的数据挖掘算法，通常用于关联规则挖掘。下面是一个简单的Python实现FP-Growth算法的示例：

python
from collections import defaultdict

class FPNode:
def __init__(self, item, count, parent):
self.item = item
self.count = count
self.parent = parent
self.children = {}
self.next = None

def increment_count(self, count):
self.count += count

def build_tree(transactions, min_support):
header_table = defaultdict(int)
for transaction in transactions:
for item in transaction:
header_table[item] += 1
header_table = {k: v for k, v in header_table.items() if v >= min_support}

if len(header_table) == 0:
return None, None

root = FPNode(None, 0, None)
for transaction in transactions:
transaction = [item for item in transaction if item in header_table]
transaction.sort(key=lambda item: header_table[item], reverse=True)
current_node = root
for item in transaction:
if item in current_node.children:
current_node.children[item].increment_count(1)
else:
new_node = FPNode(item, 1, current_node)
current_node.children[item] = new_node
if header_table[item] == 1:
update_fp_tree(new_node, header_table)
current_node = current_node.children[item]

return root, header_table

def update_fp_tree(node, header_table):
while node.next is not None:
node = node.next
node.next = header_table[node.item]

def find_frequent_patterns(tree, header_table, prefix, frequent_patterns, min_support):
for item, count in header_table.items():
new_prefix = prefix.copy()
new_prefix.add(item)
frequent_patterns.add(frozenset(new_prefix))
conditional_patterns = get_conditional_patterns(item, header_table)
conditional_tree, conditional_header = build_tree(conditional_patterns, min_support)
if conditional_tree is not None:
find_frequent_patterns(conditional_tree, conditional_header, new_prefix, frequent_patterns, min_support)

def get_conditional_patterns(item, header_table):
conditional_patterns = []
node = header_table[item]
while node is not None:
prefix_path = []
current_node = node.parent
while current_node.item is not None:
prefix_path.append(current_node.item)
current_node = current_node.parent
if len(prefix_path) > 0:
conditional_patterns.append(prefix_path)
node = node.next
return conditional_patterns

def fp_growth(transactions, min_support):
tree, header_table = build_tree(transactions, min_support)
frequent_patterns = set()
find_frequent_patterns(tree, header_table, set(), frequent_patterns, min_support)
return frequent_patterns

# 示例数据
transactions = [
['A', 'B', 'D'],
['B', 'C', 'E'],
['A', 'B', 'D', 'E'],
['A', 'B', 'C', 'E']
]

min_support = 2

frequent_patterns = fp_growth(transactions, min_support)
for pattern in frequent_patterns:
print(pattern)


|
5天前
|

Python实现数据结构与算法
【5月更文挑战第13天】学习数据结构与算法能提升编程能力，解决复杂问题，助你面试成功。从选择资源（如《算法导论》、Coursera课程、LeetCode）到实践编码，逐步学习基本概念，通过Python实现栈、队列和快速排序。不断练习、理解原理，探索高级数据结构与算法，参与开源项目和算法竞赛，持续反思与实践，以提升技术能力。
6 0
|
5天前
|

Python 数据结构和算法实用指南（四）（4）
Python 数据结构和算法实用指南（四）
10 1
|
5天前
|

Python 数据结构和算法实用指南（四）（3）
Python 数据结构和算法实用指南（四）
15 1
|
5天前
|

Python 数据结构和算法实用指南（四）（2）
Python 数据结构和算法实用指南（四）
10 0
|
5天前
|

Python 数据结构和算法实用指南（四）（1）
Python 数据结构和算法实用指南（四）
14 0
|
5天前
|

Python 数据结构和算法实用指南（三）（4）
Python 数据结构和算法实用指南（三）
10 1
|
5天前
|

Python 数据结构和算法实用指南（三）（3）
Python 数据结构和算法实用指南（三）
10 1
|
5天前
|

Python 数据结构和算法实用指南（三）（2）
Python 数据结构和算法实用指南（三）
10 1
|
5天前
|

Python 数据结构和算法实用指南（三）（1）
Python 数据结构和算法实用指南（三）
13 1
|
5天前
|

Python 数据结构和算法实用指南（二）（4）
Python 数据结构和算法实用指南（二）
11 2