极客时间已完结课程限时免费阅读

30丨关联规则挖掘（上）：如何用Apriori发现用户购物规则？

30丨关联规则挖掘（上）：如何用Apriori发现用户购物规则？-极客时间

30丨关联规则挖掘（上）：如何用Apriori发现用户购物规则？

2019-02-20 陈旸 来自北京
《数据分析实战45讲》
课程介绍

讲述：陈旸

时长10:36大小9.69M

今天我来带你进行关联规则挖掘的学习，关联规则这个概念，最早是由 Agrawal 等人在 1993 年提出的。在 1994 年 Agrawal 等人又提出了基于关联规则的 Apriori 算法，至今 Apriori 仍是关联规则挖掘的重要算法。
关联规则挖掘可以让我们从数据集中发现项与项（item 与 item）之间的关系，它在我们的生活中有很多应用场景，“购物篮分析”就是一个常见的场景，这个场景可以从消费者交易记录中发掘商品与商品之间的关联关系，进而通过商品捆绑销售或者相关推荐的方式带来更多的销售量。所以说，关联规则挖掘是个非常有用的技术。
在今天的内容中，希望你能带着问题，和我一起来搞懂以下几个知识点：
搞懂关联规则中的几个重要概念：支持度、置信度、提升度；
Apriori 算法的工作原理；
在实际工作中，我们该如何进行关联规则挖掘。

搞懂关联规则中的几个概念

我举一个超市购物的例子，下面是几名客户购买的商品列表：
什么是支持度呢？
支持度是个百分比，它指的是某个商品组合出现的次数与总次数之间的比例。支持度越高，代表这个组合出现的频率越大。
在这个例子中，我们能看到“牛奶”出现了 4 次，那么这 5 笔订单中“牛奶”的支持度就是 4/5=0.8。
同样“牛奶 + 面包”出现了 3 次，那么这 5 笔订单中“牛奶 + 面包”的支持度就是 3/5=0.6。
什么是置信度呢？
它指的就是当你购买了商品 A，会有多大的概率购买商品 B，在上面这个例子中：
置信度（牛奶→啤酒）=2/4=0.5，代表如果你购买了牛奶，有多大的概率会购买啤酒？
置信度（啤酒→牛奶）=2/3=0.67，代表如果你购买了啤酒，有多大的概率会购买牛奶？
我们能看到，在 4 次购买了牛奶的情况下，有 2 次购买了啤酒，所以置信度 (牛奶→啤酒)=0.5，而在 3 次购买啤酒的情况下，有 2 次购买了牛奶，所以置信度（啤酒→牛奶）=0.67。
所以说置信度是个条件概念，就是说在 A 发生的情况下，B 发生的概率是多少。
什么是提升度呢？
我们在做商品推荐的时候，重点考虑的是提升度，因为提升度代表的是“商品 A 的出现，对商品 B 的出现概率提升的”程度。
还是看上面的例子，如果我们单纯看置信度 (可乐→尿布)=1，也就是说可乐出现的时候，用户都会购买尿布，那么当用户购买可乐的时候，我们就需要推荐尿布么？
实际上，就算用户不购买可乐，也会直接购买尿布的，所以用户是否购买可乐，对尿布的提升作用并不大。我们可以用下面的公式来计算商品 A 对商品 B 的提升度：
提升度 (A→B)= 置信度 (A→B)/ 支持度 (B)
这个公式是用来衡量 A 出现的情况下，是否会对 B 出现的概率有所提升。
所以提升度有三种可能：
提升度 (A→B)>1：代表有提升；
提升度 (A→B)=1：代表有没有提升，也没有下降；
提升度 (A→B)<1：代表有下降。

Apriori 的工作原理

