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

1、第25卷第4期小型微型计算机系统 Vol.25 No.4 2004年4月 MINI-MICRO SYSTEMS Apr.2004融合无监督和监督学习策略生成的多分类决策树邱德红，陈传波（华中科技大学 计算机科学与技术学院，湖北 武汉430074）摘 要：提出了一种融合无监督和监督两 种学习策略生成多分类决策树的方法 .它首先利用无监督聚类方法能够发现待分类样本之间的内在联系和规律的特点 ,确定出最为符合多类样本分布特征的决策树的树型 ,继而利用监督学习支持向量机的方法对样本进行准确的分类 .通过采用核函数和不对称的 L agrangian系数限制条件 ,支持向量机很好的解决了样本特征空间上的线

2、性不可分性和决策树型确定过程中出现的训练样本不对称性的影响 .该方法具有较高的计算效率和准确性 ,在实验中取得了比较好的结果.关 键 词：多分类决策树；无监督聚类；支持向量机中图分类号：TP391.41 文献辨识码：A 文章编号：1000-1200(2004)04-0555-05Construction of Multi-classification Decision Tree CombiningUnsupervised and Supervised Learning StrategyQIU De-hong,CHENChuan-bo(School of Comouter Science and

3、 Technology Huazhong University of Science and Technology,Wuhan 430074,china)Abstract:In this paper,a new method which combines unsupervised and supervised learning steategy is put forward to construct the multi-classification decision tree,It firstly uses the unsupervised clustering to determine th

4、e structure of the multi-classification decision tree,whose each node has a binary branch.The unsupervised clustering is able to find out the relationship between the mulit-classes,therefore the decision trees structure determined by it is the best one that fits to the distribution of mulit-classes

5、in feature space.Then,a supervised learning method,i.e.support vector machine,is used to classify the two groups of samples of each node of the decision tree.Most cases the multi-classes cannot be classified by a linear hyperplane,kernel functions are therefore introduced into to solve it.Simultaneo

6、usly,unsymmetrical constrains of Lagrangian coefficients are set to overcome the negative influences of unbalanced train samples. These efforts guarantee the efficiency and accuracy of the multi-classification decision tree.Satisfying results were obtained in experiment.Key words:multi-classificatio

7、n decision tree; unsupervised cluster support vector machine收稿日期：2002-08-05 作者简介：邱德红，博士，主要研究方向为机器学习和生物测定学；陈传波，教授博士生导师，主要研究方向为图像处理和计算机网络应用。E-mail:4期 邱德红 等：融合无监督和监督学习策略生成的多分类决策树 5571 引 言 多分类问题是一个比较常见的问题，机器学习理论和方法的研究在解决二分类问题上取得了比较满意的结果1,2.多分类问题虽然也有研究3,但在理论构架和现实方法上还有相当大的困难.目前解决多分类问题主要运用多分类决策数，决策树上的每一个节点

8、对应一个二分类器，实际上是利用二分类方法解决多分类问题.生成类分类决策树的方法有（1）一对其余，决策树上N个节点对应的二分类器只判断是某一类还是其余类；（2）一对一，决策树上N(N-1)/2个节点对应的二分类器只能对类中的两类作出是否判断；（3）一半对一半，即决策树的节点对应的二分类器将节点上的类二等分（允许一类别在两个节点上出现），直至叶节点.决策树上节点的数目为，其中为大于或等于log2(N)最小整数.这三类方法生成的决策树虽然具有不同的计算效率和分类效果，但各自在应用中取得了比较好的结果47.无监督学习和监督学习是机器学习方法研究的二大策略.无监督学习方法如无监督聚类(UC)8,9是从样

9、本的特征向量出发，研究通过某种算法特征比较相似的样本聚集在一起，从而达到区分具有不同特征的样本的目的.无监督聚类的优点是可以发现样本中隐含的共性和规律，但是由于没有专家知识的监督，分类的准确性有限.监督学习方法是通过对已知类别的训练样本的学习，实现对未知样本的分类判断.支持向量机(SVM)1,2是一种主要用于二分类的准确率比较高的监督学习方法，其基础是统计学习理论中的结构风险最小化原则.它在许多领域得到了很好的应用1012.本文提出一种将无监督聚类和监督学习的支持向量机方法结合起来生成多分类决策树的方法.它的基本思想如下：待方法的多类样本可以看成是某一宏观层面之上的刺激机制激励下，或者是在某个

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

