基于粗集的混和变量决策树构造算法研究ahref=11a

基于粗集的混和变量决策树构造算法研究1胡学钢张冬艳2（合肥工业大学，计算机与信息学院，安徽，合肥，230009）摘要：决策树学习算法是一种分而治之的算法。传统的单变量决策树学习算法忽略了属性之间的关系，导致规模较大，而多变量决策树较为复杂，难以理解。本文提出混合变量决策树结构，并在此基础上提出基于粗集理论的混合变量决策树构造算法RSH2，算法在每个结点选择尽可能少的属性明确划分尽可能多的实例，减小了决策树规模，且易于理解。将RSH2算法与ID3算法以及基于粗集的单变量决策树算法HACRs进行实验比较，结果表明该算法有着良好的性能。关键词：单变量决策树；多变量决策树；粗糙集合；归纳学习中图分类号：TP18ResearchonDecisionTreeInductiveAlgorithmBasedonRoughSetTheoryHUXue-gang,ZHANGDong-yanSchoolofComputerandInformation,HefeiUniversityofTechnology,Hefei230009,Anhui,P.R.ChinaAbstract:Decisiontreelearningalgorithmsaredivide-and-conqueralgorithms.Traditionalunivariatedecisiontreesneglectthecorrelationofattributes,andthescaleofthetreewillbeverylarge.Multivariatedecisiontreescandecreasethescaleofthetreebutarecomplexandnoteasytounderstand.Tosolvetheseproblems,thestructureofhybriddecisiontreeandtheconstructingalgorithmforthestructureisproposedinthispaper.HybriddecisiontreealgorithmRSH2,whichisbasedonroughsettheory,selecttheattributesasfewaspossiblewhichcanclassifytheinstantsasmanyaspossible.Thus,thescaleofthedecisiontreewillbediminishedandthetreewillbeeasiertounderstand.Inaddition,conditionalinformationentropybasedreductionalgorithmisusedbeforeconstructingthetreesothattimewillbesaved.ThecomparisonbetweenRSH2,ID3andHACRsalgorithmbasedonroughsetiscarriedoutwithexperiments,andtheRSH2algorithmisprovedtohavegoodperformance.Keywords:univariatedecisiontree;multivariatedecisiontree;roughset;inductivelearningClassnumber：TP181引言传统决策树构造算法对每个结点采用启发式函数（即属性选择判据）选择分裂属性生成子结点以获得较为理想的结果。研究人员已提出很多属性选择判据，如ID3算法的信息熵[1]、C4.5的信息增益函数[2]等，这些判据都是基于信息论度量的，存在种类偏见问题[1]且容易陷于局部最优。另外，传统的单变量决策树构造算法在一个结点只选择一个属性进行分裂，忽略了属性之间的相互关系，因而可能引起重复子树问题，且某些属性可能被多次检验[7]。为此，出现了多变量归纳学习系统，即在树的各结点选择多个属性的组合作为分裂属性，一般表现为通过数学或逻辑算子将一些属性组合起来形成新的属性作为分裂属性，因而称这样形成的决策树为多变量决策树[3]。这种方法可以减小决策树的规模，并且对于解决属性间的交互作用和重复子树问题有良好的效果，然而，可能会导致搜索空间变大，计算复杂性增加。比较有代表性的多变量决策树算法的构造方法及其性能如下：OC1算法[3]采用动荡算法调整属性的系数来组合属性。由于动荡的顺序和次数不定，因而存在不确定性。FRINGE算法[4]用逻辑算子组合属性以构造新的属性，仅允许一个结点的属性与其父结点或祖父结点的属性合1本文受安徽省自然科学基金课题（编号050420207）资助。2胡学钢，1961.8，安徽当涂人，博士，教授，研究方向：知识工程，数据挖掘，E-mail：[e-mail]；张冬艳，1981.12，安徽合肥人，硕士研究生，研究方向：知识工程，数据挖掘。并。该算法可能会构造出更复杂的决策树。Revest[5]研究了用属性的合取来表示布尔函数的问题，在算法中必须事先规定合取项的最大值，如选择不当会影响算法的效率。由PawlakZ.于1982年提出的粗糙集合理论[6]从新的视角对知识进行了定义，把知识看作是关于论域的划分，引入等价关系来讨论知识。该理论主要用于知识的约简及知识依赖性分析，因而可以作为机器学习和复杂数据分析的工具。将粗集理论用于决策树优化已经出现了很多结合点，如初始属性的约简和预剪枝等，还出现了基于粗集的增量式决策树，而利用粗集理论作为属性选择判据也得到了关注并出现了一些算法。文献[7]中利用条件属性相对于决策属性的核，用相对泛化的概念进行多变量分裂，可以构造非常简单的树。但是，当核中的属性较多时，决策树结点中的属性过多，因而对结点分裂条件的描述十分困难，使所构造的决策树难以理解。基于粗集的单变量决策树HACRs算法[8]选择能明确分类实例最多的属性作为结点的分裂属性，然而由于受到属性分类能力的限制，在很多情况下，单个属性的正域为空，不能对任何实例明确分类，最终回归到传统的决策树算法，因而不能达到预期的效果。因此，选择属性的方法成为重要的问题。研究表明，单变量决策树的复杂度主要由树的结点个数决定，而多变量决策树的复杂度主要由结点中属性的个数决定[9]。因此，在有些情况下，在决策树的某些结点采用单变量，另外一些结点采用多变量可以很好地对实例进行划分。基于这一原则，本文提出混和变量决策树结构及基于粗集的混合变量决策树学习算法，算法在每个结点根据具体的数据集选择尽可能少的属性明确分类尽可能多的实例，以此决定当前结点分裂属性的个数，因而在某结点可能采用单变量，也可能采用多变量分裂，故称之为混和变量决策树。本文结构如下：第2部分介绍粗集的基本理论，第3部分描述并讨论基于粗集的混和变量决策树学习算法RSH2，第4部分通过实验将RSH2算法和经典的单变量决策树算法ID3以及基于粗集的决策树算法HACRs比较，并进行分析，最后给出总结。2粗集理论概述[10]在粗糙集合中，成员关系不再是一个原始概念，认为不确定性与成员关系有关。下面给出粗糙集合的几个基本定义，其中，假设知识库K=(U,R)。定义1设P⊆R且P≠∅，P中的所有等价关系的交集称为P之上的一种不可区分关系(indisernibilityrelation)，记作IND(P)。定义2设集合X⊆U，称R*(X)={Y∣(Y∈U/IND(R))∧(Y⊆X)}为X的下近似(lowerapproximation)，R*(X)={Y∣(Y∈U/IND(R))∧(Y∩X≠∅)}为X的上近似(upperapproximation)，BNR(X)=R*(X)−R*(X)为X的边界或边界区域(boundary)。POSR(X)=R*(X)称为集合X的R-正区域(R-positiveregion)。定义3设P⊆R是等价关系的一个族集，关系r∈P，若IND(P)=IND(P－{r})，则称关系r在族集P中是可缺的(dispensable)，否则就是不可缺的；若族集P中的每个关系都是不可缺的，则称族集P是独立的(independent)，否则就是依赖的或非独立的。定义4若Q⊆P是独立的，并且IND(Q)=IND(P)，则称Q是族集P的一个约简(reduct)。在族集P中，所有不可缺的关系集合称为族集P的核(CORE)，表示为CORE(P)。3基于粗集的混和变量决策树构造算法RSH23.1相关定理假设信息系统R=〈U，A〉，其中U为论域，A＝C∩D为所有属性的集合，C为条件属性，D为决策属性，C∩D=Φ。定理1对于相容决策系统R，设Q为一个D-约简，则POSQD=U。证明：由约简的定义知Card（POSQ(D)）＝Card（POSC(D)）；又因R是相容决策系统，且POSCD＝U，所以POSQD=U。得证。定理2设C1,C2⊆C，Card（POSC1(D)）≤Card（POSC1∪C2(D)）。证明：设IND(C1)={X1,X2,…,Xl}，IND(C2)={Y1,Y2,…,Ym}，IND(D)={Z1,Z2,…,Zn}，由定义可得IND(C1∪C2)={RS:RS=Xi∩Yj}，其中Xi∈IND(C1)，Yj∈IND(C2)，从而可以推出任意RS=Xi∩YjX⊆i。又因为POSC1(D)=∪{Xi:Xi⊆Zj}（i=1,2,…,lj=1,2,…,n）因此POSC1∪C2(D)=∪{RS:RS⊆Zj}（s≤i*j）综上所述POSC1(D)POS⊆C1∪C2(D)，命题得证。为描述方便，将当前状态下属性集能精确分类的对象集的比例作为属性集分类能力。因此，可用下式作为条件属性集合P对分类属性Q的分类能力的描述：k=γP(Q)=(U)card))((POScardQP定理3[7]设决策属性D有m个等价类，令),...,2,1}(:{)(/miYXXijjCINDUXijZ=⊆=∈Υ},:{)(/1iYXXijjCINDUjXmZ∀⊄=∈+Υ则U＝{Z1,Z2,…,Zm+1}为一个等价关系。证明：见文献[7]。3.2属性集选择方法为了快速寻找分裂属性集，RSH2算法根据信息熵对属性进行预排序，在求子集时，优先选取信息熵小的属性。因此，对于属性个数相同的属性子集，前面子集的正域在大多数情况下大于后面子集的正域。设定属性个数i的初始值为1并递增，逐个寻找个数为i的子集，一旦寻找到相对正域不为空(即依赖度k0)的属性组合，后面的组合就不必再考虑。选择属性集的具体方法如下：fori=1to|REDD(C)|{逐个选取元素个数为i的子集：S⊆REDD(C)，|S|=i，计算依赖度k，若k0，选择S作为当前的结点，break；}3.3算法描述基于上述定理和算法，下面给出RSH2算法的一般步骤。算法RSH2（R）输入：约简后的信息系统R，其中条件属性C，决策属性D输出：决策树T{按信息熵递增对属性进行排序；fori=1to|C|{逐个选取元素个数为i的子集S（按属性信息熵之和递增的顺序选取）：SC,|S|=i,⊆计算依赖度k，若k0，选择S作为当前的结点，break；}利用定理4划分论域U={Z1,Z2,…,Zm+1}；标记Z1,Z2,…,Zm为叶结点；IfZm+1Φ｛令U为Zm+1中所包含实例的集合；RSH2（R）；｝Else标记为叶结点；}表1一个信息系统lensesCUA1A2A3A4D111113211122311213411221512113612122712213812221921113102112211212131221221132211314221221522213162222317311131831123193121320312212132113223212223322132432223对如表1所示的lenses数据集，RSH2算法所构造的决策树如图1所示，其中共12个结点，7个叶子结点。用ID3算法构造的决策树如图2所示，共15个结点，9个叶子结点。可以看出，RSH算