（概率论与数理统计专业论文）fisher和支持向量综合分类器.pdf

学位论文独创性声明 本人承诺：所呈交的学位论文是本人在导师指导下所取得的研究成果。论文中除特别加以标注 和致谢的地方外，不包含他人和其他机构已经撰写或发表过的研究成果，其他同志的研究成果对本 人的启示和所提供的帮助，均已在论文中做了明确的声明并表示谢意。 学位论文作者签名：堡塞堕勇 学位论文版权的使用授权书 本学位论文作者完全了解辽宁师范大学有关保留、使用学位论文的规定，及学校有 权保留并向国家有关部门或机构送交复印件或磁盘，允许论文被查阅和借阅。本文授权 辽宁师范大学，可以将学位论文的全部或部分内容编入有关数据库并进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文，并且本人电子文档的内容和纸质 论文的内容相一致。 保密的学位论文在解密后使用本授权书。 学位论文作者签名：盟童孽一 指导教师签名：二b 丑立! l 签名日期：力io 年6 月7 日 辽j 2 师范人学硕十研究生学位论文 摘要 支持向量机是由v a p n i k 教授于2 0 世纪9 0 年代提出的一种新的机器学习算法，它 建立在v c 维理论和结构风险最小化原则基础上，根据小样本的信息在模型的复杂度和 期望风险之间寻求最佳折中，能够获得更好的泛化能力，其学习过程只需求解一个凸二 次规划问题。近几年，支持向量机在理论研究和算法实现方面都取得了突破性进展，是 数据挖掘中的一项新技术，其卓越的学习性能，使得该技术成为机器学习领域新的研究 热点，并且逐渐成为克服“过学习 和“维数灾难 等传统困难的强有力手段。目前， 它已经在许多领域得到了成功的应用，比如手写体数字识别、文本自动分类、人脸检测 等。 f i s h e r 线性判别分析的核心思想就是寻找最佳投影方向，使得样本在该方向上作投 影后，类内离散度尽可能的小，。类间离散度尽可能的大。基于f i s h e r 线性判别又介绍 了非线性分类方法核的f i s h e r 判别分析，其基本思想是首先将所有样本映射到某 个特征空间中，然后在该特征空问中进行f i s h e r 线性判别，从而实现了原输入空间的 非线性判别。 结合f i s h e r 判别分析和支持向量机的优点，提出了一种新的分类算法一f i s h e r 和 支持向量综合分类器( f i s h e r s u p p o r tv e c t o rc l a s s i f i e r ，简称f s v c ) 。该分类器的 核心思想就是寻找最优分类面的法向量w 。，使得样本向量在w + 上做投影后，不仅使分 类间隔达到最大，而且使类内离散程度尽可能地小。对于线性情况，可以转化为传统的 支持向量机求解，而不需要设计新的求解算法。对于非线性情况，利用再生核理论推导 出新的求解算法。最后，用五大训练数据集对f s v c 算法进行了测试，实验结果表明， 该分类器具有很高的准确度和可靠性。 关键词：支持向量机；f i s h e r 判别；分类问隔；类内离散程度；再生核理沦 辽宁师范大学硕+ 研究生学位论文 f i s h e r s u p p o i r tv e c t o rc l a s s i f i e r 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 san e w m a c h i n el e a r n i n gm e t h o dt h a tp r o p o s e db y v a p n i kd u r i n gt h e 19 9 0 s i tb a s e so nt h ev ct h e o r ya n dt h ep r i n c i p l eo fs t r u c t u r a lr i s k ，i t a l w a y sp e r f o r m sw e l li nm a n ya p p l i c a t i o n sw i t hh i g hg e n e r a l i z a t i o nb e c a u s eo fi t sb e t t e r t r a d e - o f fb e t w e e nt h ec o m p l e x i t yo fm a c h i n e sa n de m p i r i c a lr i s k s t h el e a r n i n gp r o c e s so f s v mo n l yn e e d st os o l v eac o n v e xq u a d r a t i cp r o g r a m m i n g r e c e n t l y ，s v mh a sm a d eg r e a t p r o g r e s si nt h e o r e t i c a ls t u d ya n da l g o r i t h m i cr e a l i z a t i o na n dh a sb e c o m ean e wt e c h n i q u eo f d a t am i n i n g b e c a u s eo fi t se 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 ，i th a sb e c o m ean e wh o tr e s e a r c h f i e l di nt h em a c h i n el e a r n i n ga r e aa n das t r o n gw a yt 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 h a so v e r f i t t i n g ，d i m e n s i o nd i s a s t e r ，e t c n o w a d a y s ，i th a ss u c c e s s f u la p p l i c a t i o n si nm a n yf i e l d s ， h a n d w r i t i n gd i g i tr e c o g n i t i o n ，t e x ta u t o c a t e g o r i z a t i o n ，f a c ed e t e c t i o na n d s oo n t h ec e n t r a li d e ao ff i s h e rl i n e a rd i s c r i m i n a n ta n a l y s i si st h a tt h eo p t i m a ld i r e c t i o ni s f o u n da l o n gw h i c ht h es a m p l e sa r ep r o j e c t e ds ot h a tw i t h o u t - c l a s ss c a t t e ri sk e p ta sb i ga s p o s s i b l ew h i l ew i t h i n c l a s s s c a t t e ri s k e p t a ss m a l la sp o s s i b l e b a s e do nf i s h e rl i n e a r d i s c r i m i n a n ta n a l y s i s ，an o n l i n e a rs o r t i n ga l g o r i t h m ( k e m e lf i s h e rd i s c r i m i n a n ta n a l y s i s ) i s p r o p o s e d ，t h ep r i m a r yi d e ai st h a ti tm a p sa l lt h es a m p l e st oac h a r a c t e rs p a c ef i r s t l ya n dt h e n u s e sf i s h e rl i n e a rd i s c r i m i n a n ta n a l y s i st or e a l i z et h en o n l i n e a rd i s c r i m i n a n ta n a l y s i si nt h e o r i g i n a li n p u ts p a c e w i t hc o m b i n a t i o no fa d v a n t a g e so f b o t hf i s h e rd i s c r i m i n a n ta n a l y s i sa n ds u p p o r tv e c t o r m a c h i n e s ，t h ep a p e rd e v e l o p san o v e lc l a s s i f i c a t i o na l g o r i t h m ，c a l l e df i s h e r s u p p o r tv e c t o r c l a s s i f i e r t h ec e n t r a li d e ai st h a tt h ev e c t o r wo ft h eo p t i m a lh y p e r p l a n ei sf o u n da l o n g w h i c ht h es a m p l e sa r ep r o j e c t e ds u c ht h a tt h em a r g i ni sm a x i m i z e dw h i l ew i t h i n - c l a s ss c a t t e r i sk e p ta ss m a l la sp o s s i b l e i nl i n e a rc a s e ，i tc a nb ec o n v e r t e dt ot r a d i t i o n a ls u p p o r tv e c t o r m a c h i n e s ( s v m ) t os o l v ea n dd o e s n 。tn e e dt od e s i g nn e wa l g o r i t h m s i nn o n l i n e a rc a s e ，w e c a nc o n c l u d et h a tan e wa l g o r i t h mb yt h er e p r o d u c i n gk e r n e lt h e o r y a tl a s t ，t h i sp a p e ru s e f i v ed a t as e t st ot e s tf i s h e r s u p p o r tv e c t o rc l a s s i f i e ra l g o r i t h m ，t h et e s tr e s u l ts h o w st h a tt h e f i s h e r s u p p o r tv e c t o rc l a s s i f i e re s t a b l i s h e dh a s ah i g ha c c u r a c ya n d r e l i a b i l i t y 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 ；f i s h e rd i s c r i m i n a t i o n ；m a r g i n ；w i t h i n c l a s ss c a t t e r ； r e p r o d u c i n gk e r n e lt h e o r y 辽宁师范大学硕士研究生学位论文 目录 摘要m a b s t r a c t i i i 1 绪论1 1 1 课题的研究背景及其意义l 1 1 1 研究背景l 1 1 2 研究意义1 1 2 本文的组织结构2 2 统计学习理论与支持向量机的基本原理3 2 1 统计学习理论简介3 2 1 1v c 维- 3 2 1 2 推广性的界4 2 1 3 结构风险最小化原则一4 2 。2 线性支持向量机5 2 2 1 线性可分支持向量机6 2 2 2 线性不可分支持向量机9 2 3 核函数：1 1 2 3 1 核函数的基本概念与性质“ 2 3 2 常用的一些核函数1 2 2 4 非线性支持向量机、1 3 3f i s h e r 判别分析1 5 3 1 引言15 3 2 线性判别分析法1 5 3 3f i s h e r 线性判别分析法16 3 3 1f i s h e r 的基本思想16 3 3 2 一些基本概念17 3 3 3 判别准则18 3 4 核的f i s h e r 判别分析法2 0 4f i s h e r 和支持向量综合分类器2 4 4 1 引言2 4 4 2 线性可分情形2 4 v f is h e r 和支持向量综合分类器 4 3 线性不可分情形2 5 4 4 非线性情形2 6 4 5 实验结果及分析2 8 结论与展望3 0 参考文献3 1 攻读硕士学位期间发表学术论文情况3 3 致谓 3 4 v i 辽宁师范大学硕士研究生学位论文 1 绪论 1 1 课题的研究背景及其意义 1 。1 1 研究背景 f i s h e r 线性判别是由r a f i s h e r 于1 9 3 6 年首先提出的，其基本思想就是寻找最佳 投影方向，将n 维空间的所有样本投影到该方向上，使得投影后的样本类内离散度最小， 类问离散度最大，实现了n 维空间中分类问题向一维空间中分类问题的转化，从而有效 地克服了“维数灾难”。 2 0 世纪7 0 年代后期以来，v a p n i k 等人就开始了统计学习理论方面的研究，他们做 了大量基础性的工作，但当时并未引起人们的重视。直到9 0 年代，它才形成了一个较 为完善的理论体系，而且神经网络等其他学习方法遇到了很大的困难，于是许多学者开 始逐步关注统计学习理论这一领域。 2 0 世纪9 0 年代中期，v a p n i k 与他领导的a t tb e l l 实验室小组提出了基于v c 维 理论和结构风险最小化原则的支持向量机算法，使得统计学习理论得到了进一步的丰富 与发展。自从1 9 9 9 年，将核技巧用于空间变换，并将其成功的应用于支持向量机中， 这就进一步完善了该算法。 借鉴核函数在支持向量机中成功应用的思想，将核函数用到了f i s h e r 线性判别中， 提出了核的f i s h e r 判别分析法，拓宽了f i s h e r 判别的应用范围。 由于支持向量机和f i s h e r 判别具有优越的理论基础和实用价值，在文献 1 中，提 出了f i s h e r 大间距线性分类器，但它仅限于线性情况下的分类问题，而我们遇到的大 多数是非线性问题，于是本文提出了f i s h e r 和支持向量综合分类器。 1 1 2 研究意义 支持向量机专门用于研究有限样本的学习问题，其优越性主要表现在它是建立在结 构风险最小化原则的基础上。由于具有出色的学习性能，支持向量机成为近几年机器学 习领域中的一大研究热点，备受国内外众多学者的关注，出现了许多关于支持向量机的 改进算法。本文将f i s h e r 判别分析法中类内离散度最小这一思想应用到支持向量机中， 得到一个新的算法f i s h e r 和支持向量综合分类器，通过实验证明，该算法明显优于 其它算法( 标准支持向量机、f i s h e r 判别分析法) ，可以得到相对可靠地识别率，具有 很强的实用价值和应用6 可景，凶此有必要进行研究，希望今后我们能进一步拓宽其应用 领域，解决更多的实际问题。 f is h e r 和支持向量综合分类器 1 2 本文的组织结构 全文共分四章。 第一章、绪论。 主要阐述了f i s h e r 和支持向量综合分类器的研究背景及意义。 第二章、统计学习理论与支持向量机的基本原理。 本章首先介绍了统计学习理论的核心内容( v c 维、推广性的界、结构风险最小化原 则) ，随后详细介绍了支持向量机的数学模型，并分析了核函数的特性。 第三章、f i s h e r 判别分析。 本章讨论了f i s h e r 线性判别的思想与判别准则，以及核的f i s h e r 判别分析法。 第四章、f i s h e r 和支持向量综合分类器。 本章先是给出了f i s h e r 和支持向量综合分类器在线性情况下的数学模型，根据核 理论，又给出了其在非线性情况下的模型以及应用。 最后给出了全文的总结，并指出了未来的研究方向。 2 辽，j 2 师范大学硕士研究生学位论文 2 统计学习理论与支持向量机的基本原理 2 1 统计学习理论简介 传统统计学主要研究渐进性理论，只在无穷多样本时，算法才合理。而实际中的样 本通常是有限的，这就存在一定的局限性。2 0 世纪7 0 年代后期以来，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 ： ( 1 ) 关于统计推断一致性的充要条件的一系列概念。 ( 2 ) 在这些概念基础上的反映学习机器推广能力的界。 ( 3 ) 在这些界的基础上的针对小样本数的归纳推理原则。 ( 4 ) 实现这种新的推理的方法。 其中核心内容就是v c 维、推广能力的界、结构风险最小化原则。 2 1 1v c 维 统计学习理论定义了许多关于函数集学习性能的指标，其中最重要的是v c 维，它 是由v a p n i k 和c h e r v o n e n k i s 提出的。在模式识别中，v c 维的直观定义1 是：加入存在 一个有h 个样本的样本集能够被一个函数集中的函数按照所有可能的2 “种形式分开，则 称函数集能够把样本数为h 的样本集打散。指示函数集的v c 维就是用这个函数集中的 函数所能打散的最大样本集的样本数目，换句话说，如果存在h 个样本的样本集能够被 函数集打散，而不存在有h + 1 个样本的样本集能够被这个函数集打散，则这个函数集的 v c 维就是h 。一般实值函数集的v c 维可以通过一个阈值把实值函数转化为指示函数来 定义。 v c 维反映了函数集的学习能力，一般地，v c 维越大，学习机器越复杂，目前还没 有计算任意函数集v c 维的通用方法，只知道一些特殊函数集的v c 维，如1 9 维线性空问 中线性函数集的v c 维为n + l 等，对于较复杂的学习机器，v c 维的确定有一定的困难， 这仍是一个有待于研究的问题。 将该 式( 2 1 ) 说明了学习机器的实际风险是由两部分组成的：一部分是训练样本的经 验风险如，( 厂) 。另一部分是置信区间巾( h 1 ) ，它与n 、学 - j 机器的v c 维以及训练样本 数目有关，并且巾( h ，) 随着h ，的增大而增大。所以当训练样本有限时，学习机器的 v c 维h 越高，置信区间就越大，这样就可能加剧实际风险与经验风险之间的差距，从而 产生了“过学习”现象，因此要对未来样本又较好的推广性，不仅要使经验风险最小， 而且要使v c 维尽量小，以缩小置信范围。 2 1 3 结构风险最小化原则 由上面的讨论可得以下结论： 定理h 1 ：设h 为f 的v c 维，z 是训练集所含样本点个数，如果满足条件d h h ( 1 n ( 2 l 办) 十1 ) + 1 n ( 4 5 ) l 4 ，则对于任意的概率分布p ( x ，y ) 和任意的6 ( o ，l 】，f 中的任意假设厂都可使得下列不等式至少以卜6 的概率成立 r ( f ) n 如妒( 厂) + ( 2 2 ) 式( 2 2 ) 右端的两项之和称为结构风险，其中第二项也称为置信区间。当集合f 比较大时，选择合适的厂，使得( f ) 比较小，而此时集合f 的v c 维比较大，也会使 得置信n _ f 日- j 比较大。反之，集合f 比较小时，其v c 维会降低，置信区间会变小，而如，( 厂) 有可能增大。 为此统计学习理论提出了一种新的方法，即把函数集构成一个嵌套函数子集序列， 使各个子集按照v c 维的大4 , h b 序，每个函数子集中寻找最小经验风险，在子集问折中 考虑了置信区间和经验风险，以获得最小的实际风险，这就是结构风险最小化原则( s r m ) 的思想。 4 定义：( 结构风险最小化原则) h 3 结构风险最小化原则是寻找一个函数厂，使得式 ( 2 2 ) 的右端所示的结构风险达到最小值。例如适当选择一系列嵌套的函数集 e lcecf o _ 1 在每个e 中找出使得经验风险最小的函数z ，得到一系列函数 ，以小z ，六“ 考查与无相应的结构风险随n 的变化情况，可以发现： ( 1 ) 置信区间随着n 的增大而增大， 因为e 得v c 维是递增的吃一。吃吃。 ( 2 ) 经验风险随着n 的增加而减小， 即如，( z 一。) ( z ) ( 卅) 因为e 是嵌套的；结构风险最小化原则就是要选择适当的以，使得置信区间与经验 风险之和达到最小，由此得到相应的函数f 。 ” o 2 2 线性支持向量机 在统计学习理论的基础上，根据结构风险最小化原则，由v a p n i k 于1 9 9 5 年提出了 一种新的机器学习算法支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) ，支持向量 机构成了数据挖掘的一项新技术，是借助于最优化理论解决机器学习问题的新工具，并 且近年来其理论研究、算法实现、学习性能等方面都有了突破性进展，其优越性主要表 现在：( 1 ) 支持向量机是专门针对有限样本，根据结构风险最小化原则，尽量提高学 习机器的泛化能力。( 2 ) 引入m e r c e r 核实现线性算法的非线性化，并且有效地解决了 “维数灾难”问题。( 3 ) 支持向量机是一个凸优化问题，因此局部最优解一定是全局 最优解，避免了多解性。由于其出色的学习能力和泛化性能，该技术己成为机器学习领 域的研究热点，并且在很多领域得到了成功的应用，比如手写体数字识别，6 | 、人脸检测 、故障检测睁1 0 1 、网络入侵检测n 、数据挖掘n2 。、生物信息学n 3 叫引、时间序列预测n 6 ，盯1 等方面，日益受到人们的高度重视。 支持向量机分为支持向量分类机和支持向量回归机，本文只讨论支持向量分类机， 而且只研究两类分类问题( 尽管它在多类分类中也有很广泛应用) ，我们知道通过一些 样本的特征进行推断新样本的情况，这类问题称为分类问题，也称为模式识别问题。它 大体上可分为三种类型，分别是线性可分问题( 可以用一条直线把训练集正确的分开) 、 线性不可分问题( 可以用一条直线大体上把训练集j f 确的分开) 、非线性可分问题( 用 直线划分会产生很大的误差) 。我们在实际应用中所遇到的大多足非线性可分问题，而 f i s h e r 和支持向鼍综合分类器 支持向量机的研究最初是针对模式识别中的线性可分问题，本节主要介绍前两种类型， 即线性支持向量分类机，首先介绍线性可分支持向量机，随后介绍线性不可分支持向量 机。 2 2 1 线性可分支持向量机 用数学语言可以把两类分类问题描述如下： 定义2 2 1 ：( 两类分类问题) 给定训练样本集t = 眠，m ) ，仗，欣) ，b ，乃) ) ，其 中r ”称为输入或模式，其分量称为特征，y i l ，一1 ) 称为输出，( t ，乃) 称为训练点， f = 1 ，2 ，为训练样本数目。目的是寻找r ”上的一个实值函数g ( x ) ，利用决策函 数厂( x ) = s g n ( g ( x ) ) 推断任一模式x 相对应的输出y 值是1 还是一1 。 当g ( x 1 为线性函数时，该分类问题就称为线性分类问题：否则称为非线性分类问题。 所以说求解两类分类问题，实质上就是找到一个把r ”上的点尽可能j 下确的分成两 部分的判别函数。 定义2 2 2 ：如果存在一个分类超平面( w x ) + 6 = 0 ，使得对所有使只= 1 的下标f ， 有( w _ ) + 6 1 ，而对所有使乃一1 的下标f ，有( w _ ) + 6 - 1 ，则称训练集t 是线性 可分的，也称相应的分类问题线性可分。 由于任意一个超平面( w x ) + 6 = 0 可以有许多不同的参数对( w ，b ) 来表示，为了避 免不同参数对表示同一超平面这种情况发生，下面引入正确划分训练集t 的超平面的规 范形式： 定义2 2 3 h 1 ：如果训练集t 是线性可分的，满足只( w x ，) + 6 ) 0 i = 1 ，2 ，且 ，鲤璺f l ( w 蕾) + 6 i = 1 ，则称该超平面( w x ) + 6 = 0 为关于训练集t 的规范超平面。 可以证明如下定理： 定理2 2 1 h 1 ：如果训练集t 是线性可分的，则任意正确划分训练集的超平面具有唯 一的规范形式。 定理2 2 2 n 3 ：如果训练集t 是线性可分的，则超平面( w x ) + 6 = 0 是规范超平面的 充要条件是咒 ( w 薯) + 6 1 ，i = 1 ，2 ，且，鳃n ，y i ( w 。薯) + 6 ) = 1 。 有了以上定理的保证，如无特别说明，以下所提到的超甲而均是规范超甲面。 6 辽。j 。师范人学硕士研究生学位论文 定义2 2 4 ：如果样本数据可以无误差的被划分，并且每一类数据离超平面距离最 近的向量与超平面之间的距离最大，则称这个超平面为最优分类超平面。 该最优分类超平面可以表示为如下形式：( w x ) + 6 = 0 ，其中w 称为权重向量，b 称 为偏置。 支持向量机就是从线性可分情况下的最优分类超平面发展而来的，其基本思想如图 所示： h 最大分类间隔2 1 t w l i 图2 1 最优分类超平面示意图 f i g 2 1o p t i m a ls e p a r a t i n gh y p e r p l a n e 图2 1 中。代表y i = 1 对应的训练样本，代表只= 一1 对应的训练样本，日为最优 分类超平面，可表示为( w x ) + 6 = 0 。鼠和垦分别为过离最优分类超平面最近的样本 且与h 平行的超平面，称为边界超平面，h 可表示为( w x ) + 6 = l ，儡可表示为 w x ) + 6 = 一1 ，它们之问的距离叫做分类间隔( m a r g i n ) ，易知分类间隔为2 l l w l l 。 根据上面的讨论可知，最优分类超平面不但能把两类样本正确的分开( 即要求它满 足” ( w t ) + 6 l ，f = l ，2 - 1 ) ，而且要使分类间隔2 1 1 w l i 最大( 即要求i m i 最小) ， 根据结构风险最小化原则，前者是保证经验风险最小( 为0 ) ，后者是对推广能力的控 制，分类间隔最大，v c 维就最小，置信区间就最小，从而使真实风险就最小。 所以在线性可分情况下，求最优分类超平面问题就转化为求解二次规划问题，即有 1 m i n - 2 (3)_itwll 2 2 ” ” s t 只【( w 一) + 6 j i f = 1 , 2 z 7 f i s h e r 和支持向量综合分类器 具优化函数是二次型的，约束条件是线性的，因此是一个典型的二次规划问题，具有唯 一的极小点，可以利用l a g r a n g e 乘子法求解。 引入l a g r a n g e 乘子a ，0 ，i = 1 ，2 z 则l a g r a n g e 函数为 三( 心抽) = 却w j l 2 _ 仅， 只 ( w ，薯) + 叼一1 ) ( 2 4 ) 令笔掣一善鹏删 汜5 ， 笔掣= 李鹏= 。 汜6 ， 由( 2 5 ) 和( 2 6 ) 可得到 w = ”仅，薯 ( 2 7 咒q ，= 0 ( 2 8 ) 将( 2 7 ) 代入( 2 4 ) 并考虑( 2 8 ) 可以得到 q ( 仅) 2 仅，一寺仅，o c ，y , y j ( x i 一) i = li = 1i = l 于是得到优化问题( 2 3 ) 的对偶形式： m a xe o t , 。一寺a ，仅，只乃( 薯_ ) l = 1二，- l ，= l ( 2 9 ) s t ，形= o i = 1 0 l 。0z = 1 , 2 ， 这样把原始问题转化为对偶问题计算的复杂度不再取决于空间的维数，而是取决于 样本的个数。 所以求解最优分类面的问题就转化为对仅，求解以下的优化问题： 1l|l m i n 寺叩， 乃( 薯o ) 一仅， ( 2 1 0 ) ， s t y q ；y i ：0 一一 _ l 仅f 0 若a = q ? ，仪2 9 。a j ) ，为其最优解，则幽( 2 7 ) 可得w * - - - - 少， 。 辽宁师范大学硕士研究生学f 市论文 再根据优化理论中的k a r u s h k u h n k u c k e r ( k k t ) 条件，其最优解仅+ 必须满足如下 表达式： 仅? & 五) + 6 】一1 ) = 0 ，所以对于a ? = o 所对应的样本在分类中不起什么作 用，只有a ? o 所对应的样本才对分类结果起作用，而且它们一般只占全体样本的很少 一部分，体现了最优解的稀疏性，大大压缩了有用的数据样本，于是我们引出以下定义： 定义2 2 5 ：( 支持向量，s u p p o r tv e c t o r ，简称s v ) 如果训练集中输入样本鼍所 对应的仪? o ，则称五为支持向量。 下面求b ： 任意取0 l o ，由k k t 条件得仪；，【( w x ) + 6 】一1 - - o ，根据w = 圭y ，a _ 得 i = l i ， 6 2 y j 一 仅融_ ) i = l 则最优分类器为 ) = s g n l 窆 b _ ) + 6 j ，给定一个新的输入x 便可以对其进 l 1 = 1j 行分类，由于非支持向量所对应的仅? 均为0 ，因此上式求和实际上只对支持向量进行。 2 2 2 线性不可分支持向量机 对于线性不可分问题，任何分类超平面都不能将两类样本完全正确的分开，但是 可以将其近似的分开，这时就不能再要求所有的训练样本都满足约束条件 只 ( w t ) + 6 】1 ，f _ 1 , 2 ，因为此时对偶问题的目标函数q ( 仅) 的最大值为0 0 ，所以 必须“软化 对间隔的要求，即允许不满足以上约束条件的样本点存在，为此对每个训 练样本引入一个非负松弛变量鼍，汪1 , 2 - i ，它可看作训练样本关于分类超平面的 偏差，从而可以得到“软化 的约束条件只【( w 誓) + 6 l 一亏，净1 , 2 ，。 我们仍然希望分类间隔2 川w l i 尽可能的大，同时希望错分程度尽可能的小，这样将 求解最优超平面转化为求解下面凸二次规划问题： m i n 丢h 2 + c 圭亏， 厶 1 = 1 s t 虹( w x ) + 6 l 一芎， 芎，0 9 f = 1 2 ， i = 1 , 2 z ( 2 1 1 ) f is h e r 和支持向量综合分类器 目标函数的前一项反映了置信区间，后一项反映了训练误差，总和反映了结构风险 ， 最小化原则，其中亏，描述了整个训练集被错分的程度，当芎，充分大时，样本点总可以 l = l 满足上述的约束条件，但应设法避免鼍，取太大，所以必须对它们进行惩罚，c ) o 就是某 个事先取定的惩罚参数，用来控制样本偏差与机器泛化能力( 与+ l l w l l 2 有关) 之间的平 衡，c 越大，表示对错分样本的惩罚越大。 同样利用l a g r a n g e 乘子法，引入l a g r a n g e 乘子仅，o ，y ，0 ，忙1 ，2 ，构造 l a g r a n g e 函数 三( w ，啦，y ) = 钏w 肛羔j ” w x , ) + q - 1 ) 一丫，号， ( 2 1 2 ) 令等掣一善鹏卿 业o 型b = 善i 鹏= 。 a l i ( w - , b , 一o t ) ：c 一仅，一丫，：o u ， 由( 2 1 3 ) 、 ( 2 1 4 ) 、( 2 1 5 ) 可得到 肛善鹏薯 ， 咒仪，= o ( 2 1 7 ) c 2 仅，+ 丫， 将( 2 1 6 ) 代入( 2 1 2 ) 并考虑( 2 1 7 ) ( 2 1 8 ) 可以得到 l1|l q ( 仅) 2 仅，一去a ，y t y j ( x ，_ ) = ii = li = l 于是得到优化问题( 2 1 1 ) 的对偶形式： 11ll m a x 。一寺q 。仪，y ，乃( x j _ )u 1o _ | j “j j ， s t 仪，乃= o i = l 0 a c 1 0 ( 2 1 8 ) ( 2 1 9 ) ，、，、， 3 4 5 6 l l l l 2 2 2 2kllk 辽j 。师范大学硕十研究生学位论文 即m i n 丢仅，仅，只乃( 薯_ ) 一仅， ( 2 2 0 ) s t o 【，乃= o 0 仅i ci = 1 , 2 - i 若0 【= q ? ，仅；n 为