融合无监督和监督学习策略生成的多分类决策树解读

1、2小型微型计算机系统2004 年融合无监督和监督学习策略生成的多分类决策树邱德红，陈传波（华中科技大学计算机科学与技术学院湖北武汉430074）摘要：提出了一种融合无监督和监督两种学习策略生成决策树的方法.它首先利用尢监仰聚类方法能够发现待分类样本之间的内在联系和规律的特点，确定出最为符合多类样本分布特征的决策树的树型，继而利用监督学习支持向量机的方法对样本进行准确的分类.通过采用核函数和不对称的Lagrangian系数限制条件，支持向量机很好的解决J'样本特征空间上的线性不可分性和决策树型确定过程中出现的训练样本不对称性的影响.该方法具有较高的计算效率和准确性，在实验中取得比较好的结

2、果.关键词：多分类决策树：无监督聚类：支持向量机中图分类号：TP391.41文献辨识码：A文章编号：1000-1200（2001）01-0555-05ConstructionofMulti-classificationDecisionTreeCombiningUnsupervisedandSupervisedLearningStrategyQIUDe-hong,CHENChuan-bofScfiaoCofCoTMiacrandfTtcfinoyofScienceanscfinoy.430074,ckincL)Abstract：Inthispaper,anewmethodwhichcombine

3、sunsupervisedandsupervisedlearningstrategyisputforwardtoconstructthemulti-classificationdecisiontree,Itfirstlyusestheunsupervisedclusteringtodeterminethestructureofthemulti-classificationdecisiontree,whoseeachnodehasabinarybranch.Thexmsupervisedclusteringisabletofindouttherelationshipbetweenthemulit

4、-classes,thereforethedecisiontree,3structuredeterminedbyitisthebestonethatfitstothedistributionofmulit-classesinfeaturespace.Then,asupervisedlearningmethod,i.e.supportvectorrLachine,isusedtoclassifythetwogroupsofsaziplesofeachnodeofthedecisiontree.Mostcasesthemulti-classescannotbeclassifiedbyalinear

5、hypeiplane,kernelfunctionsarethereforeintroducedintotosolveit.Simultaneously,uns>Tiimetricalconstrainso£Lagrangiancoefficientsaresettoovercomethenegativeinfluencesofunbalancedtrainsamples.Theseeffortsguaranteetheefficiencyandaccuracyofthemulti-classificationdecisiontree.Satisfyingresultswere

6、obtainedinexperiment.Keyrordi：multi-classificationdecisiontree;unsupervisedclustersupportvectorrnachine1引言多分类问题是一个比较常见的问题，机器学习理论和方法的研究在解决二分类问题上取得r比较满意的结果：二多分类问题虽然也行研究比,但在理论构架和现实方法上还有相当大的困琲.目前解决多分类问题主要运用多分类决策数,决策树上的每一个节点对应一个二分类器，实际上是利用二分类方法解决多分类问题.生成类分类决策树的方法有（1）'一对其余决策树上s个节点对应的二分类器只判断是某一类还是其余类：（

7、2）'一对一'，决策树上MRD/2个节点对应的二分类器只能对类中的两类作出是否判断：（3）'一半对一半、即决策树的节点对应的二分类器将节点上的类二等分（允许一类别在两个节点上由现,直至叶节点.决策树上节点的数目为.其中为大于或等于log：。）最小整数.这三类方法生成的决策树虽然具有不同的计算效率和分类效果,但各自在应用中取得r比较好的结果无监督学习和监督学习是机器学习方法研究的二大策略.无监督学习方法如无监督聚类（笈是从样本的特征向身出发,研究通过某种算法特征比较相似的样本聚集在一起，从而达到区分具有不同特征的样本的目的.无监督聚类的优点是可以发现样本中附含的共性和规律

