深入浅出关联规则挖掘和Apriori算法

2020-05-14

引言

超市的经营管理者时常遇到这样的问题:哪些商品经常被同时销售,哪些商品搭配起来销售能提示销售额?网络书店(如亚马逊、京东)也会希望知道:买了A这本书的人还买了哪些书,如果知道买了A这本书的人还买了B,C和D,那么下次再有人购买A,便可以向其推荐B,C和D从而得以提示销售额,进而提升总体利润.

京东在我浏览三阶魔方商品后给我推荐更多魔方

京东在我浏览三阶魔方商品后给我推荐更多魔方

如图,顾客在电商购物App上的一次浏览记录可以看做是一个交易,很显然浏览了三阶魔方的顾客也很有可能会再去浏览二阶魔方或者四阶魔方,那么

{ 三阶魔方 } -> { 二阶魔方 }

就可以看做是一条规则,表示看了三阶魔方的人很有可能再去看二阶魔方,因此在顾客浏览了三阶魔方的商品页面后像其推荐二阶魔方是合理的.

类似地,还有

书籍推荐

书籍推荐

浏览了《机器学习》的顾客也很有可能再去浏览《深度学习》和《机器学习实战》,因而有如下的规则

{ 机器学习 } -> { 深度学习, 机器学习实战 }

以上举了两个例子关于关联规则挖掘方法在商品推荐这方面的应用.

关联规则

这样的问题可被抽象为一般的问题,在数据挖掘领域中这类问题叫做关联规则挖掘问题,其中,一位顾客一次购物的购物单上的商品组合被称作一个交易(Transation),例如,一个顾客在一次购物中买了书本A,B,和C,那么这次交易可以记做

$$ \{ A, B, C \} $$

如果另外一位顾客买了B和C,那么这条交易可以写作

$$ \{ B, C \} $$

所有顾客的所有交易的集合被称作「数据集」(Dataset),数据集其实就是购物小票的集合,例如

$$ ( \{ A, B, C \}, \{B, C \}) $$

就是一个数据集.而一个超市销售的所有商品,就被称作「项集」(Itemset) 或者「商品集」,例如,这家超市都销售哪些商品,项集就是什么,例如,假如说这家超市不仅销售A,B,和C,还销售D和E,那么项集就可以记做

$$ \{A, B, C, D, E \} $$

很显然,交易(Transaction)都是且必须是项集的子集,因为你不可能在超市买到超市根本没在卖的商品,那么,交易到交易的一个关联,或者说,项集的一个子集X到项集的另一个子集Y的关联,其中Y不能是X的子集

$$ X \rightarrow Y $$

就称作一条规则,含义就是,买了X的人也很有可能会再去买Y,例如,如果有这样一条规则

$$ \{A, C \} \rightarrow \{B \} $$

就说明,同时买了A商品和C商品的人,往往也更倾向于买B,或者有很大的可能还顺便买B,说明这些商品是很容易同时出现在购物小票上的.

一般来说,人们对数据进行关联规则挖掘一般是想从数据集,也就是所有交易记录(销售记录)当中,找到这些规则

$$ X_1 \rightarrow Y_1 \\
X_2 \rightarrow Y_2 \\
X_3 \rightarrow Y_3 \\
\cdots $$

从而当有人买了$X_1$的时候就可以给他推荐$Y_1$,当有人买了$X_2$的时候给他推荐$Y_2$等等,从而提升销售额和总体利润.

而事实上,同时出现在购物小票中的商品组合有很多种,电池和面包可能出现在同一张购物小票中,而面包和黄油也可能同时出现在一张购物小票中,但显然,面包和黄油同时出现的次数,肯定会比电池和面包同时出现的次数更加多.因而,我们就有了「频繁集」的概念,其实很简单,频繁集就是经常出现在一起的商品的组合,例如

{ 面包, 黄油 }

一般都可以看做是一个频繁集,而

{ 电池, 面包 }

同时出现的次数一般比较少,因而不能看做是一个频繁集,具体来说呢,一个商品组合频不频繁要看这个商品组合的支持度,假如说,我们的数据集是这样子的

交易编号 商品组合
1 黄油、果酱、面包
2 黄油、面包
3 面包、果酱
4 电池、面包
5 果酱

那么

{ 面包, 黄油 }

作为频繁集,它的「频繁的程度」,也就是它的支持度(Support),是2/5,因为,在5次交易中,面包和黄油同时出现了2次,分别对应编号为1和编号为2的交易,同理,我们还可以数电池和面包同时出现的次数以此计算

{ 电池, 面包 }

的支持度,很明显是1/5,因为在5次交易中只出现了1次,我们看到还有果酱和黄油,那么,果酱作为频繁集

