机器学习实战（十）Apriori详解

àì夳堔傛蜴生んèń 2021-10-30 02:10 760阅读 0赞

### 文章目录 ###

*   *  前言：
     *  一、关联分析
     *  二、频繁项集的评估标准
     *  三、关联规则发现
     *  四、先验原理
     *  五、Apriori算法思想
     *  六、Apriori算法流程
     *  七、Apriori算法总结

## 前言： ##

## 一、关联分析 ##

大型超市有海量的交易数据，作为精明的商家肯定不会放弃对这些海量数据的应用，他们希望通过对这些交易数据的分析，了解顾客的购买行为。我们可以通过聚类算法寻找购买相似物品的人群，从而为特定人群提供更具个性化的服务。但是对于超市来讲,更有价值的是找出商品之间的隐藏关联，从而可以用于商品定价、市场促销、存货管理等-系列环节，来增加营业收入。那如何从这种海量而又繁杂的交易数据中找出商品之间的关联呢?当然，你可以使用穷举法，但是这是一种十分耗时且计算代价高的笨方法，所以需要用更智能的方法在合理的时间范围内找到答案。因此,关联分析就此诞生了~

**1.简介**

**关联分析**(association analysis)是一种在大规模数据集中寻找有趣关系的非监督学习算法。这种关系可以有两种形式:频繁项集或者关联规则。

**频繁项集** (frequent item sets)是经常出现在一块的物品的集合，关联规则(association rules)暗示两种物品之间可能存在很强的关系。

关联分析的一一个典型例子是购物篮分析。下面我们一 起来看一个简单例子。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70]  
交易号码代表交易流水号，商品代表一个顾客一 次购买的全部商品。

**2.在这里需要明确几个定义:**

