dongleizhao@163com

Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Click to edit Master title style,Hebei,University,基于类关联规则的分类,Classification Based on Class-Association Rules,赵东垒,符号学习研究组,引言,国际研究现状,基本概念的定义,基于类关联规则的分类,(CMAR),TD-FP-Growth,挖掘类关联规则,规则剪枝,对测试数据分类,未来工作,参考文献,1.,引言,分类问题,通过分析给定的一个带有类别信息的数据集建立一个分类器,.,预测未知类别信息的数据对象,.,关联规则是给定数据集中项之间的有趣联系,.,基于关联规则的分类,是利用数据挖掘的方法挖掘数据集中的类关联规则,然后建立分类器,并对未知类别数据进行预测,.,关联规则中右侧固定为类别的属性,A=a1,B=b2-class1,2.,国际研究现状,(1),1993,年,Agrawal,Imielinski,和,Swami AIS93,提出了关联规则的挖掘,一个流行的应用领域是购物篮分析,.,1994,年,Agrawal,和,Srikant,AS94,提出了著名的,Apriori,算法,它是一种有效的关联规则挖掘算法,它探查逐级挖掘,Apriori,性质,:,频繁项集的所有非空子集都应该是频繁的,.,在第,k,次迭代,(K1),它根据频繁,K-,项集,形成频繁,(k+1)-,项集候选,并扫描数据库一次,找出完整的频繁,(K+1)-,项集,L(k+1).,1998,年,Liu,Hsu,和,Ma LHM98,提出了,CBA,算法,它采用经典的,Apriori,算法挖掘训练集,用满足要求的关联规则来构造分类器,实验,LHM98,表明,CBA,算法比,C4.5,有较好的测试精度,.,1999,年,Dong,Zhang,Wong,和,Li,LDR00,提出了,CAEP,算法,使用项集支持度挖掘显露模式来构造分类器,2000,年,Li,Dong,和,Rmamohanarao,LDR00,提出了基于跳跃显露模式,JEP,分类法,.,1999,年,Meretakis,和,Wuthrich,MW99,将大项集应用于朴素贝叶斯分类,实验,MW99,表明,在测试精度上要优于,C4.5,CBA,和,TAN,(a,Bayesian network extension of Nave,Bayes,),国际研究现状,(2),1999,年,Wang,Zhou,和,He WZH99,提出了基于关联的决策树,它首先产生满足置信度的所有关联规则,然后以精度驱使约剪规则,.,2000,年,Han,Pei,和,Yin HPY00,提出,FP-Growth,算法,它是一种不产候选的挖掘频繁项集方法,实验,HPY00,表明,FP-Growth,算法比,Apriori,算法获得更好的效率,是目前最流行的挖掘频繁项集的算法,.,2001,年,Li,Han,和,Pei,LHP01,提出了,CMAR,算法,它是基于扩展,FP-Growth,算法来有效的挖掘类关联规则,采用多条匹配的类关联规则来预测新的样例,实验,LHP01,表明,CMAR,的测试精度优于,C4.5,和,CBA.,2003,年,Yin,和,Han YH03,提出了,CPAR,算法,它扩展了,FOIL,算法,产生了较小规模的关联规则,引入了期望精度的方法来评价规则,预测新的样例,.,2005,年,Wang,和,Karypis,WK05,提出了,HARMONY,算法,它直接产生覆盖样例具有最高置信度的类关联规则,大大提高剪枝的效率,.,3.,基本概念的定义,假设数据对象,obj,=(a1,a2,an),aiAi,其中,Ai,称为属性,.,设,C=c1,c2,cm.,数据集中的每个数据对象都存在一个类别标示,cobjC,.,对于每个样例,我们可以看成是一个项,Item,的集合加上一个类别标识,.,在这里项,Item,是一个属性,-,值对,即,Item=(Attribute,value).,设,P,为一个模式,P=Item1,Itemk,c,为类标识,对于每条规则,R:P-c.,规则的支持度,sup(R,),和规则的置信度的,conf(R,),的定义,:,sup(R,),=,训练集中匹配模式,P,并且满足类标识为,c,的样例的个数,.,conf(R,),=,规则的支持度与训练集中匹配模式,P,的样例的个数的比值,conf(R,),=,sup(R)/sup(P,),A:a1,4.,基于类关联规则的分类,(CMAR),基于类关联规则的分类,(CMAR),主要包括四个步骤：,如果是连续的属性值,需要将其离散化,或者称数据的预处理,.,挖掘所有的满足支持度和置信度的类关联规则,.,基于已经产生的关联规则,通过剪枝建立一个分类器,.,利用分类器对未知类别数据进行分类,.,数据预处理,挖掘,类关联规则,建立分类器,分类,training set,mining,pruning,testing set,results,4.1.,挖掘类关联规则,ID,A,B,C,D,Class,1,a1,b1,c1,d1,A,2,a1,b2,c1,d2,B,3,a2,b3,c2,d3,A,4,a1,b2,c3,d3,C,5,a1,b2,c1,d3,C,training data set,T,给定数据集,T,首先由,T,生成,FP-Tree.,通过,TD-FP-Growth,算法挖掘所有的满足支持度和置信度的类关联规则,.,通过剪枝策略选取一个规则子集构成分类器,.,I,tem,c,ount,l,ink,A:a1,4,A:a2,1,B:b1,1,B:b2,3,B:b3,1,C:c1,3,C:c2,1,C:c3,1,D:d1,1,D:d2,1,D:d3,3,I,tem,count,link,A:a1,4,B:b2,3,C:c1,3,D:d3,3,H,eader Table,H,eader Table,M,insup,=2,4.1.1,FP-Tree,构造过程,Item,count,link,A,a1,4,B,b2,3,C,c1,3,D,d3,3,root,A,a1,D,d3,C,c1,B,b2,C,c1,D,d3,D,d3,4,A:1,B:1,C:2,1,A:1,1,C:1,1,C:1,1,C:1,2,B:1,C:1,3,B:1,C:2,1,A,:1,2,A:1,B:1,3,A:1,B:1,C:1,1,B:1,2,B:1,C:1,1,B:1,H,eader Table,FP-Tree,1 A:a1,B:b1,C:c1,D:d1,A,2 A:a1,B:b2,C:c1,D:d2,B,5 A:a1,B:b2,C:c1,D:d3,C,4 A:a1,B:b2,C:c3,D:d3,C,3 A:a2,B:b3,C:c2,D:d3,A,M,insup,=2,M,inconf,=50%,4.1.2,TD-FP-Growth,算法,item,c,ount,link,A,a1,3,Item,count,link,A,a1,4,B,b2,3,C,c1,3,D,d3,3,root,A,a1,D,d3,C,c1,B,b2,C,c1,D,d3,D,d3,4,A:1,B:1,C:2,1,A:1,1,C:1,1,C:1,1,C:1,3,B:1,C:2,3,A:1,B:1,C:1,3,B:1,C:2,A,:a1-C,sup(R,)=2,conf(R,)=50%,2,B:1,C:1,H,eader Table,FP-Tree,Sub H,eader Table of B,b2,item,c,ount,link,A,a1,3,B,b1,2,Sub H,eader Table of C,c1,B,:b2-C,sup(R,)=2,conf(R,)=66.7%,A:a1&B,:b2-C,sup(R,)=2,conf(R,)=66.7%,D:d3,-C,sup(R,)=2,conf(R,)=66.7%,A:a1&D:d3,-C,sup(R,)=2,conf(R,)=100%,B,:b2&D:d3-C,sup(R,)=2,conf(R,)=100%,A:a1&B,:b2&D:d3-C,sup(R,)=2,conf(R,)=66.7%,M,insup,=2,M,inconf,=50%,2,B:1,C:1,4.1.3,存储类关联规则,ID,Rule,Support,Confidence,1,a,bc,-A,60,100%,2,a,bcd,-A,70,80%,3,abe,-B,70,80%,4,b,cd,-C,60,50%,CR-Tree,4.2.,规则剪枝,(1),一般的情况,产生的类关联规则的数目是非常大的,.,为了使后面的分类更加的有效,剪掉一些规则,以消除多余的噪声信息,.,定义,1:,设偏序关系,R1 R2,当且仅当,conf(R1)conf(R2).,conf(R1)=conf(R2),sup(R1)sup(R2).,conf(R1)=conf(R2),sup(R1)=sup(R2).,R1,拥有的属性值对的项数比,R2,的少,.,定义,2:R1:P-c,相对于,R2:P-c,更一般,当且仅当,P,是,P,的子集,.,规则剪枝的步骤如下,:,用更一般且有高置信度的规则剪掉那些特殊的低置信度的规则,.,如给定规则,R1,和,R2,当,R1,比,R2,更一般且,R1R2,则用,R1,剪掉,R2.,选择具有正相关的规则,.,对于规则,R:P-c,计算,P,与,c,的,2,相关值,.,我们选择,2,相关值超过阈值,(3.84),的规则,.,基于数据覆盖的剪枝,.,规则剪枝,(2),c,c,total,P,f11,f12,f11+f12,P,f21,f22,f21+f22,total,f11+f21,f12+f22,f11+f12+f21+f22,c,c,total,P,e,11,e12,e,11+,e,12,P,e21,e22,e,21+,e,22,total,e,11+,e,21,e,12+,e,22,e,11+,e,12+,e,21+,e,22,当一条规则插入到,CR-tree,中的时候,检索,CR-tree,看是否有规则用剪枝,1,约束能被剪掉或者能剪掉其它的规则,.,对于规则,R:P-c,计算,P,与,c,的,2,相关值,.,选择,2,值大于阈值,(3.84),且正相关的规则,.,在类关联规则将要插入到,CR-Tree,时测试,.,f11e11,规则剪枝,(3),Algorithm1,:Select rules based on database coverage,Input,:,a set of rules and a coverage threshold,Output,:,a subset of rules for classification,1.,sort rules in the rank descending order;,2.,for each data object in the training data set,3.,cover-count=0;,4.,/for,5.,while both the training data set and rule ser are not empty,6.,for each rule R in rank descending order,7.,find all data objects matching rule R.;,8.,If R can correctly classify at least one object,9.,select R and increase the cover-count of those objects matching R by 1;,