8、,但是由于没有专家知识的监督,分类的准确性有限.监督学习方法是通过对已知类别的训练样本的学习，实现而未知样本的分类判断.支持向量:机二是一种主要用于二分类的准确率比较高的监督学习方法，其基础是统计学习理论中的结构风险最小化原则.它在许多领域得到了很好的应用必汕.收稿日期，2820805作者荷介，邱讴红.博士.主要研究方向为机器学习和生物测定学：陈传波.教授博士生导师.主要研究方向为图像处 理和计算机网络应用.E-本文提出一种将无监督聚类和监督学习的支持向量机方法结合起来生成多分类决策树的方法.它的基本思想如下：待方法的多类样本可以看成是某一宏观层面之上的剌激机制激励下，或者是在某个进程中产生的

9、.该宏观层面之下剌激机制的差异，或者是进程中的不同阶段杼致不同类的出现，差异小的刺激机制,或者相邻进程阶段产生的类别之间的特征较为接近,反之则分散.因而.多类之间虽然具有向异性.但他们在特征空间的分布上有内在规律.如果决策树的树形结构能够体现多类之间的内在规律，就可能在计算效率和准确性上获得较好的均衡，从而提高决策树的性能.本文介绍的方法的目的是通过无监督聚类确定反映多类之间分布规律的决策树的树型，继而利用监督学习支持向母机方法的准确率高的特点对分布接近的类别进行详细分区.使多分类决策树具疗较高的计算效率和准确率.2多分类决策树的树型确定一个AQ23）类的多分类问题可以描述为：给定组训练样本：

10、（心，（布仙），出。0,（3）0,（心力），（心;“）,L=L+1：+L为N类训练样本的总数目,必£R,i=l,-,L是d维空间上的特征向量，y31,2,X）,n=l,N是N类标号.多分类问题即函数F：Y一1,2,不确定待分类向量x的类别标号y.多分类问题可以通过由二分类器为节点构成的决策树来解决.由于待分类的N类样本通常是其形成的刺激机制在某个宏观层面之下的差异.或者是同一进程的不同阶段形成的，刺激机制差异的大小和进程阶段相隔时间的久远导致N类样本在特征空间上分布有一定的规律.如图1所示的*6的多分类问题，左下三类（。、）和右上三类（+、X、*之间的刺激机制相差较远，而左下三类口、

11、）之间、右上三类（+、X、约之间的刺激机制相差较小.如果多分类决策树型能够反映出类样本之间的分布规律，继而实施轻重有别的详细区分.必将能获得比较优秀的性能，为此设计以下利用无监督聚类确定决策树型的方法.Fig.1Distributionofmulti-classessamplesonthefeatxirespace第1步:计算N类训练样本共L个特征向量中的任何两个特征向量，比如工彳,力之间的Minkowski距离“XI/一/<5=1>皿'口以p=2/-I第2步：将N类训练样本共L个特征向量编号为1,L号叶节点,从1号叶节点开始在C2个距离之中找到最小距离，将对应的两个叶节点

12、（比如为对力,）做个连接,形成一个二叉树枝.将此连接看成为一个新叶节点,编号为L+L该新叶节点到其余某个叶节点MkXr,s（即MX,之外的节点）之间的距离定义为已经连接的两个叶节点（益，力）与该节点之间的最小距离，即cL-i,k=ziin（i.k,d«,i）.第3步:按照第2步同样的规则，在新生成的叶节点和其余叶节点之中继续生成一个新的二叉连接,重灾直到生成最后一个二叉连接而成为一棵聚类树.如图2所示的一棵聚类树，它对应于图1中的60个样本.图2无赛将聚类生成的聚类树Fig-2Decisiontreeproducedbyunsupervisedclustering第4步:将第3步中最

13、后生成的一个二叉连接的左右两个分枝连接的最底层的叶节点（即1,L叶节点J对应的特征向量划分到的左右两个集介"8中.依次检查待分类的1,N类样本的特征向量，如果第n类的L个特征向量被聚类到左右两个集合S/、&.中，数目分别为1*和1+1*二3则依下情况处理： 如果1大于或等于1右且集含税中特征向量的个数大于则将集合义中对应的k个特征向班移至集合Sx 如果b大于或等于g但柒含SL中特征向比的个数等于则将集合乱中对应的J个特征向班移至集合义 如果k大于1,且集合/中特征向量:的个数大于则将集合乱中对应的L*个特征向量移至集合义 如果k大于1,但集合/中特征向母的个数等于则将集合&a