*  事务:每一条交易称为-一个事务。例如，在这个例子中包含了5个事务。
 *  项:交易的每一个物品称为一个项，例如豆奶、尿布等。
 *  项集:包含零个或者多个项的集合叫做项集，例如\{豆奶，莴苣。
 *  k-项集:包含k个项的项集叫做k-项集。 例如\{豆奶\}叫做1-项集, \{豆奶，尿布，啤酒\}叫做3-项集。
 *  前件和后件:对于规则\{尿布\}→>\{啤酒\}， \{尿布\}叫做前件，\{啤酒\}叫做后件。

## 二、频繁项集的评估标准 ##

频繁项集是经常出现在-块的物品的集合,那么问题就来了:第一,当数据量非常大的时候，我们无法凭肉眼找出经常出现在一起的物品，这就催生了关联规则挖掘算法，比如Apriori PrefixSpan、 CBA等。第二是我们缺乏一个频繁项集的标准。比如10条记录，里面A和B同时出现了三次，那么我们能不能说A和B-起构成频繁项集呢?因此我们需要一个评估频繁项集的标准。

常用的频繁项集的评估标准有支持度,置信度和提升度三个。

**1.支持度**

支持度就是几个关联的数据在数据集中出现的次数占总数据集的比重。或者说几个数据关联出现的概率。如果我们有两个想分析关联性的数据X和Y,则对应的支持度为:

![20190819154151817.png][]

比如上面例子中，在5条交易记录中\{尿布,睥酒\}总共出现了3次，所以

![20190819154304359.png][]

以此类推，如果我们有三个想分析关联性的数据X，Y和Z，则对应的支持度为:

![20190819154315955.png][]

一般来说，支持度高的数据不一定构成频繁项集，但是支持度太低的数据肯定不构成频繁项集。另外， 支持度是针对项集来说的，因此，可以定义一个最小支持度，而只保留满足最小支持度的项集，起到一个项集过滤的作用。

**2.置信度**

**置信度**体现了一个数据出现后，另一个数据出现的概率，或者说数据的条件概率。如果我们有两个想分析关联性的数据X和Y, X对Y的置信度为

![20190819163552962.png][]

比如上面例子中，豆奶对莴苣的置信度=豆奶和莴苣同时出现的概率/莴苣出现的概率,则有

![20190819154357303.png][]

也可以以此类推到多个数据的关联置信度，比如对于三个数据X，Y, Z,则X对于Y和Z的置信度为:

![20190819154410397.png][]

为什么使用支持度和置信度?支持度是一种重要度量，因为支持度很低的规则可能只是偶然出现。从商务角度来看，低支持度的规则多半也是无意义的，因为对顾客很少同时购买的商品进行促销可能并无益处。因此，支持度通常用来删去那些无意义的规则。此外，支持度还具有一-种期望的性质，可以用于关联规则的有效发现。

另一方面，置信度度量通过规则进行推理具有可靠性。对于给定的规则X-→Y,置信度越高，Y在包含x的事务中出现的可能性就越大。置信度也可以估计在给定X下的条件概率。  
同时，应当小心解释关联分析的结果。由关联规则作出的推论并不必然蕴涵因果关系。它只表示规则前件和后件同时出现的一种概率。

**3.提升度**

提升度表示含有Y的条件下同时含有X的概率，与X总体发生的概率之比，也就是X对Y的提升度与X总体发生的概率之比，即:

![20190819154459339.png][]

提升度体先了X和Y之间的关联关系，提升度大于1则X←Y是有效的强关联规则，提升度小于等于1则X←Y是无效的强关联规则。一个特殊的情况，如果X和Y独立，则有 L i f t ( X ← Y ) = 1 Lift(X←Y)= 1 Lift(X←Y)=1,因为此时 P ( X ∣ Y ) = P ( X ) P(X|Y)= P(X) P(X∣Y)=P(X)。

一般来说，要选择一个数据集合中的频繁数据集，则需要自定义评估标准。最常用的评估标准是用自定义的支持度，或者是自定义支持度和置信度的一个组合。

## 三、关联规则发现 ##

给定事务的集合T，关联规则发现是指找出支持度大于等于minsup并且置信度大于等于 m i n c o n f minconf minconf的所有规则，其中 m i n s u p minsup minsup和 m i n c o n f minconf minconf是对应的支持度和置信度阈值。挖掘关联规则的一种原始方法是:计算每个可能规则的支持度和置信度。但是这种方法的代价很高，令人望而却步，因为可以从数据集提取的规则的数目达指数级。更具体地说，从包含d个项的数据集提取的可能规则的总数为:

![2019081915491060.png][]

【公式证明过程】[可参考][Link 1]

对于我们前面聚德小例子，里面一共有6中商品，提取的可能规则数为:  3 8 − 2 7 + 1 = 602 3^8- 2^7+ 1= 602 38−27\+1=602,也就是说对于只有6种商品的小数据集都需要计算602条规则的支持度和置信度。使用 m i n s u p = 20 minsup= 20% minsup=20和 m i n c o n f = 50 minconf=50% minconf=50，80%以上的规则将被丢弃，使得大部分计算是无用的开销。为了避免进行不必要的计算，事先对规则剪枝，而无须计算它们的支持度和置信度的值将是有益的。

因此，大多数关联规则挖掘算法通常采用的-种策略是，将关联规则挖掘任务分解为如下**两个主要的子任务**。

*  **频繁项集产生:**

其目标是发现满足最小支持度阈值的所有项集，这些项集称作频繁项集(frequent itemset)。

*  **规则的产生:**

其目标是从上一步发现的频繁项集中提取所有高置信度的规则，这些规则称作强规则(strong rule)。

通常，频繁项集产生所需的计算开销远大于产生规则所需的计算开销。

最容易想到、也最直接的进行关联关系挖掘的方法或许就是暴力搜索（Brute-force）的方法：

*  List all possible association rules
 *  Compute the support and confidence for each rule
 *  Prune rules that fail the minsup and minconf thresholds

然而，由于Brute-force的计算量过大，所以采样这种方法并不现实！格结构（Lattice structure）常被用来枚举所有可能的项集。如下图所示为 I = a , b , c , d , e I=\{a,b,c,d,e\} I=a,b,c,d,e的项集格。一般来说，排除空集后，一个包含k个项的数据集可能产生 2 k − 1 2^k−1 2k−1个频繁项集。由于在实际应用中k的值可能非常大，需要探查的项集搜索空集可能是指数规模的。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 1]  
发现频繁项集的一种原始方法是确定格结构中每个候选项集（candidate itemset）的支持度计 数。为了完成这一任务，必须将每个候选项集与每个交易进行比较，如下图所示。如果候选项集包含在交易中，则候选项集的支持度计数增加。例如，由于项集\{Bread, Milk\}出现在事务1、4 和5中，其支持度计数将增加3次。这种方法的开销可能非常大，因为它需要进行 O ( N M w ) O(NMw) O(NMw)次比 较，其中 N N N是交易数， M = 2 k − 1 M=2^k−1 M=2k−1是候选项集数，而 w w w是交易的最大宽度（也就是交易中最大的项数）。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 2]  
我们必须设法降低产生频繁项集的计算复杂度。那有没有办法可以减少这种无用的计算呢?有。下面这两种方法可以降低产生频繁项集的计算复杂度:  
（1）减少候选项集的数目M。  
（2）减少比较次数。替代将每个候选项集与每个事务相匹配，可以使用高级的数据结构，或者存储候选项集或者压缩数据集，来减少比较次数。

