推荐系统实战：通俗易懂的Apriori关联规则算法

《推荐系统实战通俗易懂的Apriori关联规则算法》讲师[xxxx]目标 audience数据分析师、算法工程师、对推荐系统感兴趣的同学课时1.5 - 2 小时第一部分引子 —— 从“猜你喜欢”到“买了还买”1.1 我们熟悉的协同过滤各位同学当我们谈论推荐算法时最耳熟能详的莫过于协同过滤Collaborative Filtering。User-based CF喜欢《三体》和《流浪地球》的张三和喜欢《三体》的李四很像那把《流浪地球》推荐给李四。Item-based CF买了《深入理解计算机系统》的人通常也买了《算法导论》。协同过滤的核心逻辑找相似相似的人或相似的物品。1.2 协同过滤的“盲区”与新的角度协同过滤很强大但它有时候会陷入“信息茧房”或忽略一些跨类别、非直观的规律。一个场景超市数据分析发现购买“尿布”的男性顾客有很高的概率会同时购买“啤酒”。协同过滤怎么看它需要先找到“和这个买尿布的男人相似的其他用户”或者发现“尿布和啤酒在向量空间里比较像”。问题尿布和啤酒长得一点也不像用户画像也未必一样。协同过滤很难捕捉这种“看似无关实则强关联”的规则。1.3 引出 Apriori 算法那么有没有一种算法可以不依赖“用户评分”或“物品相似度”而是直接从海量的交易记录中挖掘出物品之间内在的、隐藏的关联规则呢有这就是我们今天的主题 —— Apriori 算法。一句话定义Apriori 算法是一种用于挖掘频繁项集和关联规则的经典算法。它试图回答一个问题“如果发生了事件A那么事件B发生的可能性有多大”第二部分地基 —— 核心概念通俗版在开始挖数据之前我们先要统一“行话”。别怕我们用超市购物篮来解释。场景下面是 5 位顾客的一次购物记录。顾客ID购买的商品项集T1牛奶面包尿布T2可乐面包尿布啤酒T3牛奶尿布啤酒鸡蛋T4面包牛奶可乐啤酒T5面包牛奶尿布可乐2.1 三个核心指标支持度 (Support) —— “这个东西普遍吗”公式Support(X)包含X的交易数总交易数Support(X) \frac{包含X的交易数}{总交易数}Support(X)总交易数包含X的交易数​通俗理解一共有 5 笔订单有多少笔买了“牛奶”牛奶出现在 T1, T3, T4, T5 - 4 次 - Support(牛奶) 4/5 0.8作用淘汰那些“冷门”的东西。没人买的东西推荐也没意义。置信度 (Confidence) —— “买了A还会买B吗”公式Confidence(A⇒B)Support(A∪B)Support(A)Confidence(A \Rightarrow B) \frac{Support(A \cup B)}{Support(A)}Confidence(A⇒B)Support(A)Support(A∪B)​通俗理解在所有买了“尿布”的订单里有多少也买了“啤酒”买尿布的订单T1, T2, T3, T5 (共4次)同时买尿布和啤酒的订单T2, T3 (共2次)Confidence(尿布 - 啤酒) 2 / 4 0.5作用这就是规则的强度。50%的概率意味着每10个买尿布的顾客有5个会买啤酒。提升度 (Lift) —— “这个规则靠谱吗还是巧合”公式Lift(A⇒B)Confidence(A⇒B)Support(B)Support(A∪B)Support(A)×Support(B)Lift(A \Rightarrow B) \frac{Confidence(A \Rightarrow B)}{Support(B)} \frac{Support(A \cup B)}{Support(A) \times Support(B)}Lift(A⇒B)Support(B)Confidence(A⇒B)​Support(A)×Support(B)Support(A∪B)​通俗理解买尿布对于买啤酒这件事有多大的“提升”作用计算啤酒的普遍性 Support(啤酒) 出现在 T2, T3, T4 - 3/5 0.6Lift 0.5 / 0.6 0.833判定标准Lift 1正相关。买了A会促进买B。这才是我们想要的强规则Lift 1独立无关。A和B没关系。Lift 1负相关。买了A会抑制买B。2.2 Apriori 的核心思想一个“反直觉”的剪枝原理如果要计算所有商品组合的支持度计算量是指数级的2^n种组合。Apriori 提出了一个至关重要的先验原理一个项集如果是频繁的那么它的所有子集也一定是频繁的。反过来一个项集如果是非频繁的那么它的所有超集也一定是非频繁的。举例如果 {可乐, 尿布} 这个组合很少出现非频繁那么 {可乐, 尿布, 啤酒} 这个更大的组合出现次数只会更少没必要去计算了这个原理让我们可以一层一层地筛选提前剪枝大大减少了计算量。第三部分实战 —— 手动演算一个案例需求使用 Apriori 算法找出上面的购物篮数据中支持度 0.4且置信度 0.6的强关联规则。数据回顾T1(牛奶,面包,尿布)T2(可乐,面包,尿布,啤酒)T3(牛奶,尿布,啤酒,鸡蛋)T4(面包,牛奶,可乐,啤酒)T5(面包,牛奶,尿布,可乐)最小支持度计数0.4 * 5 2 (至少出现2次)最小置信度0.6第一步找出所有频繁项集1. 候选1项集 C1牛奶:4 面包:4 尿布:4 可乐:3 啤酒:3 鸡蛋:1剪枝去掉支持度 2 的频繁1项集 L1{牛奶} {面包} {尿布} {可乐} {啤酒}2. 由L1生成候选2项集 C2(组合所有可能){牛奶,面包}{牛奶,尿布}{牛奶,可乐}{牛奶,啤酒}{面包,尿布}{面包,可乐}{面包,啤酒}{尿布,可乐}{尿布,啤酒}{可乐,啤酒}计算支持度计数{牛奶,面包}: T1,T4,T5 - 3{牛奶,尿布}: T1,T3,T5 - 3{牛奶,可乐}: T4,T5 - 2{牛奶,啤酒}: T3,T4 - 2{面包,尿布}: T1,T2,T5 - 3{面包,可乐}: T2,T4,T5 - 3{面包,啤酒}: T2,T4 - 2{尿布,可乐}: T2,T5 - 2{尿布,啤酒}: T2,T3 - 2{可乐,啤酒}: T2,T4 - 2剪枝去掉支持度 2的这里全部都 2所以都保留。频繁2项集 L2以上10个全部。3. 由L2生成候选3项集 C3(Apriori原理{A,B,C}要频繁{A,B}、{A,C}、{B,C}必须都在L2中)检查 {牛奶,面包,尿布}: 子集 {牛奶,面包}(L2有){牛奶,尿布}(L2有){面包,尿布}(L2有) - 保留。检查 {牛奶,面包,可乐}: 子集 {牛奶,可乐}(有){面包,可乐}(有){牛奶,面包}(有) - 保留。… (依此类推我们只关注可能出现的)我们尝试 {尿布,啤酒,可乐}: 子集 {尿布,可乐}(有){尿布,啤酒}(有){可乐,啤酒}(有) - 保留。{牛奶,尿布,啤酒}: 子集 {牛奶,尿布}(有){牛奶,啤酒}(有){尿布,啤酒}(有) - 保留。{面包,尿布,啤酒}: 子集 {面包,尿布}(有){面包,啤酒}(有){尿布,啤酒}(有) - 保留。计算支持度(扫描原始数据){牛奶,面包,尿布}: T1, T5 - 2{牛奶,面包,可乐}: T4, T5 - 2{尿布,啤酒,可乐}: T2 只有这一个 - 1 (淘汰){牛奶,尿布,啤酒}: T3 只有这一个 - 1 (淘汰){面包,尿布,啤酒}: T2 只有这一个 - 1 (淘汰)剪枝后频繁3项集 L3{牛奶, 面包, 尿布}{牛奶, 面包, 可乐}4. 生成候选4项集 C4尝试组合 {牛奶,面包,尿布,可乐}需要其子集 {牛奶,面包,尿布}(有){牛奶,面包,可乐}(有){牛奶,尿布,可乐}(不在L3因为L3里没有这个它在C3阶段被淘汰了) -剪枝不生成。最终频繁项集L1, L2, L3。第二步从频繁项集中生成关联规则我们以L3 的 {牛奶, 面包, 尿布}为例生成规则。规则形式左 - 右1. 规则{牛奶,面包} - {尿布}置信度 Support({牛奶,面包,尿布}) / Support({牛奶,面包}) (2/5) / (3/5) 2/3 ≈0.666通过0.62. 规则{牛奶,尿布} - {面包}置信度 (2/5) / (3/5) 2/3 ≈0.666 (通过)3. 规则{面包,尿布} - {牛奶}置信度 (2/5) / (3/5) 2/3 ≈0.666 (通过)4. 规则{牛奶} - {面包,尿布}置信度 (2/5) / (4/5) 2/4 0.5 (淘汰)5. 规则{面包} - {牛奶,尿布}置信度 (2/5) / (4/5) 2/4 0.5 (淘汰)6. 规则{尿布} - {牛奶,面包}置信度 (2/5) / (4/5) 2/4 0.5 (淘汰)结论我们发现当用户同时买了{牛奶,面包}时有66.6%的概率会买尿布。这是一个不错的推荐规则第四部分验证 —— 用 Python 代码实现理论要联系实际。我们使用mlxtend库专门用于数据挖掘的Python库来验证我们的手动计算。# 1. 导入必要的库importpandasaspdfrommlxtend.frequent_patternsimportapriori,association_rules# 2. 构建数据使用我们之前的例子dataset[[牛奶,面包,尿布],[可乐,面包,尿布,啤酒],[牛奶,尿布,啤酒,鸡蛋],[面包,牛奶,可乐,啤酒],[面包,牛奶,尿布,可乐]]# 3. 数据预处理将原始数据转换为一热编码One-Hot Encoding的表格# mlxtend 要求输入的数据格式是 True/False 的表格表示每件商品是否在订单中# 首先获取所有商品的唯一列表all_itemssorted(list(set([itemforsublistindatasetforiteminsublist])))print(所有商品:,all_items)# 创建空的 DataFramedfpd.DataFrame(columnsall_items)# 填充数据fori,transactioninenumerate(dataset):# 对于每一笔交易检查每个商品是否存在foriteminall_items:df.loc[i,item](itemintransaction)# 将布尔值转换为 True/Falsemlxtend 可以直接用print(\n编码后的交易数据True买了:)print(df)# 4. 应用 Apriori 算法寻找频繁项集# min_support0.4 表示最小支持度为 40%即出现次数 2# use_colnamesTrue 让结果直接显示商品名而不是列索引frequent_itemsetsapriori(df,min_support0.4,use_colnamesTrue)# 添加一列显示项集长度方便观察frequent_itemsets[length]frequent_itemsets[itemsets].apply(lambdax:len(x))print(\n频繁项集支持度 0.4:)print(frequent_itemsets)# 5. 生成关联规则# metricconfidence, min_threshold0.6 表示最小置信度为 60%rulesassociation_rules(frequent_itemsets,metricconfidence,min_threshold0.6)# 按置信度降序排列查看最强规则rules_sortedrules.sort_values(confidence,ascendingFalse)print(\n生成的关联规则置信度 0.6:)# 只显示我们关心的列print(rules_sorted[[antecedents,consequents,support,confidence,lift]])# 6. 代码执行逻辑分析# - Step 1-2: 准备数据。# - Step 3: 将文本数据转化为算法能理解的矩阵独热编码。# - Step 4: 调用 apriori 函数传入最小支持度它会自动完成我们在第三部分的“剪枝”和“连接”过程。# - Step 5: 调用 association_rules 函数基于频繁项集和最小置信度生成所有可能的规则如 A-B, B-A。# - 输出结果可以和我们手动计算的 {牛奶,面包} - {尿布} (置信度0.666) 进行对比结果一致。代码运行结果分析你会看到rules_sorted中包含一条规则antecedents (左) {牛奶, 面包},consequents (右) {尿布}confidence 0.666667。这完美验证了我们手动演算的结果同时算法还会找出其他符合条件的规则比如{可乐, 面包} - {牛奶}等。第五部分放眼生产 —— 常见的应用场景Apriori 不仅仅是教科书上的例子它在工业界有广泛的应用电商推荐经典“买了还买”场景用户将“手机”加入购物车系统推荐“手机壳”和“贴膜”。挖掘规则{手机} - {手机壳} (高置信度、高提升度)交叉销售超市货架摆放场景发现 {啤酒} - {尿布} 是强规则就把啤酒和尿布放在相邻的货架方便爸爸们一次性拿取提升销售额。挖掘规则{面包} - {牛奶}放在一起。医疗诊断症状-疾病关联场景分析病历数据发现 {高血糖, 多饮, 多尿} - {糖尿病} 的置信度极高。应用辅助医生进行早期诊断。网页分析用户点击路径场景用户浏览路径首页 - 商品列表页 - 购物车 - 支付页。挖掘规则{进入购物车} - {进入支付页} 的转化率。如果置信度低说明支付流程可能有问题。第六部分客观评价 —— Apriori 的优缺点优点 (Pros)缺点 (Cons)原理简单易于解释生成的规则如果A则B非常直观业务人员也能看懂。多次扫描数据库每生成一轮候选集都要扫描一次数据库I/O开销巨大。强大的剪枝策略Apriori原理大大减少了候选项集的数量比暴力穷举高效得多。候选集可能爆炸当最小支持度设得很低或数据量极大时C22项集可能多到内存放不下。发现隐性关联能挖掘出协同过滤难以发现的跨类别、非直观规律。兴趣度度量单一有时高置信度、高支持度的规则可能是无趣的比如买面包的人几乎都买牛奶因为牛奶是必需品提升度可以缓解但非完美。第七部分面试加油站 —— 常见面试题Q1: Apriori 算法的核心思想是什么A:核心是“频繁项集的所有非空子集也必须是频繁的”。反之如果一个项集是非频繁的那么它的所有超集都是非频繁的可以直接剪枝。这大幅减少了候选项集的数量。Q2: 支持度、置信度、提升度分别代表什么在实际应用中如何设定它们的阈值A:支持度衡量规则覆盖的普遍性。阈值设定取决于业务需求想找“爆款组合”就设高一点如0.01~0.1想找“长尾小众组合”就设低一点。置信度衡量规则的强度或概率。一般设0.5以上。提升度衡量规则的相关性方向。必须 1 才是有意义的正相关规则1 的规则不建议使用。技巧先设低一点的支持度保证召回再设较高的置信度保证精度。Q3: Apriori 算法最大的性能瓶颈是什么如何优化A:瓶颈在于多次扫描数据库和生成庞大的候选2项集。优化方法基于哈希的优化在生成C2时使用哈希表避免重复计数。划分Partitioning将数据库分块每块找出局部频繁项集最后合并。采样Sampling在数据的子集上运行算法牺牲少量精度换取速度。FP-Growth 算法这是 Apriori 的升级版它只扫描两次数据库使用一种叫 FP-Tree 的压缩数据结构完全不产生候选集速度极快。第八部分课程总结今天我们学习了推荐系统中的一个经典算法——Apriori。我们从协同过滤的局限性出发认识了关联规则挖掘的价值。我们用一个购物篮的通俗例子拆解了支持度、置信度、提升度这三个核心概念并理解了 Apriori 那巧妙的剪枝原理。我们亲手手动演算了一遍体验了从频繁项集到关联规则的完整流程。我们用 Python 代码验证感受到了算法落地的便捷。最后我们探讨了它的应用、优缺点和面试考点。一句话总结Apriori 算法虽然诞生已久性能上并非最优但它所蕴含的“先验剪枝”思想是数据挖掘领域的瑰宝。理解它是理解更高级算法如FP-Growth、PrefixSpan的基石。第九部分课后作业题题目优化你的商品组合背景假设你是某便利店的运营分析师你拿到了以下 6 位顾客的购物小票数据交易ID购买商品100薯片可乐纸巾101面包牛奶香蕉102薯片可乐面包103牛奶面包纸巾可乐104薯片牛奶可乐105面包牛奶薯片任务手动计算可以使用计算器或Excel辅助设置最小支持度 0.5(即至少出现在3笔交易中)。找出所有的频繁1项集、频繁2项集和频繁3项集。基于你找到的频繁项集计算规则{薯片} - {可乐}的置信度和提升度。编程验证使用 Python 的mlxtend库复现你的手动计算结果。找出所有置信度 0.66的规则并按提升度从高到低排序。打印出前三名规则并尝试解释这些规则对货架摆放有什么启示。提交方式将手动演算的过程拍照或扫描和 Python 代码截图或 .py 文件一并提交。提示第5笔交易104和第6笔交易105是计算关键别漏掉了。课件结束祝大家学习愉快挖掘出属于自己的“黄金规则”