★ FEATURED ARTICLE 做数据挖掘、搞数据分析的朋友基本都绕不开关联规则这个经典方向。只要一说“啤酒和尿布”的故事大家就知道说的是购物篮分析——从一堆订单里找出“哪些商品经常一起出现”然后把它变成促销策略、货架摆放、交叉销售的依据。但故事听再多落到代码和原理层面很多人其实是含糊的支持度和置信度到底怎么算Apriori和FP-Growth到底差在哪为什么FP-Growth号称更快实际项目里又该怎么选这篇文章我用一份只有5条订单的小样本把关联规则从定义到两个算法的完整推演过程走一遍再给出能直接运行的Python代码。看完你不仅能看懂Apriori的候选剪枝逻辑也能理解FP树的条件模式基是怎么递归挖掘的。适合刚接触关联规则的初学者也适合那些用过sklearn、mlxtend库但没真正搞懂内部机制的从业者。我会尽量用大白话讲原理用能落地的方式讲实操。1. 关联规则在算什么三个指标把“规律”量化关联规则要回答的核心问题其实很简单如果顾客买了A他有多大可能也买B但真实数据里没有这么干净的因果关系所以我们需要三个量化指标分别从“常见程度”“条件强度”“独立性”三个角度去衡量一条规则的价值。1.1 支持度这条规律覆盖了多少数据支持度Support是最直观的指标它表示一个项集在全部事务中出现的比例。假设有1000条订单其中同时包含“牛奶”和“面包”的订单有300条那么项集{牛奶, 面包}的支持度就是300 / 1000 0.3。公式是support(X) count(X) / N其中N是总事务数count(X)是包含项集X的事务数。为什么先看支持度因为如果一个组合在数据里只出现一两次那它再“巧合”也没有统计意义。支持度本质上是给规律画一条最低“出镜率”的线——低于这个线的组合直接淘汰不浪费后续计算资源。实际操作中这条线就是min_support阈值它决定了挖掘结果的规模。1.2 置信度这条规律靠不靠谱置信度Confidence衡量的是规则X→Y的条件概率也就是在买了X的订单中有多少比例也买了Y。公式为conf(X→Y) support(X ∪ Y) / support(X)举个例子{牛奶, 面包}的支持度是0.3{牛奶}的支持度是0.4那么规则“牛奶→面包”的置信度就是0.3 / 0.4 0.75。意思是买了牛奶的顾客里75%的人也会买面包。置信度越高规则越“强”。但它有一个隐患如果面包本身就是一个热销品很多人即使不买牛奶也会买面包那高置信度可能只是基数效应的假象。这时候就需要第三个指标来纠偏。1.3 提升度这条规律有没有增量价值提升度Lift的公式是lift(X→Y) support(X ∪ Y) / (support(X) × support(Y))也可以写成lift conf(X→Y) / support(Y)。它比较的是“规则成立的概率”和“Y本来就出现的概率”之间的比值。lift 1X的出现让Y更可能出现了说明X→Y有正向价值。lift 1两者独立规则没有意义。lift 1X的出现反而抑制了Y的出现属于负相关。还是上面那个例子support({牛奶}) 0.4support({面包}) 0.5那么lift 0.3 / (0.4 × 0.5) 1.5。大于1说明“牛奶→面包”确实是比随机搭售更有效的规律。这三个指标不是互相替代的而是互相配合的。支持度过滤“样本量不足”置信度衡量“条件强度”提升度剔除“基数效应”。实际项目中三条线都要卡只盯着其中一个很容易挖出一堆看似漂亮、落地却完全无效的规则。2. Apriori用“先验性质”剪掉不靠谱的候选Apriori是关联规则最经典的算法1994年提出直到今天依然是教科书首选。它的名字来源于一个很强的先验性质如果一个项集是频繁的那么它的所有非空子集也一定是频繁的。反过来如果一个项集不频繁那么它的所有超集一定不频繁。2.1 核心思想候选生成加剪枝Apriori的思路是逐层搜索从1项集开始一层一层往上找。每一轮分两步第一步是连接join把上一层频繁项集两两组合生成候选集。比如频繁2项集{牛奶, 面包}和{牛奶, 尿布}连接后可能生成候选3项集{牛奶, 面包, 尿布}。第二步是剪枝prune利用先验性质。生成候选3项集{牛奶, 面包, 尿布}后先检查它的所有2项子集——{牛奶, 面包}、{牛奶, 尿布}、{面包, 尿布}——是否都在上一层的频繁2项集里。只要有一个不在这个候选3项集就直接砍掉根本不用去数据库里数支持度。这个剪枝是Apriori效率的关键。因为候选集数量膨胀得极快如果不在生成阶段做筛选等真正扫描数据库的时候候选集可能爆炸到无法处理。完整流程是扫描数据库统计1项集支持度 → 过滤出频繁1项集L1 → 由L1生成候选2项集C2 → 扫描数据库统计C2支持度 → 过滤出L2 → 由L2生成候选3项集C3 → 重复直到没有新的频繁项集产生。每找一层都要完整扫一遍数据库这是Apriori最大的成本所在。2.2 手工推演一遍Apriori全过程为了把过程讲透我用一个只有5条订单的小数据集手推一遍。商品用中文方便对照订单ID购买商品T1牛奶, 面包, 尿布T2牛奶, 面包T3面包, 啤酒T4牛奶, 面包, 啤酒T5尿布, 啤酒总事务数N 5。我把min_support设为0.4也就是至少出现在2条订单中的项集才算频繁。第一轮扫描统计单项支持度项计数支持度是否频繁牛奶30.6是面包40.8是尿布20.4是啤酒30.6是4个单项全部过线得到L1{牛奶}、{面包}、{尿布}、{啤酒}。第二轮由L1生成候选2项集C2。4个单项两两组合共有C(4,2)6个候选{牛奶, 面包}、{牛奶, 尿布}、{牛奶, 啤酒}、{面包, 尿布}、{面包, 啤酒}、{尿布, 啤酒}。扫描数据库统计支持度候选2项集计数支持度是否频繁{牛奶, 面包}3T1,T2,T40.6是{牛奶, 尿布}1T10.2否{牛奶, 啤酒}1T40.2否{面包, 尿布}1T10.2否{面包, 啤酒}2T3,T40.4是{尿布, 啤酒}1T50.2否得到L2{牛奶, 面包}和{面包, 啤酒}。第三轮由L2生成候选3项集。两个频繁2项集连接可以得到{牛奶, 面包, 啤酒}。但在剪枝阶段要检查它的所有2项子集{牛奶, 面包}在L2中{牛奶, 啤酒}不在L2中{面包, 啤酒}在L2中。因为{牛奶, 啤酒}不是频繁项集所以{牛奶, 面包, 啤酒}直接剪掉不扫描数据库。最终频繁项集{牛奶}、{面包}、{尿布}、{啤酒}、{牛奶, 面包}、{面包, 啤酒}。接下来生成规则。从{牛奶, 面包}可以推出两条规则牛奶→面包置信度 support({牛奶, 面包}) / support({牛奶}) 0.6 / 0.6 1.0面包→牛奶置信度 support({牛奶, 面包}) / support({面包}) 0.6 / 0.8 0.75从{面包, 啤酒}可以推出面包→啤酒置信度 0.4 / 0.8 0.5啤酒→面包置信度 0.4 / 0.6 ≈ 0.667注意虽然{牛奶, 面包}这个项集支持度很高但它能生成的规则方向不同业务含义也完全不同。如果门店想用牛奶带动面包置信度100%当然漂亮如果反过来想用面包带动牛奶置信度只有75%说服力就弱一些。2.3 Apriori的两个性能瓶颈手工推演看着轻松但数据量一大Apriori的问题就很明显。第一个瓶颈是重复扫描数据库。每找一层频繁项集都要完整扫一遍全部事务。如果最大频繁项集的长度是5那至少要扫描5次数据库。对于百万级订单的数据磁盘I/O开销是非常可观的。第二个瓶颈是候选集爆炸。在项商品数量大的情况下2项候选集可能是几万甚至几十万个。虽然剪枝能砍掉一部分但生成候选和统计支持度本身还是巨大的计算量。尤其当支持度阈值设得很低的时候频繁项集数量会指数级增长候选集规模跟着起飞。这也是为什么后来大家更关注FP-Growth——它把“多次扫描”压缩成“两次扫描”从根上绕开了候选集生成这一步。3. FP-Growth两次扫描把事务压缩进一棵树FP-Growth的全称是Frequent Pattern Growth核心思路是用一棵FP树把整个事务数据库压缩到内存里然后在树上递归挖掘频繁项集全程不生成候选集。它也是标题里说的“FP-树频集算法”用树结构直接完成频集挖掘。3.1 FP-Tree是怎么建起来的FP树的全称是Frequent Pattern Tree。它的构建分两步第一次扫描统计所有单项的支持度并过滤第二次扫描逐条处理事务把每条订单中的商品按支持度降序排列后插入树中。为什么要降序排列因为支持度高的商品更容易成为多个事务的公共前缀把它们放前面树的分支就能共享节点压缩率更高。反过来说如果把很少出现的商品放前面每棵树的分支都不同树就会变得又细又长失去压缩意义。继续用上面5条订单的数据。第一次扫描得到单项频次面包4次、牛奶3次、啤酒3次、尿布2次。过滤后全部保留排序规则是频次降序同频次按名称顺序。所以事务T1“牛奶, 面包, 尿布”重排为“面包, 牛奶, 尿布”T3“面包, 啤酒”重排为“面包, 啤酒”T5“尿布, 啤酒”重排为“啤酒, 尿布”。逐条插入后树结构长这样root ├── 面包 (4) │ ├── 牛奶 (3) │ │ └── 尿布 (1) │ └── 啤酒 (1) └── 啤酒 (2) └── 尿布 (1)括号里是节点计数。面包节点计数4说明4条订单都以面包开头牛奶节点计数3说明在面包之后有3条订单包含牛奶。同时还要建一张项头表记录每个商品的总频次并用链表把树中所有同名节点串起来。这张表是后面递归挖掘的入口。3.2 条件模式基递归挖掘的核心建完树之后挖掘过程从项头表的底部往上走。所谓条件模式基就是“以某个商品为后缀时所有前缀路径的集合”。拿商品“啤酒”来说。树中啤酒出现在两条路径上一条是“面包→啤酒”节点计数1另一条是“root→啤酒”节点计数2。那么啤酒的条件模式基就是两条路径的前缀部分{面包} 计数1{空} 计数2空路径不产生有效前缀。把这些前缀再按支持度过滤面包的前缀计数是1小于min_support2所以被剪掉。最终从啤酒能挖出的组合只有{面包, 啤酒}支持度0.4。再看商品“牛奶”。牛奶在树中只出现在“面包→牛奶”这条路径上节点计数3。条件模式基就是{面包} 计数3。面包的计数3 ≥ 2满足阈值于是生成频繁模式{牛奶, 面包}支持度0.6。整个挖掘过程就是这样一层层递归从某个后缀开始找它的条件模式基在条件模式基上构建条件FP树再递归挖掘新的后缀。每一层都只处理与当前后缀相关的数据不需要像Apriori那样反复全表扫描。3.3 手工验证FP-Growth结果和Apriori一致我继续把剩下的两个商品也推完尿布条件模式基是{面包, 牛奶} 计数1{啤酒} 计数1。面包、牛奶、啤酒的前缀计数都只有1全部剪掉。所以尿布没有和任何商品形成频繁组合。面包没有前缀路径直接结束。最终FP-Growth挖出的频繁项集和Apriori完全一致{牛奶}、{面包}、{尿布}、{啤酒}、{牛奶, 面包}、{面包, 啤酒}。这个一致性不是巧合。两个算法解决的是同一个问题只是计算路径不同。如果你手推的结果和Apriori不一致那一定是某个环节出了问题优先级最高的怀疑对象是排序规则——FP树建树时的商品顺序如果不统一条件模式基就会错。3.4 两个算法怎么选一个表说清楚我实际项目中做选型时主要看数据规模和支持度阈值对比维度AprioriFP-Growth扫描数据库次数每层频繁项集都要扫描仅2次候选集需要生成大量候选再剪枝不需要生成候选内存占用候选集占用内存但FP树以外空间压力小树结构常驻内存数据量大时吃内存实现复杂度简单逻辑直观树构建和递归较复杂适用场景数据量小、项数少、教学验证数据量大、支持度低、生产环境FP-Growth并不是在所有情况下都碾压Apriori。数据量很小或者频繁项集很短的时候Apriori的多次扫描开销可以忽略实现简单反而是最大的优势。数据量一旦上来或者需要把支持度阈值压得很低去找长尾规律FP-Growth就明显更稳。4. Python实战同一份数据跑通两个算法原理讲完了接下来是动手环节。我用Python完整演示一遍关联规则挖掘流程数据准备、Apriori验证、FP-Growth实现、规则解读。4.1 数据准备事务数据不是表数据事务数据长什么样它不是一个规整的二维表而是每条订单一个列表、列表里是购买的商品。这是最原始、最常见的订单形态。transactions [ [牛奶, 面包, 尿布], [牛奶, 面包], [面包, 啤酒], [牛奶, 面包, 啤酒], [尿布, 啤酒], ]为了演示真实起效果我先构造一个1000条订单的模拟数据里面人工埋入一组关联只要买了牛奶70%的概率也会买面包。import random items [牛奶, 面包, 尿布, 啤酒, 鸡蛋, 薯片] random.seed(42) transactions [] for _ in range(1000): size random.randint(2, 5) basket set(random.sample(items, size)) if 牛奶 in basket and random.random() 0.7: basket.add(面包) transactions.append(list(basket))这样数据里既保留了随机噪声又有一组可被发现的真实规律。下面我分别用库和手写代码来挖掘。4.2 用现成库快速验证Apriori结果我之前用的是mlxtend库做快速验证先把事务列表转成one-hot编码的DataFrame。import pandas as pd from mlxtend.preprocessing import TransactionEncoder from mlxtend.frequent_patterns import apriori, association_rules te TransactionEncoder() te_ary te.fit(transactions).transform(transactions) df pd.DataFrame(te_ary, columnste.columns_) freq_items apriori(df, min_support0.05, use_colnamesTrue) print(freq_items.sort_values(support, ascendingFalse).head(10))min_support这里设0.05相当于至少出现50次过滤掉过稀的组合。输出会显示所有频繁项集和它们的支持度。这一步的意义是把整个流程快速跑通验证环境和数据没问题也为后面手写FP-Growth提供一个对照标准。再生成关联规则按置信度排序查看rules association_rules(freq_items, metricconfidence, min_threshold0.5) rules_sorted rules.sort_values(lift, ascendingFalse) print(rules_sorted[[antecedents, consequents, support, confidence, lift]].head(10))人工注入的“牛奶→面包”规律应该会出现在结果里置信度接近0.7lift明显大于1。这样整个挖掘链路就验证通了。4.3 手写一个可运行的FP-Growth核心实现理解了原理之后我还是建议手写一遍FP-Growth哪怕只是核心框架。因为树结构的递归逻辑如果不亲手捋一遍很多细节是记不住的。下面给一个我简化过但能跑通的版本重点看两个部分树节点和建树。class FPNode: __slots__ (name, count, parent, children, link) def __init__(self, name, parentNone): self.name name self.count 0 self.parent parent self.children {} self.link None def add_child(self, name): if name not in self.children: self.children[name] FPNode(name, self) return self.children[name] def build_tree(transactions, min_count): freq {} for t in transactions: for item in t: freq[item] freq.get(item, 0) 1 freq {k: v for k, v in freq.items() if v min_count} if not freq: return None, None header {} for item, cnt in sorted(freq.items(), keylambda x: (-x[1], x[0])): header[item] [cnt, None] root FPNode(None) for t in transactions: items sorted([i for i in t if i in freq], keylambda i: (-freq[i], i)) cur root for item in items: is_new item not in cur.children cur cur.add_child(item) cur.count 1 if is_new: if header[item][1] is None: header[item][1] cur else: p header[item][1] while p.link: p p.link p.link cur return root, header这里有一个非常容易踩的坑链表挂载。前面说过每个商品的项头表要用链表把所有同名节点串起来方便后面收集条件模式基。如果一个事务中的商品已经存在于当前节点的子节点里就不应该重复挂链表否则后面遍历时会重复计数。上面的is_new就是为这个目的加的。很多网上流传的简化代码都会漏掉这一手导致结果莫名其妙翻倍。下面是递归挖掘的核心逻辑def prefix_paths(node): paths [] p node.parent prefix [] while p and p.name is not None: prefix.append(p.name) p p.parent if prefix: paths.append((prefix, node.count)) return paths def mine(header, min_count, suffix): result [] for item, (cnt, head_node) in sorted(header.items(), keylambda x: x[1][0]): new_suffix suffix [item] result.append(new_suffix) cond_trans [] node head_node while node: for path, count in prefix_paths(node): cond_trans.extend([path] * count) node node.link if not cond_trans: continue cond_root, cond_header build_tree(cond_trans, min_count) if cond_header: result.extend(mine(cond_header, min_count, new_suffix)) return result调用方式min_count 2 # 等价于 min_support 0.4对于1000条数据就是50 root, header build_tree(transactions, min_count) freq_result mine(header, min_count, []) print(freq_result)注意这里min_count是绝对计数等价于相对支持度乘以总事务数。用绝对计数在递归里会更顺手不用每次传递事务总数。4.4 输出规则后怎么解读不管用哪个算法最终产出的都是一张频繁项集表和若干条规则。拿到结果后第一件事不是看置信度排名而是做业务翻译。规则“牛奶→面包”置信度0.7提升度1.5翻译成业务语言是买了牛奶的顾客70%会顺便买面包而且这个连带比例比面包的自然购买率高50%。这个结论可以直接指导行动比如把牛奶和面包放在同一动线上、推出牛奶面包组合优惠。规则“尿布→牛奶”如果它存在且lift接近1翻译过来就是“买尿布的人并没有比其他人更可能买牛奶”这种规则再漂亮也不能用因为它只是把两个热销品硬凑在一起。我在实际项目中还会加一道筛选只保留后件consequents是具体目标商品的规则。比如运营方想提高面包的销量那就重点看所有“X→面包”的规则按lift从高到低排找出真正能把面包带起来的关联商品。5. 实战避坑阈值、伪相关和代码细节关联规则挖掘从原理到跑通代码只是第一步真正拿到真实数据上坑比想象中多。5.1 支持度阈值怎么定别拍脑袋min_support设太高挖出来的都是人尽皆知的热门组合设太低频繁项集多到没法看。我的经验是先用一个初始值跑一遍看结果数量。如果频繁项集超过几百条大概率是阈值偏低往上调如果只有两三条孤零零的组合往下调。还有一个技巧看最大频繁项集的长度。如果设0.05之后最大长度只有2说明数据中几乎没有更长的组合这时候可以尝试降低阈值挖掘3项甚至4项的组合往往能发现跨品类的隐藏关联。5.2 提升度小于1的规则要不要留很多教程会告诉你“只保留lift大于1的规则”这是对的但要理解背后的逻辑lift小于1说明前件对后件是抑制关系也就是买了A反而不太会买B。这种负相关在业务里其实也有价值比如两类商品放在一起会互相竞争那陈列时就要刻意分开。我见过有人把这种规则全删掉后来分析竞品冲突时才后悔当初没保留。如果你只关心正向搭配那过滤掉lift ≤ 1的规则没问题如果你要做货架竞品分析负相关规则同样值得看。5.3 伪相关高置信度不等于真因果置信度和提升度衡量的都是相关关系不是因果关系。举个例子某商品“咖啡”和“咖啡滤纸”的关联规则置信度再高也说明不了谁带动谁因为咖啡滤纸本身就是咖啡的配件。再比如“烟”和“打火机”这俩的关联强到可以预测但它没有“X能带动Y”的商业价值。解决伪相关问题的一个有效方法是引入时间维度或场景维度。只分析工作日上午的订单或者只分析包含礼品包装的订单往往能让规则的业务含义更清晰。这不是关联规则算法本身的问题而是数据切分方式的问题我在项目里通常会在数据预处理阶段就做好场景切分而不是等挖出规则再解释。5.4 手写实现时的两个高频Bug第一个是前面提到的链表重复挂载。如果不判断当前节点是否新建同一个节点会被反复加入链表后面收集条件模式基时同一个前缀会被重复计数最终结果比真实支持度高出一截。第二个是商品排序不一致。FP树建树和条件模式基收集必须用同一套排序规则比如都是“频次降序、同频次按名称排序”。如果建树时按频次排条件模式基推演时又按字典序排树的结构和前缀路径会对不上挖出来的频繁项集千奇百怪。排查方式也简单先用一份小数据集跑两遍对一遍Apriori和FP-Growth的结果是否一致。还有一个小细节mlxtend的apriori结果和手写FP-Growth的结果格式不同一个是Itemsets加support的DataFrame一个是列表对比时别直接比较类型先把两者都转成集合结构再对。我在实际项目中验证算法正确性最蠢也最有效的方法就是像上面这样拿一个几行的小数据集手工推演一遍再对比代码输出。推演对了再放到百万级订单上跑心里才踏实。另外很多人纠结到底用Apriori还是FP-Growth我的看法是如果是教学、演示、数据量不大Apriori就够用代码简单不容易出错如果是生产环境、数据量大、支持度阈值要压得比较低那上FP-Growth更合适。但框架层面真没必要自己死磕底层实现mlxtend里现成的apriori和fpgrowth函数都调过稳定性没话说手写一遍主要是为了搞懂原理真上线还是建议走成熟实现把精力放到数据清洗、规则筛选和业务落地这些更值钱的事情上。
阅读完成 · 觉得有帮助？
