支持向量机性能分析及改进.doc

烟台大学毕业论文（设计）1 绪论1.1 课题背景当今随着信息技术和信息网络的飞速发展，信息产生和传播的速度迅速提高，各种各样的机构每天都在产生并积累着大批量的数据。伴随海量数据而来的问题是信息过载和信息污染，这极大地影响了人们对信息的有效利用，因此，从大量数据中发现有用知识的数据挖掘(Data Mining)，就成为一个十分迫切的富有挑战性的研究课题。基于数据的机器学习(Machine Learning)是数据挖掘技术中的重要内容，机器学习研究从观测数据出发寻找规律，利用这些规律对未来数据或无法观测的数据进行预测。其重要理论基础之一是统计学。传统统计学研究的是样本数目趋于无穷大时的渐近理论，但在实际问题中，样本数往往是有限的，因此一些理论上很优秀的学习方法在实际中的表现却可能不尽人意。令人激动的是，上述困难随着统计学习理论(Statistical Learning Theory，简记SLT)及在此基础上发展起来的支持向量机(Support Vector Machine，简记SVM)技术在实际问题中的广泛应用而逐步得到了缓解。统计学习理论(Statistical Learn-ing Theory SLT)，专门研究实际应用中有限样本情况的机器学习规律，并发展了支持向量机(Support Vector Machine SVM)这一新的通用学习方法，由于它基于结构风险最小化(SRM)原理，而不是传统统计学的经验风险最小化(ERM)，表现出很多优于已有方法的性能，迅速引起各领域的注意和研究兴趣，取得了大量的应用研究成果，推动了各领域的发展。支持向量机结构简单，并且具有全局最优性和较好的泛化能力，自20世纪90年代提出以来得到了广泛的研究。支持向量机方法是求解模式识别和函数估计的有效工具。汉字识别一直是模式识别最重要的研究领域之一。针对汉字的结构特点，许多学者分别从预处理和特征提取的角度提出了许多方法。从预处理的角度，通过对汉字点阵采取某种非线性变换，矫正手写汉字变形，以减少类内方差。从特征提取的角度，利用汉字固有的笔划构成特征提取手写汉字的笔划以及笔段信息。但是，由于汉字的结构复杂性，以及不同人书写变形的不确定性，到目前为止，手写汉字的识别性能仍然不能令人满意。神经网络由于其较强的曲线拟合和模式分类能力，在汉字识别中得到广泛的应用。经过多年的研究，已经取得了大量成果。但对区分手写得非常近似的汉字,仍然缺乏有效的手段。采用汉字笔画及字型信息的特征,即多特征的方法,可以用于相似字的识别,但效果不能令人满意。人工神经网络的方法在小规模分类中是比较有效的,但人工神经网络学习算法有其固有的缺点,如网络结构的确定尚无可靠的规则, 算法的收敛速度较慢，且无法保证收敛到全局最优点。支持向量机则在一定程度上解决了神经网络的问题，它建立在牢固的数学基础之上，其通过核函数及最优化方法，最终将算法转化为一个二次凸函数求极值问题，从理论上说得到必将是全局最优点，用支持向量机解决手写体相似字识别问题的方法,已经取得较好的效果。本文提出了一种通过修正核函数来提高支持向量机分类性能的方法，其思想是尽量放大分离曲面附近的局部区域，而保持其他区域变化不大（因为高斯核的图形是类似于钟形曲线的）。考虑到支持向量几乎总是出现在分离曲面附近，故设法放大支持向量的局部区域，通过将原来的样本点映射到一个高维空间，以拉大分类间隔的距离，从而达到提高其分类性能的目的。1.2支持向量机的概述1.2.1 支持向量机的研究背景和意义 (1)支持向量机的研究背景基于传统的统计学的机器学习方法，理论体系非常完善，但其在解决基于有限样本的实际问题时的性能往往不能令人满意。前苏联学者Vladimir N.Vapnik等人研究基于有限样本情况下的机器学习问题，形成了一个较完善的理论体系统计学习理论。同时，神经网络等一些较新型的基于传统的统计学的机器学习方法的研究则遇到了很大的困难，如过学习与欠学习问题、如何确定网络结构的问题、局部极小点问题等等。因此这种能从更深层次上描述、解决有限样本情况下的机器学习问题的统计学习理论逐步受到广大研究者的重视。20世纪90年代中期，Vaphik和他领导的AT&T Bell实验室小组提出了基于统计学习理论和结构风险最小化的SVM算法，进一步丰富和发展了统计学习理论，使它不仅是一种理论分析工具，还是一种可以构造具有多维预测功能的预测学习算法的工具，使抽象的学习理论能够转化为通用的容易实现的预测算法。 (2)支持向量机研究的意义支持向量机是在统计学习理论基础上发展起来的一种新型机器学习方法。由于具有以下主要优点而被广泛关注:基础是统计学习理论，针对有限集样本，而不是样本集数目趋于无穷大，更具有实际应用价值；将学习问题归结为一个凸二次规划问题，从理论上说，得到的将是全局最优解，解决了在神经网络方法中无法避免的局部极值问题；通过非线性变换将数据映射到高维特征空间，使数据在高维空间中可以用线性判别函数分类，巧妙地解决了维数问题，算法复杂度与样本维数无关。支持向量机建立在严格的理论基础之上，较好地解决了非线性、高维数、局部极小点等问题，成为继神经网络研究之后机器学习领域新的研究热点。支持向量机从提出、被广泛重视到现在只有很短的时间，其中还有很多尚未解决或尚未充分解决的问题，在应用方面还具有很大的潜力。因此，支持向量机是一个十分值得大力研究的领域。 1.2.2 支持向量机的基本思想从观测数据中学习归纳出系统运动规律，并利用这些规律对未来数据或无法观测到的数据进行预测一直是智能系统研究的重点。传统学习方法中采用的经验风险最小化准则(empirical risk minimization, ERM)虽然可以使训练误差最小化，但并不能最小化学习过程的泛化误差。ERM不成功的例子就是神经网络的过学习问题。为此,Vapnik提出了结构风险最小化准则( structural risk minimization, SRM)，通俗地说就是通过对推广误差(风险)上界的最小化达到最大的泛化能力。Vapnik提出的支持向量机( support vector machine, SVM) 就是这种思想的具体实现。支持向量机的基本思想是在样本空间或特征空间，构造出最优超平面，使得超平面与不同类样本集之间的距离最大，从而达到最大的泛化能力。1.2.3 支持向量机的应用研究现状模式分类是模式识别中的一项重要内容，分类也是人们认识一切事物的基础，许多优秀的学习算法都是以分类为基础发展起来的8。SVM方法在理论上具有突出的优势，贝尔实验室率先对美国邮政手写数字库识别研究方面应用了SVM方法，取得了较大的成功。在近几年内，有关SVM的应用研究得到了很多领域的学者的重视，在人脸检测、验证和识别、说话人/语音识别、文字手写体识别、图像处理、及其他应用研究等/方面取得了大量的研究成果，从最初的简单模式输入的直接SVM方法研究，进入到多种方法取长补短的联合应用研究，对SVM方法也有了很多改进。1.2.4 支持向量机的研究热点 由于支持向量机坚实的理论基础和它在很多领域表现出的良好的推广性能，目前，国际上正在广泛开展对支持向量机方法的研究。许多关于SVM方法的研究，包括算法本身的改进和算法的实际应用，都陆续提了出来。以下是其中主要的研究热点。 （1）改进训练算法由于SVM对偶问题的求解过程相当于解一个线性约束的二项规划问题(QP)，需要计算和存储核函数矩阵，其大小与训练样本数的平方相关，因此，随着样本数目的增多，所需要的内存也就增大，例如，当样本数目超过4000时，存储核函数矩阵需要多达128M内存；其次，SVM 在二次型寻优过程中要进行大量的矩阵运算，多数情况下，寻优算法是占用算法时间的主要部分。通常，训练算法改进的思路是把要求解的问题分成许多子问题，然后通过反复求解子问题来求得最终的解，方法有以下几种： 块处理算法(chunking algorithm) 它的思想是将样本集分成工作样本集和测试样本集，每次对工作样本集利用二项规划求得最优解，剔除其中的非支持向量，并用训练结果对剩余样本进行检验，将不符合训练结果(一般是指违反KKT条件)的样本(或其中的一部分)与本次结果的支持向量合并，成为一个新的工作样本集，然后重新训练。如此重复下去，直到获得最优结果。其依据是去掉Lagrange 乘子等于零的训练样本不会影响原问题的解。块算法的一个前提是：支持向量的数目比较少。然而如果支持向量的数目本身就比较多，那么随着训练迭代次数的增加，工作样本数也越来越大，就会导致算法无法实施。 固定工作样本集算法 它使样本数目固定在足以包含所有的支持向量，且算法速度在计算机可以容忍的限度内。迭代过程中只是将剩余样本中部分“情况最糟的样本”与工作样本集中的样本进行等量交换。即使支持向量的个数超过工作样本集的大小，也不改变工作样本集的规模。有一种具体的算法，将样本集分为B和N两个集合，集合B作为子问题的工作样本集进行SVM训练，集合N中所有样本的Lagrange乘子均置为零。显然，如果把集合B中，对应Lagrange乘子为零的样本i(即= 0，i B)与集合N中的样本j(即 =0, j N)交换，不会改变子问题与原问题的可行性(即仍旧满足约束条件)。于是可以按照以下步骤迭代求解：选择集合B，构造子问题；求子问题最优解，i B及b，并置 = 0 ，j N；计算g( x) y，j N，找出其中g (x) y 1 的样本j，( 其中g (x) = )，与B中满足= 0的样本 i 交换，构成新的子问题。需要指出：如果集合B不足以包括所有的支持向量，该算法没有提出改变B的大小的策略，那么有可能得不到结果。 SMO 算法 SMO 是固定工作样本集算法的一个极端情况，其工作样本数目为2。需要两个样本，是因为等式线性约束的存在使得同时至少有两个Lagrange乘子发生变化。由于只有两个变量，而且应用等式约束可以将其中一个用另一个表示出来，所以迭代过程中，每一步子问题的最优解都可以直接用解析的方法求出来，这样，算法就避开了复杂的数值求解优化问题的过程；此外，算法还设计了一个两层嵌套循环，分别选择进入工作样本集的样本，这种启发式策略大大加快了算法的收敛速度。标准样本集的实验结果证明，SMO在速度方面表现出良好性能。 （2）提高测试速度SVM 判决函数的计算量和支持向量的数目成正比。对于大训练集合，其支持向量的数目会达到几千个，这就使SVM对实验样本的测试判决速度变慢，因此，提高SVM 的测试速度是另一个研究热点。对所有N个支持向量求和，计算量很大，如果可以减少求和的数目，使其达到M (M N)个，则可以大大提高速度。判决函数d(x)的近似式如下：d(x) = (1.1)据此，Osuna 提出3 种方案： 对d(x)在特征空间中进行拟合，得到一个近似的判决函数d(x) ：d(x) = (1.2)其中， N，是特征空间中的合成向量，不一定是样本点， 是权重。 判决函数d(x)在特征空间中近似为d(x)= (1.3)其中， N， 是与支持向量对应的权重。 对原问题重新定义，得到新的判决函数为d(x) = (1.4)其中， N，是某些训练样本点，但不一定是支持向量，是权重，是样本点的类别标号。其中，第1个方案已经被Burges论证，并实现，其基本思想是：在SVM的高维特征空间中，运用比原来少得多的精简集合(Reduced Set ，RS)向量来拟合原来所有SV所构成的分界超平面，可以在损失极少信息的基础上，大大提高测试速度。 （3）核函数的构造、修正以及相应参数的调整前面提到，核函数的选取对支持向量机的性能起着非常关键的作用。而核函数可以人为地选取，只要其满足mercer条件。因此，如何构造一个新的性能较好的核函数、如何修正已有的核函数使其性能提高便成了一个被广泛研究的热点。本设计研究的就是修正核函数问题，这在后面的部分有详细的论述。 SVM的核函数有多项式核函数、径向基函数等。尽管一些实验结果表明核函数的具体形式对分类效果的影响不大，但是核函数的形式以及其参数的确决定了分类器的类型和复杂程度，它显然应该作为控制分类器性能的手段。最常用的模型参数选择方法是最小化“留一法(LOO)”错误率。其步骤是： 对于j = 1，2，个训练样本，每次取出其中一个样本 i，而对其余的- 1个训练样本求解式 (1.5) 对- 1个样本的训练结果，采用式 (1.6) 对第 i 个样本进行测试 反复重复上述步骤。LOO 的错误率是 L()=1- (1.7)可以看出，用LOO估计错误率的方法来调整参数需要的训练量很大，因此有人提出用估计错误率上限的方法来调整SVM的参数。有人提出了几种估计错误率上限的方法，其中有逐个确认估计、留一法上限估计、用支持向量数与训练样本数的比值估计上限、Jaakkola- Haussler上限、Opper- Winther上限、Radius- margin上限、Span上限。同时，还实现了根据错误率上限的估计来调整SVM参数的算法，其具体思路是：初始化SVM的核函数参数，求解式(2.38)，后利用求得的结果估计错误率上限，再利用对错误率上限的梯度下降法调整核函数参数，反复执行上述步骤，直到得到最小的错误率上限。 Chapelle等人于2000年使用基于矩阵的二项规划方法实现了利用LOO上限来调整SVM参数的方法。应当指出的是，即使对于只有几千个样本的中型问题，也很难在内存中容下整个核函数矩阵，并进行相应的矩阵操作，这种方法有时会带来问题，因此，应当找到一种合适的迭代策略来解决这个问题。 （4） 利用SVM解决多分类的问题由于支持向量机是针对两分类问题提出的，因此，存在一个如何将其推广到多分类问题上，特别是对极大类别分类的问题上。目前有以下几种方案：(1) 一对多(One class Versus all Others , OVO) 其基本想法是把某一种类别的样本当作一个类别，剩余其他类别的样本当作另一个类别，这样就变成了一个两分类问题。这种分类方案的缺点是训练样本数目大。训练困难。(2 ) 一对一(One class Versus Another class , OVA) 其做法是在多类别中，任意抽取两类进行两两配对，转化成两类问题进行训练学习。识别时，对所构成的多个SVM进行综合判断，一般可采用投票方式来完成多类识别。这种分类方案存在一个明显的缺点，就是子分类器过多，测试时需要对每两类都进行比较，导致测试速度慢。DAG方案在训练阶段也是采用一对一的配对训练方式，它的优点在于，对训练结果的推广性进行了分析，另外，它的测试速度也比一对一的方案要快。(3) SVM 决策树(Decision Tree Method , DTM) 它通常和二叉决策树结合起来，构成多类别的识别器。这种方法的缺点是如果在某个节点上发生了分类错误，将会把错误延续下去，该节点后续下一级节点上的分类就失去了意义。另外，SVM的研究点还有如何把SVM中的核函数内积思想应用到其他方面。Scholkopf 等学者首先把核函数的概念引入到PCA中，用核函数实现非线性主元分析，它是传统主元分析(Principal Component Analysis , PCA)方法的推广。对经典的SVM算法的改进也是一个研究点。Scholkopf 提出了一类新的支持向量算法，它运用参数来控制支持向量的数目及误差，使新的- SVR 回归算法更加实用，并把- SVR 的思想运用到了- SV 的分类问题中。他还提出了SVR的一种新算法，从- SVR 到- SVR，具有更好的适应性及鲁棒性。此外，有人研究如何处理样本集合中的一些特殊点或远点，尤其是样本集中的一些离散点，进一步提高SVM识别器的泛化能力。1.2.4 支持向量机的未来发展方向当前，对支持向量机的研究方兴未艾，总的来说，主要围绕两个方面：一是通过对支持向量机本身性质的研究，提出进一步完善的措施，此外还包括多类识别问题和快速训练算法等。二是不断探索新的应用领域，支持向量机本质上是一种非线性数据处理工具，人们注意到它在数字信号处理、图象处理、智能控制等领域有巨大的应用潜力，这方面已经有了一些结果，如基于核的主成分分析、非线性去噪、非线性模式重建以及数据挖掘等。遗憾的是，虽然支持向量机在理论上有很突出的优势，但与其理论研究相比，应用研究尚相对比较滞后，目前只有比较有限的实验研究报道，且多属仿真和对比实验。支持向量机的应用研究应该是一个大有作为的方向。我们相信支持向量机是一个值得大力研究的领域，对它的研究将对机器学习等学科领域产生重要影响。2 支持向量机的基本理论 2.1 基本概念2.1.1 机器学习问题的表示 机器学习的目的是根据给定的训练样本求对某系统输入输出之间依赖关系的估计，使它能够对未知输出作出尽可能准确的预测。可以一般地表示为：变量y 与x 存在一定的未知依赖关系，即遵循某一未知的联合概率 F(x,y)，(x 和y 之间的确定性关系可以看作是其特例)，机器学习问题就是根据 n 个独立同分布观测样本(x1, y1) , (x2, y2) , ., (xn, yn) , (2.1)在一组函数 f (x ,w ) 中求一个最优的函数f (x ,w 0) 对依赖关系进行估计，使期望风险R (w ) =L(y,f(x ,w )dF (x,y) (2.2)最小。其中， f (x ,w ) 称作预测函数集，w 为函数的广义参数， f (x ,w ) 可以表示任何函数集；L (y , f (x ,w ) ) 为由于用f (x ,w ) 对y 进行预测而造成的损失，不同类型的学习问题有不同形式的损失函数。预测函数也称作学习函数、学习模型或学习机器。有三类基本的机器学习问题，即模式识别、函数逼近和概率密度估计。我们这里只考虑模式识别，对模式识别问题输出 y 是类别标号，两类情况下 y = 0, 1或1, - 1，预测函数称作指示函数，损失函数可以定义为 0, if y = f (x,w ) ,L (y , f (x,w ) ) = （2.3） 1, if y f (x,w ) ,使风险最小就是Bayes决策中使错误率最小。2.1.2 经验风险最小化在上面的问题表述中，学习的目标在于使期望风险最小化，但是，由于我们可以利用的信息只有样本(3.1)，(3.2)式的期望风险并无法计算，因此传统的学习方法中采用了所谓经验风险最小化(ERM)准则，即用样本定义经验风险R (w ) =, (2.4)作为对(2.2)式的估计，设计学习算法使它最小化。事实上，用ERM准则代替期望风险最小化并没有经过充分的理论论证，只是直观上合理的想当然做法，但这种思想却在多年的机器学习方法研究中占据了主要地位。人们多年来将大部分注意力集中到如何更好地最小化经验风险上，而实际上，即使可以假定当 n 趋向于无穷大时(2.3)式趋近于(2.2)式,，在很多问题中的样本数目也离无穷大相去甚远。 那么在有限样本下ERM准则得到的结果能使真实风险也较小吗？2.1.3 VC 维 为了研究学习过程一致收敛的速度和推广性，统计学习理论定义了一系列有关函数集学习性能的指标，其中最重要的是VC维(Vapnik- Chervonenkis Dimension)。模式识别方法中VC维的直观定义是：对一个指示函数集，如果存在h个样本能够被函数集中的函数按所有可能的种形式分开，则称函数集能够把h个样本打散；函数集的VC 维就是它能打散的最大样本数目h。若对任意数目的样本都有函数能将它们打散，则函数集的VC维是无穷大。 有界实函数的VC维可以通过用一定的阈值将它转化成指示函数来定义。VC维反映了函数集的学习能力，VC维越大则学习机器越复杂(容量越大)。遗憾的是， 目前尚没有通用的关于任意函数集VC维计算的理论，只对一些特殊的函数集知道其VC维。比如在 n 维实数空间中线性分类器和线性实函数的VC维是 n+1，对于一些比较复杂的学习机器(如神经网络)，其VC维除了与函数集(神经网结构)有关外，还受学习算法等的影响，其确定更加困难。对于给定的学习函数集，如何(用理论或实验的方法)计算其VC维是当前统计学习理论中有待研究的一个问题。2.1.4 结构风险最小化由于可以利用的信息只有有限样本，无法计算期望风险，因此传统的学习方法中采用了所谓经验风险最小化准则，即用样本定义经验(Empirical Risk Minimization ERM)风险： （2.5）统计学习理论系统地研究了各种类型的函数集，经验风险和实际风险之间的关系，即推广性的界。关于两类分类问题的结论是：对指示函数（即两类分类情况的预测函数）集中的所有函数，经验风险Remp(w)和实际风险之间以至少1-的概率满足如下关系： （2.6）其中h是函数集的VC维，表征了复杂性高低； n是样本数。这一结论从理论上说明了学习机器的实际风险是由两部分组成的：一是经验风险训练误差，另一部分称作置信范围，它和学习机器的复杂性及训练样本数有关。置信范围反映了真实风险和经验风险差值的上确界，反映了结构复杂所带来的风险，它和学习机器的VC维h及训练样本数l有关8。它表明，在有限训练样本下，学习机器的VC维越高复杂性越高则置信范围越大，导致真实风险与经验风险之间可能的差别越大。这就是为什么会出现过学习现象的原因。机器学习过程不但要使经验风险最小，还要使VC维尽量小以缩小置信范围，才能取得较小的实际风险。这种思想称作结构风险最小化(Structural Risk Minimization，SRM)即SRM准则2.1.5 最优超平面设给定训练数据为 ( x1 , y1) ,( x2 , y2) ,. . . , ( xl , yl) ,其中 x R , y - 1, + 1 ,又若 n 维空间中的线性判别函数一般形式为:g( x) = ( wx) + b,且集合中的所有数据都可以被分类面( wx) + b = 0 所正确划分,并且距平面最近的样本数据与平面之间的距离最大，则该分类面就是最优超平面。而距离该最优超平面最近的异类向量就是所谓的支持向量(Support Vecter) ,支持向量与超平面之间的距离最大(即边缘最大化) ,一组支持向量可以唯一的确定一个超平面。如图所示：图 2.1 小间隔超平面图 2.2 大间隔超平面图2.1和2.2中,实心点和空心点代表两类样本,H为分类超平面,而只有（b）中的超平面才是最优超平面，因为它更远离每一类,（a）中的平面，数据集中的较小改变将导致错误分类结果，所以不是一个好的分类面。因此，为了求得最优分类面，不但要考虑分类误差最小，还要同时考虑分类面的结构。支持向量机通过引入结构风险函数恰恰能完成这个任务，从而提高了机器学习一的泛化能力。H1,H2 分别为过各类中离分类超平面最近的样本且平行于分类超平面的直线,它们之间的距离叫做分类间隔(Margin)。由于支持向量与超平面之间的距离为1/|w|,则支持向量间距为2/|w|（不同类别的最小距离）,寻找超平面问题,可转化为求解以下二次规划问题:( w) =1/2 ( w w) (a) 约束条件为不等式 : yi( wxi) + b 1 ，i =1,2, , L (b) 对一个规范超平面子集,其 VC维 h 满足不等式:h min( R A + b, n) +1 (c)式中 n 为向量空间的维数, R 为覆盖所有向量的超半球半径,由式(c)可以得到,通过最小化|w|可使VC置信度最小,若固定经验风险,则最小化期望风险的问题就是最小化|w|的问题,此即SVM算法的理论出发点。2.1.6 复杂性与推广能力开始，很多注意力都集中在如何使R (w ) 更小，但很快就发现，训练误差小并不总能导致好的预测效果。某些情况下，训练误差过小反而会导致推广能力的下降，即真实风险的增加，这就是过学习问题。ERM 准则不成功的一个例子是神经网络的过学习问题过学习现象， 一是因为样本不充分， 二是学习机器设计不合理，这两个问题是互相关联的。设想一个简单的例子，假设有一组实数样本 x ，y ， y 取值在 0, 1 之间，那么不论样本是依据什么模型产生的，只要用函数 f (x ，a) = sin (ax )去拟合它们(a是待定参数)，总能够找到一个a使训练误差为零，但显然得到的“最优”函数并不能正确代表真实的函数模型。究其原因，是试图用一个十分复杂的模型去拟合有限的样本，导致丧失了推广能力。在神经网络中，若对有限的样本来说网络学习能力过强，足以记住每个样本，此时经验风险很快就可以收敛到很小甚至零，但却根本无法保证它对未来样本能给出好的预测。学习机器的复杂性与推广性之间的这种矛盾同样可以在其它学习方法中看到。在有噪声条件下用模型y = x 2产生10个样本，分别用一个一次函数和一个二次函数根据ERM原则去拟合，结果显示，虽然真实模型是二次，但由于样本数有限且受噪声的影响， 用一次函数预测的结果更好。同样的实验进行了100次，71% 的结果是一次拟合好于二次拟合。由此可看出，有限样本情况下，1) 经验风险最小并不一定意味着期望风险最小； 2) 学习机器的复杂性不但应与所研究的系统有关，而且要和有限数目的样本相适应。我们需要一种能够指导我们在小的样本情况下建立有效的学习和推广方法的理论-统计学习理论。2.2 支持向量机的基本方法假定大小为 的训练样本集 (, ) , = 1, 2, , ，由二类别组成，如果R 属于第1类，则标记为正(= 1)，如果属于第2类，则标记为负(= - 1)。学习的目标是构造一判别函数，将测试数据尽可能正确地分类。针对训练样本集为线性、非线性两种情况分别讨论2.2.1 线性情况如果存在分类超平面wx+ b= 0, (2.7)使得w+ b1, = 1, (2.8)w+ b- 1, = - 1, = 1, 2, , ,则称训练集是线性可分的，其中wx 表示向量wR 与xR 的内积。式(2.7)和式(2.8) 中的wR ， bR 都进行了规范化，使每类样本集中与分类超平面距离最近的数据点满足式(2.8) 的等式要求。对于式(2.8)，可写成如下形式： (w+ b) 1, = 1, 2, , . (2.9)由统计学习理论知，如果训练样本集没有被超平面错误分开的，并且距超平面最近的样本数据与超平面之间的距离最大，则该超平面为最优超平面(如图2.3所示)，由此得到的判别函数 图2.3 最优分类超平面y (x) = sign (wx+ b) , (2.10)其泛化能力最优，其中sign () 为符号函数。最优超平面的求解需要最大化2/，即最小化，这样可转换成如下的二次规划问题： ， (2.11)s.t ，训练样本集为线性不可分时，需引入非负松驰变量 （没有错分的i=0，错分的i0）分类超平面的最优化问题为 ， (2.12) s.t 其中C 为惩罚参数，C 越大表示对错误分类的惩罚越大。采用拉格朗日乘子法求解这个具有线性约束的二次规划问题，即 ， (2.13) s.t 其中为拉格朗日乘子，由此得到 (2.14) (2.15) (2.16)将式(2.14) (2.16)代入式 (2.13)，得到对偶最优化问题（与原问题等价的另一种求解方法） (2.17) 最优化求解得到的可能是： = 0; 0 C; = C。后两者所对应的为支持向量( support vector, SV )。由式(2.9)知只有支持向量对w 有贡献，也就对最优超平面、判别函数有贡献，所对应的学习方法称之为支持向量机。在支持向量中，所对应的称为边界支持向量(boundary support vector, BSV)，实际上是错分的训练样本点；所对应的称为标准支持向量(normal support vector, NSV)。根据Karush- Kuhn- Tucher条件 (简称KKT条件)知，在最优点，拉格朗日乘子与约束的积为0，即 (2.18) 对于标准支持向量(0 0，则由式(2.18)得到 = 0，因此，对于任一标准支持向量，满足 (2.19)从而计算参数b为 (2.20)为了使计算可靠，对所有标准支持向量分别计算b的值，然后求平均，即 (2.21)式中：为标准支持向量数由式(2.19) 知，支持向量机就是满足式(2.9)等式要求的样本数据，支持向量如图2.3 所示。2.2.2 非线性情况训练集为非线性时，通过一非线性函数将训练集数据 x 映射到一个高维线性特征空间，在这个维数可能为无穷大的线性空间中构造最优分类超平面，并得到分类器的判别函数。因此，在非线性情况下，分类超平面为 (2.22)判别函数为 (2.23)最优分类超平面问题描述为 (2.24)类似于线形情况，得到对偶最优化问题 (2.25) 式中：称为核函数，判别函数为 (2.26)其中阈值b 为 (2.27)由式(2.25)(2.27)知，尽管通过非线性函数将样本数据映射到具有高维甚至为无穷维的特征空间，并在特征空间中构造最优分类超平面，但在求解最优化问题和计算判别函数时并不需要显式计算该非线性函数，而只需计算核函数，从而避免特征空间维数灾难问题。 2.2.3 关于支持向量机方法的说明1) 由统计学习理论知，对于分类器，实际风险和经验风险之间以至少有1- 的概率满足( 0) (2.28)其中h 为VC 维，对于线性分类器, 满足 (2.29)其中r 为包络训练数据的最小球半径。机器学习过程不仅要使经验风险最小，还要使VC 维尽量小，对未来样本才会有较好的泛化能力，这是结构风险最小化准则的基本思想。式(3.10) 中的约束条件约束了w、b，使得经验误差为0，同时最小化使VC维最小，因此式(3.10)的最优化体现了结构风险最小化准则，具有较好的泛化能力。2) 支持向量机方法本质上是一个非负的二次型优化问题，在理论上可以得到全局最优的解析解，因此SVM 不存在局部最优化问题。3) SVM 的重要特征之一是解的稀疏性，即多数最优值为0，只有少量的不为0， 也就是说只需少量样本(支持向量)就可构成最优分类器，这样有用的样本数据大大压缩。4) 对于式(12)的KKT条件，也可以写为(非线性情况) (2.30)由于KKT条件是充要条件，利用上式可判别是否为最优。2.2.4 支持向量机的基本核函数SVM中的核函数必须要满足Merce条件，不同的内积核函数将形成不同的算法，目前研究最多的核函数主要有三类，一是多项式核函数(Polynomial kernel) (2.31)所得到的是q 阶多项式分类器；二是径向基函数(RBF kernel) (2.32)所得分类器与传统RBF方法的重要区别是，这里每个基函数中心对应一个支持向量，它们及输出权值都是由算法自动确定的。也可以采用Sigmoid 函数作为内积，即， (2.33)这时SVM实现的就是包含一个隐层的多层感知器，隐层节点数是由算法自动确定的，而且算法不存在困扰神经网络方法的局部极小点问题。另外，SVM中的核函数还有线形核函数(Linear kernel) (2.34)3 多类 SVM 及其改进算法研究支持向量机的出现最初是为了解决两类模式识别问题。当它在两类问题中展现出其卓越的性能之后，人们自然而然地想到了利用它来解决模式识别与机器学习等领域中的其他难题。对于我们所处的客观世界来说，许多问题所需要面对的事物类别远远不止两类，例如语音识别，手写体数字识别问题等。因此如何将 SVM 方法有效的应用于多类模式识别问题迅速成为了 SVM 研究中的热点。针对多类模式识别问题的经典 SVM 算法主要有一对一方法（1-vs-1），一对多方法（1-vs-all），决策树方法（DAGSVM）等几种。本章将对这些主要的多类 SVM 算法以及相关方面的研究成果进行全面的讨论，并提出了两种分别基于一对多和一对一 SVM 的改进算法。3.1 经典多类 SVM 方法及研究现状3.1.1 多类模式识别问题模式识别领域中的许多问题，例如语音识别，汉字识别，文本分类等，都属于多类模式识别的问题。与两类模式识别类似，多类识别问题的目的同样也是试图通过经验数据（样本），对未知的事物或者信息进行分类。所不同的只是类别的个数由两个变为了多个。那么同样，多类模式识别问题也有其相应的数学模型：给定样本集 (x 1 , y 1 ),(x 2 , y2 ),.,(x n , yn)，其中 x i Rn， yi 1,2,., k， i = 1,2,.,n。目标是寻找一个决策函数 f ，使得对于所有 i = 1,2,.,n，都满足 f ( xi ) =yi。也就是根据不同的 yi值，将所有样本点正确的分成k 类。其中 y i值相同的样本为同一类。下图就是一个简单多类识别的模型，其中 k = 3。图 3.1 下面的小节将对几种经典的多类 SVM 方法：一对一（1-vs-1），一对多（1-vs-all），决策树方法（DAGSVM）等分别进行讨论，并对这些方法以及一些最近的研究成果进行较为全面的分析与总结。3.1.2 一对一支持向量机（1-vs-1 SVM）顾名思义，一对一支持向量机（1-vs-1 SVM）是利用两类 SVM 算法在每两类不同的训练样本之间都构造一个最优决策面。如果面对的是一个k 类问题，那么这种方法需要构造 k ( k-1 )/2个分类平面（ k 2）。这种方法的本质与两类 SVM 并没有区别，它相当于将多类问题转化为多个两类问题来求解。具体构造分类平面的方法如下：从样本集中取出所有满足 yi = s与 yi = t的样本点（其中1 s, t k ,s t），通过两类SVM 算法构造最优决策函数：用同样的方法对k 类样本中的每一对构造一个决策函数，又由于 f st ( x) = - f ts( x)，容易知道一个k 类问题需要 k (k -1 )/2个分类平面。下图 一对一支持向量机（1-vs-1 SV） 图 3.2 根据经验样本集构造出决策函数以后，接下来的问题是如何对未知样本进行尽量准确的预测。通常的办法是采取投票机制：给定一个测试样本x，为了判定它属于哪一类，该机制必须综合考虑上述所有 k ( k-1 )/2个决策函数对x 所属类别的判定有一个决策函数判定x属于第s类则意味着第s类获得了一票，最后得票数最多的类别就是最终x所属的类别。1-vs-1 SVM 方法的优点在于每次投入训练的样本相对较少，因此单个决策面的训练速度较快，同时精度也较高。但是由于k 类问题需要训练 k ( k -1 )/2个决策面，当k 较大的时候决策面的总数将过多，因此会影响后面的预测速度，这是一个有待改进的地方。在投票机制方面，如果获得的最高票数的类别多于一类时，将产生不确定区域。3.1.3 一对多支持向量机（1-vs-all SVM）一对多支持向量机（1-vs-all SVM）是在一类样本与剩余的多类样本之间构造决策平面，从而达到多类识别的目的。这种方法只需要在每一类样本和对应的剩余样本之间产生一个最优决策面，而不用在两两之间都进行分类。因此如果仍然是一个k 类问题的话，那么该方法仅需要构造k 个分类平面（ k 2）。该方法其实也可以认为是两类 SVM 方法的推广。实际上它是将剩余的多类看成一个整体，然后进行k 次两类识别。具体方法如下：假定将第 j 类样本看作正类（ j = 1,2,.,k），而将其他 k - 1类样本看作负类，通过两类SVM 方法求出一个决策函数：这样的决策函数f j( x )一共有k 个。给定一个测试输入x ，将其分别带入k 个决策函数并求出函数值，若在k个 f j(x )中 f s( x )最大，则判定样本x属于第s类。或者，按上面的方法构造出k个支持向量机，在最后决策x属于哪一类时，也用跟1-vs-1同样的投票方法，当在一个向量机中x属于某一类就将这一类中的所有类别的票数都加1，这样最后的票数最多的就是x所属的类别。这种方法，如果获得的最高票数的类别多于一类时，也将产生不确定区域。下图为 一对多支持向量机（1-vs-all SVM） 图 3.31-vs-all SVM 方法和 1-vs-1 SVM 相比，构造的决策平面数大大减少，因此在类别数目k 较大时，其预测速度将比 1-vs-1 SVM 方法快许多。但是由于它每次构造决策平面的时候都需要用上全部的样本集，因此它在训练上花的时间并不比 1-vs-1 SVM 少。同时由于训练的时候总是将剩余的多类看作一类，因此正类和负类在训练样本的数目上极不平衡，这很可能影响到预测时的精度。另外，与 1-vs-1 方法类似，当同时有几个 j 能取到相同的最大值 f j( x )时，将产生不确定区域。3.1.4 决策树算法（DAGSVM）决策树算法（DAGSVM）与前面两种方法均不太一样，1-vs-all SVM 和 1-vs-1SVM通过一系列的决策函数来依次确定样本的类别，它们可以被认为是“肯定型”的算法，而DAGSVM 却是通过在每层节点处对不符合要求的类别进行排除，最后得到样本所属的类别，应该算是一种“否定型”的算法。具体算法如下：在训练阶段 DAGSVM 和 1-vs-1 SVM 方法的步骤一样，它们的差别主要体现在预测阶段。DAGSVM 首先从 k (k-1)/2个分类决策面中任意选取一个，不妨设为 f st，然后将未知样本x代入该决策函数进行判定：若在此决策函数中x被判定为第s类，那么将所有与第t类样本相关的决策函数全部删除，然后从剩下的与第s 类样本相关的分类决策面中任取一个重复以上步骤；若是被判定为第t类，方法也是完全类似。依此类推，直到决出样本x的最终类别。图 3.4 是使用决策树算法解决一个四类问题的完全示意图图 3.4 决策树算法（DAGSVM）示意图该方法和 1-vs-1 SVM 一样，训练的时候首先需要构造 k ( k -1 )/2个分类决策面。然而和 1-vs-1 SVM 方法不同的是，由于在每个节点预测的时候同时排除了许多类别的可能性，因此预测的时候用到的总分类平面只有 k -1个，