（概率论与数理统计专业论文）支持向量机多分类方法的研究及应用.pdf

重庆大学硕士学位论文中文摘要 摘要 支持向量机( s u p o r t v e c t o r m a c h i n e ，简称s v m ) 是一种基于统计学习理论的 新型机器学习方法，是借助于最优化方法解决机器学习问题的新工具。支持向量 机是机器学习领域若干标准技术的集大成者，它集成了最大间隔超平面、m e r c e r 核、凸二次规划、稀疏解和松弛变量等多项技术，在若干具有挑战性的应用中， 获得了非常好的效果。由于其具有全局最优、结构简单、推广能力强等优点，近 几年得到了广泛的研究并广泛应用于模式识别等领域。但是支持向量机方法最初 是针对两类别的分类提出的，如何将支持向量机方法扩展到多类别分类( 也称为 多分类) 问题是支持向量机研究的重要内容之一。 本文基于统计学习理论和支持向量机方法，针对多分类问题进行了深入研究。 主要研究工作如下： 支持向量机多分类算法的分析比较。全面总结了现有的基于支持向量机的 多分类方法，包括“一对多”、“一对一”方法、有向无环图方法、树型s v m 方法 等，给出了理论上的性能比较，推广能力的分析，时间复杂度比较；并通过实验 对其中几种常用的方法进行了验证与比较。 提出了一种基于支持向量数据描述算法的s v m 多分类新方法。对基于支持 向量数据描述算法的多分类方法进行了研究，分析了它的优缺点，并深入讨论了 其推广性能一般的原因。针对其存在的不可分区域这个缺陷，提出了一种新的多 分类方法( s m s v m ) ，该方法对每类样本建立一个超球来界定，由于训练好的超 球在多数情况下是相交的，选择相交区域的样本单独建立超球，重复该步骤，直 到相交区域消失或者相交区域内没有样本点或者超过迭代终止条件。然后对其进 行了时间复杂度分析，并通过在多组u c i 数据上的实验验证了其良好的推广能力。 将支持向量机多分类方法应用于孤立肺结节的医学诊断，实验结果表明 s v m 分类器对恶性结节的诊断效果优于其他方法。孤立肺结节的诊断对临床医生 及影像科医生而言是一个极大的挑战，除了其发生率高，孤立肺结节的诊断中精 确区别无结节、良性结节和恶性结节是非常困难的，所以研究一种有效的分类方 法以辅助医生诊断是非常重要的。本文将仿生模式识别、b p 神经网络和s v m 分 别应用于孤立肺结节的识别中，实验表明三种方法对无结节和良性结节的识别效 果相当，但s v 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 mf o rs h o a ) i san e wm a c h i n el e a r n i n gm e t h o db a s e d o ns t a t i s t i c a lle a r n i n gt h e o r y , a n di ti sa l s oan e wt o o ls o l v i n gt h em a c h i n el e a r n i n g p r o b l e m sb yo p t i m i z a t i o nm e t h o d s u p p o r tv e c t o rm a c h i n ei sav e r ys p e c i f i ca l g o r i t h m ， w h i c hi sc h a r a c t e r i z e db yt h eu s eo fam a x i m a lm a r g i nh y p e r - p l a n e ，t h et h e o r yo f k e r n e l s , c o n v e xo p t i m i z a t i o n ，t h es p a r s e n e s so ft h es o l u t i o n ，m e r c e r st h e o r e ma n dt h e c a p a c i t yc o n t r o lo b t a i n e db ya c t i n go nt h em a r g i n al a r g en u m b e ro fe x p e r i m e n t sh a v e s h o w nt h a ts u p p o r tv e c t o rm a c h i n eh a sn o to n l ys i m p l e rs t r u c t u r e ，b u ta l s o b e t t e r p e r f o r m a n c e ，e s p e c i a l l yi t 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 r e c e n t l ys v mi sb r o a d l y r e s e a r c h e da n da p p l i e di n p a t t e r nr e c o g n i t i o na r e a t h es u p p o r tv e c t o rm a c h i n e a p p r o a c hw a so r i g i n a l l yd e v e l o p e dt os o l v eb i n a r yc l a s s i f i c a t i o np r o b l e m s b u ti nm a n y f i e l d s ，w en e e dt os o l v 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 m s h o wt oe f f e c t i v e l ye x t e n d s v mf o rm u l t i - c l a s sc l a s s i f i c a t i o ni ss t i l la no n - g o i n gr e s e a r c hi s s u e t h i sp a p e rr e s e a r c h e sm u l t i c l a s sp r o b l e m sb a s e do ns t a t i s t i c a ll e a r n i n gt h e o r ya n d s v m c a r e f u l l y , t h em a i nw o r k so f t h i st h e s i sa r ea sf o l l o w s ： f i r s t ，m u l t i c l a s s c l a s s i f i c a t i o nm e t h o d sb a s e do ns v ma r e c o m p a r e da n d r e s e a r c h e d t h em 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 sa r es u m m a r i z e d i n c l u d i n g o n e v e r s u s - r e s t ，o n e - v e r s u s - o n e ，d a g , a n dd e c i s i o nt r e es v m ，a n ds oo n t h e i r a d v a n t a g e , d i s a d v a n t a g ea n dg e n e r a l i z a t i o nc a p a b i l i t ya r ec o m p a r e dw i t he a c ho t h e r m o r e o v e r , s e v e r a lm e t h o d sa r ev a l i d a t e da n dc o m p a r e db ye x p e r i m e n t s s e c o n d ，an e wm e t h o db a s e do ns u p p o r tv e c t o rd a t ad e s c r i p t i o ni sp r o p o s e di nt h i s p a p e r t h em 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 db a s e do ns u p p o r tv e c t o rd a t ad e s c r i p t i o ni s r e s e a r c h e d t h ea d v a n t a g ea n dd i s a d v a n t a g eo ft h i sm e t h o di sa n a l y z e d ，t h er e a s o ni s g i v e nt 0r e p l yw h y i t sg e n e r a l i z a t i o nc a p a b i l i t yi sn o ts og o o d t os o l v et h ep r o b l e mo f t h ee x i s t e n c eo fu n c l a s s i f i a b l er e g i o n s ，an e wm e t h o di s p r o p o s e d t h i sm e t h o d c o n s t i t u t e sah y p e r s p h e r i c a lc l a s s i f i e rf o rt h es a m p l eo fe a c hc l a s s b u tt h eh y p e r s p h e r e s w h i c hh a v eb e e nt r a i n e dw e l la r es h a r i n gac o m m o nr e g i o ni nm o s tc a s e t os o l v et h i s d i s a d v a n t a g e ，t h es a m p l ei ni n t e r s e c t i o nr e g i o ni sc h o s e nt ot r a i nh y p e r s p h e r e s r e p e a t t h i sp r o c e s su n t i li n t e r s e c t i o nr e g i o nd i s a p p e a r so rt h e r ei sn os a m p l ei ni n t e r s e c t i o n r e g i o no rs t o p p i n gc r i t e r i a i sr e a c h e d i t st i m ec o m p l e x i t yi s g i v e n a tl a s t ，g o o d g e n e r a l i z a t i o nc a p a b i l i t yo f t h ep r o p o s e dm e t h o di ss h o w nb ye x p e r i m e n t sm a d eo nu c i d a m s e l s n 重庆大学硕士学位论文英文摘要 t h i r d ，t h es v mm u l t a c l a s sm e t h o d sa b o v ea r eu s e dt od i a g n o s i ss o l i t a r y p u l m o n a r yn o d u l e s ( s p n sf o rs h o f t ) t h ee x p e r i m e n t a lr e s u r ss h o wt h a ts v m c l a s s i f i e r i so ft h eb e t t e rp e r f o r m a n c ei nm a l i g n a n ts p n sd i a g n o s i st h a nt h eo t h e rm e t h o d s t h e d i a g n o s i so fs p n si s a r te x t r e m ec h a l l e n g et oac l i n i c a lp h y s i c i a no fap h y s i c i a n s p e c i a l i z i n gi ni m a g i n g ，b e c a u s ei n c i d e n c er a t eo fl u n gd i s e a s ei sh i 曲，a n di ti sd i f f i c u l t t or e c o g n i z em a h g n a n ts p n s ，b e n i g ns p n so rn o ns p n si nt h ep i c t u r e sp r e c i s e l y s oi t i sc r u c i a lt od e s i g nac l a s s i f i e ra f t ：a l la i dt od i a g n o s i so fs p n s i nt h i sp a p e rb i o n i c p a t t e r nr e c o g n i t i o n , b pn e u r a ln e t w o r k sa n ds u p p o r tv e c t o rm a c h i n ea r ea p p l i e dt o d i a g n o s i so f s p n s t h ee x p e r i m e n tr e s u l t ss h o wt h a tt h et h r e ec l a s s i f i e r sa r eo f q u i t et h e s a m ep e r f o r m a n c ei nb e n i g ns p n sa n dn o ns p n sr e c o g n i t i o n ，b u ts v mc l a s s i f i e ri so f t h eb e t t e rp e r f o r m a n c ei nm a l i g n a n ts p n sd i a g n o s i s k e y w o r d s ：s t a t i s t i c a ll e a r n i n gt h e o r y , p a t t e r nc l a s s i f i c a t i o n ，s u p p o r tv e c t o rm a c h i n e , m u l t i e l a s sc l a s s i f i c a t i o np r o b l e m s ，s o l i t a r yp u l m o n a r yn o d u l e s 1 1 1 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重麽太堂 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：砾见1 疋签字日期：加。了 年6 月j 日 学位论文版权使用授权书 本学位论文作者完全了解重庆太堂有关保留、使用学位论文的 觇定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许 沦文被查阅和借阅。本人授权重鏖太堂可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 5 i 存、汇编学位论文。 保密() ，在年解密后适用本授权书。 本学位论文属于 不保密( 、) 。 ( 请只在上述一个括号内打“4 ”) 学位论文作者签名：苏腿 签字日期：劲_ 年b 月孓日 导师妣切椤尹 签字日期：之们僻多旷日 重庆大学硕士学位论文 1 绪论 1 绪论 1 1 选题背景和研究意义 随着信息技术和信息网络的飞速发展，信息产生和传播的速度迅速提高，政 府、商业、企业等机构每天都在产生并积累着大批量的数据。伴随海量数据而来 的问题是信息过载和信息污染，这极大地影响了人们对信息的有效利用，因此从 大量数据中发现有用知识的数据挖掘就成为一个十分迫切的富有挑战性的研究课 题。基于数据的机器学习是数据挖掘技术中的重要内容，它从观测数据出发寻找 规律，并利用这些规律对违例数据或无法观测的数据进行预测。现有机器学习方 法共同的重要理论基础之一是统计学。传统统计学研究的是样本数目趋于无穷大 时的渐进理论，但在实际问题中，样本数往往是有限的，因此一些理论上很优秀 的学习方法在实际中的表现却可能不尽人意。v a p n i k 等人从二十世纪六、七十年 代开始致力于统计学习理论的研列2 】，与传统统计学相比，统计学习理论( s t a t i s t i c a l l e a r n i n g t h e o r y , 简记为s l t ) 是种专门研究小样本情况下机器学习规律的理论。 随着其理论的不断发展和成熟，也由于神经网络等学习方法在理论上缺乏实质性 的进展，统计学习理论开始受到越来越广泛的重视。 统计学习理论建立在一套较坚实的理论基础之上，为解决有限样本学习问题提 供了一个统的框架。它能将很多方法纳入其中，有望帮助解决很多原来难以解 决的问题( 比如神经网络结构选择问题、局部极小点问题) ；同时，在这一理论基 础上发展了种新的通用的学习方法支持向量机( s u p p o av e c t o rm a c h i n e 简 记为s v m ) ，它已初步表现出很多优于已有方法的性能。 支持向量机是二十世纪九十年代中期在统计学习理论基础上发展起来的一种 新型机器学习方法p l 。支持向量机采用结构风险最小化准则( s t r u c t u r a lr i s k m i n i m i z a t i o n ，简记为s r m ) ) i i 练学习机器，其主要优点有：将学习问题归结为一个 凸二次规划问题，从理论上说，得到的是全局最优解，解决了在神经网络方法中 无法避免的局部极值问题；通过非线性变换将数据映射到高维特征空间，使数据 在高维空间中可以用线性判别函数分类；巧妙地解决了维数问题，使算法复杂性 与样本维数无关；具有简洁的数学形式和直观的几何解释；人为设定的参数少、 便于理解和使用等。支持向量祝建立在严格的理论基础之上，较好地解决了局部 极小点、非线性、高维等问题，成为继神经网络研究之后机器学习领域新的研究 热点。支持向量机从提出、被广泛重视到现在只有十几年的时间，其中还有很多 尚未解决或尚未充分解决的问题，在应用方面还具有很大的潜力，因此，支持向 量机是一个十分值得大力研究的领域。 重庆大学硕士学位论文 1 绪论 支持向量机作为一种尚未成熟的新技术，目前存在很多局限。支持向量机最初 是为两类分类问题而设计的，缺乏对多类分类问题的处理能力，使得s v m 理论在 分类技术上的应用受到了很大限制。而在实际应用中，多类分类问题更为普遍， 如何将支持向量机的优良性能推广到多类分类当中去，具有很大的实用价值，并 且已成为目前支持向量机研究中的一个热点问题。 1 2 国内外研究现状 分类是将数据项分为一个或几个预定义的类的初始学习函数，是一种有监督的 学习方法。分类是模式识别中的一项重要内容，也是人们认识一切事物的基础， 许多优秀的学习算法都是以分类为基础发展起来的，如神经网络、支持向量机等。 目前，用于模式分类的方法很多，传统的方法有b a y e s i a n 方法、距离判别、f i s h e r 判别、l 【- 近邻分类以及分段线性分类等，现有的方法如粗糙分类、神经网络分类等。 还有刚刚兴起的支持向量机分类方法。模式分类方法已经在医学诊断、机器故障 诊断、语音识别、人脸识别等领域得到了广泛的应用。 支持向量机是一种非常重要的分类方法，它是建立在统计学习理论基础上的机 器学习方法，通过学习算法，s v m 可以自动寻找那些对分类有较好区分能力的支 持向量，由此构造出的分类器可以最大化类与类的间隔，因而有较好的推广性能 和较高的分类准确率。s v m 的主要思想是针对两类分类问题，在高维空间中寻找 一个超平面作为两类的分割，以保证最小的分类错误率。而且s v m 的另一个重要 的优点是可以处理线性不可分的情况，首先要从原始空间中抽取特征，将原始空 间中的样本向量映射到线性可分的高维特征空间中，以解决原始空间中线性不可 分问题。 支持向量机算法一经提出，就得到国内外学者的高度关注。学术界普遍认为它 是继神经网络之后的一个新的研究方向。近十几年来国内外一些研究者对s v m 及 其应用方面进行的有重要价值的且具有代表性的研究工作有：s v m 训练速度方面 的研究、预处理方法方面的研究、多分类方法的研究、回归方面的研究及s v m 的 应用研究h 。 1 2 1s v m 训练速度方面的研究 尽管s v m 算法的性能在很多实际问题中的应用中得到了验证，但是该算法在 计算上存在着一些问题，包括训练算法速度慢、算法复杂而难以实现以及检测阶 段运算量大等等。其中，s v m 的训练速度是限制它应用的主要问题。训练一个s v m 相当于解一个凸二次规划( q u a d r a t i cp r o g r a m m i n g , 简记为q p ) 问题。 对于小规模的q p 问题，经典最优化算法，如牛顿法等都可以较好地求解，但 当训练集很大，特别是支持向量数目很大时，多数算法需要的内存与矩阵的大小 2 重庆人学硕士学位论文 1 绪论 成比例，所以解q p 问题的经典方法不再可行。目前，一个大多数算法的一个共同 的思想就是循环迭代：将原问题分解成为若干子问题，按照某种迭代策略，通过 反复求解子问题，最终使结果收敛到原问题的最优解。根据子问题的划分和迭代 策略的不同，又可以大致分为如下两类： 第一类是所谓的块算法( c h u n k i n ga l g o r i t h m ) ，它最早在1 9 9 5 年，由c o r t e s 和 v a p n i k 提出【3 1 。块算法基于这样一个事实，即去掉l a g r a n g e 乘子等于零的训练样 本不会影响原问题的解。对于给定的训练样本集，如果其中的支持向量是已知的， 寻优算法就可以排除非支持向量，只对支持向量计算l a g r a n g e 乘子即可。实际上 支持向量是未知的，因此，块算法的目标就是通过某种迭代方式逐步排除非支持 向量。具体的作法是，选择一部分样本构成工作样本集进行训练，剔除其中的非 支持向量。并用训练结果对剩余样本进行检验，将不符合训练结果( 一般是指违 反k k t 条件【5 1 ，因为只有违背k k t 条件的样本才会影响支持向量集) 的样本( 或 其中的一部分) 与本次结果的支持向量合并成为一个新的工作样本集，然后重新 训练，如此重复下去直到获得最优结果。当支持向量的数目远远小于训练样本数 目时，这种方法显然能够大大提高运算速度。然而，如果支持向量的数目本身就 比较多，随着算法迭代次数的增多，工作集样本也会越来越大，算法依旧会变得 十分复杂。 第二类方法称为分解算法。o s u n a 等人提出了分解算法的基本框架【6 7 1 。首先 建立一个工作集，保持其大小不变，在解决每个二次规划子问题时，先从工作集 中移走一个样本，并加入一个不满足k k t 条件的样本，反复迭代直到所有的样本 都满足k k t 条件。每一个q p 子问题仍然适用迭代数值优化算法求解，o s u n a 证 明每次迭代使目标函数单调递增，因为目标函数有上界，所以经过有限次迭代后 算法将收敛并得到最优解。 s v m l i g h t 和贯序最小优化( 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 ) 【2 l j 是两个典型的分解算法。 s v m l i g h t 是由j o a c h i m s 提出来的一种有效的分解方法，它采用了可行方向法 选择工作集，并实现了k e r n e lc a c h e 和s h r i n k i n g 两种加速方法。p l a t t 提出的s m o 算法可以看作是o s u n a 算法中工作集的势等于2 的一个特例。s m o 方法将工作集 的规模减到最小两个样本，在优化过程中换入换出样本点但保持非工作集的 l a g r a n g e 乘子不变。由于子问题的优化只涉及两个变量，而且应用等式约束可以 将其中一个变量用另一个变量线性表示出来，所以迭代过程中每一步的子问题的 最优解可以直接用解析的方法求出来，而不用在算法的迭代中求解二次规划问题。 它在每一步迭代只是选择两个变量进行调整，同时固定其他变量，通过求解最优 化问题，得到两个变量的最优解，来更新相应的l a g r a n g e 乘子。 重庆大学硕士学伊论文1 绪论 除此之外，文献【8 】提出了r s v m ( r e d u c e ds u p p o r tv e c t o rm a c h i n e ，简记为 r s v m ) 方法，不采用所有样本，而是通过随机选择训练样本集合，减少训练规模， 提高训练速度。文献 9 中s u y k e n sv a n d e w a l b 等提出最小二乘支持向量机( l e a s t s q u a r es u p p o r tv e c t o rm a c h i n e 。简记为l s s v m ) ，优化指标采用平方项，只有等 式约束，从而将二次规划问题转化为线性方程组的求解，大大简化了计算复杂度。 还有一些研究者将自适应聚裂1 0 1 、概率模型l 、近邻规则【1 2 - j 3 等引入支持向量机 训练中，并取得了较好的结果。 因为目前速度问题在很大程度上限制了s v m 的应用，如何在尽可能不降低分 类准确度的情况下加快算法的速度，仍将是一个活跃的研究分支。 1 2 2s v m 预处理方法方面的研究 这类方法应用在s v m 算法之前在一定程度上减小了待解决问题的规模。如 z h e n gc h u n h o n g 提出了一种支持向量机的模糊预抽取支持向量的方法【1 4 1 ，能通过 p s v m ( p r o x i m a ls u p p o r tv e c t o rm a c h i n e ”】) 初解来求出每个训练样本的拉格朗日 因子值，然后通过拉格朗日因子来预抽取支持向量机训练样本集合，来达到缩小 支持向量机训练样本规模的目的。 z h a n gl i 提出了一种基于样本到两类样本中心点距离比方法预抽取支持向量 机训练样本集合，大大减小了支持向量机训练样本的数量，提高了支持向量机训 练速度“。 r y c h e t s k y 等人提出的t r a n s r e d 和g e t b o r d e r 方法，能够确定支持向量近似集 合，避免了c h u n k i n g 方法中对初始c h u n k 的随机选取【1 7 】。 m i n gh s u a n y a n g 等人提出了训练支持向量机的几何方法，主要是利用训练集 中的集合信息，提出了“卫向量( g u a r dv e c t o r ) ”的概念，“卫向量”即为通过该 向量能使输入空间线性可分的向量。所有的支持向量都是卫向量，但反之不成立。 当训练集合较大时，可以先找出卫向量，再以卫向量构成传统的q p 问题求出支持 向量，卫向量的求解是通过判断其对偶空间中的线性规划问题的可行性而不是求 其解，从而使问题大大简化【1 8 l 。 m a o k z 提出通过判别函数剪枝对支持向量机的特征子集进行选择的方法【1 9 1 。 1 2 3s v m 多类分类方法研究 从分类的角度讲，s v m 本质上是一个二类分类算法，不能直接用来解决多类 分类问题，而现实中的分类问题一般情况下都是多类分类问题，因此如何利用s v m 解决多类分类问题非常值得深入研究。 其中一种主要方法是组合多个二类子分类器实现对多类分类器的构造。其核 心问题是： 1 ) 如何把一个多类分类问题分解为多个两类分类问题； 4 重庆人学硕士学位论文 1 绪论 2 ) 如何将多个两类分类的结果有效组合，给出最终判决。 许多学者对s v m 的多类分类策略进行了深入研究，提出了一些有效的算法。 最早的是v a p i n k 提出的l v r ( o n ev e r s u sr e s t ，简记为l v r ) 算法1 2 0 ，它的思想 是对于类问题，构造个分类器，第i 个s v m 用第i 类中的训练样本作为正 的训练样本，而将其它的样本作为负的训练样本。最后的输出是两类分类器输出 最大的那一类。但其缺点是它的泛化误差无界【2 i 】。与1 一v - r 算法不同的是1 v 1 ( o n e v e r s u so n e ，简记为1 v 1 ) 算法将n 个类别中的每两个类别组合在一起，用一个 s v m 对其分类，因此为将n 个类别分开工需要n ( n 1 ) 2 个两类分类器。2 0 0 c 年，j p l a t t 采用d a g ( d i r e c t e da e y c l i cg r a p h ，简记为d a g ) 的方法来构造d a g s v m 多类分类算法【”，并通过实验分析了其推广性。 每种多类分类方法都有其自身的优势，同时也存在着自身的缺点，比如1 v - r 方法存在不属于任何一类或同时属于多类的不确定区域的存在，l - v 一1 及d a g 方 法所需要训练的分类器数目多，l v 1 也存在一个样本同时属于多个类别的缺点。 目前还没有很好的多类分类s v m 算法，因而限制了s v m 的推广。 1 2 4s v m 回归方面的研究 支持向量机最初是为分类问题而设计的，它已成功应用于o c r ( o p t i c a ! c h a r a c t e rr e c o g n i t i o n ，简记为o c r ) 和目标识别任务【2 ”。但近些年来，支持向量柳 在回归算法的研究方面也表现了极好的性能肼】。 支持向量机回归有线性回归和非线性回归【2 5 1 ，对于线性回归，考虑用线性叵 归函数估计样本数据。对于非线性回归，其基本思想是通过一个非线性映射中枸 数据x 映射到高维特征空间，并在这个空间进行线性回归。这样，在高维特征空 间的线性回归就对应于低维输入空间的非线性回归，其具体实现是通过核函数 k ( x ，x ，) = 庐( x ；) ( x ，) 来实现的，这样就免去了在高维空间计算复杂的点积运算。 和支持向量机的分类算法相似，支持向量机的回归算法最终也转化为一个求解凸 二次规划问题，并且其二次规划的规模为同样样本数量下分类问题的二倍，因此， 支持向量机回归同样面临着当样本较多时计算量大，训练速度慢的缺点。因此提 高支持向量机回归问题的矽i i 练速度便成为支持向量机研究的一个重要方面。 c h u n k i n g 算法是由c o r t e s 和v a p n i k 提出的一种改进的学习算法【3 】，这种学习 算法采用了并行的系列更新方法，将优化方法的大型q p 问题分解为一系列小规模 的q p 问题来解决大数据量的支持向量机回归的学习问题。这种优化算法虽然对传 统的支持向量机回归算法有了一定的改进，但是对于规模巨大的数据集或建模势 据不具有稀疏性的数据仍然不适用。p l a t t 等提出了s m o 方法【2 6 】，这种方法每次只 优化两个拉格朗日乘子，由于只有两个参数得到优化而其余参数保持不变，因而 优化方法可以不采用o p 方法而采用数字运算的分析方法进行优化。因此该方法适 5 重庆大学硕十学位论文1 绪论 合于大数据集的学习而且提高了运行速度。陶卿等提出一种基于支持向量机分类 的回归方法【z ”，通过对样本点集的适当变换，提出种将回归问题转化为二分类 问题的新思想。一方面这与前馈神经网络的理论体系相一致，另一方面也使得回 归问题中支持向量的几何意义更明显，为分类问题的研究成果应用于回归问题奠 定了理论基础。 1 2 5s v m 的应用研究 s v m 在解决实际问题时表现出的卓越性能，引起了世界范围内众多科研机构 的高度关注。目前，贝尔实验室、伦敦大学、m i t 、德国g m d 、微软设计院等己 成立了统计学习理论、s v m 及其应用的研究中心。支持向量机被广泛地应用于模 式识别领域，贝尔实验室率先对美国邮政手写数字库识别研究【3 1 方面应用了支持向 量机方法，取得了较大的成功，在随后的近几年内，有关支持向量机的应用研究 得到了更多领域学者的重视，在人脸检测【2 8 】、验证和识别、说话人语音识别、文 字手写体识别、三维物体识别【2 ”、图像处理及其它应用研究等方面取得了大量的 研究成果，从最初的简单模式输入的直接的支持向量机方法研究，进入到多种方 法取长补短的联合应用研究，对支持向量机方法也有了很多改进。 1 3 本文的研究内容和组织结构 1 3 1 研究内容 本文紧紧围绕设计一种更好的s v m 多类分类方法、将s v m 的应用推广到新 的领域这两个核心内容，重点在以下几个方面进行研究： 支持向量机多类分类算法的分析比较。全面总结了目前所存在的基于支持 向量机的多类分类方法，包括“一对多”、“一对一”方法、有向无环图方法、树 型s v m 方法等，给出了理论上的性能比较、推广能力的分析、时间复杂度比较； 并通过实验对其中几种常用的方法进行了验证与比较。 提出了一种基于支持向量数据描述算法的s v m 多分类新方法。对基于支持 向量数据描述算法的多分类方法进行了研究，分析了它的优缺点，并深入讨论了 其推广性能一般的原因，针对其存在不可分区域这个问题，提出了一种新的多分 类方法( s m s v m ) ，然后对其进行了时间复杂度分析，并通过在多组u c i 数据上 的实验证明了其良好的推广能力。 将支持向量机多分类方法应用于孤立肺结节的诊断，实验结果表明s v m 分 类器对恶性结节的诊断效果更好。孤立肺结节的诊断对临床医生及影像科医生而 言是一个极大的挑战，除了其发生率高，孤立肺结节的诊断中精确区别无结节、 良性结节和恶性结节是非常困难的，所以开发一套辅助诊断的分类器是非常重要 的。本文将仿生模式识别、b p 神经网络和s v m 分别应用于孤立肺结节的识别中， 6 重庆大学硕士学位论文 1 绪论 实验表明三种方法对无结节和良性结节的识别效果相当，而s v m 分类器对于恶性 结节的诊断效果更好。 1 3 2 本文的章节组织 本文共六章，安排如下： 第一章，主要阐述了本文研究的背景和意义，分析了s v m 的理论研究及应用 现状，确定了本文的研究内容。 第二章，系统介绍了s v m 的理论基础。给出机器学习问题的学习模型，分析 了目前一些机器学习方法所面临的问题，阐述了传统统计学的学习算法的缺陷， 介绍了统计学习理论的基本思想和主要方法，从分类的角度分析了s v m 的数学本 质及其泛化性能。本章是一个贯穿全文的理论基础。 第三章，重点对比分析了现有的s v m 多类分类方法，在理论上给出了几种方 法的时间复杂度分析和推广能力分析，并在几组标准数据上做了验证性的比较实 验。本章的工作为本文的创新点奠定了基础。 第四章，深入探讨了支持向量机数据描述算法，并针对目前的多类分类方法 存在的问题提出了一种基于支持向量数据描述算法的s v m 多类分类方法，分析了 这种方法的时间复杂度，并通过在u c i 数据上的实验验证了该方法具有良好的推 广能力。 第五章，将s v m 多分类学习算法应用于孤立肺结节的诊断，实验表明s v m 多类分类方法对恶性结节的识别优于其他常用方法。通过这些实验分析了影响 s v m 学习性能的因素，这对设计新的算法以改善s v m 的性能具有指导意义。 第六章，全文总结并对今后的工作提出展望。概括了本文的主要工作和所得 的结论，并做出展望。 7 重庆人学硕士学位论文2 支持向量机理论基础 2 支持向量机的理论基础 支持向量机是2 0 世纪9 0 年代中期，v a p n i k 等人在统计学习理论、v c 维理 论、结构风险最小化理论、核函数理论的基础上研究提出的一种新的机器学习 算法，它在很多领域都表现出优于现有学习算法的性能。如果仅从分类的角度 来讲，s v m 是一种广义的线性分类器，它是在r o s s e n b l a t t 线性感知机的基础上， 通过引入结构风险最小化理论、核函数理论、最优化理论演化而成的。 本章首先介绍了机器学习的基本问题及其存在的缺点，从而引出统计学习 理论的基本思想，在此基础之上，讨论了简单的线性情况下的最优超平面的构 造，然后进一步将其推广到非线性情况。其次，介绍了支持向量机核函数的理 论，最后就如何进行s v m 的模型选择做了简单阐述。 2 1 机器学习的基本问题 2 1 1 问题的表示 基于数据的机器学习，研究的实质是从观测数据出发寻找规律，利用这些 规律对未来数据或无法观测的数掘进行分类、研究、处理。 机器学习的基本模型可以用图2 1 表示： 输出y 预测输出y 图2 1 机器学习的基本模型 f i g2 1b a s i cm o d e lo f m a c h i n el e a m m g 机器学习的模型包括三部分： ( 1 ) 样本产生器( g ) ：以未知概率分布函数f ( x ) 产生独立同分布的样本 x r “o ( 2 ) 系统( s ) ：是研究的对象，对每一个输入向量x 产生一个输出y ，输 出与输入之间符合固定但未知的条件分布f ( y i 功。 ( 3 ) 学习机器( l e a r n i n g m a c h i n e ，简记为l m ) ：能够根据已知的训练样本 对系统输入输出之间的依赖关系进行估计，对未来样本的输出做出尽可能准确 重庆大学硕士学位论文2 支持向量机理论基础 的预测。这也是机器学习的目的所在。 机器学习的问题可以一般地表示为：变量y 与工存在一定的未知依赖关系， 即遵循某一未知的联合概率f c x ，y ) ，机器学习问题就是根据疗个独立同分布观 测样本： ( 而，y 1 ) ，( 屯，y 2 ) ，( x 。，y 。) 在一组函数 ，w ) 中求一个最优的函数f ( x ，w o ) ，对依赖关系进行估计， 使期望风险： r ( w ) = i l ( y ，f ( x ，w ) ) d f c x ，y ) 最小。其中l ( y ，f ( x ，w ) ) 称作预测函数集，w 为函数的广义参数，l ( y ，f ( x ，w ) ) 为 由于用f ( x ，w ) 对y 进行预测而造成的损失，不同类型的学习问题有不同形式的 损失函数。预测函数也称作学习函数、学习模型或学习机器。有三类基本的机 器学习问题，即模式识别、函数逼近和概率密度估计，这里只讨论模式识别问 题。其输出y 是类别标号，两类情况下y = ( 0 , 1 ) 或 一1 , 1 ) ，预测函数称作指示函 数，这时损失函数可以定义为： 地，f c x , 咖倍矿i f ；主麓暑 使风险最小就是在b a y c s 决策中使错误率最小。 2 1 2 机器学习面临的问题 在上面的问题描述中，学习的目标在于经验风险最小化，这种思想在多年 的机器学习方法研究中占据了主要地位，人们将大部分注意力集中在如何更好 地最小化经验风险，实际上当样本数目趋向于无穷大时经验风险才能趋向于期 望风险。而在很多实际问题中，样本数目离无穷大相去甚远，所以，事实上， 训练误差小并不总是导致好的预测效果，某些情况下，训练误差小反而导致推 广能力的下降，即真实风险的增加，这就是过学习问题。究其原因，由于试图 用复杂的模型去拟合有限的样本，导致其丧失了推广能力。在神经网络中，若 对有限的样本来说网络的学习能力过强，足以记住每个样本，此时经验风险很 快就可以收敛到很小甚至零，但却根本无法保证它对未来样本能给出好的预测。 由此可以看出，在有限样本的情况下，经验风险最小并不意味着期望风险 最小；并且，学习机器复杂性不但与所研究的系统有关，而且要和学习样本相 适应。所以，就需要寻找一种能够指导我们在小样本情况下建立有效的学习和 推广方法的理论。 9 重庆人学硕士学位论文2 支持向量机理论基础 2 2 统计学习理论的基本思想及核心内容 v a p n i k 等人从2 0 世纪六、七十年代就开始致力于小样本情况下的机器学习 研究工作，并建立了统计学习理论的基本体系p o l 。由于当时这些研究还不十分 完善，且没有提出将理论付诸实践的较好的算法，一度使这些研究没有得到充 分的重视。直到九十年代中期，随着统计学习理论体系的逐步完善，加之支持 向量机的产生，人们才开始迅速重视起这一早在2 0 年前就应该重视的学术方向。 统计学习理论被认为是目前对小样本统计估计和预测学习的最佳理论。它 从理论上较系统地研究了经验风险最小化原则成立的条件、有限样本下经验风 险与期望风险的关系及如何利用这些理论找到新的学习原则和方法等问题。其 主要内容包括： 1 1 经验风险最小化原则下统计学习一致性的条件； 2 1 在这些条件下关于统计学习方法推广性的界的理论； 3 1 在这些界的基础上建立的小样本归纳推理准则； 们实现新的准则的实际方法或算法。 其中，最有指导性的理论结果是推广性的界