Press "Enter" to skip to content

【机器学习算法】关联规则-1 关联规则的概念,Apriori算法,实例和优缺点

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

关联规则

 

关联规则的概念:

 

关联规则是由数据挖掘之父Rakesh Agrawal提出

 

当他提出这个关联规则之后数据挖掘概念一度非常火,比如非常着名的啤酒与尿布,其实就是通过关联规则找出啤酒与尿布的关联规则关系。

 

而且这个关联规则被运用到商业中,并且运用的非常成功,它刚开始是在IBM,现在被微软挖墙角,现在在微软工作,是微软的技术工作人员。

 

 

建立软件IBM Intelligent Miner ,当时就被部署到云计算中去,在IBM的云中。

 

许多数据挖掘算法的设计者Apriori和AprioriAll都是他设计建立的。

 

关联规则是为了寻找经常购买的产品组合。从交易数据库里,找到经常购买的数据库组合

 

关联规则的原因:

 

购物篮分析(如果我们知道了哪些产品顾客会同时购买,我们把商品包装为一个pakege,比如AB这两个商品经常被一起购买,所以我们就可以针对这项目,进行设定折扣活动,做交叉销售(cross -marketing,),就一个客户经常购买A类产品,就可以推荐他来购买B,或者catalog design现在某人购买了商品A,下面的推荐页就会出现与A相关的BCD商品组。甚至我们可以进行空间的设计,什幺商品应该放在什幺商品的旁边,(shelf space layout design)比如我们购买小孩玩具的时候,一般都会多购买几个电池,所以就可以把电动玩具和电池放在同一个位置,这就是透过关联规则了解商品被一起购买的可能性,然后一起购买,或者etc)

 

案例:

 

关联规则表示一:

 

表示为:Body——》Head[Support,Confidence]

 

Buys(x,“Computer”)——》buys(x,“Software”)[2%,60%]

 

代表了x购买computer之后再次购买软件的关系,我们有两个指标,一个是支持度support和置信度confidence,在这个规则里,支持度就是百分之2,置信度就是百分之60。置信度就是条件概率,就是在卖电脑的情况下,购买软件的概率是百分之60,支持度一会我们细说。

 

这种形式的关联规则,我们叫单维度得到关联规则,因为它只涉及一个维度,买什幺影响买什幺,

 

关联规则表示二:

 

其实我们也有多维度的关联规则,比如我们输入的是一张表格,而不是一笔一笔的交易。

 

规则表示如下:

 

major(x,“CS”)^takes(x,“DB”)——》grade(x,“A”)[1%,75%]

 

如果X它的科系是电脑CS,修了一门数据库DB的课,这个人成绩得到A的概率是百分之75。

 

而之后我们用Apriori算法既可以得到多维度的关联规则,又可以得到单维度的关联规则

 

关联规则的评估指标

 

-评估指标也就是支持度和置信度

 

刚才我们已经说了置信度,其实就是条件概率,在body发生的概率下,Head发生的概率。

 

现在说一下支持度

 

下面是案例:

 

 

字段1是我们的交易编号,通常关联规则是以一个交易为单位,所以这里就有它的交易编号,这里我们代表也是一个交易编号,代表顾客同时购买了几种商品。

 

第一个记录代表的就是ABC3个产品同时被顾客购买

 

第二笔记录是顾客同时购买AC这两种商品。

 

现在我们就2个商品A——》C这两个商品,这个方向,的关联规则

 

A——》C,关联规则都会有两个指标

 

支持度Support=Support({A,C})=50%

 

置信度Confidence=Support({A,C})/Support({A})=66.6%

 

支持度是什幺,就是我们不看——》这个方向,我们单纯就看,A与C同时被购买的概率就是我们的支持度。

 

我们来看看我们的数据,有多少数据是A和C同时被购买,第一笔,第二笔AC都被同时购买,所以AC被同时购买的支持率就是被购买的笔数除以/总笔数。就是2/4,百分之50

 

置信度就是,AC的支持度和A的支持度的除法,也就是AC同时被购买的概率除以A被购买的概率。也就是2/4除以3/4。也可以理解为,购买A的次数有3次,其中有2次也购买C了,用2/3就是置信度。也就是在A被购买的情况下C也被购买的概率。

 

但是一条规则有了支持度和置信度,它不一定是关联规则。关联规则我们必须舍得一个最低门槛,同时满足两个条件,第一个就是我们定义的最小支持度的门槛,minimum support和最小置信度的门槛minimum confidence。

 

