支持向量机论文.docx

《支持向量机论文.docx》由会员分享，可在线阅读，更多相关《支持向量机论文.docx（12页珍藏版）》请在优知文库上搜索。

1、任课教师:一、命题局部二、评分标准三、教师评语请根据您确定的评分标准详细评分，给定成绩，填入“成绩”局部。阅卷教师评语评阅教师签字:成绩200年月注1：本页由学生填写卷头和“任课教师”局部，其余由教师埴写。其中蓝色字体局部请教师在命题时删除。提交试卷时含本页。学生从第二页开始写作，要求见蓝色字体局部。注2：“阅卷教师评语”局部请教师用红色或黑色碳素笔填写，不可用也子版。无“评语”视为不合标准。注3:试题、评分标准、评语尽量控制在本页。注4：不符合标准试卷需修改标准后提交。支持向量机简述提要传统统计学研究的是样本数目趋于无穷大时的渐进理论，但在实际问题中，样本数往往是有限的，因此一些理论上很优秀

2、的学习方法实际表现却可能不尽如人意。针对小样本，Vapnik等人提出了统计学习理论，并以此为根底提出了支持向量机这一有力工具。本文对支持向量机进行了简单介绍，并以分类器为根底介绍了支持向量机的一些核心概念。关健字支持向量机统计学习理论-)支持向量机简介支持向量机(SupportVectorMachine)是COrteS和VaPnik于1995年首先提出的，它在解决小样本、非线性及高维模式识别中有许多特有的优势，并能推广应用到函数拟合等其他机器学习问题中1。支持向量机方法是建立在统计学习理论的VC维和结构风险最小原理根底上的，根据有限的样本信息在模型的复杂性和学习能力之间寻求最正确折衷，以期获得

3、最好的推广能力。1.1Ve维定义Ll(N(F,Z,.):设F是一个假设集，即由在XUR上取值为-1或1的假设干函数组成的集合。记Zrtt=玉,怎J为X中的m个点组成的集合。考虑当/取遍F中的所有可能的假设时产生的m维向量(/(XJf(Z),/(/)。定义N(F,ZQ)为上述m维向量中不同的向量个数。定义1.2(Z,“被F打散)：设F是一个假设集，Zw=玉,勺，,ZJ为X中的m个点组成的集合。称Z,“被F打散，或F打散Z,”。定义1.3IVC维)：设假设集F是一个由X上取值为-1或1的函数组成的集合.定义F的VC维为maxmN(F,ZJ=2n,.VC维反映了函数集的学习能力。一般而言，VC维越大

4、，学习机器越复杂。但目前没有通用的关于任意VC维计算的理论，只对一些特殊函数集的VC维可以计算。如何利用理论和实验的方法计算VC维是当前统计学习理论中一个待研究的问题3。1.2结构风险最小化机器学习本质上是一种对问题真实模型的逼近，由于真实世界的模型往往无法精确给出，我们给出的模型与真实模型就存在一个误差，这个与真实模型之间的误差积累就叫做风险。统计学习理论系统地研究了对于各种类型的函数集，经验风险和实际风险之间的关系，即泛化误差界。统计学习理论指出：经验风险凡“(W)和实际风险R(W)之间至少以n的概率满足如下关系RW)i)+产”/4)其中，1是样本数，h是函数集的Ve维。这一结论说明，统计

5、学习的实际风险由两局部组成：一个是经验风险，另一个是置信风险。置信风险反映了真实风险和经验风险差值的上确界，和VC维h记样本数1有关。可简单地表示为R(W)R四(W)+-)在有限的训练样本下，学习机器的复杂性越高，VC维越大，置信风险就越大，就会导致真实风险和经验风险间的差异越大。如下图函数集子集:SlUS2US3VC维:hhz1的Lagrange乘子。根据KKT条件(KarUSh-KUhn-TUCker)有：-=OnW=ZaN项f=/=1根据WOlf对偶理论，经运算将原始优化问题转为1/maxw(a)=jai-Yaiajyiyj(xixy)=1幺j,j=s.t.Zaiyi=0,ai0,i=1

6、,2,.,I.=1解此最优化问题，可确定最优超平面。且通常只有一小局部生不为0,这些非零解对应的样本就是支持向量。此时得到的最优分类函数是.f(x)=sgn(Wx)+Z?)=sgnaiyi(xix)+。i=l不难看出，式中的求和实际上只对支持向量进行。b*可由任一支持向量回代求得。此时，我们就得到了一个样本线性可分时的线性分类器。(三)核函数线性可分的问题可以由上述的线性分类器求解，当待分类样本为非线性可分时，可以通过非线性变换转化为某个高维空间中的线性问题，在变换空间求最优分类面。如图当(a,b)范围内的样本为一类，其余局部为一类时，在二维空间无法找到一个线性函数将其正确分开，但我们可以找到

