（运筹学与控制论专业论文）基于支持向量机的多分类算法研究.pdf

摘要 支持向量机最初于2 0 世纪9 0 年代v a p n i k 提出，是一种新的统计学习算法，其学习原 则是使结构风险最小化，这使得支持向量机具有很强的泛化能力近年来，支持向量机 在理论研究和算法实现都取得了突破性进展，是数据挖掘中的一项新技术，开始成为克 。维数灾难”和“过学习”等传统困难的有力手段。 核函数的核心内容是：对于输入空间中非线性可分问题，选择一个适当的映射，将输 入空间中的样本点映射到一个高维特征空间，使得对应的样本点在该空间线性可分，在 求解决策函数的过程中的计算仍在原空间进行，大大降低了在映射后的高维特征空问计 算的复杂性。 由于实际问题的复杂性，很多实际问题所采集的数据指标太多，再使用核函数，使得 维数进一步扩大，进而使得计算量过于庞大。对实际问题的解决带来了困难。此外，绝大 多数讨论仅局限于用s 、，m 解决两类问题。然而，即使我们能够将两类问题正确分类，也 并不意味着实际应用中多类分类问题的解决 本文首先从支持向量机的理论入手，介绍核函数的性质，以及根据序列极小化方法 的基本思想建立的特征选择的方法，从而提高支持向量机在分类问题中的应用能力。对 于多类分类问题，我们首先对基于支持向量机的几种多类分类方法的性能进行研究和比 较，并就基于模糊支持向量机的多类分类问题中可能出现的盲区提出了解决办法，对于 一对多类分类方法中经常出现的样本不均衡问题提出一个可行的解决方法，这些改进对 高维多类分类问题具有很强的实践价值。最后通过多类字母图象分类问题说明支持向量 机算法在多类分类问题中的应用 关键词：支持向量机；核函数；特征选择；盲区；样本不均衡；字母图像 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 e ( s v m ) i sa n e ws t a t i s t i c a ll e a r n i n gm e t h o dw h i c h p r o p o s e d b yv a p n i k t h el e a r n i n gp r i n c i p l eo fs v mi st om i n i m i z et h e8 t r u c t l l r a lr i s k w h i c h g i v e ss v mb e t t e rg e n e r a l i z a t i o n g r e a rp r o g r e s sh a sb e e nm a d ei nt h e o r e t i c a ls t u d ya n d a l g o r i t h m i cr e a l i z a t i o no f s v mr e c e n t l y , w h i c hh a sb e c o m ea n e wt e c h n i q u eo f d a t am i n i n g t oo v e r c o m et r a d i t i o n a ld i f f i c u l t i e s ，s u c ha sd i m e n s i o nd i s a s t e ro ro v e r - f i t t i n g ，e t c t h ew a ys 、，ms o l v e st h eu o n - l i n e s e p a r a b l ep r o b l e mi st h a t ：am a pi m p h e d l y d e f i n e db yk e r n e lf u n c t i o ni su s e dt ot r a n s f e rt h es a m p l e si nt h eo r i g i n a lf e a t u r es p a c ei n t oa h 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 t h e r e f o r e ，t h en o n - f i n e a rs e p a r a b l ep r o b l e mb e c o m e sa l i n e a rs e p a r a b l eo n e i nt h ec a u r s eo fs o l v i n gd e c i s i o n - m a k i n gf u n c t i o n t h ec o m p u t a t i o n c 姐h ec o n d u c t e di nt h eo r i g i n a lf e a t u r es p a c e t h u sg r e a t l yd e c r e a s i n gc o m p u t a t i o n a l c o m p l e x i t yi 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 f o rp r a c t i c a lp r o b l e m s ，t h e r ea r et o om a n yd a t ai n d e x e s ，a n db e s i d e st h a t ，t h e m e t h o do fk e r n e lf u n c t i o na d o p t e da l w a y sm a g n i f i e st h ed i m e u s i o u so ft h ef e a t u r es p a c e a l lt h e s eb e l o wc o s tt o om u c hc o m p u t a t i o n ，a n db r i n ga b o u tm u c hd i f f i c u l t y w eo f - t 朗s t u d yt w o - c l a s sc l a s s i f i c a t i o np r o b l e m b u ti td o e s n tm e a nw ec a nf i n das o l u t i o nt o c l a s s i f y i n gm u l t i - c l a s sc l a s s i f i c a t i o np r o b l e m e v e ni fw ec 衄c l a s s i f yt w oc l a a s e gc o r r e c t l y t h i sp a p e rd i s c u s s e ds u p p o r tv e c t o rm a c h i n et h e o r ya n dk e r n e lf u n c t i o n sp r o p e r t y i ta l s oc o n s i d e r sf e a t u r es e l e c t i o nm e t h o db a s e do nt h es e q u e n t i a lm i n i m i z a t i o nt e c h n i q u e a sa r e s u l t ，i tc a ni m p r o v es v m 印p l i c a t i o na b i l i t yi nc l a s s i f i c a t i o np r o b l e m f i r s t l y , t h i s p a p e rs t u d i e sa n dc o m p a r e st h ep e r f o r m a n c eo fs e v e r a lm u l t i - c l a s sc l a s s i f i c a t i o nm e t h o d s b a s e do ns u p p o r tv e c t o rm a c h i n et h e o r y s e c o n d l y , i ts u g g e s t sa p r a c t i c a lm e t h o dt o s o l v ef a d ea r e ap r o b l e mi nt h em u l t i - c l a s sc l a s s i f i c a t i o np r o b l e mw h i c hu 瞄f a d es u p p o r t v e c t o rm a c h i n em e t h o d 嘶d l y , i tg i v e saf e a s i b l em e t h o dt os e t t l es a m p l eu n b a l a n c e d p r o b l e mw h i c ho f t e na p p e a r si no n et om a n ym u l t i - c l a s sc l a s s i f i c a t i o nm e t h o d a l lt h e s e i m p r o v e m e n t sh a v ee x c e l l e n tp r a c t i c a lv a l u ei ns o l v i n gm u l t i - c l a s sc l a s s i f i c a t i o np r o b l e m l a s t l y , t h i sp a p e ri l l u s t r a t e st h ea p p l i c a t i o no fs v ma r i t h m e t i ci nm u l t i d a s sc l a s s i f i c a t i o n p r o b l e mb yc l a s s i f y i n gm u l t i - c l a s sl e t t e ri m a g e sr e c o g n i t i o np r o b l e m k e yw o r d s ：s u p p o r tv e c t o rm a c h i n e ( s v m ) ；k e r n e lf u n c t i o n ；f e a t u r es e l e c t i o n ；f a d e a r e a ；s a m p l eu n b a l a n c e d ；l e t t e ri m a g e s i i 学位论文独创性声明 本人所呈交的学位论文是我在导师的指导下进行的研究工作及取得的研究成果。据 我所知，除文中已经注明引用的内容外，本论文不包含其他个人已经发表或撰写过的研 究成果。对本文的研究做出重要贡献的个人和集体，均己在文中作了明确说明并表示谢 意 作者签名： 吼雌 学位论文授权使用声明 本人完全了解华东师范大学有关保留，使用学位论文的规定，学校有权保留学位论 文并向国家主管部门或其指定机构送交论文的电子版和纸质版有权将学位论文用于非 赢利目的的少量复制并允许论文进入学校图书馆被查阅。有权将学位论文的内容编入有 关数据库进行检索。有权将学位论文的标题和摘要汇编出版。保密的学位论文在解密后 适用本规定 学位论文作者签名：垒i k 龙 聃：卅 导师躲邋扎 日期：圆：厶7 引言 近年来，由于计算机和信息技术的快速发展，人们可以收集、存储海量的数据如 何。去粗取精”。从中提炼有用的信息，已经成为一个迫切需要解决的问题。数据挖掘技 术在这种背景下应运而生基于数据的机器学习是现代智能技术中十分重要的一个方面， 主要研究如何从一些观测数据( 样本) 出发得到目前尚不能通过原理分析得到的规律，利 用这些规律对未来数据或无法观测的数据进行预测。现实世界中存在大量我们尚无法准 确认识但却可以进行观测的事物，因此这种机器学习在从现代科学、技术到社会、经济 等各领域都有着十分重要的应用。当我们把研究的规律抽象成分类关系时，这种机器学 习问题就是模式识别 数据挖掘( d a t am i n i n g 简称d m ) 一词首次出现在1 9 8 9 年8 月举行的第1 l 届国际联合人 工智能学术会议上。迄今为止，由美国人工智能协会主办的d m 国际研讨会己经成功召开 了7 次，规模由原来的专题讨论会发展到今天的国际学术大会，研究重点也逐渐从发现方 法转向系统应用，并且注重多种学科之间的相互渗透。其它内容的专题会议也常把数据 挖掘列为议题之一，成为当前计算机科学界的一大热点经过十几年的研究和实践，数 据挖掘技术已经吸收了许多学科的最新研究成果而形成独具特色的研究分支。数据挖掘 的概念从二十世纪八十年代被提出后，其经济价值已经显现出来数据挖掘之所以吸引 专家学者的研究兴趣和引起商业厂家的广泛关注，主要在于大型数据库系统的广泛使用 和把数据转换成有用知识的迫切需要。从目前的现状看，数据挖掘的研究仍然处于广泛 研究和探索阶段。一批具有挑战性和前瞻性的问题被提出，吸引越来越多的研究者。 数学规划是运筹学一个重要分支，在机器学习、网络问题与经济学、工程机械学等 领域有着广泛而重要的应用，是国际上最活跃的运筹学研究领域之一现在，数学规划 得到极大的发展，和其他学科结合形成新的研究领域，并不断在新的领域找到应用。数 学规划在特征提取、聚类和回归等方面有很重要的应用，而这些都是数据挖掘待解决的 问题f 1 2 】从数值的角度说，数学规划方法，尤其是线性和二次规划方法是可靠的、有效 的，它们在过去的几十年中得到极大的提高。但是这些适应性很强的算法对于特定的问 题却表现出很多缺陷，如时间和空间复杂度高。对于特定问题，需要使用具有针对性的 算法，以提高运算的速度和准确率。数学规划和数据挖掘技术的结合已使挖掘领域的一 个重要大规模和高复杂性的问题的解决成为可能。 支持向量机是数学规划理论在数据应用。支持向量机理论f 3 6 】是v a p n i k 等人根据统 计学习理论提出的一种新的机器学习方法，其本质是数学规划中的凸二次规划问题【7 】。 如何准确、快速求解凸二次规划是支持向量机研究的基本问题，而这一问题的解决与数 学规划中的优化理论密切相关。在数学规划中，凸二次规划问题所求的局部最优解就是 全局最优解，这使得支持向量机具有很强的泛化能力。本文介绍了支持向量机与近似支 持向量机的学习算法。 特征提取指的是意识到存在无关而多余的特征并要剔除它们，同时对两个集合进行 区分现存模型在区分高维数据时需要的时间和空间代价很高，因此需要对有用的特征 进行提取。原来在支持向量机理论的应用实践中。主要采用序列极小化算法，但该算法在 有些实际问题中( 特别是样本特征比较多的情况) ，达不到很好的降维效果，往往经过该 算法执行后，只是剔除了样本的极少数特征，对复杂的实际问题的解决往往没什么帮助， 而且该算法对于高维问题的特征选择是相当耗时。但由于实际问题的复杂性，很多实际 问题所采集的数据指标太多，再使用核函数，使得维数进一步扩大，进而使得计算量过于 庞大，对实际问题的解决带来了困难。 在支持向量机的理论研究中，绝大多数研究讨论仅局限于用s 、w 解决两分类问题。 然而，两类分类问题的解决并不意味着多类分类问题的解决对于多类分类问题，尤其 在使用一对多的分类方法时，余类训练样本集过于庞大，如何处理这种样本不均衡问题， 往往束缚着我们对很多实际问题的解决另一方面，一对多方法在实践应用中存在分类 盲区从而大大限制了支持向量机的应用范围我们提出基本训练样本集和训练样本集 两个层次的概念，通过不断调节基本训练样本集，求得对训练样本集的最优决策函数，符 合结构风险最小原则，创造地解决了样本不均衡问题。对于盲区问题，有一种解决思想 是由日本学者t a k u g a 与s h i g e o 提t l t 的 8 - 9 1 ，但这种方法并不能保证各个多类分类器分类 结果的一致性，本文提出最小归属度支持向量机方法或平均归属度支持向量机方法，通 过对测试样本分两步测试，拒绝多类分类中盲区，从而提高这种多类分类机的性能。经 过这两方面改进的一对多方法对高维多类分类问题具有很强的实践价值。 本文简单介绍了支持向量机理论和核函数的性质，主要致力于基于支持向量机的多 类分类方法性能的研究，特别是一对多组合分类方法中的样本不均衡问题和基于模糊支 持向量机多类分类法中的盲区问题的研究与实践 本文通过模型表示，模型评价和算法的具体实施，将数学规划，尤其是优化技术应 用于数据挖掘，提高了数据挖掘的效率、速度和可靠性，使得数据挖掘技术能够更好的 适合现实世界处理数据的需要，这是本文的主要目的。故本文的研究内容有极大的社会 效益和经济效益。作者希望从理论上提供特征选择、分类等重要的数据挖掘模型和算法， 并将其应用于实践，同时运用计算机编程的知识对其进行验证，为研究提供可靠的实践 依据。 本文的意义在于：改进数据挖掘中一些数学模型和算法，提高了它们对现实数据的 适应性，尝试将这些改进后的数学模型和算法应用于实践，拓宽了支持向量机的使用范 围。 2 第一章支持向量机理论基础 1 1 统计学习理论简介 支持向量机学习方法研究是本文的主要工作之一，它借助于最优化方法解决机器学 习问题。是数据挖掘的一项新技术，它建立在统计学习理论基础之上，因此这里首先对 统计学习理论作简单介绍。统计学习理论就是研究小样本统计估计1 1 0 1 和预测的最佳理 论 1 1 1 ，它从理论上较系统地研究了经验风险最小化原则成立的条件、有限样本下经验风 险与期望风险的关系及如何利用这些理论找到新的学习原则和方法等问题其中，最具 有指导性的结果是推广性的界，与此相关的一个核心概念是v c 维( v a p n i k - c h e r v o n e n k i s d i m e n s i o u ) 1 1 1函数集的学习性能与v c 维 为研究函数集在经验风险最小化原则下的学习一致性问题，统计学习理论定义了一 系列有关函数集学习性能的指标，其中最重要的是v c 维( v a p n i k o c h e r v o n e l l k i 8d h n e n - s i o n ) 设有一个指示函数集( x ，u ) 和一组价训练样本的样本集磊= 名= ，砧，i = 1 ，2 ，竹。考虑函数集的分散性，看函数集中的函数能对这组样本实现多少种不同的分 类，记这个数目为( 磊) 定义1 1 ( 随机熵) ：定义指示函数集对某个样本集能实现的不同分类组合数目的对数 为函数集在这个样本集上的随机熵，记作日( 磊) ，即日( 磊) = l n ( 磊) 。 定义1 2 ( 生长函数) ：函数集的生长函数定义为它是在所有可能的样本集上的最大随 机熵，即g ( 磊) = m a x h n ( 磊) 通过研究v 如i l i k 和c h e r v o n e n k i s 在1 9 6 8 年发现了下面的规律【1 2 】 定理1 1 ：所有函数集的生长函数或者与样本数成正比，即g 。；n l n 2 ( a ) 或者以下列 样本数的某个对数函数为上界，即g _ h ( 1 n 罢) ( b ) ，n 危其中h 是一整数，n 为样本数，它 是生长函数满足式( a ) 到满足式( b ) 的转折点，即当n = h ，有c ( h ) = h l n 2 而g ( h + 1 ) ( h + 1 ) n 2 生长函数的这种性质，如图1 1 所示； 图1 1 生长函数的性质 3 1 ) 第一章：支持向量机理论基础华东师范大学硕士论文4 v c 维对于一个指示函数集，如果其生长函数是线性的，则它的v c 维为无穷大；而如 果生长函数以参数h 的对数函数为上界，则函数集的v c 维是有限的且等于h 显然，经 验风险最小化学习过程一致的充分必要条件就是函数集的v c 维有限，且这时的收敛速度 是快的。 模式识别中v c 维的等价直观定义【1 3 l 是：假如存在一个有h 个样本的样本集能够被 一个函数集中的函数按照所有可能的2 “种形式分开，则称函数集能够把样本数为h 的样 本集打散( s h a t t e r i n g ) 指示函数集的v c 维就是用这个函数集中的函数所能打散的最大样 本集的样本数日。换句话说，如果存在h 个样本的样本集能够被函数集打散，而不存在 有h - i - 1 个样本集能够被函数集打散，则函数集的v c 维就是h 如果对于任意的样本数， 总能找到一个样本集能够被这个函数集打散，则这个函数集的v c 维就是无穷大。一般实 值函数集的v c 维可以通过一个域值把实值函数转化为指示函数来定义【1 4 】 v c 维是统计学习理论的一个核心概念，它是目前为止对函数集学习性能的最好描 述指标。目前还没有通用的关于如何计算任意函数集的v c 维理论。只有对一些特殊的函 数集的v c 维可以准确知道。如在扎维实空间中线性分类器和实值线性函数的v c 维是- t - l ，f ( x ，a ) = s i n ( a x ) 的v c 维为无穷大，用它实现的分类器的v c 维也是无穷大对于给定 的学习函数集，如何用理论或实验的方法计算它的v c 维仍是统计学习理论中有待解决的 问题 1 1 2 推广性的界 基于统计的学习方法大多建立在经验风险最小化原则( p r i n c i p l eo fe m p i r i c a lr i s k m i n i m i z a t i o n ) 基础上，其思想是利用经验风险也m p ( 口) 来代替期望风险r ( a ) ，用使冠。，( n ) 最小的，( z ，啦) 来近似使r ( o ) 最小的f ( x ，咖) 这类方法有一个非常基本的假设，即如 果忽，( n ) 收敛于r ( a ) ，那么忍。，( o ) 的展小值将收敛于r ( 口) 的最小值。v a p n i k - - 与c h e r v - o n e n 妯l 【1 2 】证明，该假设成立的充要条件是函数族f = ，( z ，口) ，a 人，的v c 维为有限 值。v a p 舳i 证明，期望风险r ( a ) 满足一个上界，即任取町满足0 o ) ， ( 1 9 ) i = l 注：它的解中只有一部分啦是非零的，对应的样本是支持向量。因此得到的最优分类函 数是： l ，( z ) = 8 9 n ( ( u z ) + 6 ) = 8 9 n ( ：西玑( 而功+ 6 ) ， ( 1 1 0 ) 1 = 1 上式中的求和实际上是对支持向量进行的，b + 实际上是分类阀值，它的值可以由任一个 支持向量求得。对于给定的未知样本，只需计算，( z ) 即可判断z 的归属。所以将这个最 大间隔法转换而来的等价方法称为线性可分支持向量机，又称为线性硬间隔分类机，是 解决线性可分问题的常用方法。 通过比较( 1 4 ) 与( 1 7 ) 可以发现，二次规划问题的w o 对偶问题的约束远远比原始问 题的约束简单。而且利用w o l f e 对偶问题，使样本在新问题中仅以向量内积的形式出现。 正是这一重要特点，使支持向量机法推广到非线性情况。 第一章：支持向量机理论基础华东师范大学硕士论文9 现在讨论线性不可分问题，如果继续坚持使用超平面进行分划，那么必须“软化”对 间隔的要求，即允许有不满足原始问题( 1 - 5 ) 中的约束条件玑( 甄) + 砷1 的样本点存 在。通过引入非负的松弛变量6 ，i = 1 ，z ，把约束条件放松为 犰( ( u 而+ b ) + 6 ) 1 ，6 ，i = 1 ，f ，( 1 一1 1 ) 显然，当矗充分大时，样本点，玑) 总可以满足( 1 1 1 ) 的约束条件向量f = ( 6 ，自) r 体 现了允许训练集被错划的情况，而由f 可以构造出描述训练集被错划的程度。例如：可以 采用名l 矗作为一种度量。现在有两个目标：仍希望间隔2 川u 9 最大；同时希望被错划 程度乞，6 尽可能小为把这两个目标综合为一个目标可以引进一个惩罚参数g 作为综 合这两个目标函数的权重，即极小化新的目标函数： 豫扣1 2 + g 塞6 ， ( 1 1 2 ) = s t 挑( 戤+ b ) + ) 1 ，6 ，i 一1 ，j ， 与线性可分支持向量机中引入l a g r 粕g e 乘子一样，可以得到相应的l a 斟a n g e 方程，进而 转化为其w o l f e 对偶问题，即在约束条件： l 姚= 0 ，0 0 4 c , i = 1 ，z ：= 1 之下对啦求解下列函数的最小值： 癣睁酬 ( 1 1 3 ) 即可以得到线性软间隔分类机通过比较( 1 7 ) 与( 1 1 3 ) 可以发现，当参数e 一+ o o 时，线 性软问隔分类机( 1 1 3 ) 即可退化为线性硬间隔分类机( 1 7 ) 1 2 2 非线性支持向量机 1 2 1 研究了在输入空间存在线性分类面的情况，对输入空间不存在线性分类面的情 况【1 7 1 ，理论上可以通过某种变换映射到一个高维特征空间，在这个高维特征空问中可用 线性支持向量机来分类。但这种做法带来两个很现实的问题：一是怎样在这样一个高维 特征空间找到推广性很好的分类超平面? 二是如何处理高维空间中的计算呢? 定义变换妒( o ) ：舻一日，将输入空间的样本z 变换到高维( 可能是无穷维) 特征 空间( h i l b e r t 空间) 当在高维特征空间日中构造最优超平面时，训练算法仅使用内积， 即庐( z ) 庐( z ) ，而没有单独的西( z ) 出现。在1 2 1 线性支持向量机中，曾交代寻找最优分类 。一 一 巧 第一章：支持向量机理论基础华东师范大学硕士论文 1 0 面最终归结为其w o l f e 对偶问题，一个重要原因是找到了一个克服“维数灾难”，解决高 维空间中计算的绝好办法：如果数学上能够找到一个函数满足k ( z ，z ) = ( 西( z ) 妒( 一) ) ， 那么在w o l f e 对偶问题中，只需用k ( ，一) 代替( 咖( z ) 毋( ) ) ，计算就在原空间上进行，计 算量将会大大减少而确实也存在这样一些函数，我们称为核函数。关于核函数，我们将 在第二章中研究和探讨它的性质因此，我们只需在原空间中计算核函数，而不需要知 道变换的具体形式，也不需要在高维特征空问中计算。 非线性支持向量机也分为两种：非线性硬间隔分类机和非线性软间隔分类机。 非线性硬间隔分类机的最优化算法： 呼；喜妾玑协啦k c 而，巧，一妾 c - 一t 4 ， l 础 肌啦= o ，0 啦，江1 ，l i = l 非线性软间隔分类机的最优化算法： 呼：妻妾玑玢啦q k c 以，一妾q c t t s ， l “ 玑啦= 0 ，0 s 啦ai = l ，i = l 1 2 3 支持向量分类机 根据是否引入核函数k ( 卫，一) 和是否引入惩罚参数g ，可将支持向量分类机分为四 种 1 8 1 ，它们之间的关系如图1 4 所示： 线性软间隔 广分类机1 l 无k ，有g l 线性硬间隔ll 非线性软间隔 分类机_ 1r 分类机 无耳，无e i 非线性硬间隔i 有k ，有g l 一分类机j 有，无c 图1 4 支持向量分类机之间的关系 下面给出应用最广泛的非线性软间隔分类机的算法 算法1 2 ( 非线性软间隔分类机) ： 笪二皇：塞鲎宣量垫望堡茎型堡壅塑堇盔堂壅堡塞 1 1 ( 1 ) 已知训练集t = ( z l ，驰) ，( 观，饥) ( x y ) 。，其中鼢x = 曰，鼽y = - 1 ，1 ，i = 1 ，1 ； ( 2 ) 选取适当的核函数k ( x ，z ) 和合适的惩罚参数c ，构造并求解最优化问题： 哩n ；i = l j ：l 弘珊啦q k ( 矾，) 一j = x ( 1 - 1 6 ) 8 t 驰啦= 0 ，0 啦gi = 1 ，z ， 求得最优解矿= ( n ；，噶，西) r ； ( 3 ) 选取矿中的一个分量叼，满足o 噶 c ，椐此算出6 = 缈一：1 玑q ；k ，z a ； ( 4 ) 构造决策函数，0 ) = s 弘( ：l 田y t k ( x ，) + 6 ) 。 第二章核函数与特征选择 2 1 1 核函数理论 核函数的核心内容是：对于输入空间中非线性可分问题，选择一个适当的映射，将输 入空间中的样本点映射到一个高维特征空间，使得对应的样本点在该空间线性可分，而 且通过对核函数【1 9 ，2 0 】的深入研究，在求解决策函数的过程中的计算仍在原空间进行，大 大降低了在映射后的高维特征空间计算的复杂性。关于核函数可参阅【1 1 ，2 1 】 按照广义线性判别函数的思路，要解决一个非线性问题我们可以设法将它通过非线 性变换转化为另一个空间中的问题，在这个变换空间求最优或广义最优分类面。考虑到 最优分类面算法的性质，在这个变换空间中，我们只需进行内积运算。而进一步看，我们 甚至没有必要知道采用的非线性变换的形式，而只需要它的内积运算即可。只要变换空 间中的内积可以用空间中的变量直接计算得到( 通常是只样的) ，则即使变换空间的维数 增加很多，在其中求解最优分类面的问题并没有增加多少计算复杂度。 事实上，我们只要定义变换后的内积运算，而不必真的进行这种变换。统计学习理论 指出，根据h i l b e r t - s c h m i d t 理论，只要一种运算满足m e r c e r 2 2 条件，它就可以作为内积 使用 定义2 1 ( 核函数( 核或正定核) ) ：设x 是舻中的一个子集，称定义在x x 上的函 数耳( z ，一) 是核函数( 核或正定核) ，如果存在着从x 到某一个h i l b e r t 空间卸的映射 毋：x _ 日 写一咖( z ) ， 使得k ( 一) = ( 妒( z ) ( ) ) ，其中( ) 表示日中的内积。 当然，作为两个向量的内积，核函数首先应该满足内积所具有的性质： ( 2 一1 ) k ( x ，z ) = ( 曲( z ) 毋( 。) ) = ( ( 。) 妒( z ) ) = = k ( z ，。)( 2 2 ) k ( z ，z ) 2 = ( ( z ) ( 一) ) 2 - o 是7 k ( 定义积分算子政为按下式确定的在如( x ) 上的积分算子t k ( i ) = ( 2 k ，) ( ) = 厶k ( ，茹) ，( 一) ，v ，工2 ( x ) ) 的特征值，仇岛僻) 是对应凡的特征函 数( 0 妒ti l = 1 ) 它也等价于k ( 。，) 是一个核函数 其中 而( ) 是h n b e r t 空间上的内积 k ( z ，一) = ( 妒( 。) ( 。) ) 西：xc 彤- 如 z 一( o 。( z ) ，i 仰( z ) ，) t ，( 2 6 ) 2 1 2 核函数的一些基本性质 核函数的构造性质。一个对称函数是否是核函数关键是看它是否符合m e r c e r 定理的 条件，也就是看在样本空间的任意有限子集上，该函数对应的g r a m 矩阵是否半正定。根 据这个定理，可以构造出更多的核函数。下面给出一些核函数和核函数构造方面的性质： 引理2 1 ：设蚝和鲍是x x 上的核函数，x 舻，o 冗+ ，( ) 是x 上的一个实 值函数，：x j p ，配是j p 舻上的核函数，b 是佗x n 的半正定对称矩阵。则下 列函数都是核函数： 1 k 0 ，) = k t ( x ，) + k j 0 ，一) 2 k c x ，z ) = a k l ( x ，) 3 k ( x ，一) = k l ( x ，z ) k 2 c x ，一) 4 k 扛，, t j ) = ，扛) ，( 一) 5 k ( z ，一) = k s ( 妒( z ) ，咖( z ) ) 6 k ( x ，z ) = x t b x ( 2 7 ) ( 2 8 ) ( 2 9 ) ( 2 1 0 ) ( 2 1 1 ) ( 2 1 2 ) 由引理可以得到一些比较好的结论。 推论：设k 1 ( z ，) 是x y 上的核函数，z ，z x ，p ( ) 是正系数多项式，则下列函 数k ( z ，z ) 都是核函数： 整三至：壑重塾皇壁堑垫竖堡壅竖蕉盔堂塑堡塞 1 4 1 2 3 k ( z ) = p ( k d x ，, i t ) ) k ( x ，z ) = e x p ( h q ( x ，z ) ) k ( z ，z ) = 唧( 一悭z _ 广：t2 ) ( 2 一1 3 ) ( 2 一x 4 ) ( 2 1 5 ) 鼍2 1 3 一些常用典型核函数 分类问题的求解，依赖于对相似性和相似程度的评价而在支持向量机中是用内积 来评价的这些内积强列依赖于映射的选择或核函数的选择，选择不同的映射或核函数 就意味着对相似性和相似程度的不同估价标准下面，我们介绍几种常见的核函数。 1 g a u s s 径向基核 g a u s s 径向基核函数的形如： 脚，一) ：唧( 一学) ( 2 一x 6 ) 2 名r 项式核 多项式核函数形如： j f ( z ，, t t ) ；( p ) + c ) 4 ，c 0 ， ( 2 1 7 ) 其中d 为任意正整数当c 0 ，称它为非其次多项式核。当c = 0 时，即得到 耳0 ，z ) = 扛一) 4 ， 这类核函数称为齐次多项式核函数。 3 傅里叶核 常用的傅里叶核有两种，它们也都是由一维傅里叶核生成的。 第一种傅里叶核所对应的一维傅里叶核为： 虬( x ：x r ) = 2 ( 1 - 2 qc 上o s ( 竺x - x ) 一+ q 2 ) ， 其中口是满足0 口 0 ，t ， ：玑c k = 0 ，0 o q gi = 1 ，f ， i = 1 求得最优解矿= ( c t * ，口；，a ：) t 选取n 。中的一个分量o ；，满足o 2 ) 类分类问题和两类分类问题之间存在一定的对应的关系。如果一个多类分 类问题k 类可分，则这k 类中的任何两类一定可分；另一方面，在一个后类分类问题中，如 果已知其任意两类可分，则可以通过一定的组合方法最终实现k 类可分。由于经典的s v l ( 支持向量分类机) 基于两类分类问题，可以把它和二叉树思想结合起来构造多类别分类器， 这种多类分类器称为s v m 决策树方法。决策树方法需构造若干个s v 1 分类器，个数的确 定需要根据二叉树的性质：对任何一棵二叉树，如果其叶子节点个数为0 ，度为2 的节点 个数为2 ，则有n o = n 2 + 1 。最终构造的s v m 决策树中没有度为1 的节点，是一棵正则 二叉树。设对k 类样本集构造一棵二叉决策树，则树的每个叶节点对应一种类别，每个度 为2 的非叶节点对应一个子s v m 分类器。所以决策树共有2 k 一1 个节点，叶节点个数为k ， 子s v m 分类器的个数为k 一1 。 s v m 决策树方法有以下特点2 7 ，2 8 1 u：， “o l，、【 第三章：多类分类算法的研究 华东师范大学硕士论文 2 1 ( 1 ) 决策树具有层次结构，每个层次子s v m 的级别和重要性不同，其训练样本集的组 成也是不同的 ( 2 ) 测试是按照层次完成的，对某个输入样本，可能使用的子s v m 数目介于1 和决策 树的深度之间，测试速度快。 ( 3 ) 决策树的个节点和树叶的划分没有固定的理论指导，需要有一些先验知识 根据二叉树的定义，构造一棵有k 个叶子节点的严格二叉树有多种不同方案。例如： 对4 类分类问题，则有图示的三种二叉树结构： ( a ) ( b )( c ) 图3 。1s v m - - 叉决策树结构 对一个具体问题，选择s v m ：叉决策树方案时，二叉决策树结构选择可以依据以下 几点： ( 1 ) 若对k 类问题中各类基本无先验知识，无法指导树叶节点的划分，则可采用每次 决策分出一类的二叉决策树结构，如图3 1 ( a ) 所示结构 ( 2 ) 若对k 类问题中各类基本有一些相关先验知识，可以指导树叶节点的划分，则可 采用完全二叉决策树结构，如图3 1 ( b ) 所示结构 ( 3 ) 若对k 类问题中各类基本有充分的相关先验知识，可以指导树叶节点的划分，则 可采用结合二叉树理论，构造一棵测试速度最优的s v m - - 叉决策树，如图3 1 ( c ) 所示结 构 3 2 常见多类分类方法性能比较 3 2 1 算法复杂程度分析 多类分类器算法的复杂程度的分析需要从两个方面考虑：训练过程和测试过程。首 先分析算法在训练过程中的代价。有实验证明：两类分类问题中，训练时间与训练集合 的大小z 的r 次方成正比即： 正 w l 。= d ( 3 5 ) 第三章：多类分类算法的研究华东师范大学硕士论文 2 2 对于基于s v m 两类分类的多类分类算法，r = 2 ( 1 ) 一对一组合 为了简单说明问题，不妨假设所有各类都含有相同数量的样本，则一对一模式每次 训练的样本集合大小为2 t m ，其整个训练所花费的时间是： 删- - e t n e = c ! 尘乒( 豢) r = 2 r - 1 舻4 矿。( 3 - 6 ) ( 2 ) 一对多组合 一对多模式对整个训练集合建立m 个分类器，所以其整个训练时间是： t k a g a i n s t m w = c r n l ( 3 7 ) ( 3 ) 全局优化分类 全局优化分类算法将所有的样本都集中到一个优化目标函数中，算法复杂程度的核 心还是约束条件极值问题的解决全局优化算法的整个训练时问是： 马f 曲“一卿州棚溉= c r r ，r ( 3 8 ) ( 4 ) 决策树分类 假设决策树方法中，所有的决策节点都将所要处理的样本类别分成大小相同且互不 相交的两个子集。决策树的训练实践中还包括类别子集分离预定义所需要的时间，但与 聚类算法的代价相比。s v m 的训练时间要小的多，可忽略不计，则： t d t s v m - - - - d r ( 筹) ( 3 - 9 ) 根据上面所说r = 2 ，结合上述分析，不难看出，一对一组合和决策树分类所需要的 训练时间与类别数m 无关，大约是训练单个s v m 所需时间的两倍。这两种算法的训练代 价较小，而全局优化算法的训练代价最大。 再分析预测代价由核函数的计算次数决定的。一对一模式和一对多模式所需要的预 测时间与其所有的支持向量的个数成正比。一般情况下，全局优化的结果是支持向量数 大大减少，所以全局优化算法的优点就是预测快。决策树分类，其核函数的计算次数由 其决策路径上的支持向量总数决定。 3 2 2 多类分类错误率 对于两类支持向量分类机，其期望分类错误率有下面结论： 如果一个训练样本集能够被一个最优分类面或者一个广义最优超平面分开，则对于 测试样本集，分类错误率的期望的上界是训练样本集中平均的支持向量数s v 占总训练样 本的比例| 2 9 1 ，即 e ( p ( e r r ) ) 百e ( s v ) 。 ( 3 一l o ) 箜三茎：堑耋坌差差鲞堕堑窒堡壅塑堇盔堂塑堡塞 2 3 对于多类分类问题，上述结论依然成立。 3 2 3 多类分类方法性能比较的仿真实验 本文用于测试以上提出的各种多类分类方法的实验数据数据库来自u c i 数据库( w w w i c s u c i e d u 。m l e a r n d a t a b a s e s ) 。软件环境：m a t l a b w i n x p ，所选用核函数就是上文 介绍的g a u s s 径向基核函数。由于选用的数据集均未提供测试数据集，我们就将选择的 数据集随机的选取一大部分作为训练样本集，剩余的一部分作为测试样本集，来测试各 种多类分类方法的性能。 i r i s 数据集：共计1 5 0 4 - 样本，3 类，4 个特征( 关于类别，特征采集的详细介绍参见w w w i c s u c i e d u 一r e l e a r n d a t a b a s e s 的英文文档) 我们从每一类中随机选取3 0 个样本组成训练 样本集，每一类余下的2 0 4 样本组成测试样本集，为了便于比较，对每一种多类分类方 法，我们都采用g a u s s 径向基核函数，盯= 2 ，实验结果如下： 表3 1i r i s 数据集的试验结果 多类分类方法 错误率总支持向量数目 训练时间( s )平均核函数运算次数 一对一组合3 3 3 1 6 1 7 1 5 一对多组合3 3 3 1 94 31 2 全局优化3 3 3 1 11 01 1 决策树 3 3 3 1 321 1 w a v e f o r m 数据集：共计5 0 0 0 个样本，3