第6章数据挖掘-课件

Chapter6关联规则

AssociationRule

目标:提供关联规则问题的概述并介绍几种基本的关联规则挖掘算法关联规则问题概述大项目集关联规则算法Apriori算法抽样算法划分算法并行算法1©PrenticeHall啤酒和尿布的故事

沃尔玛公司在美国的一位店面经理曾发现，每周，啤酒和尿布的销量都会有一次同比攀升，一时却搞不清是什么原因。后来，沃尔玛运用数据挖掘技术发现，购买这两种产品的顾客几乎都是25岁到35岁、家中有婴儿的男性，每次购买的时间均在周末。沃尔玛在对相关数据分析后得知，这些人习惯晚上边看球赛、边喝啤酒，边照顾孩子，为了图省事而使用一次性的尿布。得到这个结果后，沃尔玛决定把这两种商品摆放在一起，结果，这两种商品的销量都有了显著增加。2©PrenticeHall这个故事说明了什么？在海量的数据中，总是隐藏着各种各样的信息。而随着时间的推移以及信息爆炸，我们已经很难不借助其他的外力去从海量的数据中发觉信息，即使能发觉，根据现在信息的发布速度，这样也是毫无实际意义的。如何从庞大的数据海洋中发掘有效信息，已经成为信息时代所急待解决的问题。于是数据仓库，数据挖掘、在线分析等等概念开始出现在我们视野里。这个时代是一个炒做概念的时代，新名词、新概念层出不穷；惹的我们纷纷双眼昏花起来。这个故事告诉大家，数据里蕴藏着许多肉眼所看不见的东西。根据现在的零售业发展规模来看，再想创造沃尔玛的神奇故事已经不可能了，谁都没有神的眼睛，没有经过梳理的数据对我们来说比垃圾还垃圾。因此，如何发掘垃圾里的有价值信息，就成了一个市场的卖点。因此，请关注数据挖掘。3©PrenticeHall例子:购物篮数据购买一种商品时也同时购买另一种商品的情形就构成了一条关联规则:花生酱

面包应用领域:场地布局广告市场营销库存控制目的:增加销售量并减少成本4©PrenticeHall关联规则相关概念一组项目:

I={I1,I2,…,Im}事务数据库:D={t1,t2,…,tn},tj

I项目集:{Ii1,Ii2,…,Iik}

I项目集的支持度:包含该项目集的事务占库中所有事务的百分比。大(频繁)项目集:

是出现次数大于阈值s的项目集.5©PrenticeHall关联规则示例5个项目I={Beer,Bread,Jelly,Milk,PeanutButter}项目集{Bread,PeanutButter}的支持度是60%6©PrenticeHall关联规则定义

给定一组项目I={I1,I2,…,Im}和一个事务数据库D={t1,t2,…,tn}，其中ti={Ii1,Ii2,…,Iik}并且Iij

I,关联规则(AR):形如X

Y的蕴含式，其中X,Y

I是两个项目集，并且X

Y=Ø;关联规则X

Y

的支持度s:数据库中包含X

Y

的事务占库中所有事务的百分比。关联规则X

Y

的置信度a:

包含X

Y的事务数与包含X

的事务数的比值。7©PrenticeHall示例8©PrenticeHall关联规则问题给定一组项目I={I1,I2,…,Im}和一个事务数据库D={t1,t2,…,tn}，其中

ti={Ii1,Ii2,…,Iik}并且Iij

I,关联规则问题就是识别出所有大于最小支持度和置信度的关联规则

X

Y.注意:

X

Y的支持度和X

Y的支持度相等.9©PrenticeHall关联规则技术发现大项目集.从大项目集合产生关联规则.10©PrenticeHall产生关联规则的算法ARs11©PrenticeHalls=30%,a=50%

利用该支持度，从表6.2得到大项目集的集合

L={{啤酒}，{面包}，{牛奶}，{花生酱}，{面包,花生酱}}

要想产生关联规则，需要有非空子集。

只有最后一个大项目集可以产生关联规则。

该大项目集产生的可能关联规则如下：

（1）面包

花生酱

，其置信度为0.75，满足条件，是一条有效的关联规则。

（2）花生酱

面包，其置信度为1，满足条件，是一条有效的个关联规则。例题12©PrenticeHallApriori算法大项目集性质:大项目集的任一子集也一定是大的。因此大项目集只能从所有大的子集的组合（连接运算）产生对照:如果一个项目集不是大的，那么它的超集也不是大的。13©PrenticeHallApriori

算法示例(cont’d)s=30%a=50%14©PrenticeHallApriori

算法C1=ItemsetsofsizeoneinI;Determinealllargeitemsetsofsize1,L1;i=1;Repeati=i+1;

Ci

=Apriori-Gen(Li-1);CountCitodetermineLi;untilnomorelargeitemsetsfound;15©PrenticeHallApriori-Gen从大小为i

的大项目集产生大小为i+1的侯选项目集。具体用法：将每一个项目集合与另外一个具有共同成员的项目集进行连接运算（组合）。

