（计算机应用技术专业论文）支持向量机及相关理论研究.pdf

i - 飞 l j矗fbll j 辽宁师范大学硕士学位论文 摘要 支持向量机( s v m ) 技术是由v v a p n i k ! l j 于2 0 世纪9 0 年代中期提出的一种能处理 非线性分类、回归等机器学习问题的新模型。近几十年其理论研究快速成熟，实际应用 也被越来越多的领域重视。传统分类方法是从归纳到演绎的分类过程，面对一些多维非 线性问题往往效率低下，测试精度不高；而s v m 则简化分类过程，用训练数据到测试 数据的转导推理( t r a n s d u c t i o ni n f e r e n c e ) 代替传统方法【2 】。s v m 模型只需要确定少数几 个参数即可确定决策函数，其他参数可以根据经验固定选择；而且时间复杂度尤其是空 间复杂度取决于支持向量的数目，而不是属性维数，对比以前的分类方法，缩短分类时 间，减少存储空间。 ， 本文所做的工作主要围绕s v m 用于分类问题开展，研究成果分为下面两个部分： l 、针对当前模糊支持向量机( f s v m ) 使用特征空间样本与类中心之间的距离构建隶 属度函数的不足，首次利用熵的不确定性定量化度量特征和蚁群算法( a c 0 ) 的智能性， 与f s v m 模型结合，提出一种基于熵和a c o 的f s v m 新方法( e a f s v m ) 。求得的聚类 中心和隶属度能更准确的反映数据本身的特点，提高测试精度。对比s v m 和f s v m ， e a f s v m 模型测试精度较高，尤其对多类数据、大规模数据具有较好的分类能力。 2 、由于支持向量机( s v m ) 的有效性依赖于对数据信息获取的准确性，针对传统 s v m 模型对数据信息考虑单一导致分类精度不高、泛化能力不强的问题，结合概率分 布特性和等价类关系，提出了一种双系数控制分类的新模型。以双系数方式改进传统参 数，优化s v m ，为每一个样本同时赋予概率值和等价类系数，充分挖掘数据信息内在 规律和联系。该模型能有效利用数据信息，与传统s v m 、f s v m 和r s v m 相比有较高 的测试精度，能有效提高分类能力，具有较高鲁棒性。 关键词：支持向量机；熵：蚁群算法：概率：等价类 s u p p o r t v e c t o rm a c h i n em o d e la n ds e v e r a lr e l a t i v et h e o r yr e s e a r c h a b s t r a c t t h ev e c t o rs u p p o r tm a c h i n e ( s v m ) t e c h n o l o g yi sal l e wm o d e lw h i c hi sp r o p o s e db yv v a p n i ki nt h em i d9 0 s t od e a lw i 【t ht h en o n 1 i n e a rc l a s s i f i c a t i o n ，r e g r e s s i o na n do t h e rm a c h i n e l e a r n i n gp r o b l e m t h et h e o r yr e s e a r c hd e v e l o p sr a p i d l y ，a n dm o r ef i e l d sp a y a t t e n t i o nt ot h e a c t u a la p p l i c a t i o n t r a d i t i o n a lc l a s s i f i c a t i o nm e t h o d w h i c hi sf r o mt h ei n d u c t i o nt od e d u c t i o n ， f a c e sp r o b l e m so fl o we f f i c i e n c ya n dp r e d i c t i v ea c c u r a c yw h e nd e a lw i t hm u l t i - d i m e n s i o n a l n o n l i n e a rc o n d i t i o n w h i l et h es v ms i m p l i f i e st h ec l a s s i f i c a t i o np r o c e s sb ya d o p t i n g t r a n s d u c t i o ni n f e r e n c eb e t w e e nt h et r a i n i n gd a t aa n dt e s td a t a ，o n l yaf e wp a r a m e t e r sa r e n e e d e dt od e t e r m i n et h ed e c i s i o nf u n c t i o ni ns v mm o d e l ，a n do t h e rp a r a m e t e r sc a nb ec h o s e n b a s e do ne x p e r i e n c e t i m ec o m p l e x i t ye s p e c i a l l ys p a t i a ld e g r e e ，w h i c hc o m p a r e dt ot h e p r e v i o u sc l a s s i f i c a t i o nw a y s ，d e p e n d i n gn o to nt h ea t t r i b u t ed i m e n s i o n ，b u to nt h en u m b e ro f s u p p o r tv e c t o r s ，s h o r t e n st h ec l a s s i f i c a t i o nt i m ea n dr e d u c e ss t o r a g es p a c e 1 1 沁l a t i v et ot h ed e f e c to ff u z z ym e m b e r s h i pa saf u n c t i o no fd i s t a n c eb e t w e e nt h ep o i n t a n di t sc l a s sc e n t e ri nf e a t u r es p a c ef o rs o m ec u r r e n tf u z z ys u p p o r tv e c t o rm a c h i n e s ，an e w f s v mw h i c hb a s e do ne n t r o p ya n da c o ( e a f s v m ) i sf i r s tp r o p o s e d e x p l o i t i n ga d v a n t a g e o fe v a l u a t i o no fe n t r o p ya n di n t e l l i g e n c eo fa n tc o l o n yo p t i m i z a t i o n ( a c o ) ，e a f s v m e n h a n c e st h ec l a s s i f i c a t i o n c a p a b i l i t y a n dm a k e sc l u s t e r i n gc e n t e rm o r es u i t a b l ea n d m e m b e r s h i pm o r ea c c u r a t e e x p e r i m e n ts h o w st h a tt h ee a f s v m h a sab e t t e rp r e c i s i o na n d c l a s s i f i c a t i o np e r f o r m a n c e ，e s p e c i a l l yt om u l t i - c l a s sa n dl a r g es c a l ed a t e s 2 t h ee f i f e c t i v e n e s so fs v mm o d e ld e p e n d so na c c u r a c yo fa c q u i r i n gt h ei n f o r m a t i o no f d a t a c o n s i d e r i n gt h el o wp r e d i c t i v ea c c u r a c ya n dp o o rg e n e r a l i z a t i o nc a p a c i t yo fs v m c a u s e db ys i m p l ym i n i n gd a t a , an e wm o d e li sp r o p o s e d c o m b i n i n gw i t hp r o b a b i l i t y d i s t r i b u t i o na n de q u i v a l e n c ec l a s si n f o r m a t i o na m o n gd a t a , t h i sm o d e lo p t i m i z e s t h e t r a d i t i o n a ls v mb ya d o p t i n gd o u b l ec o e f f i c i e n t st op r o m o t et h ec a p a b i l i t yo fa c q u i r i n g i n f o r m a t i o n e a c hi n s t a n c ew i nb ea s s i g n e dt w oc o e f f i c i e n t so fp r o b a b i l i t yv a l u ea n d e q u i v a l e n c ec l a s s t h ee x p e r i m e n to nc o m p a r i n gw i t hs v m ，r s v m a n df s v mi l l u s t r a t e st h e n e wm o d e ln o to n l yc a nu t i l i z ei n f o r m a t i o ne f f e c t i v e l yb u ta l s oa s s u r ear e m a r k a b l ep r e d i c t i v e a c c u r a c ya n dc l a s s i f i c a t i o nc a p a b i l i t y ，a n db em o r e r o b u s t k e yw o r d s ：s u p p o r tv e c t o rm a c h i n e ( s v m ) ；e n t r o p y ；a c o ；p r o b a b i l i t yd i s t r i b u t i o n ； e q u i v a l e n c e i i l，ia，lf，) 辽宁师范大学硕十学位论文 目录 摘要i a b s t r a c t i i l 绪论1 1 1 研究背景及意义1 1 2 国内外研究现状和发展趋势2 1 3s v m 中常见的几种算法3 1 4 本文的主要内容4 2 支持向量机模型5 2 1 统计学理论和v c 维【3 们5 2 2 结构风险最小化6 2 3 核函数【3 1 1 7 2 4 支持向量机模型7 2 4 1 支持向量机模型基本思想7 2 4 2s v m 模型公式推导过程9 2 5s m o 13 2 5 1s m o 概述l3 2 5 2s m o 算法的基本框架图1 4 2 5 3s m o 优化过程1 5 2 6k k t 条件推导过程l7 3 一种基于熵和a c o 的f s v m 新方法1 9 3 1 引言1 9 3 2f s v m 基本理论2 0 3 3 基于熵和a c o 的f s v m 新方法2 0 3 3 1 基于熵和a c o 的f s v m 理论模型2 0 3 3 2 蚁群聚类算法2 1 3 3 3 熵权隶属度_ 2 3 3 4 实验设计2 4 3 5 小节2 7 4 结合概率和等价类的双系数s v m 2 8 4 1 引言2 8 4 2p r s v m 的提出2 8 支持向量机及若干相关理论研究 4 2 1p r s v m 训练集2 9 4 2 2p r s v m 模型2 9 4 3 具体实现31 4 3 1 聚类中心和类数的确定【4 i 】3l 4 3 2 主体数据与外围点噪声数据的检测3 2 4 3 3 为每一个数据点分配概率值和等价类系数3 2 4 4 实验设计及结果3 3 4 5 小节3 6 结 论3 7 参考文献3 8 攻读硕士学位期间发表学术论文情况4 l 致谢4 2 辽宁师范大学硕士研究生学位论文 1 绪论 1 1 研究背景及意义 分类问题是数据挖掘方向一个很重要的方面。最原始处理线性可分两类分类问题所 用的方法是感知器口“1 。感知器的原理是找到使j 下类和负类尽量分开的平面。m i n s k y 和 p a p e r t b 3 在随后指出了由于线性可分问题限制导致的感知器不能解决的一些问题。为了 克服感知器的线性问题限制，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 v m ) 方法凸刮。支持向量机利用s r m 原则和核函数，将输 入数据映射到高维空间，使在低维空间线性不可分的两类分类问题转化成高维空间线性 可分问题，在很大程度上解决了传统机器学习中的线性不可分、维数灾难及局部极小等 问题。 s v m 能够提高学习机的推广能力，即使由有限数据集得到的判别函数对独立的测试 集仍能够得到较小的误差，而且它的求解的过程可以看作是解决一个凸二次优化问题， 能够保证找到的极值解就是最优解。s v m 理论在解决分类和回归问题上是目前较新、 较实用的部分，主要内容在1 9 9 2 年到1 9 9 5 年逐渐成熟，近年来该理论发展闩益完善， 且被许多领域广为重视和应用。经过近2 0 多年的发展和应用，支持向量机已经在算法 研究、设计和实现方面有许多突破性改进，主要围绕以下两个方面： 二是如何有效的将两类分类问题扩展到多类分类的问题，如l - v 一1 、1 - v a 、d a g s v m 。” 等。s v m 寻找能使两类分开的最大间隔的最优超平面，然而在实际应用中，分类器经常 处理多类问题n0 1 。目前已经提出了若干将两类分类方法拓展成多类分类的技术，例如 v a p n i k 畸刮提出的o n e v e r s u s r e s t ( 1 v r ) 方法。该方法将每种数据集单独分成一类，单 独构造两类分类器，将属于该类和剩下的不属于该类的数据分开，也就是所有数据分成 两类。而由k n e r r 等人提出的o n e v e r s u s o n e 方法n 2 1 是针对每个数据集两两分类，为每 一对数据构造分类器。第三种常见的将两类分类器扩展成多类分类器的方法是 d a g s v m s n 引，通过有向非循环图减少分类中的计算。 第二类是针对过适应性、对噪声数据和边缘数据敏感问题优化s v m 模型，如模糊 支持向量机( f s v m ) n 4 j 习针对每个输入数据对分类结果的不同影响，得到不同的惩罚 值，提高了支持向量机的抗噪性，其缺点是隶属值计算不精确则整个模型失效；概率支 持向量机( p s v m ) d 砌分配概率值为每一个样本，体现样本间概率分布特性，但是当数 据概率分布差异不大时该算法区分样本点不明显；粗糙支持向量机( r s v m ) n 引，考虑 支持向量机及相关理论 数据的等价性信息，将粗糙集的思想结合进s v m ，但是支持向量机要承担属性约简算 法本身产生的条件限制和信息损失。 s v m 优点是训练相对简单，不需要大规模优化，便于处理高维数据，能够调和分类 复杂度和错分率，具有学习能力，模型还具有较强泛化性能。然而随着研究的深入，该 算法存在的一些问题如：训练算法速度慢，算法复杂而难以实现，s v m 方法中如何根 据具体问题选择适当的核函数和其他参数也没有理论依据，而只是靠经验累积或者是常 用参数，测试阶段运算量大等问题等也对该算法的应用研究提出挑战；有关s v m 算法 的某些理论解释也并非完美。不论是s v m 知识体系本身还是其应用方向都有待更深入 更精确发展，用来研究的课题也是很多的。 1 2 国内外研究现状和发展趋势 按照s v m 模型本身的优化来讲，其研究方向可以分为：两类分类方法延伸至多类， 如d a g s v m 、k s v m ；提高s v m 计算速度，处理大规模数据问题，例如内点法、s m o 算法等；最优化技术改进或改造s v m 形式，简化其计算过程，如线性s v m 、l s s v m 等；根据结构风险最小化和支持向量机的某些新思想提出新算法，构造核形式；克服 s v m 对孤立点和噪声数据的敏感性研究，例如提出模糊支持向量机等方面开展。 p a w a nl i n g r a s ，c o r yb u t z u 引提出的基于1 一v - l 和1 一v - r 方法的多类粗糙支持向量机， 该方法将应用于两类分类问题的粗糙及泛化应用到多类分类问题中，利用粗糙集中边界 类的思想提纯数据，减轻噪声数据的影响。在允许存在一定错分率的条件下，能缩短传 统1 一v 一1 和1 v r 方法的训练时间，减少存储空间，并且在处理语义上有一定提高。 q i n gt a o ，g a o w e iw u ，j u ew a n 9 1 1 9 1 提出的基于l 1 准则补偿的一种软分类方法，将 适用于能用l l 准则补偿方法的算法进行了软化和泛化，较好的结合到g i l b e r t 算法，s k 算法和m d m 算法，首次解决了g i l b e r t 算法中两个软凸壳之间最近点对问题，和l 1 补偿 准则有相同的收敛性，在运算时间上l 2 软分类更具有优势，适用于大规模数据。 张学工教授是较早的将s v m 模型引入国内，介绍并研究其应用的学者之一。该篇综 述心们从统计学，( s l l t ) 角度出发，详细的介绍了s v m 理论框架、基本思想、特点和研 究发展现状，弓靛国内学者的对s v m 的广泛关注。 m i c h a e le 心等指出几何算法是直观且实用的解决某些优化问题的方法，总结了用最 近点对算法( n p a ) 减少凸包方法集合到s v m 分类方法中，能够精确有效的解决实际 的线性、非线性可分或不可分问题。 2 辽宁师范大学硕十研究生学位论文 h a n p a n gh u a n g 和y i h u n gl i u n 4 1 提出了s v m 在模式识别和数据挖掘应用方向存在 的问题，针对s v m 对边缘噪声点过于敏感的而引起的过适应性问题，提出了模糊支持 向量机( f s v m ) ，为训练集的每个正类和负类赋于相应的隶属度，并用o d m 算法检 测边缘噪声点，使主体和外围数据分开更好的进行数据预处理。试验表明该算法能够减 少噪声点的影响从而提高分类能力。 在模糊支持向量机的基础上，x i u - f e n gj i a n g ，z h a n gy i 和j i a n - c h e n gl v 心别等人认为 选取合适的隶属度是减少噪声点影响的主要因素，文章用一种新的模糊系数应用到非线 性模糊支持向量机，该系数在特征空间中计算并且用核函数表示，使得分类的测试精度 和泛化能力有一定提高。 李昆仑等人提出了一种模糊多类支持向量机模型心3 | ，引入模糊成员函数，针对每个 输入数据对分类结果的不同影响，赋予不同的惩罚值，在构造决策函数时，利用参数来 调节对分类结果影响很小的数据，算法泛化了f s v m ，并且具有良好的鲁棒性。 支持向量机在模式识别心4 2 引、函数逼近啪1 、时间序列预测、故障识别和预测心引、 水印心引、入侵检测眨鲫以中均有很好的应用。 l “。 1 3s v m 中常见的几种算法 支持向量机把分类问题和回归问题归结为一个约束最优化问题，特别是一个带有线 性约束的凸二次规划问题。相对应求解最优化问题有三类算法：无约束问题解法、内点 算法和求解大型问题的算法。其中求解无约束问题算法有基本无约束问题算法和牛顿一 条件预优共轭梯度法( n e w t o n p g g 算法) ；内点法是一类较新的有效的优化算法，常 用的内点法有原仿射尺度法和原一对偶算法；常规情况，常用内点算法解方程的方法， 但在实际处理具体问题时，由于存储和计算量两方面的要求，这些算法往往会失效，因 为这些算法都要存储与训练集相应的核矩阵，然后存储核矩阵所需的内存是随着训练集 中样本点个数l 的平方增长的。当样本点数l 以成千计时，所需的内存已相当大。例如， 当样本点数目超过4 0 0 0 时，存储核函数矩阵需要多达1 2 8 兆内存，而且算法往往包含 大量的矩阵运算，所需的运算时间往往过长m 1 。 而支持向量机中最优化问题是一类特殊的最优化问题，它们有一些良好的特性，如 解的稀疏性和最优化问题的凸性等。这些性质使得构造使用较少存储的快速专用算法成 为可能，求解大型问题的专用算法的一个共同特点是：将大规模的原问题分解成若干个 小规模的子问题，按照某种迭代策略反复求解子问题，构造出原问题的近似解，并使该 近似解逐渐收敛到原问题的最优解。事实上由于子问题的选取和迭代策略的不同，可以 有不同的算法，如c o r t e s 和v a p n i k 在1 9 9 5 年提出的选块算法( c h u n k i n g ) 、o s u n a 在 支持向量机及相关理论 1 9 9 7 年提出的分解算法( d e c o m p o s i n g ) 和j o h nc p l a t t 于1 9 9 8 年提出的序列最小最优 化方法( s e q u e n t i a lm i n i m a lo p t i m i z m i o n s m o ) 等。 “块算法”( c h u n k i n ga l g o r i t h m ) 基本思想是当去掉l a g r a n g e 乘子等于零的训练 样本不会影响原问题的解时，通常采用块算法。在给定的训练样本集中，若其中的支持 向量是已知的，寻优算法只需对支持向量计算权值( 即l a g r a n g e 乘子) 即可，可以轻 松排除非支持向量。但是实际上支持向量是未知的，于是用“块算法”的中心思想就是 通过某种迭代方式逐步排除非支持向量，保留支持向量从而计算权值。该算法大致过程 是：随机选取一部分样本构成训练集，找出其中的非支持向量，并用训练结果对剩余样 本进行检验，将不符合训练结果( 一般是指违反k k t 条件) 的样本( 或其中的一部分) 与本次结果的支持向量合并成为一个新的工作样本集，然后重新训练。如此重复下去直 到获得最优结果。 分解算法与快算法不同之处就在于它每次只更新若干个l a g r a n g e 乘子，而其他的乘 子保持不变，每次一个新的样本点加到工作集中就必须舍去另外一个样本点，迭代过程 只是将工作集之外样本点中“情况最糟糕的样本点 与工作集中的一部分样本点进行交 换，即使支持向量的个数超过工作集的大小也不改变工作集的规模。与块算法不同，该 算法的目的不是找出所有的支持向量，而是在相应的约束上解决问题，每次只针对很小 的训练子集求解。 作为经典算法的s m 0 是本文s v m 研究的核心技术，在后文会详细介绍。 1 4 本文的主要内容 本文第一部分是绪论，介绍了支持向量机研究方向和现状等等；第二部分介绍支 持向量机基础，尤其是本实验室研究的关键技术s m o 和k k t 条件等；第三部分介绍了 结合熵权系数和蚁群算法的一种新s v m 算法；第四部分是另一种结合了概率和等价类 的双系数s v m 模型；结论将在第五部分给出，总结支持向量机的优缺点和适用性。 4 辽宁师范大学硕士研究生学位论文 支持向量机模型 支持向量机有两项关键技术：利用s r m 原则设计具有最大间隔的最优超平面，在高 维特征空f b j 中设计线性最优超平面，利用核函数的技巧得到输入空间中的非线性学习算 法：第二项技术是核函数，也是目前很活跃的研究领域，核函数用非线性变换口将n 维 矢量空间中的随机矢量x 映射到高维特征空间，在高维特征空间中设计线性学习算法， 若其中各坐标分量间的相互作用仅限于内积，则不需要知道非线性变换e 的具体形式， 只要满足m e r c e r 条件的核函数替换线性算法中的内积，就能得到原输入空间中对应的 非线性算法。 2 1 统计学理论和v c 维啪1 统计学习理论是一种专门研究小样本的理论，能较好地解决小样本学习问题。基于 数据的机器学习，主要研究如何从一些观测数据( 样本) 出发得出目前尚不能通过原理分 析得到的规律，利用这些规律去分析客观，对未来数据进行预测。 统计学习理论就是研究小样本统计估计和预测的理论，主要包括四个方面： ( 1 ) 经验风险最小化准则下统计学习一致性的条件； ( 2 ) 在这些条件下关于统计学习方法推广性的界的结论； ( 3 ) 在这些界的基础上建立的小样本归纳推理准则； ( 4 ) 实现新的准则的实际算法。 其中，最有指导性的理论结果是推广性的界，与此相关的一个核心概念是v c 维。 为了研究训练学习过程一致收敛的速度和推广性，统计学习理论定义了一系列有关 函数集学习性能的指标，其中最重要的是v c 维( v a p n i k 2 - c h e r v o n e n ki sd i m e n s i o n ) 。在 模式识别方法中，v c 维的直观定义是：对一个指示函数集，如果存在h 个样本能够被 函数集中的函数按所有可能的2 办种形式分开，则称函数集能够把h 个样本打散：函数集 中，v c 维就是它能打散的最大样本数目h ，若对任意数目的样本都有函数能将它们打 散，则函数集的v c 维是无穷大，在有界实函数中，v c 维可以通过用一定的阈值将它转 化成指示函数来定义。 v c 维反映了函数集的学习能力，v c 维越大则学习机器越复杂( 容量越大) 。目前 尚没有通用的关于任意函数集v c 维计算的理论，只对一些特殊的函数集知道其v c 维。 比如在门维实数空间中线性分类器和线性实函数的v c 维是刀+ 1 ，i ( x ，口) = s i n ( o ：x ) 的 v c 维则为无穷大。对于一些较复杂的学习机器，v c 维除了与函数集关外，还受学习 支持向量机及相关理论 算法的影响，其确定更d n i b 难，对于给定的学习函数集，如何( 用理论或实验的方法) 计 算其v c 维是当前统计学习理论中有待研究的一个问题m 。 2 2 结构风险最小化 在传统基于数据的机器学习方法中，选择学习模型和算法的过程就是调整置信范围 的过程，如果模型和现有的训练样本相适应，调整置信范围的效果会很好，可是实际问 题中由于缺乏理论指导，置信范围的选择大多必须依赖先验知识和经验，造成了该过程 对使用者技巧与经验的过分依赖。认识到这种缺点，统计学习理论把函数集构造为一个 函数子集序列，在每个子集中寻找最小经验风险，在子集间折衷考虑经验风险和置信范 围，取得实际风险的最小，如2 1 所示。这种新方法我们称为结构风险最小化( s t r u c t u r a l r i s km i n i m i z a t i o n 口) 即s r m 准则。选择最小经验风险与置信范围之和最小的子集就可 以达到期望风险的最小。 实现s r m 有两种思路：一是在每个子集中求最小经验风险，然后选择使最小经验风 险和置信范围之和最小的子集，显然这种方法比较费时间，当子集数目很大甚至无穷的 时候此方法不能实现；另一种思路是设计函数集的结构，让每个子集的经验风险都尽量 小，例如设训练误差为0 ，只要让子集的置信范围最小，就可以办证该子集的最优函数 就是经验风险最小的函数。s r m 原则提供了一种不同于经验风险最小化的机器学习原则， 其关键就是找到合适的子集函数结构，可以不用一一计算就可以得到每个子集的最小经 验风险。而支持向量机很好的诠释了有序风险最小化思想。 风硷 欠擘习越学习 一：兰_ l i 一j 函散浆于集。s l c s # c s 。 v c 蛾l - t a 图2 1 结构风险最小化模型示意图 f i g 2 1s t r u c t u r a lr i s km i n i m i z a t i o nm o d e lg r a p h 6 辽宁师范人学硕七研究生学位论文 2 3 核函数日u 常用的满足m e r c e r 条件的核函数有多项式函数、径向基函数和s i g m o i d 函数等。本 实验室常用三种核函数做对比实验，处理不同的数据，三种核函数的效果各不一样，在 具体应用问题时，应结合数据特点选取合适的核函数 s v m 中不同的内积核函数将形成不同的算法： 一是多项式核函数： k ( x ，) = ( x 啦) + 1 9 ( 2 1 ) 所得到的是q 阶多项式分类器： 二是径向基函数r b f ： kx , x t ) 一e x p - 学 ( 2 2 ) 所得分类器与传统r b f 方法的重要区别是，这里每个基函数中心对应一个支持向 量，它们及输出权值都是由算法自动确定的。 三可以采用s i g m o i d 函数作为内积，即 k ( x ，一) = t a n h ( v ( 拙) + c ) ( 2 3 ) 这时s v m 实现的就是包含一个隐层的多层感知器，隐层节点数是由算法自动确定 的，而且算法也不存在困扰神经网络方法的局部极小点问题。 2 4 支持向量机模型 2 4 1 支持向量机模型基本思想 ( 1 ) 三条线的确定 图2 2s v m 基本模型 f i g 2 2s v mb a s i cm o d e l w 和x 为d 维向量，则如图，q 和皿分别表示为： 7 支持向量机及相关理论 h ：w x + b = k l 何2 ：掀+ 6 = k 2 调整表示方法： w x + b = k 丽_ + 一b ：一k( 2 4 ) 则中间h 表示为诫+ 石= 0 ，进一步简化模型，令b 为单位长度，则一、皿和h 分别 表示为： h i ： w x + b = 1 日：丽x + 万：一1 ( 2 5 ) ：诫+ 万：0 ( 2 ) 距离的表示 设x l h 。和艺h 2 ，按照公式( 2 5 ) ，计算q 和哎的距离为： 。+ b - ( w 、x 2 4 - b ) 。1 ( - 1 ( 2 6 ) 即似x 一矗) = 2 、。 也就是： 似五一叠) = 1 w i q 五- - x 2 土o s 0 ， ( 2 7 ) 从模型可以得出k - - x 2 i 和1 w i 方向一致，所以c o s o = l ，上式变为： m 。一i = 2 即x t - - x 2 1 2 两2 一般地，i w i 写成：而 ( 3 ) 分类问题 在最简单的两类分类问题里，在直线日。和马以外的点表示为： ! + 皇1 。 ( 2 9 ) w + b - 1 等号成立是点在日。和吼上。 为了方便表示，设 ，z ) 为一个点的二维属性，为某个点的个体属性，只 + l ，一l 是该点的类别属性。则上式可改写为： y i ( m + 6 ) 】l ( 2 1 0 ) 辽 。师范人学硕士研究生学位论文 要使和：把两类分的好，就要尽量使其距离大，即要i 一屯i3 南大，t g 就是1 w l 尽量小。 ( 4 ) 转化为对偶问题 根据上述转化，我们可以将分类问题看成是式如m i n l w i = m i n w 7 w 目标函数，求解 在约束条件y i ( w x i + 6 ) 1 下的最优解的问题。 利用l a g r a n g e 函数： ( w ，6 ，仅) = 去w 7 w 一a 。【( w + 6 ) 】一1 ) ( 2 ii ) 来确定参数w ，b 和仅。 ( 5 ) 对偶转化 因为上述问题有两个参数，般不直接解出上述l 式，而采用w o l f 对偶法，将，j 二 式改用全部用仅表示，从而对1 3 , 求解的方法。 在上式中，对w 和b 求解偏导，令其为零。 解得：兰：o ，婺：o wo o 反代入上式( 2 1 1 ) 中得到另一种表达式和约束条件，即对偶约束： 由詈_ o ，得到w = 善na 艄 ( 2 1 2 ) 则将最原始分类问题归纳到求解0 c 上，本文利用s m o 算法求解仅，进而实现s v m 模型的决策函数，确定分类最优超平面。下文将详细阐述如何用s m o 算法求解。 2 4 2s v m 模型公式推导过程 设给定的训练数据集为： x ，y ，) ，其中f _ l ，n ，相应的类标签为m = - 1 ，+ 1 ) 在线 性可分的情况下，s v m 能找到一个超平面来使两类的分类间隔最大这等价于解决下面 的规划问题 m i n 三w 7 w 2 s t ：m ( w x i + 6 ) l( 2 1 3 ) 通过引入l a g r a n g e 乘子口，可以把问题转化为其对偶问题： m 登q 一吉x x y , y j a , a j ( o ) “ j = li = 1 = 1 9 支持向量机及相关理论 s t ：y f 口l ，口f o ，扛1 ，n ( 2 1 4 ) 对于线性不可分情况，上述的最优分类面是不存在的，即s v m 无法将所有样本都被 正确分类，那么就必须“软化”对间隔的要求，允许部分样本点被错分，于是引入松弛变 量鲁和惩罚参数c 这时最优问题又可以表示为( s v m 的一种改进形式) ： m i n - 1w 7 w + c y 量 ， 一o s t ：0 黑誓+ ? 净1 _ 茧 ( 2 1 5 ) “茧0 ，f = l ，n 怕h w c 孝，是为了控制错误分类样本的数量c 作为s v m 中的唯一的自由参数，是分类 间隔的宽度和容许错分样本数目之间的一个折衷c 越大，对错分的惩罚程度越大，则分 类i 自j 隔越小，反之容许更多的被错分的样本，则分类间隔越大 ( 2 1 5 ) 式的对偶问题为： 嘤一吉y 。y j a i g r j ( x i x j ) “j = ii = l = 1 s t ：y ；a f = o ，o 口f c ( 2 1 6 ) 此时的决策函数可以表示为： ( 工) = s i g n ( w x + 6 ) = j i g 刀l 口，y ，( x ，x ) + 6 ( 2 1 7 ) i = l 对于非线性的情况，可以通过非线性映射将原始空间映射到高维特征空间。尽管在 原始空间是不可分的，但总可以找到一个合适的核函数k ( 葺工) 将数据映射到特征空间中 是可分的。这样( 2 1 7 ) 式变为： ( x ) = s i g n ( w x + 6 ) = j i g 门l 口f y f k ( x f x ) + 6l ( 2 1 8 ) 支持向量机是在最小化错分，同时最大化分类间隔的情况下获取最优分类面。 则该问题转化为求解0 c ，变量。通过s m 0 算法可以求解0 【j ，直至求出w = 0 c f y f x i 和 b 。 转化为二次规划问题，令 1 0 辽宁师范大学硕十研究生学位论文 f h ，= ( y j y j k ( x i ，x j ) ) u n 仪= ( 仅l ，仅j v ) 7 i y ：( 跏。y | ) 7 【y = ( ”，| ) 7 1 则公式( 2 1 6 ) 变为 竺日芝p 因为仅j ( y i ( w x i + 6 ) 一1 ) = 0 ，且仅，0 所以y f ( w x i + 6 ) 一1 = 0 通过仪，求解w ，通过k k t 求解b ，则判别函数可求。 此时的决策函数可以表示为： ( 2 1 9 ) 厂c x ，= s i g n ( w x + b ) = s i g n ( 兰口，乃c 砖x ，+ 6 c 2 2 0 ) i = 1 厂( x ) = x + l 口，乃( 而x ) + 6l ( 2 法求解i f , ，将分解算法特殊到每次只求解两个解。 a t = ( 仪1 0 【玎) ，则0 【t 0 【= 0 【2 f = l 她铲巴引 贝0a l = 0 【l 啊l + 仪2 7 砭l + 仪3 h 3 , + + 0 c 一1 0 c t h = ( 口l ，a n ) 仪t0c=c口。，兰：1=口。仅。+口z仅2+口，0c肝 按照上述条件，分解公式( 2 2 1 ) 得到如下： h ：( h b b 、h n b l l ( 2 2 1 ) 鬣 算八j 0 仅 一仅 ，_ s i l 用 仅 乖 一 厅仅 疗芦 = 口 中其 、 驯 删 h h 支持向量机及相关理论 其中，n 是未选中，b 是选中的数据点，若选中的数据点是q l ，仅2 ，则h 删表示只 有l ，2 其中的一个点，假设选取的点是仅l ，仅2 ，我们需要的是h 口b 和h s n 两种情况。 则分解函数变成： i m i n w ( q ) = 丢口t b h b b a b - - a r a ( e - h b n a n ) s t 口二y b + 口石y ，= o 2 2 2 10 a c p 假龇= a i = 0 【i ! h1 1 0 c1 2 i0 【i h 仅 因为a 2 = 仪；h2 2 0 c2 因为 2 i 仪i h2 2 a = 暾 日驴= ( y i y j k ( x i ，z 川开月 y ， 1 ，一1 l m i n ( c z l , e t 2 ) = 丢k l l a i ! + 圭k 2 2 0 c ；+ y l y 2 k 1 2 1 x l u , 2 - - ( 仅。地) 转化为：+ j ，t z 闰y i c ) 【i k l , + 耽0 c z 荟y ，0 c ，k z ， 胛 s t 仅l m + 0 c 2 耽= 一0 c f y f ( 常数) f - 3 0 v w ，“刀c ( 2 2 7 ) a 。 【， 求解出来，相应的仅p 根据公式( 2 2 4 ) 也求出来了。 至此，每次两个解析解就求出了带入到公式中，调整整体，若满足k k t 条件和目譬； 标函数，则改变值o c ? 删，a ! 删，否则继续寻找两个a 进行迭代。 2 5s m o 2 5 1s m o 概述 上文说到s v m 是一类特殊的最优化问题，一些特性，如解的稀疏性和最优化问题 的凸