{ 果酱 }

它的支持度是3/5,因为它在编号为1,3,和5的交易中出现了.而

{ 面包 }

的支持度是4/5,因为它出现在了编号为1,2,3,4的交易中.一般的,对每一个项集的子集,我们都可以从数据集中算出它的支持度,很简单,就是数包含这个子集的交易的个数再除以总的交易次数.类似地,我们还可以对一条规则计算支持度,一条规则,例如说,可以说

{ 面包, 黄油 } -> { 果酱 }

表示买了面包和黄油的顾客也可能再去买果酱,那么,要计算这条规则的支持度,我们只需把箭头左右两边的集合合并,得到

{ 面包, 黄油, 果酱 }

然后再计算这个并集的支持度即可,和上面是一样的,这里呢,这三个商品同时出现了1次,总共由5条交易,因而这条规则

{ 面包, 黄油 } -> { 果酱 }

的支持度是1/5,并且,显然,

{ 果酱 } -> { 面包, 黄油 }

的支持度也是1/5.支持度仅仅给了一条规则最基本的存在感,但还不足以表示一条规则的强度,因为支持度主要和箭头左右两边的商品组合同时出现的次数相关,但是,显然买了面包再去买黄油,和买了黄油再去买面包这两条规则是有些不同的,返回去看我们的数据集,有3条交易出现了果酱,出现了果酱的这3条交易中,其中有1条同时包含果酱、面包和黄油,我们这时就说

{ 果酱 } -> { 面包, 黄油 }

这条规则的「置信度」(Confidence)是1/3,置信度表示这条规则多「可信」,多「可靠」,多「应验」,因而能够表示规则本身的强度,而反过来,我们可以计算

{ 面包, 黄油 } -> { 果酱 }

的置信度,显然,在数据集中,有2次交易出现了面包和黄油,在这2次交易中,其中有1次交易还出现了果酱,因而,这条规则的置信度是1/2,很显然,一般情况下,规则

X -> Y

和规则

Y -> X

是不同的,虽然有着相同的支持度,但它两的置信度不总是相同.

除了支持度和置信度,还有一个描述规则的数量叫做「提升」(Lift),提升主要是表示这条规则,假如实施起来,估计会有多大的意义,假如说我们有商品(组合)A和商品(组合)B,其中A和B可以是单件商品也可以是商品的组合,只要A和B不一样,假如说顾客购买商品A这个事件,和顾客购买商品B这个事件是相互独立的,那么,顾客同时买A和B的概率就是$Pr(A) Pr(B)$,假如说我把两个商品做成一个组合$\{A,B\}$,那么顾客同时买这两个商品的概率就等于买这个商品组合的概率$Pr(\{A,B\})$,我们把

$$ \frac{Pr(\{A, B\})}{Pr(A)Pr(B)} $$

就叫做一条规则$A \rightarrow B$的提升,回顾我们的数据集,我们可以计算

{ 面包, 黄油 } -> { 果酱 }

这条规则的提升,其中,

{ 面包, 黄油 }

出现了2次,而

{ 果酱 }

出现了3次,另外,

{ 黄油, 面包, 果酱 }

仅同时出现了1次,那么,提升就是

$$ \frac{1/5}{(2/5) \times (3/5)} = \frac{5}{6} < 1 $$

说明,把面包、黄油和果酱摆在一块儿对于提升黄油和面包的销量并没有明显的效果.

Apriori算法

给定一个包含若干条交易记录的数据集$D = \{T_1, T_2, \cdots, T_N\}$,给定最小支持度$\sigma \in (0, 1)$,最小置信度$\phi \in (0, 1)$,Apriori算法可以指导我们如何:

1.从数据集$D$中找出所有支持度不小于最小支持度$\sigma$的频繁集 2.从符合条件的所有频繁集中找出所有置信度不小于最小置信度$\phi$的所有规则

具体地,Apriori算法先找出所有频繁集,然后再从频繁集中找出置信度大于给定置信度的规则集,而Apriori算法寻找频繁集的过程,是从底部开始逐渐向越来越大的频繁集构造的.光说可能不容易理解,下面,让我们举几个具体的例子吧.

假定我们的数据集有如下交易

交易编号 购买的商品
1 {A,B,C}
2 {A,C,D}
3 {B,C,D,E}
4 {A,C,D,E}
5 {B,C,E}

我们打算运用Apriori算法从该数据集中找出所有支持度不小于1/5的频繁集.首先,可以从数据集中得出项集,也就是所有商品的集合,很显然是{A, B, C, D, E},然后,我们设定最小支持度为1/5,最小置信度为1/2,要先找到所有支持度大于1/5的频繁集,然后再从这些频繁集中导出置信度大于1/2的规则.