比如下例，在第三趟扫描后，有4个大项目集。在对这些大项目集进行连接运算时，必须对三个属性中的两个进行匹配，然后生成更大的项目集。可能需要修剪，因为据此产生的大项目集有些不是大的。16©PrenticeHallApriori-Gen算法示例17©PrenticeHallApriori-GenExample(cont’d)18©PrenticeHall抽样算法针对大型数据库，可以减少扫描趟数首先对数据库进行抽样，然后对抽样应用Apriori

算法.潜在的大项目集(PL):

从抽样里产生的大项目集负边界函数(BD-):把Apriori-Gen算法推广应用到大小变化的项目集。它定义为本身不在PL中,但其子集都在PL中的最小集合.19©PrenticeHall例题假定项目集合是{A,B,C,D}。从数据库样本（抽样）中发现的大项目集合为PL={A,C,D,CD).第一趟扫描整个数据库生成下面的侯选集:C=BD-(PL)(PL)={B,AC,AD}{A,C,D,CD}

这里之所以加入AC,是因为A和C都在PL中,同理也加入了AD。

没有加入ACD，是因为它的子集AC和AD都不在PL中。20©PrenticeHall抽样算法Ds=sampleofDatabaseD;PL=LargeitemsetsinDsusingsmalls;C=PL

BD-(PL);CountCinDatabaseusings;ML=largeitemsetsinBD-(PL);

L=largeitemsetsinCIfML=

thendone elseC=repeatedapplicationofBD-（IneachiterationletC=L);CountCinDatabase;21©PrenticeHall抽样算法示例FindARassumings=20%Ds={t1,t2}Smalls=10%PL={{Bread},{Jelly},{PeanutButter},{Bread,Jelly},{Bread,PeanutButter},{Jelly,PeanutButter},{Bread,Jelly,PeanutButter}}BD-(PL)={{Beer},{Milk}}ML={{Beer},{Milk}}RepeatedapplicationofBD-generatesallremainingitemsets22©PrenticeHall作业3标准解法

若抽样数据库包括t1,t9两个事务：

Ds={t1={罩衫}，t9={牛仔裤}}将s减小到smalls=10%,那么对于一个在抽样中为大的项目集来说，它必须在至少0.1*2个事务中出现，也就必须在其中一个事务中出现；PL={{罩衫}，{牛仔裤}计算负边界可得：

BD-（PL）={{裙子}，{T恤}，{鞋}，{短裤},{罩衫，牛仔裤}}

第一趟扫描时候选集：C=PL∪BD-（PL）={{罩衫}，{牛仔裤}，{裙子}，{T恤}，{鞋}，{短裤}，{罩衫，牛仔裤}}扫描使用s=20%，并应用于整个数据库的20个事务中。因此对于一个大目集来说，它必须在大于0.2*20=4个事务中出现。得到大项目集：L1={{牛仔裤}，{裙子}，{T恤}，{鞋}，{短裤}}23©PrenticeHall第二趟扫描令C=L1，计算负边界：C=BD-（C）={…}

扫描使用s=20%，并应用于整个数据库的20个事务中。因此对于一个大目集来说，它必须在大于0.2*20=4个事务中出现。得到大项目集合：L2={…}第三趟扫描令C=L2，计算负边界C=BD-（C）={…}

得到大项目集合：L3={…}

故最终的大项目集：L=L1∪L2∪L3={…}24©PrenticeHall划分算法把数据库分成小的数据库D1,D2,…,Dp对每一部分应用

Apriori

算法。任何一个大项目集至少在一个划分是大的。25©PrenticeHallPartitioningAlgorithmDivideDintopartitionsD1,D2,…,Dp;ForI=1topdoLi=Apriori(Di);C=L1

…

Lp;CountConDtogenerateL;26©PrenticeHall划分算法示例D1D2S=10%L1={{Bread},{Jelly},{PeanutButter},{Bread,Jelly},{Bread,PeanutButter},{Jelly,PeanutButter},{Bread,Jelly,PeanutButter}}L2={{Bread},{Milk},{PeanutButter},{Bread,Milk},{Bread,PeanutButter},{Milk,PeanutButter},{Bread,Milk,PeanutButter},{Beer},{Beer,Bread},{Beer,Milk}}27©PrenticeHall平行算法依据Apriori算法大部分平行或分布式关联规则算法要么试图将数据并行化（或者划分），要么试图将侯选并行化（或者划分）。两者分别称之为数据并行和任务并行。数据并行和任务并行的典型算法分别为记数分配算法和数据分别算法。28©PrenticeHall度量关联规则的质量支持度s(AB)=P(A,B)置信度a(AB)=P(B|A)=P(A,B)/P(A)作用度或兴趣度interest(AB)=P(A,B)/(P(A)*P(B))信任度conviction(AB)=P(A)*P(¬B)/P(A,¬B)

如果A和B恒成立的规则的信任度为。如果A和B不相关（独立），则信任度为1。如果A