第六章挖掘大型数据库中的关联规则

1、,主讲：王名扬,信息与计算机工程学院,数据挖掘,引,言,要挖掘知识的类型,?,概念描述：特征化和比较；,?,关联规则；,?,分类,/,预测；,?,聚类分析；,?,其他的数据挖掘任务。,2,第,6,章,挖掘大型数据库中的关联规则,引,言,关联规则挖掘发现大量数据中项集之间有趣的,关联,或相关联系,。,从大量商业事务记录中发现有趣的关联关系，可以,帮助许多商务决策的制定，如分类设计、交叉购物和,促销分析等。,2,引,言,如何从事务,DB,或关系,DB,的大量数据中挖掘出关联规,则知识？,什么样的关联规则才是最有意义的？,如何才能使挖掘过程尽快发现有价值的关联规则知,识？,这是本章要讨论的内容。,2

2、,第,6,章,6.1,关联规则挖掘,6.2,由事务数据库挖掘单维布尔关联规则,6.3,由事务数据库挖掘多层关联规则,6.4,由事务数据库和数据仓库挖掘多维关联规则,学习目的,?,掌握关联规则挖掘算法,-Apriori,算法。,?,理解多层关联规则挖掘及其方法；,?,理解多维关联规则挖掘及其方法。,7,6.1,关联规则挖掘,关联规则挖掘,(Association rule mining),：,?,关联规则挖掘的主要对象是交易型数据库，一个交易一般,由交易处理时间，一组顾客购买的物品，有时也有顾客标识,号组成。,?,关联规则挖掘用以挖掘一次交易中，物品之间同时出现的,规律的知识模式，以反映顾客的购

3、买行为。,?,更确切的说，关联规则是通过量化的数字来描述物品,X,的出,现对物品,Y,的出现有多大的影响。,关联规则挖掘,以零售业为例，通过对销售数据的关联分析，,体育用品商店可以发现隐含在数据中的规律：,“,购买篮球的顾客中有,70%,的人同时购买篮球运,动服，所有交易中有,40%,的人同时购买篮球和篮球,运动服”,等等。,购物篮分析,购物篮分析是关联规则挖掘的最初形式。,如，某商店经理可能更想了解如下的购物习惯：,“顾客多半会在购物时同时购买什么商品组或集合？”,为解答这个问题，可以在商店顾客事务零售数据库上进,行购物篮分析。,分析的结果可用于市场规划、广告策划和分类设计。,4,购物篮分析

4、,设商店中所有销售商品为一个集合，每个商品均为一,个布尔变量，布尔变量用来表示该商品是否被,(,一个,),顾,客购买。则，每个购物篮（事务数据库）可以用一个布,尔向量表示。,分析该布尔向量，得到反映商品频繁关联或同时购买,的购买模式。,5,购物篮分析,例如，在购买计算机的同时购买财务管理软件，可,用如下关联规则表示：,computer,=,financial,_,management,_,software,support,=,2%,confidence,=,60%,?,关联规则的支持度,(support)2%,表示：,全部事务中，有,2%,的交易同时购买计算机和财务管理软件。,?,关联规则的置

5、信度,(confidence)60%,表示：,购买计算机,的顾客中，有,60%,也同时购买了财务管理软件。,6,1.,关联规则的基本概念？,关联规则挖掘的基本概念,1,）事务数据库：,?,设,I= i,1,，,i,2,，,，,i,m,是一个项目集合，事务数据库,D= t,1,，,t,2,，,，,t,n,是由一系列具有唯一标识,TID,的事务组成，每个事,务,t,i,（,i=1,，,2,，,，,n,）都对应,I,上的一个子集。,示例：,购物记录,?,I,是全部物品集合，,如商场现有的所有商品,；,?,D,是购物清单，,如顾客的购物清单,；,?,D,中的每个元组,t,i,代表一次事务（商业行为），

6、是一次购买,物品的集合（,I,的一个子集）。,基本概念,2,）支持度,(support),：,?,支持度是模式为真的任务相关的元组（或事务）所占的百分比。对于,形如“,A,?,B,”,的关联规则，支持度定义为：,包含,A,和,B,的元组数,支持度（,A,?,B,）,=,元组总数,其中，,A,、,B,是项目的集合。,示例：,假定任务相关数据由,AllElectronics,的计算机部的事务数组成，,一个支持度为,30%,的关联规则：,buys,(,X,computer,),?,buys,(,X,software,),意味着在计算机部的所有顾客中，有,30%,同时购买了计算机（,A,）和软,件（,