## 四、先验原理 ##

在上一小节的末尾，我们已经看到Brute-force在实际中并不可取。我们必须设法降低产生频繁项集的计算复杂度。除了上面介绍的两种方法，此时我们可以利用支持度对候选项集进行剪枝，这也是Apriori所利用的第一条先验原理：

**Apriori定律1：** 如果一个集合是频繁项集，则它的所有子集都是频繁项集。

例如：假设一个集合\{A,B\}是频繁项集，即A、B同时出现在一条记录的次数大于等于最小支持度min\_support，则它的子集\{A\},\{B\}出现次数必定大于等于min\_support，即它的子集都是频繁项集。

例如：  
根据先验原理，假如\{1,2，3\}是频繁项集，那么它的所有子集（下图中橘色项集）一定也是频繁的。

![2019081916043749.png][]

**Apriori定律2：** 如果一个集合不是频繁项集，则它的所有超集都不是频繁项集。

举例：假设集合\{A\}不是频繁项集，即A出现的次数小于 min\_support，则它的任何超集如\{A,B\}出现的次数必定小于min\_support，因此其超集必定也不是频繁项集。

例如：

![20190819160457756.png][]

## 五、Apriori算法思想 ##

对于Apriori算法，我们使用**支持度来**作为我们判断频繁项集的标准。

Apriori算法的**目标**是找到**最大的K项频繁集**。这里有两层意思

**首先**，我们要找到符合支持度标准的频繁集。但是这样的频繁集可能有很多。

**其次**，就是我们要找到最大个数的频繁集。比如我们找到符合支持度的频繁集AB和ABE，那么我们会抛弃AB，只保留ABE，因为AB是2项频繁集，而ABE是3项频繁集。

那么具体的，Apriori算法是如何做到挖掘K项频繁集的呢？

**Apriori算法采用了迭代的方法**

*  先搜索出候选1项集及对应的支持度，剪枝去掉低于支持度的1项集，得到频繁1项集。
 *  然后对剩下的频繁1项集进行连接，得到候选的频繁2项集，筛选去掉低于支持度的候选频繁2项集，得到真正的频繁二项集。
 *  以此类推，迭代下去，直到无法找到频繁k+1项集为止，对应的频繁k项集的集合即为算法的输出结果。

可见这个算法还是很简洁的，第i次的迭代过程包括扫描计算候选频繁i项集的支持度，剪枝得到真正频繁i项集和连接生成候选频繁i+1项集三步。

**我们下面这个简单的例子看看：**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 3]  
我们的数据集D有4条记录，分别是134,235,1235和25。

现在我们用Apriori算法来寻找频繁k项集，最小支持度设置为50%。

首先我们生成候选频繁1项集，包括我们所有的5个数据并计算5个数据的支持度，计算完毕后我们进行剪枝，数据4由于支持度只有25%被剪掉。

我们最终的频繁1项集为1235，现在我们链接生成候选频繁2项集，包括12,13,15,23,25,35共6组。此时我们的第一轮迭代结束。

