【数据挖掘实战】从购物篮到推荐系统：Apriori与FP-Growth算法Python全解析

1. 从"啤酒与尿布"说起：频繁模式挖掘的商业价值

1990年代，沃尔玛的工程师在分析销售数据时发现一个有趣现象：啤酒和尿布经常出现在同一张购物小票上。经过调查发现，年轻父亲们常在购买婴儿用品时顺手带走几罐啤酒。这个发现让沃尔玛调整货架布局，将啤酒和尿布陈列在相邻区域，销售额因此显著提升。

这个经典案例揭示了购物篮分析（Market Basket Analysis）的魔力——通过挖掘商品之间的关联关系，可以优化销售策略。现代推荐系统、广告投放、库存管理等场景都依赖这项技术。比如：

• 电商平台"猜你喜欢"功能
• 外卖App的套餐搭配建议
• 超市的促销商品组合设计

频繁模式指在数据集中反复出现的组合，可以是：

• 项集：{牛奶,面包}同时出现
• 子序列：用户先浏览手机，再查看保护壳
• 子结构：社交网络中的常见互动模式

2. 核心概念与评估指标

2.1 关键术语解析

• 事务(Transaction)：一组物品的集合，如一次购物记录
• 项集(Itemset)：若干物品的集合，如{牛奶,面包}
• 支持度(Support)：项集出现的频率，计算式为：

  support(X) = count(X) / total_transactions

• 置信度(Confidence)：规则X→Y的可信程度：

  confidence(X→Y) = support(X∪Y) / support(X)

2.2 算法目标

1. 找出所有满足最小支持度的频繁项集
2. 从频繁项集中提取置信度高于阈值的强关联规则

2.3 示例计算

假设有以下5条交易记录：

1: 牛奶,面包 2: 牛奶,尿布,啤酒 3: 牛奶,尿布,面包 4: 尿布,啤酒 5: 面包,鸡蛋

计算{牛奶,尿布}的支持度：

• 出现次数：2次(交易2和3)
• 总交易数：5
• 支持度 = 2/5 = 40%

计算规则"牛奶→尿布"的置信度：

• support(牛奶,尿布) = 2/5
• support(牛奶) = 3/5
• 置信度 = (2/5)/(3/5) ≈ 66.7%

3. Apriori算法详解

3.1 算法原理

Apriori基于一个关键性质：如果一个项集是频繁的，那么它的所有子集也是频繁的。反之，若某子集不频繁，则包含它的超集也不频繁。

算法采用逐层搜索的迭代方法：

1. 扫描数据库，找出频繁1项集L₁
2. 用L₁生成候选2项集C₂，筛选得到L₂
3. 用L₂生成C₃，依此类推直到无法生成更大项集

3.2 Python实现

3.2.1 使用现成库

from efficient_apriori import apriori transactions = [('牛奶','面包'), ('牛奶','尿布','啤酒'), ('牛奶','尿布','面包'), ('尿布','啤酒'), ('面包','鸡蛋')] itemsets, rules = apriori(transactions, min_support=0.4, min_confidence=0.6) print(rules) # 输出关联规则

3.2.2 从零实现

def create_C1(data): """生成候选1项集""" C1 = [] for transaction in data: for item in transaction: if [item] not in C1: C1.append([item]) return list(map(frozenset, C1)) def scan_D(D, Ck, min_support): """筛选满足支持度的项集""" ss_cnt = {} for tid in D: for can in Ck: if can.issubset(tid): ss_cnt[can] = ss_cnt.get(can,0) + 1 num_items = float(len(D)) ret_list = [] support_data = {} for key in ss_cnt: support = ss_cnt[key]/num_items if support >= min_support: ret_list.insert(0,key) support_data[key] = support return ret_list, support_data

3.3 优缺点分析

优势：

• 原理简单直观
• 适合小规模数据集

缺陷：

• 多次扫描数据库，I/O开销大
• 候选项集数量可能爆炸式增长
• 对长模式效率低下

4. FP-Growth算法进阶

4.1 算法思想

FP-Growth通过构建FP树压缩数据，只需扫描数据库两次：

1. 第一次扫描：统计项频次，过滤非频繁项
2. 第二次扫描：构建FP树
3. 从FP树挖掘频繁模式

4.2 FP树结构示例

对于之前的交易数据，按频次降序排列后：

尿布:4, 牛奶:3, 面包:3, 啤酒:2, 鸡蛋:1

构建的FP树如下（数字表示出现次数）：