7、B,）。,基本概念,3,）置信度,(certainty),：,?,每个发现的模式都有一个表示其有效性或值得信赖性的度量。对于形,如“,A,?,B,”,的关联规则，其有效性度量为置信度，定义为：,包含,A,和,B,的元组数,置信度（,A,?,B,）,=,包含,A,的元组数,其中，,A,、,B,是项目的集合。,示例：,假定任务相关数据由,AllElectronics,的计算机部购买物品的事务,数组成，一个置信度为,85%,的关联规则：,buys,(,X,computer,),?,buys,(,X,software,),意味着买计算机（,A,）的顾客中，有,85%,也同时购买了软件（,B,）。,基本

8、概念,4,）强关联规则：,?,置信度表示规则的可信度；,置信度小：规则无意义,?,支持度表示模式在事务数据库中的出现频率；,支持度小：规则使,用面窄,?,同时满足用户定义的最小置信度和最小支持度阈值的关联规则，,称为,强关联规则,（,strong association rule,），并被认为是有趣的。,2.,关联规则的分类？,关联规则的分类：,（,1,）基于规则中处理的变量类别,?,布尔型,：离散的、可枚举的、种类化的,如：性别,=,“男”,=,职业,=,“网络工程师”,?,数值型,：含有定量的数据项,如，性别,=,“男”,=,收入,=,“,3500,”,关联规则的分类：,（,2,）基于规则

9、中数据的抽象层次,?,单层关联规则,：所有的变量都不考虑层次,如：,性别,=,“男”,=,职业,=,“网络工程师”,?,多层关联规则,：考虑变量的不同层次性,如，数码相机,=,三星手机，（数码相机是三星数码相机的,较高层抽象）,再如，数码相机,=,手机（数码相机、手机是三星数码相机,和三星手机的较高层抽象）。,关联规则的分类：,?,多层关联规则又可以分为：,?,同层关联规则,：,如果一个关联规则对应的项目是同一个,粒度层次，那么它是同层关联规则,?,如，数码相机,=,手机,。,?,层间关联规则,：,如果在不同的粒度层次上考虑问题，那,么得到的是层间关联规则。,?,如，数码相机,=,三星手机,关

10、联规则的分类：,（,3,）基于规则中涉及的数据维数,?,单维关联规则,：只涉及一个属性（维），处理单个属性,（维）中的一些关系,如：啤酒,=,尿布，只涉及到用户购买的物品一个维；,?,多维关联规则,：处理多个属性（维）上的关系,如，性别“女”,=,职业“秘书”，此规则涉及到两个属性,（维）的关系。,6.2,由事务数据库挖掘,单维布尔关联规则,关联规则挖掘的两步过程：,?,1,）找出所有的频繁项集：,这些项集出现的频繁性要满足,最小支持度原则。,?,2,）由频繁项集产生强关联规则：,满足最小支持度和最小,置信度。,?,常用方法：,Apriori,算法,频繁项集,?,项的集合称为,项集,（,ite

11、mset,），项的项集称为,k-,项集,，如集合,computer, software,是一个,2-,项集。,?,项集的频率：,即包含项集的事务数，也称为项集的支持计数,(support_count),。,?,Min_sup:,设定的支持率阈值,?,如果项集的出现频率大于或等于,min_sup,与,D,中事务总数的,乘积，就称该项集满足最小支持度,min_sup,。,?,频繁项集：,满足最小支持度的项集，频繁,k-,项集通常记做：,L,k,。,基本概念,频繁项集：,?,频繁项集是频繁出现在数据集中的项集；,?,有助于发现数据中蕴含的内在规律,?,哪些产品经常被一起购买？,-,啤酒和尿布？,?,

12、买了,PC,之后接着都会买些什么？,?,哪种,DNA,对这种新药敏感？,?,能揭示数据集内在的、重要的特性,。,Apriori,算法,?,Apriori,算法原理：,?,任何一个频繁项集的子集必定是频繁项集；,如，如果,A,B,是频繁项集，则,A,、,B,都是频繁项集。,?,任何非频繁项集的超集都为非频繁项集,如，如果,A,、,B,是非频繁项集，则,A,B,是非频繁项,集,Apriori,算法,?,算法的关键步骤：,?,找出频繁项集：满足最小支持度的项目集；,?,方法：使用从,1,到,k,的候选集逐层递归的产生频繁项集。,?,由频繁项集产生关联规则。,APRIORI,算法过程,?,Aprior

