`
444878909
  • 浏览: 631508 次
文章分类
社区版块
存档分类
最新评论

关联规则挖掘之Apriori算法实现超市购物

 
阅读更多

一.关联规则

关联规则(Association Rules)是反映一个事物与其他事物之间的相互依存性和关联性,是数据挖掘的一个重要技术,用于从大量数据中挖掘出有价值的数据项之间的相关关系。其中关联规则挖掘的最经典的例子就是沃尔玛的啤酒与尿布的故事,通过对超市购物篮数据进行分析,即顾客放入购物篮中不同商品之间的关系来分析顾客的购物习惯,发现美国妇女们经常会叮嘱丈夫下班后为孩子买尿布,30%-40%的丈夫同时会顺便购买喜爱的啤酒,超市就把尿布和啤酒放在一起销售增加销售额。

二.基本概念

关联规则挖掘是寻找给定数据集中项之间的有趣联系。如下图所示:

其中,I={I1,I2,…Im}是m个不同项目的集合,集合中的元素称为项目(Item)。项目的集合I称为项目集合(Itemset),长度为k的项集成为k-项集。设任务相关的数据D是数据库事务的集合,其中每个事务T是项的集合,使得TI。每个事务有一个标识符TID;设A是一个项集,事务T包含A当且仅当A⊆I,则关联规则形式为A=>B(其中AIBI,并且AB= ∅)。

在关联规则度量中有两个重要的度量值:支持度和置信度。对于关联规则R:A=>B,则:

1.支持度(suppport):是交易集中同时包含A和B的交易数与所有交易数之比。

Support(A=>B)=P(A∪B)=count(A∪B)/|D|

2.置信度(confidence):是包含A和B交易数与包含A的交易数之比。

Confidence(A=>B)=P(B|A)=support(A∪B)/support(A)

如上图中数据库D,包含4个事务,项集I={I1,I2,I3,I4,I5},分析关联规则:I1=>I4,事务1、4包含I1,事务4同时包含I1和I4。

支持度support=1/4=25%(1个事务同时包含I1和I4,共有4个事务)指在所有交易记录中有25%的交易记录同时包含I1和I4项目

置信度confidence=1/2=50%(1个事务同时包含I1和I4,2个事务包含I1)指50%的顾客在购买I1时同时还会购买I4

使用关联规则对购物篮进行挖掘,通常采用两个步骤进行:下面将通超市购物的例子对关联规则挖掘进行分析。

a.找出所有频繁项集(文章中我使用Apriori算法>=最小支持度的项集)

b.由频繁项集产生强关联规则(>=最小支持度和最小置信度)

三.举例:Apriori算法挖掘频繁项集

Apriori算法是一种对有影响的挖掘布尔关联规则频繁项集的算法,通过算法的连接和剪枝即可挖掘频繁项集。补充频繁项集相关知识:K-项集:指包含K个项的项集;项集的出现频率:指包含项集的事务数,简称为项集的频率、支持度计数或计数;频繁项集:如果项集的出现频率大于或等于最小支持度计数阈值,则称它为频繁项集,其中频繁K-项集的集合通常记作Lk

下面直接通过例子描述该算法:如下图所示,使用Apriori算法关联规则挖掘数据集中的频繁项集。(最小支持度技术为2)

具体过程如下所示:

具体分析结果:

第一次扫描:对每个候选商品计数得C1,由于候选{D}支持度计数为1<最小支持度计数2,故删除{D}得频繁1-项集合L1;

第二次扫描:由L1产生候选C2并对候选计数得C2,比较候选支持度计数与最小支持度计数2得频繁2-项集合L2;

第三次扫描:用Apriori算法对L2进行连接和剪枝产生候选3项集合C3的过程如下:

1.连接:

C3=L2\bowtie(连接)L2={{A,C},{B,C},{B,E},{C,E}}\bowtie{{A,C},{B,C},{B,E},{C,E}}={{A,B,C},{A,C,E},{B,C,E}}

2.剪枝:

{A,B,C}的2项子集{A,B},{A,C}和{B,C},其中{A,B}不是2项子集L2,因此不是频繁的,从C3中删除;

{A,C,E}的2项子集{A,C},{A,E}和{C,E},其中{A,E}不是2项子集L2,因此不是频繁的,从C3中删除;

{B,C,E}的2项子集{B,C},{B,E}和{C,E},它的所有2项子集都是L2的元素,保留C3中.

经过Apriori算法对L2连接和剪枝后产生候选3项集的集合为C3={B,C,E}.在对该候选商品计数,由于等于最小支持度计数2,故得频繁3-项集合L3,同时由于4-项集中仅1个,故C4为空集,算法终止。

四.举例:频繁项集产生强关联规则

强关联规则是指:如果规则R:X=>Y满足support(X=>Y)>=supmin(最小支持度,它用于衡量规则需要满足的最低重要性)且confidence(X=>Y)>=confmin(最小置信度,它表示关联规则需要满足的最低可靠性)称关联规则X=>Y为强关联规则,否则称关联规则X=>Y为弱关联规则。

例:下图是某日超市的购物记录,使用上面叙述的Apriori算法实现了挖掘频繁项集,其中频繁项集I={i1,i2,i5}为频繁3-项集合L3,求由I产生哪些强关联规则?(最小支持度阈值为20%,最小置信度阈值为80%)

I的非空子集有{i1,i2}、{i1,i5}、{i2,i5}、{i1}、{i2}和{i5}。

结果关联规则如下,每个都列出置信度

1).i1∧i2=>i5,共10个事务;5个事务包含i1,i2;2个事务包含i1,i2和i5 confidence=2/5=40%,support=2/10=20%

2).i1∧i5=>i2,共10个事务;2个事务包含i1,i5;2个事务包括i1,i2和i5confidence=2/2=100%,support=2/10=20%

3).i2∧i5=>i1,共10个事务;2个事务包含i2,i5;2个事务包含i1,i2和i5confidence=2/2=100%,support=2/10=20%

4).i1=>i2∧i5,共10个事务;7个事务包含i1;2个事务包含i1,i2和i5confidence=2/7=28%,support=2/10=20%

5).i2=>i1∧i5,共10个事务;8个事务包含i2;2个事务包含i1,i2和i5confidence=2/8=25%,support=2/10=20%

6).i5=>i1∧i2,共10个事务;2个事务包含i5;2个事务包含i1,i2和i5confidence=2/2=100%,support=2/10=20%

因最小置信度阈值为80%,最小支持度阈值为20%,则236规则符合要求,是频繁项集I={i1,i2,i5}产生的强关联规则且可以输出。

(自己的推测:如果给定的是最小支持度计数为2,则有10个事务,最小支持度阈值supmin=2/10=20%)

五.总结

这是最近学习《商务智能》课程中对关联规则挖掘“超市购物篮”的分析,使用Apriori对数据库进行频繁项集挖掘与关联规则的产生是一个非常有用的技术,其中我们众所周知的例子如沃尔玛超市的尿布与啤酒、超市的牛奶与面包、百度文库推荐相关文档、淘宝推荐相关书籍、银行推荐相关联业务等。这些都是商务智能和关联规则在实际生活中的运用,上面的例子主要是我们学校的课件,也结合了很多网上的资料,希望该文章能帮组到大家!同时是我对该知识点的一些总结,如果有错误或不足之处,见谅!

问题:我在发表博客时想缩小行间距,不知道怎样实现,采用html也没成功,所以上面的排版间距很大?求告知,谢谢!

(By:Eastmount 2013-8-10 下午6点)

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics