支持向量机原理及应用

《支持向量机原理及应用》由会员分享，可在线阅读，更多相关《支持向量机原理及应用（13页珍藏版）》请在装配图网上搜索。

1、支持向量机简介摘要 :支持向量机方法是建立在统计学习理论的VC维理论和结构风险最小原理 基础上的，根据有限的样本信息在模型的复杂性（即对特定训练样本的学习精度） 和学习能力（即无错误地识别任意样本的能力）之间寻求最佳折衷，以求获得最 好的推广能力 。我们通常希望分类的过程是一个机器学习的过程。这些数据点 是 n 维实空间中的点。我们希望能够把这些点通过一个 n-1 维的超平面分开。 通常这个被称为线性分类器。有很多分类器都符合这个要求。但是我们还希望找 到分类最佳的平面，即使得属于两个不同类的数据点间隔最大的那个面，该面亦 称为最大间隔超平面。如果我们能够找到这个面，那么这个分类器就称为最大间

2、 隔分类器。关键字:VC理论结构风险最小原则学习能力1、SVM的产生与发展自1995年Vapnik在统计学习理论的基础上提出SVM作为模式识别的新方 法之后，SVM 直倍受关注。同年，Vapnik和Cortes提出软间隔（soft marginjSVM，通过引进松弛变量度量数据x.的误分类（分类出现错误时大 i i i 于0） ，同时在目标函数中增加个分量用来惩罚非零松弛变量 （即代价函数） ， SVM的寻优过程即是大的分隔间距和小的误差补偿之间的平衡过程；1996年， Vapnik等人又提出支持向量回归（Support Vector Regression , SVR）的方法 用于解决拟合问题

3、。SVR同SVM的出发点都是寻找最优超平面，但SVR的目的不 是找到两种数据的分割平面，而是找到能准确预测数据分布的平面，两者最终都 转换为最优化问题的求解；1998年，Weston等人根据SVM原理提出了用于解决 多 类 分 类 的 SVM 方 法 (Multi-Class Support Vector Machines ，Multi-SVM)，通过将多类分类转化成二类分类，将SVM应用于多分类问题的判 断：此外，在SVM算法的基本框架下，研究者针对不同的方面提出了很多相关 的改进算法。例如，Suykens提出的最小二乘支持向量机 (Least Square Support Vector M

4、achine 丄SSVM)算法 Joachims等人提出的SVM-1ight， 张学工提出的中心支持向量机 (Central Support Vector Machine，CSVM)， Scholkoph和Smola基于二次规划提出的v-SVM等。此后，台湾大学林智仁(Lin Chih-Jen )教授等对SVM的典型应用进行总结，并设计开发出较为完善的SVM工 具包，也就是 LIBSVM(A Library for Support Vector Machines)。上述改进模 型中，v-SVM是一种软间隔分类器模型，其原理是通过引进参数v,来调整支持 向量数占输入数据比例的下限，以及参数 来度