13、i,算法利用逐层迭代来计算数据库中的频繁项集。第,i,次迭代,计算出所有频繁,i,项集,(,包含,i,个元素的项集,),。每一次迭代有两个步,骤：,产生候选集；计算和选择候选集,。,?,原理是：,如果一个项集是频繁的，那么它的所有子集也是频繁的,。,?,在第一次迭代中，产生的候选集包含所有,1-,项集，并计算其支持度,s,，,s,大于阈值的,1-,项集被选为频繁,1-,项集。,?,第二次迭代时，,Apriori,算法首先去除非频繁,1-,项集，在频繁,1-,项集,的基础上产生候选二项集，继而结合设定的最小支持度阈值，产,生频繁,2-,项集。,APRIORI,算法过程,如，以表,6-1,中的数据

14、为例。假设,s,min,=50%,。,6,APRIORI,算法过程,?,在第一次迭代中，所有单项集都作为候选集，产生一个候选集列,表；图,5-1,给出第一次迭代的结果,?,在下一步中，计算每一项的支持度，然后在,s,min,的基础上选择频繁,项集。,图,5-1 Apriori,算法第一次迭代的结果,APRIORI,算法过程,?,在挖掘,2-,项集时，因为,2-,项集的任何子集都是频繁项集，所,以,Apriori,算法使用,L,1,*L,1,来产生候选集。,*,运算通常定义为,：,L,k,*L,k,=X,Y,其中,X,Y,L,k,|X,Y|=k+1,注,: |X,Y|=k+1,，即,X,和,Y,

15、合取容量为,k+1,?,因此，第二次迭代中的候选集,C,2,由运算,|L,1,|,|L,1,-1|/2,所产生，,其个数为：,4,3/2=6,。用该列表来扫描,DB,，计算每一个候选,集的支持度，并与,s,min,进行比较，产生,2-,项频繁集,L,2,。图,5-2,给出了所有这些步骤和第二次迭代的结果。,APRIORI,算法过程,6,APRIORI,算法过程,?,候选集,C,3,运用,L,2,*L,2,来产生，运算结果得到,C,E,，但只有,B,C,E,的所有子集是频繁项集，,成为候选的,3-,项集。然后扫描,DB,，根据最小支持计数，挖掘出频,繁,3-,项集，见图,5-3,所示,:,3_,

16、项集,C3,ABC,ACE,BCE,3_,项集,ABC,ACE,BCE,计数,0,0,2,S(%),0,0,50,频繁,3_,项集,BCE,计数,2,S(%),50,图,5-3 Apriori,算法第三次迭代的结果,?,因为本例的,L,3,无法产生候选的,4-,项集，所以算法停止迭代,过程。,APRIORI,算法过程,?,该算法不仅计算所有频繁集的支持度，也计算那些没有被,删除的非频繁候选集的支持度。,?,所有非频繁但被算法计算支持度的候选项集的集合被称为,负边界,。因此，如果项集是非频繁的，但它的子集都是频繁,的，那么它就在负边界之中。,Apriori,算法源代码,算法：,Apriori,使

17、用根据候选生成的逐层迭代找出频繁项集,输入：,事务数据库,D,；最小支持度阈值,min_sup,输出：,D,中的频繁项集,L,（,1,）,L,1,= large 1-itemsets; /,所有,1-,项目频集,（,2,）,FOR,（,k=2; L,（,3,）,C,k-1,?,; k+,）,DO BEGIN,k,=,apriori-gen,（,L,k-1,）,; / C,k,是,k-,候选集,（,4,）,FOR all transactions t,?,D DO BEGIN,（,5,）,C,t,=,subset,（,C,k,，,t,）,; / C,t,是所有,t,包含的候选集元素,（,6,）,

18、FOR all candidates c,?,C,c.count+;,t,DO,（,7,）,（,8,）,END,（,9,）,L,k,=c,?,C,k,|c.count,?,minsup_count,（,10,）,END,（,11,）,L=,?,L,k,;,36,38,由频繁项集产生关联规则,示例：,对于前面的例子，基于事务数据库,D,，在假定最小支持度阈,值为,50%,的前提下，我们得到了频繁项集,2,3,5,。问，由该频繁,项集可以产生哪些关联规则？,分析：频繁项集,L=2,3,5,的非空子集有,。则,由这些子集可以产生如下关联规则：,(,1,),(,2,),(,3,),(,4,),(,5,

19、),(,6,),2,?,3,?,5,2,?,5,?,3,3,?,5,?,2,2,?,3,?,5,3,?,2,?,5,5,?,2,?,3,confidence,=,2,/,2,=,100,%,confidence,=,2,/,3,=,67,%,confidence,=,2,/,2,=,100,%,confidence,=,2,/,3,=,67,%,confidence,=,2,/,3,=,67,%,confidence,=,2,/,3,=,67,%,如果限定最小置信度阈值为,80%,，则只有规则（,1,），（,3,）为强关联规则。,Apriori,算法的性能瓶颈,?,Apriori,作为经典的频