14、mp;中对应的k个特征向量移至集合治至此可以确定决策树上的一个二叉节点,它的训练样本是非空的左右两个集含、S,将集合，中的特征向量的标签设定为7,集合Si中的特征向身的标签设定为乜.它们将用于训练支持向量机来生成该节点对应的二分类器.第5步:分别将左右两个集含夕、夕中包含的特征向垃看成一个新的分类问题,重宴第1步到第4步,直到左右两个集合冬、丸中均只包含N类训练样本中的某一类样本.从而确定出完整的X分类决策树的树型.图1所示的X=6的分类问虺对应的决策树型如图3所示.无监督聚类方法确定决策树树型与一对其余，'一对一'和'一半对一半确定决策树树型方法上是不一样.后三者对于

15、所彳m的多分类问题采用的决策树型均是固定的,而这4期邱德虹等：网含无监密和监督学习策略生成的多分类决策树3超平面即为求(w ,b)使得最小,它等效里介绍的方法将依据X类样本之间的联系和分布规律生成相应的决策树型.决策树型本身在一定的程度上反映fN类样本之间的差异大小,可以一定程度的降低二分类的难度.以此为基础的X分类问题的计算效率将随决策树型有所变化.如果假设这些方法均采用同样的二分类方法，二分类器的计算到杂度可大致描述为夕=cnA,其中为系数，n为训练样本数，X心为发杂度指数.则对于N类、样本总数为L的多分类Fig.3Thestructureofdecisiontreeproducedbyu

16、nsupervisedclustering问题，'一对其余'生成的决策树的计算到杂度为NZ/：一对一'生成的决策树的计算发杂度为0.5cN(N-1)(/,+")Al和L为为应两类的训练样本的数目；一半对一半生成的决策树的计算发杂度约为C(21)(/')2，其中k为大于或等于log：(N)的最小整数，训练样本数1'逐步递减.无监督聚类生成的决策树的节点数小于一半对一半和一对一'生成的决策树，其节点的训练样本数小于'一对其余'的生成方法，递减速度大于一半对一半的生成方法.综合来说,无监督聚类生成的决策树具有比较高的计算效率.

17、3支持向量机二分类器无监督聚类生成的决策树上的每个二叉节点对应于一个二分类器.无监督聚类分类的准确率有限.这里采用准确率高的支持向量机来生成决策树上每个二叉节点对应的二分类器.它的训练样本分别是该二叉节点连接的左右两个集合、Sx中的样本，它们可以统一表示为：(X1,yi),Xi,Rhttp： ics. uci. edu/ al earn MLR Repository, html,yi(+1,-1)，训练样本数为1.支持向身机是一种建立在统计学习理论基础上的机器学习方法他采用学习理论的结构风险最小原则”口.其学习目的是在所有分割超平面中、确定最优超平面H：wx+b=0,该平面到两类之间的间隔最大

18、,且满足一下约束条件：wxt+b>+1if=+1卬+b<-1if凡=-1H卬，)=Tj两类之间的间隔为11"口，因此，确定最优分割求解二次优化问题,即求Lagrangian系数。使目标函数W(u)最大：W(a)=1f)2i-l满足条件。,2,1)和£%匕=0.然后可求i-l得(W,b)为：IW=atyixi,b=-cox+x_/-12X和工分别是两类向量的支持向量.与它们对应的%>0,其余的a1=0,支持向量机学习确定的分类器为：/(-V)=sign(CDx+b)=sig，(22%乂G,幻+小无监督聚类确定的分类决策树的二叉节点对应的训练样本往往不具有线性