所以我们做关联规则必须设定2个参数,一个是最小支持度,一个是最小置信度。

 

我们也把关联规则的确定叫做购物篮分析,主要原因就是因为,我们的市场分析师,就是为了分析顾客会放什幺东西到我们的购物篮里面。购物篮的东西就是同时间被购买的东西,市场分析师想了解哪些商品顾客会同时购买,那如果他知道这个信息,就可以进行很多相关的活动设定,所以我们把关联规则分析也叫做购物篮分析。

 

假如你得到了一个关联规则。

 

Shirt和tie[13.5%,70%]

 

现在你要用两句话来描述着两个关联规则,你要怎幺说

 

顾客买了一件shirt,再同时购买tie的概率有百分之70,

 

顾客同时购买shirt和tie的概率占总购买量的百分之13.5

 

现在,我们有一个案例

 

 

我们设定,我们的最小支持度为百分之50,最小置信度为百分之50。那幺我们就会得到2条关联规则。

 

A——》C[50%,66.6%]

 

C——》A[50%,100%]

 

首先我们看AC各自的支持度,AC和CA都是占了案例的一半。置信度,在A条件下的c有百分之66.6,而在C条件下的A为百分之百所以这两对会同时出现。

 

但是这两个关联规则一定会同时出现吗

 

不见得,如果我们把置信度的要求设定为百分之70.

 

那幺A——》C就不会出现了不见得会成对产生。

 

APriori算法

 

-非常有名的算法,解决暴力法的弊端、apriori的算法

 

于是我们就考虑,我们直接把全部的支持度和置信度都整理出来,不就可以找到了合理的关联规则了吗。

 

但是这里有一个问题,我们的关联规则是指数递增的我们要从这个指数个数的小规则里,寻找到全部的关联规则,需要的时间要非常非常的久,假如我们单一商品一共有100种

 

 

如果要寻找商品之间两两关联的规则,就有4950个规则,3个产品的组合,比如AB——》C,那就要求C100取3.也就是161700

 

如果要把每种方法都尝试一遍,就要关联2100-1次。在里面寻找我们需要的关联规则,这就已经是一个天文数字了,而且我们卖场还不只有100件商品,10万种商品这样,2的10万次方-1,不可能短时间得到,所以我们不可能用暴力法得到关联规则的问题。它的问题就是执行时间太久。

 

算法Apriori其实只有一个理论,Apriori Principle

 

它其实就是一句话,如何frequent itemset的子集合也一定是frequent itemset

 

Frequent itemset就是频繁被购买的组合。一个被频繁购买的组合,它的子集合也一定会被频繁购买。举例来讲

 

 

A,C,有4笔交易,有两笔是包含AC,支持度是百分之50.我们设定的最小支持度是百分之50,所以AC就是一个频繁项目。也就是只要大于最小支持度的就会被我们算做频繁商品组合。

 

而我们的理论Apriori Principle代表的就是,AC既然指数出现两次,那幺其中A,C也肯定至少出现2次。最差的情况就是和AC的支持度。这就是被频繁购买的组合,它的子集也一定被频繁购买。

 

这就是我们算法的唯一理论。

 

但是我们apriori算法使用的时候,不是直接使用,而是倒着用。比如我们有一个商品E,它仅仅出现一次,支持度是1/4,那幺所有和E的组合你就不用考虑了,AE,BE,CE都不用考虑。因为最好的情况也就是1/4。也就是说,子集合数据都不够,那幺与它相关的集合,也就不用考虑了。

 

Apriori的步骤

 

首先寻找经常被购买的组合是哪一些,例如,AB经常被购买,因为AB的支持度大于最小支持度的门槛值。所以AB代表经常被购买的产品组合。

 

这时代表它们的最小支持度已经够了,接下来再由经常被购买的项目里产生关联规则。

 

比如AB,就可以产生2条关联规则,比如A——》B或者B——》A。

 

这时就只要考虑这两个规则的置信度,如果有,就是我们的关联规则,没有就不是我们的关联规则,如果都满足,就可以输出我们的关联规则

 

Apriori算法的实例说明

 

-候选项集的产生和候选项集的缩减

 

 

这个案例是5笔交易,代表这些项目被同时购买的5笔订单。

 

我们现在设定我们的最小支持度为百分之30,最小置信度为百分之60

 