第一页

第一页

如图,我们首先尝试构造长度为1的频繁集的候选集,很显然,这里每个长度为1的候选集计算出来的支持度都比较大,都大于1/5,因而这些长度为1的候选集都可以作为长度为1的频繁集拿去构造长度为2的候选集.下边,也就是步骤2,我们写出了所有长度为2的候选集,其中,有几个支持度刚好为1/5,因而也就淘汰掉了,留下的可用的频繁集记在箭头右边.

接下来我们将尝试去构造长度为3的频繁集,注意了,长度为3的频繁集的任何子集的支持度必定要大于1/5,否则,因为随着集合的长度越大支持度越小,所以,如果子集的支持度不大于1/5,那么构造得到更长的集合的支持度也肯定不大于1/5,因此,长度为3的频繁集不妨从长度为2的频繁集作为子集开始构造.

第二页

第二页

如图,我们先枚举所有可能的长度为3的频繁集,即长度为3的候选集,然后分别计算支持度,取支持度大于2/5的,这样,我们就得到了所有长度为3的频繁集.很显然,并没有支持度大于1/5的长度为4的候选集,因而没有长度为4的频繁集,因此,寻找频繁集的步骤到此结束,接下来可以开始从所有频繁集中导出可用的规则了,我们设定的是要求所有规则的置信度都大于1/2.

对每一个频繁集,我们遍历它的每一个真子集,对每一个真子集,这个真子集到原集与这个真子集的除集的关联就是一个备选规则,可以拿来计算置信度,然后如果置信度大于1/2则考虑,不大于1/2则不考虑.例如{A,C}是{A,C,D}的一个真子集,而{D}是{A,C}对{A,C,D}的除集,因而{A,C}->{D}是一条备选规则,并且,它的置信度显然等于sup{A,C,D}/sup{A,C}.

第三页

第三页

第四页

第四页

就这样,如图所示,我们就找出了所有可用的规则,可以看到满足置信度大于1/2的规则还是非常之多的.现做一个总结,我们找出了以下频繁集:

频繁集 支持度
------------
{A} 3/5
{B} 3/5
{C} 5/5
{D} 3/5
{E} 3/5
{A, C} 3/5
{A, D} 2/5
{B, C} 3/5
{C, D} 3/5
{C, E} 3/5
{D, E} 2/5
{B, E} 2/5
{A, C, D} 2/5
{B, C, E} 2/5
{C, D, E} 2/5

以及以下置信度大于1/2的规则

规则 置信度
----------
{A, C} -> {D} 2/3
{A, D} -> {C} 1
{C, D} -> {A} 2/3
{D} -> {A, C} 2/3
{B, C} -> {E} 2/3
{B, E} -> {C} 1
{C, E} -> {B} 2/3
{B} -> {C, E} 2/3
{E} -> {B, C} 2/3
{C, D} -> {E} 2/3
{C, E} -> {D} 2/3
{D, E} -> {C} 1
{D} -> {C, E} 2/3
{E} -> {C, D} 2/3
{A} -> {C} 3/5
{C} -> {A} 1
{A} -> {D} 2/3
{D} -> {A} 2/3
{B} -> {C} 1
{C} -> {B} 3/5
{C} -> {D} 3/5
{D} -> {C} 1
{C} -> {E} 3/5
{E} -> {C} 1
{D} -> {E} 2/3
{E} -> {D} 2/3
{B} -> {E} 2/3
{E} -> {B} 2/3

我们可以看到,随着包含的商品个数的增多,频繁集的支持度似乎在降低,并且,涉及到更多商品的规则,其置信度和涉及到更少商品的规则的置信度相比也要偏低一些,这是符合常理的,因为,作为顾客的消费者的购买力是有限的,同时买更多的商品,就要支付更多的价钱,所以一般都是少量的商品组合出现得更频繁.因而,我们看到,置信度为1的规则很多都是单个商品对单个商品的,而现实中这样的情况也是平凡的.

关联规则挖掘在R语言中的实现

关联规则挖掘作为数据挖掘领域中的常用的方法,在R语言的生态中自然已有成熟的软件包已经实现好了关联规则挖掘的有关函数,例如arules包,同时,在网路上搜索R语言中的关联规则挖掘,还会有详细的讲解关于如何使用此类软件包进行关联规则挖掘以及如何对结果进行可视化,因此,R软件实现的部分,在本文中就不再讲了.

参考资料

[1] Association rule learning - Wikipedia

[2] Apriori Algorithm Explained | Association Rule Mining | Finding Frequent Itemset | Edureka

数据挖掘aprioriassociationrulesdatamining

谈一谈复数、欧拉公式和割圆术

在macOS上释放出足够的磁盘空间