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

摘要 内容摘要：支持向量机( s u p p o r tv e c t o rm 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 ) ，根据不同输入样本对分类的贡献不同，赋 予不同的隶属度，将噪声或野点与有效样本区分开 针对两类分类问题中样本点数量多，类别模糊且有孤立野点的情 况，本文提出了去边缘模糊支持向量机该方法用一类分类思想，预先 去掉那些可能不是支持向量的点，并引入了模糊隶属度计算公式，使其 适合模糊分类的性能特点本文首先对支持向量机的构造原理和基础 理论进行分析和研究。其次，对模糊支持向量机进行论述，并在此基础 上提出一种基于一类分类算法的去边缘模糊支持向量机最后，从理 论和实证分析两个方面将该方法与一般的模糊支持向量机进行了对 比分析实验结果表明：该方法不但大大减少y i i l l 练点数目，从而减少 了内存和计算量，还提高y i ) j l 练速度和分类准确率 关键词：统计学习理论；模糊支持向量机；分类；隶属度；去边缘方法 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 yi 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 na 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 ti 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 r ea 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 n s u r 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 t v e c t o rm 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 sg 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 e 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 e n o i s e so ro u t l i e r sa n dt h ev a l i ds a m p l e s an e wf u z z yv e c t o rm a c h i n eo fd i s m i s s i n gm a r g i ni sp r o p o s e d a i m i n ga tt h eo u t l i n e r sa n dn o i s e sa p p e a r i n gi nt h el a r g eq u a n t i t y s a m p l e sw i t hf u z z ym e m b e r s h i p t h en e wa l g o r i t h mh a sw e e d e do u t s o m et r a i n i n gs a m p l e sw h i c hc a n tb es u p p o r tv e c t o r sa n da d o p t sa l l 模糊支持向量机 f u z z ym e m b e rf u n c t i o n 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 ct h e o r y o 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 ，m e t h o d s o fe x i s t i n gm e m b e r s h i pa r ed i s c o u r s e d a tl a s t ，e x p e r i m e n t a lr e s u l t s s h o wt h a tt h en u m b e ro ft r a i n i n gs a m p l e si sr e d u c e d ，w h i c hm e a n st h a t t h ec o n s u m p t i o no fc o m p u t e rm e m o r yi sd e c r e a s e da n dt h ea m o u n t o fc o m p u t a t i o ni sr e d u c e d ，b u tt r a i n i n gs p e e di si n c r e a s e da n dm o r e a c c u r a t e k e yw o r d s ：s t a t i s t i c a ll e a r n i n g c h i n e s ；c l a s s i f i c a t i o n ；m e m b e r s h i p ； t h e o r y ；f u z z ys u p p o r tv e c t o rm a - t h em e t h o do fd i s m i s s i n gm a r g i n i n 学位论文独创性声明 本人承诺：所呈交的学位论文是本人在导师指导下所取得的研究成果。论文中除特 别加以标注和致谢的地方外，不包含他人和其他机构已经撰写或发表过的研究成果，其 他同志的研究成果对本人的启示和所提供的帮助，均已在论文中做了明确的声明并表示 谢意。 学位论文作者签名： 圜肇 学位论文版权的使用授权书 本学位论文作者完全了解辽宁师范大学有关保留、使用学位论文的规定，及学校有 权保留并向国家有关部门或机构送交复印件或磁盘，允许论文被查阅和借阅。本文授权 辽宁师范大学，可以将学位论文的全部或部分内容编入有关数据库并进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文，并且本人电子文档的内容和纸质 论文的内容相一致。 保密的学位论文在解密后使用本授权书。 学位论文作者签名： 整 指导教师签名： 签名日期： 0 1 年s 具；日 模糊支持向量机 1引言 模糊支持向量机 1 1研究的目的和意义 支持向量机( s v m ) 【1 】是2 0 世纪9 0 年代中期l 扫v a p n i k 2 等人提出的一种新的 机器学习算法，它是以统计学习理论( 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 ) 为基础 的，这使得支持向量机有很强的理论基础和泛化能力。该方法在很多情况下可 以克服“维数灾难等传统困难，现已成为机器学习的热点，并在很多领域得 到成功应用，如模式识别【3 、图像分类【4 】、预测【5 1 等方面，具有良好的应用价 值和发展前景 统计学习理论 6 是建立在结构风险最小化原则基础上的，它是专门针对小 样本情况下的机器学习问题而建立的一套理论体系其核心思想是对于一个给定 的具有有限数量训练样本的学习任务，如何在准确性和机器容量进行折中，以 得到最佳的推广性能此理论为机器学习问题建立了一个良好的理论框架，较好 地解决了小样本、非线性和局部极小点等实际问题 支持向量机方法是建立在v c 维( v cd i m e n s i o n ) 和结构风险最小化原则 7 】 ( s t r u c t u r a lr i s km i n i m i z a t i o n ；s r m ) 基础上的。设计支持向量机的目的是为了 处理模式识别分类问题，即首先在训练集中寻找支持向量，然后在其上构造决 策函数，使其具有良好的分类性能 但是，支持向量机作为一种尚未成熟的技术，目前存在许多局限客观世界 存在大量的模糊信息，如果支持向量机的训练集中含有噪声或野点时，这些含 有“异常 信息的样本在特征空间中常常位于分类面附近，导致获得的分类面 不是真的最优分类面，也就是说s v m 对于噪声或野点是非常敏感的针对这种 情况，台湾学者l i n 8 ，9 1 等提出了模糊支持向量机，根据不同输入样本对分类的 贡献不同，赋予不同的隶属度，从而削弱噪声或野点对分类的影响 本文正是在上述背景下展开学习和工作的，根据文献【1 0 】提出一种基于类中 心思想的支持向量机，结合一类分类思想 1 1 和f s v m 1 2 ，1 3 ，1 4 】思想，对模糊分类 问题提出了基于一类分类思想的去边缘模糊支持向量机一方面去边缘剔除了部 分非支持向量，使对应优化问题的维数( i ) i i 练集中样本点个数) 减小，从而减小了内 存和计算量，提高了训练速度；另一方面，引入适当的模糊隶属度函数，模糊隶属度 随着样本点远离中心点而逐渐减小，提取训练集的有用信息，使之适合模糊分类 的特点，减弱了孤立点和噪音点对分类的不利影响，同时通过选择合适的核函数得 到合适的分类面的形状 】 模糊支持向量机 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 a l l ，1 一v r ) 其基本思想是把某 一种类别的样本当作一个类别，剩余其它类别的样本当作另一个类别，这样就 变成了一个两类分类问题这种分类方案的缺点是训练样本数目大，训练困难 ( 2 ) 一对一( o n e a g a i n s t o n e ，1 一v 一1 ) 其基本思想是在多类别中，任意抽 取两类两两配对，转化成多个两类问题进行训练学习识别时，对所构成的多个 分类进行综合判断，一般可采用投票方式来完成多类识别这种分类方案存在一 个明显的缺点，就是子分类器过多，测试时需要对每两类都进行比较，导致测 试速度慢 ( 3 ) s v m 决策树( d e c i s i o nt r e em e t h o d ；d t m ) 它通常和二叉决策树 1 5 1 结合 起来，构成多类别的识别器这种方法的缺点是如果在某个节点上发生了分类 错误，将会把错误延续下去，该节点后续下一级节点上的分类就失去了意义。 由于s v m 在构造分类过程中存在不可分区域，对于分类问题存在一定的局限 性，模糊支持向量机( f s v 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 g h u a n g 与y i h u n gl i u 1 2 提出的这一种方法较为常用其出发点是：数据中各个 样本点对分类效果的作用是不同的，根据不同输入样本对分类的贡献不同，赋 予不同的隶属度，从而削弱噪声或野点对分类的影响 本文提出了去边缘模糊支持向量机，该方法用一类分类思想，预先去掉那 些可能不是支持向量的点，并引入了模糊隶属度计算公式，使其适合模糊分类 的性能特点该方法不但大大减少了训练点数目，从而减少了内存和计算量，提高 了训练速度和分类准确率 1 3 论文结构 第一章简要概述了支持向量机的原理，介绍了其发展及现状，指出支持向 量机目前存在的不足，本文正是在这种研究背景下阐述模糊支持向量机并指出 2 模糊支持向量机 本文所做的主要工作 第二章从支持向量机的机器学习、学习过程一致性的条件及最优化理论等 定义和定理出发，介绍了统计学习理论，为后面知识的学习奠定基础 第三章从支持向量机分类角度着手，就其分类的三种情况详细介绍了支持 向量机理论 第四章提出去边缘模糊支持向量机，从理论和实证分析两个方面将该方法与 一般的模糊支持向量机进行对比分析，从其理论以及通过标准数据实验来说明此 种方法的可行性 第五章是对全文的总结与展望 3 模糊支持向量机 2 统计学习理论 2 1机器学习的基本知识 人工智能专家s i m o n 曾经说过：“一个系统能够通过执行某种过程而改进它 的性能，这就是学习”人们把从过去的数据和知识中学习并获取规律的能力称 为“学习能力”利用获得的规律不仅可以解释已知现象，而且能够对未知现象 做出正确的预测和判断，这种能力称为“泛化能力”机器学习是现代人工智能 技术的一个重要研究内容，主要是从训练数据( 样本) 出发寻找规律，利用这些 规律对未知数据或者无法观测的数据进行预测，使其具有良好的泛化能力机 器学习按其实现方法大致分为三种：经典的参数统计估计方法、人工神经网络 和统计学习理论但前两种方法存在需要欲先已知样本分布或过拟合等缺点， 而v a p n i k 等人提出的以统计学习理论为基础的支持向量机，可以克服这些缺 点，开始受到越来越广泛的重视 2 2 机器学习问题表示 机器学习的目的是根据给定的训练样本求对某系统输入输出之间依赖关 系的估计，使它能够对未知输出做出尽可能准确的预测一般可以表示为：变 量y 与x 之间存在一定的未知依赖关系，即存在一个未知的联合概率f ( x ，可) ，机器 学习就是根据n 个独立同分布观测样本： ( x l ，u 1 ) ，( 5 2 ，y 2 ) ，( x n ，y n ) x i r n 在一组函数 ，( z ，训) ) 中求一个最优的函数y ( x ，w o ) 依赖关系进行估计，使预测期 望风险 ， r ( w ) = l ( y ，( z ，w ) ) d f ( x ，y ) ( 1 ) t ， 最小，其中 厂( z ，叫) ) 称作预测函数集，w 为函数的广义参数， 厂( z ，叫) ) 可以表 示任何函数集，l ( y ，厂( z ，西) ) 为由于用，( z ，训) 对进行预测而造成的损失，不同类 型的学习问题有不同形式的损失函数因此，机器学习问题也可以表示为，从 一组独立同分布的观测样本出发，通过最小化风险泛函冗( 叫) ，确定学习机器的广 义参数w 的过程 2 。3 学习过程一致性的条件 学习过程的一致性是统计学习理论的基础，也是与传统渐近统计学的基本 联系所在，只有满足学习过程一致性条件，才能保证在学习样本无穷大时，经 4 模糊支持向量机 验风险最小化原则下得到的最优结果趋近于使期望风险最小的最优结果经验风 险定义为： 见唧( 叫) - - i 。el ( y i ，( 观，叫) ) ( 2 ) 设使经验风险( 2 ) 式最小化的风险值为冗。唧( 蚴) ，记r ( 蚴) 为在l ( y ，( z ，硼o ) ) 下( 2 ) 式 所取得的真实风险值( 期望风险值) 当下面的两个序列依概率收敛于同一个极 限，即： r ( 蛐) 二i n f r ( w ) 见m p ( 叫o ) 三i n fr ( w ) 礼一。 则称这个经验风险最小化过程是一致的，经验风险和期望风险的关系如图2 1 所 示 图2 1 经验风险和期望风险关系 下一定理给出了经验风险最小化成立的充要条件定理l ( 学习理论的关键性 定理) 对于有界的损失函数，经验风险最小化学习一致的充分必要条件是经验 风险在如下意义上一致地收敛于真实风险： l i m p s u p ( r ( w ) 一r e m p ( w ) ) 胡= o ，v 0 ( 3 ) 一 叫 其中，p 表示概率定理将学习一致性的问题转化成( 3 ) 式中的一致性收敛问 题同时依赖于预测函数集和样本的概率分布，与( 3 ) 式中的单边一致性收敛相对 应的有双边一致性收敛，即： l i mp s u pl r ( 叫) 一亿御( 叫) j e j = 0 ，比 0 ( 4 ) ￥w 学习过程中，经验风险和期望风险都是预测函数的泛函因此，可以通过求使 经验风险最小化的函数来逼近能使期望风险最小化的函数但是学习理论的关键 5 模糊支持向量机 性定理给出了经验风险最小化原则成立的充分必要条件，并没有给出什么样的学 习方法能够满足这些条件因此，统计学习理论定义了一系列的指标来衡量函数集 的学习性能，最重要的一个指标是v c 维( v a p n i kc h e r v o n e n k i sd i m e n s i o n ) 2 3 1v c 维 v c 维作为统计学习理论中的一个核心概念，是对函数集学习性能的最好描 述v c 维反映了函数集的学习能力，v c 维越大则学习机越复杂 设有一个指示函数集f ( x ，礼) 和一组几个训练样本的样本集z n = 乞= ( 苁，y i ) ，i = 1 ，札，考虑函数集的分散性，看函数集中的函数能对这组样 本实现多少种不同的分类，记这个数目为n ( z 扎) ： 定义1 ( 随机熵) 定义指示函数集对某个样本集能实现的不同分类组合数目的 对数为函数集在这个样本集上的随机熵，记作日( ) = i n ( ) 定义2 ( 生长函数) 函数集的生长函数定义为它是在所有可能的样本集上的最 大随机熵，即g ( ) = m a x i nn ( z 亿) 定理2 函数集学习过程一致收敛的充分必要条件是对任意形式的样本分 布，都有 1 i m 盟：0( 5 ) n - - * o 佗 且这时学习过程的收敛速度一定是快的定理3 任何生长函数，它或者满足 等式 c ( i t ) = 几i n2( 6 ) 或者受限不等式 c ( i t ) h l n ( i + 1 ) ，钆 h ( 7 ) 使得当礼= h ，有g ( n ) = h i n 2 ，g ( n + 1 ) ( h + 1 ) l n 2 生长函数的这种性质，如 图2 2 所示 秘 图2 2 生长函数 6 模糊支持向量机 因此，函数的v c 维可以定义为对于一个指示函数集，若其生长函数是线性 的，则其v c 维是无穷大；若其生长函数是以参数为h 的对数函数为上界，则 其v c 维有限且等于h 2 3 2 推广性的界 统计学习理论系统地研究了对于各种类型的函数集，经验风险和实际风险 之间的关系，即推广性的界【1 3 】关于两类分类问题的结论是：对指示函数集中 的所有函数( 包括经验风险最小的函数) ，经验风险r e 唧( 叫) 和实际风险r ( w ) 以至 少1 一卵的概率满足如下关系： r ( 叫) r e m p ( 叫) - i - l l h ( 1 n ( 2 n h ) + 1 ) - l n ( r # 4 ) 1 ( 8 ) 或简写成： r ( w ) r e 仇p ( 叫) - i - 圣( n )( 9 ) 其中，危是函数集的v c 维，n 是样本数，叩是满足0 1 7 1 的参数西( 允n ) 称作置 信范围( c o n f i d e n c ei n t e r v a l ) ，置信范围不但受置信水平1 7 7 的影响，而且是函 数集的v c 维和训练样本数目的函数，并随着它们比值的增加而单调减小( 因为 这个界限反映了根据经验风险最小化原则得到的推广能力，所以称它为推广性 的界) 它表明在有限样本训练下，学习机v c 维越高，则置信范围越大，导致真 实风险与经验风险之间可能的差别越大，这就是出现过学习现象的原因 2 3 3结构风险最小化原则 我们已经发现，经验风险最小化原则在样本数目有限时是不合理的，因为 我们需要同时最小化经验风险和置信区间经验风险依赖于厂的选择，而置信区 间则是函数族f = _ f ，( z ，伽) ，w q ) 的v c 维h 的增函数简单的说，当集合f l l 较 大时，可以选择适当的厂，使得r e m p ( w ) 比较小，而此时f 的v c 维比较大，也会 使置信区间比较大反之，当缩小集合f 时，f 的v c 维会降低，而r e 仇p ( 叫) 有可 能增大，所以两者有互相矛盾的倾向为了解决这一问题，v a p n i k 等人提出了结 构风险最小化原则结构风险最小化原理如图2 3 如示 、 模糊支持向量机 函数察子集：墨c 5 2 匕b y c 缝：| 1 l 兰琏s 五， 圉2 3 结构风险最小化原则 其基本思想是先把函数集f = 1 厂( z ，伽) ，w q ) 分配为一系列嵌套的函数子集结 构 8 1c8 2c c8 kc c8 ( 1 0 ) 每个函数子集的置信范围按从小到大的顺序排列，在v c 维上也满足这种 对应的大小关系： 九1 九2 允岛 ( 1 1 ) 对应于一组嵌套的函数子集，每个子集8 。内部的置信范围是相同的，在每 一个子集内部寻找最小的经验风险选择最小经验风险和置信范围之和最小的子 集，就可以达到使期望风险最小的目的结构风险最小化原则实际上是在训练样 本逼近精度和学习模型复杂度之间折衷 1 5 】 2 4 最优化理论 支持向量机涉及两个凸规划问题原始问题和对偶问题，并且由这两个问题 之间的关系建立算法因此优化理论也是支持向量机的重要理论基础k k t 条件 8 模糊支持向量机 和w o l f e 对偶是最优化理论 1 6 n 个核心概念考虑凸约束问题： m i n y ( x ) s t c i ( x ) 0 ，i = 1 ，p( 1 2 ) q ( z ) = 0 ，i = p + 1 ，p + q ，z r n 其中目标函数厂( z ) 和约束函数q ( z ) i = 1 ，p 都是凸函数，而c i ( x ) = 0 ，i = p + 1 ，p + g 都是线性函数。 定a 4 ( h 约束问题的解) 考虑凸约束问题( 1 2 ) ，设d 是问题的可行域： d = zlc i 0 ，i = 1 ，p ；c i ( x ) = 0 ，i = p + 1 ，p + q ，x ) ( 1 3 ) 则： 1 ) 若问题有局部最优解x + ，则z + 是问题的全局最优解； 2 ) 问题的全局最优解组成的集合是凸集； 3 ) 若问题有局部最优解x ，( z ) 是d j 2 的严格凸函数，则z + 是问题的唯一全 局最优解 定义3 ( 约束规格) 考虑一般约束问题( 1 2 ) 的可行域： d = zc i 0 ，i = 1 ，p ；q ( z ) = 0 ，i = p + 1 ，p + q ，z r 一) ( 1 4 ) 其中p 个约束函数都是可微函数引进下列两种约束的限制性条件： 1 ) 线性条件：p 个约束函数c 1 ( z ) ，勺( z ) 都是线性函数 2 ) 线性无关条件：设牙是( 1 2 ) 式的一个可行解，v 色( 牙) ，i = p + 1 ，p + q ，v 勺( 牙) ，j = 1 ，p 线性无关 定理5 ( 凸约束问题解的必要条件) 考虑凸约束问题( 1 2 ) ，其中f ：r n _ r 和c i ( x ) ：础一r ( i = 1 ，p ) 都是可微凸函数，且定义3 中的某一个约 束规格成立，若牙是该问题的解，则存在着a = ( a 1 ，a 2 ，嘞) r p ，p = ( 席+ 1 ，犀+ 2 ，犀+ q ) r q ，使t 寻k k t 条件成空，即。 pp + 口 v ( 牙，a ，) = v ，( 牙) + a l v c t ( 2 ) + e 屈v c i ( 牙) = 0 i = l i = p + l q ( 牙) s0 ，i = 1 ，p 岛( 牙) _ 0 ，i ：p + 1 。，p + g ( 1 5 ) a t 0 ，i = 1 ，p 哦劬( 牙) = 0 ，i = 1 ，p 定理6 ( 凸约束问题解的充分条件) 考虑凸约束问题( 1 2 ) ，其中，：r “_ r 和q ( z ) ：r 札一r ( i = 1 ，p ) 都是可微凸函数，若牙r 札满足k k t 条 9 模糊支持向量机 件，即存在a = ( a 1 ，丘2 ，哪) r p ，矽= ( 犀+ 1 ，历p - b 2 ，犀+ g ) r q 使得 pp + q v z l ( 牙，a ，p ) = v ，( 孟) + a t v q ( 2 ) 十p t v q ( 牙) = 0 i = 1 i = p + l q ( 牙) 0 ，i = 1 ，p q ( 面) = 0 ，i = p + 1 ，p + q 觑0 ，i = 1 ，p 函色( 牙) = 0 ，i = 1 ，p 则牙是问题( 1 2 ) 的解 2 5w o l f e 对偶 定义4 ( w o l f e 对偶) 称问题 ( 1 6 ) m a x l ( x ，q ，p ) a ，z s t v z l ( x ，q ，p ) = 0 ( 1 7 ) q 0 为凸最优化问题( 1 2 ) 的w o l f e 对偶 其中l ( z ，q ) 为拉格朗日函数，即 l ( x ，) = 厂( z ) + q t q ( z ) + 屈q ( z ) ( 1 8 ) - - - - 1 i = p + l 定理7 ( 凸约束问题的强对偶定理) 考虑凸约束问题( 1 2 ) ，其中f ：r n r 和q ( z ) ： 础_ r ( i = 1 ，p ) 都是可微凸函数，q ( z ) ，i = p + 1 ，p + 口都是线性函数且 定义3 中的某一个约束规格成立，则 ( 1 ) 若原始问题( 1 2 ) 有解，则它的对偶问题也有解 ( 2 ) 若原始问题( 1 2 ) 和对偶问题分别有可行解牙和( 画，p ) ，则这两个可行解分 别为原始问题和对偶问题的最优解的充要条件是：它们相应的原始问题和对偶 问题的目标函数值相等 定理8 ( 凸约束问题的w o l f e 对偶定理) 考虑凸约束问题( 1 2 ) ，其中，：r n _ r 和龟( z ) ：r n _ r ( i = 1 ，p ) 都是可微凸函数，q ( z ) ，i = p + 1 ，p + 口都是 线性函数且定义3 中的某一个约束规格成立，则 ( 1 ) 若原始问题( 1 2 ) 有解，则它的w o l f 色对偶问题也有解 ( 2 ) 若原始问题( 1 2 ) 和w b l f e 对偶问题分别有可行解牙和( a ，声) ，则这两个可行 解分别为原始问题和对偶问题的最优解的充要条件是：它们相应的原始问题和 对偶问题的目标函数值相等 1 0 模糊支持向量机 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 v m 是一种基于结构风险最小化的分 类器，通过解二次规则问题，寻找将数据分为两类的最佳超平面它的核心内 容是：在输入空间中线性可分的情况下，在训练样本中找出构造最优分类超平 面的支持向量机，在数学上归结为一个求解具有不等式约束条件的二次规则问 题；在输入空间中非线性可分的情况下，采用一个适当的非线性变换，将输入 样本映射到高维特征空间，使其在高维空间中线性可分 定义5 ( 分类问题) 根据给定训练集t = _ ( z 1 ，u 1 ) ，( x 2 ，可2 ) ，( x l ，饥) ) ( x y ) o ，其中兢x = 础，y i y = ( - - 1 ，1 ) ，i = 1 ，c ，寻找x = r 竹上的一个 实值函数9 ( z ) ，以便使用决策函数f ( x ) = s g n ( g ( x ) ) 推断任意模式x 相对应的值 3 1 线性可分情况 s v m 是从线性可分情况下的最优分类面发展而来的，其基本思想可用下 图3 1 - - - 一维空间中两类分类情况说明 2 舡l s v m 是从线性可分情况下的最优分类面发展而来的，其基本思想可用下 图3 1 - - 维空间中两类分类情况说明其中，实心点代表“+ ”类样本，空心 点代表“一 类样本，日为分类线：甄和岛分别为各类中离分类线最近的样本 且平行于分类线的直线，它们之间的距离叫做分类间隔( m a r g i n ) 所谓最优 分类线就是要求不但能将两类正确分开( 训练错误率为o ) ，而且分类间隔最 大分类线方程为h ：w x + b = 0 ，对它进行归一化，使得对线性可分样本 集t = ( z 1 ，y 1 ) ，( x 2 ，y 2 ) ，( x l ，肌) ) ( xxy ) 2 ，其中x i x = r n ，y i y = 1 1 模糊支持向量机 一1 ，1 ) ，i = 1 ，z ，满足 协z t + 6 1 ，对于阢2 + 1 ( 1 9 ) w 耽+ b 1 ，对于y i = 一1 、7 即 玑【( 训x i ) + 6 】1 ，i = 1 ，z 此时分类间隔等于2 1 1 伽| 1 使间隔最大等价于使l | 训1 2 最小，满足表达式( 1 9 ) n 使得最i i 训1 1 2 小的分类面为最优分类面，日和吼上的训练样本点称为支持向量 在类别为+ 1 和1 的样本点之间产生最大分类间隔，这时对应于如下最优化问 题： m i n 垂( 叫) = 去l l 叫l i = m i n1 ( 叫叫) 其约束条件为： ( 2 0 ) 玑 ( 叫钇) + 6 】1 ，i = 1 ，2 ( 2 1 ) 式( 2 0 ) 和( 2 1 ) 是描述分离数据样本的支持向量机准则的常用方式，其本质是一个 求解不等式约束条件的二次优化问题 为了求解二次优化问题，我们采用l a g r a n g e 优化方法为此，必须找 至u l a g r a n g e 函数 1 l l ( w ，6 ，o ) = 专w 叫) 一o f i ( 犰 ( 圳嘎) + 6 】一1 ) ( 2 2 ) 。 i = 1 的鞍点式中由0 为l a g r a n g e 乘子函数( 2 2 ) 式中的最小值必须满足条件 1 0 l ( w r , b , a ) = 铆一妻鳓铲。 型：lob 蛾：o 一= 7 ，二，y ：= i - 鲁踟“。 将式( 2 3 ) 代入式( 2 2 ) 并考虑式( 2 4 ) ，得到 q ( 。) = 啦一吉啦o r j y i y j ( x t 巧) ff 扛1 i , j = l 1 2 ( 2 3 ) ( 2 4 ) ( 2 5 ) 猡 q 玑 。涮 1 1 w 至得此由 0 = 玑 q 。：l 模糊支持向量机 这里，将符号从l ( w ，b ，o ) 改成q ( o o ，以反映出最后的转换 q ( q ) 的表达式( 2 5 ) 称为l a g r a n g e 对偶目标函数，其约束条件为： l 毗y i = 0 ( 2 6 ) 叱0 ，i = 1 ，z( 2 7 ) 把以上约束最优化问题的目标函数转换成求极小，即得原问题的对偶规划： 1 lfi 呼去a t a j y i y j ( 即) 一啦 圭a 舻0 8 o i 0 ，i = 1 ，f 它的最优解a ；只有一部分( 通常是一少部分) 不为零，对应的样本就是支持向 量计算最优权值向量 w + = o z * y i x i 和最优偏置 f b + = 协一犰q 巧) ，0 0 ，v 0 支持向量机采用核函数k ( z ，z 7 ) 代替高维空间中的内积运算( 西( z ，咖( z ，) ) ) ， 这样就可避免高维空间中的复杂运算另外，考虑到可能存在一些样本不能被分 离超平面正确分类，采用松弛变量解决这个问题，于是优化问题变为： 约束为： 司w + c 喜已 ( 3 0 ) u i ( ( w ，( 兢) ) + b ) 21 一已，i = 1 ，2 已0 ，i = 1 ，f 其中c 为一正参数，在s v m 的复杂性和不可分数据之间寻求折衷当c 很大 时，对违反约束条件( 2 1 ) 的数据加大惩罚以减小分类间隔反之，则忽视一部分 容易错分的样本，以增大分类间隔 引入拉格朗日函数，根据k k t 条件将优化问题( 3 0 ) 变成其对偶形式： 1 m a x 啦一专叱玑y j k ( x t ，巧) i = 1 。i , j = l 1 4 ( 3 1 ) ( 3 2 ) 0 l = i | 玑 z 吼 c。斟矗 q o 为件条束约 模糊支持向量机 根据任一满足条件0 q 0 是惩罚参数 为了求解二次优化问题，我们采用l a g r a n g e 优化方法，构造l a g r a n g e 函数 ， f j l l ( w ，6 ，q ，p ) = 吉i i 伽1 1 2 + c 如岛一。( 协( ( 伽) + 6 ) 一1 + 白) 一岛岛( 4 5 ) 其中，0 ，岛o ，j 三1 ，一，1 根据w o l f e ：汴j 偶定义，利用l a g r a n g e 函, 数对叫，b ，白求极小，即： 半一妾= 。 ， 1 9 呦 ；蛐 c+ 胪 彬 1 2 璺m 为件条束约 模糊支持向量机 堂掣：一壹7 协：o ( 4 7 )= 一 fr 二，二= i li4 ，- a 6 厶一 7 。 rv 里生鱼生掣：心c 一。一伤：o ( 4 8 ) 灰_ 一2 心u 一一岛2 u 【4 苎) 将式( 4 6 ) ，( 4 7 ) ，( 4 8 ) 代入到式( 4 5 ) ，并化为二次规化的对偶形式： f 1 m a x 一砉瓯珑协k ( z t 奶) j = l 。i , j = l ( 4 9 ) 约束条件为： ：协= 0 ( 5 0 ) j = l 0 o l j t t j c ，歹= 1 ，f( 5 1 ) 求解这个二次规划问题式( 4 9 ) 可得其最优解o l + ，则模糊支持向量机最优判别函 数为： f ( x ) = s g n ( w + x ) + 6 + 】，x r n( 5 2 ) 其中 zz w + = 噶协巧，b = y i 一协噶( 巧娩) ，0 q ； 0 , x i 与之相对应的样本点就称为支持向量一般情况 下有两种支持向量：一种是满足0 q + t t j c 的支持向量x t ，是被错分的样本利用一类分类算法确定 模糊支持向量机的隶属度方法与传统的支持向量机方法差别在于：前一种方法 含有隶属度肛，相同o l + 值的样本x i 在两种方法中可能属于不同类型的支持向量另 外，在支持向量机方法中，参数c 是一个自定义的惩罚因子，它控制对错分样 本惩罚的程度，用来控制样本偏差与机器推广能力之间的平衡c 越大，惩罚 越大，对错分样本的约束程度就越大，得到分类面的间隔就越小；随着c 的降 低，支持向量机忽略更多的样本，得到较大边缘间隔的分类面利用一类分类算 法确定模糊支持向量机的隶属度方法，通过不同样本对分类贡献的大小赋予不 同的隶属度肛f ，使更小隶属度p f 的样本在训练中起更小的作用 模糊支持向量机 4 2 2去边缘模糊支持向量机 1 一类分类算法 文献 2 3 】给出去边缘算法，但是没有事先进行分类。本文结合一类分类算 法，给出去边缘的模糊支持向量机算法为了确定隶属度，首先利用一类分类 算法对样本进行聚类设一个正类样本集为 兢，i 一1 ，c ) ，耽r d ，设法找一个 以a 为中心，以r 为半径的能够包含所有样本点的最小球体如果直接进行优化处 理，所得到的优化区域就是一个超球体为了使优化区域更紧致，这里采用核映 射思想，首先用一个非线性映射将样本点映射到高维特征空间，然后在高维特 征空间求解包含所有样本点的最小超球体为了允许一些数据点存在误差，可以 引入松弛变量邑来控制，同时将高维空间优化中的内积运算采用满足m e r c e r 条 件的核函数代替，即找一个核函数k ( x ，y ) 代替 ，于是优化问题 为： 2 m i n f ( r ，o ，毛) = r 2 + c 毛 ( 5 4 ) i = 1 约束为： ( 咖( 规) 一o ) ( ( z ) 一n ) 丁r 2