（应用数学专业论文）模糊支持向量机.pdf

摘要 内容摘要：支持向量机( s u p p o r t v e c t o r m a c h i n e s ，s v m ) 是v a p n i k 等人根据统计学习理论提出的一种机器学习方法。它是建立在 v c 维和结构风险最小化原则基础上的，利用核函数把非线性可分 数据映射到高维特征空间，使其在高维特征空间中线性可分。同 时，利用核函数计算内积可避免“维数灾难”。由于支持向量机具 有较好的泛化性和学习性能，该技术已成为机器学习的研究热点， 并在很多领域得到成功应用，如模式识别、图像分类、预测等方 面。 但是，作为一种尚未成熟的新技术，支持向量机目前存在着 许多局限。客观世界存在大量的模糊信息，如果支持向量机的训 练集中含有噪声或野点时，这些含有“异常 信息的样本在特征 空间中常常位于分类面附近，导致获得的分类面不是真正的最优 分类面。针对这种情况，台湾学者l i n 等提出了模糊支持向量机 ( f u z z ys u p p o r t v e c t o rm a c h i n e s ，f s v m ) ，根据不同输入样 本对分类的贡献不同，赋予不同的隶属度，将噪声或野点与有效样 本区分开。虽然f s v m 对传统的支持向量机有所改善，但隶属度 函数的确定是f s y m 方法的难点。 目前，没有统一的确定模糊隶属度函数的方法，本文提出一种基 于线性规划的一类分类算法确定隶属度，这样确定的隶属度，即考 虑到样本到类中心的距离，又考虑到样本属于该类程度的大小，从 而提高分类效果。本文首先对支持向量机的构造原理和基础理论进 行分析和研究。其次，对目前几种模糊支持向量机隶属度的确定方 i 模糊支持向量机 法进行论述，并在此基础上提出一种基于线性规划的一类分类算法 确定隶属度。最后，给出模糊支持向量机分类方法与传统支持向量 机分类方法的对比实验。实验结果表明：模糊支持向量机比传统的 支持向量机有更好的分类效果，能够削弱噪声或野点的影响。 关键词：统计学习理论，线性规划，模糊支持向量机，隶属度 a b s t r a c t c o n t e n t ：s u p p o r tv e c t o rm a c h i n e s ( s v m ) ，w h i c hw a sp r o p o s e db y v a p n i ka n ds o m eo t h e r s ，i sam e t h o do fm a c h i n el e a r n i n ga c c o r d i n g t ot 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 ti sb a s e do nv cd i m e n s i o na n d 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 e r n e lf u n c t i o ni su s e dt om a p t h en o n - l i n e a rs e p a r a b l ed a t ai n t oah i g h e rd i m e n s i o n a lf e a t u r es p a c e s oi tc a nb es e p a r a t ei nt h eh i g h e rd i m e n s i o n a lf e a t u r es p a c e m e a n - w h i l e ，u s i n gk e r n e lf u n c t i o nt oc a l c u l a t ei n n e rp r o d u c tt h a tc a d a v o i d 。d i m e n s i o nd i s a s t e r b e c a u s es v mh a sb e t t e rg e n e r a l i z a t i o na n d l e a r n i n gp o w e r ，t h i st e c h n o l o g yh a st u r n e di n t ot h et o p i co fm a c h i n e l e a r n i n g ，a n da l s og a i n e ds u c c e s s f u la p p l i c a t i o n si nm a n yf i e l d s ，s u c h a sp a t t e r nr e c o g n i t i o n ，i m a g ec l a s s i f i c a t i o n ，f o r e c a s t i n ga n ds oo n b u ta san e wt e c h n o l o g y , s v m ，w h i c hs t i l lh a ss o m el i m i t a t i o n s t h e r ei sl o t so ff u z z yi n f o r m a t i o ni nt h eo b j e c t i v ew o r l d i ft h en o i s e s o ro u t l i e r se x i s t si nt h et r a i n i n gs e to fs v m ，t h e s e “a b n o r m a l ”s a m p l e s a l w a y sc l o s et oc l a s s i f i c a t i o ns u r f a c e s ot h eg a i n e dc l a s s i f i c a t i o ns i l l ：- f a c ei sn o tt h et r u eo p t i m a lc l a s s i f i c a t i o ns u r f a c e f u z z ys u p p o r tv e c t o r m a c h i n e si sp r e s e n t e db yl i n ，t h e nt h ec o r r e s p o n d i n gm e m b e r s h i pi s g i v e na c c o r d i n gt od i f f e r e n ti n p u td a t aa f f e c t so nt h ec l a s s i f i c a t i o nr 争 s u l t s s ot h i sm e t h o de f f e c t i v e l yd i s t i n g u i s h e sb e t w e e nt h en o i s e so r o u t l i e r sa n dt h ev a l i ds a m p l e s a l t h o u g hf s v mi sp e r f e c tt h a nt r a d i - t i o n a ls v m ，t h ed e f i n i t i o no fm e m b e r s h i pf u n c t i o ni st h ed i f f i c u l t yo f f s v m a tp r e s e n t ，t h e r ei sn o tu n i f i e dm e t h o dt h a td e t e r m i n ef u z z ym e m - b e r s h i pf u n c t i o n ，o n e - c l a s sc l a s s i f i c a t i o na l g o r i t h mb a s e d o nl i n e rp r o - g r a m m i n gi su s e dt od e t e r m i n em e m b e r s h i p i nt h i sp a p e r i tn o to n l y t h i n ko v e rt h ed i s t a n c eb e t w e e nt h es a m p l et oc l a s sc e n t e r ，b u ta l s o t h i n ko v e rh o wm u c ht h es a m p l eb e l o n gt ot h ec l a s s s ot h i sm e t h o d c a ni m p r o v ec l a s s i f i c a t i o nr e s u l t f i r s t ，s t r u c t u r a lp r i n c i p l ea n db a s i c t h e o r yo fs v ma r ea n a l y z e da n dr e s e a r c h e di nt h i sp a p e r s e c o n d ， i n 模糊支持向量机 d e f i n i t i v em e t h o d so fe x i s t i n gm e m b e r s h i pa x ed i s c o u r s e d o nt h eb 和 s i so ft h eo n e - c l a s sc l a s s i f i c a t i o na l g o r i t h mo fl i n e a rp r o g r a m m i n gi s p r o p o s e dt od e t e r m i n em e m b e r s h i p a tl a s t ，c o n t r a s t i v ee x p e r i m e n t 0 ff s v mc l a s s i f i c a t i o na n dt r a d i t i o n a ls v mc l a s s i f i c a t i o ni sg i v e n e x - p e r i m e n t a lr e s u l t si n d i c a t et h a tf u z z ys u p p o r tv e c t o rm a c h i n e sy i e l d s b e t t e rc l a s s i f i c a t i o nr e s u l tt h a nt h et r a d i t i o n a ls v m t h u st h ee f f e c t s o ft h en o i s eo ro u t l i e r sc a nb ed i m i n i s h e s 。 k e yw o r d s ：s t a t i s t i c a ll e a r n i n gt h e o r y , l i n e rp r o g r a m m i n g ，f u z z y s u p p o r tv e c t o rm a c h i n e s ，m e m b e r s h i p 学位论文独创性声明 本人承诺：所里交的学位论文是本人在导师指导下所取得的研究成果。论 文中除特别加以标注和致谢的地方外，不包含其他人和其他机构已经撰写或发表 过的研究成果，其他同志的研究成果对本人的启示和所提供的帮助，均已在论文 中做出了明确的声明并表示谢意。 学位论文作者签名：亩11 j e 1期：们譬5 学位论文版权使用授权书 本学位论文作者完全了解辽宁师范大学有关保留、使用学位论文的规定，及 学校有权保留并向国家有关部门或机构送交复印件和磁盘，允许论文被查阅和借 阅。本人授权辽宁师范大学，可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或其他复制手段保存、汇编学位论文。保密的论 文在解密后使用本授权书。 学位论文作者签名：却帕 指导教师签名：翻扎 日 期：知昭- r 模糊支持向量机 1 引言 模糊支持向量机 1 1 研究目的和意义 支持向量机( s v m ) 1 l 是2 0 世纪9 0 年代中期由v a p n i k 2 1 等人提出的一种新 的机器学习算法，它是以统计学习理论( s t a t i s t i c 赋l e a r n i n gt h e o r y ，s l t ) 为基础的，这使得支持向量机有很强的理论基础和泛化能力。该方法在很多情 况下可以克服“维数灾难”等传统困难，现已成为机器学习的热点，并在很多 领域得到成功应用，如模式识别【3 】、图像分类【4 】、预测【5 】等方面，具有良好的 应用价值和发展前景。 统计学习理论【6 】是建立在结构风险最小化原则基础上的，它是专门针对小 样本情况下的机器学习问题而建立的一套理论体系。其核心思想是对于一个给 定的具有有限数量训练样本的学习任务，如何在准确性和机器容量进行折衷， 以得到最佳的推广性能。此理论为机器学习问题建立了一个良好的理论框架， 较好地解决了小样本、非线性和局部极小点等实际问题。 支持向量机方法是建立在y c 维( y dd i m e n s i o n ) 和结构风险最小化原 则 7 ( 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 y m 对于噪声或野点是非常敏感的。针对 这种情况，台湾学者l i n s , 9 等提出了模糊支持向量机，根据不同输入样本对分 类的贡献不同，赋予不同的隶属度，从而削弱噪声或野点对分类的影响。 目前没有统一的确定模糊隶属度函数的方法。本文正是在上述背景下展开 学习和工作的，提出一种新的基于线性规划的一类分类算法确定隶属度。该方 法利用模糊支持向量机的思想，结合支持向量机分类技术，表现出很好的分类 效果，从而提高分类精度。 模糊支持向量机 1 2 研究现状 支持向量机理论源于v a p n i k 等人提出的用于解决模式识别问题的方法。 自1 9 9 5 年以来，在算法、设计和实现等方面取得丰硕的成果。s v m 最初可以 解决两类分类问题，不能直接用于多类分类。对于多类分类问题，基本上都是 将k 类分类问题转化为若干个两类分类问题。目前，关于利用s v m 解决多类 分类问题主要有下列几种方法： ( 1 ) 一对多( o n e 一a g a i n s t 一口肌，1 一u r ) 其基本思想是把某一种类别的样本当作一个类别，剩余其它类别的样本当 作另一个类别，这样就变成了一个两类分类问题。这种分类方案的缺点是训练 样本数目大，训练困难。 ( 2 ) 一对一( o n e a g a i n s t o n e ，1 一t ，一1 ) 其基本思想是在多类别中，任意抽取两类两两配对，转化成多个两类问题 进行训练学习。识别时，对所构成的多个分类进行综合判断，一般可采用投票 方式来完成多类识别。这种分类方案存在一个明显的缺点，就是子分类器过 多，测试时需要对每两类都进行比较，导致测试速度慢。 ( 3 ) s v m 决策树( d e c i s i o n t r e e m e t h o d ，d t m ) 它通常和二叉决策树【1 0 】结合起来，构成多类别的识别器。这种方法的缺 点是如果在某个节点上发生了分类错误，将会把错误延续下去，该节点后续下 一级节点上的分类就失去了意义。 由于s y m 在构造分类过程中存在不可分区域，对于分类问题存在一定的 局限性。模糊支持向量机( f s y m ) 的提出就可以解决这一问题。它是对传统支 持向量机的一种改进和完善。模糊支持向量机主要有下列几种： 第一种方法是由日本学者t a k u g a 与s h i g e o 1 1 】于2 0 0 1 年和2 0 0 2 年提出 的。此方法主要是针对o n e a g a i n s t a l l 与o n e a g a i n s t o n e 支持向量机 存在决策盲区而提出的。这种方法去除了决策盲区，提高了支持向量机的分类 效率。 另一种方法于2 0 0 2 年由台湾学者c h u n - f ul i u 、s h e n g - d ew a n g 、h a n p a n gh u a n g 与y i h u n gl i u 1 2 】提出的，这一种方法较为常用。其出 发点是：数据中各个样本点对分类效果的作用是不同的，根据不同输入样本对 分类的贡献不同，赋予不同的隶属度，从而削弱噪声或野点对分类的影响。 但是，目前没有统一的确定模糊隶属度的方法，本文所作的主要工作是对 后一种模糊支持向量机的研究和实践，提出一种基于线性规划的一类分类算法 2 模糊支持向量机 确定模糊隶属度，这样确定的隶属度，即考虑到样本到类中心的距离，又考虑 到样本属于该类程度的大小，从而提高分类效果，可大大减小噪声或野点对分 类的影响。 1 3 论文结构 第一章简要概述了支持向量机的原理，介绍了其发展及现状，指出支持向 量机目前存在的不足，本文正是在这种研究背景下阐述模糊支持向量机并指出 本文所做的主要工作。 第二章从支持向量机的机器学习、学习过程一致性的条件及最优化理论等 定义和定理出发，介绍了统计学习理论，为后面知识的学习奠定基础。 第三章从支持向量机分类角度着手，就其分类的几种情况详细介绍了支持 向量机理论。 第四章提出一种采用线性规划的一类分类算法确定模糊支持向量机隶属 变，并从其理论以及通过标准数据实验来说明此种方法的可行性。 第五章是对全文的总结与展望。 3 模糊支持向量机 2 统计学习理论 2 1机器学习的基本知识 人工智能专家s i m o n 曾经说过：“如果一个系统能够通过执行某种过程而 改进它的性能，这就是学习。人们把从过去的数据和知识中学习并获取规律 的能力称为“学习能力”。利用获得的规律不仅可以解释已知现象，而且能够 对未知现象做出正确的预测和判断，这种能力称为“泛化能力”。机器学习是 现代人工智能技术的一个重要研究内容，主要是从训练数据( 样本) 出发寻找规 律，利用这些规律对未知数据或者无法观测的数据进行预测，使其具有良好的 泛化能力。机器学习按其实现方法大致分为三种：经典的参数统计估计方法、 人工神经网络和统计学习理论。但前两种方法存在需要欲先已知样本分布或过 拟合等缺点，而v a p n i k 等人提出的以统计学习理论为基础的支持向量机，可 以克服这些缺点，开始受到越来越广泛的重视。 2 2 机器学习问题表示 机器学习的目的是根据给定的训练样本求对某系统输入输出之间依赖关系 的估计，使它能够对未知输出做出尽可能准确的预测。一般可以表示为：变量 y 与z 之间存在一定的未知依赖关系，即存在一个未知的联合概率f ( x ，3 ) ，机 器学习就是根据n 个独立同分布观测样本： ( x l ，y 1 ) ，( x 2 ，耽) ，( ，) 戤舻 在一组函数 ，( z ，叫) ) 中求一个最优的函数f ( x ，w o ) 依赖关系进行估计，使 预测期望风险 r ( w ) = i ( y ，f ( x ，w ) ) d f ( x ，y )( 1 ) ， 最小，其中 ，( z ，伽) ) 称作预测函数集，w 为函数的广义参数， ，( z ，彬) ) 可以 表示任何函数集，l ( u ，f ( x ，训) ) 为由于用f ( x ，w ) 对y 进行预测而造成的损失， 不同类型的学习问题有不同形式的损失函数。 因此，机器学习问题也可以表示为，从一组独立同分布的观测样本出发， 通过最小化风险泛函r ( 叫) ，确定学习机器的广义参数w 的过程。 4 模糊支持向量机 2 3 学习过程一致性的条件 学习过程的一致性是统计学习理论的基础，也是与传统渐近统计学的基本 联系所在，只有满足学习过程一致性条件，才能保证在学习样本无穷大时，经 验风险最小化原则下得到的最优结果趋近于使期望风险最小的最优结果。经验 风险定义为： ( 硼) = 熹( 玑，f ( x i , 伽) ) ( 2 ) 。 i - - 1 设使经验风险( 2 ) 式最小化的风险值为亿唧( 蜘) ，记r ( w o ) 为在l ( y ，厂( z ，撕) ) 下( 2 ) 式所取得的真实风险值( 期望风险值) 。当下面的两个序列依概率收敛于 同一个极限，即： r ( w o ) 暑i n f r ( w ) r m p ( 帅) 与i n f r ( w ) 扎_ 0 0 则称这个经验风险最小化过程是一致的，经验风险和期望风险的关系如图2 1 所示。 下一定理给出了经验风险最小化成立的充要条件。 定理l ( 学习理论的关键性定理) 对于有界的损失函数，经验风险最小化学 习一致的充分必要条件是经验风险在如下意义上一致地收敛于真实风险： l i mp s u p ( r ( w ) 一见唧( 叫) ) 1 = 0 ，垤 0 ( 3 ) n h o 。 卸 其中，p 表示概率。定理将学习一致性的问题转化成( 3 ) 式中的一。致性收敛问 题同时依赖于预测函数集和样本的概率分布，与( 3 ) 式中的单边一致性收敛相 5 模糊支持向量机 对应的有双边一致性收敛，即： l i mp s u pl r ( w ) 一见m p ( 叫) i e 1 = o ，垤 0 ( 4 ) n ”w t | ， 学习过程中，经验风险和期望风险都是预测函数的泛函。因此，可以通过求 使经验风险最小化的函数来逼近能使期望风险最小化的函数。但是学习理 论的关键性定理给出了经验风险最小化原则成立的充分必要条件，并没有给 出什么样的学习方法能够满足这些条件。因此，统计学习理论定义了一系 列的指标来衡量函数集的学习性能，最重要的一个指标是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 ) 。 2 3 1y c 维 y c 维作为统计学习理论中的一个核心概念，是对函数集学习性能的最好描 述。y c 维反映了函数集的学习能力，v c 维越大则学习机越复杂。 设有一个指示函数集，( z ，佗) 和一组佗个训练样本的样本集z n = 忍= ( 以，玑) ，i = 1 ，佗) 。考虑函数集的分散性，看函数集中的函数能对这组样本 实现多少种不同的分类，记这个数目为n ( z n ) 。 定义1 ( 随机熵) 定义指示函数集对某个样本集能实现的不同分类组合数目 的对数为函数集在这个样本集上的随机熵，记作日( ) = h l ( ) 。 定义2 ( 生长函数)函数集的生长函数定义为它是在所有可能的样本集上的 最大随机熵，即g ( ) = m a x l i l ( ) 。 定理2 函数集学习过程一致收敛的充分必要条件是对任意形式的样本分 布，都有 1 i m 蚴：0 ( 5 ) n h o 扎 且这时学习过程的收敛速度一定是快的。 定理3 任何生长函数，它或者满足等式 a ( n ) = 礼i n 2( 6 ) 或者受限不等式 a ( n ) h l n ( 菩+ 1 ) ，扎 h ( 7 ) 使得当n = h ，有a ( n ) = h i n 2 ，g ( n + 1 ) ( h + 1 ) i n2 。生长函数的这种性质， 如图2 2 所示。 6 模糊支持向量机 h 图2 2 生长函数 因此，函数的v c 维可以定义为对于一个指示函数集，若其生长函数是线 性的，则其v c 维是无穷大；若其生长函数是以参数为h 的对数函数为上界， 则其v c 维有限且等于h 。 2 3 2 推广性的界 统计学习理论系统地研究了对于各种类型的函数集，经验风险和实际风险 之间的关系，即推广性的界【1 3 】。关于两类分类问题的结论是：对指示函数集中 的所有函数( 包括经验风险最小的函数) ，经验风险见唧( 叫) 和实际风险r ( w ) 之间以至少1 一科1 4 】的概率满足如下关系： 冗( 伽) 冗唧p ( 叫) 4 - l h ( 1 n ( 2 n h ) + 1 ) - l n ( t 4 ) 1 ( 8 ) 或简写成： r ( w ) 亿仇p ( 伽) 4 - 圣( h n )( 9 ) 其中，h 是函数集的v c 维，佗是样本数，7 7 是满足0 叩 1 的参数，圣( h l n ) 称作置信范围( c o n f i d e n c ei n t e r v a l ) ，置信范围不但受置信水平1 一，7 的影 响，而且是函数集的y c 维和训练样本数目的函数，并随着它们比值的增加而 单调减小。f 因为这个界限反映了根据经验风险最小化原则得到的推广能力，所 以称它为推广性的界。) 它表明在有限样本训练下，学习机v c 维越高，则置 信范围越大，导致真实风险与经验风险之间可能的差别越大，这就是出现过学 习现象的原因。 7 模糊支持向量机 2 3 3结构风险最小化原则 我们已经发现，经验风险最小化原则在样本数目有限时是不合理的，因为 我们需要同时最小化经验风险和置信区间。经验风险依赖于，的选择，而置信 区间则是函数族f = 厂( z ，叫) ，w q ) 的v c 维h 的增函数。简单的说，当集 合f 比较大时，可以选择适当的，使得r 。m p ) 比较小，而此时f 的v c 维比较大，也会使置信区间比较大：反之，当缩小集合f 时，f 的y c 维会 降低，而p ( 伽) 有可能增大，所以两者有互相矛盾的倾向。为了解决这一问 题，v a p n i k 等人提出了结构风险最小化原则。 结构风险最小化原则如图2 3 如示。 围 函数集子集：5 i 匕5 lc 毛 v c 维：hs 茎旭 圈2 3 结构风险最小化原则 其基本思想是先把函数集f = ，( z ，叫) ，w q ) 分配为一系列嵌套的函数 子集结构： 8 1c8 2c c8 kc cs ( 1 0 ) 8 模糊支持向量机 每个函数子集的置信范围圣按从小到大的顺序排列，在v c 维上也满足这种对 应的大小关系： 1 2 七 ( 1 1 ) 对应于一组嵌套的函数子集，每个子集鼠内部的置信范围是相同的，在每一 个子集内部寻找最小的经验风险。选择最小经验风险和置信范围之和最小的子 集，就可以达到使期望风险最小的目的。结构风险最小化原则实际上是在训练 样本逼近精度和学习模型复杂度之间折衷1 1 5 。 2 4 最优化理论 支持向量机涉及两个凸规划问题一原始问题和对偶问题，并且由这两个问 题之间的关系建立算法。因此优化理论也是支持向量机的重要理论基础。k k t 条件和w o l f e 对偶是最优化理论1 1 6 】两个核心概念。 考虑凸约束问题： m i n i ( z ) s t c ( z ) 0 ，i = 1 ，p( 1 2 ) c ) = 0 ，i = p + 1 ，p + q ，z 形 其中目标函数，( z ) 和约束函数c ( z ) ，i = 1 ，p 都是凸函数，而c ( z ) = 0 ，i = p + 1 ，p + q 都是线性函数。 定理4 ( 凸约束问题的解) 考虑凸约束问题( 1 2 ) ，设d 是问题的可行域： d = z l q ( z ) 0 ，i = l ，p ；c t ( z ) = 0 ，i = p + 1 ，p + g ；z r n )( 1 3 ) 则： 1 ) 若问题有局部最优解矿，则矿是问题的全局最优解； 2 ) 问题的全局最优解组成的集合是凸集； 3 ) 若问题有局部最优解x ，f ( x ) 是d 上的严格凸函数，则x 是问题的唯 一全局最优解。 定义3 ( 约束规格) 考虑一般约束问题( 1 2 ) 的可行域： d = z l c ( z ) 0 ，i = l ，p ；q ( z ) = 0 ，i = p + 1 ，p + q ；z 矽)( 1 4 ) 其中p 个约束函数都是可微函数。引进下列两种约束的限制性条件： 1 ) 线性条件：p 个约束函数c 1 ( z ) ，勺( z ) 都是线性函数。 9 模糊支持向量机 2 ) 线性无关条件：设虿是( 1 2 ) 式的一个可行解，v q ( - ) ，i = p + 1 ，p + q ，v 勺( z ) ，歹= 1 ，p 线性无关。 定理5 ( 凸约束问题解的必要条件) 考虑凸约束问题( 1 2 ) ，其中f ：舻_ 冗 和c ( z ) ：舻_ r ( i = 1 ，p ) 都是可微凸函数，且定义3 中的某一个约 束规格成立，若孟是该问题的解，则存在着石= ( 西1 ，- p ) r p ，- z = ( 耻1 ，- p 峋) 即，使得k k t 条件成立，即 pp+口 v z l ( e ，西，劢= v ，( _ ) + 瓦v q ( _ ) + 瓦v c ( 虿) = 0 i = 1 i = p + l 龟( 虿) 0 ，i = 1 ，p c ( _ ) = 0 ，i = p + 1 ，p + q( 1 5 ) 瓦0 ，i = 1 ，p 砚q ( 虿) = 0 ，i = 1 ，p 定理6 ( 凸约束问题解的充分条件) 考虑凸约束问题( 1 2 ) ，其中，：舻_ r 和c i ( z ) ：舻_ r ( i = 1 ，p ) 都是可微凸函数，若虿舻满足k k t 条件， 即存在着西= ( 瓦l ，瓦) r r , ，- z = ( 耻l ，耻。) r q ，使得 pp + o v l ( 虿，瓦，劢= v ，( - ) + 瓦v 龟( - ) + 瓦v c i ( 虿) = 0 i = 1 i = p + l q ( - ) 0 ，i = l ，p c ( 虿) = 0 ，i = p + 1 ，p + q( 1 6 ) 瓦0 ，i = 1 ，p 砚c ( 虿) = 0 ，i = 1 ，p 则虿是问题( 1 2 ) 的解。 2 5 w o l f e 对偶 定义4 ( w o l f e 对偶) 称问题 m a x l ( z ，q ，p ) q ，p ，z 1 0 模糊支持向量机 s t v 霉l ( x ，口，p ) = 0 q 0 为凸最优化i ；1 题( 1 2 ) 的w o l f e 对偶。 其中l ( x ，口) 为拉格朗日函数，即 ( 1 7 ) 二p ，a ) = 厂( z ) + 啦q ( z ) + 展q ( z ) ( 1 8 ) i = 1 i = p + l 定理7 ( 凸约束问题的强对偶定理) 考虑凸约束问题( 1 2 ) ，其中f ：舻_ r 和q ) ：形一r ( i = 1 ，p ) 都是可微凸函数，q ) ，i = p + 1 ，p + q 都是 线性函数。且定义3 中的某一个约束规格成立，则 ( 1 ) 若原始问题( 1 2 ) 有解，则它的对偶问题也有解。 ( 2 ) 若原始问题( 1 2 ) 和对偶问题分别有可行解虿和( 石，劢，则这两个可行解 分别为原始问题和对偶问题的最优解的充要条件是：它们相应的原始问题和对 偶问题的目标函数值相等。 定理8 ( 凸约束问题的骱f ，e 对偶定理) 考虑凸约束问题( 1 2 ) ，其中 f ：研_ r 和c ( z ) ：舒_ r ( i = 1 ，p ) 都是可微凸函数，c ( z ) ， = p + 1 ，p + q 都是线性函数。且定义3 中的某一个约束规格成立，则 ( 1 ) 若原始问题( 1 2 ) 有解，则它的w o l f e 对偶问题也有解。 ( 2 ) 若原始问题( 1 2 ) 和w o l f e 对偶问题分别有可行解虿和( _ ，劢，则这两 个可行解分别为原始问题和对偶问题的最优解的充要条件是：它们相应的原始 问题和对偶问题的目标函数值相等。 模糊支持向量机 3 支持向量机理论 支持向量机( s u p p o r tv e c t o rm a c h i n e s ，s v m ) 的主要内容是在1 9 9 2 1 9 9 5 年间才逐步发展和完成的，作为统计理论中最年轻的一部分，它充分体 现了统计学习理论从理论思想向方法应用的过渡。s y m 是一种基于结构风险 最小化的分类器，通过解二次规则问题，寻找将数据分为两类的最佳超平面。 它的核心内容是：在输入空间中线性可分的情况下，在训练样本中找出构造最 优分类超平面的支持向量机，在数学上归结为一个求解具有不等式约束条件的 二次规则问题；在输入空间中非线性可分的情况下，采用一个适当的非线性变 换，将输入样本映射到高维特征空间，使其在高维空间中线性可分。 定义5 ( 分类问题) 根据给定训练集t = 【( z 1 ，y 1 ) ，( z 2 ，抛) ，( 却，饥) ) ( x y ) ，其中鼢x = 舻，轨y = 一1 ，1 ) ，i = 1 ，z ，寻找x = 册上的 一个实值函数g c x ) ，以便使用决策函数厂( z ) = 8 卯( 夕( z ) ) 推断任意模式z 相对应 的y 值。 3 1 线性可分情况 s v m 是从线性可分情况下的最优分类面发展而来的，其基本思想可用下 图3 1 二维空间中两类分类情况说明。 风 囤3 1 最忧超平面 2 和l 其中，实心点代表“+ ”类样本，空心点代表“一”类样本，日为分类 线，日1 和飓分别为各类中离分类线最近的样本且平行于分类线的直线，它们 1 2 模糊支持向量机 之间的距离叫做分类间隔( m a r g i n ) 。所谓最优分类线就是要求不但能将两类正 确分开( 训练错误率为0 ) ，而且分类间隔最大。分类线方程为h ：加zq - b = 0 ， 对它进行归一化，使得对线性可分样本集t = ( z 1 ，y 1 ) ，( x 2 ，耽) ，( 却，饥) ) ( x y ) ，其中z x = 冗n ，欢y = - 1 ，1 ) ，t = 1 ，j ，满足 即 w 翰q - b 1 对于y = - b l t t x i - bbs - 1 对于y i = 一1 ( 1 9 ) 犰【( 叫眈) - t - 6 】1 ，z = 1 ，z 此时分类间隔等于2 l l w l l ，使间隔最大等价于使i i 埘| 1 2 最小，满足表达式( 1 9 ) 且使得i i 叫1 1 2 最小的分类面为最优分类面，研和岛上的训练样本点称为支持 向量。 在类别为+ l 和一1 的样本点之间产生最大分类间隔，这时对应于如下最优 化问题： 曲圣( 叫) 2 毋割刎22 吉主( 叫叫) ( 2 0 ) 其约束条件为： 玑【( 彬x i ) q - 6 】1 ，i = 1 ，z ( 2 1 ) 式( 2 0 ) 和( 2 1 ) 是描述分离数据样本的支持向量机准则的常用方式，其本质是一 个求解不等式约束条件的二次优化问题。 为了求解二次优化问题，我们采用l a g r a n g e 优化方法。为此，必须找到 l a g r a n g e 函数 l ( 叫，6 ，q ) ：吾( 叫叫) 一壹啦( w x i ) + 6 】一1 ) 的鞍点。式中o l e 0 为l a g r a n g e 乘子。 函数( 2 2 ) 式中的最小值必须满足条件 型o ：伽一壹姚铲ow勺”一。 下o l ( w , b , a ) = 老躺= o劭 ”一 。 ( 2 2 ) 模糊支持向量机 由此得到 l = 蚴戤 i = 1 l a i y i = 0 i - - - 1 将式( 2 3 ) 代入式( 2 2 ) 并考虑式( 2 4 ) ，得到 q ( q ) = 啦一吉叱a 歹y t y j ( x i 巧) 1 f i - - 1 i , j = l 这里，将符号从l ( w ，b ，q ) 改成q ( 口) ，以反映出最后的转换。 q ( q ) 的表达式( 2 5 ) 称为l a g r a n g e 对偶目标函数，其约束条件为： 划： ( 2 3 ) ( 2 4 ) ( 2 5 ) l e a i y i = 0( 2 6 ) i - - - - 1 q 0 ，i = 1 ，f( 2 7 ) 把以上约束最优化问题的目标函数转换成求极小，即得原问题的对偶规 赠n 三妻骞q t 玑协c 甄巧，一妾啦 ( 2 8 ) q t 0 ，i = 1 ，l 它的最优解口；只有一部分( 通常是一少部分) 不为零，对应的样本就是支持向 量。计算最优权值向量 w + = a ；y i x i i = 1 和最优偏置 从而得到最优分类函数为： 1 4 0= 玑 口 ；汹 s d 0 时，称它为非齐次多项式核函数。当c = 0 时，即得到：k ( x ，z ) = ( z ，z ) d ，这 类核函数称为齐次多项式核函数。 3 s i g m o i d 核函数：k ( z ，z 7 ) = t a n h ( k ( x ，z ) + 钉) ，其中k 0 ， 0 。 支持向量机采用核函数k ( x ，x ) 代替高维空间中的内积运算( ( z ) ，( z ，) ) ，这样就可避免高维空间中的复杂运算。另外，考虑到可能存在一些样本不能 被分离超平面正确分类，采用松弛变量解决这个问题，于是优化问题变为： 1 l m i n 毒f j 叫j 1 2 + c 毫 ( 3 0 ) 一 t = 1 1 5 模糊支持向量机 约束为： y , ( 1 w ，砂( 戤) ) + b ) 1 6 ，i = 1 ，z & 0 ，i = 1 ，z 其中c 为一正参数，在s v m 的复杂性和不可分数据之间寻求折衷。当c 很大时，对违反约束条件( 2 1 ) 的数据加大惩罚以减小分类间隔。反之，则忽视 一部分容易错分的样本，以增大分类间隔。 引入拉格朗日函数，根据k k t 条件将优化问题( 3 0 ) 变成其对偶形式： l 1 l m a x 啦一吉a i a j y i y j k ( x i ，巧) ( 3 1 ) i - - 1 。i , j = l 约束条件为： ( 3 2 ) 0 啦g i = 1 ，z 根据任一满足条件0 0 是惩罚参数。 为了求解二次优化问题，我们采用l a g r a n g e 优化方法，构造l a g r a n g e 函 数 ， lll l ( 叫，6 ，q ，p ) = 吉| i 伽| 1 2 + c 心白一( 蚴( ( 叫巧) + 6 ) 一1 + 白) 一岛白( 4 5 ) 一 j = lj = lj = l 其中，o ，岛o ，歹= 1 ，z 。 根据w o l f e 对偶定义，利用l a g r a n g e 函数对w ，b ，白求极小，即： 塑卿：tt，一壹协：0uw ( 4 6 ) = 一一w 一u f f 山j 一 士u ， o 一。 堂等业：一壹协：0 ( 4 7 ) 劭钾1 即 、v 皇生鱼生攀：心c 一哟一岛：0 ( 4 8 ) 一= 儿二 一f y 2 一f 】= i q _ 8 乇j r j一j 、。 将式( 4 6 ) ，( 4 7 ) ，( 4 8 ) 代入到式( 4 5 ) ，并化为二次规化的对偶形式： 约束条件为： 1 1l m a x 一吉啦a j y i y j k ( x t 巧) j = l 。d = lj = l ( 4 9 ) ( 5 0 ) 0 心g j = 1 ，z( 5 1 ) 求解这个二次规划问题式( 4 9 ) 可得其最优解矿，则模糊支持向量机最优判别函 数为： f ( x ) = 8 9