数据挖掘算法09 - Apriori

桃扇骨 2022-04-25 10:10 256阅读 0赞

## Apriori ##

关联规则挖掘可以让我们从数据集中发现项与项（item 与 item）之间的关系，它在我们的生活中有很多应用场景，“购物篮分析”就是一个常见的场景，这个场景可以从消费者交易记录中发掘商品与商品之间的关联关系，进而通过商品捆绑销售或者相关推荐的方式带来更多的销售量。所以说，关联规则挖掘是个非常有用的技术。

> 知识点

*  搞懂关联规则中的几个重要概念：支持度、置信度、提升度；
 *  Apriori 算法的工作原理；
 *  熟悉与掌握 Apriori 工具包的使用；
 *  在实际工作中，我们该如何进行关联规则挖掘。
 *  在实际问题中，灵活运用。包括数据集的准备等。

> 什么是支持度呢？

支持度是个百分比，它指的是某个商品组合出现的次数与总次数之间的比例。支持度越高，代表这个组合出现的频率越大。

> 什么是置信度呢？

它指的就是当你购买了商品 A，会有多大的概率购买商品 B。

所以说**置信度是个条件概念**，就是说在 A 发生的情况下，B 发生的概率是多少。

> 什么是提升度呢？

提升度 (A→B)= 置信度 (A→B)/ 支持度 (B)

这个公式是用来衡量 A 出现的情况下，是否会对 B 出现的概率有所提升。

所以提升度有三种可能：

*  提升度 (A→B)>1：代表有提升；
 *  提升度 (A→B)=1：代表有没有提升，也没有下降；
 *  提升度 (A→B)<1：代表有下降。

> Apriori 的工作原理

Apriori 算法其实就是**查找频繁项集 (frequent itemset) 的过程**，所以首先我们需要定义什么是频繁项集。

频繁项集就是支持度大于等于最小支持度 (Min Support) 阈值的项集，所以小于最小值支持度的项目就是非频繁项集，而大于等于最小支持度的项集就是频繁项集。

到这里，你已经和我模拟了一遍整个 Apriori 算法的流程，下面我来给你总结下 Apriori 算法的递归流程：

*  K=1，计算 K 项集的支持度；
 *  筛选掉小于最小支持度的项集；
 *  如果项集为空，则对应 K-1 项集的结果为最终结果。

否则 K=K+1，重复 1-3 步。

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

*  可能产生大量的候选集。因为采用排列组合的方式，把可能的项集都组合出来了；
 *  每次计算都需要重新扫描数据集，来计算每个项集的支持度。

所以 Apriori 算法会浪费很多计算空间和计算时间，为此人们提出了 FP-Growth 算法，它的特点是：

*  创建了一棵 FP 树来存储频繁项集。在创建前对不满足最小支持度的项进行删除，减少了存储空间。我稍后会讲解如何构造一棵 FP 树；
 *  整个生成过程只遍历数据集 2 次，大大减少了计算量。

所以在实际工作中，我们常用 FP-Growth 来做频繁项集的挖掘，下面我给你简述下 FP-Growth 的原理。

*  创建项头表（item header table）

创建项头表的作用是为 FP 构建及频繁项集挖掘提供索引。

这一步的流程是先扫描一遍数据集，对于满足最小支持度的单个项（K=1 项集）按照支持度从高到低进行排序，这个过程中删除了不满足最小支持度的项。

项头表包括了项目、支持度，以及该项在 FP 树中的链表。初始的时候链表为空。

*  构造 FP 树

FP 树的根节点记为 NULL 节点。

整个流程是需要再次扫描数据集，对于每一条数据，按照支持度从高到低的顺序进行创建节点（也就是第一步中项头表中的排序结果），节点如果存在就将计数 count+1，如果不存在就进行创建。同时在创建的过程中，需要更新项头表的链表。

*  通过 FP 树挖掘频繁项集

到这里，我们就得到了一个存储频繁项集的 FP 树，以及一个项头表。我们可以通过项头表来挖掘出每个频繁项集。

具体的操作会用到一个概念，叫“条件模式基”，它指的是以要挖掘的节点为叶子节点，自底向上求出 FP 子树，然后将 FP 子树的祖先节点设置为叶子节点之和。

> 如何使用 Apriori 工具包

$ pip install efficient-apriori

> 挖掘导演是如何选择演员的

*  在实际工作中，数据集是需要自己来准备的，比如今天我们要挖掘导演是如何选择演员的数据情况，但是并没有公开的数据集可以直接使用。因此我们需要使用之前讲到的 Python 爬虫进行数据采集。
 *  有了数据之后，我们就可以用 Apriori 算法来挖掘频繁项集和关联规则

> Apriori 算法中的最小支持度和最小置信度，一般设置为多少比较合理？

**和数据集特点有关系**，不过数据集大的情况下，不好观察特征。我们可以通过设置最小值支持度和最小置信度来观察关联规则的结果。

一般来说最小支持度常见的取值有0.5，0.1，0.05。最小置信度常见的取值有1.0，0.9，0.8。可以通过尝试一些取值，然后观察关联结果的方式来调整最小值尺度和最小置信度的取值。

> 总结

今天我给你讲了 Apriori 算法，它是在“购物篮分析”中常用的关联规则挖掘算法，在 Apriori 算法中你最主要是需要明白支持度、置信度、提升度这几个概念，以及 Apriori 迭代计算频繁项集的工作流程。

Apriori 算法在实际工作中需要对数据集扫描多次，会消耗大量的计算时间，所以在 2000 年 FP-Growth 算法被提出来，它只需要扫描两次数据集即可以完成关联规则的挖掘。FP-Growth 算法最主要的贡献就是提出了 FP 树和项头表，通过 FP 树减少了频繁项集的存储以及计算时间。

当然 Apriori 的改进算法除了 FP-Growth 算法以外，还有 CBA 算法、GSP 算法，这里就不进行介绍。

![c7aee3b17269139ed3d5a6b82cc56735.png][]

Apriori 算法的**核心**就是**理解频繁项集和关联规则**。在算法运算的过程中，还要重点掌握对支持度、置信度和提升度的理解。在工具使用上，你可以使用 efficient-apriori 这个工具包，它会把每一条数据中的项（item）放到一个集合（篮子）里来处理，不考虑项（item）之间的先后顺序。

![282c25e8651b3e0b675be7267d13629d.png][]

[c7aee3b17269139ed3d5a6b82cc56735.png]: /images/20220125/61b88d2e86e54fc68ba3a06a20d2288d.png
[282c25e8651b3e0b675be7267d13629d.png]: /images/20220125/01cedcf1eba24e809ecd1ca5d5ce1dd8.png