数据挖掘-Apriori算法

迈不过友情╰ 2021-09-21 13:22 607阅读 0赞

## **微信搜索：“二十同学” 公众号，欢迎关注一条不一样的成长之路** ##

**引子：啤酒与尿布**

据说这是一个真实的案例：沃尔玛在分析销售记录时，发现啤酒和尿布经常一起被购买，于是他们调整了货架，把两者放在一起，结果真的提升了啤酒的销量。后来还分析背后的原因，说是因为爸爸在给宝宝买尿布的时候，会顺便给自己买点啤酒……这已经成为了数据挖掘领域的一个经典桥段，甚至被维克托•迈尔•舍恩伯格在2012年最火爆的《大数据时代》中大书特书……这个故事我们权当是真的，不过今天是要看看它背后的细节，也就是关联分析（或者直接成为购物篮分析）

**一、关联分析中的若干概念**

关联规则就是说，如果顾客买了啤酒，那么很可能他也会买尿布，我们在这表示为【啤酒-->尿布】。

关联规则背后的数学原理是很简单的，就是古典概率，大家都能够理解。比如，如果我们想看看【啤酒-->尿布】这个规则是不是存在，那么首先就要看看，有多大的概率，人们既买了啤酒，也买了尿布。为了更好的说明问题，我们伪造一个例子：

借用当下比较火的一个电影中的人物，在一个小卖部中有4种商品，这几位分别买了不同的东西，1表示买，0表示没有买。

![010410c2d222810bf877ca8785d0dc7c.webp][]

虚拟购物篮

我们的例子中，六爷、闷三儿、洋火儿这老哥儿仨是一起买了啤酒和尿布，我们一共假定了八位人物，因此，同时购买啤酒和尿布的概率就是3/8，这就是古典概率中计算概率的方法，在关联规则中，这个概率叫做这条规则的**“****支持度（Support）”，**表示同时购买啤酒和尿布的顾客在所有顾客当中的覆盖范围。

虽然我们现在知道，啤酒和尿布，经常一起出现，但是是不是买了啤酒的就一定买尿布呢？这里又要从另外一个角度来看，那就是，对于所有买了啤酒的人，有多大的可能性买尿布。买啤酒的人包括六爷、闷三儿、灯罩儿、洋火儿、小飞，一共五位。这五位中，六爷、闷三儿、洋火儿买了尿布，所以，在购买了啤酒的前提下，买尿布的概率是3/5。这个概率其实是古典概率中的条件概率，在关联分析中叫做关联规则【啤酒-->尿布】的**“置信度（Confidence）”，**表示可预测的程度，即顾客购买啤酒的话有多大可能性买尿布。

现在，看来【啤酒-->尿布】这条规则应该可以促进尿布销售啊，应该在结账的时候，让收银员对买了啤酒的人都问：“这位爷，您要来包儿日本原装进口花王纸尿裤吗？”。这时候问题来了：我利用这条规则，是想促进尿布的销售，但是只对买啤酒的人促销是不是合理呢？

回到我们的表格从整体来看，购买尿布的一共有四位，也就是说，人们逛这个小卖部有4/8的几率会购买尿布，是在纯天然条件下，尿布销售的概率。当利用了关联规则【啤酒-->尿布】，理论上尿布销售的概率为3/5，大于4/8，所以我们认为这条规则是有效的，有一个评价指标叫**“提升度（Lift）”，**就是用3/5除以4/8，为6/5，通俗解释就是利用关联规则后一种东西的卖出概率除以纯天然环境下卖这样东西的概率。

如果Lift>1，证明这个规则是有确实提升作用的，是有效的；

如果<1，说明不用这个规则，卖东西的概率更高，规则还不如不用；

如果=1，说明有没有规则，对卖东西的概率没影响。

其实就关联规则的日常应用来说，即使不知道算法细节，了解了Support、Confidence和Lift就可以利用分析工具开展分析工作了，在分析中需要手工定义最小支持度和最小置信度（当然一般工具中也都有默认值），**满足最小支持度和最小置信度的规则，叫做“强关联规则”，**然后，“强关联规则”中也分有效和无效，如果Lift（X-->Y）>1，则规则“X-->Y”是**有效**强关联规则，如果Lift（X--Y)<=1，则规则“X-->Y”是**无效**强关联规则。

