基于粗集的混合变量决策树构造算法研究

基于粗集的混合变量决策树构造算法研究 第30卷第3期 2007年3月 合肥工业大学(自然科学版) JOURNALOFHEFEIUNIVERSITYOFTECHNOLOGY Vo1.30No.3 Mar.2007 基于粗集的混合变量决策树构造算法研究 胡学钢,张冬艳 (合肥工业大学计算机与信息学院,安徽合肥230009) 摘要:文章提出混合变量决策树结构,并在此基础上提出基于粗集理论的混合变量 决策树构造算法RSH2, 算法在每个结点选择尽可能少的属性明确划分尽可能多的实例,减小了决策树规 模,且易于理解.将RSH2 算法与ID3算法及基于粗集的单变量决策树算法HACRs进行实验比较,结果明 该算法有良好性能. 关键词:单变量决策树;多变量决策树;粗糙集合;归纳学习 中图分类号:TP18文献标识码:A文章编号:1003—5060(2007}03—0257—04 Onthedecisiontreeinductivealgorithmbasedontheroughsettheory HUXue-gang.ZHANGDong-yan (SchoolofComputerandInformation,HefeiUniversityofTechnology,Hefei230009,CNna ) Abstract..Thestructureofthehybriddecisiontreeandtheconstructingalgorithmforthestruct ureare proposedinthispaper.ThehybriddecisiontreealgorithmRSH2,whichiSbasedontheroughs et theory,selectstheattributesasfewaspossiblewhichcanclassifytheinstantsasmanyaspossib le. Thus,thescaleofthedecisiontreewillbediminishedandthetreewillbeeasiertounderstand.In ad— dition,theconditionalinformationentropybasedreductionalgorithmisusedbeforeconstruc tingthe treeSOthattimewillbesaved.ThecomparisonamongthealgorithmsRSH2,ID3andHACRs based ontheroughsetismadewithexperiments,andtheRSH2algorithmisprovedtohavegoodperf orm— ance. Keywords:univariatedecisiontree;multivariatedecisiontree;roughset;inductivelearning 传统决策树构造算法,对每个结点采用启发 式函数(即属性选择判据)选择分裂属性生成子结 点,以获得较为理想的结果.研究人员已提出很 多属性选择判据,如ID3算法的信息熵J,C4.5 的信息增益函数等,这些判据都是基于信息论 度量的,存在种类偏见问题l1J,且容易陷于局部最 优.另外,传统的单变量决策树构造算法在一个 结点只选择一个属性进行分裂,忽略了属性之间 的相互关系,因而可能引起重复子树问题,且某些 属性可能被多次检验J.为此,出现了多变量归 纳学习系统,即在树的各结点选择多个属性的组 合作为分裂属性,一般表现为通过数学或逻辑算 子将一些属性组合起来,形成新的属性作为分裂 属性,因而称这样形成的决策树为多变量决策 树l4J.这种方法可以减小决策树的规模,并且对 于解决属性间的交互作用和重复子树问题有良好 的效果,然而可能会导致搜索空问变大,计算复杂 性增加.比较有代表性的多变量决策树算法的构 造方法及其性能如下:OC1算法采用动荡算法 调整属性的系数来组合属性,由于动荡的顺序和 次数不定,因而存在不确定性.FRINGE算法 用逻辑算子组合属性以构造新的属性,仅允许一 个结点的属性与其父结点或祖父结点的属性合 并.该算法可能会构造出更复杂的决策树.文献 E6]研究了用属性的合取来表示布尔函数的问题, 在算法中必须事先规定合取项的最大值,如选择 不当会影响算法的效率. 由文献[7]提出的粗糙集合理论,从新的视角 收稿日期:2006—02—21 基金项目:安徽省自然科学基金资助项目(050420207) 作者简介:胡学钢(1961--),男,安徽当涂人,博士,合肥工业大学教授,硕士生导师 258合肥工业大学(自然科学版)第30卷 对知识进行了定义,把知识看作是关于论域的划 分,引人等价关系来讨论知识.该理论主要用于 知识的约简及知识依赖性,因而可以作为机 器学习和复杂数据分析的工具.将粗集理论用于 决策树优化已经出现了很多结合点,如初始属性 的约简和预剪枝等,还出现了基于粗集的增量式 决策树,而利用粗集理论作为属性选择判据也得 到了关注并出现了一些算法.文献[3]中利用条 件属性相对于决策属性的核,用相对泛化的概念 进行多变量分裂,可以构造非常简单的树.但是, 当核中的属性较多时,决策树结点中的属性过多, 因而对结点分裂条件的描述十分困难,使所构造 的决策树难以理解.基于粗集的单变量决策树 HACRs算法J,选择能明确分类实例最多的属 性作为结点的分裂属性,然而由于受到属性分类 能力的限制,在很多情况下,单个属性的正域为 空,不能对任何实例明确分类,最终回归到传统的 决策树算法,因而不能达到预期的效果.因此,选 择属性的方法成为重要的问题. 研究表明,单变量决策树的复杂度主要由树 的结点个数决定,而多变量决策树的复杂度主要 由结点中属性的个数决定J.本文提出混合变量 决策树结构及基于粗集的混合变量决策树学习算 法,算法在每个结点根据具体的数据集,选择尽可 能少的属性明确分类尽可能多的实例,以此决定 当前结点分裂属性的个数,因而在某结点可能采 用单变量,也可能采用多变量分裂,故称之为混合 变量决策树. 1粗集理论概述 在粗糙集合中,成员关系不再是一个原始概 念,认为不确定性与成员关系有关L1...下面给出 粗糙集合的几个基本定义,其中,假设知识库 K一(U,R). 定义1设PR且P?j2『,P中的所有等价 关系的交集称为P之上的一种不可区分关系 (indisernibiIityrelation),记作IND(P). 定义2设集合XU,称R(X)一{YI(y EU/IND(R))^(YX))为X的下近似, R(X)一{YI(y?u/IND(R))^(YNx?j2『)) 为X的上近似,BNR(X)一R(X)一R(X)为X 的边界或边界区域.POSR(X)一R(X)称为集 合X的R一正区域. 定义3设PR是等价关系的一个族集, 关系rEP,若IND(P)一IND(P--{r)),则称关 系r在族集P中是可缺的,否则就是不可缺的; 若族集P中的每个关系都是不可缺的,则称族集 P是独立的,否则就是依赖的或非独立的. 定义4若QGP是独立的,且IND(Q)=== IND(P),则称Q是族集P的一个约简.在族集 P中,所有不可缺的关系集合称为族集P的核 (CORE),表示为CORE(P). 2混合变量决策树算法RSH2 2.1相关定理 假设信息系统R一<U,A>,其中U为论域, A=CND为所有属性的集合,C为条件属性,D 为决策属性,CND一. 定理1对于相容决策系统R,设Q为一个 D一约简,则POSQD=U. 证明由约简的定义知Card(POSQ(D))一 Card(POSc(D));又因R是相容决策系统,且 POScD=U,所以POSQD=U.得证. 定理2设C1,C2c=c,Card(POScl(D))? Card(POSq【J(D)). 证明设IND(C)一{X,X,…,X), IND(C2)一{Y1,Y2,…,),IND(D)一{Z,Z2, … ,),由定义可得IND(CUC2)一{Rs:Rs— Xny).其中XEIND(C),y,EIND(C2),从 而可以推出任意Rs—Xny,X.又因为 POSq(D)一U{X:XZ,)(一1,2,…,;J一 1,2,…,).因此,POSq【J(D)一U{Rs:Rs ZJ)(s?*).综上所述PO(D)GPOSquC' (D),命题得证. 为描述方便,将当前状态下属性集能精确分 类的对象集的比例作为属性集分类能力.因此, 可用下式作为条件属性集合P对分类属性Q的 分类能力的描述,即 k—yP(Q)一card c ( a P rd O ( Sup( ) Q)) 定理3设决策属性D有m个等价类L3],令 一 , y{X,:X,?)(i一1,2,…,) , X. ?U/~NIXO' 一 . {XJ:XJ(2=,V) 则U一{Z,Z,…,+)为一个等价关系. 证明见文献[-33. 2.2属性集选择方法 为快速寻找分裂属性集,RSH2算法根据信 息熵对属性进行预排序,求子集时,优先选取信息 熵小的属性.因此,对于属性个数相同的属性子 第3期胡学钢,等:基于粗集的混合变量决策树构造算法研究259 集,前面子集的正域大多数情况下大于后面子集 的正域.设定属性个数i的初始值为1并递增, 逐个寻找个数为i的子集,一旦寻找到相对正域 不为空(即依赖度足>0)的属性组合,后面的组合 就不必再考虑.选择属性集的具体方法如下: fori=1tolREDb(C)l {逐个选取元素个数为i的子集:S REDD(C),fSf:,计算依赖度k,若走> 0,选择S作为当前的结点,break;) 2.3算法描述 一 个信息系统lenses,见表1所列. 表1一个信息系统lenses C D 基于上述定理和算法,下面给出RSH2算法 的一般步骤. 算法RSH2(R): 输入:约简后的信息系统R,其中条件属性c,决 策属性D 输出:决策树T ( 按信息熵递增对属性进行排序; fori:1tolCl {逐个选取元素个数为i的子集S(按属 性信息熵之和递增的顺序选取):sc, fS{=,计算依赖度k,若是>O,选择S 作为当前的结点,break;} 利用定理4划分论域U一{Z,Z2,…, Zm+1}; 标记,,…,为叶结点; If+l<> {令U为Z+中所包含实例的集合; RSH2(R);} Else标记为叶结点; } 对表1所列的lenses数据集,RSH2算法所 构造的决策树如图1所示.其中,共12个结点,7 个叶子结点.用ID3算法构造的决策树如图2所 示,共15个结点,9个叶子结点.从中可以看出, RSH算法构造的决策树结构比ID3算法构造的 决策树简单. 图1RSH算法构造的混合变量决策树 Class=3Class=2Class=1Class=3Class=3 图2ID3算法构造的单变量决策树 3实验 为了比较算法的性能,本文在Matlab平台下 实现了RSH2算法及几种经典算法,并选用UCI 国际机器学习数据库中的6个数据集,比较了几 种算法所构造的决策树的结点数.实验环境为 P42.0G,256M内存,实验结果见表2所列.在 实验中,采用文献[11]提出的CEBARKNC算法 对初始属性进行了约简.除Zoo数据集外,有关 HACRs算法的数据摘自文献[12]. A—l2l2l2l2l2l2l2l2l2l2l212 A—ll22ll22ll22ll22ll22ll22 A,llll2222llll2222llll2222 A—llllllll2222222233333333 000unM" 260合肥工业大学(自然科学gt)第30卷 由实验数据可见,在大部分情况下,HACRs 算法在结点数目上对ID3算法的改进并不明显, 而RSH2算法所构造的决策树的规模要小得多. 另外,本文还比较了HACRs算法和RSH2 算法的时间性能,结果见表3所列.RSH2算法 的时间性能接近于HACRs算法,有时甚至高于 HACRs算法.然而,对Balance和Monks-2数 据集的时间性能不够理想,主要原因是优化过程 中减少的结点数较多.因此,决策树规模显着降 低与时间性能适当下降这一交换是可以接受的. 表2几种算法所构造的决策树的结点数比较 4结论 表3基于粗集的决策树构造算法时间性能比较 RSH2算法构造的混合变量决策树采用混合 变量检验方法,使生成的决策树在结点复杂度尽 可能小的前提下叶子节点明显减少.实验证明, 本文的算法是有效的.在实际应用中,结合领域 知识,用户还可以设定每个结点中分裂属性的最 大和最小个数等参数,以更好地解决实际问题. 因此,本算法可以适用于较多实际问题的解决. 寻找更有效的启发式方法来选择最佳的属性 组合,以及算法时间性能的进一步提高等问题,还 有待进一步研究. 参考文献 [1]QuinlanJRInduction0{decisiontrees[J].Machine Leaming,1986,1:8l一106. [2]QuinlanJR_C4.5:Programsformachinelearning[M]. SanMateo,CA:MorganKaufmannPublisher,1993: 56——102. [3]苗夺谦,王珏.基于粗糙集的多变量决策树构造方法 [J].软件,1997,8(6):425--430. [4]MurthySK,KasifS,SalzbergSASystemforinductionof obliquedecisiontrees[J].JournalofArtificialIntelligence Research,1994,2:l一33. [5]PagalloG.LearningDNFbydecisiontrees[A].Proceedings oftheEleventhInternationalJointConferenceonArtificial Intelligence[C].Detroit,MI:MorganKaufmann,1989: 639—644. [6]RivestRLearningdecisionlists[J].MachineLearning, 1987,2:229—246. [7]PaMak乙Roughsets:theoreticalaspectsofreasoninga— boutdata[M].Netherlands:KluwerAcademicPublish— ers,1991:35—72. [8]WeiJinmao,HuangDao,WangShuqin,eta1.Roughset baseddecisiontree[A].Proceedingsofthe4thworldCon— gressonIntelligentControlandAutomation,Shanghai,P. RChina,2002[c].2002:lO—l4. [9]史忠值.知识发现[M].北京:清华大学出版社,2002: lO,3O. [1O]王国胤.Rough集理论与知识获取[M].西安:西安交通 大学出版社,2001:1--4. [11]王国胤,于洪,杨大春.基于条件信息熵的决策表约简 口].计算机,2002,25(7):759—766. [12]卫金茂.数据挖掘若干问题的研究[D].上海:华东理工大 学自动化研究所,2001. (责任编辑张秋娟)