使用python实现FP-Growth算法

简介: 使用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)
```

 

这是一个简单的FP-Growth算法的Python实现示例。您可以根据需要进行调整和扩展。这段代码可以帮助您理解FP-Growth算法的基本原理和实现方式。

相关文章
|
5天前
|
算法 搜索推荐 C语言
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天前
|
存储 算法 Serverless
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