**关联分析，就是从大量的销售记录中，通过算法，找出所有的有效强关联规则的过程**

Support是第一个门槛，考察关联规则在“量”上的多少，剔除出镜率较低的购买组合

Confidence是第二个门槛，考察关联规则在“质”上的可靠性

Lift是第三个门槛，是基于Confidence的指标，考察关联规则的有效性

支持度和置信度这两个指标的设置是很见功夫的。支持度很低，说明在整个的购买行为中覆盖范围很小，即使置信度很高，也可能是一种偶然的行为。支持度设置的很高，说明覆盖范围很大，但有可能会发现一些常识性的结论，比如买手机的用户很有可能买手机壳，这种规则就不要费力气挖掘了……直接凭常识都知道。所以关联规则的使用和其他的数据挖掘方法一样，一定要结合业务知识，一定要有业务专家的支持。

补充一点是，一些微软开发的数据挖掘工具中，Confidence称为Probobility，同时还引入一个类似于Lift的概念叫做Importance，但是不知道具体的计算方法。

**二、关联分析的过程和Apriori算法**

根据上面的分析，关联分析的过程为：

1. 设定最小支持度和置信度

2. 找出满足最小支持度的购买组合（术语叫**频繁项集**）

3. 对于第二步中的每一个购买组合，找到满足最小置信度的关联规则

4. 验证关联规则的有效性

最基本最著名的关联规则算法是Apriori算法，这个算法用来找到所有频繁项集。这个算法背后的思想是集合论，证明虽然不长，但是牵扯到太多的数学了，不讲了。下面只手工执行以下这个算法，把我们例子做一下，领略一下Apriori算法的执行过程：

**步骤1：设定Support和Confidence**

我们设定支持度30%，置信度70%。（人为设定）

**步骤2：计算满足支持度的购买组合（及计算频繁项集）**

首先计算只有一个商品的购买组合：【啤酒】【尿布】【PM2.5口罩】【iPhone 6S】，这几个分别出现了5，4，5，2次，因此【iPhone 6S】的支持度为2/8，被剔除，剩下的为【啤酒】【尿布】【PM2.5口罩】

然后计算两个商品的购买组合：要基于上一步的结果，把剩下的三样两两组合【啤酒、尿布】【啤酒、PM2.5口罩】【尿布、PM2.5口罩】，这三个组合分别出现了3、3、2次，淘汰最后一个，剩下【啤酒、尿布】【啤酒、PM2.5口罩】

然后计算三个商品的购买组合：基于上一步结果，三样商品只能有一个组合【啤酒、尿布、PM2.5口罩】，在表格中出现了2次，淘汰

最终得到的满足最小支持度的购买组合为【啤酒】【尿布】【PM2.5口罩】【啤酒、尿布】【啤酒、PM2.5口罩】

*注：由于我懒得写太多，所以故意把例子搞得很简单，感觉像把所有可能情况全部列出来，再用支持度筛选……但其实Apriori算法在每一步组合时候，先对上一步的每个组合排序，然后只合并除了最后一个元素不同，其他元素相同的组合*

*假如计算出包含三个商品的购买组合为\{1，2，3\}，\{1，3，4\}，\{1，2，6\}，那么\{1，2，3\}和\{1，2，6\}只有最后一个元素不同，可以两两组合成四个元素的购买组合\{1，2，3，6\}，然后进行支持度判断；\{1，3，4\}可以不用管，因为它最后一个和倒数第二个元素和其他两个都不一样。为啥能这么搞呢？背后都是有强大的数学证明的，Apriori也是这么实现的。*

**步骤3：生成关联规则，判断置信度**

下一个步骤，就是利用找到的购买组合，生成规则。只有一个商品的很明显不可能有任何规则，所以只需要考虑【啤酒、尿布】【啤酒、PM2.5口罩】。

生成规则最一般的方法就是穷举法（也有一些优化过的方法，不过程Sir没有研究），一共有【啤酒-->尿布】【尿布-->啤酒】【啤酒-->PM2.5口罩】【PM2.5口罩-->啤酒】四个规则需要用置信度判断。（如果是三个商品的，比如【1，2，3】，那就是【1，2-->3】【1，3-->2】【2，3-->1】【3-->1，2】【2-->1，3】【1-->2，3】）

