模式识别-支持向量机

《模式识别-支持向量机》由会员分享，可在线阅读，更多相关《模式识别-支持向量机（23页珍藏版）》请在金锄头文库上搜索。

1、计算机模式识别报告支持向量机一、SVM 的介绍支持向量机(Support Vector Machine,SVM)是 Corinna Cortes 和 Vap nik8等于 1995 年首先提出的，它在解决小样本、非线性及高维模式识别 中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题 中。支持向量机方法是建立在统计学习理论的VC 维理论和结构风险最小原 理基础上的，根据有限的样本信息在模型的复杂性（即对特定训练样本的学 习精度）和学习能力（即无错误地识别任意样本的能力）之间寻求最佳折衷 ，以期获得最好的推广能力 。 我们通常希望分类的过程是一 个机器学习的 过程。这些数据点是

2、n 维 实空间中的点。我们希望能够把这些点通过一个n-1 维的超平面分开。通 常这个被称为线性分类器。有很多分类器都符合这个要求。但是我们还希望 找到分类最佳的平面，即使得属于两个不同类的数据点间隔最大的那个面， 该面亦称为最大间隔超平面。如果我们能够找到这个面，那么这个分类器就 称为最大间隔分类器。支持向量机将向量映射到一个更高维的空间里，在这个空间里建立有一 个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面 。建立方向合适的分隔超平面使两个与之平行的超平面间的距离最大化。其 假定为，平行超平面间的距离或差距越大，分类器的总误差越小。一个极好 的指南是 C.J.C Burg

3、es 的模式识别支持向量机指南 。所谓支持向量是指那些在间隔区边缘的训练样本点。 这里的“机（m achine,机器）”实际上是一个算法。在机器学习领域，常把一些算法看做 是一个机器。支持向量机(Support vector machines，SVM)与神经网络 类似，都是 学习型的机制，但与神经网络不同的是SVM 使用的是数学方法和优化技术 。支持向量机是由 Vapnik 领导的 AT支持向量样本集具有一定的鲁棒性;有些成功的应用中,SVM 方法对核的选取不敏感。6.SVM 是一种有坚实理论基础的新颖的小样本学习方法。它基本上不涉及概率测度及大数定律等,因此不同于现有的统计方法。从本质上看,

4、它避开了从归纳到演绎的传统过程,实现了高效的从训练样本到预报样本的“转导推理”(transductive inference) ,大大简化了通常的分类和回归等问题。在 SVM 方法中，只要定义不同的内积函数，就可以实现多项式逼近、贝叶斯分类器、径向基函数(Radial Basic Function 或 RBF)方法、多层感知器网络等许多现有学习算法。统计学习理论从七十年代末诞生，到九十年代之前都处在初级研究和理论准备阶段，近几年才逐渐得到重视，其本身也趋向完善，并产生了支持向量机这一将这种理论付诸实现的有效的机器学习方法。目前，SVM 算法在模式识别、回归估计、概率密度函数估计等方面都有应用。

5、例如，在模式识别方面，对于手写数字识别、语音识别、人脸图像识别、文章分类等问题，SVM 算法在精度上已经超过传统的学习算法或与之不相上下。目前，国际上对这一理论的讨论和进一步研究逐渐广泛，而我国国内尚未在此领域开展研究，因此我们需要及时学习掌握有关理论，开展有效的研究工作，使我们在这一有着重要意义的领域中能够尽快赶上国际先进水平。由于SLT 理论和 SVM 方法尚处在发展阶段，很多方面尚不完善，比如：许多理论目前还只有理论上的意义，尚不能在实际算法中实现；而有关 SVM 算法某些理论解释也并非完美（J.C.Burges 在2中就曾提到结构风险最小原理并不能严格证明SVM 为什么有好的推广能力）

6、 ；此外，对于一个实际的学习机器的 VC 维的分析尚没有通用的方法；SVM 方法中如何根据具体问题选择适当的内积函数也没有理论依据。因此，在这方面我们可做的事情是很多的。三、方法介绍SVM 是从线性可分情况下的最优分类面发展而来的，基本思想可用图 1 的 两维情况说明。图中，实心点和空心点代表两类样本，H 为分类线，H1、H2分 别为过各类中离分类线最近的样本且平行于分类线的直线，它们之间的距离叫 做分类间隔（margin） 。所谓最优分类线就是要求分类线不但能将两类正确分开 （训练错误率为 0） ，而且使分类间隔最大。分类线方程为，我们可0bwx以对它进行归一化，使得对线性可分的样本集，),