11、定组训练样本：（x1,y1）,（xl1,yl1）,(x1,y2),(xl2,y2),(x1,yN),(xlN,yN),L=l1+l2+lN为N类训练样本的总数目，xiRd，i=1,L是d维空间上的特征向量，yn1,2,N,n=1,N是N类标号.多分类问题即函数F：Rd1,2,N确定待分类向量x的类别标号y.多分类问题可以通过由二分类器为节点构成的决策树来解决.由于待分类的N类样本通常是其形成的刺激机制在某个宏观层面之下的差异，或者是同一进程的不同阶段形成的，刺激机制差异的大小和进程阶段相隔时间的久远导致N类样本在特征空间上分布有一定的规律.如图1所示的N=6的多分类问题，左下三类(、)和右上三

12、类(、×、*)之间的刺激机制相差较远，而左下三类(、)之间、右上三类(、×、*)之间的刺激机制相差较小.如果多分类决策树型能够反映出类样本之间的分布规律，继而实施轻重有别的详细区分，必将能获得比较优秀的性能，为此设计以下利用无监督聚类确定决策树型的方法.图 1 多类样本的特征向量在特征空间上的分布Fig.1 Distribution of multi-classes samples on the feature space第1步:计算N类训练样本共L个特征向量中的任何两个特征向量,比如xr,xs之间的Minkowski距离dr,s=,r,s=1,m+1,且rs,p=2第2步

13、: 将N类训练样本共L个特征向量编号为1,L号叶节点,从1号叶节点开始在C个距离之中找到最小距离,将对应的两个叶节点(比如为xr,xs,)做个连接,形成一个二叉树枝.将此连接看成为一个新叶节点,编号为L+1.该新叶节点到其余某个叶节点xk,kr,s(即xr,xs,之外的节点)之间的距离定义为已经连接的两个叶节点(xr,xs)与该节点之间的最小距离,即dL+1,k=min(dr,k,ds,k) .第3步:按照第2步同样的规则,在新生成的叶节点和其余叶节点之中继续生成一个新的二叉连接,重复 直到生成最后一个二叉连接而成为一棵聚类树.如图2所示的一棵聚类树，它对应于图1中的60个样本.图2 无监督聚

14、类生成的聚类树Fig.2 Decision tree produced by unsupervised clustering第4步:将第3步中最后生成的一个二叉连接的左右两个分枝连接的最底层的叶节点(即1,L叶节点)对应的特征向量划分到的左右两个集合SR,SL中.依次检查待分类的1,N类样本的特征向量, 如果第n类的Ln个特征向量被聚类到左右两个集合SR、SL中,数目分别为lnR和lnL(lnR+lnL=ln)则依下情况处理:·如果lnR大于或等于lnL,且集合SL中特征向量的个数大于lnL,则将集合SL中对应的lnL个特征向量移至集合SR·如果lnR大于或等于lnL,但集

15、合SL中特征向量的个数等于lnL,则将集合SR中对应的lnR个特征向量移至集合SL·如果lnL大于lnR ,且集合SR中特征向量的个数大于lnR,则将集合SR中对应的lnR个特征向量移至集合SL·如果lnL大于lnR ,但集合SR中特征向量的个数等于lnR,则将集合SL中对应的lnL个特征向量移至集合SR至此可以确定决策树上的一个二叉节点,它的训练样本是非空的左右两个集合SR、SL,将集合SL中的特征向量的标签设定为-1,集合SR中的特征向量的标签设定为+1.它们将用于训练支持向量机来生成该节点对应的二分类器.第5步:分别将左右两个集合SR、SL中包含的特征向量看成一个新的

16、分类问题,重复第1步到第4步,直到左右两个集合SR、SL中均只包含N类训练样本中的某一类样本.从而确定出完整的N分类决策树的树型.图1所示的N=6的分类问题对应的决策树型如图3所示.无监督聚类方法确定决策树树型与一对其余,一对一和一半对一半确定决策树树型方法上是不一样.后三者对于所有N 的多分类问题采用的决策树型均是固定的,而这里介绍的方法将依据N 类样本之间的联系和分布规律生成相应的决策树型.决策树型本身在一定的程度上反映了N 类样本之间的差异大小,可以一定程度的降低二分类的难度.以此为基础的N 分类问题的计算效率将随决策树型有所变化.如果假设这些方法均采用同样的二分类方法,二分类器的计算复

17、杂度可大致描述为,其中为系数, n 为训练样本数,为复杂度指数.则对于N 类、样本总数为L的多分类×*×+*××图3无监督聚类生成的决策树型Fig.3The structure of decision tree producedbyunsupervised clustering问题,一对其余生成的决策树的计算复杂度为；一对一生成的决策树的计算复杂度为li和lj为对应两类的训练样本的数目;一半对一半生成的决策树的计算复杂度约为c ( 2k-1)()2 ,其中k为大于或等于log2(N)的最小整数,训练样本数l逐步递减.无监督聚类生成的决策树的节点数小于一半

