关联规则推荐算法的原理及实现

  • 更新时间: 2018-03-27
  • 来源: 原创或网络
  • 浏览数: 16次
  • 字数: 35099
  • 发表评论

关联规则用来发现数据间潜在的关联,最典型的应用是电商网站的购物车分析。本文将通过一个简单的例子来说明关联规则中各个术语的含义以及具体的计算方法。

这是一些用户的购物数据,uid是用户的ID,后面是每个用户具体购买的商品名称,我们使用字母进行标识。下面我们将使用关联规则对这些数据进行分析,挖掘不同商品间的联系。

关联规则推荐算法的原理及实现,by 5lulu.com

首先将前面的一维的购物车流水数据转换为二维的列表。然后在这个基础上计算不同商品及商品组成出现的频率。

关联规则推荐算法的原理及实现,by 5lulu.com

在关联规则中,有三个重要的术语,分别为支持度(Support),可信度(Confidence)和作用度(Lift)。第一个属于是支持度,支持度是一件商品在所有购物车中出现的频率。如果我们希望分析的是两件商品的关联,那么支持度就是这两件商品同时出现的频率。支持度的作用是用来衡量关联规则重要性的指标,简单来说就是我们所要挖掘的关系有多大的普遍性,普遍性越大这条关联规则越重要。第二个术语是可信度,可信度是指两件商品中当第一件出现时,第二件商品同时出现的频率。可信度用来衡量关联规则的准确性。第三个术语是作用度,作用度用来衡量关联规则对于商品出现频率的影响。只有作用度大于1的关联规则才有实际的应用意义。下面我们分别介绍这三个术语的计算方法。

1 支持度(Support)

支持度是两件商品在所有购物车中同时出现的概率,可以记录为P(A U B)。支持度的计算公式为A,B两件物品同时出现的次数与购物车总数的比率。对于前面例子中,如果我们要计算商品A和B在5条购物车记录中的支持度,具体的计算公式为1/5。商品A和B在5条购物车记录中只在uid1中同时出现过。

关联规则推荐算法的原理及实现,by 5lulu.com

单件商品的支持度的计算方法与两件商品一样,如果我们要计算商品A的支持度,具体的计算公式为3/5。商品A在5条购物车记录中共出现了3次。单件商品的支持度描述了在没有其他商品影响的情况下,商品在购物车中出现的次数。

关联规则推荐算法的原理及实现,by 5lulu.com

关联规则推荐算法的原理及实现,by 5lulu.com


2 可信度(Confidence)

可信度是一个条件概率,两件商品其中一件出现在购物车中时,另一件也会出现的概率。可以记录为P(B|A)。对于前面的例子中,如果要计算A和B两件物品的可信度,具体的计算公式为1/3。商品A出现的3次,商品B同时出现的次数为1次。

关联规则推荐算法的原理及实现,by 5lulu.com


3 作用度(Lift)

作用度通过衡量使用规则后的提升效果来判断规则是否可用,简单来说就是使用规则后商品在购物车中出现的次数是否高于商品单独出现在购物车中的频率。如果大于1说明规则有效,小于1则无效。对于前面的例子中,如果要计算规则A-B是否有效,计算公式为(1/5)/(3/5*3/5)=(0.2)/(0.6*0.6)=0.2/0.36=0.55。作用度小于1说明A-B规则对于商品B的提升没有效果。

关联规则推荐算法的原理及实现,by 5lulu.com

关联规则推荐算法的原理及实现,by 5lulu.com
按照前面的计算公式我们分别对下面的四个规则进行了计算,在获得支持度,可信度后计算出了四个规则的作用度。其中A-D规则作用度大于1,说明对购物车中已经包含商品A的用户推荐商品D,购买概率是单独推荐D的1.11倍。

4 实例


关联规则的目的在于在一个数据集中找出项之间的关系,也称之为购物蓝分析 (market basket analysis)。例如,购买鞋的顾客,有10%的可能也会买袜子,60%的买面包的顾客,也会买牛奶。这其中最有名的例子就是"尿布和啤酒"的故事了。

关联规则的应用场合。在商业销售上,关联规则可用于交叉销售,以得到更大的收入;在保险业务方面,如果出现了不常见的索赔要求组合,则可能为欺诈,需要作进一步的调查。在医疗方面,可找出可能的治疗组合;在银行方面,对顾客进行分析,可以推荐感兴趣的服务等等。

Apriori algorithm是关联规则里一项基本算法。由Rakesh Agrawal 在 1994 年提出的,详细的介绍请猛击这里《Fast Algorithms for Mining Association Rules》。

首先我们来看,什么是规则?规则形如"如果…那么…(If…Then…)",前者为条件,后者为结果。例如一个顾客,如果买了可乐,那么他也会购买果汁。

如何来度量一个规则是否够好?有两个量,置信度(Confidence)和支持度(Support)。假设有如下表的购买记录。

顾客

项目

1

orange juice, coke

2

milk, orange juice, window cleaner

3

orange juice, detergent

4

orange juice, detergent, coke

5

window cleaner

将上表整理一下,得到如下的一个2维表


Orange

Win Cl

Milk

Coke

Detergent

Orange

4

1

1

2

2

WinCl

1

2

1

0

0

Milk

1

1

1

0

0

Coke

2

0

0

2

1

Detergent

1

0

0

0

2

上表中横栏和纵栏的数字表示同时购买这两种商品的交易条数。如购买有Orange的交易数为4,而同时购买Orange和Coke的交易数为2。

