（应用数学专业论文）支持向量机中若干优化算法研究.pdf

山东科技丈学硕士学位论文 摘要 摘要 支持向量机是一种新的机器学习方法， 本分类、回归预测、时间序列分析等领域。 已广泛应用于手写数字识别、人脸识别、文 设计实现该学习方法的有效优化算法是该领 域学者研究的重点。本文利用基于o l m a n g a s a r i a n 等人提出的解决支持向量机的若干优 化算法，分别对支持向量分类机、支持向量回归机和特殊结构支持向量机的特征选择问 韪进行了研究。 第一章主要介绍支持向量机的数学理论基础统计学习理论，支持向量机标准模 型、若干求解算法和研究方向、常用数据集和软件包及支持向量机的应用领域等。 第二章研究支持向量机分类算法，针对有效集算法不能有效求解非线性可分情形的 模型，提出基于s o r 的有效集分解策略求解支持向量机算法。 第三章研究支持向量机回归算法，将求解分类问题的有效算法推广到回归问题中来， 提出有效的牛顿型支持向量回归机和l a g r a n g e 支持向量回归机算法。 第四章讨论特殊结构的支持向量机，将其与特征选择相结合，给出了一种能自动进 行特征选择的最少核分类器。 第五章总结论文主要工作并给出对未来工作的展望。 关键词：支持向量机、统计学习理论、最优化方法、s o r 算法、a s v m 算法、l s v m 算法、牛顿型算法、l s v r 算法、特征选择、核函数 坐查型垫查兰堕主兰垡丝苎 ! ! ! ! ! ! ! ! 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 san o v e lm a c h i n el e a r n i n gm e t h o da n dh a sb e e n s u c c e s s f u l l ya p p l i e di n t ot h ef i e l do fd a t ac l a s s i f i c a t i o na n dr e g r e s s i o ns u c ha sh a n d w r i t t e n d i g i tr e c o g n i t i o n ，f a c er e c o g n i t i o n ，t e x tc l a s s i f i c a t i o n ，r e g r e s s i o np r e d i c t i o na n dt i m es e r i a l a n a l y s i se t c h o wt od e s i g nt h ee f f i c i e n to p t i m i z a t i o na l g o r i t h m sf o rs o l v i n gs v m h a sb e c o m e a no p e np r o b l e m i nt h i sp a p e r , b a s e do nt h eo p t i m i z a t i o na l g o r i t h m sf u rs o l v i n gs v mw h i c h i sp r o p o s e db yo l m a n g a s a r i a ne ta 1 ，am o d i f i e ds v mc l a s s i f i c a t i o na l g o r i t h i n ，t w os v m r e g r e s s i o n ( s v g ) a l g o r i t h m sa n d am e t h o df o rf e a t u r es e l e c t i o no fm i n i m a lk e r n e lc l a s s i f i e r s a r ep r o p o s e dr e s p e c t i v e l y f i r s t l y ，w ei n t r o d u c et h em a t h e m a t i c a lt h e o r yo fs u p p o r tv e c t o rm a c h i n e ( s t a t i s t i c a l l e a r n i n gt h e o r y , s l t ) ，t h es t a n d a r dm o d e l s ，s o m ea l g o r i t h m sf o rs v m a n dt h ed e v e l o p m e n t a sw e l la ss o m ed a t a s e t s ，o p t i m i z a t i o ns o i t w a r e sa n ds o m ea p p l i c a t i o n so f s v m i nt h es e c o n dc h a p t e r , w ed i s c u s st h es v ma l g o r i t h m sa n dp r o p o s eas o r a s v m a l g o r i t h mi no r d e rt oi m p r o v et h ea s v ma l g o r i t h mf o rs o l v i n gt h en o n l i n e a r - s e p a r a b l em o d e l i nt h en e x tc h a p t e r , a ne f f e c t i v en e w t o n - t y p es v ra l g o r i t h ma n dal a g r a n g es v r a l g o r i t h ma l ep r e s e n t e db y m a k i n gu s eo ft h ec o r r e s p o n d i n ga l g o r i t h m sw h i c hw e r ep r o p o s e d f o r s v m i nt h ef o u r t hc h a p t e r , t h es p e c i a ls t r u c t u r a ls v m ( m i n i m a lk e r n e lc l a s s i f i e r ) i si n t r o d u c e d a n da ni m p r o v e m e n to ft h em i n i m a lk e r n e lc l a s s i f i e ri sp r e s e n t e dw h i c hp e r f o r mf e a t u r e s e l e c t i o na u t o m a t i c a l l y i nt h el a s tc h a p t e r , w es u m m a r i z et h ep a p e r sc o n t e n t sa n dp r o p o s es o m es u g g e s t i o n so f t h ef u t u r ew o r k 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 ) 、s t a t i s t i c a ll e a r n i n gt h e o r y ( s l t ) 、 o p t i m i z a t i o nm e t h o d s 、s o ra l g o r i t h m ，a s v ma l g o r i t h m 、l s v m 、n e w t o n t y p ea l g o r i t h m 、 l s v r 、f e a t u r es e l e c t i o n 、k e r n e lf u n c t i o n 声明 本人呈交给山东科技大学的这篇硕士学位论文，除了所列参考文献和世所公 认的文献外，全部是本人在导师指导下的研究成果。该论文资料尚没有呈交于其 它任何学术机关作鉴定。 硕士生签名：留p 。缱 日期： 西f r a f f i r m 喳l t i o n id e c l a r et h a tt h i sd i s s e r t a t i o n ，s u b m i t t e di nf u l f i l l m e n to ft h er e q u i r e m e n t sf o rt h e a w a r do fm a s t e ro fs c i e n c ei ns h a n d o n gu n i v e r s i t yo fs c i e n c ea n dt e c h n o l o g y , i s w h o l l ym yo w nw o r ku n l e s sr e f e r e n c e do fa c k n o w l e d g e t h ed o c u m e n th a sn o tb e e n s u b m i t t e df o rq u a l i f i c a t i o na ta n yo t h e ra c a d e m i ci n s t i t u t e s i g n a t u r e ： d a t e ： 哩附健 迅。ij 叼 1 绪论 支持向量机( s u p p o r tv e c t o rm a c h i n e s ，简称s v m s ) 是一种借助于最优化方法解决 机器学习问题的新工具，最早由v a p n i k 博士在1 9 7 9 年提出，当时没有得到重视。随后 v a p n i k 等人花了很长时间完善统计模式识别的基本数学理论，随着结构风险最小化原则 的提出，s v m 的理论基础基本完善，终于引起人们的关注。直到最近，它才成为一个研 究上的热点，并开始得到非常广泛的应用。在文本识别、人脸识别、三维图像识别、非 线性回归建模、数据压缩、时间序列预测、生物信息学、企业个人信用等级评定等各方 面的应用陆续得到报道。 1 1统计学习理论概述 在计算机智能化的过程中一个重要的方面就是要让计算机能有效的从现有实例中学 习出某种规律，以便能预测未来数据或者不能观察的事实，这就是机器学习【4 9 】。现有 机器学习方法共同的重要理论基础之一是统计学。传统统计学所研究的主要是渐进理论， 即当样本趋于无穷多时的极限性质。现有学习方法大多是基于此假设的，但现实中样本 往往是有限的，因此一些本来很好的学习机器却可能表现的不尽如入意。 与传统统计学相比，统计学习理论( s t a t i s t i c a ll e a r n i n g t h e o r y ，简称s t l ) 5 1 ，5 2 ，4 6 是一种专门研究小样本情况下机器学习规律的理论。早在上世纪六、七十年代v a p n i k 等 人就开始了这方面的研究，到了九十年代中期，随着其理论的不断发展和成熟，也由于 像神经网络等其他学习方法在理论上缺乏实质性进展，统计学习理论开始受到越来越广 泛的关注。 统计学习理论是建立在一套较坚实的理论基础之上的，其主要内容包含以下四个方 面： a 关于统计推断一致性的充分必要条件的一系列概念； b 在这些概念基础上的反映学习机器推广能力的界； c 在这些界的基础上建立的针对小样本数的归纳推理原则； d 实现这些准则的实际方法( 算法) 。 其中，核心内容是：v c 维，推广能力的界，结构风险最小化。 山东科技大学硕士学位论文 绪论 i i 1v c 维反映函数集学习能力的指标 模式识别方法中v c 维的直观定义是：对于一个指标函数集，如果存在h 个样本能 够被函数集中的函数按所有可能的2 6 种形式分开，则称函数集能把h 个样本打散；函数 集的v c 维就是它能打散的最大样本数目h 。也就是说，如果存在h 个样本的样本集能 够被函数集打散，而不存在有h + 1 个样本集能被函数集打散，则函数集的v c 维就是h 。 有界实函数的v c 维可以通过用一定的阈值将其化为指标函数来定义。 v c 维反映r 函数集的学习能力，v c 维越大则学习机越复杂，目前还没有通用的关 于函数集v c 维计算的理论。 i i 2 推广能力的界 统计学习理论系统地研究了各种类型的函数集的经验风险和实际风险之间的关系， 即推广能力的晃 5 l 】。关于两分类闯题，对于指标函数集中的所有函数( 包括经验风险 最小化( e m p i r i c a lr i s k m i n i m i z a t i o n ，简称e r m ) 的函数) ，经验风险8 。( 矿) 和实际风 险r ( 矿) 之间至少以l 一，7 的概率满足如下关系： 矗( 矽) 8 ( ) 十j h ( 1 n ( 2 n h ) + 1 ) - i n ( r 4 ) i ( 1 1 1 ) 。 _r 其中，h 是函数集的v c 维，, 是样本数。( 1 1 1 ) 式从理论上说明了学习机的实际风险 是由两部分组成的：1 、经验风险( 训练误差) ；2 、置信范围，它和学习机的v c 维及训 练样本数有关。可以简单的表示为： 胄( 矿) 震哦，( y ) + 中( 以) ( 1 1 2 ) 它表明在有限样本训练下，学习机v c 维越高，则置信范围越大，导致真实风险与经验 风险之间可能的差别越大。这就是为什么出现过学习现象的原因。 进一步的分析可以发现，当n h 较小时，置信范围中较大，用经验风险近似真实风 险就有较大的误差，用经验风险最小化取得的最优解可能具有较差的推广性；如果样本 数较多，h h 较大，则置信范围就会很小，经验风险最小化的最优解就接近实际的最优 解。 2 山东科技大学硕士学位论文绪论 1 1 3 结构风险最小化( s r m ) 从( 1 1 1 ) 式看到，经验风险最小化原则( e r m ) 在样本有限时是不合理的，我们 需要同时最小化经验风险和置信范围。统计学习理论提出了一种新的策略，即把函数集 构造为一个嵌套的函数子集序列，使各个子集按照v c 维的大小排列；在每个子集中寻 找最小经验风险，在子集间折衷考虑经验风险和置信范围，使得实际风险最小。这种思 想称作结构风险最小化( s t r u c t u r a l r i s k m i n i m i z a t i o n ，简称s r m ) 。可由图1 1 直观给出： 风险欠学习 过学习 h 图1 1 结构风险最小化原则 f i g l1 s t r u c t u r a lr i s km i n i m i z a t i o np r i n c i p l e k h v c 维 在结构风险最小化原则下，一个分类器的设计过程包括以下两方面的任务： 1 ) 选择一个适当的函数子集( 使之对问题而言有最优的分类能力) ： 2 ) 从这个子集中选择一个判别函数( 使经验风险最小) 。 第一步相当于模型的选择，而第二步则相当于在确定了函数形式后的参数估计。与 传统方法不同的是，在这里，模型的选择是通过对它的推广能力的界的估计进行的。 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 l ，5 2 ，5 ，3 9 ，3 2 ，2 7 ，并且已表现出 很多优于其他算法的性能。现在已经有越来越多的学者致力于该方法的研究，井取得了 一些比较有效的成果。一些学者还认为，s l q l 和s v m 正在成为继神经网络研j 宄之后新 的研究热点，并将有力地推动机器学习理论和技术的发展。 1 2 支持向量机研究背景 首先我们给出基于统计学习理论的支持向量机( s v m ) 方法的优点，主要体现在： 1 在解决有限样本的数据分类日寸具有很强的推广能力，能有效解决神经网络过学习 现象： 2 模型求解最终体现在一个二次规划问题上，从理论上讲，可以得到全局最优解， 解决了在神经网络方法中无法避免的局部极值问题； 3 该方法通过引入核函数，有效的解决了非线性分类情形和“维数灾难”问题其 算法复杂度与样本维数无关。 但是，在现实中样本数尽管说是很有限的，然而对相应的二次规划而言由于规模巨 大也不易求解，经典的二次规划算法( 内点法、有效集法、w o l f e 对偶算法等等) 将在 某种程度上失效。这就使得该方法在实际应用中仍然存在着定的缺陷，而这也正是许 多学者直致力研究的重点。诚然s v m 的研究还包括它的理论基础的进一步研究、具 体算法优化、核函数的研究及具体应用等等，不过就s v m 发展的实践应用前景而言， 在现有理论保证下如何去解决算法实现闯题将显得更有现实意义。 1 2 1 支持向量机简介 s v m 方法是从线性可分的情况下的最优分类面( o p t i m a lh y p e r p l a n e ) 提出韵c 假 设给定一个训练集，如果训练集中所有向量均能被某超平面正确划分，并且距离超平面 最近的异类向量之间的距离最大( 即边缘最大化) ，则该超平面为最优超平面。 考虑模式识别中有监督( 带样本类别标号) 的分类问题，给定一组样本点集( j ，y ，) r t 5 r 4 ，y 。( + 1 ，一1 ) ，i = 1 , 2 ，m 。即是h 维空间中的样本点，y ，是 对应的类别标 号，+ 1 表示第l 类，一l 表示第2 类。分类闫题就是要通过已知训练样本点 每造一判别函 号，+ 1 表示第l 类，一l 表示第2 类。分类闻题就是要通过己知训练样本点构造一判别函 4 些查型苎奎堂堡兰堂垡堡三 堡垒 数( 或称分类函数、决策规则等) ，并用其对未知点进行分类决策。支持向量机就是处理 这样一种分类问题的强有效工具，其标准模型为： m m 蚋1 2 + c 艺磊 ( 1 2 1 ) s 咒( w ，t 一6 ) + 莓2 1 ； ( 1 2 2 ) 毒0 ；i = l ，2 ，埘 ( 1 2 3 ) 写成矩阵形式如下： m i n 劲叫1 2 + q 善 ( 1 2 4 ) s j d ( a w e b ) + 亭e ； ( 1 2 5 ) 考0 ( 1 2 6 ) 其中，w r “是最优超平面的法向量；6 r 为阈值，决定了最优超平面离原点位置。善r 为第i 个样本点的误差量；c 0 则是惩罚园子，或称正则化因子，起着控制对错分样本 惩罚程度的作用，实现错分样本的比例与算法精确度之间的折衷。4 为以为行的m n 阶阵，d 为以+ 1 或一1 为对角线元素的m m 阶对角阵( 其元素由t 对应的类别值m 决 定) ，e 为以l 为分量的任意维向量。这里用符号“”表示对向量或矩阵的转置，下同。 原模型中引1 2 1 埔舻币是要使两类的平行分离超平面间隔卉最大保证学 习机器的推广能力( v c 置信范围最小) ；第二项则是要求最优分离面能将两类尽可能无 误地分开，保证学习机器的经验风险最小。 当两类数据集严格线性可分时，对应毒= 0 ，两类诩练样本各自在两平行超平面的外 侧，而最优超平面则是上述两个平行超平面的中间面w 一b = 0 。当两类数据集线性不可 分时，被错分样本对应喜 0 ，此时称两类数据集被两平行超平面软间隔( s o f t m a r g i n ) 分离。以上是数据集线性可分时的情形，要得到s v m 模型的解，就要解决模型( 1 2 1 ) 一( 1 2 3 ) 或( 1 2 4 ) ( 1 2 6 ) 对应的二次规划问题，通常主要通过其腑掘对偶问题来 解决。对矩阵形式模型( 1 2 4 ) ( 1 2 6 ) ，其对偶问题为： 5 山东科技大学硕士学位论文 绪论 m i n 三a ，d a a ，d 口一p ，a 2 s j e d 口= 0 0 c t c( w = a d 口) ( 1 2 7 ) ( 1 2 8 ) ( 1 2 9 ) 设最优解是口，则w + = a d a 。其中g 的取值可能是：z = 0 ；o z c ；口：= c 。 后两者所对应的t 即为支持向量( s u p p o r t v e c t o r ，简称s v ) 。在支持向量中，所对应 的t ，称为边界支持向量( b o u n d a r ys u p p o r tv e c t o r ，简称b s v ) ，实际上是错分的训练 样本点；所对应的t ，称为标准支持向量( n o r m a ls u p p o r tv e c t o r ，简称n s v ) 。、 对应的x i 只是所有样本点中的一小部分。此情形下最优判别函数是： 厂( x ) = s g n w 。工一b j _ s g n o ，c 0 ( 1 2 1 4 ) 注1 1 ：之所以称为“支持向量机”，主要是因为最终所得最优判别函数主要由“支持向 量”表示。由w = a d a + 和b 的确定及式( 1 2 1 0 ) 知最优判别函数的表示与口j = 0 所对 应的“非支持向量”无关，而口：o 对应的点t 就称为“支持向量”。这罩的“机”实 际上是一个算法，在机器学习领域常称一个分类算法为分类“机”。 1 2 2 支持向量机谶练算法的研究 在支持向量机模型的求解过程中，主要就是求解上述提到的一个二次规划问题( 不 论是原始的，还是对偶的) 。但是由于对于含有掰( m 相当大) 个样本的海量数据集而 言，上述规划涉及了m m 阶核函数矩阵的计算及矩阵与向量的相乘运算，甚至还有矩 阵的求逆运算，从而使得经典算法不能有效解决该问题甚至没法实现。为此，一些研究 人员提出了许多针对这个大规模问题的有效s v m 训练算法。 v a p n i k 等人于1 9 9 2 年提出了求解s v m 的分块算法( c h u n k i n ga l g o r i t h m ) 【1 】，它 可以看成是一种不完全分解，算法将原来大型的q p 问题分解成一系列待优化的小型q p 子问题。子问题优化的是上次解得的支持向量( 非0 变量) 和新的违反k k t 条件 4 8 】 的最厉害的m ( m 事先确定) 个变量，需要优化的问题规模变小。这样经过反复优化迭 代，最终得到s v mq p 问题的全局最优解。当然该方法也存在一定的缺陷，就是当支持 向量数目非常大时，予问题的规模会逐渐增大，所谓“小规模”问题的求解仍将难以实 现。 1 9 9 7 年o s u n a 等人提出了新的求解s v m 的策略分解算法( d e c o m p o s i t i o n m e t h o d ) 【3 4 】。该方法要求在求解子问题时保持各子问题规模不变，要进行优化的变量 我们称它为工作集，而其他非工作集的变量则保持值不变。这样就避免了分块算法中问 题规模增大的缺陷，并且首次从理论上证明了算法的收敛性。当然该算法实现的关键是 在每次迭代求解时如何有效的选择工作集，这也是现在关于该方法研究的热点。 在工作集的选择上，o s u n a 等人给出的策略并不是最优的，但是他的这一工作却是 7 山东科技大学硕士学位论文绪论 开创性的。后来提出的s m o 算法和s v m t 自h 算法其实都可以看成是o s u n a 算法的特例或 推广。 1 9 9 8 年p l a t l 等人提出了序列最小优化算法( s e q u e n t i a lm i n i m a lo p t i m i z a t i o n ，简称 s m o ) 【3 6 ，该算法将工作集规模限定在2 个变量的优化求解上，避免了数值求解，而 直接采用解析法进行计算。并且k e e r k i 和g i l b e r t 于2 0 0 2 年证明了改进的s m o 算法 1 7 1 的收敛性。最近也有不少这方面的文章，主要集中在两个变量的启发式选择策略上和核 函数的缓存技巧上。在同年，j o a e h i m s 等人提出了算法s v m “g k ，并加以实现，是时下 应用中较为流行的一种软件。该算法主要在工作集的选择和实现上做出改进。学者们习 惯的将上述算法统称为分解算法。 下面介绍的则主要是美国威斯康星大学学者0 l m a n g a s a r i a n 等人提出的一系列算 法，主要是将现有的优化算法应用于改进的特殊s v m 模型中，得到了较好的结果。 1 9 9 9 年o l m a n g a s a r i a n 等人提出了s u c c e s s i v eo v e r r e l a x a f i o n ( s o r ) 【2 6 算法，主 要是对标准s v m 进行了改造，在 + 1 维空间中考虑最大化分类间隔( 同时考虑w 和b ) ， 从而得到的对偶问题将是一个只含超盒约束的q p 问题。这样再通过有效的矩阵分解策 略就可以直接利用求解对称线性互补问题的s o r 方法来进行有效求解了。该算法实质上 就是每次迭代优化一个乘子变量，不需要将所有样本载入内存，从而提高3 j 1 1 练速度。 2 0 0 0 年o l ，m a n g a s a r i a n 等人又提出了基于有效集方法( a c t i v es e tm e t h o d s ) 的 a s v m 2 8 算法。算法在经过特定的模型改造后得到对偶问题为没有上界的简单约束 ( 口0 ) 的q p 问题。再利用有效集方法，将优化变量分成基变量和非基变量，在迭代 过程中每次只要求解一个关于基变量的线性方程组就可以了。这样就使得问题规模大大 下降，并可以利用矩阵计算中的s h e r m a n - m o r r i s o n - w o o d b u r y ( 简称s m w ) 恒等式 4 8 】 解决方程组中矩阵求逆问题，可直接求解出问题的解。 2 0 0 1 年0 l m a n g a s a r i a n 等人又提出了具有线性收敛性的l a g r a n g i a ns v m 2 9 算法。 在求解对偶q p 问题时，直接利用隐l a g r a n g i a n 公式得到l s v m 的迭代式，算法实现非 常的方便。 值得注意的是上述两个算法都是对线性情形的大规模数据集求解比较有效，对于非 线性可分情形则只能处理中小规模的问题，主要是因为在模型求解过程中不能有效利用 s m w 公式来求核函数矩阵的逆。 在2 0 0 0 年o l ，m a n g a s a r i a n 等人还将光滑函数方法引入到改造后的s v m 中得到了 8 山东科技大学硕士学位论文绪论 求解原始规划的s m o o t hs v m 1 9 算法。经模型改造后可以把原来的有约束问题转化成无 约束问题，再利用经典的牛顿迭代方法加以解决。 虽然已经提出很多有效算法，但建立更加高效的求解支持向量机的优化算法，仍是 支持向量机理论研究的一个很有意义且急需解决的问题。 此外，鉴于s v m 在现实中的应用潜力，很多学者也都在致力于研究某些特定的问 题，以期能更好的应用于实际问题。2 0 0 1 年c a u w e n b e r g h s 等人提出了在线训练的精确 解算法，阐述了增加一个训练样本或减少一个样本对支持向量和分类面的影响，实质上 就是一种增量学习算法【6 ，4 1 ，5 0 ，1 3 】。这方面的研究已经越来越受到人们的关注。而由于 现实中某些问题在提取样本属性时存在很大的困难，一些学者也致力于研究适合s v m 特性的特征选择算法 3 ，4 4 ，7 ，1 5 。还有在多分类s v m 4 3 ，1 0 ，3 1 、超球结构s v m 4 2 ，5 3 】、 s v m 回归分析 3 9 ，1 8 ，2 1 ，3 3 ，3 5 ，3 7 ，3 8 ，4 7 等方面都有了相应的报道。 1 2 3 支持向量机求解的常用数据集和软件包 鉴于s v m 算法在现实问题应用中的实用性，数值试验比较将是各算法有效性衡量 的一个重要标准。当然比较的对象最好是比较通用的，而不是针对自己算法的特点找的 特定的人工数据集。目前国际上较为常用的标准数据库主要有： ( 1 ) u c i 机器学习数据库，拥有数据库资源最多的网站，较常用的u c i a d u l t 数据 库。可从以下地址得到：f 币：，印i c s u c i e d u p u b m a c h i n e l e a r n i n g - d a t a b a s e s ； ( 2 ) w i s c o n s i nb r e a s tc a n c e r 数据库，包括w p b c 、w d b c 等，主要是一些乳癌病 例作为数据样本，是一个典型的2 分类数据集。可从以下地址获得：邱：f t p c s w i s c e d u m a t h - - p r o g c p o d a t a s e v m a c h i n e - l e a r n c a n c e r ； ( 3 ) a t & t 贝尔实验室：m n i s t 数据库，关于手写数字识别评测的数据库，是n i s t 的一个子集，拥有6 0 0 0 0 个训练样本和1 0 0 0 0 个测试样本。具体地址：h t t p ：l y a n n 1 e c u n c o r n e x b d m n i s t i n d e x h t m l ； ( 4 ) 标准o r l 数据集，主要用于人脸识别的数据集，共包含了4 0 人的各自不同的 1 0 幅脸图。具体地址：h t t p ：w w w u k r e s e a r c h a t t c o m f a c e d a t a b a s e h t m l 。 以上仅为一些常用的数据集，当然还有很多其他的各大研究机构数据集，这里不再 一一列举。 下面我们给出现有的较为流行的一些求解s v m 的程序和软件包： 9 山东科技大学硕士学位论文 绪论 ( 1 ) s m o ，葛显平用c “编写的关于p l a t t 的s m o 算法的实现程序；程序编码下载 地址：h t t p ：l l w w w d a t a l a b u c i e d u p e o p l e x g e s v m ； ( 2 ) s v m t i s h ，t h o r s t e nj o a c h i m s 用c 语言编写的，采用了“s h r i n k i n g ”策略，解 决了分类、回归等问题；地址：h t t p ：s v m l i g h t j o a c h i m s o r g ； ( 3 ) b s v m ，台湾学者林智仁等编的一种采用s v m 分解算法求解大规模分类问题 的实现程序；地址：h t t p ：w w w c s i e n t u e d u t w 卅l i n b s v m ； ( 4 ) l i b s v m ，林智仁等人将s m o 算法结合s v m l * h 算法中的工作集选择策略而开 发的软件包，是目前无论是在运算速度上或是效果上均不错的一个软件包；地址： h t t p ：w w w c s i e n t u e d u ，t w - - e j l i n l i b s v m ； ( 5 ) 美国威斯康星大学学者o l m a n g a s a r i a n 等人在其提出的一系列算法的基础上 编写的相应的软件代码：a s v m 、l s v m 、s s v m 等；相关下载地址：h t t p ：w w w c s w i s c e d u d m i s v m 。 除上述现有流行软件外，也有许多学者给出了一些关于s v m 的m a t l a b 工具箱，以 便于新的算法编程实现和比较：h t t p ：l l w w w c i s t u g r a z a t i g i a s e h w a i g s o f l w a r e h t m l ； h t t p ：w w w i s i s e g s s o t o n a c u k r e s o u r c e s s v m i n f o ；h t t p ：t h e o v a l s y s u e a a g u k g e c s v m t o o l b o x 。 1 2 4 支持向量机的应用 随着支持向量机研究的深入，其应用方面的报道也越来越多。s v m 的应用主要集中 在模式识别领域，有手写数字识别、人脸识别与人脸检测、图像识别等，最突出的是对 美国邮政手写字库中数字的识别，人们采用不同的方法设计分类器，通过比较得到s v m 较其他方法有明显的优势，并且对于采用不同核函数类型的支持向量机表现出了大致相 同的性能。在文本分类和语音识别方面支持向量机也表现出了较强的识别性能。另外， s v m 还很好地应用到了时间序列分析和回归分析等领域。 1 3 论文研究内容及各章主要安排 论文各章安排如下： 第一章介绍支持向量机的数学理论基础统计学习理论，支持向量机的基本思想 1 0 山东科技大学硕士学位论文 绪论 及一般模型、若干求解算法和研究方向、常用数据集和软件包及支持向量机的应用领域 等，指出本文的主要研究内容； 第二章研究支持向量机分类算法，针对有效集算法不能有效求解非线性可分情形的 模型，提出基于s o r 的有效集分解策略求解支持向量机算法； 第三章研究支持向量机回归算法，将求解分类问题的有效算法推广到回归问题中来， 提出有效的牛顿型支持向量回归机和l a g r a n g e 支持向量回归机算法； 第四章研究特殊结构的支持向量机，将其与特征选择相结合，给出一种能自动进行 特征选择的最少核分类器； 第五章是全文的总结，以及对未来工作的展望和建议。 2 支持向量分类机算法研究 支持向量机的精华部分就在其分类性能上，最初提出支持向量机算法时就是针对线 性两分类模型的，之后才逐渐的向非线性、多分类、回归预测等问题推广。所以对支持 向量机分类算法的研究就显得非常重要。一般提到支持向量机主要是针对分类情形的， 本文为了区别下一章的支持向量回归机，在此特别指明针对分类情形的为支持向量分类 机。本章详细介绍支持向量分类机中的若干优化算法，然后针对其中的a s v m 算法不能 有效解决非线性可分情形的缺陷，利用有效集策略将优化问题规模下降，结合s o r 算法 求解子问题来对其进行改进，并证明了改进算法的有限终止性。 2 1 分类问题的描述 在绪论中我们曾提到分类问题的一般描述，本节则详细介绍支持向量机关于分类问 题的理论基础和若干常见算法模型。下面主要以2 维图形为例解释常见的2 分类问题。 首先看以下三种不同的情形： 、 弋o 图2 1 线性可分支持向量机 f i g2 1l i n e a r - s e p a r a b l es v m 1 2 山东科技大学硕士学位论文支持向量分类机算法研究 图2 2 线性不可分支持向量机 f i g2 2l i n e a r - n o n s e p a r a b l es v m 山 a o o + a 口 十 i + j o e o 图2 3 非线性可分支持向量机 f i g 2 3n o n l i n e a r - s e p a * a b l es v m 从图2 1 中可以看出两类样本分布间隔较大，很容易找到一条直线将两类样本分离， 这属于线性可分问题，对应的支持向量机线性可分模型主要就是求解其最大间隔分类面。 图2 2 描述的是线性不可分情形，用一条直线虽不能完全的分离样本集，但大致上仍能 把两类样本集分离，此时仍采用线性分类机予以解决，只需在模型中加入对错分样本的 惩罚项。图2 3 则描述了非线性可分的情形，此时用一条直线加以划分两样本集时会产 生很大的误差，而若采用曲线( 非线性) 分类器则可顺利地分离两样本集，这就是非线 性可分的问题，通过引入核函数将原先低维空间中非线性可分的样本集映射到高维特征 空间中，再在高维空间中采用线性分类器将映射后的样本集加以划分，对应一般的支持 向量机模型为： 1 3 山东科技大学硕士学位论文 支持向量分类机算法研究 商n 妯1 2 + c 芝量 工 i = 1 s f y , ( w x i b ) 十鲁2 1 ， 毒0 ；i = 1 ，2 ，埘 ( 2 1 1 ) ( 2 1 2 ) ( 2 1 3 ) 这里置= 妒( 葺) 为x i 映射到高维空间之后的样本点。映射9 ( x ) 的确定是关键，也是一个 难点，由于不容易得到该映射而使得直接求解该原始问题( 2 1 1 ) 一( 2 1 3 ) 变得不可行。 支持向量分类机常用的求解方法是通过先求解其对偶问题的解，再利用该对偶问题的解 来表示原始问题的解从而确定原始分类问题的最优判别函数。模型( 2 1 1 ) - ( 2 1 3 ) 的 对偶问题为： 1mm m r a i n 去咒巧哦。，z ；巧一q ( 2 1 4 ) s m 啦= o ， ( 2 1 5 ) 0 t 2 is c ，i = 1 ，2 ，m ( 2 1 6 ) 可以看出以上模型为典型的二次规划问题，只是问题的规模巨大，且绝大多数不具有稀 疏性，使得典型的二次规划求解算法不能直接应用。 下面给出支持向量机算法的一般形式： 步1 ，给定己知标号的聊个训练样本( x i ，儿) ，x ，r “，y i 十1 ，一1 ，i = 1 , 2 ，m ，选择 适当的核函数k 和惩罚参数c ，给定k k t 条件终止精度占； 步2 ，采用优化算法求解如下二次规划问题( 原问题的对偶规划) ： m i n 去咒巧a ，k ( 蕾，_ ) 一啦 ( 2 1 7 ) 1 = 11 l o i 5 m 啦= o ， ( 2 - 1 8 ) 0 - a ；c ，i = l ，2 ，m ( 2 1 9 ) 得到最优解口+ = ( 口：，a ：，a ：) ： 步3 ，求阈值6 ：任给个不为零的a 的分量弓，令6 = 巧一冀z 趸瓴，t ) ；其中 l e s t 1 4 山东科技大学硕士学位论文 支持向量分类机算法研究 s v 为a + 的不为零的分量对应的f 标集合； 步4 ，利用上述对偶规划的解来表示最优判别函数：，( z ) = s g n ( y l a k ( x i ，工) + 6 ) 。 从此标准算法可以看出整个模型求解的难点即在于求解二次规划问题( 2 1 7 ) 一 ( 2 1 9 ) ，本章所介绍和讨论的各种优化算法均围绕着标准模型( 2 1 1 ) 一( 2 ，1 3 ) 或其 对偶问题( 2 1 4 ) 一( 2 1 6 ) 展开，通过修改模型得到各种不同的求解方法。 这方面的工作主要由美国威斯康星大学学者o l m a n g a s a r i a n 等人给出，从改造标准 s v m 模型入手，针对不同模型引入不同的求解二次规划的优化算法。首先，将原先h 维 空间向一+ 1 维空间推广，在构造最大间隔分类面时不仅考虑分类超平面的法向量w ，还 考虑了确定分类超平面的阈值6 ，也即此时两分类超平面的间隔距离为赢得到 模型： m i n 知叫1 2 + 6 2 ) + c 鲁 ( 2 1 l o ) s f y i ( w 0 一b ) + 莓1 ， 喜0 ；i = 1 ，2 ，m ( 2 1 1 1 ) ( 2 1 1 2 ) 其次，在最小化软间隔分类误差时，对误差变量f 采用2 范数度量来代替传统的和式1 一 范数，得到模型： 同时，还可以得到如下模型： 曲1 1 1 w t l = + b ) + 导羔i = 1 等 ( 2 3 ) s y i ( w x i b ) + 喜1 ( 2 1 1 4 ) ( 鲁0 ；) i = l ，2 ，m ( 2 1 1 5 ) 柚洲2 + i c 擎m 2 5 t m ( 置一b ) 十岳2 1 ( 2 1 1 6 ) ( 2 1 1 7 ) ( 盏0 ；) i = 1 ，2 ，m ( 2 1 1 8 ) 1 5 山东科技大学硕士学位论文支持向量分类机算法研究 以上模型中将约束( 2 1 1 5 ) 和( 2 1 1 8 ) 去掉后与原模型同解，因为若存在毒 o ( 2 2 3 ) 这里( ) 。为2 范数意义下的投影运算： ： 三矿篱斗，m 旺： 【c 矿cj a p l = ( d 一t o e 一1 ( h h 口一e + l ( a 一1 一a ”) * ， ( 2 2 ，5 ) 直到忙川一口刮占，其中( o ，2 ) ，为给定的迭代终止精度。 能使目标函数，( 口) 严格单调下降。事实上，若对q 进行正则分裂 2 3 】，即令q = 口+ c ， 且满足四一c 正定( s o r 算法中取曰：三e + 上，c ：( 1 一1 ) e + f ) ，则可推得： o p l ) 一f ( a ) 以“一