（计算机软件与理论专业论文）模糊支持向量机的相关技术研究.pdf

武汉理1 人学硕士学位论文 中文摘要 本文针对支持向量机( s v m s ，s u p p o r tv e c t o rm a c h i n e s ) 中的过学习、不可 分区域、过长的训练时阳j 等问题，提出4 类改进的模糊支持向量机( f s v m s ，f u z z y s u p p o r tv e ct o rm a c h in e s ) 。 1 基于九一截集的f s v m s 。这类学习机将f s v m s 与模糊理论相结合，提 取训练集中的少部分样本，形成少训练样本集，构造基于这种少训练样本集上 的f s v m s 。首先选取每类样本集的中心，利用样本与其类中心的距离定义隶属 函数。该隶属函数将每类数据映射到一个超球体内，这样训练集成为一个模糊 集，每一个样本是一个三元组，包括样本的特征、样本的类别属性、样本的隶 属度；其次，选取个合适的参数a ，利用a 一截集选取特征向量，利用特征向 量构造f s v m s ；第三，利用有向无环图决策机制，将该类学习机推广到多类问 题。 2 基于线性聚类的f s v m s 。该类学习机利用线性聚类，提取距分类超平面 较近的样本构造改进的学习机。首先选取训练集中最典型的一些样本，构造一 个粗糙s v m s 的分类超平面，用样本与这个超平面的相对距离定义隶属函数， 将所有的训练样本都映射到一个带形区域；其次，选取合适的聚类参数a ，缩小 这个带形区域，将离粗糙超平面比较近的数据映射到这个小的带形区域，用这 个小的带形区域中的数据构造f s v m s ；第三，利用1 一对一1 决策机制，将该类 学习机推广到多类问题。 3 基于球形区域的f s v m s 。该类学习机也是在少训练样本集上构造的。首 先，在所有训练样本的基础上，选取训练集的中心，考虑两类样本的不平衡性， 定义该中心为两类中心的中心；其次，在每类训练样本中，利用样本与中心的 相对距离定义隶属度：选取参数，截取少训练样本集，在少训练样本集上构造 f s v m s 。 4 基于聚类的f s v m s 。许多聚类技术可以用s v m s 。该类学习机利用模糊 c 一均值聚类技术，将每类训练集划分为若干个子集，这些子集由相似样本组成 的。利用聚类中心组成少训练样本集，并用于构造f s v m s 。在聚类时，山于位 于类边缘的稀疏性，可通过选择合适的聚类参数，伎这些稀疏数据独立成为一 个聚类中心。因此，减少训练样本既不影响边缘数据，也不影响f s v m s 的性能。 关键词：支持向量机，模糊支持向量机，少训练样本集，隶属函数， 模糊c 均值聚类 武汉理：l 人学硕卜学位论文 a b s t r a c t i no r d e rt os o l v et h eo v e r f i t t i n g ，u n c l a s s i f i a b l er e g i o n sa n dt i m ec o n s u m i n gf o r t r a i n i n gi ns u p p o r tv e c t o rm a c h i n e s ( s v m s ) ，f o u rk i n d so fi m p r o v e df 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 s ) a r ep r o p o s e di nt h i sp a p e f ， f s v m sb a s e do n 九一c u ta r ep r o p o s e d t h ef i r s ti m p r o v e dl e a r n i n gm a c h i n e sa r e t h ef s v m sb a s e do nt h ee d g et r a i n i n gd a t ai ne a c hc l a s s t h el e a r n i n gm a c h i n e s c o m b i n ef s v m sw i t ht h et h e o r yo ff u z z ys e t ，e x t r a c ts o m ed a t af r o mt h e e n t i r e t r a i n i n gd a t at of o r mt h er e d u c e dt r a i n i n gs e t ，a n dt h e nc o n s t r u c tt h ef s v mo nt h e r e d u c e dt r a i n i n gs e t f i r s t l y , t h em e m b e r s h i pf u n c t i o n sa r ed e f i n e dw i t ht h ed i s t a n c e s b e t w e e nt h et r a i n i n gd a t aa n dt h e i rc l a s sc e n t e r s ，t h e nt h em e m b e r s h i pf u n c t i o n sm a p t r a i n i n gd a t af r o me a c hc l a s si n t oas p h e r i c a lr e g i o n t h et r a i n i n gs e tb e c o m e st h e f u z z yt r a i n i n gs e ti nw h i c he a c ht r a i n i n gd a t u mi n c l u d e ss a m p l e s f e a t u r e s ，l a b e la n d m e m b e r s h i pd e g r e e s e c o n d l y , t h em o r ei m p o r t a n tt r a i n i n gd a t ae x t r a c t e df r o mt h e o r i g i n a lt r a i n i n gs e lb yu s i n gt h es u i t a b l ep a r a m e t e r 九a r eu s e dt of o r m 九一f s v m s t h i r d l y , t h el e a r n i n gm a c h i n e sa r ee x t e n d e dt om u l t i - c l a s sp r o b l e m sb yu s i n gt h e d e c i s i o nd i r e c t e da c y c l i cg r a p h ( d d a g ) s t r a t e g y f s v m sb a s e do nl i n e a rc l u s t e r i n ga r ep r o p o s e d t h et r a i n i n gd a t ac l o s et ot h e h y p e r p l a n ea r e e x t r a c t e dt of o r mt h ei m p r o v e dl e a r n i n gm a c h i n e sb yu s i n gl i n e a r c l u s t e r i n g f i r s t l y , t h el e a r n i n gm a c h i n e ss e l e c tt h em o s tt y p i c a ls a m p l e s ，s u c ha st h e c e n t e r so ft w oc l a s s e s ，t of o r mt h ec o a r s ec l a s s i f i c a t i o nh y p e r p l a n eo fs v m sn a m e d p r e f o r m e dh y p e r p l a n e t h em e m b e r s h i pf u n c t i o n sa r ed e f i n e dw i t ht h ed i s t a n c e s b e t w e e nt h et r a i n i n gd a t aa n dt h ep r e f o r m e dh y p e r p l a n e a n da l lt h et r a i n i n gd a t aa r e m a p p e di n t ot h ez o n a la r e a s e c o n d l y ，t h ed a t ac l o s e dt ot h ep r e f o r m e dh y p e r p l a n eb y r e d u c i n gt h ez o n a la r e aa r eu s e dt of o r mf s v m s t h i r d l y , t h el e a r n i n gm a c h i n e sa r e e x t e n d e dt om u l t i - c l a s sp r o b l e m sb yu s i n go n e a g a i n s t o n es t r a t e g y f s v m sb a s e do ns p h e r i c a lr e g i o n sa r ep r o p o s e d t h er e d u c e dt r a i n i n gs e ti s u s e dt of o r mt h el e a r n i n gm a c h i n e s f i r s t l y , t h ec e n t e ro ft h es p h e r i c a lr e g i o ni s s e l e c t e db a s e do nt h ee n t i r et r a i n i n gs e t b e c a u s et h et r a i n i n gs e tm a y b ei si m b a l a n c e ， m i d d l ep o i n t so ft w oc l a s sc e n t e r sa r ed e f i n e da st h ec e n t e ro ft h es p h e r i c a lr e g i o n s e c o n d l y , i ne a c hc l a s s t h em e m b e r s h i pf u n c t i o nj sd e f i n e dw i t ht h ed i s t a n c eb e t w e e n l j 武汉理 大学硕士学位论文 t h et r a i n i n gd a t aa n dt h ec e n t e r t h i r d l y ，t h er e d u c e dt r a i n i n gs e to b l a i n e db yt h e s u i t a b l ep a r a m e t e ri su s e dt of o r mt h ep r o p o s e df s v m s f s v m sb a s e do nc l u s t e r i n ga r ep r o p o s e d t h e r ea r em a n yc l u s t e r i n gt e c h n i q u e s ， s u c ha sf u z z yc - m e a n s ( f c m ) c l u s t e r i n g , d e n s i t yc l u s t e r i n g ，w h i c hc a nb eu s e di n s v m s i nt h i sp a p e qw es e l e c tt h ec l a s s i cf c mc l u s t e r i n gt e c h n i q u et or e d u c et h e n u m b e ro ft r a i n i n gd a t a ，t h e s el e a r n i n gm a c h i n e sp a r t i t i o nt h et r a i n i n gd a t ai n t o m a n yc l u s t e r sb yu s i n gf c mc l u s t e r i n g e a c hd u s t e ri sm a d eu po ft h es i m i l a r t r a i n i n gd a t a t h er e d u c e dt r a i n i n gs e tc o n s i s t i n go ft h ec e n t e r so ft h e s ec l u s t e r si s u s e dt of o r mt h ei m p r o v e df s v m s d u r i n gc l u s t e r i n g ，b e c a u s eo fs p a r s e n e s so f s u p p o r tv e c t o r s ，t h es p a r s et r a i n i n gd a t al y i n gi nt h ee d g eo fe a c hc l a s sb e c o m et h e c e n t e ro fd u s t e ri n d e p e n d e n t l y s ot h er e d u c e dt r a i n i n gs e ta f f e c t sn e i t h e rt h ee d g e t r a i n i n gd a t an o rt h ep e r f o r m a n c eo ff s v m s k e y w o r d s ：s u p p o r tv e c t o rm a c h i n e s ，f u z z ys u p p o r tv e c t o rm a c h i n e s ，t h e r e d u c e dt r a i n i n gs e t ，m e m b e r s h i pf u n c t i o n s ，f u z z yc - m e a n sc l u s t e r i n g i i x8 6 0 6 8 8 此页若属实请申请人及导师签名。 独创性声明 本人声明，所里交的论文是我个人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特剐加以标注和致谢 的地方外，论文中不包含其他入已经发表或撰写过的研究成果， 也不包含为获得武汉理工大学或其它教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示了谢意。 研究生签名：亟! l i 警皂日期望6 ：望_ ：， 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定， 即：学校有权保留送交论文的复印件，允许论文被查阅和借阅； 学校可以公布论文的全部内容，可以采用影印、缩印或其他复制 手段保存论文。 ( 保密的论文在解密后应遵守此规定) 研究生签名：玉立之之导师签名拯醐尘盟 注：请将此声明装订在论文的目录前。 武汉理l 一大学硕士学位论文 1 1 前言 第1 章绪论 机器学习是现代智能技术的一个重要研究方向。s i m o n 将机器学习阐述 为：“如果一个系统能够通过执行某种过程而改进它的性能，这就是学习。” 1 9 1 3 年m c c u l l o c h 与p j t t s 对神经元模型( m p 模型) 的研究是研究机器学刊的 一个重要罩程碑，首次发现了人类神经元的工作方式，并给出了其数学描述。 计算机科学与控制理论均从这项研究中受到了启示，并开辟了新的研究方 向。 按照其受启发的机理来分类，机器学习可以分为基于分子生物学的机器 学习、基于神经生理学的机器学习以及摹于认知心理学的机器学习。而后者 按照依据的心理学现象可以分为归纳机器学习、解释机器学习、类比机器学 习等。也可以根据被学习的对象( 相当于知识) 是否可以表示为关系型数据库 形式，将机器学习分为结构化机器学习( 相当于良构知识) 与非结构化机器 学习( 相当于非良构知识) 。 根据数据的数学性质与对机器学习不同的需求，结构化机器学习可以分 为基于符号的机器学习与基于数据的机器学习，它们的理论基础分别为粗集 ( r s ，r o u g hs e t ) 理论与统计学习理论。对于非结构化的机器学习的分类 十分困难，这与非线性问题中所遇到的问题类似。本文讨论的是基于数据的 机器学习。 基于数据的机器学习从观测数据( 训练数据) 出发，寻找数据问的规律， 建立数学模型，利用这些规律和数学模型来对未知的数据和无法观测的数据 进行预测。其实现方法大致有以下三种”3 ： 一是参数估计法，如模式识别、神经网络等。现有机器学习方法共同的 重要理论基础之一是统计学。参数方法l r 是基于传统统计学的，在这种方法 中，参数的相关形式足己知的，训练样本用米估讣参数的值。这种方法有很 人的局限性，首先，它需要已知样小分布形式，这需要花费很大代价。其次， 武汉理j 人学硕士学位论文 传统统计学研究的是样本数目趋于无穷人时的渐近理论，现有学习方法也多 是苯丁此假设。但在实际i 、u j 题中，样本数往往是有限的，因此一些理论上很 优秀的学习方法实际中表现却可能不尽人意。 二是经验非线性方法，如人【：神经网络( a n n ，a r t i f i c i a ln e u r a ln e t w o r k ) 。这种方法利用已知样本建立非线性模型，克服了传统参数估计方法 的困难。但是，这种方法缺乏一种统一的数学理论。 三是基于统计学习的方法，如s v m s 。统计学习理论( s l t ，s t a t i s t i c a ll e a r n i n g t h e o r y ) 是一种专门研究小样本情况下机器学习规律的理论。该理论 针对小样本统计问题建立了一套新的理论体系，在这种体系下的统计推理规 则不仅考虑了对渐近性能的要求，而且追求在现有有限信息的条件下得到最 优结果。从六、七十年代，v v a p n i k 等人丌始致力于统计学习理论的研究 l a q o j ，到九十年代中期，随着其理论的不断发展和成熟，也由于神经网络等 学习方法在理论上缺乏实质性进展，统计学习理论丌始受到越来越广泛的重 视。 机器学习的般步骤： 第一步：观察现象。观察数据常常是高维的，高维向量数据的可视化和 挖掘是目前机器学习研究的焦点。如高维数据的降维处理，就是将测量空间 中的高维数据变换为低维( 如二维或三维) 以利于计算机进行可视化显示。 第二步：产生假设。许多数据聚类算法都可看作是数据向量对简单混合 概率模型，如高斯分布的拟合。另外，观察数据也可向相关的有预测性的随 机模型拟合，如遗传编码数据的回归模拟神经网络模型。因此，我们可以根 据实际情况假设数据符合某种模型。有时，假设的自动牛成是非常重要的。 第i 步：构造模型。根据数据构造一个好的学习模型是机器学习的中心 目标，所以对这关键阶段机器学习提供了强大的工具。如上面提到的聚类 混合模型、回归模拟神经网络模型都有有效的参数估计算法。另外，如非监 督数据聚类、监督学习算法也都有自己的统计学描述。 第四步：检验理论预测值。 第五步：修正理论，重复第二、三步。 武汉理1 人学硕i ：学位论文 1 2 相关研究现状 v v a p n i k 等人建立的统计学习理论广泛用于函数优化i 、密度估计1 4 , 8 】 和模式识别【4 ，9 j 等领域，并带动这些领域的进一步发展。统计学习理论的一个 核心概念就是v c 维，它足衡量函数集复杂性和学习机学习能力的一个重要指 标。在v c 维的基础上得出了学习过程的一致性( c o n s is t e n c y ) 、收敛速度 和推广能力( g e n e r a l i z a t i 0 1 1a b i l i t y ) 等一系列重要结论，j 。 s v m s 是建立在v c 维和结构风险最小化( s r m ，s t r u c t u r a lr is km i n i m iz a t i o n ) 基础上的一种新的机器学习方法，广泛用于模式识别和回归领域 1 4 j t 】。它在有限训练样本基础上，构造一个具有较好推广能力的学习机，即 在训练复杂性与学习能力之问寻求折衷，以获得较好的推广能力。由于有较 好的推广能力，s v m s 方法广泛用于手写数字的识别i4 1 、医疗诊断【1 2 】、人脸 检测与识别【1 3 1 等。s v m s 有以下几个优点： 一是s v m s 在训练样本有限的情况下，寻求两类问题的最大削隔分类超平 血，这种分类超平面可能是样本趋于无穷大时的最优分类超平面； 二是s v m s 寻求训练集的最大间隔分类超平面可转化为一个二次优化问 题。从理论卜该二次优化问题可获得全局最优解，从而有效地避免了神经网 络中的局部极值问题： 三是对非线性可分问题，s v m s 用核函数将原数据映射到高维空间，以实 现在高维空问线性可分。这种核函数可以隐式地表示出来，没有必要寻求复 杂的映射，这使得在原始低维空间构造一个高维特征空间上的分类超平面成 为可能。如0 一l 问题，四个点在二维空间非线性可分，若将其映射到三维空 l 、日j ，则线性可分。 但是由于s l q 、* n s v m s 尚处于发展阶段，许多方法和理论还需进一步完善。 如许多理论目前还只有理论上的意义，尚不能在实际算法中实现；而有关 s v m s 算法某些理论解释也并非完荚，j c b u r g e s 在【1 4 】中就曾提到结构风险 最小原理并不能严格证明s v m s 为什么有好的捧广能力；对于一个实际的学 习机器的v c 维的分析尚没有通用的方法。s v m 方法巾如何根据具体问题 选择适当的核函数也没有理论依据，虽然这种选择可以得到比较好的结 武汉理r 犬学硕士= 学位论文 粜。 在s v m s 中，推广能力足人们最为关注的问题之。推广能力会受到多种 因素的影响，如异常数据、噪声数据。某些因素造成s v m s 对于训练数据有更 好的分类精度，但对于测试数据的分类精度却很低，这就是过学习。由丁异 常数据，在高维空间s v m s 也有可能过学习了训练数据。h p h u a n g 和c f l i n 人提出f s v m s 1 6 , 1 7 】，其核心思想是：根据训练数据在训练过程中的不同作用， 用异常数据检测方法( o d m ，o u t l i e r sd e t e c t i o nm e t h o d ) ，检测出异常数摒， 并赋予其小的隶属度。在训练s v m s 时，该隶属度与训练样本的惩罚值是对应 的，即对异常数据赋予较小的惩罚值，或置惩罚值为0 。当置惩罚值为0 时， 即认为该训练数据对于分类超平面没有任何意义，并将其删除。文献 1 6 对 于异常数据很少的训练集，得到了很好的效果，并解决了异常数据造成的过 学习。但实际上，异常数据并不一定很少，只是和非异常数据相比很少，相 反，有时异常数据会很多。如果异常数据很多或服从某种分布，则不能删除 异常数据。因为删除异常数据会造成大量信息的丢失，从而影n n s v m s 的推广 能力。如用s v m s 进行癌细胞的诊断，训练样本中，“可能是癌细胞”的样本 对于“确定是癌细胞”的样本而言，极可能是异常数据。因为专家在收集洲 练样本时，极有可能将这类样本列为训练样本。如果这样的样本很少，删除 则可以提高s v m s 的推广能力，但是当这类样本很多时，删除它们后，分类超 平面会向“确定是癌细胞”样本移动。这样的结果是该分类超平面会将可能 是癌细胞的病例诊断为非癌细胞。 人们比较关, 0 s v m s 的另外一个问题是其扩展性。s v m s 源于两类问题的分 类，而模式分类并不局限于两类问题，还有多类问题。如何将两类问题的s v m s 扩展为多类问题的s v m s 也是人们研究的1 个热点。t ll n o u e 和s 。a b e 等人提出 了另一类改进的s v m s 也称为f s v m s l l 8 , 1 9 j ，其定义一个与分类超平面垂直的隶 属函数，减少了不可分区域。 还有一个问题是人们不得不关心的，那就是s v m s 的训练时间。对于一个 少训练样本集而言，训练时间是人们可以接受的。但是人们普遍认为训练样 本越多，学习机的性能会越好。当训练样本1 f 常多时，即使构造了快速优化 算法，训练时问也可能很长。这时人们不得不存减少洲练样本数量与s v m s 的 4 武汉理人学硕士学何沦文 学习能力之间进行折衷，即训练时f r j 与学习机的学习能力都让人接受。对于 训l 练时间，要依赖于核函数的计算时间和二次优化时间，这两方而都与训练 样本的个数有关。在研究中，我们发现i ) l l 练集中的某些样本衔t - s v m s 性能没 有大的影响m 2 3 1 ，因此提取一部分训练样本构造s v m s 既可减少核函数的计算 时间，又可以减少优化时间。 1 3 本文组织结构及创瓤点 下面的内容安排如下： 第二章模糊支持向量机及改进策略，介绍s v m s 和f s v m s 的基本思 想、基本构造方法及其存在的问题与改进策略； 第三章基于边缘数据的f s v m s 。浚类学习机是一系列的f s v m s ，提 出了几种边缘数据的提取方法，并在二维空间上对这些学习机进行分析解 释，最后在一些经典的机器学习数据集上验证这些方法的可行性和优越性： 第四章基于聚类的f s v m s 。该类学习机利用样本之间的相似性，选取 一部分典型的样本构造s v m s ，并用经典的非线性可分的双螺旋曲线验证该 方法的可行性； 第血章回顾与展望。对s v m s 的训练问题、优化问题和优化方法等问 题进行总结，并提出进一步可研究的问题。 本文的创新点是通过一些传统模糊技术如模糊截集、模糊聚类、 密度聚类【2 6 1 等，结合训练集中支持向量的特征，构造少训练样本集上的 f s v m s 。 1 提h 了基于模糊截集的f s v m s 。浚类改进的f s v m s 根据训练样本 在训l 练过程中的不同作用，构造隶属函数，将每类训l 练数据都映射到一个 球形区域内，同时对边缘容易被错分的数据赋予较大地隶属度，相反，对 中间区域的不可能被错分的数据赋予较小的隶属度。建立映射后，每个训 练样本可认为是一个三兀组，包括训练样本的特征、类别属性和隶属度。 用参数选取隶属度较大的训练样本训练学习机。该方法的目的是减少训练 样本的个数，加速优化速度同时又不影响支持向量机的推广能力。通过机 学习经典测试集验证了该类f s v m s 有相同于或高于传统f s v m s 的推广 能力； 武汉理r 人学倾士学位论文 2 提出了基于线性聚类的f s v m s 。该类改进f s v m s 用点与分类超平 面问的相似性定义隶属函数，l b 于在训练学习机之削并没有错到分类超、| 王 面，所以先用极少数的样本，如每类的中心，构造个粗糙的分类超、p 而 代替最终的分类超平面。其核心思想是将所有的j i 练样本都映射到一个带 彤区域，先选择一个小的带形区域构造f s v m s ，然后逐渐扩大这个带形区 域，以增加训练样本的数量，提高f s v m s 的性能； 3 提出了基于球形区域的f s v m s 。它利用训练样本与其中心的距离 定义隶属函数，考虑判礴娄样本可能不平衡，该中心选取了两类中心的中 心，该隶属函数将所有的训练样本近似映射到个超大的单位球体内。选 择参数，截取一部分训练样本构造学习机； 4 提出了基于聚类的f s v m s ，它利用聚娄技术，将训练集分割成若 干个聚类，每个枭类出些相似样本组成。在训练学习机时，利用聚类中 心代替鞋个聚类中的所有样本构造f s v m s 。在聚类过程中，选择聚类因子 使边缘非常重要的样本，如支持向量，单独成为 个聚类，该聚类的巾心 即为样本本身。聚类的结果是减少了训练样本，加快了优化速度，升设有 影响f s v m s 的性能。 武汉理j 一人学硕十学位论文 2 1 引言 第2 章模糊支持向量机及其改进策略 f s v m s 是一种改进的s v m s 。f s v m s 有两种表现形式，其“主要是根据 训练样本在训练过程中的不同作用，加大对容易错分样本的惩罚，以改进 s v m s 的性能。第二种f s v m s 是针对两类问题推广到多类问题时，决策过程 中存在的不可分区域，构造隶属函数，以减少不可分区域。s v m s 是针对两 类问题的分类提出的学习算法，町推广到多类问题。作为在统计学习理论 上发展的一个新方法【3 ，4 1 ，其和模式识别的其它方法结合在一起，广泛用于 医疗诊断、人脸检测与识别、手写数字的识别等。自从清华大学的张学工 教授将其引入到国内后| 27 ”】，国内掀起了一股s v m s 研究的热潮，多数都 集中在s v m s 应用方面的研究，对其理论研究和方法改进等方面的研究较少 1 2 9 , 3 0 l 。对f s v m s 的研究就更少了，主要集中在一些应用方面 3 1 , 3 2 】，很少人 提出改进的f s v m s 。 2 2 支持向量机 s v m s 是在两类问题分类的基础上提出的一种新的学习算法。其基本 的思想是最大限度地分开两类训练样本，即对于一个两类问题的训练样本， 构造一个分类超平面，使得分类间隔达到最大。这种分类间隔与学习的推 广能力有很大的关系 3 3 , 3 4 】。 定义2 1 ：两类样本中离超平面最近的样本到超平面的距离之和称分 类间隔( m a r g i n l 。这些离分类超平面最近的样本对分类超平面的构造起决 定作用，被称为支持向量。 如图2 - l 中的两类问题的分类超平而的分类间隔为a r g i n = d ，+ d ：。d 表示训练集巾第一类样本c l a s s l 中离分类超平面最近的样本到分类超平面 的距离，d 。表示i j l l 练集中第二类样本c l a s s 2 巾离分类超平面最近的样本离 分类超平面的距离。从图2 - 1 可以看出，( 1 ) 支持向量是离分类超平面最 近的向量：( 2 ) 在训练集巾，每类数据都必须有支持向量，其包括支持 武汉理i ：人学硕十学位沦文 量的数目可以不等；( 3 ) 支持向量到分类超平面的距离是相等的，即同 类样本中的支持向量位于与分类超平面平行的个超甲面卜；( 4 ) 和训练 数据相比，支持向量的数目是非常少的：( 5 ) 支持向量都位于同类数据的 边缘，即只有边缘数据才有可能成为支持向量，而类中心附近的数据不可 能成为支持向量。 图2 1 两类数据的线性分类超平 面、支持向量及分类间隔 图2 2 数据d a t a l 和d a t a 2 支持 向量机的超平面 根据s v m s 的构造思想，对于一个线性可分的两类问题的分类，其分 类超平面是唯的。如图2 2 ，分类超平面h y p e r p l a n e l 和h y p e r p l a n e 2 都 能将训练集分开，但分类超平面h y p e r p l a n e l 的分类问隔要比h y p e r p l a n e 2 的大，所以分类超h y p e r p l a n e i 是s v m s 的分类超平面。特别地，埘于只 有一个i 卜样本和一个负样本的训练集也可以构造一个分类超平面，该超甲 面就是这两个样本的中垂面。 2 2 1 线性可分的支持向量机 设训练集 s ； ( t ，y 。) i ( ，y ；) r 。x r ，i = l 2 ，q( 2 1 ) 足线性可分的，即该训练集可以被个分类超甲面正确无误地分开。设分 类超半而为 w 7 x + b ：0 则训练数据z ，与分类超平面( 2 2 ) 的距离为 ( 2 2 ) 武汉理i 大学硕士。1 _ 奇= 论文 。妒t + b l i ”可 ( 2 3 ) s v m s 的基本思想是寻找一个分类超平面，使得分类间隔最大，这个分类 间隔就是两个平行平面中间的部分。冈此自然想到两个特殊的平面 w 7 z + 6 = 1 ( 2 4 ) w 。x + b = - 1 ( 2 5 ) 使距分类超平面最近的点都在这两个平面上且训练数据都在它们的外侧， 则分类间隔为 g 讥= 埘2 丽24 赤 ( 2 6 ) 根据s v m s 的基本思想，有下面的优化问题 m a x w t w ( 2 7 a ) s i t w 耋：基1 警j 竺1 时 7 。， 7 t + 6s 一当y 一时 对( 2 7 b ) 式进行变形可得优化问题( 2 8 ) ，求其最优解可构造分类超平面 ( 2 2 ) m i n 三w r w s t 咒w 7 t + b ) 1 2 2 2 线陛不可分支持向量机 ( 2 8 a ) ( 2 8 b ) 事实上，现实中，大多数数据集都是线性不可分的，即不能构造分类超 平面对其进行准确无误地分类。为了构造训练集卜的最大问隔分类超平面， 就必须允许部分数据违反约束条件( 2 8 b ) ，当然这部分数据越少越好。引进 非负松弛因了 营乜，约束条件( 2 8 b ) 可? l j , j y iw 7 x i + 6 ) 1 一皇( 2 9 ) 当0 s 喜 0 ，数据x i 虽然违反，约束条件，但在其 分类超平血( 2 2 1 一确的方，叩数据x l 被分类超平面( 2 2 ) 正确地分类： 武汉理f 人学硕十学位论文 当毒= 1 时，y 。( w z x i + 6 ) = 0 ，数据t 违反了约束条件， 平面( 2 2 ) 卜，超平面无法对其进行判别，即数据被拒判； 当量 1 时，y 。( t + 6 ) c 0 ，数据t 违反了约束条件， 平面( 2 2 ) 错误的一方，即数据被错分。 引进非负松弛因子后，约束优化问题( 2 8 ) 可化为 m i n 2 w t w + c 皇 s t y 。( w t x i + “1 - 皇 皇 0 并在其分类超 并在其分类超 ( 2 1 0 a ) ( 2 1 0 b ) ( 2 1 0 c ) 其中c 为用户定义的一个正参数，其在s v m s 的复杂性和不可分数据之l b j 寻求折衷，也可以作为一个惩罚值。当c 很大时，对违反约束条件( 2 8 ) 的 数据加大惩罚以减少分类间隔，提高s v m s 的推广能力，反之，则忽视一 部分容易错分的样本，以增加分类间隔。由优化问题( 2 1 0 ) 的最优解，便可 得到线性不可分问题的分类超平面( 2 2 ) 。 2 2 3 非线性可分的支持向量机 还有一类s v m s 是非线性可分的s v m s ，其针对训练集虽然不能被一 个分类超平面准确无误地分开，但若将其映射到一个高维空间，在商维空 间训练集是线性可分的，可构造其分类超平面，这个高维空间被称作特征 空间。如0 1 问题，数据集中有四个二维数据( 如表2 - 1 ) ，_ 当分量相同时， 其为第一类，当分量不相同时，其为第二类。在二维空间内，训练集是非 线性可分的( 如图2 3 ) ，在三维空间内，其是线性可分( 如图2 4 ) 。之 所以在高维空间可分，是因为在低维空间和高维空间建立了个映射 ( 2 1 1 ) 。在实际应用中，核函数不是显式的映射，而是通过一个隐函数表 现出来，只要这个隐函数满足m e r c e r 定理。如二阶多项式核 k ( x , x ) ，0 7 z + 妒，通过映射0 卜o ? ，z 刍强x ：，佤，聂：，1 ) 7 ，可将二维空间 ( x ：) 7h ，x ：r 映射到六维空间 ( x j ，x ；，毛x 2 , 毛，玉! ，1 ) 7 i x , e r 。 武汉理i 大学硕士学位论文 田= ( 1 ，1 ) 一( 1 ，1 ，0 ) ( o ，0 ) 一( o ，0 ，0 ) ( o ，i ) 一( o ，1 ，1 ) ( 1 ，0 ) 一( 1 ，o ，1 ) 表21 0 一l 问题的训练数据 类别 如 11 1 o0 01 1 10 ( 2 1 i ) 图2 - 1o - 1 问题在二维空间的非图2 2o l 问题在三维空间的线 线性分类器 性分类器 通过0 1 问题的例子知道，对于一个在低维空间上不可分的训练集， 可建立它到高维空间的一个映射，以实现其在商维空间的线性可分，这种 映射通过核方法】来实现的。 2 3 模糊支持向量机 在训练过程中，每个训练数据对于支持向量机所起的作用足不同的。 边缘数掘是最容易错分的月- 成为支持向量的机会就多一些，而中间的数据 成为支持柚量的可能性要小一些，甚至根本不可能成为支持向量。文献 1 6 ，1 7 】根据训练样本在训练过程巾的不同作用，对所有数据包括异常数据 蜮予一个隶属度。 武汉理| ：人学硕十学位论文 当置是异常数据 + e 其它 其中洲表示欧氏距离，z 表示类的中心，s 是个一个非常小的正数， o c 盯cs 。这样将所有非异常的数据都映射到区阳j ，1 。 在构造s v m s 时，优化问题( 2 1 0 ) 可表示为 m i n w t l 4 u + c “冀 ( 2 1 2 a ) s t y w + b ) m l 一喜 ( 2 1 2 b ) 皇 0( 2 1 2 c ) 其中m 为模糊化因子。其拉格朗日泛函为 q ( w 点邑a ，声，“) = j 矿w + c 善t “? 葺一骞a ， y 。t x i + b ) 一1 + 爵卜吝芦高( 2 1 3 ) 其中a = ( c r la ：，a ，) ，卢；( 岛，p ：，局) 为拉格朗日乘子，将其分别对w b ，皇 求导并置为0 ，则有( 2 1 4 ) 型掣d w 一如y 舻o ( 2 1 4 8 ) 倒 旦l毯!幽：一壹口，y，=o(214b)ob 鲁 旦! q ! i 掣：c u ? 一q 一层。o ”t ( 2 1 4 c ) 将( 2 1 4 ) 式代入( 2 1 3 ) 式可得优化问题 m n q ) = 圭善1 善1 “一y 幽x ，一砉q ( 2 1 5 a ) n 多q 咒：o ( 2 _ 5 o a o ? ( 2 1 5 c ) 其中c u ；是一个变化的参数。分类超平面( 2 2 ) 的权向量w 和标最b 山 ( 21 4 ) 和( 2 1 6 ) 式决定。 1 2 = 茗 矧 j 忏一1 引 一m 武汉理1 人学硕十学位论文 b = 三l ( w 0 石( 1 ) ) 十( w o 工( 一1 ) ) 】 ( 2 1 6 ) 其中，x 0 ) 表示属于第。类的任意一个支持向量，x ( 一1 ) 表示属于第二类的 任意一个支持向量。 对于多类问题，目前使用较多的方法有1 - a a ( o n e a g a i n s t a 1 1 ) j y 法t 3 , 3 5 、 1 一a l ( o n e a g a i n s t o n e l 方法1 3 , 3 6 i 和d d a g 方法m 3 8 1 。s a b e 等人提出的解决 多类问题的f s v m s 是在这些方法的基础上，构造隶属函数以减少不可分 区域。如1 - a 1 多类模糊支持向量机，一维空间上的隶属函数定义为 f 1当d f o ) = 1 时 m q2 1 d i ，o ) 其它 其中d ，0 ) 为c l a s s 与c l a s s j 两类数据的分类超平面。利用矩阵 m ：，o ) ( f ，；l 2 ，n ，f ) ，对第f 类数据的隶属函数为 他o ) = m i 。 ) n m 即 稚加；n ( 1 簪) 将数据x 分n ( 2 1 7 ) 类中去 a r g m a x m ：g ) 2 4 模糊支持向量机的改进策略 f 2 1 7 ) 对丁- 训练集( 1 1 ) 有f 个d 维训练样本，对于优化问题( 2 1 5 ) ，引入核函 数后，核矩阵为d “；m y f t r z i ，z ，j 。核函数的计算复杂性为o 似) ，s v m s 的 计算复杂性为o ( d 1 2 ) 。因此s v m s 训练样本个数对s v m s 的计算复杂性影 响最人。 选取部分训练样本构造少训练样本集上的f s v m s 是其改进策略之 。在s v m s 中，支持向晕都集叶1 在每类训练集的边缘，类中心的样本不 武汉理t 人学颂士学位论文 可能成为支持_ 量。因此选取少训练样本集不能随机选取，要充分考虑支 持向量的特征。支持向量有叭f 特征： ( 1 ) 支持向量都集中的数据集的外部且是稀疏的。现实中人部分训练 数据都服从j f 念分向，即同一娄的大部分相对集中，少数特殊数据离其类 r f ；i 心较远。这些特殊的数拐，有些是很容易错分的并且极有可能成为支持 向量。有些是不可能被锆分的，即离分类超平面较远且在其正确的一方。 目2 5 中，与同类的其它数掂相比，支持向量五，x ：都离其类中心较远。 当然电有些训练数据小服从正态分布，但其肯定存在边缘。这时我们可以 认为边缘的数据为稀疏的，因为若选取其合适的邻域，则该邻域l 】的数据 要比其它点相同邻域中的数据少； (