从超市购物车到推荐系统：深入浅出图解FP-Growth算法（附Python实战）

从超市购物车到推荐系统：深入浅出图解FP-Growth算法（附Python实战）

当你推着购物车在超市里闲逛时，是否想过货架上那些看似随意的商品摆放背后，其实隐藏着精密的数学算法？那些"买了啤酒的顾客也会买尿布"的经典案例，正是关联规则挖掘技术的杰作。今天，我们要探讨的FP-Growth算法，就是让计算机从海量购物数据中自动发现这些隐藏规律的神兵利器。

与传统的Apriori算法需要反复扫描数据库不同，FP-Growth通过构建一种称为FP-Tree的紧凑数据结构，将效率提升了一个数量级。这种算法不仅适用于零售业的市场篮子分析，还能应用于推荐系统、医疗诊断、网络安全等众多领域。接下来，我们将用图解方式拆解算法原理，并通过Python实战演示如何发现那些令人惊讶的商品组合规律。

1. 为什么需要FP-Growth算法

在数据挖掘领域，关联规则学习是一种发现变量间有趣关系的方法。1994年提出的Apriori算法虽然开创了先河，但其性能瓶颈也显而易见：它需要多次扫描整个数据库，并且会产生大量的候选集。对于一个包含n种商品的数据集，Apriori可能需要生成2^n-1个候选集，这在商品种类较多的场景下几乎是灾难性的。

FP-Growth算法在2000年由Jiawei Han等人提出，其核心创新在于：

• 两次扫描原则：仅需扫描数据库两次，极大减少I/O开销
• FP-Tree结构：将原始数据压缩存储在一种前缀树结构中
• 无候选集生成：直接通过树结构挖掘频繁模式，避免产生大量中间结果

实际测试表明，在处理相同数据集时，FP-Growth的速度通常比Apriori快一个数量级以上。下表展示了两种算法在典型零售数据集上的性能对比：

提示：FP-Growth特别适合商品种类多但单个交易物品少的场景，如便利店销售数据分析

2. FP-Tree构建全图解

理解FP-Growth算法的关键在于掌握FP-Tree的构建过程。让我们通过一个具体例子来拆解这个精妙的数据结构。

假设我们有如下简化版的超市交易数据（每条记录代表一个购物篮）：

T1: 牛奶, 面包, 啤酒 T2: 牛奶, 尿布, 啤酒, 鸡蛋 T3: 面包, 尿布, 啤酒 T4: 牛奶, 面包, 尿布 T5: 牛奶, 尿布, 鸡蛋

2.1 第一次扫描：统计频率并排序

首先，算法扫描整个数据库，统计每个商品的出现频率：

接着，我们按频率降序重新排列每个交易中的商品：

T1: 牛奶, 啤酒, 面包 T2: 牛奶, 尿布, 啤酒, 鸡蛋 T3: 尿布, 啤酒, 面包 T4: 牛奶, 尿布, 面包 T5: 牛奶, 尿布, 鸡蛋

2.2 第二次扫描：构建FP-Tree

现在开始构建FP-Tree。我们从空根节点(null)开始，按顺序插入每条交易：

1. 插入T1: 牛奶→啤酒→面包

   • 创建路径：null→牛奶(1)→啤酒(1)→面包(1)

2. 插入T2: 牛奶→尿布→啤酒→鸡蛋

   • 共用牛奶前缀，牛奶计数+1=2
   • 从牛奶开始新分支：牛奶(2)→尿布(1)→啤酒(1)→鸡蛋(1)

3. 插入T3: 尿布→啤酒→面包

   • 尿布没有直接子节点，从根创建新路径
   • null→尿布(1)→啤酒(1)→面包(1)

4. 插入T4: 牛奶→尿布→面包

   • 共用牛奶前缀，牛奶计数+1=3
   • 从牛奶开始，尿布是现有子节点，尿布计数+1=2
   • 新分支：牛奶(3)→尿布(2)→面包(1)

5. 插入T5: 牛奶→尿布→鸡蛋

   • 共用牛奶→尿布前缀
   • 牛奶计数+1=4，尿布计数+1=3
   • 新分支：牛奶(4)→尿布(3)→鸡蛋(1)

最终形成的FP-Tree如下图所示（括号内数字为节点计数）：

null ├── 牛奶(4) │ ├── 尿布(3) │ │ ├── 啤酒(1) │ │ │ └── 鸡蛋(1) │ │ ├── 面包(1) │ │ └── 鸡蛋(1) │ └── 啤酒(1) │ └── 面包(1) └── 尿布(1) └── 啤酒(1) └── 面包(1)

同时，我们维护一个头表(head table)，将相同商品的所有节点链接起来：

这种紧凑的存储结构使得后续的频繁模式挖掘变得非常高效。

3. 从FP-Tree挖掘频繁项集

FP-Tree构建完成后，我们采用分而治之的策略挖掘频繁项集。具体过程是从频率最低的商品开始（鸡蛋），沿着头表向上逐步构建条件模式基。

3.1 挖掘以鸡蛋结尾的频繁项集

1. 从鸡蛋的头表入口出发，找到所有包含鸡蛋的路径：

   • 路径1：牛奶→尿布→啤酒→鸡蛋 (计数1)
   • 路径2：牛奶→尿布→鸡蛋 (计数1)

2. 提取这些路径的前缀（去掉鸡蛋），得到条件模式基：

   • {牛奶,尿布,啤酒}:1
   • {牛奶,尿布}:1

3. 构建鸡蛋的条件FP-Tree：

   • 统计条件模式基中的商品频率：
     • 牛奶:2, 尿布:2, 啤酒:1
   • 按频率降序排列：牛奶, 尿布
   • 构建树结构：

     null ├── 牛奶(2) │ └── 尿布(2)

