基于SVM决策树判别测试点类别的新方法

维普资讯 http://www.cqvip.com 第２７卷第１期　２００７年１月　文章编号：１００１—９０８１（２００７）０１—００８４—０２　计算机应用　Ｃｏｍｐｕｔｅｒ　Ａｐｐｌｉｃａｔｉｏｎｓ　Ｖ０１．２７　Ｎｏ．１　Ｊａｎ．２００７　基于ＳＶＭ决策树判别测试点类别的新方法　薛欣　，贺国平　（１．山东科技大学信息科学与工程学院，山东青岛２６６５１０；　２．泰山学院数学与系统科学系，山东泰安２７１０２１）　（ｘｕｅｘｉｎ０４＠１６３．ｃｏｍ）　摘要：从测试点的类别判断方式上进行改进，对容易错分的测试点给予多次判别机会，从而降　低了ＳＶＭ决策树的错分累积程度。仿真试验表明，改进的基于ＳＶＭ决策树判别测试点类别方法与　传统的基于ＳＶＭ决策树判别测试点类别方法相比，具有较高的分类精度。　关键词：间隔；决策树；支持向量机　中图分类号：ＴＰ１８１　文献标识码：Ａ　Ｎｅｗ　ｍｅｔｈｏｄ　ｆｏｒ　ｄｅｃｉｄｉｎｇ　ｔｈｅ　ｓｏｒｔ　ｏｆ　ｔｈｅ　ｔｅｓｔ　ｓａｍｐｌｅ　ｂａｓｅｄ　ｏｎ　ＳＶＭ　ｄｅｃｉｓｉｏｎ　ｔｒｅｅ　ＸＵＥ　Ｘｉｎ　一，ＨＥ　Ｇｕｏ—ｐｉｎｇ　ｆ１．Ｃｏｌｌｅｇｅ　ｏｆＩｎｆｏｒｍａｔｉｏｎ＆　删ａｎｄ　Ｅｎｇｉｎｅｅｒｉｎｇ，　Ｓｈａｎｄｏｎｇ　Ｕｎｉｖｅｒｓｈｙ　ｏｆＳｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｑｉｎｇｄｎｏ　Ｓｈａｎｄｏｎｇ　２６６５１０，Ｃｈｉｎａ；　２．Ｄｅｐａｒｔｍｅｎｔ　ｏｆＭａｔｈｅｍａｔｉｃｓ＆Ｓｙｓｔｅｍ　Ｓｃｉｅｎｃｅ，Ｔａｉｓｈａｎ　Ｕｍ￣ｙ，　ｎ　Ｓｈａｎｄｏｎｇ　２７１０２１。Ｃｈｉａ）ｎ　　．Ａｂｓｔｒａｃｔ：Ｂｙ　ｇｉｖｉｎｇ　ｔｈｅ　ｔｅｓｔ　ｓａｍｐｌｅ　ｍａｎｙ　ｄｅｃｉｓｉｏｎ　ｃｈａｎｃｅｓ，ａ　ｎｅｗ　ｍｅｔｈｏｄ　ｆｏｒ　ｄｅｃｉｄｉｎｇ　ｔｈｅ　ｓｏｒｔ　ｏｆ　ｔｈｅ　ｔｅｓｔ　ｓａｍｐｌｅ　ｂａｓｅｄ　ｏｎ　Ｓｕｐｐｏｒｔ　Ｖｅｃｔｏｒ　Ｍａｃｈｉｎｅ（ＳＶＭ）ｄｅｃｉｓｉｏｎ仃ｅｅ　ｗ鹊ｇｉｖｅｎ．Ｔｈｅ　ｎｅｗ　ｄｅｃｉｓｉｏｎ　ｍｅｔｈｏｄ　ｒｅｄｕｃｅｓ　ｔｈｅ　ｄｅｇｒｅｅ　ｏｆ　ｅｒｒｏｒ　ａｃｃｕｍｕｌａｔｉｏｎ．Ｅｘｐｅｒｉｍｅｎｔａｌ　ｒｅｓｕｌｔｓ　ｓｈｏｗｔｈａｔｔｈｅｎｅｗｄｅｃｉｓｉｏｎｍｅｔｈｏｄｂａｓｅｄ　ｏｎＳＶＭ　ｄｅｃｉｓｉｏｎｔｒｅｅｙ￣ｄｄｓｈｉｇｈｅｒｐｒｅｃｉｓｉｏｎｔｈａｎ　ｈｅ　ｔｔｒａｄｉｔｉｏｎａｌ　ｍｅｔｈｏｄ．　Ｋｅｙ　ｗｏｒｄｓ：ｍａｒｇｉｎ；ｄｅｃｉｓｉｏｎ　ｔｒｅｅ；ＳＶＭ（Ｓｕｐｐｏｒｔ　Ｖｅｃｔｏｒ　Ｍａｃｈｉｎｅ）　现有的支持向量机（ＳＶＭ）多类分类方法，从构造上可以　分为两类：①直接方法，对所有的样本使用同一个二次规划，　使测试点离正确类别越来越远，这种现象被为错分累积。如　在构造决策函数时同时考虑所有的类别，只需一次就可以决　定分类；②组合方法，通过组合多个二类分类支持向量机来构　造多类分类器，其中有：一对多…、一对一【２】、纠错编码【３】、有　向无环图支持向量机　】、ＳＶＭ决策树　】。对于类别数目较多　的分类问题，ＳＶＭ决策树是提高识别效率的有效方法。　图２所示，一个属于类别Ｃ２的测试点在ＳＶＭｏ处发生错分，这　个错分被ＳＶＭ，积累并传递给ＳＶＭ３，使原本属于类别Ｃ　的测　试点最终被错误分类。ＳＶＭ决策树的错分累积是影响其分类　精度的重要因素，当各决策节点的两个子类交叠较为严重时，　分类器的分类精度不高。　为构造分类性能良好的ＳＶＭ决策树，可以考虑将不易产　生错分的类先分离出来，然后再分不容易分的类，这样就能够　使可能出现的错分尽可能地远离树根，目前常用的树结构设　计方法有：①根据具体问题的特定知识和分类目标来设计树　ｌ　ＳＶＭ决策树　ＳＶＭ决策树的基本思想　】：采用某种方法将所有类别分　成两个子类，再将子类进一步分成两个次级子类，如此循环下　去，直到得到一个单独的类别为止，这样就得到一棵倒立的二　叉树，二叉树每个决策节点的二类分类问题用ＳＶＭ解决，如　图１，２所示，这是一个五类分类问题，其中用１，２，３，４，５表示　Ｃ。，Ｃ２，Ｃ，，Ｃ。，Ｃ，五类样本。ＳＶＭ决策树方法对于ｃ类分类问　结构　；②基于类间距离设计树结构　；③采用自然聚类设　计树结构等　Ｊ。研究者们在结构设计方面都做了一些改进，　并取得了良好的分类效果，但是树结构的错分累积问题一直　没有得到解决。　本文基于支持向量机的基本原理，提出了一种基于ＳＶＭ　题，只需构造Ｃ一１个分类决策函数，具有较高的分类效率；也　决策树判别测试点类别的新方法，这种方法可以降低错分累　积程度，提高ＳＶＭ决策树的分类精度。　不存在拒分区域。　２支持向量机的基本原理——最大间隔法　用图３所示的二维空间上的两类分类问题来说明支持向　量机的基本思想　Ｊ，图３，４中的空心点和实心点分别代表两　类数据，直线ｚ。就是一条以　为法向量且能够正确划分两类　点的直线，分别平行地向右上方和左下方推移直线ｚ。，直到碰　到某类训练点，这样就得到了两条极端的直线ｆ　和　，分别称　图Ｉ　ＳＶＭ决策树的树结构示意图　图２　ＳＶＭ决策树示意图　ｆ２和　为隔离线，ｆ２和　之间的区域为隔离带，ｚ　和　之间的　一’　但是，ＳＶＭ决策树在判别测试点的类别时，测试点一旦　被上层分类器错误分类，这种错误会被下层分类器传递下去，　距离　ｌ　１为与法向量　相对应的间隔亡Ｉ１　。支持向量　收稿日期：２００６—０７—１３；￣ＷＩ３５１：２００６—１０—１９　基金项目：国家自然科学基金资助项目（１０５７１１０９）　作者简介：薛欣（１９７０一），女，山东新泰人，博士研究生，主要研究方向：数据挖掘、支持向量机；贺国平（１９５９一）男，江苏常州人，教　授，博士生导师，博士，主要研究方向：非线性最优化、数据挖掘．　，维普资讯 http://www.cqvip.com 第１期　薛欣等：基于ＳＶＭ决策树判别测试点类别的新方法　８５　机选取使间隔达到最大的那个法向量ｔｃ，‘作为最优分类面的　图３　最大间隔法示意图　图４　近似线性可分示意图　法向量，对第ｉ个训练点（　，Ｙ１）引进松弛变量￡≥０，以　及惩罚参数ｃ，ｔｃ，’通过求解下列最优化问题获得：　１　‘，　１　＋ｃ　￡　…　１【　ｓＩｔ．　（（Ｗ・　‘）＋ｂ）＋　≥１，ｉ＝１，…，ｌ　￡≥０，ｉ：１，…，ｚ　当两类数据线性不可分时，使用非线性映射　，将样本点　从输入空间映射到特征空间，引入核函数Ｋ（　，　）＝西（　）・　咖（　），求解下列最优化问题：　ｌ　）一∑　』＝Ｉ　（２）　得到ａ‘，从而得到判别函数　ｘ）：∑Ｙ　Ｑｉ＊Ｋ（　，　）＋ｂ’，　即得到特征空间的一个分类超平面ｚ。：　１　ｙｔａ￣＂Ｋ（ｘｔ，　）＋ｂ’＝０　ｆｌ是使分类间隔达到最大的超平面。　设ＳＶＭ决策树的第ｉ个树节点包含判别函数　（　），当测　试点　代人这个判别函数时，若　（　）≥０，则判断　属于正　类；若ｆａｘ。）＜０，则判断‰属于负类。当类间交叠情况较为　严重时，这种判别方法造成大量的错分，ＳＶＭ决策树的错分　主要发生在决策边界相互混杂的样本中。下面从支持向量机　的基本原理出发，给出一种新的判别测试点类别的新方法。　３　基于ＳＶＭ决策树判别测试点类别的新方法　假设在ＳＶＭ决策树的第ｉ个树节点得到最优分类超平面　ｆ１Ｉ的同时，也得到了两个与其平行的隔离超平面　：　∑ｙ＃ｃｔ＃‘　（　，　）＋ｂｊ‘＝一１　Ｊ　Ｉ　和ｆｄ：　Ｉｔ　∑ｙ＃ｃｔ＃‘Ｋ（ｘ∥）＋ｂ　‘＝１　和ｆｄ把整个训练集分成三部分，第一部分位于　的下　方，第二部分位于ｆｄ的上方，第三部分位于　和ｆｄ形成的隔　离带里。测试点　也可以相应的分成三种情况：　第一种情况：测试点　位于　的下方。满足　Ｉｔ　（　）＝∑ｙｑａ＃‘Ｋ（　，　）＋ｂｔ＊≤一１　第二种情况：测试点　位于ｆｄ的上方，满足　Ｉｔ　（　）＝∑ｙ＃ｃｔ＃ｔＫ（ｘ　，　）＋ｂ．‘≥１　第三种情况：测试点　位于　和ｆＬ１形成的隔离带里，满　足　一１＜Ｚ（ｘ。）＝∑Ｙ＝Ｉ　　ａ　Ｋ（ｘ　。　）＋ｂｔ＊＜１　属于第一、二种情况的测试点比较容易正确地判断测试　点的类别，ｎ　：；对属于第三种情形的测试点，　首先引入隶属度　、　（　），０≤　（　）＜１　“　Ｌ１＋　（　０），　一１＜　（＂ｇＯ）＜０　∑　Ⅳ　：　≤　ｒ１－ｆ，（　），０≤　（　０）＜１　口　Ａｎ—ＩＩ０　　Ｃ　．　（ｇ．Ｏ）Ｉ，　一１＜　（ｇ．Ｏ）＜０　当测试点　代入第ｉ个ＳＶＭ决策树节点时，＝　若，＝（ｇ．Ｏ）≥１，　则判断　属于正类，进入其左侧节点继续判断；若　（‰）≤一　１，则判断　属于负类，进入其右侧节点继续判断；否则，判断　。以隶属度Ａ　属于正类，以隶属度Ａ　属于负类，这时需要分　别进入左侧和右侧节点继续判断。　最后的结果有两个：①准确地判断出测试点‰所属的类　别；②测试点ｚ。分别以不同的隶属度属于多个类别，其中第ｊ　个叶节点对应着一个隶属度序列｛Ａ　，Ａ　，…，Ａ　｝，选取具有　最高隶属度序列对应的类别为测试点　所属的类别，即若判　断　Ｅ　ｃ。，ｃ。为第　个叶节点对应的类别，则有Ａ　≥Ａ　，　Ａ＾２≥Ａ　，…，Ａｂ≥Ａ　ｄ＝１，２，…，ｃ。　４　仿真实验　用Ｖｅｈｉｃｌｅ标准数据集进行仿真试验，其中包含８４６个样　本，４个类别。每次实验，随机选取每类样本的２／３作为训练　集，全部样本作为测试集，训练每个ＳＶＭ决策树在相同的条　件下进行。用文献４给出的基于类间距离设计ＳＶＭ决策树　的树结构，使用基于ＳＶＭ决策树判别测试点类别的传统方法　得到的分类正确率为８５．７６０％，使用本文给出的新方法得到　的分类正确率为８８．４３５％，　５　结语　对于类别数目较多的分类问题，ＳＶＭ决策树是提高识别　效率的有效方法，但是ＳＶＭ决策树存在错分累积问题。影响　了其分类精度。本文从测试点的类别判断方式上进行改进，　对容易错分的点给予多次判断机会，从而降低了决策树的错　分累积程度。仿真试验表明，改进的基于ＳＶＭ决策树判别测　试点类别的方法与传统的基于ＳＶＭ决策树判别测试点类别　方法相比，具有较高的分类精度。但是有的测试点可能要访　问所有的节点，这样就降低了测试速度，如何对其改进是本文　下一步的研究方向。　参考文献：　【１】ＶＡＰＮＩＫ　Ｖ．Ｔｈｅ　ｎａｔｕｒｅ　ｏｆ　ｓｔａｔｉｓｔｉｃａｌ　ｌｅａｒｎｉｎｇ　ｔｈｅｏｒｙ【Ｍ】．Ｎｅｗ　Ｙｏｒｌ【：Ｓｐｒｉｎｇｅｒ，１９９５．　【２１　ＫＲＥＢＥＬ　Ｕ．Ｐａｉｒｗｉｓ￣ｃｌａｓｓｉｉｆｃａｔｉｏｎ　ａｎｄ　ｓｕｐｐｏｒｔ　ｖｅｃｔｏｒ　ｍａｃｈｉｎｅｓ　【Ｍ】．ＭＡ：ＭＩＴＰｒｅｓｓ。１９９９．２５５—２６８．　【３】ＤＩＥＴＹＥＲＩＣＨ　ＴＧ，ＢＡＫＩＰｄ　Ｇ．Ｓｏｌｖｉｎｇ　ｍｕｌｔｉ・ｃｌａｓｓ　ｌｅａｒｎｉｎｇ　ｐｒｏｂｌｅｍ　ｉｖａ　ｅｒｒｏｒ－ｃｏｒｔ￣ｔｉｎｇ　ｏｕｔｐｕｔ　ｃｏｄｅｓ【Ｊ１．Ｊｏｕｒｎａｌ　ｏｆ　Ａｒｔｉｉｆｃｉａｌ　Ｉｎｔｅｌｌｉｇｅｎｔ　Ｒｅｓｅａｒｃｈ。１９９５，（２）：２６３—２８６．　【４】ＰＬＡＴｒ　ＪＣ。ＣＰｄＳＴＩＡＮＩＮＩ　Ｎ。ＴＡＹＬＯＲ　ＪＳ．Ｉ哪ｅ　ｎｌａｇｇｉｎ　ＤＧＡｓ　ｆｏｒ　ｍｕｌｉｔ・ｃｌａｓｓ　ｃｌａｓｓｉｉｆｃａｔｉｏｎ【Ａ１．Ａｄｖａｎｃｅｓ　ｉｎ　ｎｅｕｒａｌ　ｉｎｆｏｒｍａｔｉｏｎ　Ｐｒｏ．　ｃｅｓｓｉｎｇ　Ｓｙｓｔｅｍｓ　１２【Ｃ】．ＭＡ：ＭＩＴ　Ｐｒｅｓ８，２０００．５４７－５５３．　【５】ＴＡＫＡＨＡＳＨＩ　Ｓ，ＡＢＥ　Ｓ．Ｄｅｃｉｓｉｏｎ－Ｔｒｅｅ．Ｂａｓｅｄ　Ｍｕｌｉｔ．Ｃｌａｓｓ　Ｓｕｐｐｏｒｔ　Ｖｅｃｔｏｒ　Ｍａｃｈｉｎｅｓ【Ａ】．Ｐｒｏｃｅｅｄｉｎｇ　ｏｆ　ｔｈｅ　Ｎｉｎｔｈ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒ－　ｅｎｃｅ　ｏｎ　Ｎｅｕｒａｌ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｐｒｏｃｅｓｓｉｎｇ［Ｃ】．Ｓｉｎｇａｐｏｒｅ：ＩＥＥＥ　Ｐｒｅｓ３，　２００２．１４ｌ８—１４２２．　【６】　ＢＥＮＮＥＴｒ　Ｋ，ＣＲＩＳＴＩＡＮＩＮＩ　Ｎ，ＷＵ　Ｄ．Ｅｎｌａｒｇｉｎｇ　ｔｈｅ　ｍａ　ｎ３　ｉｎ　ｐｅｒｃｅｐｔｉｏｎ　ｄｅｃｉｓｉｏｎ　ｔｒｅｅ【Ｊ】．Ｍａｃｈｉｎｅ　Ｌｅａｒｎｉｎｇ，２０００，４１（３）：２９５　—３ｌ３．　Ｉ　７】　ＡＺＩＭＩ　ＳＭ，ＺＣＫＡＶＡＴ　Ｓ．Ｃｌｏｕｄ　ｃｌａｓｓｉｆｉｃａｔｉｏｎ　ｕｓｉｎｇ　ｓｕｐｐｏｒｔ　ｖｅｃｔｏｒ　ｍａｃｈｉｎｅｓ【Ａ】．Ｐｒｏｃｅｅｄｉｎｇ　ｏｆ　ｔｈｅ　ＩＥＥＥ　Ｇｅｏｓｃｉｅｎｃｅ　ａｎｄ　Ｒｅｍｏｔｅ　Ｓｅｎｓｉｎｇ　Ｓｙｍｐｏｓｉｕｍ【Ｃ】．２０００．６６９—６７１．　Ｉ　８】　邓乃扬。田英杰．数据挖掘中的新方法——支持向量机【Ｍ】．北　京：科学出版社，２００４．