5、量超平面偏差，代替通常依靠经 验选取的软间隔分类惩罚参数，改善分类效果；LS-SVM则是用等式约束代替传 统SVM中的不等式约束，将求解QP问题变成解一组等式方程来提高算法效率； LIBSVM是一个通用的SVM软件包，可以解决分类、回归以及分布估计等问题， 它提供常用的几种核函数可由用户选择，并且具有不平衡样本加权和多类分类等 功能，此外，交叉验证(cross validation)方法也是LIBSVM对核函数参数选取问 题所做的一个突出贡献；SVM-1ight的特点则是通过引进缩水(shrinking燧步 简化QP问题，以及缓存(caching)技术降低迭代运算的计算代价来解决大规模样 本条

6、件下SVM学习的复杂性问题。2、支持向量机基础2.1 统计学习理论基与传统统计学理论相比，统计学习理论(Statistical learning theory或SLT) 是一种专门研究小样本条件下机器学习规律的理论。该理论是针对小样本统计问 题建立起的一套新型理论体系，在该体系下的统计推理规则不仅考虑了对渐近性 能的要求，而且追求在有限信息条件下得到最优结果。Vapnik等人从上世纪六、 七十年代开始致力于该领域研究，直到九十年代中期，有限样本条件下的机器学 习理论才逐渐成熟起来，形成了比较完善的理论体系统计学习理论。统计学习理论的主要核心内容包括：(1)经验风险最小化准则下统计学习一 致性条

7、件；(2)这些条件下关于统计学习方法推广性的界的结论；(3)这些界的基 础上建立的小样本归纳推理准则；(4)发现新的准则的实际方法(算法)。2.2 SVM原理SVM方法是20世纪90年代初Vapnik等人根据统计学习理论提出的一种新 的机器学习方法，它以结构风险最小化原则为理论基础，通过适当地选择函数子 集及该子集中的判别函数，使学习机器的实际风险达到最小，保证了通过有限训 练样本得到的小误差分类器，对独立测试集的测试误差仍然较小。支持向量机的基本思想是：首先，在线性可分情况下，在原空间寻找两类样 本的最优分类超平面。在线性不可分的情况下，加入了松弛变量进行分析，通过 使用非线性映射将低维输入

8、空间的样本映射到高维属性空间使其变为线性情况， 从而使得在高维属性空间采用线性算法对样本的非线性进行分析成为可能，并在 该特征空间中寻找最优分类超平面。其次，它通过使用结构风险最小化原理在属 性空间构建最优分类超平面，使得分类器得到全局最优，并在整个样本空间的期 望风险以某个概率满足一定上界。其突出的优点表现在：(1)基于统计学习理论中结构风险最小化原则和VC维 理论，具有良好的泛化能力，即由有限的训练样本得到的小的误差能够保证使独 立的测试集仍保持小的误差。(2)支持向量机的求解问题对应的是一个凸优化问 题，因此局部最优解一定是全局最优解。(3)核函数的成功应用，将非线性问题 转化为线性问题

9、求解。(4)分类间隔的最大化，使得支持向量机算法具有较好的 鲁棒性。由于SVM自身的突出优势，因此被越来越多的研究人员作为强有力的 学习工具，以解决模式识别、回归估计等领域的难题。3 支持向量机相关理论3.1 学习问题y=f(x,v)学习机器(LM),输入-输出映射函数集y=f(x,w)，w W，W是参数集合。学习问题就是从给定的函数集f(x,w),wW中选择出能够最好的逼近训练器响应的函数。而这种选择是基于训练集的，训练集由根据联合分布F(x,y)二F(x)F(y|x)抽取的n个独立同分布样本(xi,yi) ,i=1,2,.,n组成。3.2 学习问题的表示学习的目的就是，在联合概率分布函数F

10、(x,y)未知、所有可用的信息都包含在训练集中的情况下，寻找函数f(x勰0)，使它在函数类f(x,w)，(wW)R(w) “ L(y, f (x, w)dF (x, y)上最小化风险泛函L( y, f (x, w)二0,若y 二 f(x，w)1,若y 丰 f(x,w)模式识别问题1NR(w)二L(d , f (x , w)3.3经验风险最小化原则(ERM )i i1、最小化经验风险(训练样本错误率 ) ：函数集 Fk二F(x,w);wuWk,k=1,2,.,nF1 F2 FnVC维：h1h2_hn在使保证风险(风险的上界)最小的子集中选择使经验风险最小的函数2、ERM的缺点用ERM准则代替期望

11、风险最小化并没有经过充分的理论论证，只是直观上合 理的想当然做法。 这种思想却在多年的机器学习方法研究中占据了主要地位。人们多年来将大 部分注意力集中到如何更好地最小化经验风险上。实际上，即使可R假W当毎邸向于无穷大时经佥风险也不一定趋近于期望风险，在很多问题中的样本数目也离无穷大相去甚远 ，如神经网络。3.4 Vapnik-Chervonenkis(VC)维1、定义：vc维是对由学习机器能够实现的分类函数族的容量或表达力的测度。分类函数集= f(x,w):wW的VC维是能被机器对于分类函数的所有可能 二分标志无错学习的训练样本的最大数量，描述了学习机器的复杂性2、学习机器实际风险的界其中n样

12、本数量，h是VC维，是递减函数两种方法： 神经网络: 保持置信范围固定(通过选择一个适当构造的机器)并最小化经 验风险。支持向量机(SVM):保持经验风险固定(比如等于零)并最小化置信范围。 结构风险最小化原则函数集 Fk二F(x,w);wuWk, k=1,2,.,nF1 F2 FnVC维:h1h2hn3.5 支持向量回归机SVM 本身是针对经典的二分类问题提出的，支持向量回归机( SupportVector Regression , SVR )是支持向量在函数回归领域的应用。SVR与SVM 分类有以下不同：SVM回归的样本点只有一类，所寻求的最优超平面不是使两 类样本点分得“最开”，而是使所

13、有样本点离超平面的“总偏差”最小。这时样 本点都在两条边界线之间，求最优回归超平面同样等价于求最大间隔。3.5.1 SVR基本模型对于线性情况，支持向量机函数拟合首先考虑用线性回归函数f (x) = -x + b拟合(x ,y ),i = 1,2,.,nii需要确定和b。为输入量，y GR为输出量，即i0/，川-门)| -图3-3a SVR结构图图3-3b不灵敏度函数7 二 * 弹门 + _ qy -门号旳+二惩罚函数是学习模型在学习过程中对误差的一种度量，一般在模型学习前己 经选定，不同的学习问题对应的损失函数一般也不同，同一学习问题选取不同的 损失函数得到的模型也不一样。常用的惩罚函数形式

14、及密度函数如表3-1。表3-1 常用的损失函数和相应的密度函数损失函数名称损失函数表达式趾)噪声密度P忆)ii8 -不敏感g i 82(1) exP( |g | )2(1+8 )i 8拉普拉斯打2exp（-ig）高斯2 g 22 i1g 2莎eXP(飞)鲁棒损失厂丄(g.)2, if g G；2iiV|g | 牛，otherwise;Vexp( 27), if |gC exp(C |g |), otherwise、 2 1多项式2厂（1/严（-即。）分段多项式V|g |p , if |g|3 pC p-1 i|g 1 c _1, otherwise JpVrg pexp( i), if g |

15、c pc p-1iexp(c _1 |g 1), otherwise p 标准支持向量机采用s -不灵敏度函数即假设所有训练数据在精度s下用线性函数拟合如图（3-3a ）所示，一 y - f （x ） +i i i f （x ） 一 y 0ii式中，g g *是松弛因子，当划分有误差时，g，g *都大于0,误差不存在取0。i ii这时，该问题转化为求优化目标函数最小化问题：R（,g,g*）二- + c （g +g*）（3.12）2i ii=1式（3.12）中第一项使拟合函数更为平坦，从而提高泛化能力；第二项为减小误差；常数C 0表示对超出误差s的样本的惩罚程度。求解式（3.11）和式（3.12

16、） 可看出，这是一个凸二次优化问题，所以引入 Lagrange 函数：L = co w + C(g + g*) g + s y + f (x)3.13)2i ii iiii =1i =1工a *g * +8 y + f (x.) 工(g.Y. + g *y *)i iiii i i ii=1i=1式中，a ，a * 0，丫 ，y * 0为 Lagrange 乘数，-1,2,.,n。求函数l 对 ，ii ib , g , g *的最小化，对a ，a* , y，丫*的最大化，代入Lagrange函数得到 i iiii i对偶形式，最大化函数：W (a, a *)=(a -a*)(a -a*)(x

17、- x )i i j j i ji =1, j=13.14)+工(a -a*)y -工(a +a*)8i i ii ii=1i=1其约束条件为： (a -a*) = 0viii=10 a , a * Cii求解式(3.14 )、( 3.15)式其实也是一个求解二次规划问题，由Kuhn-Tucker定理，在鞍点处有：a8+g -y + f(x)=0 a*8+g*-y + f(x)=0 ii iiii ii3.16)3.17)g y = 0g * y * = 0i ii i得出a .a * = 0，表明a ，a *不能同时为零，还可以得出：i iii(C-a )g =0ii(C-a*)g* =0i