置信度表示了这条规则有多大程度上值得可信。设条件的项的集合为A,结果的集合为B。置信度计算在A中,同时也含有B的概率。即Confidence(A==>B)=P(B|A)。例 如计算"如果Orange则Coke"的置信度。由于在含有Orange的4条交易中,仅有2条交易含有Coke.其置信度为0.5。

支持度计算在所有的交易集中,既有A又有B的概率。例如在5条记录中,既有Orange又有Coke的记录有2条。则此条规则的支持度为2/5=0.4。现在这条规则可表述为,如果一个顾客购买了Orange,则有50%的可能购买Coke。而这样的情况(即买了Orange会再买Coke)会有40%的可能发生。

再来考虑下述情况。

支持度

A

0.45

B

0.42

C

0.4

A and B

0.25

A and C

0.2

B and C

0.15

A,Band C

0.05

可得到下述规则

规则

置信度

If B and C then A

0.05/0.15*100%=33.33%

If A and C then B

0.05/0.20*100%=25%

If A and B then C

0.05/0.25*100%=20%

上述的三条规则,哪一条规则有用呢?

对于规则" If B and C then A",同时购买B和C的人中,有33.33%会购买A。而单项A的支持度有0.45,也就是说在所有交易中,会有45%的人购买A.看来使用这条规则来进行推荐,还不如不推荐,随机对顾客进荐好了。

为此引入另外一个量,即提升度(Lift),以度量此规则是否可用。描述的是相对于不用规则,使用规则可以提高多少。有用的规则的提升度大于1。计算方式为Lift(A==>B)=Confidence(A==>B)/Support(B)=Support(A==>B)/(Support(A)*Support(B))。在上例中,Lift(If B and C The A)=0.05/(0.15*0.45)=0.74。而Lift(If A then B)=0.25/(0.45*0.42)=1.32。也就是说对买了A的人进行推荐B,购买概率是随机推荐B的1.32倍。

如何产生规则呢。可以分两步走。

首先找出频繁集(frequent itemset)。所谓频繁集指满足最小支持度或置信度的集合。其次从频繁集中找出强规则(strong rules)。强规则指既满足最小支持度又满足最小置信度的规则。

我们来看如何产生频繁集。

这其中有一个定理。即频繁集的子集也一定是频繁集。比如,如果{A,B,C}是一个3项的频繁集,则其子集{A,B},{B,C},{A,C}也一定是2项的频繁集。为方便,可以把含有k项的集合称之为k-itemsets.

下面以迭代的方式 找出频繁集。首先找出1-itemsets的频繁集,然后使用这个1-itemsets,进行组合,找出2-itemsets的频繁集。如此下去,直到不再满足最小支持度或置信度的条件为止。这其中重要的两步骤分别是连接(join)和剪枝(prune).即从(k-1)-itemsets中的项进行组合,产生备选集(Candidate itemsets)。再从备选集中,将不符合最小支持度或置信度的项删去。例如

Frequent 2-itemsets


Candidate 3-itemsets


Frqquent 3-itemsets

I1,I2

==>

I1,I2,I4

==>

I1,I2,I4

I1,I4


I2,I3,I4



I2,I3





I2,I4






下面我们再来看一个详细的例子。

设最小支持度为2,以Ck表示k-itemsets备选集,以Lk表示k-itemsets频繁集。

ID

Items


Itemset

Sup. count


Itemset


Itemset

100

I1,I2,I5


I1

6


I1


I1,I2

200

I2,I4

==>C1:

I2

7

==>L1:

I2

==>C2

I1,I3

300

I2,I3


I3

6


I3


I1,I4

400

I1,I2,I4


I4

2


I4


I1,I5

500

I1,I3


I5

2


I5


I2,I3

600

I2,I3







I2,I4

700

I1,I3







I2,I5

800

I1,I2,I3,I5







I3,I4

900

I1,I2,I3







I3,I5









I4,I5


对C2进行扫描,计算支持度。

Itemset

Sup. count


Itemset


Itemset

Sup. count


Itemset

I1,I2

4

==> L2:

I1,I2

==> C3

I1,I2,I3

2

==> L3:

I1,I2,I3

I1,I3

4


I1,I3


I1,I2,I5

2


I1,I2,I5

I1,I4

1


I1,I5






I1,I5

2


I2,I3






I2,I3

4


I2,I4






I2,I4

2


I2,I5






I2,I5

2








I3,I4

0








I3,I5

1








I4,I5

0









对于频繁集中的每一项k-itemset,可以产生非空子集,对每一个子集,可以得到满足最小置信度的规则了。例如考虑{I1,I2,I5}。其子集有{I1,I2}, {I1,I5}, {I2,I5}, {I1}, {I2}, {I5}。可以产生规则,{I1,I2} => {I5} (50%), {I1,I5} => {I2} (100%), {I2,I5} =>{I1} (100%),{I1} => {I2,I5} (33%), {I2} =>{I1,I5} (29%), {I5} =>{I1,I2} (100%)。

也不是每个数据集都有产生强规则。例如"Thinkpad notebook" 和"Canon printer"一起可能很难产生有效规则。因为恰好一起买这两个牌子的产品的顾客太少。但不妨将Thinkpad notebook放到Notebook这一层次上考虑,而Canon printer放到printer这一去层次上考虑。这样的话,一起买notebook和printer的顾客就较多了。也即Multilevel association rules。


我来评分 :6
0

转载注明:转自5lulu技术库

本站遵循:署名-非商业性使用-禁止演绎 3.0 共享协议