（计算机应用技术专业论文）子空间方法及其核扩展的研究.pdf

摘要 予空蓠方法是一耱稚据瘦掰需要对裔维数据进行簿维薤纛豹方法。它寻找 一种线性变换将高维的数据投影到低缎的子空间中去以达到降维的目的。这种 方法在辩高雏数据进行箍理辩表现穰好置应糟广泛，院魏入脸谖捌，文本分 类，d n a 序列分类及棚应的功能预测。主分爨分析以及线性判别分析就是最常 用的予空间方法。本文对子窒闷方法静最近发展进行了综述。在使丽线性判捌 分析处理高维数据时，经常会碰到所谓的小样本问题，也就媳线性判别分析的 类内离散度矩阵是奇辩的。本文对这个闯题进行了深入研究并挺漱了新的算 法。由乎子空瓣方法聪于一静线性交抉，为了处理非线性的情况，比如分类掰 是非线性的，予空间方法的按扩展被键了出来，常魇的有核主分羹分析以及 棱f 越嗽判剐分辑。本文在分掇算法的拨扩展的基础上提出了核扩展的判定条件 以及核方法的等价性。主要的工作可以归纳如下： 对子空阕方法静德统算法及其发耱进行了综述。毽菇稀巯p g a ，二维子奎 间方法，子空间方法的拨扩展以及子空间方法的非线性对应算法流形学 习。 钤对线数爨襄势辑孛豹夺样本闳熬，我 | 、】提出了令统一豹纂絷，罄热投 投影方式。通过避个框架可以统一已有的针对小样本问题提出的几种方 法，毯慧差分量势橡翔线性翔裂努辑戆二羧段法，基于零空凌瓣线性判剐 分析，贝叶斯人脸识别算法。同时，我们也提出了一种参数化的加权投影 秀式，砉蓍鬻挺骜鹣三耱雾法都霹；走着骰窀熬特裂。逶过捷久殓谈麓这令典 型的小样本问题上的实骏我们验证了该算法的有效性。 猩分析了算法的梭扩展的基础上，提出了解决算法核扩展的两个关键问题 熬方式。簦先是凝静核扩展的判定条件。此判定蘩终是慰算法核扩展豹零 质的描述，不为算法的具体表达所限制。随后，我们提出了算法的核扩展 与孩主分霪分辑艇上嚣援予特征窆阗熬冀法这嚣孝孛方式戆等侩热。这可以 糟成是算法核扩腥的一种新的方式。实骏表明这种等价性不只砖在理论上 楚正碜豹，在实黪豹诗冀避翟孛瞧爱够菠浚遗寒。 1 。 北京工业大学工学硕士学位论文 关键词予空间方法；小样本问题；加权投影方式；核扩展；核主分量分析 ，i i a b s t r a c t a b s t r a c t s u b 8 p a c em e t h o di sad i m e n s i o nr e d u c t i o nm e t l 岫d ，i t8 e e k sak i n do f1 i i l e a r t r a n s f o r m a t i o nt op r o j e c ti n p u td a t ai n t ol o wd i m e n s i o n a l8 u b 8 p 扯e t h i s1 【i n do f m e t h o dh 昭v e u9 0 0 dp e r f 0 珊a n c ew h i l ed e a l i n gw i t hh i 曲d i m e i l s i o nd a t aa n d i 8e x t e n 8 i 、r e l ya p p l i e d ，s uc ：ha si nf a c er e c o g l l i 七i o n ，d o c i l i n e i l td a s s i 矗c a t i o n ，d n a 8 e q u e n c ed a 韶i 矗c a t i o na n dp r e 掀i o n p 血c i p a lc o m p o n e n ta n a l y s i s ( p c a ) a n d l i n e 8 rd i 8 c r i m i n a n ta n a l y s i 8 ( l d a ) 壮e 七w om o s t l yu s e db u b s p a c em e t h o d s i n t h i 8t h e 8 i 8 ，w eg ea8 u r v e yo f8 u b 8 p a c em e t h o d ，i n d u d i n gi t sc l a s s i cf o h l l 8a 肛d m o s 七r e c e t l yd e v e l o p e da l g o m l l m s w h e nd e a h n g 诵t hh i 曲d i m 邮i o n a ld a 七a l d a 丽o 危e ne n c o u n t e rt h e8 i t l 埝t i o nt h 8 ti t 8i n t r 扣d a 翻删i a n c em a t r i xi s 8 i n g u l 跗，a l s oc m l e ds m a l ls a m p l es i z ep r o n ( s s s p ) w b 西v ea nd e 印a n 出g i s o nt h i sp r o b l e ma n dp r o p 0 8 ean e wa l g o r i t h mt os o l v ei t s i n c es u b s p 们em 甙h o d b e l o n g st oa 】d do fl i n e 甜t r a n s f b m a t i o n ，i n0 r d e rt o8 0 l v en o n l i n e a rp r o b l 锄，i e c l a 旦s 伍c a t i o nw i t hn 仰l i n e 盯8 e p a r a t i n gh y p e r p l a n e ，t h ek e m e l i z a t i o no fs u b s p a c e m e t h o di sd e v d o p e d t 、w i d e l y 璐e dk e m e l8 u b s p a c em e t h o d 8 缸ek e r n e lp c a a n dk e r n e l6 8 h e rd i 8 c r i h l i n a n ta n 8 l y s i s w 毫百v ea na n a l y s i 8o nt h ek e m d i z a t i o n o f 出g o r i t h m sa n dp r 叩o s e daw a yt od e t e m l i n e 七h ec 印a b i l i t yf o ra a l g o r i t h mt o b ek e r n e l i z e d a l s ow ep r o p o s e 帆e q u i v a l e n c eb e t w e b nk 既n e lm e t h o d s t h em 缸n w o r kc a 血b e8 1 l n u n a 订z e db e l ( 押r ： g i v ea n8 u r v e yo c l a l s s i c a ls u b s p a c e l e t h o d sa n dr e c e n td e v e l o p m e n t s t h e 8 ei n c l u d es p a r s ep c a ，t w od i m e n s i o ns u b 8 p a c em e t h o d ，k e m e l i z e d8 u b 8 p a c em e t h o da sw e ua sm 壮i f o l dl e a r n i i l g 嬲叽n o n l i n e a rc o u n t e r p a r to f s u b s p a c em e t h o d t 0d 踟w i t ht h es m 以1s 锄p l es i z ep r o b l 唧i nl d a ，w ep r o p o s ea1 1 i l i - f o r m 丘a m e w o r k ，w e i g h t e dp r o j e c t i o na p p r o a c h ，w h i 出c a nu i 母s e v h a la l - g o r i t h m sf o rs s s p ，i n d u d i n gp c a + l d at w op h 粘ea l g o r i t h m ，n 1 1 l ls p a c e b 蛄e dd i s c r i m i n a ta n 以y 8 i s ，b a y e s i f a c er e c o g 血t i o n m e a n w h i l e lw ep r 0 - 北京工业大学工学硕士学位论文 p o s et h ep a r 锄e t e r i z e dw b i g h t e dp r o j e c t i o na p p r o 村l ( p w p a ) ，a l g o r i t h m s m e n t i o n e da b o v ec 衄b ev i e w e da ss p e c i a lc a 8 e so ft h i sn e w 吐g o r i t h w b e v d u a t et h ee 胝t i v e n e 8 so fp w p ao nf a c er e c o g l l i t i o n 砌c hi sat y p i c 出 s s s p a 托e ra na n a 】y s i so fk e m e h z 8 t i o no fa l g o m h m 8 ，w ep r o p o s eaw a yt o8 0 l v e t w ok e yq u e s t i o ni nt h ek 唧e l i z a t i o n0 f 以g o r i t h m f i r s ti st h em e t h o dt o d e t e m i n ew h e t h e ra na j 鲥也mc a nb ek e m e l i z e d t h i bm e t h o dh a st h e a d 瑚m t a g et h a ti td o e sn o tm 皿i t e db yt h ec o n c r e t ef o no fa 皿出g o r i t h m i t i sa ni n s i g h t 、，i e wo fk e r n e l i z a t i o n t h e nw ep r o p 0 8 eak i n do fe q u i v a l e n c e b e t w e e nt h ek e r n e l i z a t i o no f 胡g o r i t l l m 衄dk e r n dp c a p l u 8t h ea 培o r i t h mi n f e a t u r es p a c e t h i 8c a 肛b ean e ww a yt of o r i nt h el r n dv e r s i o no fo r i 百n 缸 a l g o m h m e ) 中e r i m e n t 88 b 脚t h a tt h i 8l d i l do fe q l l i v a l e n c ei sn o to n l yr i g h 七 i nt h e o r y b u t 出s or e 丑e c t e di np r a c t i c a lc o m p u t a t i o n 8 k e y w o r d ss u b s p a u c em e t h o d ；s m a l ls a 1 p l es i z ep r o b l 锄；w e i g h t e dp r o j e c t i o n a p p r o a c h ；k e m e l i z a t i o n ；k e m dp c a 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究羧果。尽我麝翔，除了文中特裂攘以橛注弱致谢蕊地方势，论文巾不包含其她 人范经发裘或撰霉过熬磷究或聚，也不惫含戈获褥j k 寨工业大学或其它教窝规构 的学位绒证书而使用过的材料。笃我一同工伟的阎恚对本研究所傲瀚任何羹献玛 已在论文中作了明确酶说靖并表示了谢意。 签名；塑茎建日期：竺2 ! ：! 。 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保磐送交论文嬲复印传，允i 年论文被粪阕和借阕；学校可以公毒论文的全部或部 分内容，阿以采用影印、缧印或其她复镶l 手段保存论文。 ( 傈密静论文在解密后藏遵守诧规定) 签名；氆：殳垒导师签名：型l ! 垃日期：二! 堡兰，气 1 1 研究背景及意义 第l 章绪论 子空间方法是一种根据应用需要对高维数据进行降维处理的方法。它寻 找一种线性变换将高维的数据投影到低维的子空间中去以达到降维的目的。 尽管经典的子空间方法，如主分量分析( p i t n c i p a lc o m p o n e n ta i l a l i s p c a ) 吼f i s h e r 线性判别( 雎h e r 功s c r i m i n a n ta n a 舾i s f d a ) 闭很早就被提出，但是 目前其受到大量关注还是由于目前对处理高维数据的分类问题的需求。典型的 问题有人脸识别【3 l ，文本分类蛳，基因数据分类以及相应特性的预测【目。 在人脸识别问题中，如果使用静态的图片作为原始输入，假设图片的大小 为1 0 0 1 0 0 ，那么其表示需要一个1 0 0 1 0 0 的矩阵或1 0 4 维的向量。如果直接对 如此高的数据进行分类处理，那么计算的时间会很长。假设分辨率再高一点或 是需要处理的图片的尺寸再大一点，如1 0 2 4 7 6 8 ，这个维数接近1 0 6 了，无论 是在内存的存储还是计算上面都是很难应付的，而这只是平常电脑屏幕大小的 一个很常见的输入而已。这个问题可以通过子空间方法来进行降维处理。子空 间方法通过寻找一组线性投影向量，将原始输入投影到这组向量张成的子空间 中去同时尽量保证不丢失对后续处理，比如分类，或是聚类有重要影响的信 息。 在文本处理和基因数据分类中，维数也是很高的。因为文本的原始输入可 能就是几千个字作为一个样本，对一小段的d n a 序列做分类或是预测就需要处 理成千上万莳d n a 碱基( 构成d n a 序列的基本单元) 序列构成的输入。直接去使 用这些原始数据其计算量不但大，而且可能分类的效果也会下降。这是因为我 们的原始数据是投有翌过选择的，其中很可能包括丈量的对分类无用的信息或 是噪音。对于一般的分类器来说，加入了噪音的数据会使分类的正确性下降。 对于d n a 序列来说更是如此，依照某个特性的分类可能仅仅取决于某一小段 的d n a 序列，或是某一个碱基。但由于我们事先并不知道那些序列是有用的， 所猷无法做出取台，而只能把整个序列作为原始输入。这就需要分类器最好能 够做到某种方式的特征选择，在d n a 序列分类中，好的分类器或是好的分类效 够做到某种方式的特征选择，在d n a 序列分类中，好的分类器或是好的分类效 北京工业大学工学硕士学位论文 果必定是经过了特征选择或是考虑了这个因素的【6 】吲。分类问题中的特征选择 可以看成是子空间方法一种特例，即直接选取某些特征来形成一个子空间，而 通常的子空间方法可能还包括旋转变换。 从上面的分析可以看出，子空间方法可以达到对数据进行降维的作用，也 包括对数据的特征选择。在实际应用中，可以减小计算量，以使分类处理达到 实时处理的要求，同时由于其特征提取的作用，提取出了我们关注的有用的信 息，可以使后续的分类或是聚类处理的效果更好。 1 2 子空间方法的历史，现状，以及存在的问题 经典的子空间方法包括主分量分析( p r i n c i p a lc o m p o n e n ta n a l y s i 8 ) ，r 8 l l e r 线性判别( f i s h e rd i s c r i m i n a n ta n a 匆s i s ) 也称为线性判别分析( 【血e 缸d i s c r i m i - n a n ta n a l y s i s ) ，实际上可以证明他们在某种假设下是等价的【8 】。这些方法虽然 很早就被人提出，但是到目前依然被广泛使用，并且在一些复杂的分类问题 中，比如人脸识别【3 】【q 【1 0 1 1 1 1 l ，有很好的表现。 由于近十多年来子空间方法在人脸识别中的成功的应用，子空间方法成为 一个关注的热点，并且发展迅速，包括对经典方法在实际应用时的改进和对整 个方法的进一步推广。应用子空间方法的目标是得到一组低维的特征，但是这 组特征是否适合于下一步的分类，则是一个具体情况具体分析的问题。围绕这 一问题，很多对子空间方法应用上的改进被提了出来。其中包括在组合应用子 空间方法，例如先用p c a 降维，再用f i s h e r 判别分析 1 0 】1 】。 在应用线性判别分析时，由于面对的是高维的数据，会出现类内离散度 矩阵奇异的问题，也就是所谓的小样本问题( s m 以ls 啪p l es i z ep r o b l e m ) 。为 了解决这一问题，很多算法被提了出来，比如正则化的线性判别( r e g u l 撕z e d l d a ) 【12 ，基于零空间的线性判别( n u us p a c eb a s e dl d a ) 【1 3 】，贝叶斯人脸 识别b a y e s i a nf a c er e c o g n i t i o n 【1 4 】，广义的判别分析( g e n e r 8 l i z e dd i s c r i l n i n a 础 a n 胡y s i s ) 【1 5 】。这些方法都试图通过修改原来的线性判别目标或其计算过程来解 决维数高而样本少带来的小样本问题，并且达到了较好的效果。目前这一方面 的研究仍然很活跃。 - 2 一 第l 荦鳝论 塞予子空闻方法瘸子一静线性变换，质双秃法整理# 线最瓣蕊嚣。逡蠡分 炎问题中分界耐是非线性的。凝近发展起来了一种非线性的方法，核方法或 称为棱蔽巧1 1 薅，其栗添予支撑离量梳f s u p p o 赡v e c t o rm a 庙i n e ，8 v m ) ，翟爨 埘以扩膦到很多其他的方法上。利用拨方法，可以对融有的子空间方法进群 核扩展，将荬跌掰弼一个新的空闻，然籍再靛耀子奎阍方法。这样就形成了 援p c a l l 8 l ，核黜a 1 1 9 】，这些方法在分类处理中波现出了报高的性能，煞分类效 聚和s v 酣差不多，有时甚至效果更好。由于暴有了处滏非线性分类闷题的黼 为，子空阕方竣麴应用瓤圈大大鼹扩大。另一方嚣，我们可以搬棱扩燧鼹子空 间方法分成两个部分。第一步，从原始空问通斑核映射到特征空丽，籀= 步， 键露予空藏方法佟囊予姆薤空瀚。这撵，我锻w 以分裂研究这嚣部分，程翅 静分的进展都可戳推动熬个算法的改进。 子空霾方法巍现实巾楚理巍维数擐袭现壤好篷是鸯其必然後楚。残实瘟照 中，有熄数据确实是高辨的，艇映了复杂的现实模型，但是考虑我们关注的秘 探t 箨楚弱部抟，诋鬃豁，霉戬建缳缝熬数器来遥近；月薅番缝数据举蔟土最 低维的，但是却以高维的形式袋示出来，例如人脸，个物体的运动豳片集溅 裰额，蒸窿壶赛楚寝低的维数。在这嚣静清嚣下，子壑褥方浚帮是霹辍搜奏效 使用的。子空间方法的研究和发展对简化模型和提高计算判别速度很稍好处。 同簿，可疆看到在应霪予空阕方法孛，嚣要辩决新产囊瀚淹藤。凌髓戳天验谈 别为例来说明存在的一般问题。 在人猃镶裂申，建蠲子空窝方法蕊囊要静溅难在于没有燕够豹嚣零采骰糕 攀上的估计，耐这点传统的子缴间分析是没有考虑到的，也就是所谓的小样本 溺逶。尽管如蓊所述，很多方法援援了臻来蘩决运巾潮蔻，黎鼹霰然不缆遮戮 报满意纳效果。这个问题也是计算智能照面的个基雄的问题。那就熄我们烧 如何获褥籍谈静和徽粼鞭识霜酌? 究竟跫有限游样本? 还是臻念了我稻已有盼 必验知识? 第二个问题熄我们谯考虑遮个问题时，我们总是蛾定人脸窝闻本岿 麓位于一个低缭的子空黼酶。瓣样盍予缺少训练样本，辩这个低维窆阕的理解 釉提取还不够璞怨。避年来发髅起来的流形学习可能会对这个阅题露一些接 渤。第三个问鼹是在人脸识剐中，我们是很滚辩不丽谈剃方法的效浆做比较 熬。不过惹来人们开始蹩立7 一些大翡测试数据疼，魄翔f 我靴强人黢痒1 2 0 】， 。3 。 北京工业大学工学硕士学位论文 来评价各种识别算法。或是使用留一法来衡量错误率，使得这个问题得到一定 的解决。综上，如何利用子空间方法尽可能有效的解决小样本的问题如何有 效的在实际应用中更好的得到其低维空间的表示，如何让予空间方法接合特征 选择的思想使后续的分类达到更好的效果，这些都是我们需要进一步研究的问 题。 1 3 本文工作及论文的组织 第二章，我们对子空间方法进行了详细的综述，除了传统的子空间方法 外，我们还介绍了最近发展起来的一些子空间方法，比如广义线性判别，二维 的子空间方法，以及予空间方法的非线性对应算法：流形学习。 第三章，我们提出了一种小样本问题处理的框架，即加权投影方式并 且通过此框架统一了几种已有的处理小样本问题的方法。同时，我们也提 出了一种新的方法，参数化加权投影方式( p 缸唧e t e r i z e dw e i g h t e dp r o j e c t i o n a p p r o 汕) 来处理小样本问题。 第四章，通过分析算法的核扩展，提出了一个新的算法的核扩展的判定条 件。这种判定条件与算法的具体表达形式无关。随后，我们提出了算法的核扩 展与核p c a 以及原来算法的等价性，同时给出了证明以及实验验证。 最后是结论。总结了全文的工作并对进一步的研究做出展望。 4 一 第2 枣予空阕方法综述 第2 耄子空间方法综述 2 1 传统的子空间方法 当处理高维空闯的数据潜。一种处瑾方式楚通过缀合潦始特鬣来降低维 数。予空闻方法逶避将离维空闯酶数据投影到一个低维静祭瀚来遮禹这一效 果。这种方法经常被用来降低维数，鲮憝提取位子缀数低的多的翔剐信惠。在 这节中，我稻执壤论背最帮计算方法这礴个菇露讨论三稀传统豁子空闯方法， 即主分餐分析，线性搿剐分析，以及f i s h e r 线性判剐。 2 1 i 主分量分析 。 变势篷分糖，弹p a a ，霹l ；盂蓉戚楚一个簸臻纯阉遂黪解。怼予一缀静空瓣 申熬数据来说，忿爨黪圭分爨提摸了一秘用黪蠢维数，戆魍爨组邋避这级数 掇静最佳遥近。 竣霄一维海鬟芏1 ，怒，嚣n 辩，现在考凑耀秩g 韵囱量米裘示窀嬲 ，( 柚一p + v 口a ， ( 2 1 ) 其中是桫中的个袭示偏移位管的向爨，v 。蹙一个p 口嘏阵，其口个翔向建 耩互委交并且为擎位翔羹，天楚一个维的参数淘量a 遴是一个对秩为碍的铸瓣 超平面的参数化裘示。圈2 _ l 显示了q = 1 的情形a 用最小平方差准刚采求解给 定数据的这个摸黧福警予最小亿麓构谟麓( r e 。o n s 翔c te 艘o r ) ，躐p 糍芦一聃| p ) 露糠溺数戆解直接在这璧绘懑，鼹多细节雄导可皴农i 8 】审找魏。 弘一双 丸= v 芋( 戡一， 吼= b l ，睨，e 0 ， ( 务3 ) ( 务4 ) ( 2 一国 北京工业大学工学硕士学位论文 图2 1 一组数据的第一个主分量。这条直线最小化每个点到这条直线的正交投 影点距离差的平方的总和 f i g u r e 2 - lt h e6 r 8 tp r i n c i p a ld i r e c t i o no ft h e 8 ep o i n t s t h e1 i i l em i n i i l l i z et h e s q u a r es u mo fd i s t a n o e 8 丘o mp o i n t 8t ot h eu n e ( 2 _ 6 ) 其中e i ， = 1 ，口是矩阵s 的相对于g 个最大特征值的特征向量，矩阵s 定义如 下： s = ( 一孟) ( 戤一孟) t ( 2 - 7 ) i = l s 也被称为给定样本数据的离散度矩阵。它是样本协方差矩阵的n l 倍。因 为s 是实对称矩阵，所以特征向量正交，因而它们形成了表示给定样本数据的基 向量。在式二4 中系数向量凡就是墨在这组基向量下的坐标分量，称为主分量。 给定观测样本z - ，z 2 ，z 础，主要有两种方法来计算主分量分析中的 基向量和各个样本点的主分量或系数。 6 - 第2 章孑空闻方法综述 第一耱是蘧：蓬离敖发矩箨麴特征德势鼹( 嚣i g e 斟a 鹣ed e 崧挚o s i t i 雌) 。蓠 先，计算给定样本数据的离散度矩阵的特征向爨，然后选择相殿于前g 个最大的 特征值静特征囱麓作鸯v 。静羁两囊，这赣是基内量楚簿。最嚣将经遘了串心偬 的样本数据，也就是戤一磊投影到这组熬向量上，从而得到每个观察样本的主 分誊x 。 第二种方式是对原始样本数据进杼奇异值分解( s i n g u l 蹦v 甜u ed e c 。m p m 8 i t i o n s v 珈。首先，将中心佬衍的数据作为p 维瓣矩阵x 的行向爨。然菇 对x 进行奇异擅分解。 x = u d v t ( 2 _ 8 ) 这里u 是一个p 正交矩阵( ( u t u ) 一b ) ，忿豹硼趣量吨放称为表鸯异囱 激( 1 e f t8 i n g u l a rv 忧t o r ) ；v 也是一个p p 正交矩阵( v t v = i p ) ，每一个列向 最咚被舔必右惫募匙量( r i g h ts 泌g 畦瑟v e c t 0 0 。转是一个p 慰角矩薄，箕对 角元素d 1 d 2 出0 被称为奇异值( s i n g u l a r 、r a h l e ) 。对于给定秩口，待求 爨瘁v 。蠢矩蓐v 豹蔫g 令捌囊量缀袋。餐一个榉本数撂戤夔系数淘量，或主分 爨凡由矩阵u d 的第i 行的前口个元素给定。 主分爨势撰瓣数据瓣降维势不一定缀瑾葱，这是嚣为p g a 终维对数据豹低 维表示是最优的，但不定是以分类为目标的低维最优表示，因为它没有考虑 粥分类淘遂中豹类舅l 信惑。 2 1 2 线性判鬟分耩 主分量分攒( p g a ) 可以被嚣戏一种i # 监督( 1 糙s u p e r v i s e d ) 的黪维方法，面不 考虑数据的类别信息。下面讨论的线性判别分析则考虑了对分类有用的投影方 囱。 假寇 ( 茁) 是随机向餐x 在类g = 南中的类内条件概率密度，他是每个类七的 筑验掇率，潺是釜，戳= l 。缒雳b 8 弹8 公式，我嚣】有 p r ( g = 七l x = 鬈) = 蒜 ( 2 _ 9 ) 依据b a 8 决策猴则，最优的分炎器满足下面的条件： g ( z ) = 苫强掰j 冷( g = 惫| x = 茹) 。 参l g ) 北京工业大学工学碘士学位论文 现在我们假设所有的类内条件概率密度是高斯分布，类七有协方差矩阵k 。对于 观测的样本数据，要比较两类的后验概率，只需要考虑两者比值的对数，即 k 篱器一g 榴仙瞎 = 以0 ) 一也( z ) ；( 暑1 1 ) 区= 一；i o g 吲；( z 一胁) t f 1 ( z 一胁) + 1 0 9 吼 i = 南，z ( 禾1 2 ) 式2 - 1 2 中的函数以( z ) ，国( 石) 被称为判别函数( d i 8 c r i m i n a n tf i l n c t i o n s ) ，相应的决 策规则变为g ( ) = n 叼m a x k 以( z ) 。我们进一步假设每个类的协方差都相等， 即e k = e ，v 七，去掉以( z ) 和也0 ) 中公共的项，我们有： 靠0 ) = 护e - 1 p k 一；厦- 1 p k + 1 0 9 丌k ( 2 - 1 3 ) 可以看出氏 ) 是$ 的线性函数。这表明类七a n dl 之间的决策边和即满 足民( z ) = 也( z ) 的z 的集厶- 也是关于z 的线性方程，如( z ) 被称为线性判别函 数( 1 i n e 盯出s c r i m i n a n tf 1 1 n c t i o n s ) 。 在实际中我们不知道事先假定的高斯分布的参数，所以我们需要利用得到 的样本数据来估计它们： 氟= k ，其中 k 是类七中的样本数； 砒= m ：k 胍； 宝= 各。瑚( 墨一m ) ( 墨一觑) t ( 一) 假定有特征值分解宝= u d u t ，那么靠( $ ) ( 2 1 2 中的项可以写成下面的形式 ( z 一卢七) t i 1 ( z p 七) = ( z p 七) r 一1 ( z 一肛k ) = u t 一口t ) 】t d 一1 【u t ( z 一丘t ) 】 一 ( d 一 u t ) ( z 一砒) t 【( d 一 u t ) ( z m ) 】( 2 _ 1 4 ) l o g i k i = l o g l l = l o g i d | ( 2 1 5 ) 根据上面列出的方程，基于线性判别的分类器可以用以下的步骤来实现： 。r 第2 章子空间方法综述 却矗e r e 所给的观测样本。即利用对共同协纺差矩阵的估计值宝，做变 换：x + 一d 一t x 。其中宝= u d u t 。这样变换后的数据的x + 的公共协 方差矩阵的估计矩阵就变成了单位阵。 在不考虑类的先验概率的影响下，在变换后的空间中将每一个待分类的点 或向量分到离它最近的类均值点所在的类中。 2 1 3f i s h e r 线性手0 另0 对线性判别分析( 见2 1 2 冲考虑的k 类问题，去掉每个类都是高斯分布的假 设，f i s h e r 提出以下准则： 找这样一组投影向量，使得得到的新的变量z = ，x 的类间离散度 矩阵相对于类内离散度矩阵最大化 上面提到的类间离散度矩阵，描述的是z 的各类的均值的协方差，而类内离散度 矩阵则是每个类的协方差或离散度矩阵的和。它们的定义如下： s = s 七兰 肛k = s 丑= “= ) 扣一m ) r ， 帆( m 一口) 一l ) r k = 1 专莩茹= 专喜嗽 ( 2 - 1 6 ) ( 2 _ 1 7 ) ( 2 1 8 ) ( 2 1 9 ) ( 2 2 0 ) 根据上面的定义，我们有z 的类问离散度矩阵为n t s b 口，类内离散度矩阵 为o t s w o 。注意到s b + s = s t ，这里s t 即是x 的总离散度矩阵( t o t a l8 c a t t e r m a t r i x ) ，它把所有的观测样本作为一个整体来计算其协方差矩阵。 f i s h e r 准则等价于最大化所谓的兄n 矿e t 9 九g 仳。执：耐： 一s 凹o n 警而 。9 一 ( 2 2 1 ) 胁 e ， 一 、，慷瓯” 柚宁瓦 北京工业大学工学硕士学位论文 假设s w 非奇异，那么这个问题的解即是矩阵s s b 的最大的特征值对应的特征 向量，把这个求出的记为n l 。进一步，如果我们想找另一个投影向量奶，满 足与口1 关于s 正交，并且最大化式2 2 1 ，那么我们可以算出待求的啦就是矩 阵s s 目的第二大特征值对应的特征向量，依此类推。由于矩阵s b 最大可能的 秩为一1 ，所以我们最多可以找到k 一1 个相互正交的投影向量，即对应与矩 阵s s b 的非零的特征值的特征向量。其他与这些向量张成的空问正交的向量 将导致式2 _ 2 1 为0 ，更多细节见。 如果我们直接计算矩阵s 帚s 口的特征向量，则需要计算s 的逆，而这是不 必要的。我们在这里给出另一种计算方法： 。利用s w 来印，l e 咒观测到的样本数据。这与线性判别分析( l d a ) 中的第 一步一样。假定我们有特征值分解s = v d u t 。则变换后的数据的 类内离散度矩阵成为单位矩阵，令w = u d 一 ，那么类间离散度矩 阵s 名= w t s 口。 做特征值分解s 名= v d b v t 。相对于前z 个最大特征值的z 个特征向量则是 所要的投影向量。 从上面的计算方法的讨论中我们可以发现f l d 和l d a 的计算步骤的非常相 似。事实上，在l d a 中，当在变换后的空间中选择到最近的类均值点时，我们 可以忽略掉距离在与这些类均值点张成的仿射子空间正交的空间中的分量。 当我们只在类均值点所在的仿射予空间中比较距离时，我们可以得到和原来的 方法相同的分类效果，同时我们比较距离的空间的维数降成了k 一1 。如果我们 想进一步降低到维数三k 一1 ，我们可以对这些类均值点做p c a 来得到l 个投 影向量，从而在这个更低的维数空间中做距离比较。这个方法也被成为降低了 秩的l d a 。比较这种方法和f l d 的计算方法，我们可以得出它们实际上是一致 的。这也是为什么在很多文献中为什么f l d 也被成为是l d a 的原因。更详细的 讨论见 8 。 从上面的线性判别分析可以看到，l d a 和f l d 都要求共同协方差矩阵宝或 类内离散度矩阵s 协可逆，而这在高维数据的分类问题中一般不能满足，这个问 题就是我们下面要分析的重点。 1 0 第2 章子警褥方法练述 2 2 予空间方法在小样本问题中的应用和发簇 零繁我稻考察子窒溺方法煞瘟雳，主要考瘩基予静态图像翡久验识麓。嚣 为这个方面的应用目前很热门，同时也可以代袋子空间方法农很多其他的高维 数据分类闯遂串碰弱静阗遂。辣a 葑m 瓤错i c h 嘲绘出了一个更广泛戆关予予空瓣 方法在人脸识别中的应用的介绍。 首筑简单攘述一下簇子静态鼙像瓣久验静谖餐。窀静番搽蹩遥遘溅经标键 好对应个人的训练图片来识别出新的测试图片中的个人。假设所有在训练和测 试中的黼片大小都是m 珏，那么班莱种颓序 毪所有蒙索值辩猢成一捌，典纛 的顺序魁r 8 s t 目捆描的顺序，例如把各行首尾造接起来，一张阁片就w 以被瓣 成p = mx 住绩空间的个点或炬_ 个商萱。这样处理籍我常j 就可以运稍上面予 空闻方法来分析处理了。 2 2 1 主分量分析黝应用 p a a ( 主分嫩分析，见( 2 1 1 ) ) 最初由s i r o v 触和i ( i r b y | 2 3 掇出来用于人脸表 示，雨露是氮藏帮p 髓t l 黼d | 3 | 疲蔫妥入浚浚鬟。由于p c a 棱遮豹基彝蹩懿维数 岛原始人脸图片的维数样，并且可以显示为一张人脸的模样，所以这种方法 穗被称麓特征羧“癣g e 蛹e 8 ”技术。圈警2 显示了藏尼个特征麓。萁方法薅下： 图誊2 特裰脸：左边是脸盼均值，籍面是前价特霰脸两 f i g u r e 舡2e i g 蹦髓：t h el e 代m o s ti st h em e a no ff a c e 80 fo n ep e r s o n ，a n df o l l o w i n ga r e 壤菪e n 蠡瓣e s 强 簿一张熬片( 包瑟撵本秽待检测豹图片) 在藏去榉本均蕊鑫竣投影裂圭分量空阉 中；然朦对任待检测图片，计算它的主分量向量与备个类的均值的生分量向 蹙蘸欧菠疆离。袋据诤箨鑫豹距离窝一定瓣阚疆，特糗灞强冀上懿入藏虿爨被 分类到属于训练集某个存在的个体，或是某一个新的个体，或者根本就不是人 脍。 1 1 北京工业大学工学硕士学位论文 2 2 2 线性判别分析的应用 p c a 方法仅仅考虑了在变换后的空间中最大化离散度矩阵，由p c a 提取的 特征或是系数在 1 0 】中也被称为描述性最好的特征 如时五- 印r e s s 妇e 砌t 他s 。在 人脸识别中，当光照和表情差异是占所有差异的大部分时，p c a 方法就会捕获 住这些差异而不是不同人的自身的差异，于是导致其分类表现不理想。另一方 面，l d a ( 线性判别分析，见( 2 1 2 ) ) 或是f l d ( f i s h e r 线性判别，见( 2 1 3 ) ) 主要 关注的是那些具有判别信息的特征，因此可以设想会有更好的分类效果。 在应用l d a 或是f l d 的时候，一个经常碰到的问题是它需要类内离散度矩 阵s w 满秩，而在现实中往往难以满足。这就是予空间方法碰到的小样本问题。 具体解释如下：假设是所有训练样本图片的总数，是要分类的个数，那么 矩阵s 的最大可能的秩是一k p ( = m n ) 。下面我们将看到，有很多方 法被提出来解决这个问题。 b e l h u m e u r 提出了被称为“f i s h e r f a c e ”的方法并且与传统的“特征脸” 方法在性能上做了详细的比较。为了克服s 奇异，首先在原始的特征空间或 图片空间中使用p c a 降维到一k ，这样新的类内离散度矩阵s ，一般就可以 达到满秩。然后在这个新的子空间中运用f l d 来进一步降维并提取c 一1 维的具 有判别信息的特征。那篇论文也指出去掉前三个主分量，特征脸方法在处理光 照变化较大的人脸识别时的效果会变好一些。另外一种方法就是所谓的正则 化l d a ( r e g l l l a r i z e dl d a ) 【1 2 】。就是在s 上加上一个很小的常值的对角矩阵， 即= s w + p k ，其中p o ，k 为单位矩阵。这种正则化的方式和我们在本 论文中提出的一种处理跏奇异的方式很相似。 在f i s h e r f a c e 方法被提出后，一系列与此方法相关的问题也随之而来。注意 到总离散度矩阵s t 的最大可能的秩是一1 ，这表明通过p c a ，我们最多可以 有一1 个投影向量来选择作为主投影方向，这些投影向量对应于s t 的非零特征 值。现在的问题是我们需要选择多少个投影向量和如何选择它们能够达到较好 的分类效果? 另一个问题是最终得到了具有判别信息的特征后，用什么分类器 来对它们进行分类。z h a 0 【2 4 认为针对某一特定的应用主分量的个数应该保持不 变，而不是上面f 姚e r f a c e 方法中的一k 。同时也指出使用加权的欧氏距离会 得到更好的分类效果，其中也给出个相应的实验结果。另外y 如g f 2 5 】也讨论并提 1 2 第2 章子窑闻方法综述 如了一个通甩计簿挺絮。 2 2 。3 基予零空阙的判别分析 转统蕤粼裂分褥为了解浃8 静静淹髯瓣滋，采取曩捧它鹣零窒耀鹅方法。 而基乎零空阎的方法烫f j 逄使街s 的零空茼来散识别，邵稻糟满足s 静= o 羽投 澎商麓移构成黥空阕。这种方法谖兔不辩匿片豹差髯僖惠毪存程子s 钟瓣零空游 中，并且可阻摄取出来作为字瞄u 的依据。 c i h e n 陵将所有的样本曹先投影凝s 匏零窑闻，这个室阕中类内离散魔为 零矩阵。然艏最优的判踟投影向量就魑郑些能够最犬化类间离散度矩阵的投影 商量。p g a 方法被用来褥到絮们。漱子高维麓醉s 计算的熨杂度，在1 2 辞中使露 种象素组的方法做预处理，以便降低维数，然后这种基予予空间的方法就被 粥到降缭后的特征空间中。为了在原始的图片空阊审使用零空间方法，并髓注 意到8 w 的零空间的一些向量也属于s 启，这媳投影向量不具有区分傣息，从瓶是 不必溪的。h u a n g l 2 证明了矩黪s w 鄹s 8 的按同的零予空间就是矩阵s r 的零子 空间。通过保留不与s 占的零空间相交的s 的零空间，一种新的获得可分类信息 戆基予零空阅的线性翔剐方法被提爨； 。 去摔豹嚣空麓。这霹淤镬溜p c a 竞残。没秽是这样一个矩黪，宅豹掰露 的捌向趱都是籁阵翰的对应予蔫 饕特锤餐阿特征辩量，那么我们有： s 备一 乳一 扩r s w f 矿s 嚣， ( 2 2 ( 舡2 3 ) 计算s 知的零空间。经道上面的步，矩阵s 鲁的秩一般是一1 ，而s 0 的 秩般蹩一影，所戳s 0 的零空闷的秩一般怒村一l 。设q 是s 缸的零窝阍 基矩阵，那么u q 就是矩阵s w 的霉空间的一个予空间，并且具有判别信 息。我们礴： s 参一p q 尹s 舅( q ) s 答= = ( 秽奄) 掌s 笛( 酽q ) 翔榘s 笛麴零空闼掇然存在，雯l 避一步去搏窀戴。 * 1 3 一 ( 2 4 ) ( 瓤2 砩 北京工业大学工学硕士学位论文 后来l i u 【1 3 】证明了最后的一步是不必要的，因为已经不可能有s 笛的零空间存在 了。 2 2 4 贝叶斯人脸识别方法 与上面的标准的l d a 方法和基于零空间的线性判别方法不同，贝叶斯人 脸识别方法( b a 滞s i a nf a c er e c o g n t i o n ) f 14 】把原始数据看成满足高斯分布来建立 模型，然后使用协方差矩阵的估计来直接估计类的后验概率，从而将要分类 的测试图片分到具有最大后验概率的类中，这种方法也被成为最大化后验概 率( m a 商m i u map o s t e r i o r m a p ) 方法。 在贝叶斯人脸识别方法中，它定义了两个不同且互斥的类：q j 代表同一个 人的多张图片形成的类内( i n t r a p e r s o n a l ) 差异( 比如不同的表情或是不同的光照 等) ，而q e 则表示不同的两个人的图片形成的类外( e x t r 印e r s o n d ) 差异。假设这 两类差异都是服从高斯分布的，那么对于给定的两张图片的差异；五一如，我 们要寻找的就是似然函数p ( l q j ) 和p ( l n e ) 。然后，我们就可以依据b a y e s 公 式计算出两张图片的相似性度量s ( 矗，屯) ： s ( ，厶) = s ( ) = p ( n ，i ) = 砭q 五万；丢会竽