明白了关联规则中支持度、置信度和提升度这几个重要概念，我们来看下 Apriori 算法是如何工作的。
首先我们把上面案例中的商品用 ID 来代表，牛奶、面包、尿布、可乐、啤酒、鸡蛋的商品 ID 分别设置为 1-6，上面的数据表可以变为：
Apriori 算法其实就是查找频繁项集 (frequent itemset) 的过程，所以首先我们需要定义什么是频繁项集。
频繁项集就是支持度大于等于最小支持度 (Min Support) 阈值的项集，所以小于最小值支持度的项目就是非频繁项集，而大于等于最小支持度的项集就是频繁项集。
项集这个概念，英文叫做 itemset，它可以是单个的商品，也可以是商品的组合。我们再来看下这个例子，假设我随机指定最小支持度是 50%，也就是 0.5。
我们来看下 Apriori 算法是如何运算的。
首先，我们先计算单个商品的支持度，也就是得到 K=1 项的支持度：
因为最小支持度是 0.5，所以你能看到商品 4、6 是不符合最小支持度的，不属于频繁项集，于是经过筛选商品的频繁项集就变成：
在这个基础上，我们将商品两两组合，得到 k=2 项的支持度：
我们再筛掉小于最小值支持度的商品组合，可以得到：
我们再将商品进行 K=3 项的商品组合，可以得到：
再筛掉小于最小值支持度的商品组合，可以得到：
通过上面这个过程，我们可以得到 K=3 项的频繁项集{1,2,3}，也就是{牛奶、面包、尿布}的组合。
到这里，你已经和我模拟了一遍整个 Apriori 算法的流程，下面我来给你总结下 Apriori 算法的递归流程：
K=1，计算 K 项集的支持度；
筛选掉小于最小支持度的项集；
如果项集为空，则对应 K-1 项集的结果为最终结果。
否则 K=K+1，重复 1-3 步。

Apriori 的改进算法：FP-Growth 算法

我们刚完成了 Apriori 算法的模拟，你能看到 Apriori 在计算的过程中有以下几个缺点：
可能产生大量的候选集。因为采用排列组合的方式，把可能的项集都组合出来了；
每次计算都需要重新扫描数据集，来计算每个项集的支持度。
所以 Apriori 算法会浪费很多计算空间和计算时间，为此人们提出了 FP-Growth 算法，它的特点是：
创建了一棵 FP 树来存储频繁项集。在创建前对不满足最小支持度的项进行删除，减少了存储空间。我稍后会讲解如何构造一棵 FP 树；
整个生成过程只遍历数据集 2 次，大大减少了计算量。
所以在实际工作中，我们常用 FP-Growth 来做频繁项集的挖掘，下面我给你简述下 FP-Growth 的原理。
1. 创建项头表（item header table）
创建项头表的作用是为 FP 构建及频繁项集挖掘提供索引。
这一步的流程是先扫描一遍数据集，对于满足最小支持度的单个项（K=1 项集）按照支持度从高到低进行排序，这个过程中删除了不满足最小支持度的项。
项头表包括了项目、支持度，以及该项在 FP 树中的链表。初始的时候链表为空。
2. 构造 FP 树
FP 树的根节点记为 NULL 节点。
整个流程是需要再次扫描数据集，对于每一条数据，按照支持度从高到低的顺序进行创建节点（也就是第一步中项头表中的排序结果），节点如果存在就将计数 count+1，如果不存在就进行创建。同时在创建的过程中，需要更新项头表的链表。
3. 通过 FP 树挖掘频繁项集
到这里，我们就得到了一个存储频繁项集的 FP 树，以及一个项头表。我们可以通过项头表来挖掘出每个频繁项集。
具体的操作会用到一个概念，叫“条件模式基”，它指的是以要挖掘的节点为叶子节点，自底向上求出 FP 子树，然后将 FP 子树的祖先节点设置为叶子节点之和。
我以“啤酒”的节点为例，从 FP 树中可以得到一棵 FP 子树，将祖先节点的支持度记为叶子节点之和，得到：
你能看出来，相比于原来的 FP 树，尿布和牛奶的频繁项集数减少了。这是因为我们求得的是以“啤酒”为节点的 FP 子树，也就是说，在频繁项集中一定要含有“啤酒”这个项。你可以再看下原始的数据，其中订单 1{牛奶、面包、尿布}和订单 5{牛奶、面包、尿布、可乐}并不存在“啤酒”这个项，所以针对订单 1，尿布→牛奶→面包这个项集就会从 FP 树中去掉，针对订单 5 也包括了尿布→牛奶→面包这个项集也会从 FP 树中去掉，所以你能看到以“啤酒”为节点的 FP 子树，尿布、牛奶、面包项集上的计数比原来少了 2。
条件模式基不包括“啤酒”节点，而且祖先节点如果小于最小支持度就会被剪枝，所以“啤酒”的条件模式基为空。
同理，我们可以求得“面包”的条件模式基为：
所以可以求得面包的频繁项集为{尿布，面包}，{尿布，牛奶，面包}。同样，我们还可以求得牛奶，尿布的频繁项集，这里就不再计算展示。