20、繁项目集生成算法，在数据挖掘中具有,里程碑的作用。,?,Apriori,算法有两个致命的性能瓶颈,:,1,多次扫描事务数据库，需要很大的,I/O,负载,?,对每次,k,循环，侯选集,C,k,中的每个元素都必须通过扫描数据库来,验证其是否加入,L,k,。假如有一个频繁大项目集包含,10,个项的话，,那么就至少需要扫描事务数据库,10,遍。,2,可能产生庞大的侯选集,?,由,L,k-1,产生,k-,侯选集,C,k,是指数增长的。,如何提高,Apriori,算法的效率,?,一些算法虽然仍然遵循,Apriori,属性，但是由于引入了相关技术，,在一定程度上改善了,Apriori,算法适应性和效率。,?

21、,主要的改进方法有：,基于数据分割（,Partition,）的方法,：基本原理是“在一个划分,中的支持度小于最小支持度的,k-,项集不可能是全局频繁的,”,。,基于散列（,Hash,）的方法,：基本原理是“在一个,hash,桶内支持,度小于最小支持度的,k-,项集不可能是全局频繁的,”,。,基于采样的方法,：基本原理是“通过采样技术，评估被采样的,子集，并依次来估计,k-,项集的全局频度,”,。,其他,：如，动态删除没有用的事务：“不包含任何,L,k,的事务对,未来的扫描结果不会产生影响，因而可以删除,”,。,6.3,由事务数据库挖掘多层关联规则,多层关联规则：,?,对许多应用，由于多维数据空

22、间数据的稀疏性，在,低层或原,始层的数据项之间很难找到强关联规则,。,?,如，,IBM,台式机,= Sony,打印机，在两个数据项间可能很难找到,强关联规则,?,在,较高的概念层，则较容易得到强关联规则,。这种强关联规,则对某些用户可能是普遍意义的，对其他用户则可能是新颖,的。,?,如，台式机,=,打印机，找到强关联规则的可能性就大多了,?,因此，数据挖掘系统应当能提供一种能力，在,多个抽象层,挖,掘关联规则，并容易在不同的抽象空间转换。,示例,示例：给定,AllElectronics,公司分店的计算机部的销售数据，如表,6-,2,所示，对每个事务,TID,给出了购买的商品。,表,6-2,任务

23、相关数据集,D,TID,T1,T2,T3,T4,T5,.,购买的商品,IBM desktop computer, Sony b/w printer,Microsoft educational software, Microsoft financial management software,Logitech mouse computer accessory, Ergoway wrist pad computer accessory,IBM desktop computer, Microsoft financial management software,IBM desktop computer

24、,.,示例,all,computer,software,printer,Computer,accessory,desktop,laptop,educational,Financial,management,color,b/w,Wrist pad,mouse,.,IBM,.,.,.,Microsoft,.,.,HP,.,Sony,.,.,Ergoway,.,Logitech,图,5-4,商品的概念分层,示例,?,概念分层：定义了低层概念到更一般的高层概念的映射序列。,可通过对数据内的低层概念用概念分层中其高层概念进行替换,，以实现对数据的概化。,?,图,5-4,中的概念分层有,4,层，记做,0,

25、1,2,3,：,?,0,层：根节点,all,（最一般的抽象概念）；,?,1,层：,computer,software,printer,computer accessory,?,2,层：,desktop computer, laptop computer,educational software,financial management software,?,3,层：,IBM desktop computer, Microsoft educational software,示例,?,表,5-2,中的项对应图,5-4,中概念分层的最低层，即第,3,层，在这种,原始层很难找出有趣的购买模式。如，很难

26、找到“,IBM,desktop computer”,和“,Sony b/w printer”,的强关联规则，因为很,少有人同时购买它们，是的,IBM desktop computer, Sony b/w,printer,不太可能满足最小支持度。,?,然而，考虑将,“ Sony b/w printer”,概化到,“b/w printer”,，在“,IBM,desktop computer”,和“,b/w printer”,之间比在“,IBM desktop,computer”,和“,Sony b/w printer”,间，更可望发现强关联规则。,?,类似的，在“,computer”,和“,pri

