（应用数学专业论文）基于核函数的非线性判别分析——引入shannon尺度核函数的核fisher判别.pdf

基于核函数的非线性判别分析 一一引入s h a n n o n 尺度核函数的核f i s h e r 判别 专业名称：应用数学 硕士生：张玉姬 指导老师：张磊副教授 摘要 本文在经典的f i s h e r 判别分析与核函数f i s h e r 判别分析的基础上，依据 m e r c e r 核函数理论与多分辨率分析理论，参考尺度核支持向量机的做法，把 s h a n n o n 尺度函数作为核函数或核函数的一部分应用到核f i s h e r 判别法当中。 基于f i s h e r 准则的判别方法已成为特征抽取的最好方法之一，另一方面， 在f i s h e r 思想基础上，w f l k s 等创立的经典f i s h e r 判别法可以直接推广到多类问 题上，故基于核函数的f i s h e r 判别法在很多方面得到广泛的应用。根据小波分 析中的多分辨率分析理论，尺度函数通过平移可以生成r ( 科) 的子空间的一组 完备的基，从而，若把尺度函数应用到核函数中，训练分类器所得到的决策方 程便可逼近r ( 瓞刀) 的子空间上的任意分界面。 本文的主要创新之处：给出了尺度函数可以成为一个允许核函数的条件， 并且把一允许尺度核函数一- - s h a n n o n 尺度函数与核f i s h e r 判别法相结合，推 导了算法流程，并且尝试把s h a n n o n 尺度核函数与线性核函数结合所得的混合 核函数应用到核f i s h e r 判别中。 基于径向基核函数的支持向量机分类器是得到认可的优秀的分类器，本文 的实证分析将把基于径向基核函数的支持向量机分类器做为参照。应用到u c i 数据集上时，实验结果显示，基于s h a n n o n 尺度核函数的f i s h e r 判别法的分类 效果可以媲美径向基核函数的f i s h e r 判别，而且把s h a n n o n 尺度核函数与线性 核函数结合所得的混合核函数在核f i s h e r 判别中的分类效果甚至还优于基于径 向基核函数的支持向量机分类器。 关键词核函数f i s h e r 判别分析尺度函数s h a n n o n 尺度核函数 n 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 sb a s e do nk e r n e lf u n c t i o n l e a d i n gs h a n n o ns c a l i n gk e r n e lf u n c t i o ni n t ok e r n 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 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 ：z h a n gv u j i s u p e r v i s o r ：a s s o c i a t ep r o f e s s o rz h a n gl e i a b s t r a c t b a s e do nc l a s s i c a lf i s h e rd i s c r i m i n a n ta n a l y s i sa n dk e r n e lf i s h e rd i s c r i m i n a n t a n a l y s i s r e f e r e n c et ot h em e t h o do fs c a l i n gk e m e ls u p p o r tv e c t o rm a c h i n e s t h e s h a n n o ns c a l i n gf u n c t i o ni su s e da st h ek e m e lf u n c t i o no rp a r to ft h ek e m e lf u n c t i o n , t h a ti sa p p l i e dt ot h ek e m e lf i s h e rd i s c r i m i n a n ta n n l y s i s a c c o r d i n gt ot h et h e o r yo f m e r c e rk e r n e la n dm u l t i r e s d u t i o na n a l y s i s ( m r a ) i ti sw e l l k n o w nt h a tt h ed i s c r i m i n a n tb a s e do nf i s h e rc r i t e r i o nh a sb e c o m eo n e o ft h em o s te 伍e c t i v et e c h n i q u e sf o rf e a t u r ea b s t r a c t i o n o nt h eo t h e rh a n d c l a s s i c a l f i s h e rd i s c r i m i n a n t a n a l y s i sc a nb ee x t e n d e dd i r e c t l y t om u l t i c l a s sp r o b l e m , t h e r e f o r et h ef i s h e rd i s c r i m i n a n ta n a l y s i sb a s e do nk e r n e lf u n c t i o ni sa p p l i e db r o a d l y i nm a n yf i e l d s b a s e do nt h em u l t i - r e s d u t i o na n a l y s i s ，s c a l i n gf u n c t i o nc a ng e n e r a t e as e to fc o m p l e t eb a s e si nt h es u bs p a c eo fq u a d r a t i cc o n t i n u o u si n t e g r a ls p a c eb y t r a n s l a t i o n h e n c e ，t h ed e c i s i o nf u n c t i o no b t a i n e db yt r a i n i n gac l a s s i f i e r , w h i c hi s b a s e do nt h es c a l i n gf u n c t i o na sak e r n e l ，c a ns i m u l a t ea n ys e p a r a t i n gh y p e r p l a n ei n t h a ts u bs p a c e t h em a i ni n n o v a t i o no ft h i sp a p e ri st h a t ，g i v i n gt h ec o n d i t i o n sh e was c a l i n g f u n c t i o nc a nb e c o m eak e n n e lf u n c t i o n , a n dc o m b i n i n gas c a l i n gk e r n e l f u n c t i o n o s h a n n o ns c a l i n gf u n c t i o nw i t hk e n n e lf i s h e rd i s c r i m i n a n t a n a l y s i s b e s i d e s ，i tg i v e st h ed e r i v a t i o no ft h ea l g o r i t h mp r o c e s s e s a l s oah y b r i dk e r n e l f u n c t i o ng o t t e nb yc o m b i n i n gs h a n n o ns e a l i n gk e r m e lf u n c t i nw i t hl i n e a rk e n n e l f u n c t i o mw h i c hi su s e da st h ek e r n e lf u n c t i o l l i sa p p l i e dt ot h ek e r n e lf i s h e r d i s c r i m i n a n ta n a l y s i s d u et os u p p o r tv e c t o rm a c h i n e sb a s e do nt h er a d i a lb a s i sf u n c t i o nk e r n e li sa l l e x c e h e n tc l a s s i f i e r , t h ee m p i r i c a la n a l y s i si n t h i sp a p e rw i l lm a k ei ta sar e f e r e n c e 肌i l ep r a c t i s i n gi to nau c id a t as e t ，t h ee x p e r i m e n t a lr e s u l t ss h o wt h a t ，t h e c l a s s i f i c a t i o na b i l i t yo ft h ef i s h e rd i s c r i m i n a n ta n a l y s i sb a s e do ns h a n n o ns c a l i n g k e m e lf u n c t i o ni sc o m p a r a b l ew i t ht h a to ft h ef i s h e rd i s c r i m i n a n ta n a l y s i sb a s e do n r a d i a lb a s i sf u n c t i o nk e r n e l b e s i d e s ，t h ec l a s s i f i c a t i o n a b i l i t yo ft h e f i s h e r d i s c r i m i n a n ta n a l y s i sb a s e do n ah y b r i dk e m e lf u n c t i o ng o r e nb yc o m b i n i n g s h a n n o ns c a l i n gk e n n e lf u n c t i nw i t hl i n e a rk e r m e lf u n c t i o ne v e nf a i r l yb e t t e rt h a n t h a to fs u p p o r tv e c t o rm a c h i n eb a s e do nr a d i a lb a s i sf u n c t i o nk e r n e l k e yw o r d sk e n n e lf u n c t i o n , f i s h e rd i s c r i m i n a n ta n a l y s i s ，s c a l i n gf u n c t i o n , s h a n n o ns c a l i n gk e n n e lf u n c t i o n 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：吞 易姬 日期：湘叩年f 月万日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学 位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查 阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其 他方法保存学位论文。 学位论文作者签名：球乏垭导师签名： 日期：1 年j 月冶日 日期：了 日 第1 章前言 1 1 判别分析方法的研究背景 在人们的生活生产中，产生和收集了有用而海量的信息数据库，一种自然的 需求人们希望用计算机帮助分析数据和理解数据，帮助他们基于丰富的数据 做出决策1 1 i i 羽。数据挖掘，就是从大量数据中以非平凡的方法发现有用的知识， 是数据库研究、开发和应用的一个活跃分支，而判别分析( d i s c r i m i n a n ta n a l y s i s ) 是数据挖掘的重要组成部分，随着计算机的出现、人工智能的兴起，判别分析在 很多科学和技术领域中得到了广泛的应用，在得到非常多令人满意的结果的同 时，与生物的识别系统相比，判别分析方法的识别能力和鲁棒性还有比较大的进 步空间，还有许多的基础理论和基本方法有待人们去解决，新问题也层出不穷。 判别分析一般由五大部分组成1 3 l ( 见图1 ) ： 图1 判别分析结构图 判别分析的应用范围非常的广泛，尤其在自然科学、社会学及经济管理学科 中其应用之广可与回归分析媲美。以下是判别分析的一些应用实例1 4 j ： ( 1 ) 文字和字符识别。如垃圾邮件过滤、文件处理、文件搜索等。 ( 2 ) 图形图像识别。如人脸图像表情分类、遥感和航空照片分析等。 ( 3 ) 生物医学上的应用。如疾病诊断、生物基因遗传判断等。 ( 4 ) 信息安全。如身份鉴定，病毒过滤等。 ( 5 ) 经济管理学科。如人口收入调查，市场研究等。 判别分析的内容很丰富，方法很多。判别分析按判别的类数来区分，有两类 判别分析和多类判别分析；按区分不同总体的所用的数学模型来分，有线性判别 和非线性判别；按判别时所处理的变量方法不同，有逐步判别和序贯判别，按不 同数学原理可分为概率型判别分析和非概率型判别分析等等。常用的线性判别方 法有距离判别法、f i s h e r 判别法( 典型判别法) 、b a y e s 判别法和支持向量机等。引。 1 2 相关工作及文献综述 本人在本科阶段对线性判别法进行了一定的研究，由于线性判别在实际应用 上有比较大的限制，在此阶段除了继续在这一方面深入学习外，把研究方向侧重 在非线性判别方法上面。核方法把非线性问题线性化，是非线性判别法的研究重 点，尽管径向基核函数已经成为支持向量机算法中应用得最广泛的核函数，且核 函数可推广到模式识别、函数拟合及逼近等很多领域，故核函数、核映射仍然是 研究讨论的热点。在阅读了很多有关书籍和文献后，本人着重对多类问题的 f i s h e r 判别法和核f i s h e r 判别法的模型和其最优权向量求解进行了严格的推导， 并应用到实验当中。在掌握了小波理论中的多分辨分析理论的知识后，验证尺度 函数成为一个允许核函数的条件，参考尺度核最小二乘支持向量机的方法，把 s h a n n o n 尺度函数作为核函数应用到核f i s h e r 判别法中，然后，考虑把s h a n n o n 尺度核函数与其他常用的核函数进行混合，希望得到令人满意的效果，并且对其 作实证分析。 1 3 本文的主要研究工作及成果 f i s h e r 判别法是一种较为简单的线性判别模型，其目的是选择使得f i s h e r 准 则函数达到极值的最佳投影方向p l 【6 1 1 7 1 ，从而使得样本在该方向上投影后，达到 最大的类间离散度和最小的类内离散度，而把核函数方法与f i s h e r 判别相结合 后，可以有效地解决实际中的非线性可分的分类问题，本文把小波理论中的尺度 函数作为核函数应用到核f i s h e r 判别法当中，使得根据f i s h e r 准则函数所得的决 策面函数可以逼近r ( 科) 的子空间上的任意分类面，以达到提高分类效果的目 2 的。经过实验分析得出，基于s h a n n o n 尺度核函数的f i s h e r 判别法对实验数据集 的分类效果可媲美基于径向基核函数的f i s h e r 判别法。对于本文所使用的实验数 据集，基于径向基核的支持向量机有着非常好的分类效果，回代错误只有一个， 本文把线性核函数与s h a n n o n 尺度核函数相结合得到一个混合的核函数，作为核 f i s h e r 判别的核函数，实验结果显示，其分类效果甚至优于基于径向基核的支持 向量，回代错误为零。除此外，本文还对基于s h a n n o n 尺度核函数的f i s h e r 判别 法的泛化能力进行了测试，结果发现该方法对新样本具有较高的识别能力。这表 明，使用尺度函数作为分类器的核函数确实提高了分类器的判别分析能力。 1 4 本文的主要内容 基于核函数的判别方法成为非线性判别最为广泛应用的方法之一，本文针对 核f i s h e r 判别法的核技巧及其特点，把允许尺度核函数一- - s h a n n o n 尺度函数作 为核f i s h e r 判别法的核函数，并作实证分析。除外，把s h a n n o n 尺度函数与线性 核函数混合使用，以求得到更优的分类效果。各章节主要内容如下： 本章简介判别分析的研究背景及个人研究工作，指出本文的意念和目的；第 二章介绍了线性判别方法的概念和线性分类器的设计，并给出本文研究的线性分 类型一一经典的f i s h e r 判别法及其推广和硬间隔支持向量机；在第三章中，给出 了非线性判别分析与核函数的概念和m e r c 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 判别和基于径向 基的支持向量机的分类结果进行了对比分析，得出了实验结论，及本文的研究尚 待解决问题和进一工作展望。其中第四章和第五章是本文的主要工作所在。 3 第2 章线性判别分析方法简介 2 1 线性判别函数的基本概念 在一个d 维的样本空间有样本点；= ( 五，而，) r ，线性判别函数的一般表 达式为： g ( ；) = o h x l + 吐而+ + 勤+ 锄+ l ( 2 1 ) 式中：q ，吐，吼+ 。为加权因子，也称为判别系数3 1 。如果记鬲= ( q ，吐，锄) ， 鬲称为权向量，+ 。是一个常数( 阈值权) ，则 t g ( x ) = x + 吼+ l 例如：若要设计一个一维分类器，使其功能为： 如果x 口，则决策x 属于第1 类g l ； 如果 b x 口， 则决策x 属于第2 类g 2 。 显然，上述问题的判别函数为下列二次函数： g ( x ) = ( x - a ) ( x 一6 ) 二次函数的一般形式为： g ( x ) = c 0q - c l x q - c 2 x 2 + - 4 - c n x ” 我们令 一y = 则g ( x ) 可表示成： m ： 咒 1 x ： 9 口2 嘞 q ： g ( x ) = a 可一y = 窆q 咒 g ( x ) = q 咒 i s o 4 c 0 q ： 巳 ( 2 - 2 ) ( 2 - 3 ) 形如( 2 - 3 ) 的判别函数称为广义线性判别函数。按照上述原理，任何非线性函数 g ( ；) 用级数展开成高次多项式后，都可转化成线性函数来处理【5 1 。 2 2 线性判别分析方法的原理 在一个d 维的样本空间( 记为r d ) 中，有m 个已知的总体g l ，g 2 ，吼，或 者说m 个类，同时有样本点；= ( _ ，屯，勤) r ，它属于而且仅属于这m 个总体中 的一个，判别分析所要解决的问题就是确定这个样本点；具体应该属于哪一个总 得到一系列判别函数蜀( ；) ，g ：( ；) ，g m ( x ) ( 称为分类超平面) ，再利用这些判别 线性实值函数1 3 1 ： f ：x r d 寸r ， 厂( ；) = 蛾五+ 吐而+ + 吻+ 6 这里( 鬲，b ) e r d r 是控制函数的参数，对任意的样本点；= ( 而，恐，劫) r ，决策 r 6 ) o ，则把；判给正类； 如果f ( x ) 0 及 g j ( x ) o ，七 1 ，2 ，m ) ，g j ( x ) 当然，投影到不同方向得到的一维特征对于模式分类的效果可能会有很大的 差别，而由于我们特别关注的是石的方向，在求解最佳方向时我们可令忪= 1 ， 则以就是在鬲方向上的投影3 1 5 悯。可见，使得甲。和甲：最容易区分开的石方 向正是分类超平面的法线方向，f i s h e r 判别法用两个指标定量地衡量分类效果。 1 ) 两类样本投影后的均值之差 e 2 = i 磊一码1 2 ( 2 - 4 ) 其中，厩= 丢喜以，f = 1 ，2 分别是第f 类样本投影后的均值, e 2 标志两类样本之 间投影后的分开程度，从分类的要求来看，它应该越大越好。 2 ) 每一类样本投影后自身的分散程度( 均方差) ( 2 - 5 ) + s ；标志各类样本投影后自身分散程度的总效果，为了在分类中尽量避免两类 混淆，它应该越小越好。 综合上面两条，为了得到满意的分类，应选取使得 ，( 鬲) ：蝉( 2 删 s ：+ s ： 取极大值的鬲作为投影方向1 6 1 1 1 们。 9 2 ，b = zp历一 以 ，l 吩蹦 = # 为了求得最佳投影方向鬲，我们先把，( 鬲) 表示为石的显函数： 记厩= 上n l 壹k = l ，f = l ，2 为第i 类样本的均值( 向量) ，则 厩= 寺喜以= 击善c 面r ) = 面r f ，! n i 童k = l 、1 j = 鬲r 厩 ( 2 7 ) 从而，把( 2 7 ) 式代入( 2 4 ) 式有： i 商一砚1 2 ：l 鬲r 厩一鬲r 而：1 2 = 鬲7 ( 厩一晚) ( 厩一而：) r 云( 2 - 8 ) 记 i = 艺( 一碗) 2 = ( 一而。) ( 一厩) ti = l ，2 k = lk = l 表示第i 类样本自身的分散程度，则 彳+ = ( 以一羁) 2 + ( 以一历：) 2 2 善晒r 。黾- i 一舻厩) 2 + 否晒7 - 2 - 0 3 r r 话2 ) 2 ( 2 9 ) ：面r f 艺( 鞋一厩) ：+ 艺( 霹吨) 2 卢 k = l k = l ：面7 ( 夏+ 夏) 鬲 定义下列矩阵： 样本类间离散矩阵& = ( 厩一历2 ) ( 厩一晚) r 样本类内离散矩阵 昂：写+ 瓦：壹艺( 一而，) ( 一而j ) r i = lk = l 把( 2 8 ) 式和( 2 9 ) 式代入( 2 6 ) 式，并利用上面的定义得 j ( 历) ：孽避 一r c o 。s f i ，c o ( 2 - 1 0 ) 上式就是数学物理方法中著名的广义r a y l e i g h 商。f i s h e r 判别法就是要求投影 方向一c o 使得( 2 1 0 ) 式取得极大值1 3 1 0 下面用l a g r a n g e 乘子法求j ( 一e o ) 的极值点。令分母等于非零常数，即 l o c ：一0 9 r s w a 一, * o 。定义l a g r a n g e 函数： 三( 鬲，a ) ：石r & 鬲一x ( 3 ，昂鬲一c ) 上式两边对石求导并令其等于0 ，得 掣掣：2 ( g 一, o 一允& 鬲) ：0 从上式即得使得，( 鬲) 达到的极大值的石满足： 品鬲= 九勘鬲 ( 2 1 1 ) 显然，是对称的和半正定的，当样本数目刀大于维数d 时，昂是非奇异的。 故有： a 鬲= 聊s , 3 ( 2 - 1 2 ) 这样，问题就转化为求一般矩阵蹄& 的特征值和特征向量，则九是其特征根， 而我们所要求的鬲就是对应的特征向量。 而由于 & 云= ( 厩一碗) ( 厩一碗) ， 鬲= ( 厩一碗) y ( 2 1 3 ) 其中，y = ( 磊一历：) r 鬲是一个标量，所以& 历与( 厩一碗) 同方向，故可以 不必求矩阵聊的特征值和特征向量，将( 2 1 3 ) 式代k ( 2 1 2 ) 式即得最佳投 影方向： 石= 姜蹄( 厩一历：) 孟是一个比例因子，我们关心的是投影的方向石，故可不理会，进而得到最后的 解： c o ：剐( 厩一疡：) 上式的石是使，( 历) 取得极大值的解，它可将样本由d 维空间向一维空间投影， 其投影方向是最佳的，在该投影方向e 分类的效果最好1 6 l l l l l l l 2 l 。 二、多个总体的f i s h e r 判别法 多个总体的f i s h e r 判别法一般也称广义的f i s h e r 判别法，是把f i s h e r 判别法 从两类推广到多类的判别法【6 1 。广义f i s h e r 最佳判别是尝试在输入空间中寻找一 组相互正交的向量集，将输入空间的样本数据分别向这组向量集进行投影，也就 是要找到一组法向互相垂直的线性判别函数，每个判别函数可把样本集中的一类 样本与其他类分开，最后把待测样本判给具有最大决策函数值的那一类。 设样本集同上，x = 墨，而，瓦) ，每个样本是d 维空间上随机向量，样本 类别数，其中傀个样本属于类别g l ，依次类推，个样本属于类别g ，分别 表示为： 墨= 爿，乏，式) ， 置= 并，吃- - 2 ，蕞) ， x n = 镦，i ：，i 孙。 广义f i s h e r 最佳判别是以经典的f i s h e r 判别为基础，将两类模式识别的求解 推广到多类模式识别的求解中。类似上面的推导，广义f i s h e r 判别的最佳投影方 向是使得 厶 ) ：j c o s b = c o ( 2 - 1 4 ) c o 岛国 取极大值的向量组石o = 1 ，2 ，n ) ，其中，每个c o 为d 维列向量，且两两相 互正交。广义f i s h e r 最佳判别的类间离散矩阵 类内离散矩阵 & = ( 厩一历) ( 厩一而) r 1 2 r 一 一 爰一 一 露l 吩胤耐 = 昂 式中，而，= 三n t 羔k = l ，f = 1 ，2 ，表示类别q 的均值向量：历= 丢喜五表示所有 样本的均值向量。 使式( 2 - 1 4 ) 取极大值的第一个向量石是经典f i s h e r 判别法的最佳投影方向， 其物理意义是模式样本集在石方向上的投影使得模式具有极小的类内散布和极 大的类间散布。一般情况下，求出r ( r 1 ) 个线性f i s h e r 判别方向石，( 一0 2 ，瓦后， 第r + 1 个线性f i s h e r 判别方向是在满足正交条件石：。面：o ( i = 1 ，2 ，) ，且使 ( 2 一1 4 ) 式取极大值的向量瓦，一直到求出n 个投影方向为止。一种求解方法为： 类似于两类问题，有式子： a 鬲= 剐s o 设 如扎为矩阵昭& 的最大的n 个特征值，则可选取正交方向组 为丑( 江1 ，2 ，) 对应的特征向量厨，尾，风1 3 1 。 求得正交的最佳投影方向组石，( 0 2 ，瓦后，任意一个样本i 到方向为i 的 投影为： 此时，可根据判别函数： g ( ；) ：鬲；舅，i ：1 ，2 ，n 厂( i ) ：a r g m a x 石o ；孑一反】，i ：1 ，2 ，n i 把i 判给判别函数值最大的那一类，其中6 f ( 扛1 ，2 ，n ) 为待求的决策阈值。 在每个总体互相之间不重叠的情况下，线性判别分析方法的原理保证了广义 f i s h e r 判别法的可行性，但在有总体是重叠的情况下，广义f i s h e r 判别法则存在 不可分区域o “i 。 1 3 2 4 2 线性支持向量机 s v m 是统计学习理论中最年轻的部分，1 9 9 5 年才完成其主要的理论内容，现 在仍然在不断地发展。s v m 的基本思想是根据v a p n i k 提出的结构风险最小化 ( s t r u c t u r er i s km i n i m i z a t i o n ) 原理，通过最大化分类间隔( m a r g i n ) 尽量提高学习机 的泛化能力3 1 1 5 1 。 一、硬间隔支持向量机模型 设有甩个d 维的训练样本i ( f = l ，甩) 分别属于第1 类或第2 类，用类标乃= 1 表示第1 类，只= - 1 表示第2 类。若样本线性可分，则我们可找到线性判别函数： d ( ；) ：鬲卜x + b 这里鬲为d 维向量，b 为偏置项，对f = 1 ，刀，有 或者写成 ( 2 - 1 7 ) 等价于 戒+ 6 甾z 掌三。 一r 一，i 1 f o ， y j = i 矿6 仨一1 加咒：一1 y , ( r q oi + 6 ) 1f o r 汪1 ，珂 从而，分类面可表示为 ( 2 - 1 5 ) ( 2 - 1 6 ) ( 2 1 7 ) ( 2 - 1 8 ) d ( ；) ：云卜x + b ：cf o r 一1 c o ) 到( 2 - 1 s ) 式： y , ( j o ，i + 6 ) 芝卜磊f o r i = 1 ，刀( 2 3 1 ) 1 6 o 图2 4 二维样本集非线性可分的情形 由( 2 - 3 1 ) 式，引入松驰变量后，它允许在一定程度上违反间隔约束，这样在 一般情况下便存在可行解7 - 1 1 0 l 。如图2 4 ，对训练样本i ， f0 色 1 ，则样本薯与分类超平面的距离不满足最大间隔，但还 l 是可以被最优分类超平面正确分类； 如果磊1 ，则样本葺被最优分类超平面错分； l i 毛= 0 ，则样本鼍与分类超平面的距离满足最大间隔，被最优分 l 类超平面正确分类。 在这种情况下，我们要得到的最优分类超平面是使得尽可能少的训练样本具有非 零的松弛变量的那一分类超平面，故必须要： r n i n q ( 鬲) = 日( 考，) ( 2 3 2 ) 鼽吣沪骺z 譬蹴喜吣雅判定分类超平面酬黼 本错分的程度，被错分的样本越多，该值越大。但要在尽可能满足最大间隔的同 时来解问题( 2 3 2 ) 是一件很困难的事情，因为与最大间隔取定为比较小的值来比 1 7 较，最大间隔取得值大的时候，具有非零松弛变量的训练样本肯定要多，此时， 9 ( 董) 的值就会很大，不满足( 2 3 2 ) 式。故此，我们引入间隔参数c 来调节对 i = i 错分的惩罚，它是一个调节要求尽可能多的样本满足最大间隔和尽可能少的样本 具有非零松弛变量两个约束的参数1 1 0 1 1 1 5 l 。这样，问题转化为： 1 1 1 i n q ( 石a 手) = 列鬲8 2 + c 喜第 ( 2 3 3 ) j ，y , ( 7 0 7 i + 6 ) 1 一色f o ，江1 ，万 ( 2 3 4 ) 我们取p = 1 或p = 2 ，由问题( 2 3 3 ) 和( 2 3 4 ) 得出的分类面为软间隔分类 面。当p = 1 时，称为一阶范数软间隔支持向量机( l ls o r m a r g i ns u p p o r tv e c t o r m a c h i n e s ) i 当p = 2 时，称为二阶范数软间隔支持向量机( l 2s o f t - m a r g i ns u p p o r t v e c t o rm a c h i n e s ) 下面以p = 1 时的情况为例，引入两个非负拉格朗日乘子a ，和 屈，类似于硬间隔支持向量面的方法，有： q ( 云 手，云，两= 列面8 2 + c 兰i = 1 色一喜a ， 以西r x i + 6 ) 一1 + 色 一兰t = l 屈色( 2 3 5 ) 其中：夏= ，a ：，a n ) r 和万= ( 岛，殷，成) r 。 对( 2 3 5 ) 式求导并令其为0 ： 坌望塑：垒薹：竺：盟：石 a o q ( e o , b , 毒, a , f 1 ) ：o a 6 o q ( c o ，b ，孝，a ，卢) 元 = 一2u 必 解( 2 3 6 ) 一( 2 - 3 8 ) 式，得到： 石= a ，”i t = l ( 2 - 3 6 ) ( 2 - 3 7 ) ( 2 - 3 8 ) ( 2 - 3 9 ) 一 a ，只= o i = 1 a f + 屈= cf o ，i = 1 ，2 ，疗 再结合k k t 条件： a ， ”( 鬲r i + 6 ) _ 1 + 善扣。加，2 ，” 屈考，= 0f o ri = 1 ，2 ，刀 口f 0 ，屈0 ，考f 0 户， i = 1 ，2 ，甩 我们得到当p = 1 时，问题( 2 - 3 3 ) 、( 2 3 4 ) 的对偶问题为： 一q ( 云) ：窆旷委窆a i a j y y j x 卅ii ( 2 - 4 0 ) s ，v i a f = o o a f cf o r i = l ，刀 ( 2 4 6 ) i = l 可见，一阶范数软间隔支持向量机与硬间隔支持向量机的唯一区别就在于， 一阶范数支持向量机的a ，不能大于间隔参数c 。在实际应用中要根据不同情况来 取定不同的间隔参数值1 0 j 1 1 6 i 。根据上述松弛变量色与是否被错分的关系，有： 当a ，= 0 时，由( 2 4 2 ) 式得邑= 0 ，此时，样本被正确分类； 当o a ， c 时，由( 2 4 2 ) 式得咒( 石7i + 6 ) 一1 + 毛= o ，由( 2 4 1 ) $ i ( 2 4 3 ) 式得色：0 ，从而只( 鬲r i + 6 ) = 1 ，则i 为支持向量。特别地，我们称满足 0 c 的支持向量为极大支持向量( u n b o u n d e ds u p p o r tv e c t o r ) 。 当口，= c 时，由( 2 4 1 ) 和( 2 4 3 ) 式得色0 ，由( 2 4 2 ) 式得 儿( 鬲7i + 6 ) 一l + 喜= o ，故i 为支持向量，我们称满足= c 的支持向量为有界 支持量( b o u n d e ds u p p o r tv e c t o r ) 。此时，5 0 善 o ， 则把；判给第1 类； 如果| 。( ；) 。， 则把；判给第2 类； d ( ；) = 0 ，则x 落在分类超平面上，不可分。 当一阶范数软间隔支持向量机不存在有界支持向量，即不存在训练样本i 同 时满足咒( 石r i + 6 ) 一1 + 色= o 和a i c 时，区域 ；i - 1 d ( ；) 1 是其泛化域，这 与硬间隔支持向量机的一样1 1 0 1 1 1 7 l 。 第3 章非线性判别分析及核方法 3 1 简单的非线性判别函数 由于训练样本空间分布的复杂性，在很多情况下采用线性判别函数往往得不 到令人满意的分类效果。见图3 1 ，给出了两类样本在二维空间的分布，其中， 且和马同属一类，焉为另一类。显然若采用线性判别函数i ，无论判别方向如 何都无法得到满意的分类效果。在这种情况下，我们可以采用分段线性判别函数 i i 或二次判别函数m ，由图可见，后两种判别方法的分类效果较线性判别要好得 多。而非线性分类器的设计与上面介绍的线性分类器设计过程一样，只需在设计 过程中把非线性判别函数的形式设置好”删。 ：l 芝鬈捌生煳。 i i i = ：敬u 月i 图3 i 不同判别方法的比较 比起一般的超曲分类面，分段线性判别函数和二次判别函数是非线性判别中 的最简单形式分段线性判别函数的决策面是若干个超平面，而二次判别函数的 决策面则是一个超二次曲面，包括超球面、超椭球面、超双曲面等等。但是，若 训练样本的每个类别都有很多个子类或者是维数较高，我们一般很难直接选取 适合的非线性判别函数形式，而且所要确定的未知参数很多，在实际应用中会很 大困难硎。 核函数方法提供了另一条解决非线性可分的样本分类问题的有效途径一一 将样本数据映射到高维空间中处理来增加线性分类器的分类能力，使得利用线性 分类器来学习一个非线性可分的关系成为可能【3 l 【1 8 j 。在核函数能够计算对应着两 个输入样本数据的内积的前提下，选择使用恰当的核函数来替代内积，可以隐式 地将训练样本非线性映射到高维空间，而不增加可调参数的个数1 1 9 1 。核函数方 法还有另外一个吸引人的地方是学习算法和理论可以很大程度上同应用领域的 特性分开，这些特性我们可以在设计合适的核函数时加以考虑。 3 2 核函数简介 3 2 1 核函数的概念 在对样本数据的预处理策略中，通常包括改变样本数据的表达形式，对训练 样本；= ( 而，x 2 ，劫) r ： ；= ( 五，x 2 ，吻) rh 孑( ；) = 触( 动，如( ；) ，九( ；) ) r 这个步骤等价于将输入空间x 映射到一个新的空间日= 矛( ；) i ；x ) ，一般把这 个新的空间称为特征空间1 1 6 l 。 如图3 2 ，孑是将二维输入样本映射到特征空间的映射，由此可见，在原输 入空间中样本是非线性可分的样本，可以在特征空间中样本变得线性可分，这样 就可在特征空间中运用线性分类方法来实现在原输入样本空间的非线性分类效 图3 2 二维样本空间映射到特征空间的映射 定义 设有样本空间x = i ，i ，i c 酞d ，核是一个函数k ，对所有 i ，x jex ，满足：k ( i ，i ) = ( 矛( i ) ，孑( i ) ) ，孑为从x 到特征空间日的映射m l 。 从核函数的定义便可以看出，核的思想其实是推广了输入空间的标准内积， 核的使用使得将样本数据空间隐式表达为特征空间，而越过了本来需要计算的特 征映射的问题，从而使用核函数时不需要为了在特征空间中学习而去了解特征映 射西，训练样本数据映射后的唯一有用的信息全都包含在特征空间的核矩阵 k = ( k ( i ，i ) ) 疗中m l l 2 0 1 。 3 2 2 核函数的性质及常用的核函数 核函数具有下列性质： 核函数k 是对称的。这是显然的，从核函数的定义可知： k ( i ，i ) = ( 孑( i ) ，孑( i ) ) = ( i ) ，孑( i ) ) = k ( i ，i ) 设样本空间x 是有限的输入空间，k ( x 。，三) 是x 上的对称函数。那么 k ( x ，z ) 是核函数的充分必要条件是矩阵 k = ( k ( 薯，一) ) 搞 是半正定的( 即特征值非负) 1 6 l l 埔i 。 事实上，因为k 是对称的，必存在一个正交矩阵y 使得k = v a v r ，其中人是 由k 的特征值九组成的对角矩阵，即： k = 设特征值乃对应的特征向量为m = ( ) ：，现假定所有的特征值都是非负的， i x ，考虑映射： vlj ； 则有： 孑：ih ( 风)