基于支持向量机的分类研究

1、支持向量机在模式分类中的应用 谢 骏 胡均川 笪良龙 海军潜艇学院战术水声环境数据中心，山东青岛266071) 摘 要：介绍了支持向量机的基本思想，依据是否引入核函数，是否具有惩罚因子，支 持向量分类算法被分为线性分界面硬间隔、线性分界面软间隔、非线性分界面硬间隔和 非线性分界面软间隔四类，并讨论了它们的数学模型。以 RBF 为核函数的非线性支持向 量机对 2类 2维样本进行的仿真分析，并与最近邻法分类结果进行了比较，结果表明支 持向量机分类能力受核函数参数影响较大，当选取适当参数时，其分类性能与最近邻法 相当。 关键词 ：特征提取；最近邻分类法；支持向量机；模式分类 中图分类号 ： TP39

2、1.4文献标识码 ：A 文章编号： The Application of Support Vector Machines in Pattern Classification XIE 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

3、including linearly 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 ty

4、pes.The results show 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 neighbou

5、r classification ;support vector machines; pattern classification 1、引言 在模式识别领域如何设计一种具有较好泛化能力的优良分类器一直以来是个备受关注 的问题。 传统的模式识别或人工神经网络方法都都是以大样本统计理论为基础的，而许多实际 问题中常常面对的是小样本。 如何从小样本集出发， 得到泛化能力较好的模型， 是模式识别研 究领域内的一个难点。 Vapnik1 等人早在 20 世纪 60 年代就开始研究有限样本情况下的机器 学习问题， 但这些研究长期没有得到充分的重视。 近十年来， 有限样本情况下的机器学习理 论逐渐成熟起来，

6、形成了一个较完善的统计学习理论(SLT)体系。而同时，神经网络等较 新兴的机器学习方法的研究则遇到一些重要的困难， 比如如何确定网络结构的问题、 过拟合 与欠拟合问题、局部极小点问题等。在这种情况下，试图从更本质上研究机器学习的 SLT 体系逐步得到重视。 19921995年，在 SLT 的基础上发展了支持向量机( SVM )算法 基金项目： 国防预研基金， 51303060403-01；新世纪优秀人才支持计划 NCET 。 作者简介：谢 骏(1976-), 男, 安徽颍上 , 汉, 博士生 , 讲师 , 研究方向为声纳环境效应仿真、水下目标特性分析。 ， 在解决小样本、 非线性及高维模式识别

7、问题中表现出许多特有的优势。 尤其是在非线性支持 向量机中通过引入核函数， 将原始空间的非线性问题转化为特征空间的线性问题来求解， 而 且核方法的引入从理论上较好的解决了经验风险最小化原则下统计学习的一致性条件， 在这 1 些条件下关于统计学习方法泛化性的界， 在这些界的基础上建立小样本归纳推理原则， 以及 在此原则下如何构造学习算法等统计学习的基础理论问题。 2、支持向量机分类器的几种数学模型 支持向量机最初思想是对于线性可分问题如何寻求最优分类面， 对于特征空间中线性可 分问题， 最优分类面就是间隔 最大的分界面， 根据上述核理论的分析可知， 它的确是在保 证样本被正确分类前提下，具有最好

8、泛化能力的分界面。对于特征空间中线性不可分问题， 可通过一个惩罚因子来综合考虑间隔和松弛因子的影响。 根据面对的不同问题和采取的不同 优化策略可将解决分类问题的支持向量机分为如下四类。 2.1 线性分界面硬间隔 当在原始空间中分界面是线性的，即解决的问题是在原始空间中寻求最优分界面问题。 该问题的数学模型是： min w,b , s.t. yi( w ,xi b ) i, ，1 , 2 w1 其中 为间隔， 是训练样本数， xi是训练样本矢量， w是权矢量， b 是阈值， yi为样本 标记， yi1 1 构造拉格朗日函数， xi1 i 1 ， i 代表第 i 类。 xi2 得到 L(w,b,

9、,a, )ai yi( w, xi b) ( w 1) i1 分别对 w,b, 求微分，得到 L(w ,b, ,a, ) ai yi xi 2 w 0 i1 L(w,bb, ,a, )ai yi0 i1 L(w ,b, ,a, ) 1a i 0 i1 将上式代入拉格朗日函数，得到 L(w,b, ,a, )aiyi w, xiw i1 1 =aiaj yi yj(xi xj) 4 i, j 求 得最优化，得到 aiaj yiyj(xi 2 i ,j 得到对偶拉格朗日函数 xj) 1/ 2 L(a)aiaj yi yj(xi xj) i,j 原问题转化为如下最优化问题 min aL(a) 问题在原

