（模式识别与智能系统专业论文）支持向量机算法的研究及其应用.pdf

浙江火学博：t 学位论文 摘要 作为结构风险最小化准则的具体实现，支持向量机方法具有全局最优、结构 筵单、推广能力强等饯点，返几年褥到了广泛嚣磷究。本文仔纲疆究了支持彝爨 机理论，并针对目前些支持向量机算法存在的缺陷，分析了产生的原因，提出 了两种新的支持向量机算法。针对支持向量机算法难以处理大规模数据的问题， 提出了甄张毅的支持向量枫分类方法。著就多类别分类阀题等方面开展了切步鲍 理论研究。 本文主要工作篷强： ( 1 ) 讨论了支持向量机理论中各种变形的支持向餐枧算法，对常规支持向 量机公式进行变形的算法主要有c s v m 系列、v s v m 系列、o n e 。c l a s ss v m 、 r s v m 、w s v m 帮l s s v m 等算法，逶过增翔蘧数矮、交量或系数等方法使公 式变形，产生出各种有某一方面优势或者一定应用范围的算法。通过比较它们备 自的优缺点等情况，为提出新的支持向量机算法做了理论准备。 ( 2 ) 禽缨了超球嚣支持囱量极算法鲍惑想，以及趣球嚣襄超乎瑟的区别。 研究了目前超球面支持向豢机算法，它们的目标函数中缺少了使分类间隔尽量大 这个条件，丽这个条件是统计学习理论中结梅风险最小纯酶体现，轰接爱睽了算 法的推广能力。因此，提出了一糖新的超球蕊支持向量机算法，具肖较好的推广 能力，成功地解决了现有超球面支持向量机算法在推广能力的缺陷。 ( 3 ) 针对菜些支持期蓬援舅法不麓勰淡样本类裂之闰差异造成懿不嶷影嫡 的缺陷，提出了一种掰的加权支持向量机算法，该算法具有补偿类别差异的优点， 可应用于解决多类剐分类问题。并且从另外一个角度对加权c - s v m 算法和加权 v + s v m 箕法夔类别 偿性2 进行了分毒写。 ( 4 ) 提出了基于粗糙集理论和支持向量机理论的粗s v m 分类方法。该方 法采用粗糙集满住约简的穗怨减少属健个数，且在属性约筒避程中选出凡缀合适 的聪，睦集鳃残毅的属性集，使模型具礴一定的抗信息丢失能力。同时充分利用支 持向量机理论的良好推广性能，提高了预测分类精度。 ( 5 ) 提出了基予主戒分分析方法和支持商量梳理谂豹去噤声麓权s v m 分 类方法。该方法通过日l 入主成分分析方法来降维去噪声，同时补偿类别豢异造成 的不利影响，撼高了预测分类精度。 ( 6 ) 把支持良羹辊理论应弱裂浮本处糕过程运幸亍状态整控中去。 关镳词：支持向量机，交形公式，加税，类剐差弊，分类精淡，超球面支持向嚣 枫算法，污拳处理过程 塑鎏尘兰堕主兰垡堡壅 ! ! ! a b s t r a c t i nt h i s d i s s e r t a t i o n ，s o m ep r o b l e m so fs u p p o r tv e c t o rm a c h i n ea l g o r i t h m sa r e a n a l y z e d t os o l v et h ep r o b l e mo fu n e v e ns i z eo fc l a s s e sa n do t h e rp r o b l e m s t w on e w s u p p o r t v e c t o rm a c h i n e a l g o r i t h m sa n dt w on e wc l a s s i f i c a t i o nm e t h o d sa r es h o w e d t h em a i nr e s e a r c hi nt h i sp a p e rc a nb e c l a s s e da sf o l l o w s ： ( 1 ) a no v e r v i e wo nav a r i e t yo fc l a s s i f i c a t i o n a l g o r i t h m sf o rs u p p o r tv e c t o r m a c h i n e ( s v m ) i sg i v e n s o m ea l g o r i t h m ss u c ha sv s v m ，o n e c l a s ss v m r s v m ，w e i g h t e ds v m a n dl s s v ma r ec o n c e n t r a t e d ( 2 ) b a s e do nt h et h e o r yo fs u p p o r tv e c t o rm a c h i n e ，an o v e l a p p r o a c ht h a t c o n t a i n ss u p p o r tv e c t o r sd e s c r i b i n gt h eh y p e r s h p e r et os e p a r a t e st h es a m p l e s i ss h o w e d ( 3 ) w h e n t r a i n i n gs e t s 埘t hu n e v e nc l a s ss i z e sa r eu s e d ，t h ec l a s s i f i c a t i o nr e s u l t b a s e do ns u p p o r tv e c t o rm a c h i n ei su n d e s i r a b l yb i a s e dt o w a r d st h ec l a s sw i t h m o r es a m p l e si nt h et r a i n i n gs e t t h a ti st os a y , t h el a r g e rt h es a m p l es i z e ，t h e s m a l l e rt h ec l a s s i f i c a t i o ne r r o r , w h e r e a st h es m a l l e rt h es a m p l es i z e ，t h el a r g e r t h ec l a s s i f i c a t i o ne r r o r t h i sp a p e r p r o p o s e sw e i g h t e ds u p p o r tv e c t o rm a c h i n e a l g o r i t h m sb a s e do nt h ea n a l y s i s o ft h ec a u s eo fs u c hp r o b l e m ，a n dt h i s a l g o r i t h mo v e r c o m e st h ed r a w b a c kw h i c hs t a n d a r ds u p p o r tv e c t o rm a c h i n e a l g o r i t h m c a n td e a l 、讲t he a c hs a m p l ef l e x i b l ya n dc o m p e n s a t e sf o rt h e u n f a v o r a b l e i m p a c t c a u s e d b y t h i sb i a s s u c h w e i g h t e ds u p p o r t v e c t o r m a c h i n e si m p r o v ec l a s s i f i c a t i o na c c u r a c yf o rc l a s sw i t hs m a l ls i z ea tt h ec o s t o fa c c u r a c yr e d u c t i o nf o rl a r g es i z ec l a s s ，a n dc a nb ea p p l i e dt ot h ec a s eo f r e g a r d i n g s m a l ls o r to fc l a s s i f i c a t i o na c c u r a c ys u c ha sf a u l td i a g n o s i s ( 4 ) an e wc l a s s i f i c a t i o nm e t h o dn a m e d r o u g hs u p p o r t v e c t o rm a c h i n ei s p r e s e n t e di nt h i sp a p e r , b a s e d o n s u p p o r tv e c t o rm a c h i n ea n dr o u g h s e tt h e o r y t h i sm e t h o dh a s h i g hp r e d i c t i v e c l a s s i f i c a t i o n a c c u r a c y w i t l lm u c hl e s s a t t r i b u t e s ，w h i c hm e a l l sl e s s s e n s o r sa n dl e s sc o s t a n di t k e e p sc e r t a i n r e d u n d a n ta t t r i b u t e st oh a v eh i g hp r e d i c t i v ea c c u r a c yi nt h ec a s eo fm i s s i n g i n f o r m a t i o nc a u s e db ys u c ha ss e n s o r s f a u l t b yg o o dp e r f o r m a n c e s o f s u p p o av e c t o rm a c h i n e ，t h i sm e t h o di n c r e a s e sc l a s s i f i c a t i o na c c u r a c yw i t h g o o dg e n e r a l i z a t i o np e r f o r m a n c e ( 5 ) an e wc l a s s i f i c a t i o nm e t h o db a s e do ns u p p o r tv e c t o rm a c h i n et h e o r ya n d p r i n c i p a lc o m p o n e n ta n a l y s i s ( p c a ) t e c h n i q u e s i s p r e s e n t e d n o i s e i s e l i m i n a t e db yp c a ，w h i c hc a ni n c r e a s e st h ep r e d i c t e dc l a s s i f i c a t i o na c c u r a c y t h ec o m p e n s a t i n gw a yf o rt r a i n i n gs e t sw i t hu n e v e nc l a s ss i z e si ss h o w ni n i v 浙江大学搏士学位论文 t h i sm e t h o d ( 6 ) t h ep r o p o s e ds u p p o r tv e c t o rm a c h i n ea l g o r i t h m sa n dc l a s s i f i c a t i o nm e t h o d s a r eu s e di nc l a s s i f y i n go p e r a t i o ns t a t eo fw a s t e w a t e rt r e a t m e n t p r o c e s s e s t h e n u m e r i c a le x p e r i m e n t ss h o wt h a tt h e s ea l g o r i t h m sa n dm e t h o d sa r ee f f e c t i v e k e y w o r d s ：s u p p o r t v e c t o rm a c h i n e ，v a r i a n tf o r m u l a t i o n s ，u n e v e nc l a s ss i z e s ，w e i g h t ， c l a s s i f i c a t i o n a c c u r a c y , h y p e r s p h e r es u p p o r tv e c t o rm a c h i n ea l g o r i t h m ，w a s t e w a t e r t r e a t m e n tp r o c e s s 浙江大学博士学位论文 第一章绪论 摘要 本章首先介绍了机器学习、统计学习理论和支持向量机基本理论等相关内 容，然后，讨论了支持向量机的主要研究内容。最后对本文的研究工作和获得 的成果做了简要的概述。 关键词：机器学习，统计学习，支持向量机 广义地讲，智能泛指人类认识世界、改造世界的能力，是物质运动的一种 特定的形式。人类智能包括了记忆、观察、想象、思考、判断、类比、推理、 学习、决策、发明、创造等。自从1 9 4 6 年计算机诞生以来。科学家又设想是否 可以运用机器来实现人类的智能。人工智能的目标就是研究如何应用机器来承 担本来由人类智能可以承担的任务。 智能技术是将人工智能方法运用于生产实际中所产生的具体的技术的总 和。例如集成了知识表示与逻辑推理技术的专家系统，基于自然语言处理理论 的机器翻译系统，基于决策理论、空间信息系统上的空间决策系统等等。 近些年来，随着计算机性能价格比的提高，以及网络的普及，i t 企业界也 越来越重视智能技术在提高产品品质与服务质量方面的作用。例如，m i c r o s o f t 公司提出的让计算机“更具有易用性”的口号，i b m 提出的商业智能解决方案， 等等。 几乎所有的智能技术均要涉及到知识的运用，而知识的获取是进行知识运 用的一个瓶颈。机器学习的目标就是研究如何从各类数据中自动地获取知识。 本文主要就人工智能中的机器学习理论中的支持向量机( s u p p o r tv e c t o r m a c h i n e 。s v m ) 理论进行讨论与研究。 1 1 机器学习的发展历史与现状 对于学习的定义，目前大家比较公认的说法是s i m o n 对学习的阐述：“如果 一个系统能够通过执行某种过程而改进它的性能，这就是学习” 陆汝矜，1 9 9 6 1 。 机器学习的研究主要经历了如下几个阶段 v a p n i k ，1 9 9 5 ；v a p n i k ，1 9 9 8 ；边 肇祺等，2 0 0 0 ；张学工，2 0 0 0 ；王钰等，2 0 0 1 1 ： 1 、1 9 4 3 年m c c u l l o e h 和p i t t s 对神经元模型( 简写为m p 模型) 的研究； 2 、五十年代，在控制理论中，使用多项式等为基函数，利用优化的方法建 立模型，以刻画被控对象的行为，这个过程在控制理论中称为辨识或参 三一 塑二塞堑丝 数估计； 3 、r o s e n b l a t t 的感知机为代表的研究，则是从m p 模型出发将扩展为多个 神经元的m p 模型作为优化算法的数学基函数； 4 、v a p n i k 提出了“统计学习理论”： 此外，z d z i s k e w p a w l a k 在1 9 8 2 年提出的粗糙集( r o u g hs e t ) 理论也有一定 的特色。它是一种新的数学工具，可以用于处理含糊性与不确定性，在数据挖 掘中发挥了重要作用 史忠植，1 9 9 7 1 。 目前，机器学习的研究已不仅是人工智能研究的重要问题，而且已成为计 算机科学与技术的核心问题。这种动力来源于数字网络的普及与计算机对社会 生活的普遍渗入，由此，根据需求，提出了一些迫切的问题f 石纯一，1 9 9 3 ；王 钰等，2 0 0 1 ：( 1 ) 发现海量数据中的规律，特别是那些非结构化的数据。这方 面主要的发展是数据中的知识发现；( 2 ) 如何对个性化的需求进行处理和分析。 1 2 有限样本的预测学习方法简介 预测学习方法是机器学习的一个重要研究领域，绝大部分机器学习算法的 应用都涉及到对数据的预测性学习，目的是从已知数据中估计相关性以达到准 确预测将来数据变化。经典的模式识别方法，各种统计方法以及近些年来出现 的各种神经网络算法都被应用于估计这种数据中固有的相关性，试图建立个 能预测未来数据的模型。虽然，这些应用在一些特殊的领域取得了一定的进展， 并且提出了一些新的概念和方法，但是，这些方法有其固有的算法缺陷：由于 不知道数据的分布密度以及有限的训练数据，常常导致了病态的训练结果，预 测效果往往不尽人意。人们迫切需要关于预测学习算法共同的概念和理论框架 以及更高效的预测学习方法。 到目前为止，几乎所有的预测学习算法都可以归结为以下三类 c h e r k a s s k y , 1 9 9 9 ： ( 1 ) 传统的统计预测方法 这类方法是在参数结构形式已知的前提下，通过训练数据，预测各参数的 值，例如：最d , - - 乘法。应用这些预测方法除了需要很强的先验知识外，还需 预先知道模型的结构形式。但是，在处理大量的实际预测问题时，常常不知道 背景知识，面对一大堆采样来的数据，也不知道模型的结构形式。由于传统统 计学研究的前提是样本数目趋于无穷大时的渐进理论，而参数预测方法几乎都 是建立在这一前提基础之上的。因此只有当采样数据趋于无穷时，参数方法的 浙江大学博士学位论文 训练结果才趋于真实的模型。由于实际样本数目是有限的，很难满足这一前提。 ( 2 ) 经验非线性预测方法 8 0 年代发展起来的人工神经网络和柔性统计方法就属于这一类。虽然，这 些新的方法克服了参数预测方法的部分弱点，能够依照需要，假设数据内在相 关性而构造非线性模型。然而，这些非线性方法缺乏统一的数学理论基础，通 常是从生物学的理论和一些学术流派中得到灵感，对于诸如神经网络中的结构 选择和权重的初值设定，仍需要借助于经验，得到的模型通常是局部最优解， 而4 全局最优。 ( 3 ) 统计学习理论 早期的统计学习理论( s t a t i s t i c a ll e a r n i n gt h e o r y ) 是从6 0 年代发展起来的 v a p n i k ，1 9 6 3 ，直到9 0 年代，它一直是作为一种针对有限样本的函数预测问题 的纯理论分析工具 v a p n i k ，1 9 9 1 。虽然，早期的统计学习理论提出了v c 维 ( v a p n i k c e r v o n e n k i s ) 理论 v a p n i k ，1 9 7 1 1 ，为衡量预测模型的复杂度，提出了 有效的理论框架。但是，它仍然是建立在经验风险最小化原则基础之上，即： 以训练的平均误差为最小的模型作为期望的最终模型。所以，早期的统计学习 理论一直停留在抽象的理论和概念的探索之中，直到9 0 年代初期，v c 维理论 还没有得到很好的应用【c h e r k a s s k y , 19 9 9 】。 9 0 年代中期，v a p n i k 和他的a t & tb e l l 实验室小组提出了s v m 算法，进 一步丰富和发展了统计学习理论，使它不仅是种理论分析工具，还是一种能 构造具有多维预测功能的预测学习算法的工具，使抽象的学习理论能够转化为 通用的实际预测算法。 在统计学习理论基础之上发展起来的s v m 算法，是一种专门研究有限样 本预测的学习方法。与传统统计学相比，s v m 算法没有以传统的经验风险最小 化原则作为基础，而是建立在结构风险最小化( s t r u c t u r a lm s km i n i m i z a t i o n ， s r m ) 原理基础之上，发展成为一种新型的结构化学习方法。它能很好的解决有 限数量样本的高维模型的构造问题，而且所构造的模型具有很好的预测性能。 s v m 算法有很多成功的应用都说明了这种基于v c 维理论而发展起来的结构化 学习方法的潜在优势。 更重要的是：作为s v m 算法基础的v c 维理论和结构最小化原则也为进一 步完善传统的统计预测方法和经验非线性预测方法提供了理论基础和统一的理 论框架。如何在此框架下重新构建各类预测方法，解决许多原来难以解决的问 题，迸一步发展和完善s v m 算法是当前亟待解决的一个问题。国际上已有许 多学者为此做了大量的工作。本文基于这一出发点，仔细研究了支持向量机理 论、方法及应用。 第一牵绪论 1 3 统计学习理论主要内容介绍 缩擒风陵最小| 趋缡藤瑾惩统计学习理论掇崮的一释运矮子小样本学习润题 的归纳原理，它包括了学习过程的一致性、边界的理论和结构风险最小化原理 等部分。它所提出的缩构风险最小化归纳学习过程克服了经验风险墩小化的缺 点，实焉中获褥了更好酌学习效巢。下蕊，魏肘此淫论酌一些主要内容逡行介 绍。 3 边髯鹣瑾论与维 边界理论主要包含了两部分，一是非构造性边界的理论，它可以通过基于 谱长溺数的概念获得；二是构造毪的边界，它的主饔润麓是运爝褐造性的概念 来估计这些国数。主要需要研究的翊题是后者。 ( 1 ) v c 维：v c 维主要刻画了给定的函数可以打散的类别的数目； ( 2 ) 一致收敛静泛纯边界； 根据榉本的分布楚秀独立，可以分别获怒不同性质的学习函数的、可以控 制学习机器之推广能力的构造性的边界。 v c 缝，简弼言之，它摇述了组成学习梭餮的函数集台的容量，也就是说 刻画了此醴数集合的学习能力。v c 维越大，函数集合越大，其相殿的学习能 力就越强。例如，对于二分类问题而言，h 题运用学习机器的函数集合将点集 以2 8 种方法划分为两类的最大的点数目，即，对于每个可能的翔分，在诧函数 集合中均存在一个函数厶，往褥此函数对萁中一个类取l ，蔼对勇姊一个类取 ，1 。如采，取在太社( 2 维实平面) 上的3 个点( 如图1 1 所示 b u r g e s ，1 9 9 8 】) ， 3 个点分别出( r ) 、( b ) 、( p ) 这3 个图形簿号来表示( 也可以 用图形符号旁的英文符号表示它们) 。设函数集合 f ( x ，a ) ) 为一组“有向线集 合”。易知，3 个点最多可以存在2 。( = 8 ) 种划分：( r p ，b ) 、( r b ，p ) 、( p b ， r ) 、( r p b ，) 、( b ，r p ) 、( p ，r b ) 、( r ，p b ) 、( ，r p b ) ；其中，二元组的 第1 项指示的是十l 类，二元组的第2 项指示的是- l 类。对于任意一个划分，我 们均可以在函数集合中发现一个有向线对应之，如图1 i 给出了所有的这8 稀 对应。划分线款方向爨指示黪是+ l 类，反向所指示鲍是一l 类e 另势，这榉的 函数集合无法划分2 维平面中任意4 个点。所以，函数集合的v c 维等于3 。 浙江大学博士学位论文 1 3 2 推广误差边界 一 图1 1 在2 维平面中被有向线打散的三个点 为构造适合于小样本学习的归纳学习原理，可以通过控制学习机器的推广 能力来达到此目的。下面给出两类学习机器的推广能力边界。 结构风险最小化的归纳学习过程克服了经验风险最小化的缺点，实用中获 得了更好的学习效果。统计学习理论给出了如下估计真实风险r 的不等式， 即对于任意a f ( f 是抽象参数集合) ，以至少1 一野的概率满足以下不等式， 厶 e ( a ) r e i n p ( a ) + 、壬，g ) ( 1 1 ) l 其中， 甲( 争 n 2 ) r 唧( 口) 表示经验风险；、 ，( 等) 称为置信风险；，是样本个数；参数忍称为 一个函数集合的v c 维，对于线性分类器，满足 v a p n i k ，1 9 9 8 】 h - 1 1 口, 1 1 2 r 2 + 1 ( 1 3 ) 其中r 为包络训练数据的最小球半径。机器学习过程不仅要使经验风险最 小，还要使v c 维尽量小，对未来样本才会有较好的推广能力，这是结构风险 最小化准女f f 的基本思想。 第一章绪论 1 3 3 结构风险最小化归纳原理 结构风险最小化归纳原理的基本想法是：如果要求风险最小，就需要不等 式( 1 1 ) e e 的两项相互权衡，共同趋于极小；另外，在获得的学习模型经验风险 最小的同时，希望学习模型的推广能力尽可能大，这样就需要h 值尽可f i g , l , ， 即，置信风险尽可能小。 根据风险估计公式( i i ) ，如果固定训练样本数目，的大小，则，控制风险 r ( a ) 的参量有两个：r 。 ) 与h 。其中， ( 1 ) 经验风险依赖于学习机器所选定的函数f ( a ，x ) ，这样，我们可以通 过控制a 来控制经验风险。 ( 2 ) v c 维h 依赖于学习机器所工作的函数集合( 如前所述) 。为了获得 对h 的控制，可以将函数集合结构化，建立h 与各函数子结构之间的关系，通 过控制对函数结构的选择来达到控制v c 维h 的目的。具体做法如下， 首先，运用以下的方法将函数集合 f ( x ，a ) ，a f ) 结构化。考虑函数嵌 套子集的集合，如图】2 v a p n i k ，19 9 5 所示， 墨c 是c c 匕 鼠 ( 1 4 ) 其中，s k = f ( x ，a ) ：a f t ) ，并且有 = u & ( 1 5 ) k 结构s 中的任何元素墨( 或一个函数集合) 拥有一个有限的v c 维；且 岛吃，吃， ( 1 6 ) 图1 2 由函数的嵌套子集决定的函数的集合 如果给定一组样本( x l ，m ) ，( x 2 ，儿) ，( _ ，y ) ，结构风险最小化原理在函 浙江大学博士学位论文 数子集s 中选择一个函数f ( x ，乜，k ) 来最小化经验风险，同时，s 女确保置信风 险是最小的。 以上的思想就称为“结构风险最小化归纳原理”。为了进一步说明，请看 图1 3 v a p n i k ，1 9 9 5 1 ，已知一个嵌套的函数子集序列s l ，是，s n ，它们的v c 维分别对应为岛，琏，亿。而且有如如，吃。图中给出了真实风险、 经验风险与置信风险分别与v c 维h 的函数变化关系曲线。显然随着h 的增加， 经验风险r 。( 日) 递减，这是因为h 增加，根据v c 维的定义，对应的函数集 合的描述能力增加，学习机器的学习能力就增强，可以使有限样本的经验风险 b 很快地收敛，甚至于变为0 ；根据式( 1 1 ) ，置信风险v ( ；) 随着h 的增加而增 f 加；这样，真实风险r ( 口) 是一个凹型曲线。所以，要获得最小的真实风险，就 需要折中考虑经验风险与置信风险的取值。 风险 欠学习 过学习 图1 3 结构风险最小归纳原理图 c 维 根据这一分析，可以得到两种运用结构风险最小化归纳原理构造的学习机 ，l。l 第一章绪论 器的思路： ( 1 ) 给定了一个函数集合，按照上面的方法来组织一个嵌套的函数结构， 在每个子集中求取最小经验风险，然后选择经验j x l 险与置信风险之和最小的子 集。当子集数目较大的时候，此方法较为费时。甚至于不可行。 ( 2 ) 构造函数集合的某种结构，使得在其中的各函数子集均可以取得最小 的经验风险( 例如，使得训练误差为o ) 。然后，在这些子集中选择适当的子集 使得置信风险最小，则相应的函数子集中使得经验风险最小的函数就是所求解 的最优函数。 支持向量机采用的就是方法( 2 ) ，将在下面做详细介绍。 1 4 支持向量机算法的发展历史和现状 作为s v m 的奠基者v v a p n i k 早在6 0 年代就开始了统计学习理论的研究 【v a p n i k ，1 9 6 3 ，1 9 7 1 年，v v a p n i k 和a c h e r v o n e n k i s 在“t h en e c e s s a r ya n d s u f f i c i e n tc o n d i t i o n sf o rt h eu n i f o r m s c o n v e r g e n c e o fa v e r a g e st o e x p e c t e d v a l u e s ”一文中，提出了s v m 的一个重要的理论基础_ v c 维理论。 19 8 2 年，在“e s t i m a t i o no f d e p e n d e n c e s b a s e do n e m p i r i c a ld a t a ”一书中， vv a p n i k 进一步提出了具有划时代意义的结构风险最小化原理，堪称为s v m 算法的基石。 1 9 9 2 年，b o s e r , g u y o na n dv a p n i k 在“at r a i n i n ga l g o r i t h mf o ro p t i m a l m a r g i n c l a s s i f i e r s ”书中，提出了最优边界分类器 b o s e r , 1 9 9 2 。 1 9 9 3 年，c o r t e s 和v a p n i k 在“t h es o f t m a r g i n c l a s s i f i e r ”一书中，进一步 探讨了非线性最优边界的分类问题 c o r t e s ，1 9 9 3 1 。 1 9 9 5 年，vv a p n i k 在“t h en a t u r eo f s t a t i s t i c a ll e a r n i n gt h e o r y ”一书中， 完整地提出了s v m 分类。 1 9 9 7 年，v v a p n i k ，s g o k o w i c h 和a s m o l a ，发表的“s u p p o r t v e c t o r m e t h o d f o rf u n c t i o n a p p r o x i m a t i o n ，r e g r e s s i o ne s t i m a t i o na n d s i g n a lp r o c e s s i n g ”一文中， 详细介绍了基于s v m 方法的回归算法和信号处理方法。 由于s v m 算法的潜在应用价值，吸引了国际上众多的知名学者，近几年 出现了许多发展和改进的支持向量机算法，如文献 s c h s l k o p f , 1 9 9 6 ；s c h f l k o p f , 1 9 9 7 a ；s c h o l k o p f , 1 9 9 8 a ；s m o l a ，1 9 9 8 a ；b e m n e t t ，1 9 9 8 ；w e s t o n ，1 9 9 9 a ；z h a n g x u e g o n g ，1 9 9 9 1 所述。有关非线性s v m 中核的研究方法，如文献 s c h 6 1 k o p f , 1 9 9 8 b ；b u r g e s ，1 9 9 7 ；b u r g e s ，1 9 9 8 ；b u r g e s ，1 9 9 9 ；s c h 6 1 k o p f , 1 9 9 7 b 所述。值得一 提的是：1 9 9 8 年，s m o l a 在他的博士论文中详细研究了s v m 算法中各种核的 机理和应用，为进一步完善s v m 非线性算法做出了重要的贡献 s m o l a , 1 9 9 8 b 】。 浙江大学博上学位论文 s v m 在模式识别领域已经有了一些应用，如手写体数字识另l j s c h 6 1 k o p f , 1 9 9 5 ；y a n g ，1 9 9 4 ；y a n g ，1 9 9 7 】、人脸识别与人脸检测f o s u n a ，1 9 9 7 a ；o s u n a ， 1 9 9 7 b 、以及文本分类 j o a c h i m s ，1 9 9 7 ；j o a c h i m s ，1 9 9 8 ；j o a c h i m s ，1 9 9 9 1 等各种领 域 k r e j e l ，1 9 9 9 ；c a iy u d o n g ，2 0 0 2 1 。此外，s v m 还很好地应用于时间序列分析 【m u k h e r j e e ，1 9 9 7 1 和回归分析 d r u c k e r , 1 9 9 7 ；k w o k ，1 9 9 8 ；s c h 6 1 k o p f , 1 9 9 8 等领 域的研究。例如，m i t 、b e l ll a b 和微软研究所等已成功地将s v m 算法应用于 动态图象的人脸跟踪，信号处理，语音识别，图象分类和控制系统等诸多领域 c o r t e s ，1 9 9 5 ；g u y o n ，1 9 9 7 ；e o s u n a ，1 9 9 7 ；v a p n i k ，1 9 9 7 】。 1 5 支持向量机基本方法 假定大小为z 的训练样本集 ( x ，y ，) ，i = 1 ，2 ， ，由二类别组成，如果 x ，r 属于第1 类，则标记为正( 咒= 】) ，如果属于第2 类，则标记为负( 儿= 一1 1 。学习的目标是构造一个决策函数，将测试数据尽可能正确地分类。针对训 练样本集为线性或者非线性两种情况分别讨论。 15 1 线性情况 如果存在分类超半囱 x + b = 0( 1 7 ) 使得 裂兰z=一10,1 xb1 y i 1 ，i 乩2 ， s ， + 一，= 一，= 1 ，f 则称训练集是线性可分的，其中x 表示向量r 与x r 的内积。式 ( 1 7 ) 和式( 1 8 ) 中的r ，b r 1 都进行了规范化，使每类样本集中与分类超 平面距离最近的数据点满足式( 1 8 ) 的等式要求。对于式( 1 8 ) ，可写成如下形式 y t 的x ，+ b ) 2 1 ，i = l ，2 ， ( 1 9 ) 由统计学习理论知，如果训练样本集没有被超平面错误分开，并且距超平 面最近的样本数据与超平面之间的距离最大，则该超平面为最优超平面( 如图 1 4 所示) ，由此得到的决策函数 f ( x ) = s i g n ( x + b ) ( 1 1 0 ) 第一章绪论 ( o x + b = 一1 x + b = 0 为最优超平面 图1 4 最优分类超平面 。第1 类 a 第2 类 支持向量 冥推厂能力最优，其中s i g n ( ) 为符号凼数。最优趟半田1 阴汞肼斋晏最大化 2 1 l 吣1 l ，即最小化l b l l 2 ，为如下的二次规划问题 m 。i ，。n - ；l l o l l 2( 。) s t m 油x ，+ b ) 1i = 1 2 ， 训练样本集为线性不可分时，需引入非负松驰变量专，i = l ，2 ，z ，分类超 平面的最优化问题为 m 。i n ，- - 1t o b 1+c毒2，6智“ s t 只( 1 x ，+ 6 ) 1 一专 ( 1 1 2 ) 专0 ，i = 1 ， 其中，c 为惩罚参数，c 越大表示对错误分类的惩罚越大。采用拉格朗日乘子 法求解这个具有线性约束的二次规划问题，即 。= j 1 恻1 2 + l 善! 专一善l 毗y ； x j + 6 ) 一1 + 专】一喜屈毒( 1 1 3 ) 其中，口，屈为拉格朗日乘子o 口，0 屈，由此得到 罢：一l 哪x ，：o ( 】1 4 ) a 二一i = l ” 蓑一喜哪_ o 嘲 浙江大学博士学位论文 嚣= c - a , - ，, 2 。 s ， 将式( 1 1 4 ) - ( 1 1 6 ) 代入式( 1 1 3 ) ，得到对偶最优化问题 呀n 吉7 q n e k s t 0 必c ，f = 1 ，( 1 1 7 ) y t a = 0 最优化求解得到的中，口，可能是：a i = 0 ；0 口， c ：o i = c ；后两者 所对应的x ，为支持向量( s u p p o r tv e c t o r , s v ) 。由式( 1 1 4 ) 可知只有支持向量对 有贡献，也就对最优超平面、决策函数有贡献，支持向量由此得名，对应的学 习方法称之为支持向量机。在支持向量中，所对应的x ，称为边界支持向量 ( b o u n d a r ys u p p o r t v e c t o r , b s v ) ，实际上是错分的训练样本点，所对应的x 称 为标准支持向量( n o r m a ls u p p o r tv e c t o r ，n s v ) 。根据k a r u s h - k u h n t u c h e r 条件 v a p n i k ，1 9 9 5 1 ( t 称k k t 条件) 知，在最优点，拉格朗日乘子与约束的积为0 ， 即 q 眦 x ，+ 6 ) 一1 + 戋】= ( 1 1 8 1 i尼专= 0 、。 对于标准支持向量( 0 o t t 0 ，则由式( 1 1 8 ) 得到 皇= 0 ，因此，对于任一标准支持向量，满足 y f 的- x ，+ 6 ) = 1 ( 1 1 9 ) 从而计算参数b 为 b = 乃一x ，= 咒一哆乃x j x ，x f j n ( 】2 0 ) i j e j 为了计算可靠，对所有标准支持向量分别计算b 的值，然后求平均，即 6 = 古( 只一哆乃( x ，x ，) ) ( 1 2 1 ) v n s vx i j n x j 其中，n s v 为标准支持向量数，j n 为标准支持向量的集合，3 为支持向量的 集合。 由式( 1 1 9 ) 可知，支持向量机就是满足式( 1 1 6 ) 要求的样本数据，支持向量 如图1 4 所示。2 ( 1 1 7 ) 中的约束条件约束了，b 使得经验误差为0 ，同时最小 化i b l l 2 v c 维最小，因此，式( 1 1 7 ) 的最优化体现了结构风险最小化准则，具 l 一塑二雯笪堡 有较好的推广能力。 1 5 2 非线性情况 训练集为非线性时，通过一个非线性函数矽( ) 将训练集数据x 映射到一个 高维线性特征空间，在这个维数可能为无穷大的线性空间中构造最优分类超平 面，并得到分类器的决策函数。因此，在非线性情况，分类超平面为 ( x ) + b = 0 ( 1 2 2 ) 决策函数为 f ( x ) = s i g n 曲( x ) + b 最优分类超平面问题描述为 ( 1 2 3 1 魄圭如+ c 善1 专 s t y f ( t o o ( x ，) + 6 ) 1 一毒( 1 2 4 ) 专0 ，扛1 ， 类似于1 5 1 节，得到对偶最优化问题 f 厶：圭呸一丢杰杰q 哆咒乃矿( x i ) ( x ，) m a x 1 爿p 1 。f ：i 一丢杰圭a f f y s k ( x 州 l i = 11 = 1 j = l s t 0 口f c g g i y i = 0 ( 1 2 5 ) 其中k ( x ，x ，) = ( x ，) 矽( x ，) 称为核函数。决策函数和参数6 分别为 ， 夕( x ) = s i g n ( 乃q k ( x ，x ) + 6 ) ( 1 2 6 ) i = 1 6 2 忐( 圹荟峨酢川) 其中n s v 为标准支持向量数，j n 为标准支持向量的集合，j 为支持向量的集 、，l，j o d 式( 1 2 5 ) 一式( 1 2 7 ) 失w ，尽管通过非线性函数将样本数据映射到具有高维甚 至于无穷维的特征空间，并在特征空间中构造最优分类超平面，但在求解最优 化问题和计算决策函数时并不需要显式计算该非线性函数，而只需计算核函数， 从而避免特征空间维数灾难问题。核函数的选择必须满足m e r c e 条件【、，a p i l i k ， 1 9 9 5 。常见的核函数有线性函数k ( x ，x ) = x ，x 、多项式函数k ( x ，x ) = ( x ，+ x + 1 ) 4 、径向基函数k ( x ，x ) = e x p ( 一0 x - - x i l | 2 盯2 ) 、多层感知器函数 k ( x ，x ) = t a n h ( k x ，x + 0 ) 。 对于式( 1 1 8 ) 的k k t 条件，也可以写为( 非线性情况1 iy i o ( x ，) + 6 ) 1q = 0 y i 矽( x ，) + b ) = 10 口 c( 1 2 8 ) 【y ，的o ( x ，) + b ) 1口，= c 由于k k t 条件是充要条件，利用上式可判别a 是否为最优。 1 5 3 支持向量机的说明 超平面的分类