4. 从条件FP-Tree生成频繁项集：

   • {鸡蛋} (支持度2)
   • {牛奶,鸡蛋} (支持度2)
   • {尿布,鸡蛋} (支持度2)
   • {牛奶,尿布,鸡蛋} (支持度2)

3.2 挖掘以面包结尾的频繁项集

同样的方法应用于面包：

1. 包含面包的路径：

   • 牛奶→啤酒→面包 (1)
   • 牛奶→尿布→面包 (1)
   • 尿布→啤酒→面包 (1)

2. 条件模式基：

   • {牛奶,啤酒}:1
   • {牛奶,尿布}:1
   • {尿布,啤酒}:1

3. 面包的条件FP-Tree：

   • 频率统计：牛奶:2, 尿布:2, 啤酒:2
   • 树结构为空（所有商品支持度相同，无法形成树）

4. 频繁项集：

   • {面包} (3)
   • {牛奶,面包} (2)
   • {尿布,面包} (2)
   • {啤酒,面包} (2)

3.3 递归挖掘所有频繁项集

按照商品频率升序（鸡蛋→面包→啤酒→尿布→牛奶），重复上述过程，最终可以得到所有满足最小支持度的频繁项集。例如，当最小支持度为3时，部分频繁项集包括：

• {牛奶} (4)
• {尿布} (4)
• {啤酒} (3)
• {面包} (3)
• {牛奶,尿布} (3)
• ...

这种挖掘方式避免了Apriori算法产生大量候选集的问题，直接通过树结构提取频繁模式，效率显著提升。

4. Python实战：用FP-Growth发现商品关联

现在让我们用Python的mlxtend库来实现FP-Growth算法，分析一个真实的零售数据集。

4.1 准备环境和数据

首先安装必要库：

pip install mlxtend pandas

我们使用UCI Machine Learning Repository中的Online Retail数据集：

import pandas as pd from mlxtend.preprocessing import TransactionEncoder from mlxtend.frequent_patterns import fpgrowth # 加载数据 df = pd.read_csv('OnlineRetail.csv', encoding='ISO-8859-1') # 预处理：按InvoiceNo分组，获取每笔交易的商品列表 transactions = df.groupby('InvoiceNo')['Description'].apply(list).values.tolist() # 转换为one-hot编码格式 te = TransactionEncoder() te_ary = te.fit(transactions).transform(transactions) df_encoded = pd.DataFrame(te_ary, columns=te.columns_)

4.2 运行FP-Growth算法

# 挖掘频繁项集（最小支持度2%） frequent_itemsets = fpgrowth(df_encoded, min_support=0.02, use_colnames=True) # 按支持度降序排列 frequent_itemsets = frequent_itemsets.sort_values('support', ascending=False) print(frequent_itemsets.head(10))

输出示例：

4.3 生成关联规则

从频繁项集中提取有意义的关联规则：

from mlxtend.frequent_patterns import association_rules # 生成关联规则（最小提升度1.5） rules = association_rules(frequent_itemsets, metric="lift", min_threshold=1.5) # 按置信度降序排列 rules = rules.sort_values('confidence', ascending=False) print(rules[['antecedents', 'consequents', 'support', 'confidence', 'lift']].head())

输出示例：

这些规则揭示了有趣的商品关联，例如购买"午餐袋红色复古点"的顾客有72.1%的概率也会购买"大号袋红色复古点"，这种组合的销售可能性是随机组合的7.83倍。零售商可以利用这些洞察优化商品摆放位置或设计组合促销方案。

5. FP-Growth在推荐系统中的应用

FP-Growth算法在推荐系统中有着广泛的应用场景。与协同过滤等传统方法相比，基于关联规则的推荐有以下优势：

• 可解释性强：能够明确说明"因为买了A，所以推荐B"的逻辑
• 冷启动友好：不需要用户历史评分数据，仅基于交易记录
• 发现意外关联：能捕捉非直观但实际存在的商品关系

5.1 实现简单的推荐引擎

基于前面挖掘的关联规则，我们可以构建一个简单的推荐系统：

def recommend_products(rules, current_items, top_n=5): # 筛选出当前商品作为前件的规则 relevant_rules = rules[rules['antecedents'].apply(lambda x: set(x).issubset(current_items))] # 按提升度降序排列 relevant_rules = relevant_rules.sort_values('lift', ascending=False) # 提取推荐商品（去除已购买商品） recommendations = [] for _, rule in relevant_rules.head(top_n).iterrows(): for item in rule['consequents']: if item not in current_items: recommendations.append((item, rule['lift'])) return sorted(recommendations, key=lambda x: -x[1])[:top_n] # 示例：用户当前购物车中有"LUNCH BAG RED RETROSPOT" current_cart = {'LUNCH BAG RED RETROSPOT'} print(recommend_products(rules, current_cart))

输出可能类似于：

[('JUMBO BAG RED RETROSPOT', 7.83), ('SET OF 3 CAKE TINS PANTRY DESIGN', 3.45), ...]

5.2 优化策略与挑战

在实际应用中，我们还需要考虑以下优化策略：

• 时间衰减因子：给近期交易赋予更高权重
• 商品分类层级：在不同粒度层级上挖掘规则
• 排除明显规则：如"充电器→手机"这类常识性关联
• 实时更新机制：定期重新挖掘规则以适应销售趋势变化

主要挑战包括：

• 处理大规模数据时的内存消耗
• 动态调整最小支持度阈值
• 解释和评估非对称关联规则
• 与其它推荐算法的融合

在真实项目中，FP-Growth通常作为推荐系统的一个组件，与协同过滤、内容推荐等方法结合使用，形成混合推荐策略。