19、的可分性.此时可以引入适当的核函数K(,)=<1)(x06(x0,将将原空间中的向量映射到另一特征内积空间中去进行分类.此时目标函数(1)相应修正为：j/W(a)=一£%丁/&%)满足约束条件：引入核函数''后新特征向fibc的分类器法则如下：f(x)=signZayKa,x)+/Iz核函数KGi,xj)需要满足MerceH定理【2】，经常采用的核函数有多项式函数:K(x,y)=(x尸l)d,高斯径向基函数K(x,y)=exp-IJ和多层感知器函数：K(x»y)=taiili(Zc(x>)-/)训练样本中如果存在不可分的样本(噪音)，就需

20、要适度对待训练误差.此时，如果过份地强调减小训练误差可以导致二分类器的性能恶化.闪为这样生成的二分类器可能过于颈向训练样本的个性特征,而没行体现出训练样本整体共性，不利于对未知样本的判断.这时候需要采用柔性边界，它依然可以通过求解最大目标函数得到,然而需要将约束条件a10改为0Wa&WC.C可以协调训练误差和分类器的综含能力,其物小型微型计算机系统MINI-MICRO SYSTEMS第25卷第4期2004 年 4Vol.25 No.4Apr.2004理的朝祥可以看成是与参数九对应的训练样本为分类边界的作用力大小的变化范围.无监督聚类生成的决策树型时经常会出现的左右两个集合片、Sl中的样

21、本数目的不均衡，数目少的一边对分类边界确定的作用合力的大小往往有限，因而对分类边界的确定影响力弱.为此我们对数目不等的两类样本确定不对称的作用力变化范闱，即使0WT,+<C,0WT,WC,G和C与训练样本数目相关,以此来消除训练样本数目不均衡性的影响.4实验结果我们采用Cleveland心脏病变数据来检验上文介绍的融含无监督聚类和监督学习支持向量机生成的多分类决策树的Cleveland心脏病变数据在一个知名的有关机器学习研究的网站1上公布,成为许多分类方法的检验数据.这组数据包含有303个样本,每个样本的特征向身的维数为13.其中有6个样本的特征向量不完整，这里将它们从样本中剔出，因而可

22、使用的样本数据为297个.样本的特征向量被分为5类,其中心脏没有病变的正常情况的样本数目为160个,标号为0.其余的样本为心脏彳j病变的特征样本，标号依此为1、2、3和4,对应的样本数目分别为54、35、35和13,标号递增表示心脏病变的程度越发历害.我们对于每一类样本,选择其中的四分之三为训练样本，数目共为223个，其余的四分之一用来验证，数目共为74个.利用第二节介绍的无监督聚类方法,首先从224个训练样本确定决策树的树型，结果如图4所示.为平衡样本特征向母各个特征值对决策树型的影响程度，对所行样本的特征向班的每项特征值进行了正规处理，即进行了以下运算：8=一,-min（e）表示所有样本特

23、征向量的同max（0）min（0）一项特征值构成的列向5L从图4可见，无监督聚类方法确定的决策树型明确地反映出Cleveland心脏病变数据中几类样本之间的关系，如正常的样本向量（0）与病变样本向量首先被区分开来,严重病变的样本向身（3、4）将与轻度病变（1、2）的样本向量区分开来，最后区分比较难以区分的两类样本.无监督聚类方法生,成的决策树型不仅很好的体现/心脏病变这一进程中不同阶段的特点,而且符合人们区分事物先易后难的习惯.图4无监督聚方法生成的Clusland心脏柄变诊断决策树型Fig4Thestructureo£decisioatreeofclevelandheart决策树型

24、确定之后,采用监督学习支持向无机的方法来生成决策树中二叉节点对应的二分类器,采用的是径向基核函数和非对称的Lagrangian系数限制条件.调节径向基的宽度和系数限制条件，可以得到对应决策树上每个二叉节点的性能很好的二分类器.之后用5类共74个心脏病变样本的特征向量进行/测武测试结果列在表1之中.在表1中还给出J'几个其它研究人表1采用不同方法对Cleveland心脏病变数据的处理结果Table1ExpernientalresultsofClevelandheartdiseasedatausingdifferentclassifer方法准确率说明cc+svx93.2http： /mw.

