（概率论与数理统计专业论文）支持向量机分类与回归方法研究.pdf

摘要 作为传统统计学的重要补充和发展，针对小样本数据提出的统 计学习理论近来受到广泛重视。在统计学习理论基础上发展起来的 支持向量机已经展现出优秀的学习性能，并由最初的分类任务成功 地扩展到处理回归、概率密度估计和异常值检测等问题。支持向量 机一改传统方法的经验风险最小原则，而是根据结构风险最小化原 则提出的，这就使其能够达到更好的泛化能力。 支持向量机另外一些优势可以通过与神经网络相比展示出来。 支持向量机只有少数可调的参数，而且训练问题可以归结为解一个 凸二次规划，从而所得的解是全局最优的，通常也是唯一的。 本文以支持向量机理论为基础，对分类与回归的基本方法及其 应用进行了系统的研究。全文共分七章，具体内容如下。 第一章综述了分类与回归的基本方法，包括贝叶斯方法、神经 网络方法和支持向量机方法等。 第二章介绍了支持向量机一类分类、二值分类以及回归算法， 并在一类分类的基础上，提出一种多值分类算法。所给方法有效地 克服了通过构造一系列二值分类而达到多值分类的复杂计算问题， 从而有机地将一类分类、二值分类及多值分类融合到一起。进一步 提出了多值分类算法的分解形式，为解决大规模数据分类问题提供 了一条可行的途径。 第三章首先总结归纳了线性规划下的支持向量机方法。其次， 在基于线性规划的支持向量机算法基础上，提出几种新的回归模 型，所给模型不但简化了原模型的复杂结构，而且仍能保持良好的 预测性能。最后，提出一种基于线性规划的多值分类算法和它的分 解形式，该方法不但简单易行，而且仍能保持良好的分类精度。同 时，结合基于核的主成分分析( k e r n e lp r i n c i p a lc o m p o n e n ta n a l y s i s ， k p c a ) 方法和所给多值分类算法建立了一种人脸识别模型。对0 r l 人脸图像库的实验结果表明所给方法是可行的、有效的。 第四章对支持向量机回归模型进行了一些扩展研究，具体内容 分四部分：一、提出一种单参数约束下的回归模型，并证明了该模 型与标准回归模型的等价性；二、针对实际回归问题中经常出现异 方差性，提出一种加权支持向量回归算法。仿真实验表明，当数据 中存在异方差性时，所给方法的预测结果更接近真实值；三、针对 支持向量回归模型中只有点输出而没有概率输出这一缺点，根据局 部预测思想，在回归模型中定义了一种预测信任度的概念，从而为 预测值提供了一个可信度评判。另外，通过对可信度的观测，还能 在一定程度上判别数据中的噪声含量；四、研究了回归与分类之间 的关系，为快速分类算法应用于回归模型中提供了定的理论依 据。 第五章对异常值检测进行了探讨。利用支持向量回归算法中结 构风险函数较好的平滑性以及k k t 条件，提出一种回归中的异常值 检测方法。另外，结合一类分类方法和相空间重构理论，提出一种 时间序列中的异常值检测方法。 第六章讨论了支持向量机与神经网络之间的关系，同时将支持 向量回归的各种版本及r b f 网络应用予混沌时间序列预测中，并通 过加入不同水平的噪声来比较分析它们的预测性能。 第七章总结全文并对今后研究工作提出展望。 关键词支持向量机，结构风险最小化原则，核函数，分类， 回归 a b s t r a c t r e c e n t l y s t a t i s t i c a l l e a r n i n gt h e o r y h a sr e c e i v e dc o n s i d e r a b l e a t t e n t i o np r o p o s e db a s e do ns m a l ls a m p l ed a t a ，w h i c hi sa l l i m p o r t a n t c o m p l e m e n t a r i t y a n d d e v e l o p m e n t o ft r a d i t i o n a l s t a t i s t i c s s u p p o r t v e c t o r m a c h i n e s ( s v m s ) a l g o r i t h m s b a s e do nt h ef o u n d a t i o n so f s t a t i s t i c a l l e a r n i n gt h e o r ys h o we x c e l l e n tl e a r n i n gp e r f o r m a n c e ，w h i c h h a v e b e e n s u c c e s s f u l l y e x t e n d e df r o mb a s i cc l a s s i f i c a t i o nt a s k st o r e g r e s s i o n ，d e n s i t ye s t i m a t i o n ，n o v e l t yd e t e c t i o n ，e t c u n l i k et r a d i t i o n a l m e t h o d s ，w h i c hm i n i m i z e t h e e m p i r i c a lt r a i n i n ge r r o r ，s v m s m a k eu s eo f t h es t r u c t u r er i s km i n i m i z a t i o np r i n c i p l e ，w h i c hm a yb r i n go nag o o d g e n e r a l i z a t i o np e r f o r m a n c e a d d i t i o n a la d v a n t a g e so fs v m sc a nb ea p p r e c i a t e di nc o m p a r i s o nt o n e u r a ln e t w o r k s f o rs v m st h e r ea r e o n l yas m a l ln u m b e ro ft u n a b l e p a r a m e t e r s a n d t r a i n i n g a m o u n t st o s o l v i n g ac o n v e x q u a d r a t i c p r o g r a m m i n gp r o b l e mh e n c eg i v i n gs o l u t i o n st h a ta r eg l o b a l ，a n du s u a l l y u n i q u e t h i st h e s i sc o n s i s t so fs e v e nc h a p t e r s ，w h i c hs t u d i e st h e p r o b l e m so f p a t t e r nc l a s s i f i c a t i o n ，r e g r e s s i o na n d t h e i r a p p l i c a t i o n s t h eb a s i cm e t h o d sa b o u tc l a s s i f i c a t i o na n d r e g r e s s i o n a r e s u m m a r i z e di nt h ef i r s tc h a p t e r ，w h i c hi n c l u d eb a y e s i a nm e t h o d ，n e u r a l n e t w o r k s ，s u p p o r t v e c t o rm a c h i n e s ，e t c c h a p t e r 2i n t r o d u c e st h e a l g o r i t h m s o fo n e c l a s s s u p p o r t v e c t o r m a c h i n e ，b i n a r yc l a s s i f i c a t i o na n dr e g r e s s i o n ，a n dt h e nan e w m u l t i c l a s s c l a s s i f i c a t i o na l g o r i t h mi sp r o p o s e db a s e do no n e c l a s sc l a s s i f i c a t i o ni d e a ， w h i c hc a n l a r g e l yr e d u c ec o m p u t a t i o nc o m p l e x i t ) r a n ds y n c r e t i z et h e m e t h o d so fo n e c l a s s ，t w o c l a s sa n dm u l t i - c l a s sc l a s s i f i c a t i o n a tt h e s a m et i m e ，a d e c o m p o s i t i o na l g o r i t h m o fm u l t i c l a s sc l a s s i f i c a t i o ni s p r o p o s e d ，w h i c h c a n p r o v i d e af e a s i b l e a p p r o a c h f o r s o l v i n g t h e c l a s s i f i c a t i o np r o b l e mo f l a r g e - s c a l ed a t a i n c h a p t e r3 ，s u p p o r t v e c t o rm a c h i n ea l g o r i t h m sb a s e do nl i n e a r p r o g r a m m i n ga r e s u m m a r i z e df i r s t l y s e c o n d l y ，t h r e en e wr e g r e s s i o n m o d e l sa r ep r o p o s e db a s e do nl i n e a rp r o g r a m m i n g ，w h i c hc a nr e d u c et h e i i i c o m p l e x i t yo fm o d e l sa n dk e e pt h eg o o dp e r f o r m a n c eo fp r e d i c t i o n f i n a l l y ，a n e wm u l t i c l a s sc l a s s i f i c a t i o n a l g o r i t h m a n di t sf o r mo f d e c o m p o s i t i o na r ep r o p o s e db a s e do nl i n e a rp r o g r a m m i n g ，w h i c hc a r l o b t a i ng o o d r e c o g n i t i o np r e c i s i o n ，a n dl a r g e l ys h o r t e nt h et r a i n i n gt i m e a tt h es a m et i m e ，an e wm e t h o do ff a c e r e c o g n i t i o ni sp r o p o s e d ，w h i c h i s b a s e do nk e r n e lp r i n c i p a lc o m p o n e n t a n a l y s i s ( k p c a ) a n d m u l t i c l a s s c l a s s i f i c a t i o na l g o r i t h m t h er e s u l t so f e x p e r i m e n t sa to r l f a c ei m a g e d a t a b a s es h o wt h a tt h ep r o p o s e dm e t h o di sf e a s i b l ea n de f f e c t i v e t h ec o n t e n t so fc h a p t e r4c o n s i s to ft h r e e p a r t s f i r s t l y ，an e w s u p p o r t v e c t o rr e g r e s s i o n ( s v r ) a l g o r i t h mi sp r o p o s e d b yi n t r o d u c i n g a s i n g l ep a r a m e t e r ，a n d t h e nt h e e q u i v a l e n c e b e t w e e n t h e p r o p o s e d a l g o r i t h ma n ds t a n d a r ds u p p o r tv e c t o rr e g r e s s i o ni sp r o v e d s e c o n d l y ，a k i n do f w e i g h t i n gs u p p o r t v e c t o r r e g r e s s i o n m e t h o di s p r o p o s e d c o n t r a p o s i n gh e t e r o g e n e i t yo fv a r i a n c ei nr e g r e s s i o nm o d e l s t h i r d l y ，a n o t i o no f p r e d i c t i n gc r e d i b i l i t yi sp r o p o s e di ns u p p o r tv e c t o rr e g r e s s i o n ， w h i c hc a i lm a k ep r e d i c t i n gv a l u eh a v eac r e d i b l em e a s u r e ，a n dt h e n r e l a t i o n s h i pb e t w e e np r e d i c t i n gc r e d i b i l i t ya n d n o i s ei sd i s c u s s e d f i n a l l y ， t h ec o n n e c t i o nb e t w e e nr e g r e s s i o na n dc l a s s i f i c a t i o ni s s t u d i e d , w h i c h c a r l p r o v i d ed e f i n i t et h e o r yf o u n d a t i o nf o r f a s tc l a s s i f i c a t i o na l g o r i t h m a p p l y i n g t or e g r e s s i o nm o d e l s i n c h a p t e r 5o u t l i e rd e t e c t i o ni sd i s c u s s e d am e t h o do fo u t l i e r d e t e c t i o ni n r e g r e s s i o n i s p r o p o s e dm a k i n g u s eo ft h ec h a r a c t e ro f s t r u c t u r er i s kf u n c t i o na n dk k tc o n d i t i o ni ns u p p o r tv e c t o r r e g r e s s i o n i n a d d i t i o n ，an e wm e t h o do fo u t h e rd e t e c t i o ni nt i m es e r i e si sp r o p o s e db y c o m b i n a t i o no f p h a s es p a c et h e o r y a n do n e - c l a s sc l a s s i f i c a t i o nm e t h o d c h a p t e r6d i s c u s s e st h er e l a t i o n s h i pb e t w e e nn e u r a ln e t w o r k sa n d s u p p o r tv e c t o rm a c h i n e s ，a n dt h e na p p l i e sd i f f e r e n tv e r s i o n so fs u p p o r t v e c t o rr e g r e s s i o na n dr b fn e t w o r k st ot h ep r e d i c t i o no fn o i s ec h a o t i c t i m es e r i e sa n d c o m p a r e s t h e i rc a p a b i l i t yo f p r e d i c t i o n c h a p t e r7i st h es u m m a r i z a t i o no f w h o l et h e s i sa n de x p e c t a t i o nf o r t h ef u t u r e k e yw o r d ss u p p o r tv e c t o rm a c h i n e ，s t r u c t u r er i s km i n i m i z a t i o n p r i n c i p l e ，k e r n e lf u n c t i o n ，c l a s s i f i c a t i o n ，r e g r e s s i o n i v 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得中南 大学或其他单位的学位或证书而使用过的材料。与我共同工作的同志对本 研究所作的贡献均已在论文中作了明确的说明。 作者签名：塾j 整圭曰期：坦生年上月宣日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校有权 保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位论文的全 部或部分内容，可以采用复印、缩印或其它手段保存学位论文；学校可根 据国家或湖南省有关部门规定送交学位论文。 作者签名：垫建些导师签名矬日期：色! 生年卫月孕日 博士学位论文第一章导论 1 1 课题背景及意义 第一章导论 随着科学技术的飞速发展以及计算机、i n t e r n e t 的日益普及，越来越多的复 杂非线性高维数据需要分析、处理，这也给传统的统计学方法提出了严峻挑 战。从数据中发现知识是分析复杂数据、建立决策系统的基石。模式分类和回 归分析是知识发现中的重要内容，也是处理许多其它问题的核心。 用于分类与回归的方法很多，如传统的统计分析方法以及神经网络方法【l 圳 等。这些方法虽然在实际应用中占据主导地位，但人们也发现它们还存在着许 多不足之处。比如，传统的统计方法一般需要事先知道样本的先验分布，并要 求有足够多的样本数据，而这些要求在实际应用中往往难以达到，这就使其在 实际应用中效果往往并不理想。神经网络方法虽然很好地解决了非线性问题， 但由于其自身存在着结构不易确定、易陷入局部极小等固有的缺陷，从而限制 了其实际应用。另外，神经网络的学习算法仅仅试图使经验风险最小化，并没 有使期望风险最小化，与传统的最小二乘法相比，在原理上缺乏实质性的突 破，这也是神经网络过拟合现象产生的原因，从而导致了其推广能力的下降。 v a p n i k 等人提出的统计学习理论( s t a t i s t i c a ll e a r n i n gt h e o r y ，s l t ) 【3 ，4 1 是 一种针对小样本情况研究统计学习规律的理论，该理论的核心思想是通过引入 结构风险最小化准则来控制学习机器的容量，从而刻画了过度拟合与泛化能力 之间的关系。在这一理论基础上产生的支持向量机( s u p p o r tv e c t o rm a c h i n e s ， s v m ) 学习方法近来受到广泛重视，该方法不但引入了结构风险的概念，还采 用了核映射的思想，与传统方法相比，支持向量机所具有的优势体现在，即克 服了传统方法的大样本要求，还有效地克服了维数灾难及局部极小问题，并在 处理非线性问题时显示了其卓越的优越性。 作为一门新兴的学科，有关支持向量机方面的很多研究在国外也是刚刚起 步，国内的有关研究只是在近几年才逐渐引起人们的注意。虽然支持向量机方 法有比较完善的理论基础，但有关其应用研究还有很多亟待解决的问题，并且 随着其应用领域的不断扩大，其理论也有待进一步完善和发展。 本文正是在这一理论背景下，以支持向量机方法为主线，在二次规划和线 性规划的框架下对分类与回归中的基本方法进行研究，讨论了分类与回归之间 的关系，并提出了一些新的分类及回归方法，同时探讨了支持向量机在异常值 博士学位论文 第一章导论 检测以及在时间序列预测中的具体应用。该课题的研究将扩展支持向量机的应 用空间。 1 2 目前发展状况 模式分类是模式识别中的一项重要内容，分类也是人们认识一切事物的基 础，许多优秀的学习算法都是以分类为基础发展起来的，如神经网络、支持向 量机等。目前，用于模式分类的方法很多，传统的方法有b a y e s i a n 方法、距离 判别、f i s h e r 判别、k 近邻分类以及分段线性分类等口】，现代的方法如模糊分类 6 1 、粗糙分类7 以及神经网络分类等，还有刚刚兴起的支持向量机分类方法【8 】。 模式分类方法已经在医学诊断、机械故障诊断、语音识别、人脸识别等领域得 到了广泛的应用。 回归分析【9 】发展和完善的根本动力在于其在生产实践中的广泛应用。从高 斯提出的最小二乘法算起，回归分析的历史已有1 9 0 多年。从经典的回归分析 方法到近代的回归分析方法，它们所研究的内容己非常丰富。基于最d , - - 乘法 的模型回归方法由于简单且模型具有很好的解释性，在实际中被广泛采用。随 着应用的不断深入，人们发现经典的最小二乘估计结果并不总是令人满意的， 于是人们从多方面进行努力试图克服经典方法的不足，从而产生了岭估计、压 缩估计、主成分估计、s t e i n 估计，以及特征根估计、偏最小二乘法等多种有偏 估计。另外，为了克服最小二乘法估计对异常值的敏感性，人们提出了各种稳 健回归方法；为了分析和处理高维数据，产生了投影寻踪回归、切片回归等； 为了解决非线性问题，人们还提出了许多非线性回归模型。 虽然分类与回归具有许多不同的研究内容，但它们之间却有许多相同之 处，简单地说，它们都是研究输入输出变量之间的关系问题，分类的输出是离 散的类别值，而回归的输出是连续的数值。有很多学习方法既可以用于分类又 可以用于回归中，如贝叶斯方法、神经网络方法和最近刚刚兴起的支持向量机 方法等。由于这三种方法在分类与回归研究中具有广泛的代表性，下面分别综 述如下。 1 21 贝叶斯学习理论 贝叶斯( 1 7 0 2 1 7 6 1 ) 的论文“论有关机遇问题的求解”是贝叶斯学派产生 的重要基础，由于其最初在理论和实际应用中存在很多不完善的地方，因此长 时间未被广泛接受。2 0 世纪初，b d ef i n e t t i 与j e f f r e y sh 对贝叶斯学派的理论 2 博士学位论文第一章导论 做出了重要贡献。2 0 世纪4 0 年代末，w a l d 建立了以贝叶斯理论为核心的统计 决策理论【l 。随后，以r o b b i n sh 为代表，提出了经验贝叶斯方法与经典方法 相结合1 , 1 2j ，引起了统计界的广泛重视。 2 0 世纪9 0 年代可学习的贝叶斯网络【1 3 的出现，为贝叶斯理论赋予了新的 内涵。贝叶斯网络已经广泛地用于数据挖掘和机器学习中 1 4 l 。有关贝叶斯分类 与回归方法的研究也层出不穷【1 5 , 1 6 。 贝叶斯学习理论利用概率的形式来表示变量间的依赖关系，通过先验信息 和样本数据来获得对未知样本的估计。先验概率既可以借助人的经验、专家的 知识来指定，也可以通过分析样本数据的特点直接获得。后者要求有足够多的 数据才能真正体现数据的真实分布。 贝叶斯方法的优点是可以利用人的先验知识，而缺点是当假设模型与样本 实际分布情况不相符时，就难以获得较好的效果。 1 2 2 神经网络学习理论 神经网络 2 1 的产生起源于2 0 世纪4 0 年代，心理学家m c c u l l o c h 和数学家 p i t t s 合作提出了形式神经元的数学模型，成为人工神经网络研究的开端。1 9 4 9 年，心理学家d 0 h e b b 提出神经元之间突触联系强度可变的假设，并据此提 出神经元的学习准则，为神经网络的学习算法奠定了基础。 1 9 5 8 年，r o s e n b l a t t 提出的感知器模型在神经网络的发展中有着重要的作 用，由于其只有一层的权值可调，因此它只能解决线性可分问题。虽然m i n s k y 在1 9 6 9 年出版的专著 p e r c e p t r o n s ) ) 中指出，在感知器中加入隐层神经元有可 能解决非线性可分问题，但他对加入隐层神经元后能否给出一个有效的算法持 悲观态度。1 9 8 6 年，r u m e l h a r t 等人提出了误差反向传播算法，即b p 算法，才 使神经网络的研究获得了新的生机。另外，著名的k o l m o g o r o v 连续性定理从数 学上证明了神经网络可以以任意精度逼近任意非线性函数 1 ”，这为神经网络解 决非线性问题提供了重要保证，也是神经网络在许多领域得到广泛应用的重要 基础。目前常用的神经网络模型有b p 网络、r b f ( r a d i a lb a s i sf u n c t i o n ) 网络、 h o p f i e l d 网络、自组织映射( s e l f - o r g a n i s i n gm a p ，s o m ) 神经网络等，这些网络 在分类与回归研究中都有广泛的应用 1 ”。另外，神经网络同模糊理论以及遗 传算法等软计算方法相结合产生了模糊神经网络、遗传神经网络等许多研究成 果 2 2 4 “。 虽然神经网络在很多领域得到了成功的应用，但其得到的理论成果并没有 对一般的学习理论带来多大贡献，也就是说神经网络还缺乏严密理论体系的指 博士学位论文第一章导论 导，其应用效果往往取决于使用者的经验。为了克服神经网络结构不易确定以 及泛化能力差等缺点，1 9 9 0 年，h a n s e n 和s a l a m o n 首次提出了神经网络集成 ( n e u r a ln e t w o r ke n s e n 曲l e ) 的概念 2 6 1 ，并证明了可以简单地通过训练多个神经网 络而将其结果进行合成，可以显著地提高神经网络系统的泛化能力。1 9 9 6 年， s o l l i c h 和k r o 曲给出神经网络集成的一个定义【2 ”，“神经网络集成是用有限个 神经网络对同一个问题进行学习，集成在某输入示例下的输出有构成集成的各 神经网络在该示例下的输出共同决定”。由于神经网络集成方法易于实现且效 果明显，因此吸引了大批学者从事这方面的研究工作，其中b o o s t i n g ”j 和 b a 画n 一”】集成技术是用得最多的方法。 12 3 统计学习理论 v a p n i k 等人从2 0 世纪六、七十年代就开始致力于小样本情况下的机器学 习研究工作，并建立了统计学习理论 3 州的基本体系。由于当时这些研究还不十 分完善，且没有提出将理论付诸实践的较好的算法，一度使这些研究没有得到 充分的重视。直到九十年代中期，随着统计学习理论体系的逐步完善，加之支 持向量机的产生，人们才开始迅速重视起这一早在2 0 年前就应该重视的学术方 向。统计学习理论的核心思想是通过控制学习机器的容量实现对推广能力的控 制。下面给出其中的一些重要概念。 - v c 维 统计学习理论中的一个重要概念是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 n ) ，v c 维反映了函数集的学习能力。 定义1 1 一个函数集的v c 维是p ，当且仅当存在p 个样本点 x 。 昌，函 数集能够将该样本点按所有可能的2 ，种形式分开，且不存在集合 x i ) 函( 其中 口 p ) 满足这个性质。 v c 维的直观意义就是函数集能够打散的最大样本数目，若对任意数目的 样本都有函数能将它们打散，则函数集的v c 维是无穷大。一般而言，v c 维越 大则学习机器越复杂，学习容量就越大。目前尚没有通用的关于任意函数集 v c 维计算的理论，只对一些特殊的函数集知道其v c 维。例如在n 维实数空间 中线性分类器和线性实函数的v c 维是” t - 1 ，f ( x ，a ) = s i n ( a x ) 的v c 维为无穷 大。而对于一些比较复杂的学习机器( 如神经网络) ，其v c 维的确定非常困 难。 经验风险 4 博士学位论文第一章导论 设变量y 与x 之间存在着某种未知依赖关系，即遵循某一未知的联合概率 分布f ( x ，y ) 。设有f 个来自于该分布的观测样本： ( x l ，y i ) ，( x 2 ，y 2 ) ，一，( x ，y ，) 学习的目的是根据给定的训练样本，在一组函数 f ( x ，c o ) ) 中求一个最优的 函数f ( x ，) ，使期望风险最小。期望风险为： r ( w ) = l c ( y ，f ( x ，w ) ) d f ( x ，y ) ( i - 1 ) 其中， ，( x ，r ) 称作预测函数集，w 为函数的广义参数，c ( y ，f ( x ，w ) ) 为损失函 数。 由于分布f ( x ，y ) 未知，实际上r ( w ) 无法计算，因此在传统的学习方法 中，通常采用经验风险代替期望风险。经验风险根据样本给出： r 。，( w ) = c ( y ，( x 。，p ) ) ( 1 2 ) j = l 很多学习算法如神经网络方法、最小二乘法等都是基于经验风险最小化 ( e m p i r i c a lr i s km i n i m i z a t i o n ，e r m ) 原则提出的。 事实上，即使当样本点个数趋于无穷大时，也不能保证经验风险趋于期望 风险，更何况实际中的样本数总是有限的。这就导致了e r m 准则在实际应用 中有时并不理想，一个典型的例子就是神经网络的过学习问题。 结构风险 v a p n i k 早在1 9 7 1 年就曾指出经验风险最小未必收敛于期望风险的最小值 3 0 1 ，并得出经验风险r o m p ( w ) 和实际风险r ( w ) 之间以至少1 一口的概率满足如下 的关系： 尺( w ) r 。( w ) + p ( 1 n ( 2 1 p ) + i ) - l n ( r 4 ) ( 1 - 3 ) - 其中，p 是函数集的v c 维，是样本数，7 是满足0 s 叩1 的参数。由此可 见，统计学 - j 的实际风险r ( w ) 由两部分组成：一是经验风险( 训练误差) r ( 1 p ) ，另一部分称为置信界限( v cc o n f i d e n c e ) 。置信界限反映了真实风 险和经验风险差值的上确界，反映了结构复杂所带来的风险，它和学习机器的 v c 维p 及训练样本数，有关。在有限i l l 练样本下，学习机器的复杂性越高，也 就是v c 维越高，则置信界限越大，就会导致真实风险与经验风险之间的差别 越大。 博士学位论文 第一章导论 因此，在设计分类器时，当样本数z 固定时，要想实际风险最小，不但要 使经验风险最小化，还要同时使v c 维尽可能小，这就是结构风险最小化原则 ( s t r u c t u r a lr i s km i n i m i z a t i o n ，s r m ) 。 支持向量机 支持向量机是统计学习理论中最实用的部分，也正是由于它的产生才使统 计学习理论有了新的动力。支持向量机首先是针对二值分类问题提出的，其核 心思想是将结构风险函数引入到分类中。为了便于理解，先考虑一个二维情况 下的线性可分的两类样本，如图1 1 所示。图中显示了两个能完全正确将两类 样本分开的分类线，哪个分类线更好呢? 那么显然是分类线a 更好，因为它更 远离每一类。而分类线b 虽然也正确地划分了两类，但由于它离两类样本较 近，数据集中的较小改变将导致错误分类结果，因此它不是一个好的分类线。 因此，为了求得最优分类线，不但要考虑分类误差最小，还要同时考虑分 类线的结构。支持向量机通过引入结构风险函数恰恰能完成这个任务，从而提 高了机器学习的泛化能力。此外，支持向量机还通过引入核函数的方法巧妙地 解决了非线性分类问题，并且使计算的复杂度不再取决于空间维数，而是取决 于样本数量，尤其是样本中的支持向量数。这些特点使支持向量机能有效地克 服高维问题。 类1 口 口 口 图1 1 两条分类线比较 b类2 支持向量机所展现出的优秀学习性能使得它很快受到广泛重视，并由最初 的二值分类扩展到解决回归 3 1 1 以及一类分类【3 2 悯题。支持向量机算法都是将优 化问题最终归结为解一个凸的二次规划，因此还有效地克服了局部极小问题， 并且可以直接利用目前很多优秀的二次规划工具软件。 前面已经说过，支持向量机算法的复杂度主要取决于样本的数量。因此， 当样本数据量很大时，一般的二次优化工具往往不能直接应用，于是人们提出 6 川州 博士学位论文第一章导论 了各种分解算法来解决大规模数据问题3 3 州】，其中包括分块算法( c h u i 】k i n g a l g o r i t h m ) 、s m o ( 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 ) 算法等。为了进一步降低算 法的复杂性，一些基于线性规划的支持向量机算法被提出 4 5 书】，实验表明线性 规划支持向量机在保持较好推广能力的前提下，算法复杂度大大降低。、另外， 由于支持向量机是针对两分类问题提出的，因此，还存在一个如何将其推广到 多值分类问题。目前常用的方法有一对多法、一对一方法、s v m 决策树法 5 0 l 等。w e s t o n 于1 9 9 8 年还提出一种多值分类算法 5 l 】，它是直接在目标函数上进 行改进，建立多值分类支持向量机。这些推广虽然在理论上是直接的，但在实 际应用中导致了计算复杂度很高。有关支持向量机的应用研究目前也已广泛展 开，包括文本识别5 2 - 5 4 、人脸识别 5 5 - 59 1 、语音识别 6 0 - 6 1 】、故障诊断 6 2 郴】、时间 序列预测 6 6 。6 8 1 等。 核函数 核函数在支持向量机中起着非常重要的作用，它是解决非线性问题以及克 服维数灾难问题的关键。核函数作为一种由线性到非线性之间的桥梁，它的作 用就是代替高维特征空间中的内积运算，这样就避免了复杂的高维运算。统计 理论指出，只要对称函数k ( x ，y ) 满足m e r c e r 条件就可以作为核函数。关于 m e r c e r 条件有下面的定理 6 9 j 。 定理1 1 对于任意的对称函数k ( ，y ) ，它是某个特征空间中的内积运算 的充分必要条件是，对于任意的不恒为零的妒( z ) 且l 妒2 ( x ) d x 0( 1 - 4 ) 目前常用的核函数有 ( 1 ) 多项式核函数 世“j ，) = f + 1 】 ( 2 ) 高斯径向基核函数 k ( x , y ) ：e x p ( 一哔) 盯 ( 3 ) 指数径向基函数 量( 训) ：e x p ( 一掣) 仃 ( 4 ) 多层感知器核函数 k ( x ，j ，) = t a n h v + c 】 ( 5 ) f o u r i e r 序列核函数 博士学位论文 第一章导论 s m ( n + 言) ( x 一_ y ) g ( x ，y ) = 彳生一 s i n ( ( 工一) ，) ) z ( 6 ) b 样条核函数 x ( x ，y ) = 雪2 + 1 0 y ) 最近，a m a r i 和w u 通过对核函数的黎曼几何分析，提出了利用实验数据 逐步修正原有的核函数7 们，使之更好适应实际问题。这种方法被称为动态核函 数，它不仅可以明显地降低错误识别率，而且还可以减少支持向量的个数，从 而提高识别速度。 1 3 本文内容安排 本文以支持向量机理论为基础，对分类与回归方法进行了一些扩展研究， 并对其在异常值检测及时间序列预测中的应用进行了探讨。全文共分七章，具 体内容安排如下： 第二章详细给出了支持向量机一类分类、二值分类以及回归算法的推导过 程，并在类分类思想的基础上提出一种新的多值分类算法，该方法能有效地 克服通过构造一系列支持向量机二值分类而达到多值分类目的而带来的复杂计 算问题。另外，为了解决大规模数据分类问题，进一步提出该算法的分解形 式，该分解算法不仅能保持良好的分类精度，而且能有效地提高程序的运算速 度。 第三章详细归纳总结了线性规划下的支持向量机方法，并分别针对回归与 分类展开研究。首先在线性规划基础上提出几种新的回归模型，同时比较分析 了它们的预测性能及各自的优缺点。其次，根据第二章中的多值分类思想，提 出一种基于线性规划的多值分类算法，该方法不但简单易行，而且仍能保持较 高的分类精度，同时可以采用其分解形式应用于大规模数据分类中。最后，结 合基于核的主成分提取方法和多值分类算法建立一种人脸识别模型，对o r l 人 脸图像库的识别实验表明所给方法在达到较高识别精度的前提下，训练及识别 时间大大缩短。 第四章针对支持向量机回归模型进行一些扩展研究，具体内容包括以下几 个方面：一、在标准支持向量回归模型的基础上，提出一种单参数约束下的回 归模型，同时证明了所给模型同标准模型是等价的，并且所给方法可以在一定 程度上提高程序的运算速度；二、针对实际回归应用中经常出现异方差性，提 博士学位论文 第一章导论 出了一种加权支持向量回归模型，仿真实验表明，当回归中存在异方差时，所 给算法的预测效果好于标准的支持向量回归模型；三、定义种回归中的预测 信任度概念，使预测结果有了一定的可靠性度量，并且能在定程度上反映数 据中的噪声含量；四、证明了回归与分类之间的等价性，从而为快速分类算法 应用于回归模型中奠定了理论基础。 第五章对数据中的异常值检测进行了探讨。一方面利用结构风险函数较好 的平滑性以及k k t 条件，提出一种回归中的异常值检测方法。另一方面，结 合一类支持向量机和相空间重构理论提出一种时间序列中的异常值检测方法。 仿真实验表明，两种方法是可行的、有效的。 第六章对支持向量机与神经网络之间的关系以及它们在时间序列预测中的 应用进行了比较分析。首先将支持向量回归算法应用于r b f 网络学习中，并且 有效地提高了r b f 网络的泛化能力，从而说明了二者之间的构建思想是一致 的。其次，将支持向量回归的各种版本以及r b f 网络应用于时间序列预测中， 并通过加入不同的噪声水平来比较分析它们的预测性能。 第七章全文总结，并对今后工作提出展望。 博士学位论文 第二章二次规划支持向量机 2 1 前言 第二章二次规划支持向量机 支持向量机是针对二值分类问题提出的，并且成功地应用于解函数回归及 一类分类问题。虽然支持向量机在解决二值分类问题时获得了巨大的成功，但 实际应用中的大量多值分类问题也迸一步要求如何将支持向量机推广到多分类 问题上，目前有以下几种常用的方法： 1 一对多法。其思想是把某种类别