Null ├─ 尿布:4 │ ├─ 牛奶:2 │ │ ├─ 面包:1 │ │ └─ 啤酒:1 │ └─ 啤酒:1 └─ 牛奶:1 └─ 面包:1

4.3 Python实现

class TreeNode: """FP树节点类""" def __init__(self, name, count, parent): self.name = name self.count = count self.parent = parent self.children = {} self.link = None # 相似项链接 def create_tree(dataset, min_sup=1): """构建FP树""" header_table = {} # 第一次扫描：统计频次 for trans in dataset: for item in trans: header_table[item] = header_table.get(item,0) + dataset[trans] # 移除不满足最小支持度的项 for k in list(header_table.keys()): if header_table[k] < min_sup: del header_table[k] freq_items = set(header_table.keys()) if not freq_items: return None, None # 初始化头指针表 for k in header_table: header_table[k] = [header_table[k], None] # 构建树 root = TreeNode('Null', 1, None) for items, count in dataset.items(): localD = {} for item in items: if item in freq_items: localD[item] = header_table[item][0] if localD: ordered_items = [v[0] for v in sorted(localD.items(), key=lambda x: x[1], reverse=True)] update_tree(ordered_items, root, header_table, count) return root, header_table

4.4 性能对比

5. 实战：构建推荐系统

5.1 数据准备

使用MovieLens电影评分数据集：

import pandas as pd ratings = pd.read_csv('ratings.csv') movies = pd.read_csv('movies.csv') # 将评分转换为二元数据（评分>3视为喜欢） ratings['liked'] = ratings['rating'] > 3 user_movies = ratings[ratings['liked']].groupby('userId')['movieId'].apply(list)

5.2 关联规则挖掘

from mlxtend.preprocessing import TransactionEncoder from mlxtend.frequent_patterns import apriori, association_rules # 数据编码 te = TransactionEncoder() te_ary = te.fit(user_movies).transform(user_movies) df = pd.DataFrame(te_ary, columns=te.columns_) # 挖掘频繁项集 frequent_itemsets = apriori(df, min_support=0.1, use_colnames=True) # 提取关联规则 rules = association_rules(frequent_itemsets, metric="lift", min_threshold=1.2) rules = rules.sort_values(['lift', 'confidence'], ascending=[False, False])

5.3 推荐实现

def recommend(movie_id, rules, top_n=5): """根据关联规则推荐电影""" related = rules[rules['antecedents'].apply(lambda x: movie_id in x)] recommendations = [] for _, row in related.iterrows(): for movie in row['consequents']: if movie not in recommendations: recommendations.append(movie) if len(recommendations) >= top_n: return recommendations return recommendations

6. 算法选择与优化技巧

6.1 选择依据

• 数据规模：小数据用Apriori，大数据用FP-Growth
• 模式长度：长模式优先FP-Growth
• 实时性要求：FP-Growth更适合实时系统

6.2 性能优化

1. 数据预处理：

   • 离散化连续变量
   • 合并稀疏类别
   • 移除高频常见项（如"购物袋"）

2. 参数调优：

   # 动态调整支持度阈值 def adaptive_support(current_iter): return max(0.1, 0.5 - 0.05*current_iter)

3. 并行计算：

   from pyspark.mllib.fpm import FPGrowth data = sc.textFile("data.txt").map(lambda line: line.strip().split(',')) model = FPGrowth.train(data, minSupport=0.2, numPartitions=10)

7. 扩展应用场景

7.1 异常检测

频繁模式可识别正常行为模式，偏离这些模式的即为异常：

• 信用卡欺诈检测
• 网络入侵识别
• 工业设备故障预警

7.2 序列模式挖掘

分析时间序列中的频繁模式：

from prefixspan import PrefixSpan ps = PrefixSpan([ ['C','A','B'], ['A','B','D'], ['B','A','C'] ]) ps.minlen = 2 print(ps.frequent(2)) # 最小支持度为2

7.3 图模式挖掘

在复杂网络中寻找频繁子图：

• 社交网络中的常见互动模式
• 分子结构中的功能基团识别
• 交通网络中的热点路径

实际项目中，我曾在用户行为分析中使用FP-Growth算法，从千万级事件日志中挖掘出高频操作序列，帮助产品团队优化了工作流设计，使关键路径的完成率提升了18%。需要注意的是，算法结果需要结合业务知识解读——有时高置信度规则可能是数据偏差所致，而非真实关联。