7、一条曲线，如此时该函数表达式为g(x)=C0X2+C1X+C2新建一个向量y=(必，%，丁3)/=(一,%1)丁，。=51，。2，。3)7=(C0，G，C2)T将g()转化为/(y)=,此时f(y)与g()等价，且为四维空间中的线性函数。这样，我们就将低维的非线性可分问题转化为了高维的线性可分问题。但遗憾的是，目前还没有一种系统地将低维向量映射到高维的方法5。事实上，计算过程中我们只关心高维向量之间的内积，只要找出一种方法可以求出此值就得到了我们想要的结果。核函数(kernelfunction)正是为了求出低维空间的向量经过变换后在高维空间的内积而提出的。并且由于其输入为原空间中的低维向量，避

8、开了高维变换计算问题，使得问题大大简化了0根据泛函的有关理论，只要种核函数K5,Xj)满足MerCer条件，它就对应某一变换空间中的内积6。Mercer条件：对任意的对称函数K(X,/),它是某个特征空间中的内积运算的充分必要条件是，对任意夕(X),0,且2(xyZr0用核函数替换内积函数后，此时的最优分类目标函数变为f(x)=Sgn力令yiK(xiX)+bZ=I此时由于计算仍在原空间进行，分类器的计算复杂度没有增加4。目前，常用的核函数有以下几种：线性核函数：Kxi,xj)=xixj多项式核函数：Ka巧)=(一)+球径向基函数(RBF)：K(xi,xj)=ex(-xz-xyI)Sigmoid

9、函数：K(Xi,Xj)=tanh(v(xzxy)+C)这时SVM实现的是包含一个隐层的多层感知器，隐层节点数是由算法自动确定的，而且算法不存在困扰神经网络方法的局部极小点问题。(四)松弛变量及惩罚因子核函数解决了低维向高维空间映射的计算问题，但如果映射到高维空间之后有少量样本的存在使得问题仍然是非线性可分的，这种造成少量错分的问题称为近似线性可分。如图ma 2in=2 v4.1 松弛变量此时我们对错分样本点i引入一非负松弛变量二使其间隔可以大于规定的间隔。并使用一个惩罚因子C衡量其带来的损失。此时，我们的原始优化问题就变为：yi(wxi)+h1-f(Z=1,2,.)subjectto7jo此时

10、，近似线性可分问题就转为了线性可分问题。由此得到的分类器称为软间隔分类器，之前未参加松弛变量得到的分类器为硬间隔分类器。引入松弛变量可以获得更大的分类间隔，但同时也使分类器的精确分类能力降低了。4.2 惩罚因子惩罚因子C代表了对离群点的重视程度，C越大，表示不能舍弃该样本的程度越大，在极端的情况下，C趋于无穷时退化为硬间隔分类问题。惩罚因子可用来解决数据集偏斜的问题，即分别给正类、负类的样本点赋予不同的惩罚因子，由此区分对两类样本的重视程度。数据集偏斜是指参与分类的两类样本数量差距很大，此时对于数量少的样本应予以重视，不能轻易舍弃，应赋予较大的惩罚因子。此时我们目标函数中因松弛变量而损失的局部

11、就变为pp+qC,+c.i=j=p+lc其中，i=l.p为正样本，j=p+lp+q为负样本。C.、C的比例选取应根据实际情况具体问题具体分析，如当两类样本分部情况类似时，正负类惩罚因子的比例可以由数量之比确定，当一类与另一类相比样本较集中时，可以用覆盖两类的超球半径之比来确定。(五)SVM用于多类分类由于SVM属于二类分类器，一个分类器只能完成二类分类，在处理多类分类问题时，需要用到多个分类器共同完成分类工作。常用的多类分类方法有：类对余类(l-a-r)s一对一类(Ial)和有向无环图支持向量机(DAGSMV)lar方法是指，训练时，每次选取一个类的样本作为正类样本，其余为负类样本，此时生成的

12、分类器个数为n。分类时，将待分类样本代入每个分类器进行运算。lar方法由于分类器较少，所以分类速度较快，但会出现分类重叠或不可分类现象，并且由于训练阶段正负类数量差距较大，这就人为造成了数据集偏斜。1.a-I方法是指，训练时，选取一个样本作为正类样本，分别取其余样本中的一类为负类样本进行训练，此时生成的分类器个数为n(n-l)个。分类时，将待分类样本代入每个分类器进行运算，采用每个分类器投票的方式决定样本类别。方法的优点在于，由于训练阶段正负类样本数量较少，整体上来说，速度要优于l-ar方法，虽然仍然存在分类重叠现象，但防止了不可分类现象，缺点在于分类器个数过多，分类过程会较慢。DAGSMV方法是指，训练时，按照1-a-l的方法求