（应用数学专业论文）超球面支持向量机方法的探讨.pdf

超球面支持向量机方法探讨 专业：应用数学 硕士生：温德美 指导教师：张磊副教授 摘要 分类技术是众多应用领域的关键技术，用于分类技术的方法有多种多样。与 其它方法相比，支持向量机方法是以结构风险最小化为学习原则，具有较好的泛 化能力，且在非线性和样本属性维数高的分类问题中有较大优势。 支持向量机最初是针对二分类问题提出的，现在其热点之一是推广到多分类 问题。从几何意义上来看，支持向量机可以分为超平面支持向量机和超球面支持 向量机，虽然前者的研究较为成熟，但在多分类问题处理类别之间样本数目不平 衡的情况下，超球面支持向量机会更加适合。 在分析了常用的超球面支持向量机方法基础上，本文提出了两种新的超球面 支持向量机方法，主要包括：( 1 ) 引入正负超球面分隔两类样本，并把负超球 面半径和正超球面半径之差的大小作为衡量该方法泛化能力的一个指标，提出了 最大间隔同心超球面多类支持向量机( m m c h m s v m ) 方法；( 2 ) 基于调节训练样 本中的分类错误率和支持向量数占训练样本总数的比例的目的，引入了参数 ，l ，2 ，通过改进m m c 删- s v m 方法，提出了y l ，2 - m m c h m s v m 方法，并证明了 参数，。，、，的意义。 最后，通过对u c i 机器学习数据库的若干数据集进行的实证分析，本文验 证了v 。，、，一m m c h m s v m 方法的有效性。 关键词：支持向量机，超球面，多类分类 d i s c u s s i o na b o u th y p e r s p h e r e - b a s e dm u l t i c l a s s s u p p o r tv e c t o rm a c h i n e m a j o r ：a p p l i e dm a t h e m a t i c s n a m e ：w e nd e m e i s u p e r v i s o r ：z h a n gl e ia s s o c i a t ep r o f e s s o r a b s t r a c t c l a s s i f i c a t i o ni st h ek e yt e c h n o l o g yo fm a n ya p p l i c a t i o n s t h e r ea r eav a r i e t yo f c l a s s i f i c a t i o nm e t h o d s c o m p a r e dw i t ho t h e rm e t h o d s ，s u p p o r tv e c t o rm a c h i n ei s b a s e do nt h es 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 i th a sb e t t e rg e n e r a l i z a t i o na b i l i t y a n da d v a n t a g e si nd e a l i n g 谢t hn o n l i n e a ra n dh i g hd i m e n s i o nc l a s s i f i c a t i o np r o b l e m s t h o u g hs v mw a so r i g i n a l l yp r o p o s e df o rt h et w oc l a s s e sp r o b l e m s ，i ti sh o tf o r m u l t i 。c l a s s i f i c a t i o np r o b l e m s f r o mt h ev i e wo fg e o m e t r y , s v mc a nb ep a r t e di n t o h y p e r p l a n es v m m e t h o d sa n dh y p e r s p h e r e b a s e ds v m m e t h o d s h y p e r p l a n es v m i s m o r em a t u r e b u th y p e r s p h e r e - b a s e ds v mi sm o r es u i t a b l ef o ri m b a l a n c ep r o b l e m s b a s e do nt h ea n a l y s i so ft h em a i nh y p e r s p h e r e - b a s e ds v m m e t h o d s ，t h i sp a p e r p r o p o s e st w on e wh y p e r s p h e r e b a s e ds v m s o n ei st h em a x i m a lm a r g i nc o n c e n t r i c h y p e r s p h e r e sm u l t i c l a s ss v m ( m m c h m s v m ) ，w h i c hi n t r o d u c e st w oc o n c e n t r i c h y p e r s p h e r e st os e p a r a t et h ee x a m p l e so ft h ep o s i t i v ec l a s sa n dt h en e g a t i v ec l a s s t h e o t h e ri s y l ，y 2 一m m c h m s v mw h i c hu s e sp a r a m e t e r sv 1 ，2 t oc o n t r o lt h ee r r o r r a t ea n ds u p p o r tv e c t o r so ft h et r a i n i n gs a m p l e s a tl a s t ，t h i sa s s a ye x p e r i m e n t so ns e v e r a ld a t as e t sf r o mu c ia n dv e r i f i e st h e v a l i d i t yo ft h ey l ，y 2 一m m c h m - s v m 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 ，h y p e r s p h e r e ，m u l t i c l a s s i i 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：温弓惠龛 日期：劢i p 年歹月压日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学 位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查 阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其 他方法保存学位论文。 学位论文作者签名 日期：2 0 o 年多月 中山大学硕士学位论文 1 1 研究背景 第一章绪论 分类技术的应用范围非常广泛，例如语音识别，图像识别，文本分类，信用 评分，生物医学应用等。分类问题由来已久，但计算机的普及，使得基于机器学 习的分类技术得到快速的发展。目前，主要的分类方法包括决策树，朴素贝叶斯， 关联分类，f i s h e r 判别法，神经网络和支持向量机等【1 l 。 支持向量分类机是一种基于统计学习理论的分类方法。与传统的基于统计学 基础的分类方法不同，统计学习理论研究的是有限样本的学习方法，而不是研究 样本数目趋于无穷时的渐近理论【2 】。支持向量机的训练过程是求解一个凸二次优 化问题，通常能够得到全局最优解。 最先提出的支持向量机，是超平面支持向量机，其原理是用最大间隔分类超 平面分隔两类样本。t a x 和d u i n 提出了一种用超球面代替超平面的支持向量机 方法，用于数据描述( s v d d ) 3 1 1 4 后来超球面支持向量机方法被推广到用于多 类分类。其原理是，每类样本用一个超球面包围住，训练的任务是找到每一类样 本相应的超球面的球心和半径，超球面支持向量机的特点是训练速度快，支持向 量少。因为上述优点，在近几年中，超球面支持向量机在理论和应用上的研究成 果也不少。但是由于在训练过程中没有考虑其他类样本的信息，使得超球面支持 向量机往往没有超平面支持向量机的分类精度高。针对这一问题，众多学者提出 了各自的改进方法，使得超球面支持向量机的分类精度能与超平面支持向量机相 比，甚至更好。目前主要的超球面支持向量机方法涉及的模型参数较多，且参数 的可选范围较广，而参数通常没有定量上的意义，因此在参数选择上遇到不少困 难。本文通过变更训练任务和选取新的目标函数，使得模型参数在定量上有意义。 中山大学硕士学位论文 1 2 支持向量机的研究现状 近年来，支持向量机的研究取得了众多突破，但依然还有很多需要完善的地 方，主要在以下几方面： ( 1 ) 提高大型问题的训练速度。对于大型问题，如果用经典的寻优算法，需 要存储核矩阵和进行多次的大矩阵运算，要耗费大量的空间和时间。针对大型问 题，v a p n i k 等人首先提出选块( c h u n k i n g ) 算法【5 】，接着o s u n a 等人提出了分解算 法1 6 ，j o a c h i m s 将分解算法推广，提出了s v m l i g h t 算i ! 去【7 】，p l a t t 提出了序贯最小 最优化( s m o ) 算法【引s m o 也是分解算法，但是s m o 已经把问题分解到最小( 工 作样本集个数为2 ) ，并且每次分解后的优化问题的解可以解析表示，使得s m o 算法的应用十分广泛。后来也有众多国内外学者提出改进的算法，如k e e r t h i 9 1 ， 李建民【1 0 】，曾志强【l l 】等k e e r t h i 后来还提出了n p a 算法【1 2 j ，也是一种速度较快 的训练方法。目前，寻找更高效快速的训练算法，仍然是众多学者努力的方向。 ( 2 ) 核函数参数选择和构造。核函数的参数对于支持向量机的分类性影响 甚大，核函数参数的选择通常有网格搜索，梯度下降法，交叉验证法【”】，遗传算 法和粒子群算法【1 4 】等。核函数的构造也是一个重要的研究方向，a i n a r i 等人提出 了k m o d 核函数f 1 5 】，张莉等人提出了尺度核函数【1 6 1 。 ( 3 ) 多类分类问题。从支持向量机算法的提出至今，将它推广到多类分类 问题吸引了大批学者的研究，也取得了较多成果，提出了多种多类分类支持向量 机方法。详细情况将在第三章介绍。 1 3 本文的主要工作 本文介绍了标准的s v m 算法，以及它的几种变形算法c s v m ，一s v m 等， 介绍了主要的多类分类支持向量机算法，并分析它们的特点。分析了现有的超球 面支持向量机方法后，提出了m m c h m s v m 和y l ，v 2 一m m c h m - s v m 方法。 主要的研究工作包括： ( 1 ) 引入同心超球面来分离两类样本，同心超球面中负类超球面的半径与 2 中山大学硕士学位论文 正类超球面的半径之差作为衡量该方法的泛化能力的指标，与分类间隔的作用类 似，提出了多类分类超球面支持向量机方法m m c h m s v m 。并且允许这个指 标取负值，这点与分类间隔不同，但考虑到不同类的样本非近似线性可分时，若 规定这一指标必须非负，可能会取值为0 ，也就是正负类超球面将会重合。若允 许出现负值，虽然正超球面的半径可能比负超球面要大，但是能够得到两超球面 半径的大小，可以在正负超球面之间构造一个超球面作为分类超球面，增加了灵 活性。 ( 2 ) 针对m m c h m s v m 方法中，参数难以确定的问题，从y s v m 得到 启发，通过变换目标函数，引入新的参数u ，：，使得新参数在定量上有一定的 意义( 在第四章中具体说明) ，降低了参数选择的难度。 1 4 本文的内容安排 本文余下部分的安排如下： 第二章介绍支持向量机的基本原理和几种变形算法。 第三章综述多类分类支持向量机分类方法。 第四章提出了超球面多类分类支持向量机方法m m c h m s v m 和u ，v ：一 m m c h m s v m 第五章选取u c i 机器学习数据库的三个数据集进行实验，对比四种支持向 量机方法的分类效果。 中山大学硕士学位论文 第二章支持向量机基本原理 2 1 分类问题的提出 给定训练样本集 ( 彤，彤) i ，= l ，2 ，磅，其中乃e 1 ，2 ，舒，z r ，基于统 计学基础的分类方法，通常假设x 和y 符合某一未知的联合分布，概率分布函数 为f ( 五力，而分类的任务就是找出x 和y 具体的函数依赖关系少= ( 五叻，使得 期望损失最小。常用的一个分类问题的损失函数为： 地以删= 譬歹多麓：， p ， 期望损失或期望风险为： 厦力= i z 以五功) 识五力( 2 - 2 ) 因此，训练的任务就是通过从训练样本集中学习规律，然后从指示函数集中选择 适合的函数，使得同最小。但由于只五力未知，无法直接计算期望风险。 传统的处理方法是用经验分布函数代替只五力，从而用经验风险来近似期望风 险。即通过最小化经验风险 = 三喜z ，以，嗍，( 2 - 3 ) 来求得函数( 五功 欧氏空间r ，中的一个函数集的v c 维是指，能够被函数集中的函数打教的 点的最大数卧17 】。我们知道，把元素个数为n 的集合h 划分成两个子集q 和u ( 即夕n = f 2 j ，并且夕u = ) 的方法共2 ”种。 对于二类分类问题，统计学习理论中给出了经验风险( 功和实际风险 顾功之间的一个重要关系式【1 9 l ： 4 中山大学硕士学位论文 尸卜功c 叻+ 、a ( i n ( 2 n a ) + 1 ) - i n ( 0 4 ) 孙叼，仁4 ， 其中，h 是指示函数集的v c 维，1 1 是训练样本个数，0 0 ，则判x n s ：i g 类若( 力 0 ； ( 3 ) 双曲正切( 或s 型) 核函数：瞰，) = t a n h ( a x ，号+ 国 2 4 标准支持向量机的两种变形算法 v a p n i k 等人提出的c s v m 就是一种标准支持向量机的变形算法，并且较好 的解决了线性不可分的分类问题，下面将要介绍另外两种与本文的研究相关的支 持向量机变形算法。 中山大学硕士学位论文 2 4 1y s v m 方法 在c s v m 中，参数c 是用于调节分类间隔大小和分类错误率的，c 是训练 误差的惩罚因子，选取较大的c ，就会使得分类器具有较小的分类间隔和较小的 错误率，反之则使得分类器具有较大的分类间隔和较大的错误率。但是对于c 的选择范围及对结果的影响却无法作定量估计。因此，s c h o l l ( o p f 等人提出了一 种变形算法【2 0 】【2 l 】，其中参数v 的大小具有明确的意义。其优化问题为： 骢以噱加1 1 1 1 2 邮+ 蔫邑 ( 2 - 3 2 ) 约束条件为： 彤( 9 i ( 五) + 功p 一考， ( 2 - 3 3 ) 专，0 ，= 1 ，2 ，1 ， ( 2 - 3 4 ) p0(2-35) 其对偶问题为： 哑n 三喜喜几俨严以勃砂 ( 2 - 3 6 ) 约束条件为： 决策函数为： | 朋，= o ， ( 2 - 3 7 ) o 舛；闰，2 ， f y 口，之， 一一 ，b l ( 2 - 3 8 ) ( 2 - 3 9 ) | f ( x ) = s g n y f f ，蜀，功+ 毋 ( 2 - 4 0 ) 定理2 2 阉给定个样本点组成的训练集，使用y 一删算法进行分类若所 得到的p 0 ，则 1 2 中山大学硕士学位论文 ( 1 ) 若记间隔错误样本点的个数为p ，则y 等，即 ，是间隔错误样本点的个 ， 数所占总样本点数的份额的上界； ( 2 ) 若记支持向量的个数为q ，则，兰，即y 是支持向量的个数所占总样本 ， 点数的份额的下界 定理2 2 说明了参数，的大小的意义。 2 4 2o n e - c l a s ss v m 方法 o n e c l a s ss v m 首先由s c h 6 1 k o p f 等人提出【2 3 1 ，用于高维分布的估计，且最初 也是使用超平面支持向量机，初始问题如下： 酬m 刮i n 椰扣刚2 1 1 y 百, 4 ，一p ( 2 删 酬刮椰圳i | 2 + ，百，一p ( 2 。4 1 ) 约束条件为： ( r e 6 ( ) ) p 一髻， ( 2 - 4 2 ) 孝，0 ， i = 1 ，2 ，1 ( 2 - 4 3 ) 对偶问题为： 哑n 三喜喜口但勃一， c 2 讹， 约束条件为： 口，_ l ， ( 2 - 4 5 ) o 仅，乃1 ，= l ，2 ，( 2 - 4 6 ) t a x 和d u i n 提出一种变形的方法t 3 1 1 4 1 ，就是用超球面代替超平面，方法如下： m旁癌i去善劲(2-47)rer,；eg，癌， ： 约束条件为： 0 b ( x , ) - c l l 2 铲+ 莹， ( 2 - 4 8 ) 中山大学硕士学位论文 考，0 ， i = 1 ，2 ，z ( 2 4 9 ) 其中c 是待求的超球面的球心，r 是超球面的半径，上述问题的对偶问题为： 约束条件为： m 2 n 善善口鬈而劫一善口，叙而劫) ( 2 内) 。舛去，川，2 ， 口，_ 1 解出对偶问题，便可求得超球面半径f = 倪力( ) ，从而得到决策函数为： ( 2 - 5 1 ) ( 2 5 2 ) ( 力= s g n 露- z 口p ，叙五，一) + 2 口，圈r ，x ) - k ( x ，z ) ( 2 - 5 3 ) ，= lj = 1月l o n e - c l a s ss v m 通过参数l ，( o ，l 】来调节超球面的大小，通常v 越小，对落在 超球面外的正类样本的处罚越大，超球面就越大，反之亦然。超球面的引入，使 得支持向量机的方法得到了较大的改变，因为用超平面分隔的两类样本地位是平 等的，但是用超球面分隔在球内和球外的两类样本地位是不平等的，对于侧重某 一类或只对某一类感兴趣时，用超球支持向量机更为适合。 2 5 本章小结 本章首先介绍了基于数据学习的两个原则，经验风险最小化和结构风险最小 原则，并且引述了一些关于这两个原则的研究结论，并比较两者之间的优缺点和 适用范围。然后介绍基于结构风险最小化原则的支持向量机算法，包括原始的 s v m 算法，以及改进的c s v m 。接着简单介绍了核函数理论和基于核函数的非 线性支持向量机算法。在c - s v m 算法中，参数c 的作用是很关键的，关系到整 个模型的泛化推广能力，然而参数c 的大小没有明确的直观意义，使得c 的选 取较为困难。针对c s v m 这一缺点，本章最后部分介绍了，一s v m 方法，参数v 1 4 中山大学硕士学位论文 的大小是具有明确意义的。最后还介绍了o n e c l a s ss v m 方法，这一方法是超球 面支持向量机方法的基础。 中山大学硕士学位论文 第三章多类分类支持向量机方法 3 1 多类分类问题 给定训练样本集 ( 墨，彤) i ，= l ，2 ，谚，其中z 豫，y e l ，2 ，毋，要求找出 少与z 的依赖关系少= ( 力，使得对任意输入的名，能够输出其对应的= ( ) ， 这就是k 类分类问题。 支持向量机作为一种机器学习和数据挖掘方法，虽然具备很好的理论基础， 但是支持向量机方法最初是针对二类分类问题而提出的，在解决多类分类问题方 面还需不断完善。而在实际应用中，多类分类问题更为常见，因此如何有效的将 支持向量机方法推广到解决多类分类问题是现今研究的热点之一。至今人们也提 出了一些有效的多类分类支持向量机方法，其中又包括超平面多类分类支持向量 机和超球面多类分类支持向量机。 3 2 超平面多类分类支持向量机 3 2 1 直接构造多类分类器方法 w e s t o n 和w a t k i n s 提出了一种直接构造多类分类支持向量机方法 2 4 2 5 1 ，把 所有的优化参数放到同一个优化式子里面，通过求解一个优化问题直接得到决策 函数： 1膏， m i n ( 彤善) = 去( ) + 匹够 ( 3 1 ) - m = - i ，；l 脚” 约束条件为： ( 彤) + 气( 芬) + 乞+ 2 一孝夕， ( 3 - 2 ) 彩0i = l ，2 ，m e 1 ，2 ，毋彤( 3 3 ) 中山大学硕士学位论文 从而得到此分类器的决策函数为： ( 力= a r g m a x w , z + 匆 = 1 ，2 ，后( 3 - 4 ) 此方法需要解决一个后个变量和后1 个约束条件的二次优化问题，计算复 杂度高，训练速度慢，但其优点是支持向量的数目较少。 3 2 2o n e - v e r s u s - r e s ts v m ( 简称o v rs 讧) 方法 o v r s v m 方法最初由v l a d i l l l i r v a p n i k 出1 2 6 1 1 2 7 1 ，这是比较常用的一种多类分 类支持向量机算法，对后类分类问题，它需要构造后个分类器每个分类器的构造 都要使用全部的训练样本，构造第个分类器时，把第类的训练样本当成是正 类，其余训练样本当成是负类，然后通过求解以下最优化问题得到分类器的参数： 约束条件为： 叻刘1 1 1 2 + 1 善 ( + ) l 一影 ( 3 - 5 ) ( 3 - 6 ) 其中，= ( 3 7 ) 每检验一个样本，都必须使用全部k 个分类器最理想的情况下，是k 个分类 函数中只出现一个+ 1 ，其余的都是一1 但是由于误差的存在，如果直接这样使用就 可能出现以下问题：( 1 ) = ( 曲，= l ，2 ，后中出现多个+ l ，即此样本属于多个 类：( 2 ) = ( 力，= l ，2 ，后中全部为一1 ，即此样本不属于任何类为了修正这一问 题，选取( 力= a r g m 。；，s a x ， w z + ) 作为判别函数即使如此，仍然可能出现两个 1 7 中山大学硕士学位论文 石+ 相等或相差很小的情况，这样做出的判决结果是难以让人信服的对此， 可以引入一个适当的阈值0 ，把两个最大的z + 之差是否大于p 作为分类的 依据：只有差大于日的才做分类，否则拒绝分类 o v rs v m 方法的另一个明显的缺点就是训练样本中正类和负类的数目相差 较大，对模型的精度有一定的影响。 3 2 3o n e - v e r s u s - o n e s v m ( 简称o v os v m ) o v os v m 万法在训练集中每两类之i 司都构造一个分类器，对于后类分类问 题，要构造塑冬尘个分类器每个分类器的训练只需要用到两类样本对于类e 和e ，构造分类器需要求解以下最优化问题啪3 ： m i n 三zl l 圳2 + 匹t = - i 考夕( 3 - 8 ) 约束条件： 形( + ) i 一髻夕 ( 3 - 9 ) 其中，彤= 二。多耄三孑， 0 为 常数参数，用于调节超球的刘、和训练样本分类错误率，通常会取为g = 老， 其中以是第m 类的训练样本数。由拉格朗日理论，可以得到上述问题的对偶问 题为： m 。a x a ， 一a , a ) ( 3 一1 4 ) f ，1 1 2 m ，j f 2 mf ) 4 j 。m 约束条件为： 口，- - 1 ，o 0 当k 个超球面彳的半径和球心确定后，定义好距离函数攻，) 我们就 可以对样本点x 进行分类，决策函数为： ( 力= a r g m i n 放五影)( 3 - 1 7 ) ， 孤立超球面支持向量机方法的优点就是效率很高，因为求解每个超球面只需 要训练一类样本，训练速度很快，但是由于没有利用到其他类训练样本的信息， 导致它的精度受影响，准确率通常不能达到很高。 中山大学硕士学位论文 3 3 2m s v d d 帅m g 方法 m s v d d - n e g 3 7 】【3 8 】( s u p p o r t v e c t o rd o m a md e s c r i p t i o nw i t h n e g a t i v e e x a m p l e sf o rm u l t i c l a s sp r o b l e m ) 异于孤立超球面多类分类支持向量机方法的地 方是，它考虑全部训练样本，把一类当成正类，其余类当成负类。对于k 类分类 问题，训练的目的就是对于每一类样本，求得一个超球面，尽量的包围此类的所 有样本，同时也尽量不包围其他类的样本，还要求超球面的尽可能小。用数学模 型可以如下描述： 约束条件为： r a i n o 露+ 磊磬+ 麦丕劲 仔 i i9 i ( ) 一l i s 0 为常数，用于 调节超球面的大小和分类错误率。由拉格朗日最优化理论，司以得到上述问题的 对偶问题： m 。a x 口，敏，) 一a k ( x ，乃) 一 a p 艘，) 、 yii霸|。产mi 。净t j 严m 【玉2 3 ) + 2 a p 厥而劫一a , a f 擞而劫) 、7 约束条件为： a i 一a = l ， ，一1 2 m | ：y | 亭m 眶哪磊w 肛形一， ( 3 - 2 4 ) ( 3 2 5 ) 中山大学硕士学位论文 o 0 和3 3 1 中类似的方法，可以得到决策函数： ( 力= a r g r a i n 敌五影) ( 3 2 9 ) m s v d d 心范g 方法相比孤立超球面多类分类支持向量机方法，融入了负类 的信息，使精度得到了提高，但是由于每个超球面的求解都需要使用全部的训练 样本，训练速度比孤立超球面支持向量机方法要慢。 3 3 3 最大间隔超球面多类分类支持向量机( m s m s ) 在标准的支持向量机方法中，其中最关键的一个步骤就是求出最大间隔分类 超平面，追求最大间隔目的就是减小误差上界。而在3 3 1 和3 3 2 的超球面支持向 量机方法中，并没有考虑到间隔。j g w a n g 等人在文献 3 8 1 q b 首先将间隔引入到 超球面支持向量机中，提出p t t e mc l a s s i f i c a t i o nv i as i n g l es p h e r e s ( 以下简称 p c v s s ) 方法对于一个二类分类问题，求出一个超球面夕，距离正类和负类的距 离都是，并且使得分离比率妄写最大，简单的推导可将最大化妄写的问题 转化为最小化启一，其中石l 是调节超球面半径和分离比率的参数，用数 学模型描述如下 3 9 1 ： 删n 一) ( 3 - 3 0 ) c 。a 0 、 约束条件为： 堂评一 ) ( 3 - 3 1 ) v ，= l ，2 ，刀 中山大学硕士学位论文 由拉格朗日优化理论得到上述问题的对偶问题： 约束条件为： 啷荟口朋 。3 2 ) 一一 口，= 墨口= l ， 口0 ， i = 1 ，2 ，刀 求解上述问题，得到倪，就能求出半径和球心， f = 口脶， 月l 詹：型m i n i ix , - c l l f 2 + m a x i _ ( 3 3 3 ) ( 3 3 4 ) ( 3 - 3 5 ) ( 3 - 3 6 ) 从而便可构造决策函数进行分类。 受到p c v s s 方法的启发，p e i y ih a o 等人提出一种基于最大间隔思想的多类 超球面支持向量机，m s m - s v m 3 9 1 ( t h em a x i m a l - m a r g i ns p h e r i c a l s t r u c t u r e d m u l t i c l a s ss u p p o r tv e c t o rm a c h i n e ) 。可以用数学模型描述如下： m 聪i n 露一磁+ 导z y , = m 针磊毳射 ( 3 - 3 7 ) 约束条件为： 0 妒( ) 一a m1 1 2 + 考， ( 3 3 8 ) 孝，0 ，v i s t y ，= 朋， ( 3 - 3 9 ) 0 ( 而) 一0 2 露+ 磋一邑， ( 3 - 4 0 ) 考，0 ，v l s t y ，m ( 3 - 4 1 ) 其中，= 虿i 万一尼就是正负类样本之间的间隔，肜 o 是调节间隔和超球面大 小的常数参数，f o 用于控制分类误差的大小由拉格朗日最优化理论，可以求 得上述问题的对偶问题： 中山大学硕士学位论文 m 。a x 口，叙，五) 一口，取乃，乃) 一口放，t ) = 敏乃劫) ( 3 _ 4 2 ) + 2 ，傲而劫一口。敏乃劫) 卜一7 a ，= l + 必口，= 肜，o 4 o i 。 眍邴麦v ，础彤一 眍口，麦w 肚乃绷 由对偶问题求出口，进而求得第m 个超球面的半径和球心， = a 矽( 丐) 一口力( 乃) ， y ? = m y | m 尼= j i 驴( ) 一a n , | | 其中a o 定义好距离函数放，) ，便可得到决策函数： 3 4 本章小结 ( 力= a r g m i n 攻五墨) ， ( 3 - 4 3 ) ( 3 - 4 4 ) ( 3 - 4 5 ) ( 3 - 4 6 ) ( 3 - 4 7 ) ( 3 - 4 8 ) 本章主要介绍多类分类问题的支持向量方法，包括超平面支持向量机和超球 面支持向量机，并简单比较它们之间的异同和优缺点。超平面支持向量机在众多 文献中均有介绍，而对超球面支持向量机的介绍较少。本章介绍了比较典型的几 种超球面支持向量机方法，为在第四章中提出本论文的方法做铺垫。 中山大学硕士学位论文 第四章多类分类超球面支持向量机 4 1 多类分类超球面支持向量机的提出 现有的超球面多类分类支持向量机方法，如m s v d d - n e g ，p c v s s ， m s m s v m 等，与传统的超平面支持向量机方法的一点不同之处是，正负类样本 的地位不再是一样的。在超平面支持向量机中，正负类样本的地位是平等的，如 果直接把一类当作正类，其余类当作负类，必定会造成正负类样本数目的不平衡， 从而会影响到分类器的精度。而用超球面进行分类时，超球面内外的空间地位是 不平等的，对于处理正负类数目不平衡的情况，可能更为适合。但是目前超球面 支持向量机方法也有各种不足的地方，如m - s v d d n e g 方法就没有考虑到正负 类样本之间的间隔；p c v s s 方法采用最大化分离比率! 竺兰为目标函数，并不完 k d 全等价于最大化分类间隔；m s m s v m 方法也有类似的不足，同时追求疋和以 的最大，并不能保证分类间隔露+ 兹一兄的最大。 4 2 最大间隔同心超球面多类支持向量机( m m c m s 江) 分析了主要的超球面支持向量机方法的优缺点，并结合超平面支持向量机用 两个平行超平面分离正负类样本的特点，我们考虑直接用两个同心超球面来分离 正负类样本，正球面包围正类样本，而负球面外面是负类样本，负正球面半径之 差作为分类间隔。 4 2 1 模型的构造及求解 给定训练样本集 ( ，形) i ，= l ，2 ，砖，- k - 中y , l ，2 ，毋，用m m c h m - s v i v i ( m a x i m i z em a r g i nc o n c e n t r i ch y p e r s p h e r e sm u l t i c l a s ss v m ) 方法进行分类 中山大学硕士学位论文 时，当训练样本集中的各类不是超球面可分的时候，首先要将训练样本映射到特 征空间中，得到特征空间中的训练样本集为 ( 6 ( ) ，y j ) i ，= l ，2 ，刀) 对于第m 类， 任务是在特征空间中找到两个同心超球面和，分别称作正负超球面，它 们共同的球心是，半径分别是和靠，使得_ 尽量包围正类样本，墨尽 量不让负类样本进入，且间隔鲰一如尽可能大。理想的情况下，戤一稚 0 ， 但是m m c h m s v m 方法允许出现戤一稚 1 通常可以取q ：三，乞= 上，其中，分别是第m 类和非第m n 帏魏” 类的训练样本数目。由上述优化问题，我们可以得到广义拉格朗日函数： d r m ，r m 一，毛，r , o m ，q ，f ) ，a ，白、= 岛曩i 一月i + q + 乞乃+ q 1 | 玖) 一0 2 一露+ 一卜屏一 4 【j | 烈) 一0 2 一扉+ 纺】一哆乃 ( 4 - 4 ) j ：y j # m f y 严“ 其中， 口= ( ，气，) ，= ( 儡，履，) ，f = ( 毛，磊，炙) ， 彳= ( 以，以，) ，刀= ( 包，色，) ，矽2 ( ，) 由k k t 条件有： 老= 2 c o r + - 2 一q _ o ，( 4 - 5 ) 薏一2 易。+ 2 磊衫耻。， ( 4 - 6 ) 石o l ：q 一( 4 - 7 ) - a , , - f l , = o , 瓦2 q 瓦o l = 乞一衫一哆= 。，( 4 - 8 ) 老一2 暑q 训+ 2 暑删矿咖。，( 4 - 9 ) q 0 故) 一1 1 2 一最一】= o ， ( 4 1 0 ) 4 | | 烈t ) 一1 1 2 一+ 乃】= 0 ( 4 一1 1 ) 其中，满足乃= 彬，满足乃彬由于q ，屏，4 ，乃均是非负实数，所以，由 似5 1 r 4 9 ) ，可以推得： 哆= 岛， f y 产m ( 4 - 1 2 ) 中山大学硕士学位论文 4 = 1 ， f y j t m 0 q q ， 0 4 岛， 2 击【三q 一盖形】 将( 4 7 ) ，( 4 - 8 ) ，( 4 - 1 2 ) ，( 4 - 1 3 ) 代入l 中，得： ( 4 1 3 ) ( 4 - 1 4 ) ( 4 - 1 5 ) ( 4 - 1 6 ) z = q 【i i 改) 一1 1 2 一4 1 i 烈t ) 一| 1 2 ( 4 1 7 ) y | 2 m 妻y 产m 令7 - - ( ，7 2 ，) ，其中， 则 代入l 中得： f 口， 以2 “， 移yl = m 矿! | m ：士壹乃烈n 2 再备乃烈) z = 却一菇讹川 似) 认) 一古乃能) 烈一) t = - i o o 一- 1 = 1j = l ( 4 一1 8 ) ( 4 - 1 9 ) ( 4 2 0 ) 由此，z 。，1 j 原问题的对偶问题是o 哮告壹i = i 妻= i 乃讹) 她) 一喜缎珈虢) ) ( 4 2 1 ) 约束条件为： 0 乃qv 工正y ，= 历， 一乞乃0 比珐y 肋， 乃- - - - e o ， ，y # - - m 3 l ( 4 2 2 ) ( 4 - 2 3 ) ( 4 2 4 ) 中山大学硕士学位论文 乃= 一1 f y j t m ( 4 - 2 5 ) 引进核函数敢，哆) = ( 玖五) ，玖芍) ) ，并且记乃= 联，哆) ，眉= ( 乃) 。则上 述优化问题可以写成矩阵形式为： 叩 击俩一相 ( 4 - 2 6 ) 约束条件为： b 7 u b ，( 4 2 7 ) 研= m 件2 8 ， 其中， 彳= ( 乃2 x a i j - - 【0 ，1 , z ) 矿 y y j = m 历，吃= 【0 1 ，, 矿f ”y j = 所m ， ( 4 2 9 ) 彦= ( 局l ，乞2 ，) ， ( 4 - 3 0 ) 场= ( - 4 q l ，一c 2 a i 2 ，一c 2 q 。厂， ( 4 3 1 ) u b =