18、i从式(3.17 )可得出，当a = C，或a * = c时，f(x ) - y |可能大于8，与 iiii其对应的x称为边界支持向量(Boundary Support Vector，BSV)，对应图i3-3a 中虚线带以外的点；当a * g (0, C)时，|f (x ) - y | = 8，即g = 0 ，g * = 0，iiiii与其对应的x称为标准支持向量(Normal Support Vector，NSV )，对应图i3-3a中落在8管道上的数据点；当a =0，a =o时，与其对应的x为非支持向iii量，对应图3-3a中8管道内的点，它们对w没有贡献。因此8越大，支持向量 数越少。对

19、于标准支持向量，如果0a c(a* = 0)，此时g = 0，由式(3.16)iii可以求出参数b:b = y _乙(a _a *)x -x -si j j j i=y (a a *) x . x - si j j j ix eSVj同样，对于满足0 a* c(a = 0)的标准支持向量，有 iib = y 工(a a *)x x si j j j ixjeSV般对所有标准支持向量分别计算b的值，然后求平均值，即b = 工 y -工(a a*)K(x ,x) s3.18)3.19)Nij jj iN 0aiCx.eSV+y (a a*)K(x , x) si. i0a* 0;冋斯核.k(x,x

20、) = exp(RBF 核.k(x,x) = exp(x XB 样条核:k(x,x) = B?n (卜x|)；Fourier 核：sin(N + 2)(x x)Fourier 核.上(x,x) =-2sin (x x)2因此式(3.20)变成W(a,a*)= 工 (a a*)(a a*) - K(x-x)2 i i j j i i=, j=3.21)3.22)(a a *) y 工(a +a *)8i i i i ii =i=可求的非线性拟合函数的表示式为.f (x) = (x) + b=g (a a*)K(x,x) + b i i i i=4、结论和讨论以统计学习理论作为坚实的理论依据，SV

