FP-growth（Frequent Pattern Growth）算法是一种高效挖掘频繁项集的算法，它避免了Apriori算法中繁重的候选集生成和多次数据库扫描的问题。

🔍 一、FP-growth 算法基本思想

FP-growth 算法通过构建一棵 频繁模式树（FP-Tree） 来压缩数据库中的交易数据，并通过递归地挖掘条件模式基来高效地发现频繁项集。

🧩 二、FP-growth 算法步骤

第一步：构建 FP-Tree

1. 扫描事务数据库，统计每个项的支持度。

2. 去除不满足最小支持度的项，对剩下的项按支持度从大到小排序。

3. 第二次扫描数据库，将事务按上述顺序插入 FP-Tree 中，合并公共前缀路径，并在树中记录计数。

第二步：递归挖掘频繁项集

1. 从FP-Tree中选择一个频繁项，找出它的所有“条件模式基”（即含它的路径前缀集合）。

2. 构建该频繁项的条件FP-Tree，即基于其条件模式基建立的子树。

3. 在条件FP-Tree上递归挖掘频繁项集。

4. 将频繁项组合生成所有可能的频繁项集。

🎯 三、与 Apriori 的比较

以下是一个简单的 FP-growth 算法案例（使用 Python 和 mlxtend 库实现）：

🌽 案例背景：购物篮分析

假设有一个简化的交易数据集：

✅ 数据预处理 & FP-growth 实现

import pandas as pd
from mlxtend.preprocessing import TransactionEncoder
from mlxtend.frequent_patterns import fpgrowth, association_rules

# 步骤1：原始交易数据
dataset = [
    ['牛奶', '面包', '饼干'],
    ['牛奶', '尿布', '啤酒'],
    ['面包', '黄油'],
    ['牛奶', '面包', '尿布'],
    ['面包', '啤酒']
]

# 步骤2：转换成布尔型数据表
te = TransactionEncoder()
te_ary = te.fit(dataset).transform(dataset)
df = pd.DataFrame(te_ary, columns=te.columns_)

# 步骤3：应用 FP-growth 算法
frequent_itemsets = fpgrowth(df, min_support=0.4, use_colnames=True)
print("频繁项集：")
print(frequent_itemsets)

# 步骤4：生成关联规则
rules = association_rules(frequent_itemsets, metric="confidence", min_threshold=0.6)
print("\n关联规则：")
print(rules[['antecedents', 'consequents', 'support', 'confidence', 'lift']])

📌 输出示例（部分）

频繁项集：
     support        itemsets
0       0.6           [面包]
1       0.6           [牛奶]
2       0.4           [尿布]
3       0.4         [牛奶, 面包]
4       0.4         [牛奶, 尿布]

关联规则：
  antecedents consequents  support  confidence  lift
0      [牛奶]      [面包]      0.4        0.666     1.11
1      [面包]      [牛奶]      0.4        0.666     1.11
2      [牛奶]      [尿布]      0.4        0.666     1.66