1、支持向量机在模式分类中的应用谢 骏 胡均川 笪良龙（海军潜艇学院战术水声环境数据中心，山东青岛 266071）摘 要：介绍了支持向量机的基本思想，依据是否引入核函数，是否具有惩罚因子，支持向量分类算法被分为线性分界面硬间隔、线性分界面软间隔、非线性分界面硬间隔和非线性分界面软间隔四类，并讨论了它们的数学模型。以 RBF 为核函数的非线性支持向量机对 2 类 2 维样本进行的仿真分析，并与最近邻法分类结果进行了比较，结果表明支持向量机分类能力受核函数参数影响较大，当选取适当参数时，其分类性能与最近邻法相当。关键词：特征提取；最近邻分类法；支持向量机；模式分类中图分类号：TP391.4 文献标识码
2、：A 文章编号： The Application of Support Vector Machines in Pattern ClassificationXIE Jun，HUN Junchuan，DA Lianglong(Naval Submarine Academy，QingDao 266071, China)Abstract：The foundations of support vector machines are introduced. Four mathematics models of support vector classifications including linearl
3、y hard margin SVM, linearly soft margin SVM, non- linearly hard margin SVM and non-linearly soft margin SVM are discussed. Comparison between non-linearly SVM classification with RBF kernel and nearest neighbour classification for a 2-dimension feature data set which contains two types.The results s
4、how that the classification performance of SVM is affected by kernel function parameter. the classification performance of SVM is equivalent with nearest neighbour classification while kernel function parameter is selected appropriately.Key words：feature abstract; nearest neighbour classification ;s
5、upport vector machines; pattern classification1、引言在模式识别领域如何设计一种具有较好泛化能力的优良分类器一直以来是个备受关注的问题。传 统 的 模 式 识 别 或 人 工 神 经 网 络 方 法 都 都 是 以 大 样 本 统 计 理 论 为 基 础 的 ， 而 许 多 实际 问 题 中 常 常 面 对 的 是 小 样 本 。 如 何 从 小 样 本 集 出 发 ， 得 到 泛 化 能 力 较 好 的 模 型 ， 是 模 式 识别 研 究 领 域 内 的 一 个 难 点 。 Vapnik1等人早在 20 世纪 60 年代就开始研究有限样本情况下
6、的机器学习问题，但这些研究长期没有得到充分的重视。近十年来，有限样本情况下的机器学习理论逐渐成熟起来，形成了一个较完善的统计学习理论（SLT）体系。而同时，神经网络等较新兴的机器学习方法的研究则遇到一些重要的困难，比如如何确定网络结构的问题、过拟合与欠拟合问题、局部极小点问题等。在这种情况下，试图从更本质上研究机器学习的 SLT 体系逐步得到重视。 19921995 年，在 SLT 的基础上发展了支持向量机（SVM ）算法 1，在解决小样本、非线性及高维模式识别问题中表现出许多特有的优势。尤其是在非线性支持向量机中通过引入核函数，将原始空间的非线性问题转化为特征空间的线性问题来求解，而且核方法
7、的引入从理论上较好的解决了经验风险最小化原则下统计学习的一致性条件，在这 11基金项目：国防预研基金，51303060403-01；新世纪优秀人才支持计划 NCET。作者简介：谢 骏(1976-), 男, 安徽颍上, 汉, 博士生, 讲师, 研究方向为声纳环境效应仿真、水下目标特性分析。些条件下关于统计学习方法泛化性的界，在这些界的基础上建立小样本归纳推理原则，以及在此原则下如何构造学习算法等统计学习的基础理论问题。2、支持向量机分类器的几种数学模型支持向量机最初思想是对于线性可分问题如何寻求最优分类面，对于特征空间中线性可分问题，最优分类面就是间隔 最大的分界面，根据上述核理论的分析可知，它
8、的确是在保证样本被正确分类前提下，具有最好泛化能力的分界面。对于特征空间中线性不可分问题，可通过一个惩罚因子来综合考虑间隔和松弛因子的影响。根据面对的不同问题和采取的不同优化策略可将解决分类问题的支持向量机分为如下四类。2.1 线性分界面硬间隔当在原始空间中分界面是线性的，即解决的问题是在原始空间中寻求最优分界面问题。该问题的数学模型是：,minwb.st(,),1,iiybix ，21其中 为间隔， 是训练样本数， 是训练样本矢量， 是权矢量， 是阈值， 为样本ixwbiy标记， ， 代表第 类。iy12ixi构造拉格朗日函数，得到 21(,)()(1)iiLbaybwwx,a分别对 求微分
9、，得到 1(,)20iiiyx1(,)iiLbawa1(,)0ii将上式代入拉格朗日函数，得到 21(,)iiLbaywx,= ,()4ijijj求 得最优化，得到1/2,1()2ijijjayx得到对偶拉格朗日函数 1/2,()()ijijjL原问题转化为如下最优化问题mina()， ， ，.st1iia10iiyia1, ，根据最优化理论， =0 为 KKT 附加条件，只有少量样本具有非零拉()ibwx,格朗日乘子，这些样本即为支持向量，它们是数据集中最能提供信息的数据。2.2 线性分界面软间隔问题在原始空间是非线性的，用线性分界面划分，需采用线性分界面软间隔，该问题的数学模型是：,min
10、wb1iC.st(,),01,ii iybix ，2其中 为惩罚因子， (,iigbwx应用拉格朗日乘子，得到 21 1(,)()(1)iiiiiLbCay w w ,a分别对分别对 求微分并设其值为零，得到,(,)()4ijijjyx在关于 把这个函数最优化，可得到拉格朗日函数对偶形式 1/2,()()ijijjLa和硬分隔结果一样，但要注意此时约束条件有差异。原问题转化为如下最优化问题mina()， ， ，.st1ii10iiay iC1,i ，KKT 附加条件为=0； ()iiiybwx, ()0i,i，2.3 非线性分界面硬间隔通过引入核函数将问题从原始空间嵌入到特征空间，在特征空间中
11、问题是线性可分的，求解特征空间中最优分界面。该问题数学模型如下,minwb.st(,),1,iiybix ，21其中函数 是原始空间到特征空间的映射。与 2.1 推导过程类似，可得到对偶拉格朗日函数 1/2,()()ijijjLayx其中函数 是核函数， (),ijijx原问题转化为如下最优化问题mina()L， ， ，.st1ii10iiayi1, ，KKT 附加条件=0。()iiybwx,2.4 非线性分界面软间隔通过引入核函数将问题从原始空间嵌入到特征空间，在特征空间中问题是非线性可分的，此时求解特征空间中最优分界面要考虑惩罚因子。该问题数学模型如下,minwb1iC.st(,),01,
12、ii iybix ，2与 2.2 推导过程类似，可得到对偶拉格朗日函数 1/2,()()ijijjLayx原问题转化为如下最优化问题mina()， ， ，.st1ii10iiay iC1,i ，KKT 附加条件为=0； ()ii iybwx, ()0ia,i，当 时，此时支持向量机称为 支持向量机， 。/C(从上述结果可知，线性和非线性支持向量机的区别是是否引入核函数，硬间隔和软件隔支持向量机的区别是是否具有惩罚因子。遗憾的是，有关支持向量机核函数和惩罚因子的选择缺乏理论指导 2。3、非线性支持向量机的仿真分析以下是以 RBF 为核函数非线性支持向量机对 2 类 2 维样本进行的仿真分析结果，
13、两类样本点分别用黑色和浅灰色表示。图 1图 4 是核函数参数 ，惩罚因子 为不同值时的C分类结果，相应分类错误率见表 1，图中浅灰色线是贝叶斯分类器的分类边界，其分类错误率为 13%。其中 RBF 核定义为： 。2(,)expijij从分类错误率结果来看，支持向量机性能受核函数参数和惩罚因子参数选择的影响很大。文献3针对两类样本情况，讨论了 RBF 核函数参数空间中不同区域对应的 SVM 的性能。 越小，SVM 欠训练，倾向于把样本分到样本数占优的一类；C 越大，SVM 过训练，越大，SVM 趋向线性分类器。 越小，SVM 视 的情况出现欠训练或过训练。图C1图 4 的仿真结果验证了这点。有关
14、最优参数选择，文献4中提到采用网格方法、双线性和改进双线性法。文献5认为最近邻算法是一种直推的方法，即是一种直接从已知样本出发对特定未知样本进行识别的方法和原则，不同于 SVM 试图设计一种分类器，使其对未来所有可能样本的预期性能最优的原则，这使得最近邻法在面对某一具体问题时，能够表现出很好的分类性能，图 5 的仿真结果也说明了这一点，最近邻法分类错误率为 15%。表 1 RBF 核函数对 2 类 2 维问题的分类错误率C错误率5 0 26%5 100 49%0.2 0 15%0.2 100 20%图 1 时 SVM 分类结果图 图 2 时 SVM 分类结果图5,0C 5,10C图 3 时 S
15、VM 分类结果图 图 4 时 SVM 分类结果图0.2,C 0.2,1C图 5 最近邻算法分类结果4、结论本文阐述了支持向量机应用于分类问题的几种情况，分别讨论了它们的数学模型，并通过仿真试验进行了分析。理论分析和仿真试验结果表明，SVM 作为一种基于结构风险最小原则的以样本间的某种距离作为划分依据的模式识别方法，它可以在高维空间中构造较低 VC 维的函数集，从而获得好的推广能力，解决了神经网络的局部最优问题，它的数学模型中样本仅以点积形式出现，使得这种方法很容易推广到非线性。但 SVM 也有明显的不足，分类性能受核函数参数影响大，参数选择没有明确的理论来指导，文献4中提出的一些参数选择的方法
16、，本质上都是通过划分参数区间，然后进行搜索寻优的方法，这使得SVM 算法的效率会受到大大影响。仿真结果也表明，基于直推的最近邻算法的性能往往不比 SVM 算法差，因此有必要对 SVM 算法与最近邻算法等其它分类算法结合构建混合式分类系统做进一步研究。参考文献：1.V. Vapnik. The Nature of Statistical Learning Theory. Springer, N.Y., 1995. ISBN0-387-94559-8.2.O.Chapelle,V Vapnik et aI. Choosiog multiple parameters for support vector machinesJ.Machine Leaming,2002;46:131-1593. Keethi S.S,Lin C.J; Asymptotic Behaviors of Support Vector Machines with Gaussian KernelJ M;Neural Computation 4.边肇祺, 张学工.模式识别(第二版 ) M.北京:清华大学出版社,2003:P3045.王鹏,朱小燕.基于RBF核的SVM的模型选择及其应用J.计算机工程与应用,2003; 39(24) :7273