总结

今天我给你讲了 Apriori 算法，它是在“购物篮分析”中常用的关联规则挖掘算法，在 Apriori 算法中你最主要是需要明白支持度、置信度、提升度这几个概念，以及 Apriori 迭代计算频繁项集的工作流程。
Apriori 算法在实际工作中需要对数据集扫描多次，会消耗大量的计算时间，所以在 2000 年 FP-Growth 算法被提出来，它只需要扫描两次数据集即可以完成关联规则的挖掘。FP-Growth 算法最主要的贡献就是提出了 FP 树和项头表，通过 FP 树减少了频繁项集的存储以及计算时间。
当然 Apriori 的改进算法除了 FP-Growth 算法以外，还有 CBA 算法、GSP 算法，这里就不进行介绍。
你能发现一种新理论的提出，往往是先从最原始的概念出发，提出一种新的方法。原始概念最接近人们模拟的过程，但往往会存在空间和时间复杂度过高的情况。所以后面其他人会对这个方法做改进型的创新，重点是在空间和时间复杂度上进行降维，比如采用新型的数据结构。你能看出树在存储和检索中是一个非常好用的数据结构。
最后给你留两道思考题吧，你能说一说 Apriori 的工作原理吗？相比于 Apriori，FP-Growth 算法都有哪些改进？
欢迎你在评论区与我分享你的答案，也欢迎点击“请朋友读”，把这篇文章分享给你的朋友或者同事，一起来学习。
分享给需要的人，Ta购买本课程，你将得18元
生成海报并分享

赞 6

提建议

© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
上一篇
29丨EM聚类（下）：用EM算法对王者荣耀英雄进行划分
下一篇
31丨关联规则挖掘（下）：导演如何选择演员？
unpreview
 写留言

