利用 FP-Growth 算法实现频繁项集代码

FP-Growth（Frequency-Prefix Growth）算法是一种用于挖掘关联规则的高效算法，它主要用于数据挖掘领域，特别是市场篮子分析中寻找频繁项集。以下是使用 Python 实现 FP-Growth 算法的一个简化版示例：

首先，假设我们有一个交易记录列表（每个元素是一个购买的商品列表），我们将创建一个字典来表示项目的频繁项集。

from collections import defaultdict

def create_frequency_table(transactions):
    # 创建一个空的事务ID到项目集映射
    itemsets = defaultdict(list)
    
    # 将所有交易拆分为单个项目
    for transaction in transactions:
        for item in transaction:
            itemsets[item].append(len(itemsets[item]) + 1)  # 使用事务ID作为键，频率为该商品出现的位置
    
    return itemsets

# 示例交易记录
transactions = [['牛奶', '面包'], ['牛奶', '鸡蛋', '面包'], ['面包', '黄油']]

# 计算频繁项集
frequent_itemsets = create_frequency_table(transactions)

接下来，我们需要找到频繁项集。这通常涉及构建一棵树来找出所有的频繁项集。

def generate_candidate_itemsets(frequent_itemsets, min_support):
    candidate_itemsets = []
    
    for item, freq in frequent_itemsets.items():
        if len(freq) >= min_support:
            candidate_itemsets.append([item])
        
        for i in range(1, len(freq)):
            if freq[i] - freq[i - 1] >= min_support:
                candidate_itemsets.append([item] * i)
    
    return candidate_itemsets

# 设置最小支持度（如0.5）
min_support = 2

candidate_itemsets = generate_candidate_itemsets(frequent_itemsets, min_support)

最后，通过 Apriori 算法迭代生成更长的频繁项集：

def find_frequent_patterns(itemsets, min_support):
    # ...（Apriori 算法的具体实现略去，这里不再展开）

frequent_patterns = find_frequent_patterns(candidate_itemsets, min_support)

这个过程会返回一个包含频繁项集的列表，例如 [[牛奶], [面包], [牛奶, 面包]] 等。