10、始空间是非线性的， 数学模型是： min w,b, s.t. Ci i1 yi( w ,xi b ) 2 21 i , i 0i, ，1 , s.t.ai 1， aiyi 0，ai 0， i 1， , i 1 i1 根据最优化理论， aiyi( w,xi b) =0为 KKT 附加条件， 只有少量样本具有非零拉格 朗日乘子，这些样本即为支持向量，它们是数据集中最能提供信息的数据。 2.2 线性分界面软间隔 用线性分界面划分， 需采用线性分界面软间隔， 该问题的 其中 C 为惩罚因子， g(xi ) w, xi b 应用拉格朗日乘子，得到 L(w,b, ,a, ) C iai yi( w, xi

11、 b)ii i ( w 1) i 1 i 1 i 1 分别对分别对 w, b, , 求微分并设其值为零，得到 1 L(a, )aiajyi yj(xi xj) 4 i ,j 在关于 把这个函数最优化，可得到拉格朗日函数对偶形式 1/2 L(a)aiaj yi yj(xi xj) i,j s.t. 和硬分隔结果一样，但要注意此时约束条件有差异。 原问题转化为如下最优化问题 min aL(a) ai 1， aiyi 0，0 ai C， i 1， i 1 i1 i 1， , KKT 附加条件为 aiyi( w,xi b)i =0； i(ai C) 0 2.3 非线性分界面硬间隔 通过引入核函数将问题

12、从原始空间嵌入到特征空间，在特征空间中问题是线性可分的， 求解特征空间中最优分界面。该问题数学模型如下 min w,b, s.t.yi( w , x(i ) b ) i , ，1 , 2 w1 其中函数 是原始空间到特征空间的映射。 与 2.1 推导过程类似，可得到对偶拉格朗日函数 1/2 L(a)aiaj yiyj (xi xj ) i,j 其中函数 是核函数， (xi xj )(xi), (xj ) 原问题转化为如下最优化问题 min a L(a) s.t.ai 1， aiyi 0，ai 0， i 1， , i 1 i1 KKT 附加条件 aiyi( w, (xi) b) =0。 2.4

13、非线性分界面软间隔 通过引入核函数将问题从原始空间嵌入到特征空间，在特征空间中问题是非线性可分 的，此时求解特征空间中最优分界面要考虑惩罚因子。该问题数学模型如下 min w,b, C i i1 s.t.yi( w, x( i ) b ) i ,i i0,， 1 , 2 w1 与 2.2 推导过程类似，可得到对偶拉格朗日函数 1/2 L(a)aiaj yiyj (xi xj ) i,j 原问题转化为如下最优化问题 min a L(a) s.t.ai 1， aiyi 0，0 ai C， i 1， , i 1 i1 KKT 附加条件为 aiyi( w, (xi) b)i =0； i(ai C) 0

14、 i 1， , 当 C 1/( ) 时，此时支持向量机称为支持向量机， (0,1 。 从上述结果可知， 线性和非线性支持向量机的区别是是否引入核函数， 硬间隔和软件隔 支持向量机的区别是是否具有惩罚因子。 遗憾的是， 有关支持向量机核函数和惩罚因子的选 择缺乏理论指导 2 。 3、 非线性支持向量机的仿真分析 以下是以 RBF 为核函数非线性支持向量机对 2 类 2 维样本进行的仿真分析结果，两类 样本点分别用黑色和浅灰色表示。图1图 4 是核函数参数，惩罚因子 C 为不同值时的 分类结果，相应分类错误率见表 1，图中浅灰色线是贝叶斯分类器的分类边界，其分类错误 2 xi x j 率为 13%

15、。其中 RBF核定义为： (xi,xj) exp i 2 j 。 2 从分类错误率结果来看，支持向量机性能受核函数参数和惩罚因子参数选择的影响很 大。文献 3 针对两类样本情况，讨论了 RBF 核函数参数空间中不同区域对应的 SVM 的性 能。 C 越小， SVM 欠训练，倾向于把样本分到样本数占优的一类； C 越大， SVM 过训练， 越大， SVM 趋向线性分类器。 越小， SVM 视C 的情况出现欠训练或过训练。图 1 图 4 的仿真结果验证了这点。有关最优参数选择，文献4 中提到采用网格方法、双线性和 改进双线性法。文献 5 认为最近邻算法是一种直推的方法，即是一种直接从已知样本出发

16、对特定未知样本进行识别的方法和原则，不同于 SVM 试图设计一种分类器，使其对未来所 有可能样本的预期性能最优的原则， 这使得最近邻法在面对某一具体问题时， 能够表现出很 好的分类性能，图 5 的仿真结果也说明了这一点，最近邻法分类错误率为15%。 表 1 RBF 核函数对 2 类 2 维问题的分类错误率 C 错误率 5 0 26% 5 100 49% 0.2 0 15% 0.2 100 20% 图 2 5,C 100时 SVM分类结果图 图 1 5,C 0 时 SVM分类结果图 4 0.2,C 100 时 SVM分类结果图 3 0.2,C 0时 SVM分类结果图 图 5 最近邻算法分类结果

17、4、 结论 本文阐述了支持向量机应用于分类问题的几种情况，分别讨论了它们的数学模型，并通 过仿真试验进行了分析。理论分析和仿真试验结果表明， SVM 作为一种基于结构风险最小 原则的以样本间的某种距离作为划分依据的模式识别方法，它可以在高维空间中构造较低 VC 维的函数集，从而获得好的推广能力，解决了神经网络的局部最优问题，它的数学模型 中样本仅以点积形式出现，使得这种方法很容易推广到非线性。但 SVM 也有明显的不足， 分类性能受核函数参数影响大，参数选择没有明确的理论来指导，文献4 中提出的一些参 数选择的方法，本质上都是通过划分参数区间，然后进行搜索寻优的方法，这使得 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 su