25、 ph/s. uni. torun. pl/kmk/projects datasets, h七匚 1本文方法,如果只区分病变和非病变cc+svxS5.IS本文方法,区分所有类别INC-NET90.0、病变和非病变分类,文献13Na1veBaye582.8K±1.3%病变和非病变分类,文献Mk-XN,VDMS3.6S病变和非病变分类,文献15GOT5VMS3.5S树型边界分类病变和非病变.文献16员采用不同的研究方法对Cleveland心脏病变数据的分类结果,更多的有关该组数据的处理结果可以参阅文献11力或网站这些结果准确率均在85.遥之下，居多方法只区分样本特征向量是病变还是非病变,

26、是二分类的研究结果.从表1的数据比较可以看出，本文提出的决策树型确定和决策树节点的二分类器的生成方法一定程度的提高/分类效果.5结论综合利用多种学习策略来解决多分类问咫是一种比较好的指导思想，它可以提高解决问题的效率和结果.本文利用无监督聚类学习策略和监督学习支持向无机的方法来生成多分类决策树，在实胎中获得r比较好的效果.该方法不仅能够针对待处理的多分类问题多类之间的内在联系和分布特点，生成相应的决策树型，具有灵活解决问题的能力，而且采用r准确率高的支持向量机对不易区分的类别进行分类,弥补r无监督聚类分类准确率低的玦陷,实现r策略之间的优势互补.该方法在解决多分类问虺上体现门问题产生的剌激机制

27、和人们区分多种类别时先易后难的思维习惯,实现r比较高的计算效率和分类效果.References:1. VapmkV.Thenatureofstatisticallearningtheory.NewYork：Sprmser-Verlac,1995.2. VapmkV.StatisticallearningtheoryM.JohnWiley&Sons,XewYork,1993.3. HestonJandWatkins.Xulti-classsupportvectorzuichinesR：.TechnicalReportCSD-TR-9S_01,RoyalHolloway,Universit

28、yofLondon,Departmento£ComputerScience.EBIOL199s.Availableonhttp：/,clrc.diseasedataproducedbyunsupervisedclustering小型微型计算机系统5562004 年rhul.ac.ukresearcSVM.pub.zhtsl.4. MurthyS.K.»KasifS.andSalzbereS.,Asysteeforinductiono£obliquedecisiontreesJ.Journalo£ArtificialIntelligenceResearch

29、,1991,(2)：1-32.5. BroadleyC.E.andUtco££P.E.,XultivariatedecisiontreesJMachineLearning.1995,(19)：4577.6. PlattJ.C.CristianiniN.andShawe-TaylorJ.,Lar：eaarginDAGsforaultxclassclassificationJ.advancesinNeuralInformationProcessinsSystems,2000：517553.7. Chapelle0.,HaffnerP.andVapnikV.,Supportvec

30、toraachinesforhistogram-based:cageclassificationLJJ.IEEETrans.NeuralNetworks,1999,(10):1055-1061.5. AldenderferX.S.andBlashfieldP.K.,ClusteranalysisM.SagePublications.BeverlyHills,USA,19S4.9. CherkasskyV.andXullerF.,Learning£rosxData-Concept,Theoryandmethods翼.JohnWiley&Sons,XY»USA,199S

31、.10. BurgesC.Atutorialonsupportvectormachines£orpatternrecognitionJ.DataXimnsandKnowledseDiscover7>1998(2):121167.11. OsunaE.FreundR.andGiro二iF.,TrainineSupportVectorMachines：Anallicationto£acedetectionC.TheProceedingoflEEEConferenceonComputerVisionandPatternRecognition,Puert。，1997:1301

32、36.12. LiXiaoLi.LxuJiMxnandShiZhonZhi.AChineseWebpajeclassifierbasedonsupportvectorsachmeandunsupervisedclusterins.J.ChineseJournalo£Computers,2001,24(1)：62、6s13. JankowskiN.andKadirkamanathanV.,Statisticalcontrolo£growingandpruninginRBF-lxkeneuralnetworksC.InThirdCon£erenceonNeuralNetworksandTheirApplications*Kule,Poland,1997：663"-670.14