我们会得到一条规则(orange juice)——》(soda)

 

也就是买orange juice就很可能买soda。

 

而且仅有这条关联规则,那幺这条真的是关联规则吗。我们来看看,第一订单他们俩被同时购买,第3笔订单他们也被同时购买。剩下的没有。

 

所以它的支持度是百分之40,置信度是百分之66.6因为3笔购买orange juice的情况购买了

 

我们来看看apriori的实际处理过程。

 

 

我们来看第一个表格,它是把全部的商品的支持度都计算出来,寻找其中满足置信度大于最小置信度的商品。最后剩下左上第二个表格的3个商品,1orange juice 2soda 3window cleaner。

 

然后我们可以根据这3个商品组合出长度是二的商品组合。也就是左下角的图片,这3个图进行求支持度,因为后两个关联规则不满足条件然后它就被我们过滤掉。于是我们就只找到 关联规则orange juice和soda的关联规则。

 

而且由于长度为2的关联规则只有1,我们就没法去组长度为3的关联规则。

 

然后我们就可以去找卖orange juice——》soda

 

和soda——》orange juice的规则

 

第一条规则的置信度是百分之66.6

 

第二条规则的置信度是百分之50

 

为什幺第二条才一半呢,因为soda有4次购买,其中只有2次购买了orange juice

 

 

于是我们就得到他的过程,就是这样。先从单个项目中去筛,然后两两关联的项目中去筛,因为不能得到3个关联规则的情况,最后利用置信度,来筛出关联规则。

 

再举一个复杂一些的例子。

 

 

这里我们有一个数据D,代表4笔交易,我们会对里面的商品进行计数处理,得到C1,然后我们现在设定支持度,这里我们不用百分比,直接用次数介绍,也就是,至少要出现2笔交易,于是就筛选出1235这4个情况L1,我们现在通过L1产生交叉长度为2的候选人,最后得到,12,13,15,23,25,35,再次扫描一下数据库,扫描他们出现的次数。最后得到出现次数为121232.筛除出长度为2的频繁项目:13,23,25,35。然后我们要得到长度为3的频繁项目。一个长度为3的频繁项目要求,每个两两对应的单独频繁项目都有频繁出现过才能检查,比如235,就要求23,25,35都频繁出现过,这就是我们的候选人235,其他都不用考虑。最后我们就得到235的项目组合。

 

还有一个更为复杂的案例:

 

 

它也是一样,进行单独商品的计数,然后寻找两两对应的商品组合进行计数,在组长度为3的组合,我们要找头相同尾巴不同的组合,得到2个关联规则I1I2I3,I1I2I5候选人,进行计数,次数都大于二,所以这3个就可以被作为被频繁购买的项目集。

 

如果我们要组合出L4的话,那幺我们也是一样的处理方法,

 

比如现在有4个长度为3的频繁项目(abc,abd,acd,ace,bcd)

 

那幺我们就可以找到abcd和acde,因为没有cde,所以我们就只有一个长度为4的候选人abcd。

 

Apriori算法的实例的缺点及瓶颈

 

Apriori算法的瓶颈就是它的速度慢,它是用频繁被购买的候选集合,去产生频繁被购买的集合。用l2产生c3再产生l3

 

每次产生都得扫描数据库的内容才知道那些要保留,那些要删除。

 

也就是2步,产生候选人,在扫描数据库。

 

瓶颈1:候选人可能非常非常多。比如我们之前的案例,长度为1的样本就只有5个候选人就产生了10个。更不用说之后商品假如有1万个。就要产生1千万个长度为2的候选人。候选人集合很大,很占用记忆空间,

 

瓶颈2,如果你要产生长度为n的数据,那幺就可能要扫描n+1次原始数据。比如我们选择c5经过扫描,没有通过就只能选择l4,所以程度为4的数据,那幺就要扫描5次。如果原始数据有几万笔,那幺不断的扫描会很浪费时间。

 

所以有浪费记忆体和浪费时间的缺点。于是有人就提出FPGrower的方法来解决这两项缺点。

 

小结:

 

我们今天讲了关联规则的概念,和它的两个指标,还有说明了一个算法Apriori的算法,它是为了解决暴力法的弊端所出现的,我们也发现Apriori的缺点,如何解决呢?于是就有FPgrowth的方法。

Be First to Comment

发表回复

您的电子邮箱地址不会被公开。