（计算机软件与理论专业论文）rbf核支持向量机的参数快速选择方法的研究与实现.pdf

中山大学硕士学位论文 r b f 核支持向量机的参数快速选择方法的研究与实现 r b f 核支持向量机的参数快速选择方法的研究与实现 专业：计算机软件与理论 硕士生：陈华材 指导教师：姜云飞教授 摘要 支持向量机( s v m ) 是机器学习领域中正在快速发展的一种技术，在模式 识别、回归预测、密度估计等方面都有广泛的应用。支持向量机建立在统计学 习理论的基础之上，特别适用于有限样本、非线性问题，得到的学习模型推广 性较好，具有优良的性能。在应用s v m 方法时，核函数的选用和参数的选择 都会对s v m 的性能产生很大的影响。最常用的寻找参数方法是网格搜索法， 它是一种穷举式的搜索，没有利用启发式的信息。网格搜索法虽可以求出很好 的参数，但需要消耗很长的时间。本文主要针对r b f 核函数和s v m 分类问题， 利用了训练样本在特征空间中的分离性特征和r b f 核s v m 的渐近性质等一些 研究成果作为启发式信息来快速确定一个近似最优的参数组合，并通过小范围 的搜索来求精，得出了一种快速选择参数的方法，本文在l i b s v m 工具包的基 础上实现了该方法。 本文通过在几个u c l 分类数据集上进行实验，将本文方法与网格搜索方法 在运行速度和结果精度等方面进行了对比。实验数据证明本文方法在运行速度 上比网格搜索方法有较大的优势，且结果的质量基本保持一致，这显示了本文 方法有一定的实用价值。 在本文方法的适用范围和课题的理论深度等方面，都值得进一步探讨和研 究。 关键词：支持向量机，参数选择，r b f i i i 中山大学硕士学位论文 r b f 核支持向量机的参数快速选择方法的研究与实现 r e s e a r c ha n d i m p l e m e n t a t i o no naf a s tp a r a m e t e r s e l e c t i o nm e t h o df o rs v mw i t hr b fk e r n e l m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e c h e nh u a c a i s u p e r v i s o r ：p r o f e s s o rj i a n gy u n f e i a b s t r a c t s u p p o r tv e c t o rm a c h i n e ( s v m ) i sar a p i dd e v e l o p i n gt e c h n o l o g yi nt h ef i e l do f m a c h i n el e a r n i n g s v mi sw i d e l yu s e di np a r e mr e c o g n i t i o n ，f u n c t i o nr e g r e s s i o n a n dd e n s i t ye s t i m a t i o n s v mm e t h o di sb a s e do nt h es t a t i s t i c a ll e a r n i n gt h e o r y , a n di sp a r t i c u l a r l ys u i t e df o rs m a l l - s a m p l e ，n o n l i n e a rp r o b l e m s t h em o d e l sa c q u i r e d b ys v m h a v eg o o dg e n e r a l i z a t i o na b i l i t ya n de x c e l l e n tp e r f o r m a n c e i na p p l i c a t i o n ， t h ec h o i c eo fk e r n e lf u n c t i o na n di t sp a r a m e t e r sw i l lh a v eag r e a ti m p a c to nt h e p e r f o r m a n c eo fs v m t h eg r i ds e a r c hm e t h o d ，w h i c hi sm o s tc o m m o n l yu s e dt o f i n dp a r a m e t e r s ，i se x h a u s t i v ea n dd o e sn o tu s ea n yh e u r i s t i ci n f o r m a t i o n t h e 鲥d s e a r c hm e t h o dc a no b t m nv e r yg o o dp a r a m e t e r s ，b u ti sv e r yt i m e - c o n s u m i n g t h i s p a p e ri sm a i n l yc o n c e r no nt h es v mb a s e do nr b fk e r n e la n d c l a s s i f i c a t i o n p r o b l e m s u s i n gs o m eh e u r i s t i c s ，i n c l u d i n gs e v e r a lk i n d so fs e p a r a t i o nm e a s u r e so f t r a i n i n gs a m p l e si nf e a t u r es p a c e sa n dr e s e a r c hr e s u l t so f t h ea s y m p t o t i cb e h a v i o ro f t h es v mw i t hr b fk e r n e l ，t h ef a s tp a r a m e t e rs e l e c t i o nm e t h o dp r o p o s e di nt h i s p a p e ri sa b l et od e t e r m i n et h ea p p r o x i m a t eo p t i m a lp a r a m e t e rc o m b i n a t i o nq u i c k l y , a n dt h e np e r f o r m sas m a l l s c o p es e a r c h i n gf o rr e f i n e m e n t t h ep r o p o s e dm e t h o di s i m p l e m e n t e db a s e do nt h el i b s v m t o o l b o x t h r o u g he x p e r i m e n t so ns e v e r a l u c ic l a s s i f i c a t i o nd a t a s e t s ，t h ep r o p o s e d m e t h o di sc o m p a r e dt ot h e 鲥ds e a r c hm e t h o db o t ho nt h es p e e da n dt h ea c c u r a c yo f r e s u l t s e x p e r i m e n t sp r o v et h a tt h ep r o p o s e dm e t h o dt a k e sg r e a ta d v a n t a g et ot h e 鲥ds e a r c hm e t h o di ns p e e d ，w h i l ep r e s e r v i n gc o m p a r a b l ea c c u r a c y e x p e r i m e n t r e s u l t ss h o wt h a tt h ep r o p o s e dm e t h o di so f p r a c t i c a lv a l u e v 中山大学硕十学位论文r b f 核支持向量机的参数快速选择方法的研究与实现 t h em e t h o dp r o p o s e di nt h i sp a p e ri sw o r t hf u r t h e rd i s c u s s i o na n ds t u d yb o t hi n i t sa p p l i c a b l es c o p ea n dt h e o r e t i c a la n a l y s i s k e y w o r d s ：s u p p o r tv e c t o rm a c h i n e ，p a r a m e t e rs e l e c t i o n ，r b f v i 中山人学顾i ：学位论文r b f 核史持向量机的参数伙速选择方法的研究与实现 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研 究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他 个人或集体已经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人 和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本 人承担。 学位论文作孝签名：耳靠华材 日期： 2 0 0 0 d 年岁月2 日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保 留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权 将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料 室被查阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、 缩印或其他方法保存学位论文。 学位论文作者签名：丫意啤孝才 日期： z d 彩年岁月z 日 导师签名： 日期：2 b d8年( 月2 丫日 中山大学硕士学位论文r b f 核支持向量机的参数快速选择方法的研究与实现 第1 章引言 1 1 统计学习理论和支持向量机的发展 机器学习是人工智能的一个重要研究领域。在面对数据但缺乏理论模型时， 统计学是最基本的甚至可能是唯一的分析手段，是机器学习方法的重要理论基 础之一。传统的统计学主要是研究样本数量趋于无穷大时的渐近统计性质，故 基于传统统计学理论的各种学习方法也都是建立在样本数量趋于无穷大的假设 基础上。然而，在具体应用中样本数量通常是有限的。当样本数较少时，用这 类方法得到的结果往往不够理想。因此，研究小样本的机器学习问题具有非常 重要的实际意义。 2 0 世纪6 0 年代间，v l a d i m i rn v a p n i k 等人针对小样本的机器学习的研究 取得了一系列进展，一个统计学习理论体系( s t a t i s t i c a ll e a m i n gt h e o r y ) 得以 逐步建立起来。在统计学习理论的框架下，v a p n i k 等人提出了一种新的通用学 习方法一支持向量机( s u p p o r tv e c t o rm a c h i n e s ，简称s v m ) 方法，它在解 决小样本、非线性及高维模式识别问题中表现出许多特有的优判。s v m 方法 具有非常优良的性能，在小样本的情况下得到的学习模型具有很强的推广能力。 从2 0 世纪9 0 年代开始，随着s v m 方法在一系列实际应用中取得令人瞩目的 成果，统计学习理论和s v m 方法受到了学术界的重视，取得了快速的发展和 应用。 1 2 论文研究的内容 在应用支持向量机方法解决问题的时候，核函数的选择对结果的好坏起着 至关重要的作用。如何针对特定问题选择最优的核函数仍然是一个难以解决的 问题。在目前广泛使用的几种核函数中，r b f 核函数具有广泛的适应性、良好 的性能，而只有较少的参数，这些突出优点使其成为在缺乏对问题的先验知识 时首选的核函数之一，本文研究的主要对象就是基于r b f 核的支持向量机的参 数选取方法。 中山人学硕一i j 学位论文r b f 核支持向量机的参数快速选择方法的研究与实现 s v m 的参数包括核参数和惩罚参数，这些参数的选择对s v m 的性能有非 常重要的影响。最常用的寻找参数方法是网格搜索法，它是一种穷举式的搜索， 没有利用启发式的信息。网格搜索法虽可以求出很好的参数，但也需要消耗很 长的时间。本文主要利用了几种启发式信息来加快r b f 核s v m 的参数寻找速 度，通过快速确定最优参数组合的大致区间，大大缩小参数空间中需要搜索的 范围，再通过小范围的穷举式搜索来保证求解的精度。本文的方法能够在很大 程度上降低盲目搜索参数的消耗，可以较大幅度地加快s v m 的参数寻优速度 和总体训练速度。 本文通过在一系列u c l 分类数据集上进行实验，将本文提出的方法与网格 搜索方法在运行速度和结果精度等方面进行了比较，实验结果证明了本文方法 的快速和有效性。 1 3 论文的组织结构 本文的后续章节的组织结构如下： 第2 章介绍了统计学习理论和支持向量机的一些基础知识，主要包括统计 学习理论的一些重要概念和思想，线性s v m 、非线性s v m 和核函数的基本概 念和基本思想，以及如何利用s v m 解决多分类问题和s v m 模型选择等相关知 识。 第3 章主要通过理论分析和实验来讨论r b f 核支持向量机的参数性质和参 数选择方法。通过分析r b f 核s v m 的核参数和惩罚参数的性质及意义，提出 了一种利用启发式信息分别选取核参数和惩罚参数的思路，所用到的主要启发 式信息是特征空间中类间分离性度量的变化和r b f 核s v m 的渐近性质。通过 在几个小规模二分类数据集上进行实验，尝试寻找随着核参数的变化，几种类 间分离性度量的变化趋势与对应s v m 的学习精度的关系，并验证了文献 2 0 中提出的r b f 核s v m 的一个渐近性质。在分析实验结果的基础上，肯定了快 速选择参数方法的可行性。 第4 章是本文算法的实现和实验结果。首先，根据第3 章的实验结果和分 析结论，提出一种r b f 核支持向量机的快速选择参数方法的，并在l i b s v m 2 中山大学硕士学位论文r b f 核支持向量机的参数快速选择方法的研究与实现 工具包的基础上，通过修改其代码实现了本文提出的方法。然后，通过在多个 u c l 分类数据集上进行实验，分析实验数据，将本文提出的方法与网格搜索方 法在运行速度和测试正确率等方面进行了对比，并根据实验结果对本文方法进 行总结和评价。 第5 章是总结和展望，对本文所阐述的内容进行总结，提出本文方法存在 的问题和不足，并对下一步的研究工作作出展望。 中山人学硕i ：学位论文 r b f 核支持向量机的参数快速选择方法的研究与实现 第2 章支持向量机概述 2 1 统计学习理论简介 统计学习理论( s t a t i s t i c a ll e a r n i n gt h e o r y ) 的研究开始于2 0 世纪6 0 年代，主 要由v a p n i k 等研究者创立。其后，统计学习理论不断发展和成熟，到了2 0 世 纪9 0 年代中期，开始得到了成功的应用并受到越来越广泛的关注。 统计学习理论是目前公认的针对小样本统计估计和预测的最佳理论。它系 统地研究了经验风险最小化原则适用的条件、小样本条件下经验风险与期望风 险的关系，以及如何根据这些理论来构造新的学习原则和学习方法等基本理论 问题【2 1 。统计学习理论是支持向量机方法的理论基础。在本节中介绍的统计学 习理论的基础知识主要参考了文献【1 4 等，其中融入了本文作者的一些理解和 总结。 2 1 1 学习问题的基本模型 机器学习的目的是根据给定的训练样本求出对某系统的输入输出之间的依 赖关系的估计，以使它对未知输入样本的输出能够做出尽可能准确的预测【4 1 。 文献 1 】和文献 4 中将学 - - j 问题的基本模型一般地表示为：变量y 与石存在着一 定却未知的依赖关系，即x 和y 遵循某一未知的联合概率盹y ) ( y 和x 之间的 确定性关系删可以看作是一种特例) ，学习问题就是根据，个独立同分布的 观测样本 ( o ，y 1 ) ，y 2 ) ，帆y t ) ) ( 2 一1 ) 在一组函数舭) 中求一个最优的函数j ( x ，c o o ) 使得期望风险 r ( c o ) = il ( y ，f ( x ，c o ) ) d p ( x ，y ) ( 2 - 2 ) 最小。其中，如，c o ) 称为预测函数集，0 9 为函数的广义参数，地) 可以表示任 何函数集；，似，国) ) 称为损失函数( 1 0 s sf u n c t i o n ) ，表示由于用j ( x ，c o ) 对y 进 行预测产生的偏差所造成的损失，不同类型的学习问题有不同形式的损失函数。 学习的目标就是通过选择一个参数c o d ，使得学习系统的输出( x ，c o o ) 与期望输出 4 中山大学硕士学位论文r b f 核支持向量机的参数快速选择方法的研究i j 实现 y 之间的偏差概率最小化，这个原则称为期望风险最小化。 然而，期望风险r ( ) 是无法直接计算的，因为( 2 1 ) 式中的p ( x ，y ) 是未知的 概率分布。在传统学习方法中，通常采用经验风险来作为对期望风险的估计， 经验风险尺聊( ) 定义为在训练样本集上的学习误差，其数学表达形式如下【l 】： ， r 唧( 国) = 专x l ( y 。，f ( x i 缈) ) ( 2 3 ) i = l 由统计学中的大数定律可知，随着训练集的增大，r 。r a p ( c o ) 将会逐渐收敛于r ( ) 。 可以看出，学习的目标是使期望风险最小化，但在只有给定样本信息的情 况下，期望风险无法直接计算，而对应的经验风险却可以计算；当训练集足够 大时，经验风险将会趋近于期望风险。因此，在传统的学习方法中用经验风险 来作为期望风险的估计，并在学习过程中设法使经验风险最小化，这种思想称 为经验风险最小化准则( e m p i r i c a lr i s km i n i m i z a t i o np r i n c i p l e ) 【2 1 。用经验风险 最小化代替期望风险最小化的做法在机器学习方法的研究中长期占据着主导地 位，但是这种思想并没有充分的理论基础。实际上，在很多问题中训练样本的 数目较少，与接近无穷大还相差很远，用经验风险最小化准则得到的结果并不 能使实际风险最小化。 经验风险最小化准则一个不成功的例子是神经网络的过学习问题【4 】：在神 经网络的研究中很早就发现，使训练误差小的结果在测试未知样本时并不一定 能得到好的正确率，在某些情况下，训练误差过小反而会导致测试正确率的下 降，即经验风险下降反而导致真实风险的增加，这就是过学习问题。在样本有 限的情况下，神经网络拟合能力过强就足以记住每个样本，使得经验风险可以 收敛到零，但这时推广能力则会很差，对未知样本无法给出好的预测结果。学 习机器的复杂性与推广性的矛盾在其它学习方法中也可以看到。 小样本情况下容易出现过学习现象的原因主要是在学习机器的设计上存在 不合理因素。文献 2 指出，在有限样本的情况下： ( 1 ) 经验风险最小并不代表期望风险最小； ( 2 ) 学习机器的复杂性不但应与所研究的系统有关，还要和有限数目的训练 样本相适应。 5 中山火学硕i ：学位论文 r b f 核支持向量机的参数快速选择方法的研究与实现 在这种背景下，适应小样本学习的统计学习理论逐步得到了发展和完善。 2 1 2v c 维与推广性的界 统计学习理论是主要研究小样本统计估计和预测的理论，对小样本情况下 的可学习性、正确性、过学习和欠学习、局部极小点等问题取得了较好的结果。 统计学习理论主要包括以下四个方而的内型2 】： ( 1 ) 经验风险最小化准则下，统计学习一致性的条件； ( 2 ) 在这些条件下，关于统计学习方法推广性的界的结论； ( 3 ) 在这些界的基础上建立的小样本归纳推理准则： ( 4 ) 实现新的准则的实际算法。 统计学习理论中，v c 维和推广性的界是两个关键的核心概念，具有很重要 的指导意义。 v c 维( v a p n i k c h e r v o n e n k i sd i m e n s i o n ) 是为了研究学习过程一致收敛的 速度和推广性而定义的有关函数集学习性能的指标。在分类问题中，指示函数 ( i n d i c a t o rf u n c t i o n s ) 集的v c 维的直观定义是【l 】：对于一个指示函数集，如果 存在h 个样本能够被函数集中的函数按所有可能的2 6 种形式分开，则称该函数 集能够把这h 个样本打散( s h a t t e r e d ) ；一个函数集的v c 维就是它能够打散的 最大样本数目h 。若函数集能打散任意数目的样本，则该函数集的v c 维是无 穷大。实函数集的v c 维可以通过引入阈值转化为指示函数集来定义。v c 维 反映了函数集的学习能力，v c 维越大则学习机器越复杂。 目前还没有计算任意函数集v c 维的通用理论，只知道一些特殊函数集的 v c 维【4 】：例如，在n 维实数空间中线性实函数的v c 维是n + l ，似，a ) = s i n ( a x ) 的v c 维则是无穷大。对于一些比较复杂的学习机器，如神经网络，其v c 维 除了与函数集( 神经网络结构) 有关外，还受到学习算法等因素的影响，要确 定就更加困难。如何计算给定的学习函数集的v c 维，仍然是统计学习理论中 有待解决的一个问题。 推广性的界是统计学习理论中的另一个核心概念，它反映了经验风险和实 际风险的关系。统计学习理论系统地研究了各种类型的函数集，对于二分类问 6 中山大学硕士学位论文r b f 核支持向量机的参数快速选择方法的研究与实现 题，有如下结论【4 】：对指示函数集中的所有函数( 包括使经验风险最小的函数) ， 经验风险尺唧( ) 和实际风险尺( c d ) 之间至少以1 - 呷的概率满足以下关系： 尺0 ) r e m p ( ( - o ) + 其中h 是函数集的v c 维，是训练样本数。 ( 2 - 4 ) 这结论从理论上指出，学习机器的实际风险是由两部分组成的：一部分 是经验风险( 即训练误差) ，另一部分称为置信范围，它和学习机器的v c 维及 训练样本数有关，( 2 4 ) 式中的结论通常可以简单地表示为【4 】： 尺o ) 尺唧o ) + f 了hl ( 2 - 5 ) 其中右侧的两项之和称为结构风险。 以上推广性的界的结论表明，在训练样本有限的情况下，学习机器的v c 维越高，即复杂性越高，则其对应的置信范围就会越大，从而可能导致真实风 险与经验风险之间的差别越大，这就是出现过学习现象的原副4 1 。推广性的界 的指导意义在于它指出了在机器学习的过程中仅最小化经验风险是不够的，还 要控制学习机器的v c 维以缩小置信范围，才能把实际风险控制在一个较低的 水平，以使得学习模型对未知样本具有较好的推广性。 在文献 2 中，v a p n i k 指出( 2 - 4 ) 式中推广性的界是最坏情况下的结论，在很 多情况下推广性的界是较松的。而且，推广性的界只在对同一类学习函数进行 比较时有效，可以指导从一个函数集中选择最优的函数，但在不同函数集之间 比较却不一定有效。寻找更好地反映学习机器能力的参数和得到更紧的推广性 的界是统计学习理论今后的重要研究方向之一。 2 1 3 结构风险最小化准则 从上面关于推广性的界的结论可知，在训练样本有限时，经验风险最小化 原则是不合理的，一个合理的学习过程应该同时最小化经验风险和和置信范围。 在传统的学习方法中，选择学习模型和算法的过程就是调整学习机器的置信范 围的过程【2 1 ，如果模型比较适合现有的i ) i l 练样本，则在学习过程中使经验风险 7 中山大学硕士学位论文r b f 核支持向量机的参数快速选择方法的研究与实现 最小化就可以得到满意的结果。很多传统学习方法因为缺乏理论指导，导致在 选择模型时很大程度依赖于使用者的经验和技巧，不容易取得置信范围合适的 学习模型，因此得到的结果具有很大的不确定性。 统计学习理论提出了一种新的策略，即把函数集s - - j ( x ，c o ) 构造为一个函数 子集序列s cs ，c cs 。c ，使各个子集按照v c 维的大小排列，即： h h ，h 。通过在每个子集中寻找最小经验风险，在子集间折衷考 虑经验风险和置信范围，通过使得推广性的界最小来取得实际风险的最小值， 这种思想称为结构风险最小化归纳准则( s t r u c t u r a lr i s km i n i m i z a t i o ni n d u c t i o n p r i n c i p l e ) 【4 1 。文献 2 指出了合理的函数子集结构应满足的条件以及在结构风 险最小化准则下实际风险收敛的性质。文献 4 】中给出了结构风险最小化的一个 示意图，如图2 1 所示。 风险 欠学习过学习 图2 1 结构风险最小化示意图 函数集子集：s t c 毋c 而 v c 维：h i 垃j i l j v a p n i k 在文献 2 中指出实现结构风险最小化原则有两种方法： 第一种方法是在设计学习机器时先确定一个v c 维为某个 + 的容许函数集， 然后在学习过程中使经验风险最小化。对于给定的数量为，的训练样本集，h 的值决定了学习机器的置信范围 等l 。如果设计了一个过于复杂饵口v c 维 中山大学硕士学位论文r b f 核支持向量机的参数快速选择方法的研究与实现 过高) 的学习机器，置信范围将会很大，这时即使可以把经验风险最小化为零， 它的实际风险仍可能很大，即产生了过学习现象；如果构造的学习机器v c 维 过小，则又难以逼近训练样本，容易造成欠学习。神经网络方法首先确定网络 结构，相当于确定了学习机器的置信范围，然后在训练过程中使经验风险最小 化，实现的是第一种方法。 另一种方法是设法保持经验风险固定，并最小化置信范围。支持向量机方 法实际上就是这种思想的具体体现。在第一种方法中，选择不同的学习机器结 构对置信范围造成的影响很大且常常难以控制。支持向量机解决了这个问题， 是一种具有较高的通用性的学习机器。支持向量机的思想和方法将在下节中作 详细介绍。 2 2 线性支持向量机 支持向量机( s v m ) 是基于统计学习理论，实现了结构风险最小化准则的 一种通用机器学习方法，是统计学习理论中最实用的成果。s v m 的核心内容是 在1 9 9 2 到1 9 9 5 年间提出的，目前仍处于快速发展和完善的阶段，它的思想对 机器学习领域产生了重大的影响。 s v m 的基本思想从线性可分的两类样本的最优分类面发展而来。通过把输 入空间中的向量映射到高维特征空间和引入核方法，s v m 解决了线性不可分的 两类样本的分类问题；s v m 一般通过构造和组合多个s v m 二分类器的方法来 解决多分类问题。这些扩展手段使s v m 分类器成为一种通用性高，适应性广， 效果较好的分类器。 2 2 1 最优分类超平面 s v m 方法的基本思想是从最优分类超平面思想发展而来的，最优分类超平 面的思想可以通过二维平面中的最优分类直线的情况来说明，如图2 2 所示。 9 中山大学硕士学位论文r b f 核支持向量机的参数快速选择方法的研究j 实现 图2 2 二维平面中线。陛可分情况下的分类直线 图图2 2 中空心小圆圈和空心小正方形分别代表两类样本，这两类样本在 二维平面中是线性可分的，有无数条直线可以把它们无错地分开。如图2 2 所 示，( a ) 和( b ) 中的直线都可以把两类样本正确分开，那么，这两条直线中哪一条 更适合作为这两类间的分隔线呢? 根据s v m 的基本思想，认为最优分类线不 但要把两类样本无错分开，还要使这两类之间的分类间隔最大。分类间隔指的 是经过两类中离分类线最近的样本且平行于分类线的两直线之间的距离，如图 2 2 ( a ) ( b ) 中的虚线所示，两条平行虚线之间的间隔就是对应分类线的分类间隔。 采用这个准则立刻可知，尽管图2 - 2 ( a ) 中的分类线的数学表达式可能更加简单， 图2 - 2 ( b ) 中的分类线才是最优的分类直线，因为它使两类样本间的分类间隔最 大。处在图2 - 2 ( b ) d ? 两条虚线上的样本称为支持向量。 使分类间隔最大实际上就是对学习机器的置信范围的控制，这是支持向量 机的核心思想之一。统计学习理论中，有如下定理： 定理2 1 【2 1 设在，z 维空间中，所有样本分布在一个半径为r 的超球内，则 所有分类间隔为的超平面集合的v c 维h 以下面的不等式为界： 五m i n f 等 ，z + - c 2 6 ， 在n 维空间中，所有超平面的集合的v c 维是n + l ，从定理2 1 则可以得知， 以维空间中间隔分类超平面集合的v c 维可以比n + l 更小。s v m 思想要求在 1 0 中山人学硕士学位论文r b f 核支持向量机的参数快速选择方法的研究与实现 线性可分的情况下使分类间隔尽可能大，也就是使对应超平面集合的v c 维 的上界尽可能小，从而实现结构风险最小化准则中对置信范围的控制；在非线 性可分的情况下，则是在控制错分训练样本数量( 即控制经验风险) 的同时最 小化置信范围，因此，s v m 体现了上节中讨论的结构风险最小化原则的第二种 实现方法【2 1 。 2 2 2 线性支持向量机的基本思想 线性支持向量机包括线性可分和近似线性可分两种情况，根据文献 3 和文 献 1 0 1 等，本文归纳得到线性支持向量机思想的一种较简洁描述如下： 假设训练样本集d 是含有z 个n 维向量的二类样本集： d = ( 吒，以) lk 1 ，2 ，z ) ，砟r n , 儿 + 1 ，一1 ) )( 2 - 7 ) 在n 维空间中的一个超平面可以表示为( 饥6 ) ，其中1 _ o 是和超平面正交的一个疗 维向量，b 是偏移常量。超平面砷+ 6 将样本正确分成两类，当且仅当： (，os-xz、)+bof胪“(2-8)b 【( 葺) + 0 fy z = 一1 如果限制样本和超平面的最小距离为1 i t o l ，则得到 ：耋；+6三二if矿y乃i=：+一1-i-b 1， c 2 9 ， 【( 葺) 一 矿乃= 一l 、7 也即 咒 ( 葺) + 6 】1 v i ( 2 1 0 ) 使得训练集中两类样本的分类间隔取得最大值的超平面就是最优分类超平 面，两类样本的分类间隔是 獭沏=min警一蚓m胪axxllyz=+1叫掣= 击o j1 2 一高= 击亿 、7 i i z “一1 ) l 1 2i 1 2i 1 2 、7 因此，寻找最优分类超平面的问题相当于： m i n j m i z e _ ioj-2(2-1 2 ) s t ：咒 ( 吐，薯) + 刎1 v i 中山大学硕士学位论文r b f 孩支持向量机的参数快速选择方法的研究与实现 两类样本近似线性可分的情况即训练集中的两类样本有少量融合和交叉， 不能被一个超平面严格无错误地分开。在这种情况下，上述约束条件需要作一 些修改，在条件中引入松弛变量轮o ，i = 1 ，2 ，寻找最优分类超平面的问 题相应地转化为如下问题： m i n i m i z e ( 1 ) 咒 ( ) + 6 1 一毒 ( 2 1 3 ) ( 2 ) 磊0 其中的c 是惩罚参数，选择较大的c 值相当于增大错分样本的代价。对于上述 优化问题，其最优解可通过构造拉格朗日函数并求解它的对偶问题的解得到， 上述问题可以转化为如下的二次规划问题： m i n i m i z e 三( ，b ，反) = o t i 一+ z z a ，a j y i y ，( 薯x j ) ( 2 1 4 ) f = li = l ，= l s t ： ( 1 ) o 0( 2 1 6 ) 1 2 中山大学硕士学位论文r b f 核支持向量机的参数快速选择方法的研究j j 实现 对输入向量x ，通过最优分类超平面可以预测其所属类别为： ，( x ) = s i g n ( o ) o x + b o ) = s i g n (口? m ( 葺x ) + 6 。)( 2 1 7 ) s u p p o r tv c e t o b 2 3 非线性支持向量机 在很多情况下，两类样本并不是线性可分的。当给定的训练样本集不能用 一个超平面线性分开或近似线性分开时，s v m 方法利用非线性映射把输入样本 映射到高维空间来解决可分性问题，具体方法如下所述【3 】： 首先构造一个从输入空间到特征空间z ( z 的维数一般大于刀) 的一个映 射：r ”i - - ) z ，然后把输入样本向量劫映射到z 中，最后在特征空间z 中寻找 一个可以把输入样本的像点o ( x 3 线性分开的分类超平面：这相当于在输入空间 中的一个非线性分类面。 需要解决的问题是如何构造一个合适的高维特征空间。一个合适的特征空 间的维数可能非常大，从而导致计算量和存储空间都会超出可接受的范围。幸 运的是，在特征空间中求解二次规划问题( 2 1 4 ) 以及进行分类预测( 即计算( 2 1 7 ) 式) 时，都只用到了两个向量的内积形式。因此，如果可以通过计算两个输入 向量而和而的某个函数来求得特征空间中这两个向量的像和0 的内积， 即找到函数k 使得 g ( x f ，x ) = o ( x f ) 。o ( x ) ( 2 - 1 8 ) 那么，则可以不直接计算西，甚至可以在不知道的具体形式的情况下，通过 使用函数k 来构造特征空间中的最优分类超平面的解。满足( 2 1 8 ) 式的函数k 称为核函数。选定了合适的核函数后，只需要将线性支持向量机的相关公式中 两个输入向量的内积形式劫换成核函数形式k ( x i ，x 3 ，再进行求解即可。此 时需要求解的二次规划问题( 2 1 4 ) 转化为： m i n i m i z e ，1， l ( r o ，b ，口) = q 一去吒巳咒乃k ( 葺，_ ) ( 2 1 9 ) i = l j j = l s t ： ( 1 ) 0 口f c 1 3 中山大学硕士学位论文r b f 核支持向量机的参数快速选择方法的研究与实现 ， ( 2 ) 口，y i = o 同时，在特征空间中的线性分类决策函数( 2 1 7 ) 也变为输入空间中的一个非 线性分类决策函数： m 问劬( s u p p o r tv e 相c t o r s 删纠 仁2 。， 一， 早在1 9 0 9 年，m e r c e r 就从数学上证明了正定核函数存在和判定的充分必要 条件，即著名的m e r c e r 定理，所有满足m e r c e r 定理的函数都对应着某个特征 空间的核函数。与核函数相关的一个概念是核方法，一般来说，在含有点积的 任何算法中，用核函数运算来代替点积运算的方法就可以称为核方法。核方法 从理论上为训练学习机器提供了一种系统而有原则的方法，它的应用范围十分 广泛。 通过选用不同的核函数k ，可以构造出输入空间中任意形状的非线性分类 超平面。以下是几个常用的核函到2 】： ( 1 ) 线性核 线性核函数的形式是： x ( x f ，z ) = x f x j ( 2 2 1 ) 实际上，线性核函数就是原输入空间中的点积，也即到原输入空间的恒等映射。 ( 2 ) 多项式核 多项式核函数的形式是： x ( x f ，x j ) = ( ( x f x ，) + c ) 。，c 0 ( 2 - 2 2 ) 其中d 为任意正整数。当c 0 时，称为非齐次多项式核，当c = 0 时，称为齐次 多项式核。 ( 3 ) 径向基函数( r b f 核) 径向基函数( r a d i c a lb a s i sf u n c t i o n ) 又称高斯核函数，其形式为： 叫一p ( 一学 仁2 3 ， 其中盯为径向基半径，在本文中，为了讨论的一致性，考虑如下形式的径向基 1 4 中山大学硕上学位论文r b f 核支持向量机的参数快速选择方法的研究与实现 函数： k ( x ，工) = e x p ( - 7 x ，一x 1 2 ) ( 2 2 4 ) 即以参数y ：去代替了参数盯，它本质上和( 2 2 3 ) 形式的径向基函数是完全一样 盯 的。 ( 4 ) s i g m o i d 核 s i g m o i d 核函数的形式为： k ( _ ，一) = t a n h ( r ( x ，。x ，) + c ) ( 2 - 2 5 ) s i g m o i d 核虽然不是正定核，但在某些应用场合却非常有效。 2 4 多类支持向量机 经典支持向量机算法只是针对二分类问题，而在实际应用中需要解决的常 常是多分类问题，多类支持向量机是s v m 领域内的研究热点之一。现有的多 类s v m 算法主要可以分为两类5 】： ( 1 ) 通过构造一系列的二类s v m 分类器，然后将其按某种规则组合起来， 以实现多分类的问题。 ( 2 ) 将多个分类超平面参数求解合并到一个最优化问题中，通过求解该最优 化问题，一次性实现多分类。 大部分经典的多分类s v m 算法都是第一类方法，这也是二分类s v m 算法 比较自然的扩展方式。第二类方法的一次性求解方式看似直接，但其对应的最 优化问题的求解复杂性很高，在运算量上比第一类方法要大很多，且其分类的 精度与第一类方法相比并没有优势。当训练集较大时，第二类方法的求解速度 和精度问题会更加突出。因此，现在实用的多分类方法一般都是第一类方法， 常见的几种通过构造多个二分类器来实现多分类s v m 算法如下： ( 1 ) “一对一”方法 一对一方法( 1 - v s 1a p p r o a c h ) 的基本思想是对训练集构造所有可能的二类 s v m ，对于n 分类问题，共需要构造n m 1 ) 2 个s v m 分类器，每个分类器 仅是在n 类中的两类样本上进行训练。一对一方法采用投票法( m a x w i n ) 进 行分类，对于一个测试样本x ，需要分别用所有的n m 一1 ) 2 个分类器进行分 1 5 中山大学硕士学位论文r b f 核支持向量机的参数快速选择方法的研究与实现 类，每个分类器判定测试样本所属的类将得到一票，最后得票最多的类成为输 出的分类结果。 一对一方法的优点是训练算法简单，容易实现，分类效果也较好。缺点是 对每个测试样本，要用很多不适当的分类器来测试，可能给投票造成误差，整 个模型趋于过学习。另外，分类器的数目随着类数量的增加而急剧增加，导致 测试时所需要的时间也随之增大。投票法可能出现多个类得票数相等的情况， 无法很好地作出决策。但由于一对一方法简单明了，仍然是被广泛使用的。为 了改进一对一方法的缺点，研究者们提出了一系列办法，如消除不适当的分类 别6 1 ，增加后验概率估算【7 1 等。 ( 2 ) “一对其余”方法 一对其余方法( 1 - v s r e s ta p p r o a c h ) 的基本思想是对于n 分类问题，构造 n 个二分类器：第i 个分类器把第i 类样本作为正类样本，而把其余所有类的 样本一起作为负类样本来训练分类器。在分类时，把待分类样本用所有n 个分 类器都计算一次，取输出值最大的分类器的序号作为分类结果。 一对其余方法的优点是需要训练的s v m 个数较少，分类速度相对比较快。 缺点是存在不可分区域，有可能某些测试样本同时属于多类或不属于任何一类 的情况。文献 8 中的方法通过组合一对其余方法和一对一方法，增强了分类的 精度。 ( 3 ) 基于有向无环图的方法 为了解决一对一方法在分类时要使用n x ( n 1 ) 2 个分类器，分类速度较慢， 且存在不可分区域的缺点，文献 9 提出了d a g s v m 算法，采用一种称为有向 非循环图( d a g ，d i r e c t e da c y c l i cg r a p h ) 的分类器组织形式。该方法把n x ( n 1 ) 2 个分类器组织成n 1 层的三角形结构，如图2 - 3 ( a ) 所示。在分类时，待 测样本从位于图的根结点处的二分类器开始，若这个结点将测试样本分为j 下类， 则排除这个结点的负类，每经过一个结点，都排除掉一类，然后相应进入下一 层的某个结点，直到根结点，位于根结点的分类器的分类结果就是最终的分类 结果。对每个样本，d a g s v m 方法只需要经过n 1 个分类器测试即可得到所 属类别。 文献 1 0 】和文献 1 1 针对d a g s v m 中层次过多，容易造成累积误差的缺点， 1 6 中山大学硕士学位论文r b f 核支持向量机的参数快速选择方法的研究与实现 进一步提出了一个a d a p t i v ed a g ( a d a g ) 方法及其改进形式，该方法把n 1 个二分类器组织成一个倒三角形结构，如图2 3 ( b ) 所示，分类时采用类似锦标 赛的方式，从最上层开始，该层的每个分类器依次对待测样本进行分类，每个 分类器的分类结果传递到下一层，决定了下一层需要采用哪些分类器；位于最 下层的一个分类器的输出就是最终的分类结果。a d a g 方法比d a g s v m 方法 减少了正确类别和其它类别的比较次数，因而降低了积累误差。