7、(iiyxni,.,1dRx，满足1, 1ynibyii, 1,01)(L xw(1) 此时分类间隔等于 2/|w|，使间隔最大等价于使|w|2最小。满足条件(1)且使最小的分类面就叫做最优分类面，H1、H2上的训练样本点就称作支持2 21w向量。 利用 Lagrange 优化方法可以把上述最优分类面问题转化为其对偶问题2， 即：在约束条件, (2a) yii in 10和 i 0 i=1，n (2b) 下对i求解下列函数的最大值： njijijijiniiyyQ1,1)(21)(xx(3) i为原问题中与每个约束条件（1）对应的 Lagrange 乘子。这是一个不等式约 束下二次函数寻优的问

8、题，存在唯一解。容易证明，解中将只有一部分（通常 是少部分）i不为零，对应的样本就是支持向量。解上述问题后得到的最优分 类函数是, (4) niiiibybf1*)(sgn)sgn()(xxxwx式中的求和实际上只对支持向量进行。b*是分类阈值，可以用任一个支持向量 （满足(1)中的等号）求得，或通过两 类中任意一对支持向量取中值求得。 对非线性问题，可以通过非线性 变换转化为某个高维空间中的线性问 题，在变换空间求最优分类面。这种 变换可能比较复杂，因此这种思路在 一般情况下不易实现。但是注意到， 在上面的对偶问题中，不论是寻优目 标函数(3)还是分类函数(4)都只涉及训练样本之间的内积运算

9、。设有)(jixx 非线性映射 : Rd 将输入空间的 样本映射到高维(可能是无穷维)的特征空间 中。当在特征空间 H 中构造最优超 平面时，训练算法仅使用空间中的点积，即 (xi).(xj)，而没有单独的 (xi)出 现。因此，如果能够找到一个函数 K 使得 K( xi , xj )=(xi).(xj)，这样，在高维 空间实际上只需进行内积运算，而这种内积运算是可以用原空间中的函数实现 的，我们甚至没有必要知道变换 的形式。根据泛函的有关理论，只要一种核 函数 K( xi，xj)满足 Mercer 条件，它就对应某一变换空间中的内积。 因此，在最优分类面中采用适当的内积函数 K( xi，xj

10、)就可以实现某一非线性 变换后的线性分类，而计算复杂度却没有增加，此时目标函数(3)变为：, (5) njijijijiniiKyyQ1,1),(21)(xx而相应的分类函数也变为， (6),(sgn()(*1*bKyfniiii xxx这就是支持向量机。 这一特点提供了解决算法可能导致的“维数灾难”问题的方法：在构造判 别函数时，不是对输入空间的样本作非线性变换，然后在特征空间中求解；而 是先在输入空间比较向量(例如求点积或是某种距离)，对结果再作非线性变换9。 这样，大的工作量将在输入空间而不是在高维特征空间中完成。SVM 分类函数图 1 最优分类面形式上类似于一个神经网络，输出是 s 中

11、间节点的线性组合，每个中间节点对 应一个支持向量，如图 2 所示。 函数 K 称为点积的卷积核函数，根据公式，它可以看作在样本之间定义的 一种距离。显然，上面的方法在保证训练样本全部被正确分类，即经验风险 Remp为 0 的前提下，通过最大化分类间隔来获得最好的推广性能。如果希望在经验风险 和推广性能之间求得某种均衡，可以通过引入正的松弛因子i来允许错分样 本的存在。这时，约束（1）变为(7)nibyiii, 1,01)(Lxw而在目标最小化中加入惩罚项，这样，Wolf 对偶问题可221wniiC1以写成：Maximize: njijijijiniiKyyQ1,1),(21)(xx(8)s.t

12、. (9a)yii in 100 i C i=1，n (9b) 这就是 SVM 方法的最一般的表述。为了方便后面的陈述，这里我们对对偶问题 的最优解做一些推导。 定义(10)iiiiy)()(x(11)i jjijjiiiyKyyF),()()(xxx对偶问题的 Lagrange 函数可以写成：图 2 支持向量机示意图22y11y),(xxsK),(2xxK),(1xxKx1x2xdssyy输入向量),.,(21dxxxx基于 s 个支持向量的非sxxx,.,21线性变换（内积）权值iiy输出（决策规则）：),(sgn(1bKyysiiii xx(12)iii iii iii iyCL)()(

13、)(21KKT 条件为(13a)0)( iiii iyFL(13b)00iii且i (i C ) = 0 i (13c) 由此，我们可以推导出如下关系式： 若i = 0 则 i 0 i = 0 (Fi i )yi 0 (14a) 若 0 #include #include #include #include “svm.h“ #define Malloc(type,n) (type *)malloc(n)*sizeof(type)void exit_with_help() printf( “Usage: svm-train options training_set_file model_file

14、n“ “options:n“ “-s svm_type : set type of SVM (default 0)n“ “0 - C-SVCn“ “1 - nu-SVCn“ “2 - one-class SVMn“ “3 - epsilon-SVRn“ “4 - nu-SVRn“ “-t kernel_type : set type of kernel function (default 2)n“ “0 - linear: u*vn“ “1 - polynomial: (gamma*u*v + coef0)degreen“ “2 - radial basis function: exp(-gamma*|u-v|2)n“ “3 - sigmoid: tanh(gamma*u*v + coef0)n“ “4 - precomputed kernel (kernel values in training_set_file)n“ “-d degree : set degree in kernel function (default 3)n“ “-g gamma : set gamma in k