数据挖掘导论之频繁模式及关联规则挖掘技术(一)

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第3课,频繁模式及关联规则挖掘技术,徐从富，,副教授,浙江大学人工智能研究所,浙江大学本科生数据挖掘导论课件,内容提纲,关联规则挖掘简介,关联规则基本模型,关联规则价值衡量与发展,参考文献,关联规则简介,关联规则反映一个事物与其他事物之间的相互依存性和关联性。如果两个或者多个事物之间存在一定的关联关系，那么，其中一个事物就能够通过其他事物预测到。,典型的关联规则发现问题是对超市中的货篮数据（Market Basket）进行分析。通过发现顾客放入货篮中的不同商品之间的关系来分析顾客的购买习惯。,什么是关联规则挖掘,关联规则挖掘,首先被Agrawal,Imielinski and Swami在1993年的SIGMOD会议上提出,在事务、关系数据库中的项集和对象中发现频繁模式、关联规则、相关性或者因果结构,频繁模式,:数据库中频繁出现的项集,目的:发现数据中的规律,超市数据中的什么产品会一起购买？啤酒和尿布,在买了一台PC之后下一步会购买?,哪种DNA对这种药物敏感?,我们如何自动对Web文档进行分类?,频繁模式挖掘的重要性,许多重要数据挖掘任务的基础,关联、相关性、因果性,序列模式、空间模式、时间模式、多维,关联分类、聚类分析,更加广泛的用处,购物篮分析、交叉销售、直销,点击流分析、DNA序列分析等等,关联规则基本模型,关联规则基本模型,Apriori算法,Fp-Tree算法,关联规则基本模型,IBM公司Almaden研究中心的R.Agrawal首先提出关联规则模型，并给出求解算法AIS。随后又出现了SETM和Apriori等算法。其中，Apriori是关联规则模型中的经典算法。,给定一组事务,产生所有的关联规则,满足最小支持度和最小可信度,关联规则基本模型（续）,设,I,=,i,1,i,2,i,m,为所有项目的集合，,D,为事务数据库，事务,T,是一个项目子集（,T,I,）。每一个事务具有唯一的事务标识,TID,。设,A,是一个由项目构成的集合，称为项集。事务,T,包含项集,A,，当且仅当,A,T,。如果项集,A,中包含,k,个项目，则称其为,k,项集。项集,A,在事务数据库,D,中出现的次数占,D,中总事务的百分比叫做项集的支持度。如果项集的支持度超过用户给定的最小支持度阈值，就称该项集是频繁项集（或大项集）。,关联规则基本模型（续）,关联规则是形如,X,Y,的逻辑蕴含式，其中,X,I,，,Y,I,，且,X,Y,=,。如果事务数据库,D,中有,s,%的事务包含,X,Y,，则称关联规则,X,Y,的支持度为,s,%，实际上，支持度是一个概率值。若项集,X,的支持度记为,support,(,X,)，规则的信任度为,support,(,X,Y,),support,(,X,)。这是一个条件概率,P,(,Y,|,X,)。,也就是：,support,(,X,Y,)=,P,(,X,Y,),confidence,(,X,Y,)=,P,(,Y,|,X,),规则,度,度量,：,：支,持,持度,与,与可,信,信度,查找,所,所有,的,的规,则,则,X&Y,Z,具有,最,最小,支,支持,度,度和,可,可信,度,度,支持,度,度,s,一,一次,交,交易,中,中包,含,含X,、,、Y,、,、Z,的,的可能,性,性,可信,度,度,c,包含X,、,、Y的,交,交易,中,中也,包,包含,Z,的条件,概,概率,设最,小,小支,持,持度,为,为50%,最,最小,可,可信,度,度为50%,则,则可,得,得到,A,C,(50%,66.6%),C,A,(50%,100%),买尿,布,布的,客,客户,二者,都,都买,的,的客,户,户,买啤,酒,酒的,客,客户,关联,规,规则,基,基本,模,模型,（,（续,）,）,关联,规,规则,就,就是,支,支持,度,度和,信,信任,度,度分,别,别满,足,足用,户,户给,定,定阈,值,值的,规,规则,。,。,发现,关,关联,规,规则,需,需要,经,经历,如,如下,两,两个,步,步骤,：,：,找出,所,所有,频,频繁,项,项集,。,。,由频,繁,繁项,集,集生,成,成满,足,足最,小,小信,任,任度,阈,阈值,的,的规,则,则。,Letmin_support=50%,min_conf=50%:,A,C,(50%,66.7%),C,A,(50%,100%),Customer,buys diaper,Customer,buys both,Customer,buys beer,Transaction-id,Items bought,10,A,B,C,20,A,C,30,A,D,40,B,E,F,Forrule,A,C,:,support=support(,A,C,)=50%,confidence=support(,A,C,)/support(,A,)=66.6%,Min.support50%,Min.confidence50%,Transaction-id,Items bought,10,A,B,C,20,A,C,30,A,D,40,B,E,F,Frequent pattern,Support,A,75%,B,50%,C,50%,A,C,50%,Apriori算,法,法的,步,步骤,Apriori算,法,法命,名,名源,于,于算,法,法使,用,用了,频,频繁,项,项集,性,性质,的,的先,验,验（Prior）,知,知识,。,。,Apriori算,法,法将,发,发现,关,关联,规,规则,的,的过,程,程分,为,为两,个,个步,骤,骤：,通过,迭,迭代,，,，检,索,索出,事,事务,数,数据,库,库中,的,的所,有,有频,繁,繁项,集,集，,即,即支,持,持度,不,不低,于,于用,户,户设,定,定的,阈,阈值,的,的项,集,集；,利用,频,频繁,项,项集,构,构造,出,出满,足,足用,户,户最,小,小信,任,任度,的,的规,则,则。,挖掘,或,或识,别,别出,所,所有,频,频繁,项,项集,是,是该,算,算法,的,的核,心,心，,占,占整,个,个计,算,算量,的,的大,部,部分,。,。,频,繁,繁,项,项,集,集,为,了,了,避,避,免,免,计,计,算,算,所,所,有,有,项,项,集,集,的,的,支,支,持,持,度,度,（,（,实,实,际,际,上,上,频,频,繁,繁,项,项,集,集,只,只,占,占,很,很,少,少,一,一,部,部,分,分,）,）,，,，Apriori,算,算,法,法,引,引,入,入,潜,潜,在,在,频,频,繁,繁,项,项,集,集,的,的,概,概,念,念,。,。,若,若,潜,潜,在,在,频,频,繁,繁,k,项,集,集,的,的,集,集,合,合,记,记,为,为,C,k,，,频,频,繁,繁,k,项,集,集,的,的,集,集,合,合,记,记,为,为,L,k,，,m,个,项,项,目,目,构,构,成,成,的,的,k,项,集,集,的,的,集,集,合,合,为,为,，,，,则,则,三,三,者,者,之,之,间,间,满,满,足,足,关,关,系,系,L,k,C,k,。,构,构,成,成,潜,潜,在,在,频,频,繁,繁,项,项,集,集,所,所,遵,遵,循,循,的,的,原,原,则,则,是,是,“,“,频,频,繁,繁,项,项,集,集,的,的,子,子,集,集,必,必,为,为,频,频,繁,繁,项,项,集,集,”,”,。,。,关,联,联,规,规,则,则,的,的,性,性,质,质,：,：,性,质,质1,：,：,频,频,繁,繁,项,项,集,集,的,的,子,子,集,集,必,必,为,为,频,频,繁,繁,项,项,集,集,。,。,性,质,质2,：,：,非,非,频,频,繁,繁,项,项,集,集,的,的,超,超,集,集,一,一,定,定,是,是,非,非,频,频,繁,繁,的,的。,Apriori,算,算,法,法,运,运,用,用,性,性,质,质1,，,，,通,通,过,过,已,已,知,知,的,的,频,频,繁,繁,项,项,集,集,构,构,成,成,长,长,度,度,更,更,大,大,的,的,项,项,集,集,，,，,并,并,将,将,其,其,称,称,为,为,潜,潜,在,在,频,频,繁,繁,项,项,集,集,。,。,潜,潜,在,在,频,频,繁,繁,k,项,集,集,的,的,集,集,合,合,C,k,是,指,指,由,由,有,有,可,可,能,能,成,成,为,为,频,频,繁,繁,k,项,集,集,的,的,项,项,集,集,组,组,成,成,的,的,集,集,合,合,。,。,以,以,后,后,只,只,需,需,计,计,算,算,潜,潜,在,在,频,频,繁,繁,项,项,集,集,的,的,支,支,持,持,度,度,，,，,而,而,不,不,必,必,计,计,算,算,所,所,有,有,不,不,同,同,项,项,集,集,的,的,支,支,持,持,度,度,，,，,因,因,此,此,在,在,一,一,定,定,程,程,度,度,上,上,减,减,少,少,了,了,计,计,算,算,量,量,。,。,Apriori,算,算,法,法,(1),L,1,=,频,频,繁,繁1,项,项,集,集;,(2)for(,k,=2;,L,k,-1,;,k,+)dobegin,(3),C,k,=apriori_gen(,L,k,-1,);/,新,新,的,的,潜,潜,在,在,频,频,繁,繁,项,项,集,集,(4)forall,transactionst,D,dobegin,(5),C,t,=subset(,C,k,t,);/t,中,中,包,包,含,含,的,的,潜,潜,在,在,频,频,繁,繁,项,项,集,集,(6)forall,candidatesc,C,t,do,(7),c,.,count,+;,(8)end;,(9)L,k,=c,C,k,|c.count,minsup,(10)end;,(11)Answer=,实,例,例,DatabaseTDB,1,st,scan,C,1,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,VisualizationofAssociationRules:PaneGraph,VisualizationofAssociationRules:RuleGraph,提,高,高Apriori,算,算,法,法,的,的,方,方,法,法,Hash-baseditemsetcounting,（,（,散,散,列,列,项,项,集,集,计,计,数,数,）,）,Transactionreduction,（,（,事,事,务,务,压,压,缩,缩,）,）,Partitioning,（,（,划,划,分,分,）,）,Sampling,（,（,采,采,样,样,）,）,关,联,联,规,规,则,则,挖,挖,掘,掘,算,算,法,法,Agrawal,等,等,人,人,提,提,出,出,的,的AIS,，,，Apriori,和,和AprioriTid,Cumulate,和,和Stratify,，,，Houstsma,等,等,人,人,提,提,出,出,的,的SETM,Park,等,等,人,人,提,提,出,出,的,的DHP,Savasere,等,等,人,人,