18、对一半和一对一生成的决策树,其节点的训练样本数小于一对其余的生成方法,递减速度大于一半对一半的生成方法.综合来说,无监督聚类生成的决策树具有比较高的计算效率.3 支持向量机二分类器无监督聚类生成的决策树上的每个二叉节点对应于一个二分类器.无监督聚类分类的准确率有限，这里采用准确率高的支持向量机来生成决策树上每个二叉节点对应的二分类器，它的训练样本分别是该二叉节点连接的左右两个集合SR、SL中的样本，它们可以统一表示为：(xi,yi),xi,Rd,yi+1,-1,训练样本数为l.支持向量机是一种建立在统计学习理论基础上的机器学习方法他采用学习理论的结构风险最小原则【1,2】.其学习目的是在所有分

19、割超平面中http:/mlearn/MLR Repository,html确定最优超平面H:wx+b=0,该平面到两类之间的间隔最大,且满足一下约束条件： 两类之间的间隔为，因此, 确定最优分割超平面即为求( w ,b)使得最小，它等效求解二次优化问题，即求Lagrangian系数使目标函数W ()最大: （1）满足条件i0(i=1,2,l)和然后可求得（w,b）为；X+和x-分别是两类向量的支持向量，与它们对应的i0，其余的i=0,支持向量机学习确定的分类器为：无监督聚类确定的分类决策树的二叉节点对应的训练样本往往不具有线性的可分性.此时可以引入适当的核函数K(

20、xi,xj)=(xi)·(xj),将将原空间中的向量映射到另一特征内积空间中去进行分类.此时目标函数(1)相应修正为:（2）满足约束条件：引入核函数后新特征向量x的分类器法则如下：核函数K(xi ,xj)需要满足Mercer定理【2】,经常采用的核函数有多项式函数:K(x,y)=(x·y+1)d,高斯径向基函数和多层感知器函数：训练样本中如果存在不可分的样本(噪音),就需要适度对待训练误差.此时,如果过份地强调减小训练误差可以导致二分类器的性能恶化.因为这样生成的二分类器可能过于倾向训练样本的个性特征,而没有体现出训练样本整体共性,不利于对未知样本的判断.这时候需要采用柔性

21、边界,它依然可以通过求解最大目标函数(2)得到,然而需要将约束条件i>0改为0iC. C可以协调训练误差和分类器的综合能力,其物理的解释可以看成是与参数Ti对应的训练样本对分类边界的作用力大小的变化范围.无监督聚类生成的决策树型时经常会出现的左右两个集合SR、SL中的样本数目的不均衡,数目少的一边对分类边界确定的作用合力的大小往往有限,因而对分类边界的确定影响力弱.为此我们对数目不等的两类样本确定不对称的作用力变化范围,即使0Ti+ C+,0TiC-,C+和C-与训练样本数目相关,以此来消除训练样本数目不均衡性的影响.4 实验结果我们采用Cleveland心脏病变数据来检验上文介绍的融合

22、无监督聚类和监督学习支持向量机生成的多分类决策树的效果.Cleveland心脏病变数据在一个知名的有关机器学习研究的网站1 上公布,成为许多分类方法的检验数据.这组数据包含有303个样本,每个样本的特征向量的维数为13.其中有6个样本的特征向量不完整,这里将它们从样本中剔出,因而可使用的样本数据为297个.样本的特征向量被分为5类,其中心脏没有病变的正常情况的样本数目为160个,标号为0.其余的样本为心脏有病变的特征样本,标号依此为1、2、3和4,对应的样本数目分别为54、35、35和13,标号递增表示心脏病变的程度越发厉害.我们对于每一类样本,选择其中的四分之三为训练样本,数目共为223个,

23、其余的四分之一用来验证,数目共为74个.利用第二节介绍的无监督聚类方法,首先从224个训练样本确定决策树的树型,结果如图4所示.为了平衡样本特征向量各个特征值对决策树型的影响程度,对所有样本的特征向量的每项特征值进行了正规处理,即进行了以下运算:，表示所有样本特征向量的同一项特征值构成的列向量.从图4可见,无监督聚类方法确定的决策树型明确地反映出Cleveland心脏病变数据中几类样本之间的关系,如正常的样本向量(0)与病变样本向量首先被区分开来,严重病变的样本向量(3、4)将与轻度病变(1、2)的样本向量区分开来,最后区分比较难以区分的两类样本.无监督聚类方法生1http:/www.phys

