《关联规则与关联分析课堂课件.ppt》由会员分享，可在线阅读，更多相关《关联规则与关联分析课堂课件.ppt（37页珍藏版）》请在三一办公上搜索。
1、第四章,关联规则与关联分析,1,摘要,?,关联规则挖掘是数据挖掘中成果颇丰而且,比较活跃的研究分支。本章主要介绍了关,联规则挖掘的基本概念及其分类，以单维,单层布尔关联规则的挖掘理论为切入点，,介绍关联规则挖掘理论模型以及算法方面,的内容，并简单扼要介绍了多层关联规则,挖掘、多维关联规则挖掘的相关内容，最,后通过一个实例给出了关联分析的医学应,用。,2,什么是关联规则挖掘？,?,关联规则挖掘：,从事务数据库，关系数据库和其他信息存储中,的大量数据的项集之间发现有趣的、频繁出现,的模式、关联和相关性。,?,应用：,购物篮分析、分类设计、捆绑销售等,3,“尿布与啤酒”,典型关联分析,案例,?,采用
2、关联模型比较典型的案例是“尿布与,啤酒”的故事。在美国，一些年轻的父亲,下班后经常要到超市去买婴儿尿布，超市,也因此发现了一个规律，在购买婴儿尿布,的年轻父亲们中，有,30%,40%,的人同时,要买一些啤酒。超市随后调整了货架的摆,放，把尿布和啤酒放在一起，明显增加了,销售额。同样的，我们还可以根据关联规,则在商品销售方面做各种促销活动。,4,购物篮分析,?,如果问题的全域是商店中所有商品的集合，则对,每种商品都可以用一个布尔量来表示该商品是否,被顾客购买，则每个购物篮都可以用一个布尔向,量表示；而通过分析布尔向量则可以得到商品被,频繁关联或被同时购买的模式，这些模式就可以,用关联规则表示（,
3、0001001100,，这种方法丢失了什么信息？,）,?,关联规则的两个兴趣度度量,支持度,置信度,%,60,%,2,sup,),(,),(,?,?,?,confidence,port,software,X,buys,computer,X,buys,5,?,关联（,association,）：两个或多个变量的取值之,间存在某种规律性。,?,关联规则（,association rule,）：指在同一个事件,中出现的不同项的相关性。,?,关联分析（,association analysis,）：用于发现隐,藏在大型数据集中的令人感兴趣的联系。所发现,的联系可以用关联规则或者频繁项集的形式表示。,关
4、联规则挖掘就是从大量的数据中挖掘出描述数,据项之间相互联系的有价值的有关知识。,?,应用：购物篮分析、生物信息学、医疗诊断、,Web,挖掘、科学数据分析、分类设计、捆绑销售,和亏本销售分析,6,购物篮事务的例子,TID,项集,1,面包，牛奶,2,面包，尿布，啤酒，鸡蛋,3,牛奶，尿布，啤酒，可乐,4,面包，牛奶，尿布，啤酒,5,面包，牛奶，尿布，可乐,7,第一节,关联规则基本概念和关联规则挖掘分类,?,关联规则的基本概念,?,关联规则挖掘的基本过程与分类,8,关联规则的基本概念,?,令,I=i1,，,i2,，,，,id,是购物篮数据中所,有项的集合，而,T=t1,，,t2,，,，,tn,是所,
5、有事务的集合。,?,每个事务,ti,包含的项集都是,I,的子集。,?,在关联分析中，包含,0,个或者多个项的集合,被称为项集（,itemset,）,?,如果一个项集包含,k,个项，则称它为,k-,项集。,例如,啤酒，尿布，牛奶,是一个,3-,项集。,?,空集是指不包含任何项的项集。,9,?,事务的宽度定义为事务中出现项的个数。,?,如果项集,X,是事务,tj,的子集，则称事务,tj,包含,项集,X,。,?,项集的一个重要性质就是它的支持度计数，,即包含特定项集的事务个数，数学上，项,集,X,的支持度计数,（,X,）可以表示为：,（,X,）,=|ti|X,ti,，,ti,T|,10,?,关联规则
6、是形如,X,Y,的蕴含表达式，其中,X,和,Y,是不相交的项集。,?,关联规则的强度可以用它的支持度,（,support,）和置信度（,confidence,）度量。,支持度确定了规则可以用于给定数据集的,频繁程度，而置信度确定了,Y,包含,X,的事务,中出现的频繁程度。,11,规则度量：支持度和置信度,TID,购买的,item,2000,A,B,C,1000,A,C,4000,A,D,5000,B,E,F,Customer,buys diaper,Customer,buys both,Customer,buys beer,?,对所有满足最小支持度,和置信度的关联规则,支持度,s,是指事务集,
7、D,中,包含,的百分比,置信度,c,是指,D,中包含,A,的事务同时也包含,B,的百,分比,?,假设最小支持度为,50%,，,最小置信度为,50%,，则,有如下关联规则,A,?,C(50%,66.6%),C,?,A(50%,100%),B,A,?,),(,),(,sup,B,A,P,B,A,port,?,?,?,),(,/,),(,),|,(,),(,A,P,B,A,P,A,B,P,B,A,confidence,?,?,?,?,12,关联规则挖掘的基本过程与分类,?,关联规则挖掘的基本过程,?,关联规则挖掘的分类,13,关联规则挖掘的基本过程,?,给定事务的集合,T,，关联规则发现是指找出,支
8、持度大于等于,minsup,，并且置信度大于,等于,minconf,的所有规则，其中,minsup,和,minconf,是对应的支持度和置信度的阈值。,14,原始关联规则挖掘方法：,?,计算每一个可能规则的支持度和置信度。,但是这种方法由于过高的代价而让人望而,却步。,15,关联规则挖掘任务的步骤,?,找出所有频繁项集：其目标是发现满足最,小支持度阈值的所有项集，这些项集称作,频繁项集（,frequent itemset,）,?,由频繁项集产生强关联规则：其目标是从,上一步发现的频繁项集中提取所有高置信,度的规则，这些规则称作强规则（,strong,rule,）,16,关联规则挖掘分类,(1)
9、,?,关联规则有多种分类：,根据规则中所处理的值类型,?,布尔关联规则,?,量化关联规则（规则描述的是量化的项或属性间的关联性）,根据规则中涉及的数据维,?,单维关联规则,?,（仅涉及,buys,这个维）,?,多维关联规则,),(,),48,.,42,(,),39,.,30,(,computer,X,buys,k,k,X,income,X,age,?,?,),(,),(,software,X,buys,computer,X,buys,?,software,management,financial,computer,_,_,?,17,关联规则挖掘分类,(2),根据规则集所涉及的抽象层,?,单层关
10、联规则,?,多层关联规则,（在不同的抽象层发现关联规则）,根据关联挖掘的各种扩充,?,挖掘最大的频繁模式（该模式的任何真超模式都是非频,繁的）,?,挖掘频繁闭项集（一个项集,c,是频繁闭项集，如果不存在,其真超集,c,，使得每个包含,c,的事务也包含,c,）,?,（最大的频繁模式和频繁闭项集可以用来减少挖掘中产,),_,(,),39,.,30,(,computer,laptop,X,buys,X,age,?,),(,),39,.,30,(,computer,X,buys,X,age,?,18,由事务数据库挖掘单维布尔关联规,则,?,最简单的关联规则挖掘，即单维、单层、布尔关,联规则的挖掘。,T
11、ransaction ID,Items Bought,2000,A,B,C,1000,A,C,4000,A,D,5000,B,E,F,Frequent Itemset,Support,A,75%,B,50%,C,50%,A,C,50%,最小支持度,50%,最小置信度,50%,?,对规则,A,?,C,，,支持度,=50%,?,置信度,%,6,.,66,),(,sup,/,),(,sup,),(,/,),(,),|,(,),(,?,?,?,?,?,?,?,A,port,C,A,port,A,P,C,A,P,A,C,P,C,A,confidence,),(,),(,sup,C,A,P,C,A,por
12、t,?,?,?,19,Apriori,算法,(1),?,Apriori,算法是挖掘布尔关联规则频繁项集的算法,?,Apriori,算法利用的是,Apriori,性质：频繁项集的所,有非空子集也必须是频繁的。,模式不可能比,A,更频繁的出现,Apriori,算法是反单调的，即一个集合如果不能通过测试，,则该集合的所有超集也不能通过相同的测试。,Apriori,性质通过减少搜索空间，来提高频繁项集逐层产,生的效率,B,A,?,20,Apriori,算法,(2),?,Apriori,算法利用频繁项集性质的先验知识,（,prior knowledge,），通过逐层搜索的迭,代方法，即将,k-,项集用于
13、探察,(k+1)-,项集，,来穷尽数据集中的所有频繁项集。,先找到频繁,1-,项集集合,L,1,然后用,L,1,找到频繁,2-,项集集合,L,2,，接着用,L,2,找,L,3,，直到找不到频繁,k-,项集，找每个,L,k,需要一次数据库扫描。,21,Apriori,算法步骤,?,Apriori,算法由,连接,和,剪枝,两个步骤组成。,?,连接：,为了找,L,k,，通过,L,k-1,与自己连接产生候选,k-,项集的集合，该,候选,k,项集,记为,C,k,。,L,k-1,中的两个元素,L1,和,L2,可以执行连接操作,的,条件是,?,C,k,是,L,k,的超集，即它的成员可能不是频繁的，但,是所有
14、频繁的,k-,项集都在,C,k,中（为什么？）。因,此可以通过扫描数据库，通过计算每个,k-,项集的,支持度来得到,L,k,。,为了减少计算量，可以使用,Apriori,性质，即如果一个,k-,项集的,(k-1)-,子集不在,L,k-1,中，则该候选不可能是频繁的，,可以直接从,C,k,删除。,),1,1,(,),2,2,(,.,),2,2,(,),1,1,(,2,1,2,1,2,1,2,1,?,?,?,?,?,?,?,?,?,?,?,?,k,l,k,l,k,l,k,l,l,l,l,l,2,1,l,l,?,22,Apriori,算法,示例,Database TDB,1,st,scan,C,1,
15、L,1,L,2,C,2,C,2,2,nd,scan,C,3,L,3,3,rd,scan,Tid,Items,10,A,C,D,20,B,C,E,30,A,B,C,E,40,B,E,Itemset,sup,A,2,B,3,C,3,D,1,E,3,Itemset,sup,A,2,B,3,C,3,E,3,Itemset,A,B,A,C,A,E,B,C,B,E,C,E,Itemset,sup,A,B,1,A,C,2,A,E,1,B,C,2,B,E,3,C,E,2,Itemset,sup,A,C,2,B,C,2,B,E,3,C,E,2,Itemset,B,C,E,Itemset,sup,B,C,E,2,
16、最小支持计数：,2,23,使用,Apiori,性质由,L,2,产生,C,3,?,1,连接：,C3=L,2,L,2,EC,E,C,E,?,2,使用,Apriori,性质剪枝：频繁项集的所有子集必须是频,繁的，对候选项,C,3,，我们可以删除其子集为非频繁的选,项：,A,B,C,的,2,项子集是,C,，其中,A,B,不是,L,2,的,元素，所以删除这个选项；,A,C,E,的,2,项子集是,E,，其中,A,E,不是,L,2,的,元素，所以删除这个选项；,B,C,E,的,2,项子集是,E,，它的所有,2,项子集,都是,L,2,的元素，因此保留这个选项。,?,3,这样，剪枝后得到,C,3,=B,C,E,
17、?,?,24,由频繁项集产生关联规则,?,同时满足最小支持度和最小置信度的才是,强关联规则，从频繁项集产生的规则都满,足支持度要求，而其置信度则可由一下公,式计算：,?,每个关联规则可由如下过程产生：,对于每个频繁项集,l,，产生,l,的所有非空子集；,对于每个非空子集,s,，如果,则输出规则“,”,),(,_,sup,),(,_,sup,),|,(,),(,A,count,port,B,A,count,port,B,A,P,B,A,confidence,?,?,?,?,conf,s,count,port,l,count,port,min_,),(,_,sup,),(,_,sup,?,),(,
18、s,l,s,?,?,25,多层关联规则挖掘,?,多层关联规则可以分为同层关联规则和层,间关联规则，同层关联规则是指处于同概,念层的关联规则；层间关联规则是指不同,概念层的关联规则。,?,多层关联规则基本上可以沿用“支持度,-,置,信度”的框架，但是在设置问题上有一些,要考虑的东西,26,?,统一的最小支持度：对于不同层次，都使,用一个最小支持度。这样对于用户和算法,实现来讲都比较容易，但是弊端也是显然,的。,?,递减的最小支持度：每个层次都有不同的,最小支持度，较低层次的最小支持度相对,较小。同时还可以利用上层挖掘得到的信,息进行一些过滤的工作,27,多维关联规则挖掘,?,数值字段被分成一些预定义的层次结构：,这些区间都是由用户预先定义的。得出的,规则也称为静态数量关联规则,?,数值字段根据数据的分布分成了一些布尔,字段：每个布尔字段都表示一个数值字段,的区间，落在其中为,1,，反之为,0,。这种分,法是动态的，得出的规则称为布尔数量关,联规则。,28,29,30,31,32,33,34,35,36,37,