27、nter”,间，则更容易发现强关联,规则。,多层关联规则,?,多层关联规则挖掘的度量方法仍可以沿用“支持度,-,置信,度框架”；,?,但是，有两种,设置支持度的策略,：,?,对于所有层使用一致的最小支持度（,一致支持度,）：在每一,层挖掘时，使用相同的最小支持度阈值。,?,在较低层使用递减的最小支持度（,递减支持度,）：每个抽象,层有它自己的最小支持度阈值，抽象层越低，对应的阈值越,小。,一致支持度,如下图，在挖掘过程中，设置一致的最小支持度阈值,5%,。发现，层,1,满足,此阈值，在层,2,中，“,2%milk”,满足，而“,skim milk”,则不满足。,说明，较低层次抽象的项不大可能像

28、较高层次抽象的项出现得那么频繁。,一致支持度,优势：,?,使用一致的最小支持度阈值，搜索过程是简单的，且用户只需用,指定一个最小支持度阈值。,缺陷：,?,如果最小支持度阈值设置太高，可能丢掉出现在较低抽象层中有,意义的关联规则；,?,反之，设置太低，则可能会在较高抽象层产生无兴趣的关联规则,解决方法：,?,“递减支持度”,递减支持度,如下图，在挖掘过程中，使用递减支持度。层,1,和层,2,的阈值分别设,定为,5%,和,3%,，用这种方法，,“,Milk”,，“,2% Milik”,和“,Skim,Milk”,都是频繁的。,递减支持度,对于具有递减支持度的多层关联规则挖掘，有许多可用的,搜索策略

29、：,?,“逐层独立”,?,“层交叉单项过滤”,?,“层交叉,k-,项集过滤”,1,）逐层独立,逐层独立：,?,这是完全的宽度搜索，没有频繁项集的背景知识用于剪枝；,?,频繁项集：如果一个项集是频繁的，那么它的所有子集也是频,繁的,；,?,考虑每一个节点，不管它的父节点是否是频繁的。,2,）层交叉单项过滤,层交叉单项过滤：,?,一个第,i,层的项被考察，当且仅当它在第,(i-1),层的父节点是频繁的。,即，由较一般的关联考察更特定的关联。,?,如果一个节点是频繁的，它的子女将被考察；否则，它的子孙将被,剪枝。如下图所示。,层,1,：,min_sup=12%,Computer,support=10

30、%,层,2,：,min_sup=3%,Laptop (,未考,察,),Desktop computer (,未考察,),具有递减支持度的多层挖掘，使用层交叉单项过滤,3,）层交叉,k-,项集过滤,层交叉,k-,项集过滤：,?,一个第,i,层的,k-,项集被考察，当且仅当它在第,(i-1),层的,k-,项集父节点是频,繁的。,?,如，下图中，,2-,项集,computer, printer,是频繁的，因而节点,laptop computer,b/w printer, laptop computer, color printer, desktop computer, b/w printer,des

31、ktop computer, color printer,被考察。,层,1,：,min_sup=5%,Computer and printer,support=7%,层,2,：,min_sup=2%,Laptop computer,and b/w printer,support=1%,Laptop computer,and color printer,support=2%,desktop computer,and b/w printer,support=1%,desktop computer,and color printer,support=3%,具有递减支持度的多层挖掘，使用层交叉,k-,

32、项集过滤,6.4,由关系数据库和数据仓库挖掘多维关联规则,单维关联规则：,?,前面所介绍的关联规则都只涉及一个谓词，如,buys,谓词。如在一,个商场的数据库挖掘中，可挖掘出如下关联规则：,其中,X,为代表顾客的一个变量。同样，一个多层次关联规则可为：,在上述两个关联规则中仅包含一个特定的谓词：,buys,，因此被称,为,单维关联规则,，或维内关联规则。,6.4,由关系数据库和数据仓库挖掘多维关联规则,?,假定不是对事务数据库进行分析，而是对关系数据库或数据仓,库中的销售和相关信息进行分析，此时的数据是以多维形式定,义存储的。,如，除记录在销售事务中购买的商品外，关系数据库可能还,记录着与商品有关的其他属性，如购买数量、价格、销售地址,等；还可能有购物顾客的基本信息，如年龄、职业、信誉度、,收入、地址等。,若将数据库的每个属性或数据仓库的每个维看作一个谓词，,可挖掘得到,多维