21、M有很多优点，如基于结构风险 最小化，克服了传统方法的过学习(Overfitting )和陷入局部最小的问题，具 有很强的泛化能力；采用核函数方法，向冋维空间映射时并不增加计算的复杂性， 又有效地克服了维数灾难(Curse of Dimensionality)问题。但同时也要看到目 前SVM研究的一些局限性：(1) SVM的性能很大程度上依赖于核函数的选择，但没有很好的方法指导针对具体问题的核函数选择；(2) 训练测试SVM的速度和规模是另一个问题，尤其是对实时控制问题， 速度是一个对SVM应用的很大限制因素；针对这个问题。Platt和Keerthi 等 分 别 提 出 了 SMO(Seque

22、ntial MinimizationOptimization)和改进的SMO方法，但还值得进一步研究；(3) 现有SVM理论仅讨论具有固定惩罚系数C的情况，而实际上正负样本 的两种误判往往造成损失是不同的。显然，SVM实际应用中表现出的性能决定于特征提取的质量和SVM两方面： 特征提取是获得好的分类的基础，对于分类性能，还可以结合其他方法进一步提 高，文中已经给出了多个实例。另外，忻栋等提出的SVM概率输出的方法也是 对SVM功能的发展。就目前的应用研究状况而言，尽管支持向最机的应用研究已经很广泛，但应 用尚不及人工神经网络方法，所以有理由相信SVM的应用研究还有很大潜力可 挖。参考文献1 刘

23、霞，卢苇SVM在文本分类中的应用研究，计算机教育，2007.12 张学工.关于统计学习理论与支持向量机J.自动化学报,2000, 26(1): 32-41.3 VAPNIK V N. 统计学习理论的本质 M. 张学工, 译. 北京: 清华大学出版社 , 2000.4 VAPNIK V N.统计学习理论M.许建华，张学工，译北京：电子工业出版社, 2004.5 刘晓亮，丁世飞.SVM用于文本分类的适用性J.计算机工程与科学,2010, 32(6):6 林开标，王周敬.基于支持向量机的传真收件人识别方法J.计算机工程与应用， 2006, 42(7): 156-158.7 谢塞琴，沈福明，邱雪娜.基于支持向量机的人脸识别方法J.计算机工程，2009, 35(16): 186-188.8 李颖新，阮晓钢.基于支持向量机的肿瘤分类特征基因选取J.计算机研究与发展, 2005, 42(10): 1796-1801.9 高伟, 王宁. 浅海混响时间序列的支持向量机预测 J. 计算机工程, 2008, 34(6): 25-27.