精选留言(30)

  • third
    置顶
    2019-02-20
    我也是自己的理解，不知道是否正确，给大家参考一下 构建子树 1.假设已经完成创建项头表的工作，省略count+1 2.扫描数据集，按照项头表排列好的结果，一次创建节点 3.因为尿布出现在所有订单中，没有例外情况，所以这只有一个子节点 4.因为牛奶出现在尿布中的所有订单里，所以只有一个子节点 5.由表中数据可得，在出现牛奶的订单中，面包出现的情况，分为两种， 1）出现3次面包，出现在有牛奶的订单中 2）出现一次面包，出现在没有牛奶的订单中 故，生成两个子节点 6.后续内容属于迭代内容，自行体会 3.创建条件模式集 是一个减掉子树过程。将祖先节点的支持度，记为叶子节点之和，减少频繁项集。 简单理解，就是有几个叶子，说明最开始的节点，怀了几个孩子，怀几个生几个 理解 1.创建含有啤酒的FP树，只有订单中含有啤酒的频繁项集才存在 2.去掉啤酒节点，品酒节点为空，得到，两个频繁项集 见图可理解 作业 1.工作原理 1）K=1，计算支持度 2）筛选小于最小支持度的项集 3）判断如果项集项集为空，K-1项集为最终结果 4）判断失败，K=K+1，重复1-3 2.优化 1）利用FP树和项头表，减少频繁项集的数量存储和计算
    展开

    编辑回复: 总结的不错，都可以看下。

    15
  • 王彬成
    2019-02-24
    简述FP-Growth 算法创建过程： 【1】创建项头表。 项 支持度 尿布 5 牛奶 4 面包 4 啤酒 3 【2】将数据集按照【尿布-牛奶-面包-啤酒】进行排序，得到 1）尿布、牛奶、面包 2）尿布、面包、啤酒、可乐 3）尿布、牛奶、啤酒、鸡蛋 4）尿布、牛奶、面包、啤酒 5）尿布、牛奶、面包、可乐 【3】构造FP树 1）遍历第1条数据，得到 尿布1 |牛奶1 |面包1 2）遍历第2条数据，得到 尿布2 |面包1 |啤酒1 |牛奶1 |面包1 3）遍历第3条数据，得到 尿布3 |面包1 |啤酒1 |牛奶2 |面包1 |啤酒1 4）遍历第4条数据，得到 尿布4 |面包1 |啤酒1 |牛奶3 |面包2 |啤酒1 |啤酒1 5）遍历第5条数据，得到 尿布5 |面包1 |啤酒1 |牛奶4 |面包3 |啤酒1 |啤酒1 【4】寻找条件模式基 1）以‘啤酒’为节点的链条有3条 -尿布1 |面包1 |啤酒1 -尿布1 |牛奶1 |面包1 |啤酒1 -尿布1 |牛奶1 |啤酒1 2）FP子树 尿布3 |面包1 |啤酒1 |牛奶2 |面包1 |啤酒1 |啤酒1 3）“啤酒”的条件模式基是取以‘啤酒’为节点的链条，取‘啤酒’往前的内容，即 -尿布1 |面包1 -尿布1 |牛奶1 |面包1 -尿布1 |牛奶1
    展开
    共 7 条评论
    64
  • 滨滨
    2019-04-06
    使用步骤图来解释FG-Growth算法https://www.cnblogs.com/zhengxingpeng/p/6679280.html
    共 6 条评论
    15
  • lipan
    2019-02-28
    k=2时，商品项集1,3的支持度是4/5啊
    共 1 条评论
    12
  • Sam.张朝
    2019-05-09
    https://www.ibm.com/developerworks/cn/analytics/library/machine-learning-hands-on2-fp-growth/index.html FP 还是这里说的清楚

    作者回复: 多谢分享

    9
  • Sam.张朝
    2019-05-09
    构造FP 树，看不懂
    共 2 条评论
    7
  • 曹恒源
    2019-04-08
    您好，陈哥，在文章中，k=2,（1,3）的支持度，不应该是4/5么？这部分的计算方式，不是（1,3）在总的购买的商品出现的次数除以总次数所得到的最后结果？
    7
  • leestar54
    2019-06-13
    为啥“啤酒“的条件模式基为空呢？图上祖先节点尿布:3的支持度=3/5大于0.5，这样啤酒的频繁项集可以得到{尿布，啤酒}
    共 3 条评论
    5
  • 白夜
    2019-02-21
    Apriori 的工作原理： 0.设置一个最小支持度， 1.从K=1开始，筛选频繁项集。 2.在结果中，组合K+1项集，再次筛选 3.循环1、2步。直到找不到结果为止，K-1项集的结果就是最终结果。 FP-Growth相比Apriori的优点： 降低了计算复杂度，只要遍历两次数据集。可以直接得到指定商品的条件模式基。
    展开

    编辑回复: 对的 是Apriori和FP-Growth的特点。

    4
  • Kai
    2020-11-28
    这篇文章只介绍了计算频繁项集的算法呀，具体提升度在计算完频繁项集后该怎么用能进一步解释一下吗
    2
  • lemonlxn
    2020-10-12
    商品相集 itemset，1、3 同时出现的支持度为 4/5，不是1/5，你把这个item给过滤了
    1
  • Ronnyz
    2019-11-21
    老师，想问下那置信度和提升度在Aproiri和FP-Growth算法中应用在哪了

    作者回复: 可以用于筛选，比如itemsets, rules = apriori(data, min_support=0.5, min_confidence=1)

    1
  • Sniper
    2019-08-16
    这个支持度 不应该是个小于1的百分比么，怎么到输出结果里面都变成具体的数字了，这些数字的大小怎么理解呢
    共 1 条评论
    2
  • 滨滨
    2019-04-06
    Apriori 的工作原理是根据排列组合来计算频繁项集，去掉低于阈值的，然后继续排列组合，直到频繁项集为空。FP-Growth 算法就是利用树来减少查询遍历的次数。
    1
  • 梁林松
    2019-02-28
    Apriori算法工作原理是通过计算子集的置信度来寻找频繁项集，从而确立关联。 PF-Growth算法是改进的 Apriori, 改进之处在于它是按照明确品类去计算频繁项目集的，而不是去求全部数据集的频繁项集。

    作者回复: 对的

    1
  • 李沛欣
    2019-02-26
    支持度：购买ABC这一商品组合，在所有商品组合中的出现概率 置信度：购买A商品的条件下，购买B商品的概率 提升度：购买A商品又购买B商品的概率，与所有购买了B商品的概率之比。也就是购买A商品对购买B商品的可能性提升能力。 提升度＞1，说明相互促进 等于1，没影响， ＜1，相互排斥
    展开
    1
  • ken
    2019-02-20
    Apriori挖掘频繁项集，那么置信度和提升度是对得出的频繁项集进行验证的是吧？如得出了啤酒的频繁项集后是对每个结果计算提升度，怎么选择最优的组合呢？是否会出现提升度大而置信度下降的情况？

    编辑回复: 置信度和提升度是对频繁项集的一种验证，在筛选最优组合的时候，一般会设置最小支持度，最小置信度，这样频繁项集和关联关系都要满足这个条件。提升度 (A→B)= 置信度 (A→B)/ 支持度 (B)，所以提升度是对满足前两者条件的另一种验证方式，这样避免一种情况：置信度(A->B)很高，是因为本身支持度(B)很高，实际上和A的出现关系不大。

    1
  • 开心小毛
    2022-08-01 来自美国
    请问老师：在“啤酒”的条件模式基中祖先节“尿布”的support为3，为啥“尿布”会被剪枝呢？3/5的订单数是大于0.5的最小支持度要求的不是么？
  • Longerian
    2021-11-17
    Apriori 算法咋看上去没有用到置信度，提升度这些指标，那前文介绍这些概念的目的是啥
  • McKee Chen
    2021-01-19
    Apriori算法的原理： 1. 输入数据集合D，支持度阈值α 2. 扫描整个数据集，得到所有出现过的数据，作为候选频繁1项集。K=1，频繁0项集为空集 3. 扫描数据计算候选频繁K项集的支持度 4. 去除候选频繁K项集中支持度低于阈值的数据集，得到频繁K项集。如果得到的频繁K项集为空，则直接返回频繁K-1项集的集合作为算法结果，算法结束。否则继续对K项进行计算，直到没有更新的频繁项集 Apriori算法和FP-Growth算法的区别： 1. Apriori算法需要对数据集进行多次扫描，而FP-Growth只需要扫描数据集两次 2. Apriori算法可能产生大量的候选集。而FP-Growth只需要创建FP树来储存频繁项集，并在创建前对不满足最小支持度的项进行删除
    展开

    作者回复: 加油 总结的不错