进入第二轮迭代，我们扫描数据集计算候选频繁2项集的支持度，接着进行剪枝，由于12和15的支持度只有25%而被筛除，得到真正的频繁2项集，包括13,23,25,35。

现在我们链接生成候选频繁3项集,123, 135和235共3组，这部分图中没有画出。

通过计算候选频繁3项集的支持度，我们发现123和135的支持度均为25%，因此接着被剪枝，最终得到的真正频繁3项集为235一组。

由于此时我们无法再进行数据连接，进而得到候选频繁4项集，最终的结果即为频繁3三项集235。

## 六、Apriori算法流程 ##

下面我们对Aprior算法流程做一个总结。

输入：数据集合D，支持度阈值α  
输出：最大的频繁k项集

1）扫描整个数据集，得到所有出现过的数据，作为候选频繁1项集。k=1，频繁0项集为空集。
    2）挖掘频繁k项集
    	a) 扫描数据计算候选频繁k项集的支持度
    	b) 去除候选频繁k项集中支持度低于阈值的数据集,得到频繁k项集。如果得到的频繁k项集为空，则直接返回频繁k-1项集的集合作为算法结果，算法结束。如果得到的频繁k项集只有一项，则直接返回频繁k项集的集合作为算法结果，算法结束。
    	c) 基于频繁k项集，连接生成候选频繁k+1项集。
    3） 令k=k+1，转入步骤2。

从算法的步骤可以看出，Aprior算法每轮迭代都要扫描数据集，因此在数据集很大，数据种类很多的时候，算法效率很低。

## 七、Apriori算法总结 ##

Aprior算法是一个非常经典的频繁项集的挖掘算法，很多算法都是基于Aprior算法而产生的，包括FP-Tree,GSP, CBA等。这些算法利用了Aprior算法的思想，但是对算法做了改进，数据挖掘效率更好一些，因此现在一般很少直接用Aprior算法来挖掘数据了，但是理解Aprior算法是理解其它Aprior类算法的前提，同时算法本身也不复杂，因此值得好好研究一番。

Apriori算法的缺点：

(1)由频繁k-1项集进行自连接生成的候选频繁k项集数量巨大。  
(2)在验证候选频繁k项集的时候需要对整个数据库进行扫描，非常耗时。

网上提到的频集算法的几种优化方法：

1.  基于划分的方法。
2.  基于hash的方法。
3.  基于采样的方法。
4.  减少交易的个数。

**参考文档：**

\[1\]《机器学习实战》Peter Harrington著

\[2\] https://www.bilibili.com/video/av40186599?t=67

\[3\] https://blog.csdn.net/baimafujinji/article/details/53456931

\[4\] https://www.cnblogs.com/pinard/p/6293298.html

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70]: /images/20211029/7b6882c00fa74494b3fd52a0bfaf9a2a.png
[20190819154151817.png]: /images/20211029/a1c61452348c4cfebcf9b4cbddc89ad7.png
[20190819154304359.png]: /images/20211029/b3ff98b154bf40f1a074b5bb6094f7b1.png
[20190819154315955.png]: /images/20211029/46f76bfbbc024aa5b644b9ca77f385b0.png
[20190819163552962.png]: /images/20211029/88809b2f2e0f456caa3412fac78c7946.png
[20190819154357303.png]: /images/20211029/cd163a60eb3040f990b103657cc57a2e.png
[20190819154410397.png]: /images/20211029/28c364b476e6427283d90e15a518e6a9.png
[20190819154459339.png]: /images/20211029/ed105cda54d64f0b8a92a8577b2d5930.png
[2019081915491060.png]: /images/20211029/2406c4265c7148979c06fa4cdb7dd0b2.png
[Link 1]: https://blog.csdn.net/wxbmelisky/article/details/48268833
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 1]: /images/20211029/6affb6bf29324a9192d9f6fffd8adcab.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 2]: /images/20211029/6b9457a75844498d94419a5e54886db9.png
[2019081916043749.png]: /images/20211029/3e10c9432fae4958bd6e61ede7ac6d34.png
[20190819160457756.png]: /images/20211029/a1a007dfb2294361954bc32b6a6ede55.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 3]: /images/20211029/caae9e9997264b438c7292eaf84542dc.png