【啤酒-->尿布】，置信度3/5，小于70%，淘汰

【尿布-->啤酒】，置信度3/4，大于70%，保留

【啤酒-->PM2.5口罩】，置信度3/5，小于70%，淘汰

【PM2.5口罩-->啤酒】，置信度3/5，小于70%，淘汰

**步骤4：计算Lift，验证有效性**

最后验证有效性，自然条件下，买啤酒的概率为5/8，小于【尿布-->啤酒】的置信度3/4，可以算出Lift为6/5=1.2，是一条“有效的强关联规则”。

因此，对于这个例子来说，在设定的30%支持度和70%置信度的水平下，我们挖掘出了一条规则：【尿布-->啤酒】

**三、其他关联分析的算法**

各种关联分析算法的核心都是快速的找出所有的频繁项集，Apriori算法需要对数据库进行多次扫描，同时产生大量的候选频繁集，这就使Apriori算法时间和空间复杂度较大。后来，伊利诺伊大学的华裔数据科学家Jiawei Han（韩家炜）老爷爷在2000年提出了FP-growth算法，利用一个叫做频繁模式树（FP-tree）的数据结构，加快了数据挖掘的速度。这里提一句，Jiawei Han老爷爷写了一本大部头重量级著作，号称是数据挖掘领域里程碑意义的经典著作。

![b22e653b639a87451c64ffb8e85ff12e.webp][]

图片来自京东网站

FP-growth算法比Apriori算法快一个数量级，在空间复杂度方面也比Apriori也有数量级级别的优化。但是对于海量数据，FP-growth的时空复杂度仍然很高，可以采用的改进方法包括数据库划分，数据采样等等。

**四、关联分析的应用领域**

很多很多领域都可以应用，电商推荐系统、交叉销售、商品目录的设计、商品货架摆放等，就我本身所从事的电信行业来说，运营商可根据用户的APP安装和使用情况，挖掘关联规则，提升自有互联网业务和流量包业务的订购量

**五、啤酒与尿布其实只是一个传说**

看起来最靠谱的“啤酒与尿布”的起源，来自 KDnuggets News 00:13, item 23, Publications：

> *The "diapers and beer" example was created by Tom Blishok who ran a retail consulting group for NCR.  They first did market basket forOsco Drugs in Chicago.  This pre-dated commercial availability of associations algorithms (1992?).  Tom had a team of a half dozen or so SQL hackers (I know a couple of them) creating queries that defined affinities that theythought might be in the data.  They found "cosmetics and greeting cards" and a few others.*
> 
> In the process of Tom creating materials for NCR to make the argument for why you want to house transaction data he needed a snappy example, so**he dreamed up the "diapers and beer" example**.  To the best of my knowledge it was never supported in any data that they analyzed.  Tom's original example had "diapers and beer" appearing in C-Store data which,**to the best of my knowledge, they never analyzed at the transaction level.**
> 
> It's still a nice example, of course.  As they say, never let truth get in the way of a good story.

虽然“啤酒与尿布”的故事是假的，但并不是说关联分析本身是毫无价值的。这个故事成为了传播数据挖掘理念的重要的案例，同时，上文中提到的NCR后来分离出了大名鼎鼎的Teradata，直到今天也是数据挖掘领域的主要玩家之一，尤其在电信领域。

**尾声：**

其实我很喜欢最后这句话，**never let truth get in the way of a good story. **

非常感谢：**点赞**、**收藏**和**评论**

**微信搜索：“二十同学” 公众号，或者直接扫一扫，关注一条不一样的成长之路**

![20201202173850460.jpg][]

[010410c2d222810bf877ca8785d0dc7c.webp]: /images/20210920/390c25cc153c4fe7978e9818b951aab4.png
[b22e653b639a87451c64ffb8e85ff12e.webp]: /images/20210920/ebbf9f3ddc214f7eb0489be53957e921.png
[20201202173850460.jpg]: /images/20210920/6ae3689b21204f3095ab68fb81d6edd7.png