基于支持向量机的若干分类问题研究

《基于支持向量机的若干分类问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

摘要分类问题是实际应用中普遍存在的问题，也是机器学习领域的基础研究之一，快速发展的信息技术对其在理论研究和实际应用中提出了许多新的难题和挑战。支持向量机(SupportVectorMachine，SVM)是基于统计学习理论，借助最优化方法来解决机器学习问题的有力工具，目前，已表现出很多优于已有方法的性能。本文以深入探讨分类问题为研究目标，立足于对支持向量分类机的理论模型和在实际中的应用进行完善、推广和创新。论文的主要内容包括以下几个方面：1．对本文采用的基础理论进行了介绍。主要包括机器学习的主要问题，统计学习理论的基本内容，以及支持向量机的基本思想和研究现状。2．从特征空间的几何结构入手，对核函数所蕴含的黎曼度量、距离度量和角度度量进行详细分析，在此基础上深入探讨高斯径向基核函数的几何性质，并分析了映射、核与度量之间的关系，说明支持向量机算法的解本质上依赖于度量。3．提出一种新的解决类不平衡与代价敏感分类问题的方法。支持向量机通过核函数，将数据嵌入到高维特征空间的一个低维流形表面，利用微分几何中流形表面诱导的黎曼度量，在半径间隔界的控制下，通过保角映射，放大类不平衡问题中少样本类与分界面之间的间隔，从而在保证多数类准确率较高的前提下，达到提高少数类的分类准确率，有效的减少了支持向量机在类不平衡问题中的有偏性。4．对1．v．r方法中子分类器采用不同核参数时，各决策输出值的可比性进行了深入分析，说明此时将各子分类问题映射到不同的特征空间，其决策输出值仍具有可比性，且能提高总体分类的性能。5．对分解多分类方法中存在的不可分现象进行了研究，针对一些实际应用问题，提出一种基于决策间隔的模糊输出支持向量机算法，该方法可以更为有效地解决不可分问题。 6．从VC维的角度比较了有序与无序分类问题的复杂度，说明线性分类器的VC维与其分级维相同；结合支持向量机技术提出一种改进的内嵌空间算法，并在实际有序分类问题——企业信用风险评估问题中验证了该方法的有效性。最后，对本文的工作进行了总结，并对今后的研究工作提出了展望。关键词：分类问题；统计学习理论；支持向量机 AbstractClassificationproblemisacommonprobleminpracticalapplications，aswellasabasicresearchtopicinmachine-learningdomain．Itfacesmanynewpuzzlesandchallengesbothintheoreticalresearchandinpracticalapplicationsontherapidlydevelopinginformationtechnique．SupportVectorMachine(SVM)isanewlydevelopedmachinelearningmethodbasedonthefoundationoftheStatisticalLearningTheory(SLT)andtheoptimizationtheory．Now,SVMhasalreadyshownexcellentlearningperformanceinmanyfields．Thisthesisfocuses011theclassificationproblem，particularlyconcernsoftheresearchesonthetheoreticalmodelaswellasthepracticalapplicationsofSVM．Themainworksofthisthesisarcasthefollowing：1．Thebasictheoriesusedinthisthesiswereintroduced，includingthemainproblemsandmethodsinMachineLearning，StatisticalLearningTheoryandSupportVectorMachines；then，someoftherecentresearchesonSVMwerealsoreviewed．2．Fromtheviewpointofgeometricstructureofthefeaturespace，somemetrics(Riemannianmetric，distancemetric，andanglemetric)inducedbythekernelfunctionarcanalyzed；thegeometriccharacterofGaussianRadiusBasiskernelisdiscussedindetail；therelationsamongthemapping，thekernelandthemetricarealsoanalyzed．3．Anewmethodtosolvetheimbalancedor／andcost．sensitiveclassificationproblemisproposed．UndertheRiemannianmetricinducedintheembeddedmanifold，asuitableconformalmappingofkernelisappliedtoenlargethespatialresolutionaroundthesupportvectorsofthelesspattemclass，suchthattheseparabilityforthesamplesofthelessclassiswellimproved．4．Thecomparabilityofthedecisionfunctionsgivenbythesub-classifierswithdifferentkernel—parametersin1-V-rmethodisdiscussed，andthepositive resultisobtained．5．Theexistanceoftheinvalidregionsinthemulti—classclassificationproblemsisanalyzed，andafuzzy-outputSVMisproposedtoresolvethepatternswithinsuchregionsforsomepracticalproblems．6．ThecomplicaciesoftherankingproblemandthegeneralclassificationproblemarecomparedfromtheviewpointofVCdimension，anewconcept“rankingdimension'’isproposed．Thetraditionalembeddedspacemethod，whichCandirectlytransformanordinalrankingproblemintoabinaryclassificationproblem，ismodifiedtoadaptthenonlinear-separableproblembasedonSVMscheme，andtheperformanceofthenewmethodisvalidatedbyit’Sapplicationinenterprisecreditriskassessmentproblem．Keywords：classificationproblem，StatisticalLearningTheory,SupportVectorMachine 厦门大学学位论文原创性声明兹呈交的学位论文，是本人在导师指导下独立完成的研究成果。本人在论文写作中参考的其他个人或集体的研究成果，均在文中以明确方式标明。本人依法享有和承担由此论文产生的权利和责任。声明人(签名)：阔绢l虱纠年lf月尹El 厦门大学学位论文著作权使用声明本人完全了解厦门大学有关保留、使用学位论文的规定。厦门大学有权保留并向国家主管部门或其指定机构送交论文的纸质版和电子版，有权将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆被查阅，有权将学位论文的内容编入有关数据库进行检索，有权将学位论文的标题和摘要汇编出版。保密的学位论文在解密后适用本规定。本学位论文属于1．保密()，在年解密后适用本授权书。2．不保密(√f(请在以上相应括号内打“4")J1月扣日11月伽 第一章绪论1．1研究背景第一章绪论从数据中发现知识是分析复杂数据、建立决策系统的基石。随着信息技术和信息网络的飞速发展，信息产生和传播的速度迅速提高，政府、商业、企业等各行各业出现了越来越多的复杂非线性高维数据需要分析、处理。如何有效的利用数据，如何从大量的数据中寻找规律，并用这些规律对未来数据进行预测，成为一个十分迫切的富有挑战性的研究课题。机器学习领域的模式分类和回归分析等方法是知识发现中的重要内容，也是处理许多其它问题的核心。许多优秀的学习算法(如神经网络、支持向量机等)都是以分类为基础发展起来的。分类的作用和根本目的在于面对某一未知类别的具体事物时，能按照已知的信息将其正确的归于某一类。将某一事物正确归入某一类的方法即分类方法，研究分类方法首先要确定分类标准，而对任何事物都不存在纯客观的分类标准，任何分类都带有主观性，因此，对不同的分类标准会产生不同的分类方法。目前，机器学习方法共同的重要理论基础之一是统计学，在此基础上已有各种各样的分类方法，如：人工神经网络、贝叶斯决策、l【．近邻、决策树等等。这些传统的统计学方法将经验风险最小化(ERM)原则作为出发点，在样本数趋于无穷大的假设下进行学习，在实际问题中，样本数目往往是有限的，这些理论上非常优秀的方法在一些实际应用中的表现却可能不尽人意，传统的统计学方法面临了严峻挑战。Vapnik等人提出的统计学习理论(StatisticalLearningTheory，SLT)【l】【21是一种针对小样本情况研究统计学习规律的理论，该理论的核心思想是通过引入结构风险最小化准则(s瑚)来控制学习机器的容量，从而刻画了过度拟合与泛化能力之间的关系。在这一理论基础上产生的支持向量机(SupportVectorMachines，SVM)学习方法近年来受到广泛重视，该方法不但引入了结构风险的概念，还采用了核映射的思想，与传统方法相比，支持向量机具有的优势体现在：即克服了传统方法的大样本要求，又有效地克服了维数灾难及局部极小问 基于支持向量机的若干分类问题研究题，并在处理非线性问题时显示了其卓越的优越性。随着支持向量机技术的不断发展和推广，目前，国内外关于SVM的研究正方兴未艾，其理论研究正在不断深入发展和完善，实践应用不断拓广，已成为机器学习和数据挖掘领域的标准工具。虽然分类问题不是新的问题，现有的各种技术也在一些分类问题中表现出较好的性能，但计算机的普及应用，特别是机器学习和数据挖掘的迅速发展赋予了它新的意义，目前再次引起了人们热切的关注。如：海量高维数据的分类，无标签数据的使用，多类别数据的分类，类不平衡和代价敏感数据的分类，有序分类等等。本文正是在支持向量机这一新兴的理论背景和实际分类问题这一应用背景下，以支持向量机方法为基础，探讨了其关键技术——核函数的几何性质及若干分类问题的理论基础，并提出一些新的解决各种实际分类问题的方法，该课题的研究将扩展支持向量机的应用空间和丰富分类问题的解决途径。1．2分类问题的研究现状和研究要点1．2．1问题描述目前，基于数据的学习，逐渐引起各行各业的广泛重视，许多学者提出了“信息有效利用”的问题。“信息有效利用"的本质是，如何根据用户的特定需求从海量数据中建立模型或发现有用的知识。对计算机科学来说，这就是机器学习。自20世纪50年代，人们从仿生学的角度出发研究学习问题至今，机器学习已成为促进计算金融学、生物信息学、工业过程控制、信息安全、机器人、遥感信息处理、行星地质学等众多学科发展的重要基础之一。美国航空航天局JPL实验室的科学家Mjolsness等人在Science上撰文指出【31：“每个科学领域的科学过程都有它自己的特点，但是，观察、创立假设、根据决定性实验或观察的检验、可理解检验的模型或理论，是各学科所共有的。对这个抽象的科学过程的每一个环节，机器学习都有相应的发展，我们相信它将导致科学方法中从假设生成、模型构造到决定性实验这些所有环节的合适的、部分的自动化。当前的机器学习研究在一些基本论题上正取得令人印象深刻的进展，我们预期2 第一章绪论机器学习研究在今后若干年中将有稳定的进展"。这个提法指出，在科学研究的整个过程(观察、假设、实验、检验、模型或理论)中机器学习都扮演着重要的角色。Simon对学习的论述是：“如果一个系统能够通过执行某个过程改进它的性能，这就是学[41”。这是一个相当广泛的说明，其要点是“系统’’，它涵盖了计算系统、控制系统以及人系统等，对这些不同系统的学习，显然属于不同的科学领域。即使计算系统，由于目标不同，也分为了“从有限观察概括特定问题世界模型的机器学习"、“发现观测数据中暗含的各种关系的数据分析’’，以及“从观测数据挖掘有用知识的数据挖掘"等不同分支。由于这些分支发展的各种方法的共同目标都是“从大量无序的信息到简洁有序的知识"，因此，它们都可以理解为Simon意义下的“过程”，也就都是“学习’’。本文将讨论内容限制在一个狭义的学习问题上，即，“从有限观察发现观测数据中暗含的各种关系的数据分析”的方法上。具体说就是从实际问题的一个有限的子集(样本集)出发，探求问题的内在规律(建立模型)，从而对未知数据做出正确判断(分类)。这就是机器学习领域的分类问题(classification)，也称为模式识别问题，在概率统计中则称为判别分析问题，在本文中我们采用“分类问题"这一术语。用数学语言可以把分类问题简单描述如下：分类问题：根据给定的训练集S={(而，乃)，(吃，y2)⋯(西，M))∈(Xx聊7，其中毛∈X=Rn,以∈Y={1,-1}，f=l，．．．，J『，寻找X=R”上的一个实值函数g(x)，以便用决策函数厂(x)=s印(g(x))(1—1)推断任一模式x相对应的Y值。上述分类问题是分成两类的问题，与此类似还有分成多类的分类问题，它们的不同之处仅在于前者的输出只取两个值，而后者可以取多个值。我们把解决上述分类问题的方法称为分类学习机。3 基于支持向量机的若干分类问题研究1．2．2分类问题的研究现状现实生活中存在大量的分类问题，如：机械故障诊断、医学诊断、语音识别、人脸识别、信用评估、文本分类、网络入侵检测、图像识别等。目前，用于分类的方法很多，传统的方法有Bayesian方法、距离判别、Fisher判别、k-近邻分类以及分段线性分类等【51，现代的方法如模糊分类[61、粗糙分类‘71、神经网络和支持向量机分类等。其中具有代表性的方法是：Bayesian方法、神经网络和支持向量机方法。这些方法已在医学诊断、语音识别、文本识别、人脸识别等领域得到了广泛的应用。贝叶斯学习理论利用概率的形式来表示变量间的依赖关系，通过先验信息和样本数据来获得对未知样本的估计。先验概率既可以借助人的经验、专家的知识来指定，也可以通过分析样本数据的特点直接获得。后者要求有足够多的数据才能真正体现数据的真实分布。贝叶斯方法的优点是可以利用人的先验知识，而缺点是当假设模型与样本实际分布情况不相符时，就难以获得较好的效果。著名的kolmogorov连续性定理从数学上证明了神经网络可以以任意精度逼近任意非线性函数【8】，这为神经网络解决非线性问题提供了重要保证，也是神经网络在许多领域得到广泛应用的重要基础。目前常用的神经网络模型有BP网络、RBF(RadialBasisFunction)网络、Hopfield网络、自组织映射(Self-OrganisingMap，SOM)神经网络等，这些网络在分类研究中都有广泛的应用【9】【101。另外，神经网络同模糊理论以及遗传算法等软计算方法相结合产生了模糊神经网络、遗传神经网络等许多研究成果【ll】【121。虽然神经网络在很多领域得到了成功的应用，但其得到的理论成果并没有对一般的学习理论带来多大贡献，也就是说神经网络还缺乏严密理论体系的指导，且易出现过学习和局部极小等问题，其应用效果往往过分依赖于使用者的经验。支持向量机技术是目前泛化能力较强的学习方法之一，因其坚实的理论背景和优良的实用性能成为近年来广泛应用的分类方法，而实际问题的复杂性和实际需求的多样性也给支持向量机技术提出了许多富有挑战性的课题。4 第一章绪论1．2．3分类问题的研究要点与传统的模式分类问题不同，在算法和应用的双重驱动下，各种各样的复杂分类问题摆在了我们面前。从算法的角度看，如何处理大量非线性数据，如何提高分类算法的泛化能力，及如何对各类不同数据设计有效分类方法等问题亟待解决；从应用的角度看，目前，我们面临的观测数据与传统意义下的数据集合并不一样。在过去的日子里，数据一般是通过精心设计的试验，再仔细筛选而获得的，这些数据往往在统计上满足一定的条件(这在试验设计时就已经仔细考虑)；而现在我们获得的数据是涌现性的，如网络数据、生物数据以及经济金融数据，人们不能有效地控制这些数据的产生，只能被动地接受它们。这正是我们的困难所在，也是机器学习领域未来发展的重要研究方向。目前，在实际应用中经常出现的，还需要进一步从理论和应用去完善的分类问题主要有以下几种：(1)类不平衡与代价敏感分类一般的学习机器在分类时总是假定各类别样本数是均衡的，且误分代价是相等的。在实际分类问题中，不同类别的样本数目往往并不相等。以两类分类为例，所谓类不平衡分类问题是指，待分的两类中一类的样本数目远大于另一类的样本数目，当数目较少的类的样本数占1‰3％时，就认为是极度不平衡数据集【13】。在医疗诊断，机械故障诊断，欺诈检测，入侵检测和信用评估等领域，各类数据的分布通常不平衡，即不同类别的样本数相差较多，如：医疗诊断中“病人"样本通常少于“健康人”样本，机械故障诊断中“故障”样本通常少于“正常"样本等。且在医疗诊断、信用卡欺诈检测、网络入侵、故障识别等问题中，不同样本的误分类代价通常不相等，如将“健康人"诊断为“病人”，和将“病人”诊断为“健康人"的误分代价是有很大差别的，国际上将这种误分代价不同的学习问题称为“代价敏感学习(cost—sensitivelearning)”。由于现有的分类算法(如决策树和神经网络等)大多假定待分数据中各类样本数是均衡的，且每个或每类样本的误分代价是相同的，而致力于提高分类器的整体泛化精度，导致在类不平衡或代价敏感问题中分类器的结果偏向于大样本类别，或造成较大的实际损失。因此，在这类问题中，仅凭全局精度评价分类器的优劣是不够的。5 基于支持向量机的若干分类问题研究类不平衡与代价敏感问题涉及到的应用领域非常广泛，目前，已成为机器学习和数据挖掘领域研究的一个新的热点。国内外的众多学者如：Domingos[14】，Margineantu[151，Elkan[161，BianeaZadrozny[171，周志华，刘胥影【18】f191等人已在这方面开展了研究。正如Saitta在MLnetII工程的技术路线图中描述的一样：“融合了代价的学习问题是未来机器学习领域的一个重大挑战[201”。(2)多类分类目前，两分类问题已有较好的解决方法，在实际应用中，多分类问题(类别数大于2)非常普遍，如文本分类、信用评估等。对于这些类别数目较多的分类问题，仍缺乏有效的解决方法。目前已有的多分类方法大至可分为两种，一是将多分类问题分解为多个两分类问题，再将这些分类结果采用某种组合策略组合起来，得到最终的分类结果。如基于支持向量机的一对一(one．against．one)t211、一对多(one．against-res0[221、有向无环图(DAGSVM)等方法【231，及CecilioAngulo[241等人在一对一、一对多方法的基础上提出的一对一对多的方法(KSVCR)等。这些方法可以直接利用原有的SVM两分类方法，不过需要构造多个子分类器，且可能在决策输出时产生不可分区域等问题。另一种途径是在一个优化问题中同时解决多分类问题【221【251，这种方法尽管看起来简洁，但是在最优化问题求解过程中的变量远远多于第一类方法，训练速度远不及第一类方法，而且在分类精度上也不占优，尤其当训练样本数非常大时，这一问题更加突出。如何针对实际多分类问题提出更有效的解决方法，是许多学者在不断努力创新的一个方向。(3)有序分类有序分类是一种特殊的多分类问题，当分类对象的输出标识具有某种自然序的关系时，我们称这种多分类问题为有序分类。如：根据影迷的喜好程度将电影分为若干类(如：Benchmark数据库中EachMovie数据集)，对接收到的大量电子邮件按重要程度分成若干等级来查看，或银行根据客户的信用情况对客户进行信用等级的划分等。目前，机器学习领域中大部分多分类算法都是将有序和无序分类问题同等对待，即假定分类变量是无序的，其标识可用数值表示是第几类，但此数值无排序意义，仅仅是一个代号。这样虽然是可行的，但对有序问题而言，却忽略6 第一章绪论了问题本身所具有的“序’’的信息。W．Cohen，R．Schapire，K．CrammerandY．Singer【26】【271，E．FrankandM．Hall[281，R．Herbfich，T．Graepel，K．Obermayer【29】，AiilnonShashua，AnatLevin[30】等人从有序问题的结构和大间隔分类等方面，对有序分类问题进行了深入研究，并提出一些融合了“序”的信息的实用算法。此外，机器学习中长期存在的，可能永远也无法得到最终解决，但又非常重要的几个问题：提高泛化能力、提高学习速度、提高可理解性，以及在走向实用过程中出现的高维数据的处理、未标记数据的利用、有结构数据的学习及领域知识的利用等，也都是分类问题研究中需要不断努力去解决的。1．3论文的主要内容和结构论文从理论研究和解决各种实际分类问题方法研究两方面出发，以支持向量机理论为基础，对若干分类问题进行了扩展研究，提出一些新的思想和方法。全文共分七章，具体内容安排如下：第二章首先回顾了机器学习的主要内容、学习问题的一般表示和经验风险最小化准则，以及学习机器的复杂性与推广能力之间的关系，并在此基础上介绍了统计学习理论的基本知识，主要包括VC维、推广性的界和结构风险最小化原则；接着介绍了支持向量机的基础理论知识及其优点，最后对支持向量机的发展现状进行了总结和讨论。第三章重点从特征空间的几何度量出发，对核函数所蕴涵的黎曼度量、距离度量及角度度量，进行了详细分析；接着深入探讨高斯径向基核函数的几何性质，并对映射、核与度量间的对应关系进行了分析，指出SVM方法本质上依赖于度量。第四章首先概述了目前解决类不平衡与代价敏感分类问题的方法，接着从特征空间内嵌流形的几何结构入手，通过对特征空间局部区域的放大和对半径间隔界的控制，提出一种新的基于黎曼度量的类不平衡分类方法，最后在人工数据集和实际数据集上对该方法的性能进行了验证。第五章首先通过对一对多方法中采用不同核参数所映射的特征空间几何度量的分析，提出一种基于相对间隔的比较策略，对各决策函数输出值的可比性进7 基于支持向量机的若干分类问题研究行了深入分析；然后对一对一、一对多等分解多分类方法中存在的不可分区域进行研究，针对一些特殊的应用问题，提出一种新的多分类方法一模糊输出支持向量机，最后通过一系列实验，对本章给出的结论和方法进行了验证。第六章对有序分类问题进行了研究，首先概述了目前解决有序分类问题的一般方法，接着从解决普通多分类问题与有序分类问题中函数集容量，即：VC维和分级维的角度，比较了有序与无序分类问题的复杂度，提出一种基于支持向量机的改进的内嵌空间法，最后将其应用在实际有序分类问题中，通过实验比较说明该方法的有效性。第七章总结全文，并对今后的工作提出了展望。8 第二章支持向量机理论基础第二章支持向量机理论基础在利用实际数据进行建模的过程中，传统统计方法对数据要求较高，一些实际应用的效果不理想；而智能学习算法在理论上又缺乏实质性的进展，对很多现象无法作机理上的解释。针对这些问题，Vapnik等人从六七十年代起开始致力于小样本情况下机器学习规律的研究工作，建立了一套全新的理论体系一一统计学习理论(StatisticsLearningTheory，SLT)，并在此基础上发展了支持向量机(SupportVectorMachine，SVM)这一种通用的学习算法，该算法目前已成为机器学习和数据挖掘领域的标准工具，本章将对这一理论做详细的介绍。2．1机器学习的主要问题基于数据的机器学习是现代智能技术中的重要方面，其目的是根据给定的训练样本求对某系统输入输出之间依赖关系的估计，使它能够对未来数据或无法观测的数据进行预测，以实现为人类更好服务的目的。迄今为止，关于机器学习的理论算法较多。其实现方法之一是经典的(参数)统计估计方法，包括模式识别等在内。现有机器学习方法共同的重要理论基础之一是统计学。参数方法正是基于传统统计学的，在这种方法中，参数的相关形式是已知的，训练样本用来估计参数的值。这种方法有很大的局限性：首先，它需要已知样本分布形式，这需要花费很大代价；其次，传统统计学研究的是样本数目趋于无穷大时的渐近理论，现有学习方法也多是基于此假设，在现实问题中，样本数目通常是有限的，传统以无穷多为假设来推导的各种算法，希望在样本较少时也能得到较好的表现，然而，事实很难做到这一点。另一种方法是经验非线性方法，如人工神经网络(ArtificialNeuralnetwork，ANN)。这种方法利用已知样本建立非线性模型，克服了传统参数估计方法的困难。但是，这种方法缺乏一种统一的数学理论，且过分依赖于使用者的经验和技巧。针对这些问题，Vapnik等人从六七十年代起开始致力于小样本情况下机器学习规律的研究工作，建立了一套全新的理论体系——统计学习理论，并在此基础上发展了支持向量机这一种通用的学习算法。到九十年代中期，随着其理论的不断发展和成熟，也由于神经网络等学习方法在理论上缺乏实质性进展，9 基于支持向量机的若干分类问题研究统计学习理论受到越来越广泛的重视。目前，关于SVM的研究正方兴未艾，其理论正在不断深入发展，实践应用不断拓广，已成为机器学习和数据挖掘领域的标准工具，并将有力地推动机器学习理论和技术的发展。2．1．1学习问题的一般表示学习问题可以一般地表示为：变量Y与x存在一定的未知依赖关系，即遵循某一未知的联合概率分布F(x，y)，(X和Y之间的确定性关系可以看作是其特例)，机器学习问题就是根据，个独立同分布观测样本fix,，Y1)，(恐，y2)⋯(而，乃))(2-1)其中，t∈R”，Yj∈R，f=1，．．．，，在一组函数{f(x，co))中寻求一个最优的函数f(x，‰)对依赖关系进行估计，使期望风险尺(缈)=IL(y，f(x，w))dF(x，y)(2—2)最小。其中，{f(x，co))称作预测函数集，缈为函数的广义参数，{f(x，oJ))可以表示任何函数集；L(y，f(x，w))称为损失函数，它是评价预测准确程度的一种度量，不同类型的学习问题有不同形式的损失函数。预测函数也称作学习函数、学习模型或学习机器。有三类基本的机器学习问题，即模式识别(分类问题)、函数逼近和概率密度估计。对模式识别问题，输出Y是类别标号，两类情况下，Y={O，1)或{l，一1)，预测函数称作指示函数，损失函数可以定义为：三cJ，，厂c工，∽，={：；二；{二：：；c2-3，使风险最小就是Bayesian决策中使错误率最小。在函数逼近问题中，Y是连续变量(这里假设为单值函数)，损失函数可定义为：L(y，f(x，w))=(y-f(x，w))2(2-4)即采用最小平方误差准则。而对概率密度估计问题，学习的目的是根据训练样10 第二章支持向量机理论基础本确定x的概率密度。记估计的密度函数为p(x，彩)，则损失函数可以定义为2．1．2经验风险最小化三(p(五缈))---一logp(x，叻(2—5)在上面的问题表述中，学习的目标在于使期望风险最小化，由于联合分布F(x，Y)是未知的，所以我们可以利用的信息只有样本(2-1)，而式(2-2)的期望风险并无法计算和最小化，因此，传统的学习方法中采用了所谓经验风险最小化(EmpiricalRiskMinimum，ERM)准则，即用样本定义经验风险：1fR唧(国)=亭∑三(咒，厂(而，国))(2-6)Ii=1式(2—6)作为对式(2-2)的估计，设计学习算法使它最小化。对损失函数式(2-3)，经验风险就是训练样本错误率；对式(2．4)的损失函数，经验风险就是平方训练误差；而采用式(2．5)损失函数的ERM准则就等价于最大似然方法。事实上，用ERM准则代替期望风险最小化并没有理论上的保证，只是直观上合理的想法，但这种思想却在多年的机器学习方法研究中占据了主要地位。人们多年来将大部分注意力集中到如何更好地最小化经验风险上，而实际上，即使可以假定当，趋向予无穷大时式(2．6)趋近于式(2．2)，在很多问题中的样本数目也离无穷大相去甚远。那么在有限样本下ERM准则能保证得到较小的真实风险吗?2．1．3复杂性与推广能力ERM准则不成功的一个典型例子是神经网络的过学习问题。最初，很多研究者都将注意力集中在如何使R。。(w)更小，但他们很快就发现，训练误差小并不总能导致好的预测效果。某些情况下，训练误差过小反而会导致推广能力(即，泛化能力，指学习机器对未知样本进行正确预测的能力)的下降，即真实风险的增加，这就是过学习问题。之所以出现过学习现象，一是因为样本不充分，二是学习机器设计不合理，这两个问题是互相关联的。设想一个简单的例子，假设有一组实数样本{x，y)，取值在[0，1】之间。那么不论样本是依据什么模型 基于支持向量机的若干分类问题研究产生的，只要用函数f(x，口)=sin(ax)去拟合它们(口是待定参数)，总能够找到一个口，使训练误差为零，但显然得到的这个“最优”函数并不能正确代表真实的函数模型。究其原因，是试图用一个十分复杂的模型去拟合有限的样本，导致学习机器丧失了推广能力。同理，在神经网络中，若对有限的样本来说网络学习能力过强，足以记住每个样本，此时经验风险很快就可以收敛到很小甚至零，但却根本无法保证它对未来样本能给出好的预测。学习机器的复杂性与推广性之间的这种矛盾同样可以在其它学习方法中看到。文献㈨给出了一个实验例子，在有噪声条件下用模型Y=x2产生lO个样本，分别用一个一次函数和一个二次函数根据ERM原则去拟合，结果显示，虽然真实模型是二次，但由于样本数有限且受噪声的影响，用一次函数预测的结果更好。同样的实验进行了100次，71％的结果是一次拟合好于二次拟合。由此可看出，在有限样本情况下：1．经验风险最小并不一定意味着期望风险最小；2．学习机器的复杂性不但应与所研究的系统有关，而且要和有限数目的样本相适应。这就是有限样本情况下学习机器的复杂性和推广能力之间的矛盾。我们需要一种能够指导我们在小样本情况下建立有效的学习和推广方法的理论。统计学习理论的发展和完善为此问题的解决提供了坚实的理论基础和有效的学习方法。2．2统计学习理论统计学习理论是一种专门研究小样本情况下机器学习规律的理论。该理论针对小样本统计问题建立了一套新的理论体系，在这种体系下的统计推理规则不仅考虑了对渐近性能的要求，而且追求在现有有限信息的条件下得到最优结果。Vapnik等人从六、七十年代开始致力于此方面研究，到九十年代中期，随着其理论的不断发展和成熟，也由于神经网络等学习方法在理论上缺乏实质性进展，统计学习理论开始受到越来越广泛的重视。其主要内容包括四个方面【1】【2】：1．经验风险最小化准则下统计学习一致性(Comistency)的条件；12 第二章支持向量机理论基础2．在这些条件下关于统计学习方法推广性的界的结论；3．在这些界的基础上建立的小样本归纳推理准则；4．实现新的准则的实际方法(算法)。其中，最具有指导性的理论结果是推广性的界，它揭示了经验风险和真实风险之间的关系，与此相关的一个核心概念是VC维(Vapnik-ChervonenkisDimension)。2．2．1VC维为了研究学习过程一致收敛的速度和推广性，统计学习理论定义了一系列有关函数集学习性能的指标，其中最重要的是VC维。在分类(模式识别)方法中vC维的直观定义是：对一个指示函数集，如果存在，个样本能够被函数集中的函数按所有可能的2。种形式分开，则称函数集能够把，个样本打散；函数集的VC维就是它能打散的最大样本数目，。有界实函数的VC维可以通过用一定的阈值将它转化成指示函数来定义。若对任意数目的样本都有函数能将它们打散，则函数集的VC维是无穷大。例如函数集：F={f(X，口)=sgn(sin(ax))，口∈R}(2—7)的VC维就是无穷大。VC维反映了函数集的学习能力，VC维越大则学习机器越复杂(容量越大)。遗憾的是，目前尚没有通用的关于任意函数集VC维计算的完整理论，只对一些特殊的函数集知道其VC维。比如在11维实数空间中线性分类器和线性实函数的VC维是n+l，对于一些比较复杂的学习机器(如神经网络)，其VC维除了与函数集(神经网络结构)有关外，还受学习算法等的影响，其确定更加困难。对于给定的学习函数集，如何(用理论或实验的方法)计算其VC维是当前统计学习理论中有待研究的一个问题【321。2．2．2推广性的界统计学习理论系统的研究了对于各种类型的函数集，经验风险和实际风险 基于支持向量机的若干分类问题研究之间的关系，即推广性的界【21。关于两分类问题，结论是：对于指示函数集中的所有函数，经验风险R唧@)和实际风险R@)之间以至少卜rl的概率满足如下关系：R(a)sR唧(口)+(2-8)其中h是函数集的VC维，．『是样本数。上式可简单的表示成：R(口)≤Re．p(口)+≯(Z／功(2-9)这一结论从理论上说明了学习机器的实际风险是由两部分组成：一部分是经验风险尺一@)，另一部分称作置信范围矽(t／h)，它和学>-j机器的VC维及训练样本数有关。可以看出，在有限样本的情况下一味地追求经验风险最小是没有意义的，因为此时学习机器可能过于复杂，导致置信范围变大，从而使真实风险增大，这也就从机理上解释了神经网络的过学习现象。为了使学习机器的推广性较好，必须同时最小化经验风险和置信范围，因此，对学习机器进行容量控制(VC维)是极其重要的。2．2．3结构风险最小化式(2．8)导出了一种控制学习机器推广能力的新思想：为了通过最小化经验风险来达到实际风险的最小界，应该采用VC维最小的学习机器(函数集)。这两种要求，即最小化经验风险和采用VC维最小的学习机器，是相互矛盾的，为了最小化经验风险，我们必须从更广的函数集中选取函数，而不是从VC维小的窄函数集中选取函数。因此，为了找出最优解，我们必须在对给定数据的逼近精度和逼近函数的复杂性之间寻求最佳折衷。为了实现这种折衷，统计学习理论提出一种新的策略，即把函数集构造为一个函数子集序列，使各个子集按照VC维的大小排列；在每个子集中寻找最小经验风险，在子集间折衷考虑经验风险和置信范围，取得实际风险的最小，如图2．1所示，这种思想称作结构风险最小化(StructuralRiskMinimization，SRM)或有序风险最小化【lJ。实现SI蝴原则可以有两种思路，一是在每个子集中求最小经验风险，然后选择使最小经验风险和置信范围之和最小的子集。这种方法比较费时，在子集14 第二章支持向量机理论基础数目很大甚至无穷时是不可行的。第二种思路是设计函数集的某种结构，使在每个子集中都能取得零经验风险，然后只需选择适当的子集使置信范围最小，则该子集中使经验风险最小的函数就是最优函数。支持向量机实际上就是这种思想的具体实现。文【321中讨论了一些函数子集结构的例子，和如何根据SRM准则对某些传统方法进行改进的问题。风险围险函数集子集：slcs2cs3VC维：hl，i=1，．．．，J『，满足只【(w·薯)+明一1≥0，i=1，⋯，，(2—10)此时分类间隔等于2／llwll，因此使间隔最大等价于使|I桫旷最小。要找到最优分类超平面，我们需要在约束条件(2．10)下最小化泛函：痧(w)=i1(w．w)(2-10这个优化问题的解由式(2-12)的Lagrange泛函的鞍点给出：三(w'6，口)=丢(w．们一∑l％{只【@．w)+6卜1)(2-12)其中，嘶为每个样本对应的Lagrange乘子。在鞍点上，W，b，口的解必须满足以下条件：—aL_(w-,b,一a)：0，(2—13)钓、掣：0。(2-14)解(2．13)、(2．14)式，得到下列方程：16 第二章支持向量机理论基础，∑乃q=o，q≥o，i=1，⋯，，(2-15)l-l，w=∑以呸‘i=l(2—16)式(2．16)说明了最优超平面的权系数向量是训练集中的向量的线性组合。将式(2．15)、(2．16)代入式(2．12)，且将原问题转化为其对偶问题，即在式(2—15)的约束下，求解磁，使下列函数有最大值：，1，Q位)=∑q一寺∑噶哆咒乃(x。·x_，)(2-17)j=l厶f，』=l此时，需要解决的问题已经转化为一个不等式约束下二次函数寻优的问题，存，在唯一解，若嘶宰为最优解，则∥=∑M西薯，最后得到的最优分类函数是：j-lf(x)=sgn{(w·x)+6)=sgn{妻zy，(薯·x)+6．)(2—18)·x)+6)=sgn{∑咖，(薯·x)+6．}(2一Ll=lJ式(2．18)中，只有一部分(通常是很少部分)∞幸不为零，对应的样本就是支持向量(SupportVector，SV)，6幸是分类阈值，可以用任一个支持向量求得，或通过两类中任意一对支持向量取中值求得。2．3．2软间隔分类超平面在样本集线性不可分的情况下，可以在条件式(2一lo)q]增加一个松弛项最≥0成为：并将目标改为求咒【(w·xf)+6卜1+孝f≥0，i=1，⋯，，(2-19)(蜩=撕|2+C嘻磊】(2-20)最小，即构造一个软间隔，折衷考虑最少错分样本和最大分类间隔，就得到广义最优分类面，其中C>0是一个常数，它控制对错分样本惩罚的程度。17 基于支持向量机的若干分类问题研究2．3．3支持向量机支持向量机实现的是如下的思想：通过某种事先选择的非线性映射将输入向量映射到一个高维特征空间，在高维空间中求解最优分类超平面，从而将一个棘手的非线性问题转化为一个较简单的线性问题。一般来说这种非线性变换比较复杂，不易实现，但是注意到，在上面的对偶问题中，不论是寻优目标函数式(2．17)，还是分类函数式(2．18)都只涉及训练样本之间的内积运算。这样，在变换后高维特征空间中实际上只需进行内积运算，根据泛函的有关理论，只要一种核函数瓜麓，xj)满足Mercer条件，它就对应某～变换空间中的内积，这样高维空间中的内积运算就可以用原空间中的函数实现。因此，在最优分类面中采用适当的内积函数圈％，xj)就可以实现某一非线性变换后的线性分类，而计算复杂度却没有增加，此时目标函数式(2．17)变为：，1，Q(口)=∑q一去∑口，ay,yjK(X，,Xj)(2—21)i=1二l，J=l而相应的分类函数也变为这就是支持向量机。，厂(x)=sgn(y．a,‘y_fK(x，，x)+6．)(2—22)2．3．4多分类支持向量机支持向量机本质上是对两分类问题提出的，如何将其扩展到多分类问题，是一个研究的重点。设训练样本集为S={(x。，Y1)，(x2，Y2)⋯(x，，Y，))，其中，为训练样本集规模、赡∈X为n维特征向量、Y。∈{1⋯七)为第iX样本对应的等级。目前，基于支持向量机的多分类方法，主要有以下几种：(1)一对多方法(one-versus．rest，l-v-r)122J最早出现的将支持向量机用于多分类问题的方法是一对多方法。该方法对k个类别的样本集构造k个SVM子分类器，在构造第i个分类器Z时，将训练样本中18 第二章支持向量机理论笨础属于第i类的样本标示为“+1"，不属于第i类的其余k一1类样本全部标记为“一l’’，这样，依据不同的样本划分进行训练，就可以构造出k个不同的SVM子分类器。如：第j类SVM解决如下问题：蟛争抄02+C[喜彰】(w。‘xf)+6。一1+彰≥0，if以=J(2—23)(w’·xf)+∥-1+彰-<0，if咒≠歹彰≥0，f=1。』，用这种方法进行多分类时我们解其对偶问题，最终得到k个决策函数一(x)，对于未知类别属性的样本x进行测试时，有的采用多数投票法，大部分还是采取MaxWin策略，即对测试样本分别计算k个子分类器的判别函数值，并选取最大的判别函数值所对应的类别作为测试数据的类别：z的类别考argmax川玉．．k乃(x)(2—24)(2)一对一方法(one-versus．one，l-v．1)文【211中介绍了另一种称之为一对一或成对分类(palrwise)的多分类方法。与一对多方法不同的是，它每次仅使用两类不同类别的样本来构造一个子分类器厶(f≠／)，这样穷尽所有的两两组合，我们可以得到q=k(k一1)／2个子分类器。如：对第i类和第J类我们解如下的二分类问题：mi⋯n刳∥112+c【∑舶彬，|F，i兽，i厶t【(w‘’·Xt)+∥’71-1+彰’’≥0，if．"=f(2—25)[(wL。·It)+∥J卜l+等J≤0，if乃=，彰√≥0对于未知类别属性的样本x进行测试时，分别使用k(k一1)／2个子分类器对其进行属性判别，并采取如下投票策略：如果分类器厶判定x属于第i类，则第i类的得票数加l，否则第j类的得票数加l，最终看哪一类的得票数最多，x就属于哪一类。(3)有向无环图法(DirectedAcycficGraph，DAG)123119 基于支持向量机的若干分类问题研究有向无环图法在训练阶段采用和一对一方法同样的办法构造k(k一1)／2个子分类器，在测试时，并不是所有的子分类器都参与决策，而是采用一种有k(k一1)／2个内部结点和k个叶子结点的有向无环图的方法：首先从k(k-1)／2个分类器中任选一个分类器口，对x进行判别，如果判定X属于第i类，则我们从k(k一1)／2个分类器中将含有第J类标识的分类器剔除，然后利用剩下的分类器继续进行判别、剔除，如此循环，直至剩下最后一个分类器，此时的判别结果才是x的最终类别。(4)整体求解法(KSVM)上面描述的多类别分类方法都是通过构造一系列二值子分类器的求解得到，一些SVM研究者提出可以一次性求解多类别分类问题的方法【251【35】【361，其基本思想类似于one—versus—rest法需要构造k个SVM_．--值分类器，不同的是一次性求解方法是由一个优化问题同时求解k个SVM分类器。把优化问题式(2—23)推广到如下优化公式：min昙圭o％112+c圭∑∥W，b，{4m#lf2，Ⅲ≠见(w乃。xf)+％一(w，’xf)+6肼一2+第≥0(2-26)第≥0，f=l。』，m∈{1，⋯七)＼{y，}判别函数为：classofx三argm，ax，(wm·x+b)(2．27)与二值SVM分类器一样，可通过求解(2-26)的对偶问题来进行优化参数。除了以上的几种方法外，Dietterich等人将纠正数字通讯中的错误码位的方法引入多类分类问题中，提出了输出编码校验(ErrorCorrectingOutputCode，ECOC)方法【37】；CecilioAngulo等人在分解方法的基础上将基于支持向量机的分类和回归方法相结合提出了一对一对多的方法K．SVCR[24】；此外，还有大量的学者提出了一种快速的基于二叉树的多分类方法。不过从算法的复杂性和分类的准确率等方面的综合考虑，目前在实际应用中常用的解决多分类方法主要还是一对一和一对多方法。 第二章支持向量机理论基础2．3．5内积核函数支持向量机将结构风险最小化原理、对偶原理、最优化方法和核函数等几项技术有机地组合在一起，成为解决传统机器学习方法中出现的“维数灾难"和“过学习’’等困难的非常有力的工具。其中，在解决非线性学习机器的计算能力和泛化能力方面，核函数起了决定性的作用。由本章2．3．3节的知识我们知道，解决复杂非线性数据的分类或回归问题，需要将数据映射到高维空间，这就不免会引起“维数灾难"问题，核函数巧妙地把高维Hilbert空：间中两个点的内积计算，用原来输入空间中的两个样本点的简单核函数的求值来代替，不需要清楚的知道映射的具体形式，却隐含实现了映射功能，其算法复杂度与特征空间的维数无关。核函数的理论很早就出现了，与之相关的Mercer定理可以追溯至1J1909年【3引，再生核希尔伯特空间的研究是AroIls冽n在20世纪40年代开始的【39】，Poggio和Girosit4。0l[41】将再生核扩展到机器学习和神经网络领域。支持向量机的性能在很大程度上依赖于核函数的选择，使用不同的核函数，其表现出来的性能有很大的不同，因此寻找一个合适的核函数是支持向量机算法的关键。目前在各类文献和实际应用中，比较常见的核函数有M2】：多项式核函数：K(x，y)=O·y+1)，(2-28)采用这个核函数得到的是一个P阶多项式分类器。径向基核函数：卿川=exp(．一嗲)(2-29)所得分类器与传统的RBF的重要区别是这里每个基函数中心对应一个支持向量，它们及输出权值都是由算法自动确定的。神经网络核函数：K(x，y)=S【(v(x，y)+c】(2-30)其中S【u】是sigmoid函数。这时SVM实现的就是包含一个隐层的多层感知器，隐层节点数是由算法自动确定的，而且算法不存在困扰神经网络方法的局部2l 基于支持向量机的若干分类问题研究极小点问题。一些实验表明，采用上述三种不同核函数的SVM能得到性能相近的结果，且大部分的支持向量都重合【43】，但该结论也仅仅是有限实验中观察到的现象，第三章的实验表明，在非线性可分情况下，对一个特定的核函数，给定的样本集中的任意一个样本都可能成为一个支持向量。这意味着在一个支持向量机下观察到的特征在其它支持向量机下(其它核函数)并不能保持。因此，对解决具体问题来说，选择合适的核函数是很重要的。本文将在第三章对核函数的性质和选择等问题做具体研究。目前绝大部分的SVM算法的核函数，都选用上述三种形式的核函数，但是满足Mercer条件的核函数，远远不止这几种，不同形式的核应用的场合也不同，国内外的研究人员在这个方面已经做了大量的工作。目前对核函数的研究集中在以下几个方面：1．核函数理论研究。如Evgeniou[441，Scholkopfl451，Watkjns湖，MacKayD．M，孔锐【48】，等人在核理论方面做了深入的探索，并构造了一些核函数。2．核函数参数的选择。如CristiaIlini【49】，董春曦pOl，阎辉刚等人关注于核函数参数的选择，得到一些重要的结论。3．特定对象特性的核函数构造和使用。如文‘521提出的子波核函数在图像处理方面取得了较好的结果，文【531中提出了三个同维映射的核，对双螺旋线数据分类，取得了100％的正确率。Vapnik等在文献【54】中提出了一维样条多项式核，弱正则化傅立叶核，强正则化傅立叶核及半正定核等。此外，Scholkopf／”J，Watkinst5q和Haussler【571的论文对核的使用进行了扩展，使之不仅定义在欧式空间上，而且可以定义在一般的集合上，输入空间可以是生物序列、文本、图像等。2．3．6SVM与SRM的联系SVM所做的工作就是让分类间隔最大，这实际上就是对推广能力的控制，它实现了SRM的一种策略，即保持经验风险值固定而最小化置信范围。统计学习理论指出【2】，在Ⅳ维空间中，设样本分布在一个半径为尺的超球范围内，则满足条件Il叫I≤A的正则超平面构成的指示函数集厂(而．．，，6)=sgn{(w·x)+6)的VC维满足下面的界：h_，其中<①(x)·①(y)>为特征空间中两点的内积。定理3．1(Mercer定理)111要保证L2下的对称函数K(x，y)能以系数以>0展开成dFK(x，少)=∑丸①。(x)·①。(少)n=l(3-1)(即，K(x，Y)是某个特征空问的一个内积)，其充分必要条件是：对任一平方可积函数g似卜2(x)dx0(3-3)成立。满足式(3．3)的任一连续对称函数称为半正定核。从定义可以看出核应满足两个条件：对称性，即K(x，Y)=K(y，X)和Cauchy．Schwarts不等式K2(x，Y)≤K(x，x)K(y，Y)。对称正定的函数在统计上称为协方差，所以核从本质上来讲是协方差。从公式(3．1)可以看出，核函数实际上是一个凸锥。Mercer核是依据Mercer定理得到的，根据泛函分析中Hilbert．Schmidt理论，核函数K(x，J，)只要满足Mercer条件，它就可作为内积使用。 第三章高斯径向基核函数几何性质研究定义3．2(嵌入)①是一个嵌入当且仅当①是一个同胚映射，即：Vx，Y∈X，V占>O，了磊，暖满足：d伍”<磊jdB(x，y)<占，dB(X，y)<磊jd(x，YlI(3．12)=4k(x，x)+k(x’，X’)一2k(x，x．)显然，有锣；(x，X’)≥o，锣；(x，x)=o，但矽；(x，xt)=o不能推出x=x’，VXl，X2，x3∈疋，办(Xl，X2)≤办(西，龟)+dy(x3，X2) 基于支持向量机的若干分类问题研究因此dF(x，X’)是输入空间上的一个半度量。从距离度量的角度看，一个核函数蕴含了一个距离变换，即将输入空间上的距离d(z，xt)变换为dF@，x’)，办(x，x’)就称为核函数蕴含的距离度量。由式(3．12)可知，图3．1中的欧氏距离不是黎曼距离。例如：在S上取连接三点P1，P2，P3的一条路径，则在欧氏距离中d(P1，P2)+d(P2，P3)一般会大于d(P1，P3)，而式(3．7)要求两者必须相等。3．2．4角度度量在向量空间，两个向量的相似性可以利用其方向的一致性，即夹角∥来进行判断。给定输入空间x上的核函数后(x，x9，则x，x’在特征空间上的夹角余弦为COSF(X，x’)=k(x，x')／4k(x，x)·k(x’，x’)(3-13)从角度度量的观点看，一个核函数也蕴含了一个角度变换，即将输入空间上x，x’夹角的余弦cos(z，xt)变换为COSF(X，x’)，COSF@，x’)称为核函数蕴含的角度度量。3．3高斯径向基核函数的几何性质研究实际应用中常见的核函数有线性核、多项式核、高斯径向基核和sigmoid核。文‘100]指出线性核是高斯径向基核的一种特例，当线性核采用惩罚参数e时，其性能相当于高斯径向基核采用某参数(C，19")；文‘1011分析了sigmoid核与高斯径向基核之间的关系，表明sigmoid核参数在一限定的范围内其性能与RBF核相接近，不过，一般情况下选用sigmoid核的性能不会超过RBF核。因此，本节我们以高斯径向基核作为研究目标，由以上的分析导出它所蕴含的黎曼度量、距离度量和角度度量，在此基础上给出它的一些几何性质，并深入分析核参数对其性能的影响，为核参数的选择提供指导。32 第三章高斯径向基核函数几何性质研究3．3．1高斯径向基核函数几何度量高斯径向基核函数具有以下的形式：撕，)-exp(一呼)其中仃是尺度参数，如图3．2所示：图3．2RBF核函数示意图由式(3．11)和式(3．14)可直接求出RBF核诱导的黎曼度量：(3-14)喇2杀毒m√儿，：。q[exp(_呼)]，bf[exp(-嗲盯(“№卅b：，=一8。[exp(一嗲)]，b：，：i16u(3-15)其中磊={糍乡由上式可知RBF核将输入空间内嵌到一个平坦的黎曼流形(黎曼曲率张量为零)，该流形是局部欧氏空间的，即局部上能够与欧氏空间的开子集建立等距对应的黎曼流形。 基于支持向量机的若干分类问题研究记r=1／(20"2)，d--IIx一一l|，则根据式(3-12)，有露(x，x-)：2—2k(x，x')=2—2一即112／(20．2)功Ilx-x'|12∥哮．!----+2(-1)n+lrn訾竽从而它的距离度量为：锣；(x，x．)=2府2(x，x．)一2r：d4(x，x．)+。(d4(z，x’))(3．16)=仃之d2(x，x．)一去仃-4d4(x,x3+o(d4(x，xt))根据式(3．13)，它的角度度量为：COSF(X，xt)=后(x，工’)／√后(x，x)。后(x：x’)=后(x，x’)(3-17)一P一(1lxll2+llx]12-211x11．Ilxlleos(x，x．))／(2盯2)对于高斯径向基核函数，根据它的黎曼度量、距离度量和角度度量，可得如下的性质。定理3．2对于高斯径向基核函数，如下的性质成立：1．在所有点上的黎曼度量都相等；2．黎曼度量与距离度量是～致的；3．将输入空间嵌入到特征空间的单位球面上；4．将输入空间中的球面映射到特征空间单位球面上的一个圆上，反之不然；5．输入空间的正交变换和平移变换都不改变特征空间的黎曼、距离和角度度量。6．保持输入空间的距离相似性，对于输入空间中的单位向量，也保持角度相似性；证明：性质1，由式(3．15)，即得；性质2，由式(3．16)，有lim靼=仃-2，Xt'---}Xdz(x，x’)由式(3．8)和(3．15)，有 第三章高斯径向基核函数几何性质研究(出)2=∑go(x)咄呜i，j=∑勖(奶)2=仃一2∑(幽)2=仃-2(出)2因此lim靼：蟛=仃-2，x’--'争Xdz(x，x．)(出)z即黎曼度量与距离度量一致。性质3，根据特征空间中向量的范数为IlzIIF=√：页i万=1，即得；性质4，在输入空间X，任给一球面：C‘IX--aI=，．，经高斯核变换，由(M删=exp(掣)_exp(丢)，懈H(以)112=2-2exp(一知，可知该球面C的像在特征空间中以g(a)为方向向量的一个超平面上，且到矽(口)的距离相等，结合性质3，可知，该球面的像是在特征空间单位球的一个圆上，即以≯(口)为中心的球面与单位球面的交线上。反之，由于，≯(口)在X空间的原像不一定唯一，且特征空间以≯(口)为中心的球面与单位球面的交线上的点zo的逆像F-1(％)不一定属于X，所以其在原空间中的像不一定是球面。性质5，根据高斯径向基核的定义(3—14)，即得；性质6，由式(3—16)，可得，对于固定的仃，当d(x，xt)小时，如(x，x’)也小，当d(x，x’)大时，dF(x，x．)也大，也就是说，高斯径向基函数保持输入空间的距离相似性；由式(3一17)，对于输入空间的单位向量，有cosF(x，x．)=e-(2—2c。s(x，x9)／(20-2)=P一2e2cos(x，x．)“2cr2)；35 基于支持向量机的若干分类问题研究从而当eos(x，x’)大时，COSF(x，xI)也大，反之亦然。因此对于单位向量，它也保持输入空间的角度相似性。此外，根据高斯径向基核蕴含的几何度量我们可以很容易的验证，流形上任意两点的测地距离大于欧氏距离：设x，Y是输入空问任意两点，令d2--IIx-yll2，则S上两点矽(力，妒(j，)之间的测地距离的平方是d2／∥，欧几里德距离是：眵(曲一矽(J，)112--2(1一P-dV2,,J)由公式：l一日1．K(xs，■)专0(3-23)(3—24)由上两式可知，当盯专0时，特征空间任意两个向量互相正交，且间距是√互，由定理3．2我们知道高斯核将数据映射到特征空间一个单位球上，因此，在这种情况下，特征空间的每一点都只在某一维坐标上的值为1，在其他坐标上值全为零，且每个坐标轴上都只有一个点，可以表示为：≯(-)={0，0，．．叩1⋯0)，其中1。表示在第i位上值为1。即所有的学习数据都被映射到特征空间单位球的正半球或负半球的内接矩形的顶点上，因此，函数集可以将全部的样本点打散。此时只要设最优分类超平面：f(x)=W·x+b，其中b=O，W在所有正类样本值为l的对应的位上为1，在所有负类样本值为l的对应位上值为．1(如：三个样本Xl=(1，0，0)∈+1，x2=(o，1，0)∈+l，X3=(O，0，1)∈-1，取w=(1，1，-1))，即可以将所有的训练样本正确分类，且所有的样本到超平面的代数距离为f(x)=W·x=1，即所有的训练样本都成为了支持向量，定理得证。定理3．4当盯趋于∞大时，高斯核SVM将所有测试样本点全部判为同一类，即其学习推广能力为零。证明：当盯一。。时，高斯核Kc薯，_，：e坤c一监丢乒，一，，比，y，此时高斯核SvM的判决函数为：，f／(x)=sgn(∑a,y,r(x。，x)+6)=sgn(∑aiYt+6)，，由上述Ⅺ厂T条件知，∑y,tr,=o，所以高斯核sVM的最终判决函数为一个常数函数：f(x)=sgn(b)，即把所有点分为一类。同时，我们还可以从黎曼度量的角度，对上述性质进行分析：当盯专。时，流形上任意两点的测地距离s2／o‘2专oo，也就是说，没有哪39 壮十芷持向量机的若十f分类【lJl题IIIf究两点具有椰似性，每个点距离其他的点都是无穷远，因此每个点都成为了支持向量，都町以被lF确分类。当盯--4∞时，流彤L任意两点的测地距离j2／盯2-÷0，也就是蜕所有的点都聚到起，具有相同的性质，所以分类机器将所有的样本点都分为了‘类。我们以一个两类数据(半径小于等十05的圆内点(红色)和半径大Y'O5d'于等于1的圆环罩的点(蓝色))为例，分别取核参数口_÷0，和盯--->∞，在训练集}二学习结果如下图所示，图中所有的点都成了支持向量(其中带有白色圆圈的点表示是支持向量)。图3．9盯_÷0的分类结果图3．10盯_÷∞的分类结果当盯．÷0时，几乎每一个训练样本点都成为了支持向量，出现了过学习现象f图391。此时虽然学习准确率非常高，但学习机器已失去了泛化能力t故测试准确率非常低。当盯呻∞时，分类超平面成为一条直线，出现欠学习现象，学习机器失去了泛化能力(图3．10)。更进一步，我们对训练样本平衡和不平衡的情况分别做了实验，发现：当两类样本严重不平衡时，如：『F类样本远远大于负类样本，无论盯趋于0或趋于无穷大，全部样本都会分为正类。 第三章高斯径向基核函数几何性质研究3．4映射、核函数与度量在支持向量机中，我们通常是直接选用一个满足Mercer条件的核函数表示特征空间中两点的内积，而不需要清楚的知道映射的具体形式。由式(3—1)我们知道这样的映射是存在的，由核函数可以反解出映射西的具体形式，且这个解不是唯一的，即多个不同的映射对应着同一个核函数。从这种意义上说核比映射更本质。由式(3．11)～(3．13)可知对某一具体的核函数，在特征空间有唯一的度量与之对应，但是反之不然，Nash嵌入定理告诉我们：任何一个dL维紧致的黎曼流形可以嵌入(吮／2)(3吮+11)维欧氏空间子流形，任何一个dL维非紧致的黎曼流形可以嵌入(吃／2)(吮+1)(3dL+11)维欧氏空间子流形u021。而我们知道支持向量机采用高斯径向基核映射的特征空间的维数是无穷维，采用P阶多项式核映射的特征空间的维数是C，吒～，这远远超出了Nash嵌入定理给出的界。对这一现象的一个合理解释是：对同一个度量，存在不同的核函数，也就是说核到度量是多对一的关系。从这种意义上说，度量比核更本质。举例，如图3．11所示，我们可以构造一个恒同映射，将尺2空间的一个子集映射到它自身，即内嵌空间的维数是2，度量是欧几里得度量。我们也可以选择另外一个核函数将这个子集映射到一个圆柱面或圆锥面的子集，此时内嵌空间的维数是3，而度量仍然是欧几里得度量。这也在一定程度上说明为什么经过核映射在一个高维的特征空间采用大间隔分类方法却不会出现维数灾难等问题。图3．11核到度量的多对一映射41 基于支持向量机的若干分类问题研究由以上分析我们可知，映射、核与度量之间存在以下关系：定理3．5在SVM分类问题中，核比映射更本质，而度量比核更本质；定理3．6给定一个度量可反解出满足式(3．11)一(3．13)中的核函数，给定一个核函数可反解出满足式(3．1)的映射，且其解都不是唯一的。由以上两个性质我们可以看出在核函数的选择上有一些等价类，在特征空间它们产生同样的度量，即同样的分类效果和泛化能力。从而说明支持向量机算法的解本质上依赖于度量而不是核函数。另一个启发思想是，我们可以根据数据的性质，事先构造可以产生好的分类性能的度量，再寻找可以产生这种度量的核函数，具体实现见第四章和第六章。3．5本章小结核函数研究是目前机器学习领域的一个热点和难点，核函数的选择在很大程度上决定了支持向量机性能的好坏。由于核函数刻画的是特征空间中的内积，因此核函数蕴函了许多几何度量。考虑到特征空间几何意义直观的度量对核选择能提供更为有效的指导，本章从特征空间的几何度量出发，对核函数所蕴涵的黎曼度量、距离度量及角度度量，进行了详细分析，进而深入探讨高斯径向基核在上述三种度量下的几何性质，以及核参数对其性能的影响，并分析了映射、核与度量的关系，指出SVM方法本质上依赖于度量而不是核与映射。42 第四章基于黎曼度量的类不平衡与代价敏感分类问题研究第四章基于黎曼度量的类不平衡与代价敏感分类问题研究4．1引论在真实世界的分类问题中，不同的分类错误往往会带来显著不同的损失，而且不同类别样本的数目往往有显著的差别。传统的机器学习研究大多假定所有的分类错误会带来相同的损失，而且不同类别的样本数基本相同，仅凭全局精度评价分类器的性能优劣，这在解决类不平衡与代价敏感问题时效果并不理想。因此，为了更好地解决真实世界的问题，代价敏感学习和类别不平衡学习正越来越引起人们的重视。以两类分类为例，所谓类不平衡分类问题是指，待分的两类中一类的样本数目远大于另一类的样本数目。实际应用中在医疗诊断，机械故障诊断，欺诈检测，入侵检测和信用评估等领域，各类数据的分布通常不平衡，即不同类别的样本数相差较多，如：医疗诊断中“病人’’样本通常少于“健康人’’样本，机械故障诊断中“故障”样本通常少于“正常"样本等。在类不平衡数据的分类和预测中，基于精度的传统分类算法(如：多元判别分析，神经网络模型等)往往偏向于大类别样本，即样本较多的类的分类和预测精度要高于样本较少的类，我们将其称为“有偏分类器”。这些算法虽然可以获得较高的整体准确率，却使少样本类的分类准确率大大降低，在极端情况下，甚至会将所有的样本分为一类。若样本集包含2个“病人"样例和98个“健康人"样例，则分类器通过把所有的样本划分为“健康人"即可得到98％的分类精度，但这样的诊断不能识别出所需的“病人"样例，没有实际意义。传统的分类方法里，这种极力追求总体低错误率的方法同样会对一些错分代价敏感(cost．sensitive)问题产生严重影响。因为不同领域所容忍的错误代价并不一样，即使同一领域中不同的判断所对应的代价也不尽相同。严格来讲，错分代价敏感问题分为两种，一种是依赖于样本的错分代价，另一类是依赖于类的错分代价。前者假定不同的样本有不同的错分代价，即使它们属于同一类并被错分到相同的另一类，产生的错分代价也是不一样的；后者认为同一类的样本被错分到另一相同类的错分代价是一样“191。本文中，我们只考虑第二种43 基于支持向量机的若干分类问题研究情况，即依赖于类的错分代价敏感问题。这里所说的代价可以是花费的财力，物力或消耗的时间等等。如：在银行信用风险评估中，参评的企业大多具有良好的信用，信用较差的企业仅仅占总样本的一少部分。同时，信用评估问题又是代价敏感分类问题。将信用良好的“履约企业"评估为信用较差的“违约企业"和将“违约企业"评估为“履约企业’’的损失代价是不同的。前者仅仅使银行损失一笔贷款利息，而后者会使银行面临本金无法收回的巨大风险。Altman的研究指出：在信用风险评估中，这两类错误的损失代价相差20倍到60倍‘103l。目前，类不平衡分类与代价敏感分类问题已引起很多学者的关注，成为国际机器学习领域的研究热点之一。本章在对比现有的解决类不平衡与代价敏感分类方法的基础上，从特征空间的几何结构入手，通过对局部空间的放大和对半径间隔界的控制，提出一种新的基于黎曼度量的类不平衡分类的方法，最后在人工数据集和实际数据集上对该方法的性能进行验证。4．2目前解决类不平衡和代价敏感问题的方法由以上分析可知，传统的基于精度的学习机器片面的追求高的总体准确率，在类不平衡和错分代价敏感问题中并不适用，我们要根据实际应用问题的要求来进行研究。最近的一些研究表明代价敏感学习的方法与类不平衡学习的方法有紧密的联系。Malooftl041等人指出，在某些情况下，从类不平衡数据集学习和从代价敏感数据集学习可归结为相同的方式。一方面，代价敏感学习方法是类不平衡学习方法的有效解，另一方面针对类不平衡问题设计的学习方法对代价敏感问题同样适用‘1051。目前解决类不平衡和代价敏感问题的方法主要集中在以下两类：(1)重构训练集，然后使用现有的算法实现类不平衡和代价敏感分类。典型方法主要包括“上采样(upsampling)"和“下采样(downsampling)”【105】【106】【1071。“上采样"方法是在训练之前，根据已有的学习样本，通过简单复制或插值等方法，人为的制造少类别的样本，以使得不平衡训练样本中各类别的样本数目相等或接近。对代价敏感问题同样，“上采样"通过复制高代价类的样本使 第四章基于黎曼度量的类不平衡与代价敏感分类问题研究得两类样本的代价和其数目成比例。“下采样’’方法是从大类别样本中随机抽取与少样本类数目相当的样本作为该类的训练数据。对代价敏感问题，“下采样”从低代价类样本中抽取部分数据，使得两类样本的代价和其数目成比例。设两分类问题中学习样本误分代价较高的类别为正类，样本数为t，相应的误份代价为e，误分代价较低的类别为负类，样本数为t，相应的误分代价为C-，我们可以通过标准化将C-设为1，则在误分代价敏感问题中e总是大于1，采用重采样法正类对负类的优化比例为：K2芑降。，在训练样本类不平衡学习问题中，具有较少样本的类应有较大的比例系数：几2专㈣，(2)重新设计分类器，使分类器本身具有代价敏感性。典型的方法主要包括“加权系数法"和“增加虚支持向量法"等。“加权系数法"是根据每类样本数目的多少或错分代价的大小，对样本或分类误差分别赋予不同的权系数，使得实际误差达到最小等。针对非线性可分的类不平衡问题，支持向量机同样是“有偏分类器"。当样本分布不均衡时，其基于软间隔的“广义最优分类超平面’’会偏向于样本较少的类，这样虽然保证了整体分类准确率较高，但少样本类的分类准确率却大大降低了。“增加虚支持向量法【1081"就是采用支持向量机进行分类时，通过某种规则，增加少数类虚支持向量，使两类的支持向量个数达到基本平衡。所谓虚支持向量，是指按照某种规则人为添加的，类似于支持向量的，位于分类超平面周围的点。由于事先我们并不知道样本的分布，因此没有一个统一的增加虚支持向量的规则。通常，我们假设包含在某类样本的一个充分小的邻域内的样本与该样本属于同一类。这样我们可以在以少数类的支持向量为中心的一个充分小的邻域内增加虚支持向量，作为少数类样本的支持向量，使其与多数类样本支持向量的数目比较均衡。45 基于支持向量机的若干分类问题研究以上这几种方法各有优缺点：重采样法比较简单，实现起来比较容易，但是“下采样’’方法如果从大类别或低代价样本中随机抽取部分样本，会丢失剩余样本的有用信息，当样本数比较少时一般不宜采用这种方法；“上采样”方法如果采用简单复制或插值等方法人造数据，则可能带来噪音，有时反而降低了分类准确率。加权系数法中代价权重的选择没有统一的标准，较难确定。不过这两种方法只需要训练一次学习机器。由于支持向量机分类时只依赖于各类的支持向量，所以增加虚支持向量法可以在一定程度上解决类不平衡问题，且充分利用了已有的信息，但这种方法至少需要训练两次学习机器，并且当增加的虚支持向量不适当的时候，反而成为噪音数据，会降低分类的准确率。此外，在支持向量机中，我们可以根据实际应用问题中两类误分代价间存在的差异，将目标函数的具体表达式改为：min(w，孝)=去0叫12+c，∑白+c：∑厶二{』：Yj2—1“”xj)+b121}{肼：‰21，【(”‘如)+6l=-I}(4．3)其中Cl表示第一类错误的惩罚系数，C2表示第二类错误的惩罚系数。即在目标函数中，对不同的误分代价采用不同的惩罚系数Cl和C2(Cl，C2>0)，并通过对Cl，C2的调整来控制两类误分代价的分布【109]。4．3一种基于黎曼度量的类不平衡分类方法4．3．1利用黎曼度量扩大分类间隔由第三章的知识我们知道输入空间的映像S在特征空间是一个扭曲的子流形，它定义了从输入空间X到特征空间F的一个嵌入，且它的维数是输入空间的维数。一般F为再生核Hilbert空间(RKHS)，RKHS是Hilbert空间的子空间。也就是说，核函数将输入空间的数据映射到高维特征空间的一个低维子流形，且在这个流形表面可以采用合适张量定义的黎曼度量来分析距离。由3．2．2小节我们知道这样的张量g的成分如下式：啪，2C三哿一鬻]如，“剞此时，可以在S空间引入一个黎曼度量G(x)=(‰(z))，其中G(x)是行×刀的 第四章基于黎曼度量的类不平衡与代价敏感分类问题研究正定矩阵，即我们由核函数可以直接计算出黎曼度量张量。对于高斯核m咖e啾一呼)，其诱导的黎曼度量为：g{，(功=专磊其中磊=骱多对于d阶多项式核K(x，x’)=(1+x·X7)d，其诱导的黎曼度量为：岛(x)=d磊+xfx．／d(d一1)(4—5)(4—6)在黎曼空间中，体积元dV=490，必存在一个正数∥使得c(x)≥胗0(4．14)从而49 基于支持向量机的若干分类问题研究II。4K(x，x’)g(x)g(x')dxdx’5J[AxAC(x)c(x．)K(x，z39(x)g(x’)axax7≥∥2Il。爿K(m’)g@)g(x')dxdx’>0(4．15)因此霞(x，r)满足Mercer定理。总结以上讨论，我们的方法是分为两步：(1)用原有的核K优化一个支持向量机，求出支持向量；(2)利用公式(4．8)和(4．11)构造新的核函数霞，再利用新的核函数进行分类。4．3．3实验与分析为了检验上述方法的有效性，我们在人工数据集和实际数据集上分别做了仿真实验，实验结果如下。实验1：人工非线性可分数据的分类。我们在[一0．5，0．5】×[一0．5，0．5】区域随机产生800个两维数据，由非线性边界J，=0．5sin(2xx)将其分为两类，正弦曲线的上部标记为正类，下部标记为负类，取其中的250个正类数据和40个负类数据作为训练数据，其余样本中各抽取60个作为测试数据，由于训练样本中正类明显多于负类，因此这是一个训练数据类不平衡的分类问题。我们用OSUSVMClassifierMatlabToolbox3．00作为仿真工具，取高斯径向基核，分别做两组实验。第一组实验是直接用交叉验证的方法优化高斯径向基核参数，找到最优分类超平面进行分类；第二组实验是，首先标记第一组实验中找到的支持向量，再利用上节介绍的方法修正原始核函数，重新进行训练。两组实验中，最优分类面与支持向量的变化如图4．1和图4．2所示，实验结果如表4一l所示。从图4．1和图4．2中我们可以看出：采用修正核函数的分界面更接近理想分界面，且支持向量的个数更少；从表4．1的分类结果来看本章提出的方法可以有效的提高负类样本的分类准确率。 第四章基于黎曼度量的类不平衡与代价敏感分类问题研究+正类样本口负类样本一原始分界面～一SVM最优分界面。支持向量图4．1普通RBF核分类时的最优分类面图4．2修正RBF核分类时的最优分类面与SV表4-1sin曲线分类结果训练准测试准确正类准确负类准确SV个核函数确率率窒率数普通RBF核0．98940．82930．85590．802721修正RBF核0．99650．84530．85200．8385135l 基于支持向量机的若干分类问题研究实验2：商业银行信用风险评估数据分类在商业银行信用风险评估问题中，由于进行评估的客户中大多具有良好的信用，因此，信用风险评估问题是一个典型的训练样本类不平衡分类问题。这里抽取的364个实验数据来自于福建省某商业银行，其中280家企业的财务状况良好，银行对其发放贷款的风险较小，这些企业我们简称为“履约’’企业，将其标识为正类；其余的84家企业的财务状况较差，若给予贷款，其违约的可能性较大，这些企业我们简称为“违约”企业，将其标识为负类。两类样本中各取其中的75％作为训练样本，剩下样本中各取21个作为测试样本。和实验1一样，我们同样做两组实验，第一组实验采用普通RBF核函数，第二组实验采用本文所述的修正的RBF核函数。实验工具是LIBSVM．mat一2．81，核参数采用5重交叉验证进行优化，实验中支持向量机的分类准确率和支持向量的变化如表4—2所示。表4．2银行信用风险评估数据分类结果训练准确测试准确正类准确负类准确SV个核函数率数普通RBF核0．89260．83810．91400．7622114修正RBF核0．91210．85690．90120．8126103由以上两个实验结果我们可以清晰的看出，由于待分类问题中两类训练样本数目相差悬殊，若直接用于SVM的学习，会造成SVM的最优分类面偏向样本密度小的一方，这样将来用于预测时，会造成少样本类有较大的分类误差。而采用本章介绍的修正核函数的SVM学习，少样本类的分类准确率得到提高，另一类的分类准确率也不会下降太大，从而在解决了类不平衡问题的同时，保持较高的整体分类准确率，使学习机器的泛化能力更强。由式(4．8)～(4．11)式可知特征空间中，少样本类的支持向量附近区域被放大，增大了少样本类与分类超平面的间隔从而提高了少样本类的分类准确率，同时由于距离少样本类支持向量最近的点是另外一类的支持向量，所以另 第四章基于黎曼度量的类不平衡与代价敏感分类问题研究外一类的支持向量附近的区域也在一定程度上有所放大，故其分类准确率不会下降太多。同时，由于每个支持向量作用的范围被增大，建立最优分类超平面所需的支持向量个数就减少了。对于代价敏感问题，同样可以采用上述方法降低误分代价。这时，我们只要将误分代价较大的一类对应于上述方法中的少样本类，通过修改核函数，扩大其与分类超平面的距离，就可以在一定程度上解决代价敏感分类问题。值得注意的是，本章所述的方法是建立在支持向量的稀疏性上的，如果原始核函数的参数、类型选择不恰当或其他原因，使得大部分训练数据都成为支持向量，采用此方法则说明几乎整个数据集在特征空间中被放大了，由上述的半径间隔界可知，此时修正后的核函数不会起到更好的分类效果。另外，参数f的选择直接影响到分类的准确率和支持向量的个数，而如何选择一个合理的f，以及分析它与其它参数的关系是以后继续研究的一个内容。4．4本章小结由于类不平衡与代价敏感问题涉及的应用领域非常广泛，而成为近年来研究的热点，目前主要的研究方法都是集中在对样本集的处理和代价权重的选择。本章从特征空间的几何结构入手，通过对局部空间的放大和对半径间隔界的控制，提出一种新的基于黎曼度量的类不平衡分类的方法，在保证多数类准确率较高的前提下，达到提高少数类分类准确率，有效的减少了支持向量机在类不平衡问题中的有偏性，并在人工数据集和实际数据集上对该方法的性能进行了验证。53 基于支持向量机的若干分类问题研究第五章基于支持向量机的多分类问题研究5．1引论实际应用中我们经常会遇到大量的多分类问题，即待分样本的类别数大于二。支持向量模式分类方法最初是针对二类别的分类问题而提出的，如何将其有效的推广到多类别分类仍然是当前支持向量机研究的重要内容之一。目前，已有一些基于支持向量机的多类别分类方法，这些方法的设计主要有两类途径，其中一类是分解算法，即将一个多分类问题分解为若干个两分类问题，通过构造多个SVM二值分类器并将它们组合起来实现多类分类，如一对一，一对多，DAGSVM等方法。另一种途径是整体方法，即直接在一个优化公式中同时考虑所有类别的参数优化。整体求解的方法尽管看起来简洁，但是在最优化问题求解过程中，此二次规划问题的变量个数远远多于前几种方法，训练速度远不及分解方法，而且在分类精度上也不占优，尤其是当训练样本数非常大时，这一问题更加突出，所以，目前实际应用中还是以一对一和一对多方法为主。在一对多方法中，采用比较各子分类器中测试样本点到分类超平面的距离大小作为决策依据，如果采用不同的核函数参数优化各个子分类器，相当于在不同的特征空间进行分类，此时，能否直接采用求输出最大值等判别策略，需要研究各分类器的输出是否可比，目前的文献中还没有对此问题进行深入的研究。此外，一些分解多分类方法在决策输出时，会产生一个不可分区域，对此区域内的样本缺乏做出合理预测的依据，而在某些实际应用中落在此区域的样本又是需要特别关注的，如何对这些样本进行分类也是一个值得研究的问题。本章包括两个内容，一是通过对一对多方法中采用不同核参数所映射的特征空间几何度量的分析，提出一种基于相对间隔的比较策略，对各决策函数输出值的可比性进行了深入分析；二是对一对一、一对多等分解多分类方法中存在的不可分区域进行了深入研究，针对一些特殊的应用问题，提出了一种新的多分类方法一模糊输出支持向量机(FuzzyOutputSupportVectorMachine，FOSVM)，并通过一系列实验，对本章给出的结论和方法进行了验证。 第五章基于支持向量机的多分类问题研究5．2不同特征空间的分解多分类方法目前，常用的分解多分类SVM在构建各个子分类器时，基本采用统一的核参数，而各类文献当中也没有明确指出不同核参数与决策值之间的关系，实际上我们在构建各个子分类器时由于分类的数据不同，各子分类器中最优分类超平面所对应的核参数是不同的，如果采用统一的核参数进行优化，只能在总体上大致达到一个好的分类效果，而各个子分类器的性能并不一定是最优的。如果各个子分类器采用不同的核参数，对普通一对一方法这种采用多数投票法决策的分类方法是可行的，但对于一对多这种以决策函数的输出值大小直接比较的方法，就需要考虑其输出值的可比性。由本文第3章的分析我们知道，同一核函数中选择不同的核参数对应着不同的特征空间，而在不同的特征空间，样本间相似度的度量尺度是不同的。从嵌入流形的角度看，不同的核函数或同一核函数采用不同核参数，所对应的流形形状是不同的。在分解多分类算法中，如果各个两分类器的最优核参数不一致，那么，从直观上看，直接比较他们的输出结果是没有意义的。那么如何使不同特征空间的决策值具有可比性呢?这里我们以最常用的高斯径向基核为例进行分析。5．2．1高斯核不同特征空间度量可比性分析(1)局部可比性分析由第三章的分析我们知道，通过核函数，可将输入空间的数据映射到高维空间的一个子流形，且在这个流形表面可以通过黎曼度量分析两点的距离。设x，Y是输入空间任意两点，则这两点在输入空间距离的平方为：s2=llx-yll2，采用尺度参数为盯的高斯径向基核将x，Y映射到特征空间流形S上两点矽(x)，矽(y)，在S上这两点之间的测地距离的平方是：s：学：事㈤-，欧几里德距离是：55 基于支持向量机的若干分类问题研究疋=愀x)一≯(叫2=2(1一P一卜一汗／2口2)=2(1e-$2／2口2)(5—2)由式(5—1)可以看出，当RBF核尺度参数仃增大时，≯(x)，≯(J，)间的测地距离会减小，反之，当盯减小时，矽(x)，≯(y)间的测地距离会增大。由式(5—2)可以看出，当RBF核尺度参数盯增大时，≯(x)，≯(y)间的欧氏距离会减小，反之，当盯减小时，矽(x)，矽(y)间的欧氏距离会增大。(2)全局可比性分析从全局的角度出发，我们可以分析采用不同核参数将数据映射到不同高维特征空间所占区域的大小，即在特征空间数据间距被放大(缩小)的程度。这一点我们可以利用特征空间包含所有样本点的最小超球半径来分析。由第3．3．2节我们知道特征空间包含所有样本点的最小超球半径具有如下形式：R=max～／(矽(x，)一矽(丁))·(≯(x，)一≯(丁))=max√矽(x，)·≯(一)一20(x，)·矽(丁)+≯(丁)·矽(丁)(5-3)=max4X(xf，t)一2K(xj，丁)+K(T，r)其中：矽(丁)=∑q矽(薯)，是特征空间中包含所有样本点的最小超球中心。将RBF核代入上式得：R=maxx[r(x,，‘)一2K(xt，r)+K(T，丁)=maX(5．4)上式表明当RBF核尺度参数盯增大时超球半径减／ix；当o-减小时超球半径增大。与局部可比性分析类似，从全局的角度看，RBF核尺度参数仃增大时，特征空间数据问的距离减小，反之，当仃减小时，特征空间数据间的距离增大。由以上两点分析我们可以得出如下结论：结论5．1给定训练样本集“，x2，．．．，xt>∈R”，采用不同的RBF核参数会将其映射到不同的特征空间，且在不同特征空间，样本间的距离与RBF核尺度参数盯有如下关系：较大的参数仃对应的特征空间中，样本间的距离较小；较小的参数盯对应的特征空间中，样本间的距离较大。但是以上的结论并不能说明，在一对多分类问题中采用较小的核参数得到 第五蒂堆十立{=j_n量机的多分类问题研冗的决策值就大，采用较大的核参数得到的决策值就小。由最大『日J隔原理可知，基奉支持向量到最优超平面的最犬削隔‘儿何间隔)是力／叫I，其决策函数值‘函数州隔)是f(x。)=w·烈t，)+6=1，在不同的核参数F，问隔是不刚的从而影响到决策值的大小。图5．2展示了在四个数据集上当盯变化时，ll叫I与SD=∑1w妒(‘)+6I(所有样本点到分类超平面的函数间隔的绝对值之和)的变化情况，其中二_三个是人工数据集，如图5．1所示：图图5．t(C)sin图51(a)twociFCle是由两个圆组成的两分类数据集，图5．1(b)hyperbo】a是二维平面上由双曲线划分的两类数据，图51(c)Sin是在_维平面上由正弦曲线划分的两类数据，另外一个数据集是UC[数据库的balance数据集，取其 基于支持向量机的若干分类问题研究中的L类作为正类，B，R类作为负类，由于balance数据集具有四个属性，此处没有给出数据分布图。图5．2(a)twocircle图5．2(b)hyperbolar图5．2(c)sin图5．2(d)balance图5·2中横坐标表示高斯核函数参数72专，纵坐标表示分类超平面方向向量l|w0与所有样本点到分类超平面的函数间隔的绝对值之和SD的值，其中实线表示I|w|I的变化情况，虚线表示SD的变化情况，为了方便作图，图5．2(a，b)中的SD值为实际SD值除以10(SD／IO)，图5．2(C，d)中的SD值为实际SD值除以50(SD／50)。由图5．2及本文3．3．2节的知识，我们可以得出在同一数据集中RBF核参数仃的变化，对方向向量w的模llw0和所有样本点到分类超平面的函数间隔的绝对值之和SD的影响如下： 第五章基于支持向量机的多分类问题研究结论5-2RBF核参数仃越大，相应的11wo越大，即：间隔％8越小，且在仃取最优值附近时，SD达到最大值。由结论5．1和结论5．2可知，当RBF核尺度参数盯增大时，样本间距离减小，分类间隔ר也相应的减小了，因此，在比较不同仃对决策输出值的影响／¨W¨时要将这两者结合起来考虑。从实验当中我们还发现，所有样本点到分类超平面的函数间隔的绝对值之和SD，达到最大值所对应的核参数盯，与通过交叉验证，取得的最优值盯基本一致，这也启发我们可以根据SD值的大小对核参数进行优化。5．2．2基于相对间隔的不同特征空间分解多分类方法实际上，通过对相对间隔的比较分析，我们发现，在分解多分类问题中，如果各个子分类器采用不同的核参数，其决策函数值同样是可以直接比较的。如图5．3和5．4所示，若图5．3是某一较大核参数对应的特征空间一对多分类中的1类(图中的圆圈)对2，3，4类分类结果，图5．4是另一相对较小核参数对应的特征空间中2类(图中的三角形)对1，3，4类分类结果，由上一节的分析可知，在特征空间，样本间的距离和分类间隔应具有图5．3和5．4的形式。对未知样本x(图中以实心圆表示)进行预测，由图我们可以清楚的看出x与第一类更相似，应将其标识为第一类，如果采用最大几何间隔预测其类别时由于x到图5．4中的间隔比5．3更大所以X会被标识为第2类。因此，不能直接采用几何间隔比较其大小。此时，我们可以采取先将各类输出标准化到一个o／／L嚣≥△2／11w。6／寒◇△口。口：◇；I图5．3较大参数l-v-2，3，4图5．4较小参数2-v-1，3，459o 基于支持向量机的若干分类问题研究可比的度量尺度，再比较其大小。由于在不同的特征空间，样本间间隔减小的同时，分类间隔也相应的减小，我们可以利用样本点到分类超平面的相对间隔，即：测试样本点到超平面的几何间隔除以分类间隔的大小来表示此样本在该特征空间的可分性，不同特征空间的输出值转化为相对间隔值来进行可分性的对比。设测试样本点薯到分类超平面的距离为D(‘)，分类间隔为夕缸。定义5．1相对间隔r：铲：D(xi)．I|wlI(5．5)俐wlI由于薯到分类超平面的距离D(葺)=(W·≯(t)+6)／¨wII，代入上式得：F=W·≯(．t)+6(5—6)式(5—6)式正是支持向量机中的决策函数值厂(而)，因此，我们有如下的结论：结论5．3在一对多等采用决策值大小比较的多分类问题中，分别优化各个子分类器，其核参数可以是不相同的，在最终决策时可以使用Maxwin策略直接比较决策函数值的大小，最大的值所对应的类别就是测试样本的类别。5．2．3实验与分析我们以标准数据库中的6个多类数据集为例，采用上节介绍的不同核参数优化各子分类器，使其性能达到最佳，直接比较决策函数值的大小进行多分类实验，并与普通的一对多方法进行了比较。其中glass6指原始glass数据集的全部六类数据，共214个样本；glass3指glass数据集中的70个“floatprocessedbuildingwindows"数据，76个“non．floatprocessedbuildingwindows”数据和51个“non—windowglass”共197个样本。letter(abcd)数据集是从标准数据库的letter—recognition数据集中抽取的表示字母‘A’，‘B’，‘C’，‘D’的部分数据。实验采用LIBSVM．mat．2．81工具包，每一个数据集的每类数据均采用5重交叉验证选择最优的参数。实验数据集描述及实验结果如表5—1和表5—2所示。 第五章基于支持向量机的多分类问题研究表5-1不同核参数实验数据集描述名称类别数属性数学习数据大小测试数据大小balance34438187W1ne313490209glass33913859glass66914965letter(abcd)416690280vehicle418592254表5-2不同核参数实验结果名称普通1中r(y。％盯：)不同参数卜V—r(厂2％仃z)91．97％balance90．37％(0．05)(0．04，0．1，0．04)98．11％Wlne98．11％(1)(1，0．1，1)77．97％glass374．58％(0．3)(O．3，0．5，0．09)63．07％glass661．53％(1)(2，9，0．5，0．1，l，0．5)86．26％Letter(abcd)84．53％(0．05)(O．01，0．05，O．05，0．01)78．74％vehicle76．37％(0．5)(0．1，l，l，0．02)由表5—2我们可以明显看出，在一对多方法中可以采用不同的核参数，分别优化各子分类器使其性能达到最优，不同核参数的子分类器输出结果同样是具有可比性的，可以直接采用原始的一对多决策函数对测试数据进行判断，其性能在整体上比采用统一核参数的一对多方法要好。61 基于支持向量机的若干分类问题研究5．3基于决策间隔的多分类模糊输出支持向量机5．3．1多数投票法与不可分区域多数投票法是目前分类器组合中常用的一种决策方法，它根据各个子分类器的分类结果进行投票，得票数最高的类别就是最终的决策。基于支持向量机的一对一和一对多方法在决策时如采用多数投票法会产生一个不可分区域，此区域的大小直接影响到分类器的分类性能。如图5．5所示，以分三类为例，一对一方法采用多数投票法决定测试样本的类别，图中落入阴影区域的样本每类均得一票因而无法决策出其最终类别。一对多方法采用多数投票法时不可分区域如图5．6所示，虽然一对多方法可以采用最大输出值的策略决定阴影区样本的类别，但也有可能出现多个决策函数的值相等且达到最大，此时便无法推断测试样本的类别，或当决策函数的值相差很小时，其推断结果也已很不可信p训。图5．5卜v一1不可分区域图5．61．v-r不可分区域我们以分三类为例，对一对一方法中的多数投票法和不可分区域进行简单的分析。K设：nt，汪l⋯K代表多分类问题中每类的样本数，甩；i=ni+疗i，N=∑ni，VJ』_t=l助表示子分类器C：f，的分类准确率，当K--3时，一对一方法需构造七(后一1)／2=3个子分类器，采用多数投票法决策，则每个样本得两票才能正确分类，此时，整体分类准确率的上界和下界为：3上界：UB=∑％Po／2N(5-7)62 第五章基于支持向量机的多分类问题研究TYe：LB=瞧％岛-N]+／Ni,i．j侉8，：I∑％岛l(5·8)Lj，户j+其中【“】+={：；ffuu≤>吕若各子分类器的分类准确率相同，即助=p，i≠，，f，J=l，2，3则，式(5—7)、(5—8)简化为：下界：LB=[2p-1]．，上界：UB2P。由式(5．7)，(5．8)可知相应的不可分样本的上下界是：3不可分样本的上界：FUB=∑％岛／N-2LB(5-9)j，j=l，j≠．，3不可分样本的下界：FLB=∑嘞岛／Ⅳ一2咖=o(5-lo)f，j=l,i≠j设分3类，每个子分类器的准确率相同，则整体分类准确率与不可分区域的上界如图5．7所示：子分类器准确率粕图5．7卜v-1整体分类准确率与不可分区域由以上的分析我们可知，在各个子分类器准确率相同时，一对一方法的整体准确率不会超过单个子分类器的准确率，不可分区域的大小与分类器的准确率有很大关系，实验中我们还发现，不可分区域的大小与核函数的参数和惩罚系数都有很大的关系。实际上，式(5—9)给出的上界是很宽的，实际应用中如果各个子分类器的准确率都比较高，则可大大降低不可分样本的数目。 基于支持向量机的若干分类问题研究5．3．2模糊支持向量机文‘113】【1141介绍了两种分别解决一对一和一对多多分类问题中不可分区域的方法，文H151在其基础上进行了改进，我们以一对一方法为例，简单介绍如下：设采用一对一方法对一个k类问题，建立类i与类j的最优分类超平面是：乃(x)=(We‘x)+％(5—11)石(x)=一厶(x)，对输入向量x计算Z(x)=∑s劬饥(x))(5-12)黼唰加器拦采用多数投票法：x的类别量arg啦蝉Z(x)(5—13)I=i⋯．丘在图5．5的不可分区域Z(x)=1(汪l，2，3)，即每类都是一票。文【1151引入两种隶属度函数竹(x)=min(1,j,,艇8．^‘(x))(5-14)和mr(加吉，善。％o)(5-15)卜石(x)≥1其中：mo(x)={乃(x)一1<石(x)<1【一lAj(x)≤一1对不可分区域的样本，将式(5．13)改写为：x的类别兰argm样％(x)(5-16)tffil⋯．七此时图5．5中不可分区域成为图5．8中的可分区域。 第五章基于支持向量机的多分类问题研究O图5．8FsvM分类结果xl这种模糊支持向量机方法可以对不可分区域的样本给出一个合理的决策，不过，在实际应用中还可能存在以下几个问题：1．当X点的隶属度函数佩(x)在几个类别上取相同的最大值时X仍然是不可分的；2．在决策函数值Z(x)相差不是很大时，其推断结果也已很不可信；5．3．3基于决策间隔的多分类模糊输出支持向量机由以上的分析我们知道，不可分区域的存在影响了分类器的泛化能力，而在一些实际问题中这些不可分样本却是我们要特别关注的。以医疗诊断为例，一个就医者身体的各项指标介于健康与患病之间，这时我们不能强行采用明确分类的方法对其做出判断，否则，误分为健康人则可能耽误病情的治疗，误分为病人，则可能带来治疗的负作用，这时应当采取保守治疗的方法，不是立即做出判断而是通过一段观察再进行判断。从求解分类问题的角度来看，解决上述问题的一个可行的方法是：根据问题的需要给定一个阈值，对待分类的数据给出其分类标识的同时给出一个分类置信度，对分类置信度大于阈值的数据可直接决定其类别，对分类置信度小于给定阈值的数据可采用其它的方法进一步分类。目前已有的以置信度分类的方法基本上都是单独考虑各决策值的置信度，本节提出一种新的基于决策间隔的模糊输出支持向量机(FuzzyOutputSVM，FOSⅧ)，可以解决上述的问题1和问题2。分别以一对多和一对一方法为例，具体描述如下：65 基于支持向量机的若干分类问题研究(1)基于决策间隔的一对多模糊输出支持向量机一对多方法中，求解如下的k个子分类问题：⋯min，扪12+c[圭i=1等】(w，‘xj)+6J一1+孝f≥0，／f弗=J(5．17)(w，·xi)+6Jf—l+孝f≤0，／f乃≠J彰≥0，i=l一』，得到k个决策函数六(x)，此时不用下式x的类别兰argmax闰如．k乃(x)(5·18)作为决策函数，我们定义一个决策间隔函数：定义5．2(决策间隔)分解多分类问题中各决策函数厂(x)中最大值和次大值之差称为决策间隔，公式表示如下：DM(x)2mHa⋯x。l乃(x)。孵fj(x)(5-19)其中：m=Laxklfj(x)表示决策值中的最大者，max7fj(x)表示决策值中的次大者。引入一个隶属度函数：∥(x)2再≯丽1(5-20)其中DM(x)是决策间隔，A，C是可调参数，则此时分类器的最终输出为：x的类别：arg∥max，．．fj(x)if∥(x)>9(5—21)【refuseif∥@)≤00是根据实际问题的需要设定的阈值，如果决策间隔小于阈值则拒识此样本。接下来我们以分三类为例对该方法进行讨论，首先我们分析一下决策边界： 第五章基于支持向量机的多分类问题研究。图5．9l-v-r不同分类区域xl由图5．9我们可以看出，整个特征空I司被分类超平面划分成三类区域：1．完全可分区域：罂孵乃(x)‘翠孵乃(x)≥2；2·基本可分区域：万AA>A>B>C’’。此外，在医学领域也有大量的有序分类问题，如：临床中的疗效评价，结果为“无效、好转、显效，治愈"，流行病学中有一些慢性病的危险因素研究，有时疾病需按其严重程度进行分类，观察结果可能是“无、轻、中、重"等。相对有序分类问题而言，无序分类问题中，其标识可用数值表示是第几类，但此数值无排序意义，仅仅是一个代号，如手写体数字识别，人脸识别，植物种类分类等。目前机器学习领域中大部分多分类算法都是将有序和无序分类问题同等对待，即假定分类变量是无序的，这样虽然是可行的，却忽略了问题本身所具有的“序’’的信息。本章首先从函数集容量的角度，对有序分类和无序分类问题的复杂度进行比较，然后介绍了现有的几种有序分类方法，并充分利用样本具有的自然序的特性提出一种改进的内嵌空间算法，最后将其应用在实际有序分类问题中，通过实验比较说明本章提出的方法的有效性。6．2有序分类与无序分类问题复杂度比较6．2．1问题的表示设大小为，的训练样本集S={(五，y0，(而，儿)，．．．，(而，M))，t∈X，咒∈Y其中X是n维特征向量x∈R”，Y是样本对应的等级，Y_{l，2，3，．．．，K>，其中K表示最71 基于支持向量机的若干分类问题研究大等级。与无序问题不同的是，这里的儿不仅仅是一个标号，还表明了在实际问题中样本具有某种特性的程度(如企业或个人信用的高低，对某事物的喜爱程度等)，如果一个样本的标号为k，则它具有比样本标号为l，2，⋯k-l高的特性，而比样本标号为k+1，k+2，⋯K低的特性，一般的多分类问题中不具有这种“序"的特性。我们的任务是根据给定的训练样本集S，训练一个分类器．厂，对未知标号的任意一个样本X，预测其对应的等级。即：实现。厂：X专Y。假设6．1在特征空间中存在这样的“坐标轴”：特征空间中的点投影到该“坐标轴"的相对位置能标识该点的等级。设h为特征空间X中的某一超平面，特征空间中的数据点X到h的算术距离(SignedDistance)为hrx，则在此特征空间中，由假设6．1，样本点之间的有序信息可用hrX表示(如图6．1)。为判定数据X的等级，还需K．1个阈值幺<岛<⋯<最一。，将分级器记为(办，q，岛，．．．，嚷一。)，其分级规则为：f1厂(x)={iiflKLifhrx<岛包一l≤hrx<包i≠1，K(6—1)／fhrx≥oK—l图6．1有序分类示意图这就是有序分类问题。需要说明的一点是，有序分类问题与排序问题(Sorting)不同，排序问题要求能将所有的样本点按某种规则排成一个序列，一个样本就代表了一个等级，其输出值K的取值个数与样本个数相同，而有序分类问题中，输出值K一般少于样本的个数，一个等级中可能包含若干个样本。6．2．2复杂度比较文【117】从算法的角度出发，讨论了有序与无序分类问题的复杂度，并指出相对无序分类问题而言，有序分类问题在求解上更复杂。本文将从函数集容量的72 第六章有序分类角度出发，讨论有序与无序分类问题的复杂度。从统计学习理论中我们知道VC维能够表征函数集的容量或学习机器的复杂程度，而一个函数集或学习机器的VC维是指：该函数集或学习机器能够以任意方式打散的最大样本点的个数。类似VC维的定义，我们提出如下的分级维：定义6．1对分级问题，一个函数集或学习机器能够以任意方式分成若干等级的最大样本点的个数称为该函数集的分级维。如：一个函数集的分级维是3，则它最多可将一个分级问题中的3个样本点以任意形式分级，即最多可将三个样本点xl，x2，x3的等级分为(rankl，rank2，rank3)，(rankl，rank3，rank2)，(rank2，rankl，rank3)，(rank2，rank3，rankl)，(rank3，rankl，rank2)或(rank3，rank2，rankl)@的任意一种形式。定理6．1一个线性函数集的分级维等于它的VC维。证明：不失一般性，我们假设所讨论的特征空间是n维实域空间，即特征向量x∈R”，则对任意的两点鼍，x，∈R”，满足薯-xj∈R”。对，个样本点S={Xl，x2，．．．，而)，其对应的等级为：锄，鸬，．．．乃)。假设存在某一函数集厂能将S中的m个点以任意方式分级，则他可将这m个点以任意方式打散。考虑一个子集，SocS，标识&中的样本点为正类，属于S但不属于So(S＼So)的样本点为负类。此时，只要我们将品中的样本点分成比S＼&中样本点低的级别，这样就可以按照由等级确定的阈值将＆分为正类，而将S＼瓯分为负类。即，任意一个函数集的分级维，不会超过它的VC维。另一方面，我们知道n维空间只”中的线性分类器的VC维是n+l，给定n+1个样本点的任意一个排序，重新标号样本点，使得rank(x1)Oj乃r誓>hrxj_l，这表示样本点到超平面的距离，根据假设6．1我们知道它给出了样本点的等级。这样n维空间的任意n+1个点都能够被一个线性分类器以任意方式分级，即，任意一个线性函数集的VC维，不会超过它的分级维。综合以上分析我们可以得出：一个线性函数集的分级维等于它的VC维。由定理6．1我们很容易得出如下的推论：推论6．1n维空间线性函数集的分级维等于n+l。以上我们从函数集容量的角度对分级问题的复杂度进行了分析，说明分级问题与普通多分类问题的假设空间的复杂度是一样的。如何将这一点利用到有序分类问题中是一个有待继续研究的内容。6．3基于支持向量机的内嵌空间法6．3．1现有有序分类算法目前，对于有序分类问题，一般采用的方法是当作无序问题求解，如本文第五章介绍的多分类方法中的两分类组合或一次性求解等方法，或采用有序回归的方法【118】【1191。前者就是普通的多分类方法，用多分类方法求解有序问题虽然是可行的，但却忽略了问题本身所具有的序的结构，没有充分利用数据隐含的信息，后者对于有序分类和排序问题都是可行的但求解相对比较麻烦。除了以上的两种方法外，许多学者利用有序分类问题的特点，提出一些新的有序分类方法，其中比较有代表性的有AmnonShashua和AnatLevin[1201提出的两种基于最大间隔的有序分类方法：“固定间隔策略(fixedmarginstrategy)”与“和间隔策略(sumofmarginstrategy)”，这两种方法可以一次求解分级问题，但由于需要求解一个复杂的二次规划方程，实现起来比较困难；C．Burges提出一种用于分级的梯度下降法【12l】；文【1221介绍了一种通过重构训练集使分级问题转化为一个两分类问题的方法，不过由于重构的训练集数量太大达到oq2)，一般的学习算法的计算复杂度依赖于训练集的大小，而难于处理；Shyamsundar12Rajaram等人用新的方法构造上述数据集使其减小到D(刁1-【1231，不过，当K较小74 第六章有序分类时，这种方法的计算复杂度仍然很大，此外，ShyamsundarRa6a均m等人提出了一种将有序分类问题转化为两分类问题的内嵌空间法，本节结合支持向量机技术，通过对核函数的修改，提出一种改进的内嵌空间法，进一步提高有序分类支持向量机的泛化能力。6．3．2内嵌空间法(EmbeddedSpaceApproach)由式(6-1)我们知道，分级器用K．1个平行的超平面将特征空间分为K部分。点x到h的距离被映射到一维空间，阈值q，岛，⋯，＆-．用来与该距离比较；对等级为i的任意点x，办k在点包一。和2之间(设岛=娟，艮=oo)，令％=谚-e,一l，1≤i≤K-1，显然有q>0。．．．．．．．}聃．．．．．．．．．．．．．．．—{10102030K．20K．1图6．2内嵌空间法示意图等级为f(f>1)的样本点呀满足：hrxj>2一l；hrxj-I-OCi—l>包；而等级为i(f瓯H∑一+0矿 基于支持向量机的若干分类问题研究j■【，】l≤，≤刀xj[1】={0刀<，o且矿xj，由于矽(x)是非线性映射，存在这样的问题：对等级为i的样本t有矿荔>oj办rx／>谚一。，但对于一般的核函数K(fi，弓)=≯(万)r·cW)>o并不一定保证矽(办)r·矽(_)>谚一。从而得不到所需的分级规则。为了解决这个问题，定义映射：歹：歹(习=【≯(x)，x-[n+1：刀+K一211；歹(万)=[矽(办)，万m+1：n+K一2】】(6．6)万只将变元的前n维(即X和h)映射到高维空间，而保持变元的后K．2维不变；通过这样的歹可进一步定义核函数：K：K(葛，弓)=K(t，■)+亏印+l：”+K一2】7L[n+l：n+K一2】(6-7)也就是说，霞是两个核函数之和，前一项K(薯，x，)为特征向量i前n维的76 第六章有序分类核，后一项是葛与i，的后K-2维的线性核。为了进一步提高样本点在特征空间的可分性，我们采用第四章介绍的方法，利用一个保角变换对核函数进行修改，增大特征空间的分级边界区域，此时需做如下的保角变换：K’(‘，■)=d(薯)d(■)K(薯，■)(6-8)其中荆是一个正纯量函数。与第四章中的保角变换不同的是，此时，我们需要在保证特征空间中包含所有训练样本点的超球半径较小的情况下，放大所有分界面周围的区域，即增大各等级间的分类间隔。因此荆可取如下的形式：d(X)=∑e慨。2／2r(6-9)iESV’其中f是一大于零的常数，SV’是所有的支持向量中满足II矽(％矿)-ao112≤秒