（计算机应用技术专业论文）模糊支持向量机算法研究.pdfVIP

延边大学工学硕士学位论文 摘要 支持向量机( s u p p o r tv c c t o r m a c h i n e s ) 是2 0 世纪9 0 年代曲v a p n i k 等人提出 的一类新型机器学习方法，它能够非常成功地处理分类和回归问题。由于支 持向量机出色的学习性能，该技术已经成为机器学习界的研究热点，并在很 多领域得到了成功的应用。但是，作为一种尚未成熟的新技术，支持向量机 目前存在着许多局限。客观世界存在大量的模糊信息，如果支持向量机的训 练集中含有噪声和模糊信息，那么支持向量机的性能将变得非常微弱甚至无 能为力。 本文针对存在模糊信息的样本时已有支持向量机的不足之处，提出了改进 的模糊支持向量机( f u z z ys u p p o n 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 s v m ) ，w h i c hw a sp r o p o s e di n1 9 9 0 sb yv h p n i k e t c ， i s0 n eo ft h es t a n d a r dt o o i sf o rm a c h i n e 王e a m i l l ga n dd a t am i n i n g nc a nd c a lw i t h d a s s i f i c a t i o np r o b l e m sa dr e g r e s s i o np r o b l e m ss u c c c s s f u l l y b e c a u s e0 fi t s e x c c l l c n tl e a m i n gp e d o 咖柚c c ，t h i st e c h n o l o g yh 硒b e e nt h eh o tt o p i c0 fm a c b i n e l e a r n i n g b u t 嬲an e wt e c h o l o g y ，j ts t i l lh a ss 伽ep r 0 m e m s t h e r ea f el o t so f f i l z z yi n f o 咖a t i o ni n t h eo b j e c t i v ew o f l d ，a n di ft h ct 汹i n g th 鹤f i l z z y i n f o 硼a t j o n ( 如z z yp a r a m e t c 墙) i ns v m ，t r a d i t i o n a 王s v mw i l lb e 啪ep o o f 锄d i n d e e d w i l lf a n 1 陆sd i s s c n a t i p r o p o s c d 距 i m p r o v e df u z z y s u p p o n v c c t o r m a c h i n e ( f s v m ) a l g o r i l h mt os o l v et h es h o n a g ew h e nt h et r a i n i n gs c th 弱f l l z z y i n f 咖a t i o ni nt h es a m p l e s f i r s t ，t h es t n l c t l l r e t h c o f ya n db 髂i ct h e o r y s t a t i s t i c a ll e a m i n gt h c o r ya r c 姐a l y s e da n dr c s e a r c h e d f u n h e 皿o r e ，t h em o d i f i e d t h ef s v ma l g o r i t h mi sp r o p o s e d i i lt h em o d e lo fm o d i f i e df s v m ，t h ei n n e r c o n s t 川c t i n gp r o c e d u r c 觚dt h ee x t e d o rs t r u c t u r co ff s v ma f cd e s 酬b e d m a t h e m a t i ca p p m a c ha n du s i n gt l l ef s v ma sd 舔s i f i e d 船s i f i c a t i o n 柚d r e c o g n j | i o nf o re x t 删：t e df c a 如r ca r ec a f r i e do u t ，f i n a l l y ，t h ee x p e r i m 明t a ld a t ao f t h i sm o d e lw i t ht h a to ft h eo t i l e rs v m sa r ec o m p a r e d t h er e s u l t so fe x p e r i i l l ts h o wt h a tt h ep r o p o s e df s 讧c a np r c f e r 曲l y f c s o l v et h ed a s s i 丘c a t i o np r o b l e mf o ft h es a m p l e sw i t hf 1 1 z z yi n f o 咖a t i o n ， c o m p a r i n gw i t hs o m eo t h c rs v m sa l g o r i t h m 也i sa 1 9 0 r i t h mh 弱e x c e l l e n c c0 f r e d u c i n gt h es a m p l es p a c cs i z e 龃dt h er e q u i r e m e n to fm e m o 踢a i l dt h es p c e do f r a i n i n ga n dc l 弱s i f 王c a t i o nj si m p r o v e d k e y w o r d sm a c h i n el e a m i n g ；s t a t i s t i c a ll e a m i n gm r y ；f l l z z ys u p p o r tv e c l o r m a c h i n e 一一 延边大学工学硕士学位论文 1 1 研究目的和意义 第1 章绪论 自2 0 世纪9 0 年代中期以来，综合统计学习理论、支持向量机算法的优 点和最优化技术，设计实现新算法成为机器学习领域的一个研究热点，并取 得了丰硕的成果。 支持向量机( s u p p o nv c c t o fm a c h i n 鹪，s v m s ) 方法是上世纪九十年代中 期v a p n i k 等人提出的一类新型的机器学习算法1 1 】，受到理论界和工程晃的广 泛关注。它以小样本的统计学习理论( s 【册为基础，具有很强的学习能力和泛 化性能，能够较好地解决小样本、高维数、非线性、局部极小等模式识别问题， 且人为设置的参数少，便于使用，己经成功地应用于模式识别、图象处理等 许多方面【2 】【3 1 。 设计支持向量机的原本意图是为了处理模式识别分类问题，即首先寻找 训练集的一个小的子集，这个子集叫支持向量集，然后在其上构造决策函数， 使它具有良好的推广能力。 尽管支持向量机有着很高的数据分类性能，作为一种尚未成熟的新技术， 对于现实世界中存在的很多数据样本中参杂的不规则和模糊信息，尤其是在 构造最优分类面时所有的支持向量样本具有相同的作用，当训练样本中含有 噪声与野值样本时，这些含有“异常”信息的样本在特征空间中常常位于分 类面附近，导致获得的分类面不是真正的最优分类面。另外，在实际应用中， 对某些重要的类需要非常高的分类精度，而对其它类分类精度的要求相对低 一些，所有这些问题，对于常规的支持向量机都无法解决。 本文便是在上述背景下展开工作的，在研究和实践过程中，将统计学习 理论和模糊理论应用于支持向量机的构造中，用来提商支持向量机对参杂模 糊信息的样本进行分类时的效率，提高支持向量机的训练和分类速度，减少 空间大小和所需内存，提高分类的效率。 1 2 研究现状 支持向量机的主要思想是基于统计学习理论( s t a t i s t i c a lk a m i n gn e 0 啦 延边大学工学硕士学位论文 s u ) 的结构风险最小化原理( s c n i c t u a l 剐s km i n i m i z a t i o ni n d u c t i y cp 豳c i p l e ) 。 支持向量机应用于分类问题，可看作是感知器的推广。在线性可分的情况下， 就是建立一个超平面使得可分的两类数据到该平面的距离最小，通常称该平 面为最优分离超平面。对于非线性问题，是通过一个非线性映射把原始数据 影射得到另一个称之为特征空间的新数据集上，使得新数据集在该特征空间 上是线性可分的，由此建立最优超平面在原始空间内是超曲面。 自1 9 9 5 年以来，在实用算法研究、设计和实现方面取得了丰硕的成果， 可归结为几个大的研究方向： 1 2 1 改进训练算法 训练算法改进的思路是把要求解的问题分成许多子问题，然后通过反复 求解子问题来求得最终的解，方法有以下几种： 1 2 1 1 块处理算法( c h u n l 【i n ga l g o r i t h m ) 1 4 1 它的思想是将样本集分成工作样本集和测试样本集，每次对工作样本集 利用二项规划求得最优解，剔除其中的非支持向量，并用训练结果对剩余样本 进行检验，将不符合训练结果( 一般是指违反汀条件) 的样本( 或其中的一 部分) 与本次结果的支持向量合并，成为一个新的工作样本集，然后重新训练， 直到获得最优结果。其依据是去掉l a f a n g e 乘子等于零的训练样本不会影 响原问题的解。块算法的一个前提是支持向量的数目比较少。然而，如果支 持向量的数目本身就比较多，那么随着训练迭代次数的增加，工作样本数也越 来越大，就会导致算法无法实施。 1 2 1 2 固定工作样本集算法( s v m q p ) 1 5 】 它使样本数目固定在足以包含所有的支持向量，且算法速度在可以容忍 的限度内。迭代过程中只是将剩余样本中部分“情况最糟的样本”与工作样 本集中的样本进行等量交换。即使支持向量的个数超过工作样本集的大小， 也不改变工作样本集的规模。需要指出的是如果集合不足以包括所有的支持 向量，该算法没有提出改变该集合的大小的策略，因此有可能得不到结果。 1 2 1 3 序贯最小化( 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 ) 算法槲以及 改进的序贯最小化算法1 7 j s m o 是固定工作样本集算法的一个极端情况，其工作样本数目为2 。需要 两个样本是因为等式线性约束的存在使得同时至少有两个l a g r a n g c 乘子发 生变化。由于只有两个变量，而且应用等式约束可以将其中一个用另一个表示 出来，所以在迭代过程中，每一步子问题的最优解都可以直接用解析的方法求 出来。这样，算法就避开了复杂的数值求解优化问题的过程；此外，算法还设计 延边大学工学硕士学位论文 了一个两层嵌套循环，分别选择进入工作样本集的样本，这种启发式策略大大 加快了算法的收敛速度。标准样本集的实验结果证明，s m 0 在速度方面表现 出良好性能。 1 2 。2 提高测试速度 从最优分类函数入手，对支持向量有关的最优解和阙值进行操作捧j l 。 减少支持向量所有求和的数目为目的改变并近似判决函数的形式，使其满足 约束条件，以此来提高速度。判决函数分别以三种方式进行改进： ( 1 ) 对判决函数在特征空间中进行拟合，得到一个近似的判决函数，使特 征向量成为特征空间中的不一定是样本点的合成向量； 对判决函数在特征空间中近似加支持向量对应的权重； ( 3 ) 对原问题重新定义，得到新的判决函数。 1 2 3 核函数的构造、改进以及相应参数的调整 核函数从理论上为训练学习机提供了一种系统特有原则的方法【1 0 】【l l 】。可 以说在任何一种含有点积的算法中，用核函数来代替点积就可以称作是核方 法。核函数的形式以及其参数的确定决定了分类器的类型和复杂程度，它显然 应该作为控制分类器性能的手段。 1 ，2 4 利用s v m 解决多分类的问题 ( 1 ) 一对多( o n ec l 懿sv e r s u sa l lo t h e r s ，o v 0 ) 【1 2 l 其基本想法是把某一种类别的样本当作一个类别，剩余其他类别的样本 当作另一个类别，这样就变成了一个两分类问题。这种分类方案的缺点是训练 样本数目大，训练困难。 ( 2 ) 一对一( o n ed a s sv e r s u sa 丑o t b e fd a s s ，o v f q 【1 3 l 其做法是在多类别中，任意抽取两类进行两两配对，转化成两类问题进行 训练学习。识别时。对所构成的多个s v m 进行综合判断，般可采用投票方式 来完成多类识别。这种分类方案存在一个明显的缺点，就是子分类器过多，测 试时需要对每两类都进行比较，导致测试速度慢。 ( 3 ) s v m 决策树( d e c i s i o nt r e em e t h o d ，d t m ) f 1 4 j 它通常和二叉决策树结合起来，构成多类别的识别器。这种方法的缺点是 如果在某个节点上发生了分类错误，将会把错误延续下去，该节点后续下一级 节点上的分类就失去了意义。 ( 4 ) m u l t i 2 a a s ss v m 【1 5 j 直接在目标函数上进行改进，建立k 分类支持向量机。由二分类支持向 量机进行推广得到满足特定约束条件的目标函数。利用l a g r a n g e 优化方法 延边大学工学硕士学位论文 同样可以把上述最优分类面问题转化为其对偶问题，得到的函数变量数为k 个。这种方法因为变量数日过多，所以只在小型问题的求解中才能使用。 1 3 研究内容和主要创新点 本论文的研究主要涉及s v m 算法的前3 个领域。首先，我们结合模糊 模式识别的方法修改算法的某些元素来得到算法的改进形式，以提高s v m 算法的性能；其次，使用改进的支持向量机来解决不同的问题，同时修改s v m 算法的参数状态便之对该问题有针对性。本课题针对支持向量机训练中需要 的参杂噪声和野值样本，用模糊k 近邻算法对样本进行预选取，对样本中存 在的噪声进行有效的识别和处理，提高支持向量机对参杂噪声和野值样本进 行训练时的效率，提高支持向量机的训练和分类速度，减少样本空间大小。 最后，根据隶属度对支持向量机进行模糊处理，进一步提高支持向量机对模 糊样本的分类效率。 本文的主要创新点在于： ( 1 ) 在对支持向量机训练样本中存在噪声和野值时对这些影响分类效果 的噪声结合模糊k 近邻算法，进行有效的剔出，经过样本预选取过程有效地 较少样本中的噪声，减少样本空间大小，提高支持向量机的训练和分类速度。 ( 2 ) 根据统计学习理论，结合模糊模式识别的原理，对支持向量机的内 部构造进行了改进，使其成为模糊支持向量机，能够有效地处理存在模糊信 息的样本，有效解决标准支持向量机算法对类似样本操作时的能力下降甚至 无能为力的情况，提高有效分类操作的效率。 1 4 内容安排 本学位论文的内容安排如下： 第一章对研究目的和意义、支持向量机的研究现状和本文主要内容进行 了简要的论述。 第二章介绍了与本文有关的相关的基础理论，包括：统计学习理论、支 持向量机理论和标准模糊支持向量机算法。 第三章分为两部分，前一部分对样本的预选取方法进行研究，提出了模 糊k 近邻算法对样本进行预选取方法。后半部分根据模糊支持向量机的构造 原理，从模糊特征表示方法入手，结合模糊隶属度的确定方法和模糊规划后 的阈值确定方法，构造了模糊支持向量机并进行了算法的描述。 第四章利用m a t i a b 对样本的预选取方法和模糊支持向量机的算法进行了 延边大学工学硕士学位论文 实验验证，并对其结果进行了分析。 最后是本文的结论，归纳了本文的工作，提出了模糊支持向量机的优缺 点，并指出了进一步努力的方向。 延边大学工学硕士学位论文 2 1 引言 第2 章相关理论和算法 本章介绍与本论文相关的理论和算法的基本思想以及其理论基础，包括 统计学习理论，支持向量机理论和标准模糊支持向量机算法。 2 2 统计学习理论 统计学习理论( s t a t i s t i c a lh 锄i n gt 1 l e o r y ，s l l ) 是由、，印n 呔等人提出的 一种小样本统计理论，着重研究在小样本情况下的统计规律及学习方法【1 6 l 。 s u l 为机器学习问题建立了一个较好的理论框架，也发展了一种通用的学习 算法【1 7 】一支持向量机。 2 2 1v c 维 v c 维是由v a p n i k 和c h e r v o n e n k i s - 提出的概念。它是统计学习理论中的一 个核心概念，是对函数集学习性能最好的描述指标。 对一个预测函数集，若存在 个样本能够被函数集中的函数按所有可能 的2 种形式分开，则称函数集合能够把| 1 1 个样本打散，函数集的v c 维就是它 能打敬的最大样本数 。也就是说，如果存在j 1 1 个样本的样本集能够被函数集 打散，而不存在 + 1 个样本的样本集能够被函数集打散，则函数集的v c 维就 是 。如果对于任意的样本数，总能找到一个样本集能够被这个函数集打散， 则函数集的v c 维就是无穷大。应当指出，存在 个样本的样本集能够被函数 集打散，不是指任意 个样本的样本集能够被函数集打散。函数集的v c 维( 而 不是其自由参数个数) 影响了学习机器的推广性能。v c 维给我们克服所谓的 “维数灾难”指出了很好的途径：以一个包含很多参数但却有较小的v c 维的函 数集为基础实现较好的推广性。但是对于一个问题，v c 维的计算不是一个容 易的问题【1 羽。 延边大学工学硕士学位论文 2 2 2 泛化能力推广性界 统计学习理论系统地研究了各种类型函数集的经验风险和实际风险之间 的关系，即推广性的界。对指示函数集中的所有函数馆l 括使经验风险最小化 函数) 经验风险扣) 和实际风险r ) 之间至少以概率1 一叩满足下列关系； 尺和) i 和) + ( 2 1 ) 或简写为； r ( 讲) 车墨。( ) + 妒( 乡乞，叩) ( 2 2 ) 其中， 是函数集的v c 维，l 是样本数，呀是满足o c 町t 1 的参数，妒( ，7 ) 称 作置信范围( c o n f i d 髓c ei n l e r v a l ) ，也有人把它叫做v c 信任cc o n f i d e c c ) ，置 信范围不但受置信水平1 一卵的影响，而且是函数集的v c 维和训练样本数目的 函数，并随着它们比值的增加而单调减少。因为这个界限反映了根据经验风 险最小化原则得到的机器学习的推广能力，所以称它为推广性的界。可以看 出，置信界限反映了真实风险和经验风险差值的上确界，它和学习机器的v c 维 及训练样本数，l 有关。因此，要想得到期望风险最小值，除了控制经验风 险最小外，还要控制函数集的置信界限，而置信界限随着函数集v c 维的增长 面增大，在有限训练样本下，学习机器的复杂性越高，v c 维越商，则置信界 限越大，也就会导致真实风险与经验风险之间可能的差别越大。在神经网络 中存在一个过学习现象，其原因首先是学习样本不充分，其次是学习机器的 复杂性过高，导致它的v c 维过大，以至于在经验风险最小的情况下，函数集 的置信界限很大，所以其推广能力仍然很差【1 9 j 。经验风险最小化原则在样本 有限时，不尽合理，般需要同时最小化经验风险和置信界限。统计学习理 论提出了一种新的策略，即把函数集构造为一个函数子集序列，使各个子集 按照v c 维的大小( 亦即的大小) 排列；在每个子集中寻找最小经验风险，在子 集间折衷考虑经验风险和置信界限，取得实际风险的最小，这种思想称为结 构风险最小化( s t m c t u r a lr i s km i n i m i z a t i o n ，s r m ) 准则1 2 0 j 。 延边大学工学硕士学位论文 2 2 3 结构风险最小化原则 设函数集s 一 q ( 毛口) ，4 a 具有一定的结构，这一结构是由一系列嵌套的 函数子集合最一 q 0 ，4 ) ，4 ) 组成，他们满足 置c 是c 。墨c ( 2 3 ) 其中结构的元素满足以下面两个性质： ( 1 ) 每个函数集合s 的v c 维瓯是有限的，因此 j l i s 吃s 鬼墨 ( 2 。4 ) ( 2 ) 结构的任何元素& 或者包含一个完全有界函数集合 o j q 0 ，4 ) s 曰，口a ( 2 - 5 ) 或者包含对一定的p ，) 对满足下列不等式的函数集合： 澄错钒护2 ( 2 - 6 ) s u p l 一s 。巩，p ，z 。o j n 文 r q g ，4 ) 卵 一 。 这种结构叫做一个容许结构。 一 函数集子集：墨c s ，c 是 v c 维： s k 主以 图2 1 有序风险最小化 f i 9 2 1o f d e r e dr i s km i n i m i z a t i o n 这种容许结构，随着子集序号栉的增加，经验风险的最小值减少，但决定 置信范围的项却增加了，如图2 1 所示。统计学习理论提出的方法就是将这两 延边大学工学硕士学位论文 者都考虑在内，通过在每个子集中寻找最小经验风险，子集间折衷考虑经验 风险和置信范围，从而取得最小的实际风险，这种思想就是结构风险最小化 原则( s t m c t u r a lr i s km i n i m i z a t i o n ，简称s r m ) ，或者称为有序风险最小化原则。 该原则定义了在对给定数据逼近的精度和逼近函数的复杂度之间的一种折 衷。 实际风险的界是经验风险与置信范围之和，随着结构元素序号的增加， 经验风险将减少，而置信范围将增加，最小的风险上界是在结构的某个适当 的元素上取得的，一般是在经验风险与置信范围的交叉点得到。 2 3 支持向量机 s v m 是统计学习理论中最年轻的内容，也是最实用的部分。其核心部分 内容是在1 9 9 2 年到1 9 9 5 年间提出的【2 1 l 【2 2 1 。 s v m 是对结构化风险最小化原则( s t n l c t l l r a lr i s km i n i m i z a t i o nh d u c t i v e p 血c i p l e ) 的近似。为了最小化期望风险的上界，s v m 在固定学习机经验风险 的条件下最小化v c 置信度。其直观的解释为从训练集中选择一组特征子集， 使得对特征子集的线性划分等价予对整个数据集的分割。 支持向量机方法根据有限的样本信息在模型的复杂性和学习能力之间寻 求最佳折衷，以期获得最好的推广能力( g c n 盱a l i z a t i o na b i l i t y ) 【2 3 l 【2 4 1 。其基础 性理论有以下几点。 2 3 1 最优分类面与广义最优分类面 设有可分的两类样本 ( 而，m ) ，瓴，) ，2 ) ，“，m ) ，善尺“，_ ， 一1 ，+ b 可用超平面 w j + 6 _ o 进行分离。参数w ，6 约束于 m i n l w x + 6 i t l 超平面约束于 ) ( w 五) + 6 】1 f 一1 ，2 ， ( 2 7 ) ( 2 - 8 ) ( 2 - 9 ) ( 2 - l o ) 延边丈学工学硕士学位论文 样本点到超平面的距离 扣帮 ( 2 1 1 ) 所谓最优分类线就是要求分类线不但能将两类正确分开，而且使分类间 隔最大，如图2 2 所示。推广到高维空间，分类线即为分类面。 在图2 2 中，实心点和空心点分别代表两类样本，h 为分类线，h l ，h 2 分 别为过两类中离分类线最近的样本且平行于分类线的直线，它们之间的距离 幽2 为 ( 2 - 1 2 ) 图2 2 最优分类超平面 f i 9 2 2o p t i m a lc l a s s i f ：i c a t i o nh y p e r p l a n e 由式( 2 _ 9 ) 和( 2 _ 1 0 ) 可知分类间隔等于彳，圹使分类间隔最大等价于使 去hh ，“2 最小。满足式( 2 1 0 ) 且分类间隔最大的分类面就叫做最优分类面h l ， h 2 上的训练样本点称为支持向量。使分类间隔最大就是对推广能力的控制， 这是s v m 的核心思想之一。设在n 维空间中，样本分布在一个半径为r 的超球 范围内，则满足条件w | i s 爿的正则超平面构成的v c 维满足： sm i n ( 矗2 】，疗) + 1 ( 2 一1 3 ) 因此使妻叫1 2 最小就是使v c 维的上界最小，从而实现结构风险最小化准则中 对函数复杂性的选择。在式( 2 1 0 ) 的约束条件下，最小化妻0 川1 2 可以写成拉格 群 m 一 骧 - l i篙n q 商 如 延边大学工学硕士学位论文 朗日泛函式： 上( w ，6 ，口) 一丢o w i l 2 一套口f y f 【 叻+ 刎一1 ( 2 1 4 ) 其中q 是拉格朗日因子。对鸩6 最小化( h ，6 ，4 ) ，由最优解满足的条件 ( 勋m s h k u l i n t u c k e “繇份得 旦掣。o = ，妻西只- o ( 2 1 5 )曲白 。 掣- o = ，w 。塞口；五) 。o ( 2 1 6 ) 删 何 采用经典拉格朗日函数的对偶将原问题转换成对偶问题 峄 ) 。峄叻工( m 6 ，4 ) 卜警 善q 一主篆酗缈一y ，“巧) ) ( 2 _ 1 7 ) 由约束于式( 2 1 5 1 和下式 口：2 0 ，i = l ，2 ，l ( 2 - 1 8 ) 求解即得西解，解中将只有一部分( 通常是少部分) 西不为零，对应的样 本就是支持向量。得到的最优分类函数是 ， ) s 印 ( w 。聋) + 6 ls 驴 蓍口 “工) + 6 。( 2 _ 1 9 ) 其中 6 一三【( x ( 1 ) ) + x ( 一1 ) ) 】 ( 2 2 0 ) 其中x ( 1 ) 表示第一类的任意一个支持向量，石( 一1 ) 表示第二类的任意一个支持 向量。 对于线性不可分的情况，可以在条件( 2 2 0 ) 中增加一个松弛变量毒z0 ，则 约束变为： 只【( w 薯) + 6 】+ 毒1( 2 2 1 ) 将三h w “2 最小改为求三w 目2 十c ( 塞毒) 最小，即折衷考虑最少错分样本和最大 类间隔，就得到广义最优分类面。其中，c o 是一个常数。它控制对错分样本 延边大学工学硕士学位论文 惩罚的程度。广义最优分类面的对偶问题与线性可分情况下几乎完全相同， 只是条件( 2 1 8 ) 变为： 0 qs c ， i - 1 ，2 ，l( 2 - 2 2 ) 2 3 2 支持向量机 上一节介绍讲述统计学习理论时涉及到了线性可分的情况，这一节重点 介绍对非线性问题的支持向量机算法。 对非线性问题，可以通过非线性变换转化为某个高维空间中的线性问题， 在变换空间求最优分类面。被映射的高维空间可能是有限维的，也可能是无 限维的【2 5 i 【冽。这种映射可以表示为 x 一垂 ) 一( 吼中l o ) ，4 2 m 2 0 ) ，口由。0 ) ) ，口。r ，西。只 ( 2 - 2 3 ) 在支持向量机中，这种映射的具体实现是通过核函数七“，) 一垂“) 垂0 ，) 来 实现的。这里用满足m e r c c r 条件的核函数七瓴，_ ) 代替线性可分情况下的内积 而_ 变换的方法，它对应某一变换空间中的内积。变换后式( 2 - 1 7 ) 变为： t 彤( 口) 。警 妻吩一三妻套q 4 ，咒y 产“_ ) 得到的最优分类函数为 ，o ) _ s 印 善4 江“。工) + 6 ( 2 2 4 ) ( 2 2 5 ) 简单地说，支持向量机就是通过用内积函数定义的非线性变换将输入空间变 换到一个高维空间，并在这个空间中求( 广义) 最优分类面【2 7 】【2 8 1 。s v m 分类函 数形式上类似于一个神经网络，输出是中间节点的线性组合，每个中间节点 对应一个支持向量，如图2 3 所示。 延边大学工学硕士学位论文 2 3 3 核函数 五屯 z 图2 3 支持向量机结构示意图 f i 萨一3d i a g r a mo fs v m s t m c t i i f e 在s v m 算法中不同的内积函数将形成不同的算法，用的比较多的主要有 有三类【2 9 l ： 一类是多项式核函数 k ( 毛玉) l 【 t ) + 耶 ( 2 2 6 ) 式( 2 2 6 ) 是q 阶多项式的核函数。 第二类是径向基函数( r b f ) k ( 石，五) - 唧( 一i 工一毛| 2 盯2 ) ( 2 2 7 ) 所得的分类器与神经网络r b f 算法的区别根本在于：每个径向基函数的中心对 应 一个支持向量，网络结构及其网络权值由算法自动确定。 第三类是s i g m o i d 核函数，即 k o ，五) 一t 趾h 以 五) + q ) ( 2 - 2 8 ) 这时的s v m 算法对应于包含了一个隐层的多层感知器，隐层结点数是由算法 自动确定的，而且算法不存在困扰神经网络的局部极小点的问题。 延边大学工学硕士学位论文 2 4 标准模糊支持向量机 设训练集为 s - 瓴，n ，墨) ，“j ( 而，* ，s ) 其中_ 彤，y j 一1 q ，盯s 1 ，盯为大于零的实数。0 为训练点 j ，j ，j ，s j 的 输出j ，1 ( 正类) 或一1 ( 负类) 的模糊隶属度( ，- 1 ，f ) 【3 0 1 【3 1 l 。 由于模糊隶属度5 ，是训练点( ，) ，s ) 隶属于某一类的程度，而参数岛是 测量错分程度的度量，因此s ，量就成了衡量对重要性不同的变量错分程度的 度量( j 。1 ，j d 。 对线性问题，求最优分类超平面问题转化为求解如下二次规划问题： 魄扣n c 妻响 s j j ( ( 1 ，x ) + 6 ) + 岛2 1 ，j 一1 ，f ( 2 - 2 9 ) 岛o ，j 一1 ，z 其中c 0 是惩罚参数，亭。( 袅，一j 岛) 7 ，5 ，是训练点( 巧，y ，s ) 隶属于某一类的 程度。 为求解二次规划( 2 - 2 9 ) 的对偶规划，构造如下l 4 鲫增p 函数： l 似以最刃。扣w 旷+ c 善旬一荟口，饥“w 功+ + 岛一1 ) 一善岛岛 2 3 0 其中口一 1 ，q ) f ，卢一( 层，局) ，4 ，o ，局乏o ，一1 ，f 。 根据矸，d 馋对偶定义，对l 昭，口，l g e 函数关于w ，6 ，亭求极小，即 v 乒( ，6 ，亭，口，芦) 2 w 一4 ，y _ - o ( 2 3 1 ) r 二( 鹕以手，口，声) _ 一4 ，y ，o ( 2 _ 3 2 ) 延翅丈学工学顽士学位论文 t l ，b ，o ，p 1 _ s 1 c nj p l o tj - t j l ( 2 之o ) 将( 2 - 3 1 ) ，( 2 3 2 ) 和( 2 3 3 ) 代入式( 2 - 3 0 ) ，对口求极大，得二次规划 的对偶规划； 毒套口，一三砉套y ，咒a ，q _ ， 豇荟y n o ( 2 弼 o s 口js j ，c ，葺1 ，。， 把以上二次规划的目标函数转换为求极小，得到二次规划的对偶规划： 睁三塞粪y ，弘口，q 一，一套口， 虬荟y 一- 像3 5 o s a ls s i c ，j - t ，l 因此求最优超平面问题转化为求解二次规划( 式2 2 9 ) 的对偶规划( 式 2 - 3 5 ) 问题。规划式( 2 3 5 ) 所示规划是一个凸二次规划，解得其最优解 4 + 一“，彳) 7 ，所以得到模糊最优分类函数p 2 】p 3 】为： ，0 0 一s 印 ( 矿功+ 6 ) ，x 月”， 其中。荔口；y _ ，6 只一再y 一+ 五) ，z 鬈i o z t 毛q 。 在口一“，西) 7 中只有一部分蠢，o ，而与之相对应的训练点的输入毛称 为支持向量。一般情况下支持向量有两种；一种是o t 口? c 屯c 相对应的支持 向量，这种支持向量分布在超平面的边缘；另一种是西，墨c 所对应的支持向 量，这种支持向量就是被错分的样本。标准模糊支持向量机与支持向量机最 延边大学工学硕士学位论文 大的区别在于由于墨的存在，标准模糊支持向量机中西所对应的支持向量可 能与支持向量机中所对应的不是同一类支持向量。 对于非线性问题，引入核函数k “，_ ) ，则分类问题可用如下二次规划 表示： 呼主塞套y ，乃口，q x “_ ，一妻q 弘荟乃q q 。6 0 5 口j 5 j c ，一1 ，f 式( 2 3 6 ) 所示规划为一个凸二次规划，解得其最优锯得到模糊最优分 类函数： ， ) 一s g i l 口；) ，k _ ) + 6 ) ，z 彤 ( 2 - 3 7 ) 其中 6 - 咒一暑y ，口，k 西) ，f f i o t it 墨c ， ( 2 3 8 ) 2 5 本章小结 本章对本文所需要的相关基础理论进行了概括性的论述，包括统计学习 理论，支持向量机理论和算法，模糊模式识别概念和基本原理，并对他们进 行了分析和数学上的概述，对本论文模糊支持向量机算法的研究奠定了基础。 延边大学工学硕士学位论文 3 1 引言 第3 章改进的模糊支持向量机算法 当样本中存在模糊因素或对支持向量机起决定性因素的分类面周围有噪 声时，支持向量机运算结果将受到很大影响，对这种情况必须首先应该对噪 声进行有效的去除，使之对样本的影响减少到最小程度，使支持向量机能够 有效地工作。首先根据模糊k 近邻的方法对合成样本中的在分类面附近确定 为噪声的点去除掉，然后根据模糊样本的隶属度对标准模糊支持向量机进行 改进。 3 2 样本选取方法 支持向量机分类只与训练样本中的支持向量( s u p p o r tv e c o 鹤，s v ) 有 关，s v 最终决定了决策函数。按照支持向量机理论，s v 集合包含了所有解决 分类问题的信息，并且s v 位于离超平面较近的位置。”。一般情况下，s v 只是 训练集中的一部分，然而在优化学习过程中，将大量时间花费在非s v 的优化 上。这就有必要对样本进行必要的预处理，即减小样本集。在本学位论文中为 了减小样本集，提高s v 所占比例，采用了模糊k 近邻的方法，有效去除样本 中的噪声点，保留模糊样本，使优化学习过程更有效地集中在s v 的优化上。 3 2 1k 近邻算法 k 近邻f k n n ) 算法是模式识别中广泛使用的一种基于实例的分类方法” k n n 算法假定所有的样本对应于n 维空间中彤的点，一个样本的最近邻是根 据标准的欧氏距离定义的。任意的样本x 表示为特征向量x 一 1 ，一，矿) ，一 表示样本x 的第i 个特征的值。那么，两个样本而和的距觏，j 定义为： j 一踊 ( 3 一1 ) 在最近邻学习中，目标函数可以是离散值( 分类问题) ，也可以是连续值 延边大学工学硕士学位论文 ( 回归l 司题) ，本文主要讨论目标函数为离散值的情况，即，：彤一y ，兵甲 y 一“，l ，匕) 。k n n 算法的返回值于( ) 就是对，( ) 的估计，它就是距离最 近的k 个训练样本中最普遍的f 值： ，吒) 一缸g m a x 6 p ，) ) ( 3 - 2 ) y 8 口 其中， 讹6 ) - 麟：妇 ( 3 _ 3 ) 3 2 2 模糊k 近邻样本预选取方法 本文对鼢州算法进行改进的思路是根据距离对k 个近邻的贡献模糊加权， 将较大的权值赋给较近的近邻( 样本距离越近，相似度越高，贡献也就越大 ) ，根据与每个近邻的距离矾，平方的倒数加权这个距离的贡献： ，瓴) 一a r g m a x 以6 “，“) ) ( 3 4 ) ， 舒 其中， 讹6 ) _ = 伊5 ， 模糊k 近邻样本预选取的步骤如下。 1 ) 根据样本的类别数确定类别数，并对每一个样本作以下步骤( 本文只 研究2 类问题) 。 2 ) 对训练数据样本距离作升序排序( 为样本4 到4 之间的距离) 3 ) 找出每一个点x 的k 近邻，然后对每一个近邻点，如果近邻点与该点的 类别相同，则标记k - l ，否则k o ) 。o ，设厶 ) ( i = 1 ，k ) 为点x 的 第i 个近邻的欧式距离。近邻模糊度定义为； 延边大学工学硕士学位论文 k 厶 p o ) - 筮1 一 ( 3 6 ) 七罗k o ) ，= f 4 ) 根据每个训练数据的模糊k 近邻隶属度式( 3 6 ) 进行分析，设定预值 口，声( 0 口c ，1 ) 。若a t p ) t 声，则认为是噪声，是不确定样本；弘 x ) 卢 或( x ) 墨a 则保留设置为模糊样本。 5 ) 删除不相关点后，重新计算样本间最近邻距离。 6 ) 根据没有模糊噪声点的样本进行训练得到m a r g i n 。 7 ) 对于步骤4 ) 中的每个不确定样本，计算它到超平面的距离d ( x ) ，如 果d ( x ) m a r g i n 2 ，根据式2 ) 步骤进行分 析操作。 3 3 改进的模糊支持向量机算法 根据预选取后的去除了噪声但含有模糊样本的合成样本，从模糊特征表 示方法入手，结合模糊隶属度的确定方法和模糊规划后的阙值确定的依据， 对模糊支持向量机进行改进，能够使支持向量机有效地对参杂模糊样本的合 成样本进行处理。 3 3 1 模糊特征表示方法 对于本文研究的模糊信息，其模糊特征有三种啪1 ：模糊正类( 样本点属于 正类的隶属度大于属于负类的隶属度为) ：模糊负类( 样本点属于负类的隶属 度大于属于正类的隶属度) ；居中( 样本点属于正类隶属度等于属于负类隶属 度1 。 设样本点属于正类( 用1 表示) 或负类( 用1 表示) 的隶属度为6 + 或6 一 ( 6 + ，6 。【，1 】) 。为表示方便，我们引进6 卜1 - 0 5 】u 【o 5 ，1 】，使得 6 + 6 6 一一d 。因此，三种模糊特征可用特殊的三角模糊数表示： 延边大学工学硕士学位论文 ) ，i ( ，2 ，r 3 ) 暑 学，2 6 一l 三鱼二：= 翔，。5 d 墨t 。一，) ( 半胁1 ，华- l s 多妯5 3 3 2 模糊隶属度的确定 在支持向量机中唯一的自由变量就是参数c ，它控制分类间隔和错分训 练点的个数( 要求无错分训练点c m ) 。在标准模糊支持向量机中，可以设 置c 为一个比较大的值，这样就能和支持向量机一样得到分类间隔以及较少 的错分训练点数。若将所有的模糊隶属度s j ( ，一1 ，f ) 都孳置为1 ，则标准模 ， 糊支持向量机变为普通支持向量杌a 通过不同的模糊隶属度5 的确定，可以 控制所需要的训练点，一个小的s ，值使得相对应的训练点变得较为不重要。 对于给定的一个模糊分类问题，应先设置一个小的下限值，并根据具体 问题的要求，选择一个合适的函数来给每一个训练点赋予一个模糊隶属度； 最后，根据前述的标准支持向量机方法，求出最优超平面和最优分类函数。 例如，若想构造一个连续学习阅题，先选择d ，o 作为模糊隶属度的下艰。 由于是连续学习问题，因此选择s ；以时间f ；作为参数，即 s i - f q l ) ，j 1 1 ，l ( 3 8 ) 其中s 乞s 是训练点在系统中出现的时刻可以认为最后一个训 练点最重要，故它的模糊隶属度五一，辑) 一1 ，第一个训练点的模糊隶属度 而厂瓴) 一盯。如果认为模糊隶属度是时间的线性函数，则可以选择 s | - f q | ) 一8 | i 年b 。 将边界条件代入，可以得到 延边大学工学硕士学位论文 旷他) - 等p 臀 ( 3 9 ) l 一l 一h 如果考虑模糊隶属度是时间的二次函数，则可以选择 s j 篁，o ，) - a o ，一6 ) 2 + c ( 3 - 1 0 ) 将边界条件代入得 p 他) | ( 1 训( 饕2 + 仃 ( 3 3 3 3 阈值确定 设模糊训练集为 s - ( 而，_ ，) ，( 】0 ，y ，) ，( b h ，y ，“) ，“，) 0 ) ( 3 一1 2 ) 其