（控制理论与控制工程专业论文）支持向量机建模方法的研究.pdf

l ， 、 at h e s i sf o rt h e d e g r e eo fm a s t e ri nc o n t r o l e n g i n e e r i n g t h e o r ya n dc o n t r o l r e s e a r c ho nm o d e l i n gm e t h o do f s u p p o r tv e c t o rm a c h i n e d o n gg a n g s u p e r v i s o r ：a s s o c i a t ep r o f e s s o rh ed a k u o n o r t h e a s t e r nu n i v e r s i t y j a n u a r y2 0 0 8 气， 疆j 一 - 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的 研究成果除加以标注和致谢的地方外，不包含其他人已经发表或撰写过的 研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示诚挚 的谢意。 学位论文作者签名：一留闰 签字e t 期：沙田彦、 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师同意网上交流，请在下方签名：否则视为不同意) 学位论文作者签名：茜钢 导师签名： 签字日期：签字日期： 1 鼍 - ， j i j 东北大学硕士学位论文摘要 支持向量机建模方法的研究 摘要 支持向量机是v a p n i k 教授领导的研究小组于上世纪末提出的一种机器学习的新方 法，是统计学习理论的核心部分，是处理小样本学习的有效工具。支持向量机作为统计 学习理论的实现方法，能很好地解决非线性和高维数问题，克服了神经网络方法收敛慢、 解不稳定、推广性差的缺点，近年来得到了广泛地研究，在模式识别、信号处理、控制、 通讯等方面得到了广泛地应用。因此，研究支持向量机的理论和应用问题具有重要的理 论与现实意义。 回归估计是支持向量机方法的重要研究领域，本文以支持向量机理论为基础，对回 归问题的方法进行了研究。全文共分六章，具体内容如下： 1 介绍了机器学习领域中统计学习理论的基本思想和方法，进一步详细说明了结构 风险最小化原理，同时，对支持向量机的发展进行了概括性的总结； 2 在深入分析支持向量机基本原理的基础上，对目前的支持向量机的改进算法进行 了总结，同时，将各种算法与传统算法进行了比较； 3 针对非线性建模问题，提出一种新的支持向量机核函数构造方法，对高斯核函数 在支持向量密集处拟合效果差的缺点进行了改进，仿真研究结果显示，新方法可以一定 程度上减少泛化误差； 4 提出了一种基于f i s h e r 判别率的支持向量机回归算法。该方法通过引入样本内部 相似程度的判别因子来减少样本错分几率，理论分析与仿真实验均验证了算法的有效性 和优越性； 5 提出了一种新的用于回归的支持向量机增量算法。该算法与传统算法相比，可以 在满足模型精度要求的基础上，明显地提高算法的计算速度。 关键词：支持向量机；统计学习理论；核函数；f i s h e r 判别率；增量算法 一i i 椰 - ， 1 h j r e s e a r c ho nm o d e l i n gm e t h o do fs u p p o r tv e c t o rm a c h i n e 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 ) ，t h ek e r n e lc o n t e n to ft h es t a t i s t i c a ll e a r n i n gt h e o r y , i s an e wa n do u t s t a n d i n gm a c h i n el e a r n i n gm e t h o d ，w h i c hw a sp u tf o r w a r di nt h et w e n t i e t h c e n t u r y i ti sav a l i dm a c h i n e l e a r n i n gt o o li nd e a l i n g 、析ms m a l ls a m p l e s s v mo v e r c o m e s s o m es h o r t c o m i n g so fn e u r a ln e t w o r k ，s u c ha ss l o wc o n v e r g e n c e ，u n s t a b l es o l u t i o na n dp o o r g e n e r a l i z a t i o n s oi t h a sb e e nw i d e l ya p p l i e dt om a n ya r e a s ，s u c ha sp a t t e r nr e c o g n i t i o n ， s i g n a lp r o c e s s i n g ，a u t o m a t i o na n dc o m m u n i c a t i o n s oi ti sv e r yi m p o r t a n tt os t u d yt h et h e o r y a n di t sa p p l i c a t i o nf o rr e s e a r c h i n ga n dp r o d u c i n gp u r p o s e s v mf o rr e g r e s s i o ni sa ni m p o r t a n tr e s e a r c h i n gf i e l d i nt h i sp a p e r , s e v e r a lr e g r e s s i o n a l g o r i t h m sb a s e do ns v m a l ep r o p o s e d n l cp e r f o r m a n c ea n da p p l i c a t i o n so ft h ea l g o r i t h m s a r es t u d i e di ns i xc h a p t e r s 1 1 1 er e s e a r c hi sc a r r i e do u ti nt h ef o l l o w i n ga s p e c t s ： 1 a n o v e r v i e wo nm a c h i n el e a r n i n g ，s t a t i s t i c a ll e a r n i n gt h e o r ya n ds t r u c t u r a lr i s k m i n i m i z a t i o ni sp r o v i d e d ，f o l l o w e db yas u m m a r yo nt h ed e v e l o p m e n ta n da p p l i c a t i o n so f s v m 2 b a s e do nt h ea n a l y s i so ft h eb a s i ct h e o r yo fs v m ，t h ei m p r o v e da l g o r i t h m so fs v m a r es u m m e du pa n dc o m p a r e dw i t ht r a d i t i o n a lo n e 3 an o v e lk e r n e lf u n c t i o ni sp u tf o r w a r di ns o l v i n gn o n l i n e a rm o d e l i n gp r o b l e m ，w h i c h o v e r c o m e st h ed e f e c to f g a u s sk e r n e lf u n c t i o nw h e nt h es u p p o r tv e c t o r sa r et o oc l o s et oo n e a n o t h e r s i m u l a t i o nr e s u l t ss h o wg o o dp e r f o r m a n c ei nf o r e c a s t i n ge r r o r 4 am o d i f i e ds v ma l g o r i t h mf o rr e g r e s s i o ni n s p i r e df r o mt h eo p t i m i z a t i o no ff i s h e r s d i s c r i m i n a n tr a t i oi sp r e s e n t e d ，w h i c hc a nr e d u c et h ew r o n g l ys c a t t e r e dr a t eb yu s i n gb e t w e e n c l a s ss c a t t e rm a t r i x e s t h ea d v a n t a g ei sp r o v e db yt h e o r e t i ca n ds i m u l m i o ns t u d y 5 af r a m e w o r kf o ri n c r e m e n t a la l g o r i t h mo fs v mf o rr e g r e s s i o ni sp r e s e n t e d ，w h i c hh a s ab e t t e rp e r f o r m a n c et h a nt r a d i t i o n a lo n ei nt r a i n i n gs p e e dw h e nt h ef o r e c a s t i n ge r r o ri s a c h i e v e d k e y w o r d s ：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 ；k e r n e lf u n c t i o n ；f i s h e r sd i s c r i m i n a n tr a t i o ； i n c r e m e n t a la l g o r i t h m i i i ； 二 东北大学硕士学位论文目录 目录 独创性声明i 摘要i i a b s t r a c t i i i 第一章绪论1 1 1 论文研究背景1 1 2 统计学习理论2 1 2 1 经验风险最小化原则2 1 2 2 结构风险最小化原则与v c 维3 1 3 支持向量机研究现状与应用5 1 3 1 支持向量机研究现状。5 1 3 2 支持向量机的应用6 1 4 本文的主要工作及内容安排7 第二章支持向量机算法简介9 2 1 支持向量分类9 2 1 1 线性可分支持向量机9 2 1 2 非线性分类支持向量机1 1 2 2 支持向量回归12 2 3 各种支持向量机算法1 4 2 3 1c s v m 算法1 4 2 3 2b s v m 算法1 6 2 3 3d s v m 算法。1 6 2 3 4o n e c l a s ss v m 算法17 2 3 5r s v m 算法18 2 3 6l s s v m 算法19 2 4 各种支持向量算法的比较与总结2 0 2 5 小结2 l 第三章核函数的改进与应用研究2 3 3 1 核函数方法简介2 3 3 1 1 核函数的定义2 3 3 1 2 核函数的构造2 4 3 2 几何学方法提高核函数效果2 4 一i v 东北大学硕士学位论文目录 3 3 基于放大因子的核函数构造方法2 6 3 3 1 高斯( r b f ) 核函数2 6 3 3 2 内积核函数2 7 3 3 3 核函数保角变换2 7 3 4 参数的选择2 8 3 4 1r 的选择2 8 3 4 2d 的选择2 8 3 5 仿真实验2 9 3 6d 、l ；3 0 第四章基于f i s h e r 判别率的支持向量机回归算法的研究3 1 4 1 用于分类的m c v s v m 算法31 4 1 1 问题描述3 1 4 1 2f i s h e r 判别分析3 1 4 i 3m c v s v m 算法3 2 4 1 4 ，j 、结3 3 4 2 基于f i s h e r 判别率的支持向量机回归算法3 4 4 2 1 基于f i s h e r 判别率的线性软间隔支持向量机回归算法3 4 4 2 2 非线性问题的求解方法。3 6 4 2 3 改进后算法与原算法的关系4 0 4 2 4 仿真实验4 0 4 2 5d 、结4 2 第五章增量支持向量机回归算法的研究4 3 5 1 增量支持向量机基本算法4 3 5 1 1 支持向量机回归和k k t 条件一4 3 5 1 2 添加新样本的递增算法一4 5 5 2 新的增量学习算法4 7 5 3 新的增量算法中的参数优化4 8 5 3 1 摄动参数的调整4 8 5 3 2 核参数的调整5 0 5 4 仿真实验5 l 5 5 ，j 、结。5 l 第六章结论与展望5 3 参考文献5 5 j 1 5 c 谢6 l v 一 东北大学硕士学位论文 第一章绪论 第一章绪论弟一早三百了匕 基于数据的机器学习是现代智能技术的重要方面，其研究实质是从观测数据出发寻 找规律，利用这些规律对未来数据或无法观测的数据进行预测。现有机器学习方法共同 的重要理论基础之一是统计学。传统统计学研究的是样本数目趋于无穷大时的渐进理 论，现有学习方法也多是基于此假设，并在某些领域取得了一定的发展，提出了一些新 的概念和学习方法。 但在实际问题中，样本个数往往是有限的，而且不知道数据内的相关性，因此传统 的机器学习方法导致了病态的训练结果，在实际应用中的表现不尽人意。这正是统计学 习理论及支持向量机越来越受到重视的主要原因。 1 1 论文研究背景 数据挖掘( d a t am i n i n g ，d m ) ，又可称之为数据库中的知识发现( k n o w l e d g ed i s c o v e r y i nd a t a b a s e ，k d d ) ，就是从大量数据中获取有效的、新颖的、潜在有用的、最终可理解 的模式的非平凡过程，简单的说，数据挖掘就是从大量数据中提取或“挖掘 知识。 数据挖掘涉及了许多研究领域的思想和方法，包括经典统计学的抽样、估计和假设 检验方法，以及人工智能、模式识别和机器学习的搜索算法、建模技术和学习理论。数 据挖掘也采用了来自其他领域的思想，这些领域包括最优化、进化计算、信息论、信号 处理、可视化和信息检索。 机器学习( m a c h i n el e a r n i n g ，m l ) 是数据挖掘领域的重要方法。机器学习是研究计算 机怎样模拟或实现人类的学习行为，以获取新的知识或技能，重新组织已有的知识结构 使之不断改善自身的性能。它是人工智能的核心，是使计算机具有智能的根本途径，其 应用遍及人工智能的各个领域，它主要使用归纳、综合而不是演绎。机器学习是继专家 系统之后人工智能应用的又一重要研究领域，也是人工智能和神经计算的核心研究课题 之。现有的计算机系统和人工智能系统没有什么学习能力，至多也只有非常有限的学 习能力，因而不能满足科技和生产提出的新要求。因此，对机器学习的讨论和机器学习 研究的进展，必将促使人工智能和整个科学技术的进一步发展。 统计学在机器学习中起着重要的基础作用，但是传统的统计学研究的主要是渐进理 论，即当样本趋于无穷多时的统计性质。所以基于传统统计理论的各种学习方法，都是 以样本无穷多为前提来推导算法。然而现实中，我们面对的样本数量往往是十分有限的， 通常的方法是仍以样本无穷多为假设进行算法推导和建模。当样本数较少时，用这种方 法得到的结果有时是难以令人满意的。例如，在普通的神经网络学习中，当样本数有限 一1 一 东北大学硕士学位论文第一章绪论 时，本来很好的学习机器却表现出很差的推广能力，这种现象被称为过学习现象。 为了解决这类问题，人们进行了坚持不懈的研究工作，直到2 0 世纪7 0 年代， v a p n i k 等人开始建立一种研究有限样本情形下统计规律及学习方法性质的理论，即统 计学习理论( 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 ) n 一，它为有限样本的机器学习问题建立了一 个良好的理论框架，较好地解决了小样本、非线性、高维数和局部极小点等实际问题， 其核心思想就是学习机器要与有限的训练样本相适应。1 9 9 5 年，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 ) ( 1 羽， 经过不断的发展，该理论越来越受到广泛的重视并应用到不同的领域。支持向量机方法 目前仍处于研究阶段，它仍存在许多有待进一步研究和探讨的问题，如保证学习机器具 有最佳推广能力而需进行模型参数选择问题；把二类别分类推广到多类别分类的问题； 在处理大规模问题时，为减少计算时间和存储空间的算法实现问题等。 1 2 统计学习理论 1 2 1 经验风险最小化原则 统计学习理论是一种专门研究小样本情况下机器学习规律的基本理论和数学构架， 是对小样本数据进行统计估计和预测学习的最佳理论。下面先从求解分类问题出发具体 描述。 分类问题的一个自然的数学提法可以表述如下：已知训练集， t = ( 五，m ) ，( 而，m ) ( x xy ) 。 ( 1 1 ) 其中毛xcr “，y y = 一1 ，1 ，f = l ，假定这些样本点是按照某个( 未知的) x xy 上的概率分布p ( x ，y ) 独立同分布地产生的。那么分类问题就是求解一个使其期望风险 r 【门， 天们= e c ( x ，y ，厂( x ) ) 】= k y c ( x , y ，f ( x ) ) d p ( x ，力 ( 1 2 ) 达到最小的决策函数f ( x ) 。其中c ( x ，y ，厂( x ) ) 为定义的损失函数，它是评价预测准确程 度的一种度量。在分类问题中常用的一个损失函数是o 1 损失函数，即 “而弘八呦= c o 一0 ) ) ( 1 3 ) 其中 珏侄嚣 m 4 ) 在回归问题中，一般情况下，损失函数具有如下形式 一2 一 东北大学硕士学位论文 第一章绪论 “c ( x ，y ，厂( x ) ) = c ( 厂0 ) 一y )( 1 5 ) 其中c 是取非负值的单变量函数。 这里应该强调，在分类问题中的提法中，并没有假设概率分布p ( x ，y ) 是已知的。己 知的只是训练集r 。换句话说，我们并不知道概率分布p ( x ，y ) 的具体形式，而只是知道 存在着这样一个概率分布，使得训练集中的样本点是遵循这个分布独立产生的。因为期 望风险是依赖于概率分布p ( x ，y ) 的，所以要构造一个仅仅根据若干个样本点就能找出使 期望风险最小的假设厂的学习算法看来是不可能的。为此人们引出了“经验风险”的概 念，希望在一定的条件下，用评价训练集上的经验风险的大小的方法来评价( x ) 。所谓 决策函数f ( x ) 对于它们的经验风险是指， 1， r , m p f = c ( 五y 厂( x ) ) ( 1 6 ) ，i l 那么我们要得到的决策函数厂就是从任意给定的训练集r ，并适当选定由假设构成 的集合fc f ：x ( xc r 开) 一y = - 1 ，l 中选择使其经验风险尺唧【】最小的f 。即经验 风险最小化原贝, l j ( e m p i r i e a lr i s km i n i m i z a t i o n , e r m ) h 1 。 构造学习算法的一个直观想法是，把假设集f 限制在一定的范围内，然后在这个范 围内寻求使经验风险最小的决策函数厂。归纳起来，该学习算法应具有如下步骤： ( 1 ) 给定训练集t = ( x l ，y t ) ，( 而，m ) ) ( x xy ) ，其中而xcr “，y y = - i ，1 ) ， f = l ，并选定损失函数c ： ( 2 ) 选择适当的假设集f ； ( 3 ) 在f 中找出一个使经验风险达到最小值的决策函数厂o ) ，即 厂( x ) _ a r g m i n 【门 ( 1 7 ) 然而，经验风险最小化与实际风险最小化等价的前提是样本数据的无穷多，而且用 经验风险最小化准则代替期望风险最小化并没有经过充分的理论论证，只是直观上合理 的想当然做法。因此，在实际应用中，结果往往不是很理想，在样本数量有限的情况下， 依据e r m 原则下建立的模型所得到的结果，有时候会出现过拟合的情况。在样本集中 能够获得非常小的训练误差，却难以保证算法具有很好的泛化能力，即在测试集中难以 得到同样小的估计误差。因此，为了在有限的样本数据情况下，获得预测能力较强的模 型，就必须对e r m 原则进行改进。 1 2 2 结构风险最小化原则与v c 维 一3 一 东北大学硕士学位论文第一章绪论 为了解决e r m 存在的问题，在过去的几十年中，提出了许多新的统计技术，结构 风险最小化原贝j j ( s t r u e t u r a lr i s km i n i m i z a t i o n , s r m ) 口1 就是其中最著名的一个。v a p n i k 证 明，期望风险斛厂】满足一个上界，即对于任意的概率分布p ( x ，少) 和任意的万( 0 , 1 】，f 中的任意假设厂都可以使得下列不等式至少以1 一万的概率成立， r 【厂】r m a f + 詈( 办( 1 1 1 詈+ 1 ) + h l 吾) ( 1 8 ) 特别地，当尺 门= 0 时，有 ( 1 9 ) 其中，式( 1 8 ) 中右端的第二项被称为置信区间，而此式右端的两项之和称为结构风险， 它是期望风险r 厂】的一个上界。参数h 称为f 的v c 维( v a p n i k - c h e r v o n e n k i s ) ，为训练 样本数目。v c 维是函数集f 的一种性质，它具体描述了函数集的容量，即无错误划分 数据的能力。模式识别方法中v c 维的直观定义是：对一个指示函数集，如果存在h 个 样本能够被函数集中的函数按所有可能的2 6 种形式分开，则称函数集能够把h 个样本打 散，函数集的v c 维就是它能打散的最大样本数目h 。由式( 1 8 ) 看出，这个上界是经验 风险和置信区间的和。我们知道经验风险依赖于厂的选择，而置信区间则是f 的v c 维 h 的增函数。粗略地说，当集合，比较大时，可以选到适当的厂，使得r 门比较小。 而此时由于f 的v c 维比较大，也会使置信区间比较大。反之，当缩小集合f 时，f 的 v c 维会降低，置信区间变小，而r 硎。【门有可能增大。所以两种有互相矛盾的倾向。 0 图1 1 结构风险最小化 f i g1 1s t r u c t u r a lr i s km i n i m i z a t i o n 一4 一 ， 东北大学硕士学位论文 第一章绪论 因此，如果要实现期望风险最小，就必须对式( 1 8 ) 右端的两项同时最小化，就是说， 必须使v c 维成为一个可以控制的变量。为此引进了结构风险最小化原则。s r m 是寻找 一个假设厂，使得式( 1 8 ) 右端所示的结构风险达到最小值。例如，适当选择一系列嵌套 的假设集， e 1cece + l ( 1 1 0 ) 在每个只中找出使经验风险最小的假设五，得到一系列假设， ，z - l ，厶小( 1 1 1 ) 考察与五相应的结构风险随刀的变化情况，可以发现： ( 1 ) 置信区间随着，l 的增加而增大，因为e 的v c 维是递增的， 一l s 吃+ l ( 2 ) 经验风险随着甩的增加而减小， e l 一- 】【以】【“ s r m 就是要选择适当的刀，使置信区间与经验风险之和到达最小， 设。图1 1 示意性地描述了结构风险最小化原则。 1 3 支持向量机研究现状与应用 1 3 1 支持向量机研究现状 。 ( 1 1 2 ) ( 1 1 3 ) 由此得到相应的假 训练支持向量机需要求解的是一个二次规划的优化问题瞳1 ，对于大容量数据来说， 二次规划的求解几乎是不可能的。为了降低计算资源、提高计算效率，人们提出了许多 支持向量机训练算法睁刀。s v m 训练算法主要有三类：二次规划算法，分解算法，增量 算法。另外，针对特定的问题，很多研究者在这三类算法的基础上提出了很多改进算法， 这些算法在特定问题的解决中表现出了很好的效果。 第一类是二次规划算法。s v m 可以归结为一个二次规划问题，二次规划是一种常 见的优化方法，有一套比较成熟的理论。从数学角度分析，s v m 是一个求条件极值问 题，在二次规划中，条件极值问题的通常解法有罚函数法和单纯形法呻1 们。 第二类是分解算法。当训练样本增加时，二次规划算法面临维数灾难，或者由于内 存限制无法用计算机正常处理。为此，研究者提出了处理大规模训练集的支持向量机分 解训练算法。如c h u n k i n g 算法1 、工作集算法n 纠 、序列最小优化算法n 1 等。 第三类是增量算法。训练方式是在训练样本逐个输入的情况下训练，其训练样本总 的个数是未知的瞄卜2 们。最典型的应用是系统的在线辨识，如a h m e d s n 最早提出的支 一5 一 东北大学硕士学位论文第一章绪论 持向量机增量训练算法、c a u w e n b e r g h s 的增量s v m 训练算法、c a r o z z a 啪3 和 x i a o t 2 8 均增量式学习的支持向量机训练算法、s u y k e n s 的周期最d x - - 乘支持向量机油1 。 此外，在以上三类基本算法的基础上，研究者们还提出了其它算法，如：张学工提 出的c s v m 算法，将每类训练样本集进行聚类分成若干子集，用子集中心组成新训练 样本集训练s v m ；s s k e e r t h i 提出的n p a 最近点算法口，将s v m 原问题惩罚项由 线性累加改为二次累加，从而使优化问题转化为两个凸集间的最大间隔；m i n g h s u a n y a n g 提出y 0 1 1 练支持向量机的几何方法和“卫向量”的概念啪1 ；b a s t o s 等提出了p s v m 算法，样本被分配到数据空间中最近的两个平行平面；l i i l 等提出了模糊支持向量机 ( f s v m ) 1 ，通过给样本增加一个模糊成员关系，来充分利用样本的信息；l e e 提出的 约简支持向量机算法( r s v m ) 嘶矧；s u y k e n s 提出的最小二乘支持向量机训练算法阱1 ；国 内的研究者们也提出了一些新算法3 h ，如基于线性规划的支持向量机分类器，最小二 乘隐空间支持向量机，基于小波的支持向量机算法，加权支持向量机分类算法等。 在多类别分类应用方面，多类支持向量机算法研究也较多h 糊1 ，主要有：对类问 题构造个两类分类器的1 一口一，算法；在类训练样本中构造所有可能的两类分类器， 每类仅仅在类中的两类训练样本上训练，结果共构造u ( u 一1 ) 2 个分类器的卜口一1 算 法；p l a t t 等提出的决策导向循环图( d d a g ) ；s e b a l d 提出的对于个类别的分类问题构 造l o g ，个支持向量机的多类s v m s 方法；基于s v m 的二叉树多类分类算法；分裂层 次聚类s v m 多值分类方法；李蓉等提出的s v m k n n 分类器；李红莲等提出的改进 的支持向量机n n s v m 等。 1 3 2 支持向量机的应用 目前，支持向量机的应用已逐渐成为各国研究者的研究重点，在模式识别、回归估 计、概率密度函数估计等领域均有应用成果。 在模式识别方面，最突出的应用研究是贝尔实验室对美国邮政手写数字库进行的实 验，用三种支持向量机方法得到的错误率分别为4 0 、4 1 、4 2 ，优于决策树和神 经网络方法n 一。在人脸检测与识别领域，m i t 用支持向量机进行的人脸检测实验也取 得了很好的效果阱瑚1 ，可以较好地学会在图像中找出可能的人脸位置，国内也有了较多 研究成果3 h 。支持向量机还广泛用于图像处理，在图像分割1 、图像检测h 、图像检 索1 等方面都得到了良好应用，在遥感图像分析、语音识别、文本分类、三维物体识别 等也有较多的应用研究成果一1 。 在医学研究领域的应用研究成果也较多。支持向量机被用于从基因数据中对基因进 行分类、人类基因表示数据的分析、基因功能的确定、蛋白结构类别的预测、肺癌诊断、 胎儿肺部图像检测等删。此外，支持向量机在工业工程领域的应用研究正逐渐受到研 - - 6 - - - _ i ， ：- 东北大学硕士学位论文第一章绪论 究者的重视，如水轮发电机组故障诊断、内燃机故障诊断、工业过程故障诊断、工业对 象系统辨识、最优控制、预测控制等晦3 。在信号处理领域、金融领域等都显示出了支 持向量机的强大优势h 钔。 支持向量机在国内的研究尽管滞后于国外，但近年发展较快，国内研究人员开展了 许多有效的研究工作，取得了不少成果m 。7 酗，为国内支持向量机的发展起到了重要的推 动作用。 1 4 本文的主要工作及内容安排 全文共分六章，在结构上安排如下： 第一章介绍了论文的研究背景及意义。其中包括机器学习领域中统计学习理论的基 本思想和方法、结构风险最小化原理，同时，对支持向量机的发展进行了概括性的总结， 并给出了几种支持向量机的应用实例，最后介绍了本文的主要工作。 第二章叙述了支持向量机的基本原理和方法。首先讨论了用于分类和回归线性软间 隔支持向量机算法；其次将上述算法过渡到非线性情况；最后介绍了一些学者对支持向 量机算法的改进研究，并对各种算法的优缺点进行了分析和比较。 第三章针对核函数的构造方法进行研究。高斯核函数存在支持向量密集处拟合效果 差的缺点，本文引入了支持向量放大因子的概念，提出了基于放大因子的核函数改进算 法。利用该算法进行函数预测，有效地减少了预测误差，提高了支持向量机回归的泛化 精度。 第四章提出了基于判别因子的支持向量机回归算法。该算法综合了f i s h e r 判别分析 和支持向量机回归算法，采用样本内部相似程度的判别因子来减少样本错分几率，并通 过仿真实验验证了算法的有效性和优越性。 第五章提出了一种新的支持向量机增量回归算法。该算法与传统算法相比，可以在 满足一定精度要求的基础上明显的提高算法的训练速度。 第六章总结了全文的工作，并介绍了今后需要继续研究的课题。 一7 一 东北大学硕士学位论文第一章绪论 一8 一 ， 东北大学硕士学位论文第二章支持向量机算法简介 第二章支持向量机算法简介 统计学习理论是建立在坚实的理论基础之上，为解决有限样本学习问题提供的一个 统一的框架，它能将很多现有的方法纳入其中，解决了神经网络方法收敛慢、解不稳定、 推广性差的缺点。而支持向量机正是在这一理论基础的上发展出的新方法，而且受到了 很多学者的重视。本章介绍了支持向量机的基本理论，同时对目前的一些改进算法进行 了比较和总结。 2 1 支持向量分类 支持向量机中最简单也是最早提出的模型是最大间隔分类器。它是更加复杂的支持 向量机算法的主要模块。下面首先考虑线性可分问题的线性分划。 2 1 1 线性可分支持向量机 设训练集为t = ( x l ，y 1 ) ，( 而，m ) ) ( x xy ) 。，其中毛xcr ”，y l y = - 1 ，1 ) ， 汪1 ，问题线性可分表明，存在着超平面，及约束条件， 沏x ) + b = 0( 2 1 ) 一) + 6 1 ，y 。= l( 2 2 ) ( 缈而) + b - 1 ，儿=一l(23) 使得训练点中的正类输入和负类输入分别位于该超平面的两侧，或者说存在着参数对 0 ，6 ) ，使得 m = s g n ( ( r x f ) + 6 ) ，f = 1 ，( 2 4 ) 求解这样的分类问题时，一种自然的考虑是选择正确分划训练集的线性分划，即选择使 得式( 2 1 ) 成立的参数对0 ，6 ) ，然后构造决策函数， ( x ) = s g n ( ( 国而) + 6 ) ( 2 5 ) 样本点到超平面的距离 拈南陋+ 6 ) i ( 2 6 ) 要想实现最佳分划就是要求分类超平面能将两类分类正确，而且使分类间隔最大。如图 2 1 所示。 一9 一 东北大学硕士学位论文第二章支持向量机算法简介 直接计算可知超平面h i ：( c o x ，) + 6 = 1 与i - 1 2 ：( c o 毛) + 6 = - 1 之间的的距离为 t l 缈l ，那么求解最优分类问题就等同于求解如下优化问题， r a 础i n扣1 2 ( 2 7 ) s t y ，( 洄薯) + 6 ) 1 ，i = 1 ， 求得最优解白，b ) 后，就可以构造决策函数( 2 5 ) 图2 1 最优分划超平面 f i g2 1o p t i m a ls e p a r a t i n gh y p e r p l a n e 求解上述优化问题，首先引入l a g r a n g e 函数， 三( c o , a , b ) = 扣1 2 一缸( 啪叭) 删- 1 ) 其中口= ( ，嘶) r r ：为l a g r a n g e 乘子。由极值条件， v 6 三( 缈，口，b ) = 0 ，v m 三( 缈，口，b ) = 0 得到 ， 乃= 0 ， i l ， 0 9 = 乃x j_ j i - i 将( 2 1 0 ) 代入l a g r a n g e 函数( 2 8 ) ，消去国与6 ，即得原始问题的对偶问题， 一1 0 一 ( 2 8 ) ( 2 9 ) ( 2 1 0 ) 东北大学硕士学位论文第二章支持向量机算法简介 m 口a x 一圭善善儿y ，口，( 毛喵，) + 善q s t 乃q = o ， ( 2 1 1 ) 口l 0 , i = 1 ， 式( 2 1 1 ) 的解口就是原始问题的全局最优解，选择口的一个正分量，并据此计算， ， b = y j - zy t a ：q t x j ) ，一i 则所求的分类超平面为， ( 2 1 2 ) 厂( x ) = s g n ( z 口? y ，( x 而) + 6 。) ( 2 1 3 ) 最优化问题( 2 1 1 ) 能j 解口的每一个分量都与一个训练点相对应，所以所构造的分划超平 面，仅仅依赖于那些相应于口? 不为零的训练点“，y t ) ，而与相应于口：为零的那些训练 点无关。称对应于口? 不为零的i j l l 练点( 而，y ，) 的输入而为支持向量。 2 1 2 非线性分类支持向量机 前文对于线性可分问题，选择了能够正确分划训练集的超平面，或者说硬性地使训 练集关于该分划超平面的几何间隔取正值。现在讨论线性不可分问题。此时上述出发点 是行不通的，因为不存在这样的超平面，使得训练集关于该分划超平面的几何间隔取正 值。换句话说，如果继续用超平面进行分划，那么必须“软化 对间隔的要求，即允许 有不满足约束条件( 2 2 ) 和( 2 3 ) 的样本存在。通过引入松弛变量六o ，i = l ；ee 9 j 可得“软 化 了的约束条件， 咒“缈而) + 6 ) 1 一点，f = l ，( 2 1 4 ) 显然，当磊充分大时，样本点总可以满足上述约束条件。但是应该设法避免参取太大的 值。为此在目标函数里对它们进行惩罚，则原始优化问题( 2 1 ) 改为， ra=in。携二煮l-iyl 六， 亿均 s t ( ( 国x 1 ) + 6 ) 1 一直， 二j j ， 磊0 ，f _ 1 ， 其中y 0 是一个惩罚参数。 广义最优分类面的对偶问题与线性可分情况下类似，利用对偶原理，类似于线性可 分情况的推导过程可以得到线性不可分优化问题的对偶问题为， 东北大学硕士学位论文第二章支持向量机算法简介 掣一圭善善y t y j a t a j ( 毛嘻，) + 善口， 。 s t y 鸬= 0 ， ( 2 1 6 ) 0 口f 厂， i = 1 ，1 由于输入空间中的样本数据线性不可分，( 2 1 6 ) 式中的内积运算( 一x ，) 无法得到。因此， 为解决非线性可分问题，可以设法将输入数据通过非线性变换缈：x 岭伊( x ) 映射到一个 高维空间，将非线性问题转化为高位空间中的线性问题，在高维空间中求最优分类面， 这样，原问题的内积运算就变成了在高维空间中的内积运算。为得到非线性映射函数 驴( 力，支持向量机引进了内积核函数的概念，即通过计算核函数k 瓴，工，) 代替计算高维 空间中的向量内积( 伊( ) 缈 ，) ) 。这里所选用