24、.uni.torun.pl/kmk/projects/datasets.html 成的决策树型不仅很好的体现了心脏病变这一进程中不同阶段的特点,而且符合人们区分事物先易后难的习惯.0,1,2,3,41,2,3,43,4432011,2图4无监督聚方法生成的Cleveland心脏病变诊断决策树型Fig .4The structure of decisiontree of clev eland heartdisease data produced by unsupervised clustering决策树型确定之后,采用监督学习支持向量机的方法来生成决策树中二叉节点对应的二分类器,采用的是径向基核

25、函数和非对称的Lagrangian系数限制条件.调节径向基的宽度和系数限制条件,可以得到对应决策树上每个二叉节点的性能很好的二分类器.之后用5类共74个心脏病变样本的特征向量进行了测试,测试结果列在表1之中.在表1中还给出了几个其它研究人表1采用不同方法对Clev eland心脏病变数据的处理结果Table 1Expermental results of cleveland heartdisease datausing different classifer方法准确率说明UC+SVM93.2%本文方法，如果只区分病变和非病变UC+SVM85.1%本文方法，区分所有类别INC-NET90.0%病

26、变和非病变分类，文献13Naïve Bayes82.8%±1.3%病变和非病变分类，文献14k-NN,VDM82.6%病变和非病变分类，文献15GOT/SVM82.5%树型边界分类病变和非病变，文献16员采用不同的研究方法对Cleveland心脏病变数据的分类结果,更多的有关该组数据的处理结果可以参阅文献17或网站2.这些结果准确率均在85.1%之下,居多方法只区分样本特征向量是病变还是非病变,是二分类的研究结果.从表1的数据比较可以看出,本文提出的决策树型确定和决策树节点的二分类器的生成方法一定程度的提高了分类效果.5结论综合利用多种学习策略来解决多分类问题是一种比较好的

27、指导思想,它可以提高解决问题的效率和结果.本文利用无监督聚类学习策略和监督学习支持向量机的方法来生成多分类决策树,在实验中获得了比较好的效果.该方法不仅能够针对待处理的多分类问题多类之间的内在联系和分布特点,生成相应的决策树型,具有灵活解决问题的能力,而且采用了准确率高的支持向量机对不易区分的类别进行分类,弥补了无监督聚类分类准确率低的缺陷,实现了策略之间的优势互补.该方法在解决多分类问题上体现了问题产生的刺激机制和人们区分多种类别时先易后难的思维习惯,实现了比较高的计算效率和分类效果.References:1. Vapnik V. The nature of statistical lear

28、ning theoryM.NewYork: Springer-Verlag,1995.2. Vapnik V. Statistical learning theoryM. John Wiley &Sons,New York ,1998.3. Weston J and Watkins . M ulti-class support vector machines R .Technical Report CSD-T R-98-04, Royal Holloway, University of London, Department of Computer Science,EBIOL 1998.

29、 Available on http:/www. clrc. rhul.ac.uk/research/SVM/pub.shtml.4. Murthy S.K. ,Kasif S. and Salzberg S. , A system for inductionof oblique decision treesJ.Journal of Artificial Intelligence Research, 1994, (2): 132.5. BroadleyC.E.andUtgoff P. E. , Multivariate decision treesJ Machine Learning, 199

30、5,(19):4577.6. Platt J.C. ,Cristianini N. and Shawe-Taylor J. ,Large marginDAGs for multiclass classification J . advances in Neural Information Processing Systems, 2000: 547553.7. Chapelle O., Haffner P. and Vapnik V., Support vector machinesfor histogram-based image classification J . IEE E Trans.

31、 Neural Networks, 1999, (10):10551064.8. Aldenderfer M.S. and BlashfieldP.K. , Cluster analysis M.Sage Publications, Beverly Hills,USA,1984.9. Cherkassk y V. and MullerF. , Learning f romDat a- Concept,Theory and m ethods M . John Wil ey&Sons , NY, U SA, 1998.10. Bu rgesC. , A tut ori al on supp

32、ortvecto r machines f or pat t ernrecognition J . Data Mining and Know ledge Di scovery, 1998( 2): 121 167.11. OsunaE. , Freund R. and Girosi F. , Training Support V ectorMachines: An allication to f ace detect ion C . The Proceeding ofIEEEConference on Com put er Vision and Pat tern Recognition,Puert o, 1997: 130 136.12. Li XiaoLi, Liu JiMin and Shi ZhongZhi. A chinese Web page classifier b