从超市购物车到推荐系统：深入浅出图解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快一个数量级以上。下表展示了两种算法在典型零售数据集上的性能对比指标Apriori算法FP-Growth算法扫描次数O(频繁项集长度)2次候选集指数级增长无内存使用高中等适用规模万级商品十万级商品提示FP-Growth特别适合商品种类多但单个交易物品少的场景如便利店销售数据分析2. FP-Tree构建全图解理解FP-Growth算法的关键在于掌握FP-Tree的构建过程。让我们通过一个具体例子来拆解这个精妙的数据结构。假设我们有如下简化版的超市交易数据每条记录代表一个购物篮T1: 牛奶, 面包, 啤酒 T2: 牛奶, 尿布, 啤酒, 鸡蛋 T3: 面包, 尿布, 啤酒 T4: 牛奶, 面包, 尿布 T5: 牛奶, 尿布, 鸡蛋2.1 第一次扫描统计频率并排序首先算法扫描整个数据库统计每个商品的出现频率商品频率牛奶4尿布4啤酒3面包3鸡蛋2接着我们按频率降序重新排列每个交易中的商品T1: 牛奶, 啤酒, 面包 T2: 牛奶, 尿布, 啤酒, 鸡蛋 T3: 尿布, 啤酒, 面包 T4: 牛奶, 尿布, 面包 T5: 牛奶, 尿布, 鸡蛋2.2 第二次扫描构建FP-Tree现在开始构建FP-Tree。我们从空根节点(null)开始按顺序插入每条交易插入T1: 牛奶→啤酒→面包创建路径null→牛奶(1)→啤酒(1)→面包(1)插入T2: 牛奶→尿布→啤酒→鸡蛋共用牛奶前缀牛奶计数12从牛奶开始新分支牛奶(2)→尿布(1)→啤酒(1)→鸡蛋(1)插入T3: 尿布→啤酒→面包尿布没有直接子节点从根创建新路径null→尿布(1)→啤酒(1)→面包(1)插入T4: 牛奶→尿布→面包共用牛奶前缀牛奶计数13从牛奶开始尿布是现有子节点尿布计数12新分支牛奶(3)→尿布(2)→面包(1)插入T5: 牛奶→尿布→鸡蛋共用牛奶→尿布前缀牛奶计数14尿布计数13新分支牛奶(4)→尿布(3)→鸡蛋(1)最终形成的FP-Tree如下图所示括号内数字为节点计数null ├── 牛奶(4) │ ├── 尿布(3) │ │ ├── 啤酒(1) │ │ │ └── 鸡蛋(1) │ │ ├── 面包(1) │ │ └── 鸡蛋(1) │ └── 啤酒(1) │ └── 面包(1) └── 尿布(1) └── 啤酒(1) └── 面包(1)同时我们维护一个头表(head table)将相同商品的所有节点链接起来商品频率节点链牛奶4牛奶节点1→...尿布4尿布节点1→...啤酒3啤酒节点1→...面包3面包节点1→...鸡蛋2鸡蛋节点1→...这种紧凑的存储结构使得后续的频繁模式挖掘变得非常高效。3. 从FP-Tree挖掘频繁项集FP-Tree构建完成后我们采用分而治之的策略挖掘频繁项集。具体过程是从频率最低的商品开始鸡蛋沿着头表向上逐步构建条件模式基。3.1 挖掘以鸡蛋结尾的频繁项集从鸡蛋的头表入口出发找到所有包含鸡蛋的路径路径1牛奶→尿布→啤酒→鸡蛋 (计数1)路径2牛奶→尿布→鸡蛋 (计数1)提取这些路径的前缀去掉鸡蛋得到条件模式基{牛奶,尿布,啤酒}:1{牛奶,尿布}:1构建鸡蛋的条件FP-Tree统计条件模式基中的商品频率牛奶:2, 尿布:2, 啤酒:1按频率降序排列牛奶, 尿布构建树结构null ├── 牛奶(2) │ └── 尿布(2)从条件FP-Tree生成频繁项集{鸡蛋} (支持度2){牛奶,鸡蛋} (支持度2){尿布,鸡蛋} (支持度2){牛奶,尿布,鸡蛋} (支持度2)3.2 挖掘以面包结尾的频繁项集同样的方法应用于面包包含面包的路径牛奶→啤酒→面包 (1)牛奶→尿布→面包 (1)尿布→啤酒→面包 (1)条件模式基{牛奶,啤酒}:1{牛奶,尿布}:1{尿布,啤酒}:1面包的条件FP-Tree频率统计牛奶:2, 尿布:2, 啤酒:2树结构为空所有商品支持度相同无法形成树频繁项集{面包} (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, encodingISO-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, columnste.columns_)4.2 运行FP-Growth算法# 挖掘频繁项集最小支持度2% frequent_itemsets fpgrowth(df_encoded, min_support0.02, use_colnamesTrue) # 按支持度降序排列 frequent_itemsets frequent_itemsets.sort_values(support, ascendingFalse) print(frequent_itemsets.head(10))输出示例supportitemsets00.178(WHITE HANGING HEART T-LIGHT HOLDER)10.092(JUMBO BAG RED RETROSPOT)20.085(REGENCY CAKESTAND 3 TIER)30.072(PARTY BUNTING)40.068(LUNCH BAG RED RETROSPOT)50.062(ASSORTED COLOUR BIRD ORNAMENT)60.058(WHITE METAL LANTERN)70.056(JUMBO BAG RED RETROSPOT, WHITE HANGING HEART T-LIGHT HOLDER)80.051(SET OF 3 CAKE TINS PANTRY DESIGN)90.049(LUNCH BAG RED RETROSPOT, JUMBO BAG RED RETROSPOT)4.3 生成关联规则从频繁项集中提取有意义的关联规则from mlxtend.frequent_patterns import association_rules # 生成关联规则最小提升度1.5 rules association_rules(frequent_itemsets, metriclift, min_threshold1.5) # 按置信度降序排列 rules rules.sort_values(confidence, ascendingFalse) print(rules[[antecedents, consequents, support, confidence, lift]].head())输出示例antecedentsconsequentssupportconfidencelift0(LUNCH BAG RED RETROSPOT)(JUMBO BAG RED RETROSPOT)0.0490.7217.831(JUMBO BAG RED RETROSPOT)(LUNCH BAG RED RETROSPOT)0.0490.5337.832(SET/6 RED SPOTTY PAPER PLATES)(SET/6 RED SPOTTY PAPER CUPS)0.0280.6836.923(SET/6 RED SPOTTY PAPER CUPS)(SET/6 RED SPOTTY PAPER PLATES)0.0280.5816.924(RED RETROSPOT CHARLOTTE BAG)(JUMBO BAG RED RETROSPOT)0.0230.6927.52这些规则揭示了有趣的商品关联例如购买午餐袋红色复古点的顾客有72.1%的概率也会购买大号袋红色复古点这种组合的销售可能性是随机组合的7.83倍。零售商可以利用这些洞察优化商品摆放位置或设计组合促销方案。5. FP-Growth在推荐系统中的应用FP-Growth算法在推荐系统中有着广泛的应用场景。与协同过滤等传统方法相比基于关联规则的推荐有以下优势可解释性强能够明确说明因为买了A所以推荐B的逻辑冷启动友好不需要用户历史评分数据仅基于交易记录发现意外关联能捕捉非直观但实际存在的商品关系5.1 实现简单的推荐引擎基于前面挖掘的关联规则我们可以构建一个简单的推荐系统def recommend_products(rules, current_items, top_n5): # 筛选出当前商品作为前件的规则 relevant_rules rules[rules[antecedents].apply(lambda x: set(x).issubset(current_items))] # 按提升度降序排列 relevant_rules relevant_rules.sort_values(lift, ascendingFalse) # 提取推荐商品去除已购买商品 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, keylambda 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通常作为推荐系统的一个组件与协同过滤、内容推荐等方法结合使用形成混合推荐策略。