（模式识别与智能系统专业论文）基于核的非线性特征抽取与图象识别研究.pdf

博士论文基于核的非线性特征抽取与图象识别研究 摘要 特征抽取是模式识别研究的最基本问题之一对于图象识别而言，抽取有效的图 象特征是完成图象识别的首要任务。基于核的特征抽取方法是最近刚刚提出的一种非 常有效的非线性特征提取的方法。该文就有关基于核的非线性特征抽取及识别方法中 的若干问题进行了深入的研究，所提出的算法在人脸识别和手写体字符识别方面得到 了较成功的应用。 基于统计不相关性的f i s h e r 线性鉴别分析是特征抽取的最好方法之一，在此基础 上，本文提出了基于核的统计不相关鉴别分析方法。该方法不仅能够有效地抽取非线 性特征，而且能够彻底消除样本特征之间的统计相关性，并指出基于核的统计不相关 鉴别分析方法是经典的f i s h e r 鉴别分析和统计不相关鉴别分析的进一步发展。在o r l 标准人脸库上的试验结果表明，在识别性能上所提出的方法不仅优于基于经典的线性 鉴别分析方法和统计不相关线性鉴别分析方法，而且也优于核f i s h e r 鉴别分析。在此 基础上，引入空间变换的思想，提出了一种快速的核f i s h e r 鉴别分析，从理论上巧妙 地解决了高维特征空间内类内散布矩阵奇异情况下最优鉴别矢量集的求解问题，而且 较大幅度地降低了求解最优鉴别矢量集的计算量，提高了计算速度。在o r l 人脸库上 的试验结果表明，其特征抽取的速度提高了近3 倍。 该文对核f i s h e r 鉴别分析( k f d a ) 进行了深入分析，发现了一种与之等价的但 更为简单的非线性特征抽取方法，即先利用一个函数向量映射将原始1 1 维输入空间r n 变换到一个更低维的空间r “( n 是训练样本的数目，n n ) ，然后在该空间上利用线性 f i s h e r 鉴别分析进行最优特征抽取。在此基础上，本文给出了特征抽取的般模型， 根据此模型，设计了一个基于矩阵相似度的特征抽取算法。最后，在o r l 人脸库上的 实验结果验证了本文所提模型的有效性。 目前，尽管核方法在图象等模式识别领域应用的非常广泛和成功，但也存在如下 一些问题：一、构造特征空间h 中的核矩阵k 所耗费的计算量非常大。二、当训练样 本数n 很大时，一方面会使得核矩阵的存储空间急剧增加，因为核矩阵的维数为n x n ： 另一方面造成核矩阵的不可逆。为此，本文提出了两种两阶段的核特征抽取方法： p c a + k f d a 和p c a + k p c a ，即在进行非线性映射之前，首先利用经典的主分量分析 降维，然后再执行核f i s h e r 鉴别分析( k f d a ) 或核主分量分析( k p c a ) 。为了进一步降 低经典p c a 的处理时问，使本算法具有更高的效率，对c p c a 进行了改进，提出了 静务玄攫j 走攀 摘要博士论文 直接基于图象矩阵的主分量分析( i p c a ) 。在o r l 标准人脸库上的试验结果验证了所 提算法的有效性。 聚类技术是模式式别领域应用非常广泛的非监督学习技术，为了解决核方法中计 算复杂度随着训练样本的数目的增加而增大的问题，本文提出了一种基于聚类的核矩 阵维度缩减技术，它的思想就是首先利用非线性映射牵将原始输入空间变换到某高维 特征空间，然后根据k 一均值聚类算法计算代表集，利用该代表集计算得到一组标准正 交的基向量，构成一个低维的投影子空间。在c e n p a r m i 手写体阿拉伯数字库的试 验结果证实了所提算法的有效性。 本文提出了一种融合小波特征的核f i s h e r 鉴别分析方法，即在进行非线性映射之 前，首先利用小波变换对原始输入图象进行预处理，抽取图象的小波特征，然后在频 域上进行核f i s h e r 鉴别分析。在0 r l 标准人脸库上的试验结果表明所提出的方法不仅 在识别性能上优于现有的核f i s h e r 鉴别分析方法，而且，特征抽取的速度提高了近1 3 倍；在y a l e 人脸库上进一步证实了本文方法的有效性。 因为传统的p c a 方法是以总体协方差矩阵作为产生矩阵的k - l 展开方法，本身 无法利用训练样本的类别信息( 包括k p c a ) 。另一方面，p c a 是基于线性变换的特 征抽取方法，无法抽取非线性特征，第三，p c a 主要选取模式样本的主分量信息，忽 视了可能对分类仍然有用的次分量信息。针对p c a 的上述缺点，本文提出了一种改进 的核主分量分析方法核最优鉴别k - l 变换方法，该方法不仅能够抽取模式的非线 性最优表示特征，而且这些特征具有与l d a 等价的鉴别力，并且保留了一部份有用 的次分量信息( 二阶矩鉴别信息) 。在o r l 标准人脸库上的试验结果验证了所提的方 法的有效性。 关键词：模式识别，特征抽取，核方法核主分量分析，核f i s h e r 鉴别分析，k 均值聚类，小波变换，特征抽取模型，特征空间，人脸识别，手写体字符识别 i l 簿南章程，走掌 博士论文 基于核的非线性特征抽取与图象识别研究 a b s t r a c t f e a t u r ee x t r a c t i o ni st h ee l e m e n t a r yp r o b l e mi nt h ea r e ao fp a t t e r nr e c o g n i t i o n f o r i m a g er e c o g n i t o nt a s k s ，e x t r a c t i o no fe f f e c t i v ei m a g ef e a t u r e si st h ek e ys t e p k e r n e l - b a s e d f e a t u r ee x t r a c t i o nm e t h o d sa r ca v e r y e f f e c t i v en o n l i n e a rf e a t u r ee x t r a c t i o nm e t h o dw h i c hi s r e c e n t l yp r o p o s e db yv a p n i k i nt h i sp a p e r , w e f o c u so u ra t t e n t i o no nk e r n e l b a s e dn o n l i n e a r f e a t u r ee x t r a c t i o na n d d e v e l o p s o m eh e w a l g o r i t h m sa sr e g a r d si t a n d ，t h e s ea l g o r i t h m sa r e v e r i f i e dt ob ee f f e c t i v ei nt h ea p p l i c a t i o no ff a c ei d e n t i f i c a t i o na n dh a n d w r i t t e nc h a r a c t e r r e c o g n i t i o n i ti sw e l lk n o w nt h a tf i s h e r - b a s e dd i s c r i m i n a n t a n a l y s i s m e t h o d sa r et h em o s t e f f e c t i v ef e a t u r ee x t r a c t i o nm e t h o d t h ek e r n e l b a s e ds t a t i s t i c a iu n c o r r e l a t ed i s c r i m i n a n t a n a l y s i si sp r o p o s e d i nt h ep a p e r t h ep r o p o s e dm e t h o dd o n to n l ye x t r a c tn o n l i n e a rf e a t u r e s e f f e c t i v e l y , b u ta l s o r e m o v e ss t a t i s t i c a lc o r r e l a t i o nb e t w e e nc o m p o n e n t so ft h ep a t t e r n s a m p l e s o n t h i s b a s i s ， af a s t a l g o r i t h m f o re x t r a c t i o no ft h e o p t i m a l n o n l i n e a r d i s c r i m i n a n tv e c t o r si n h j 【g h d i m e n s i o n a lf e a t u r es p a c ei s p r e s e n t e d u n l i k et h e k f d a m e t h o d ，t h ep r o p o s e da l g o r i t h mo n l yn e e dt op e r f o r mi nal o wd i m e n s i o n a lt r a n s f o r m e d s p a c e ，w h i c hl e a d st os i g n i f i c a n tc o m p u t a t i o n a lr e d u c t i o n t h ee x p e r i m e n t a lr e s u l t so n o r l f a c ed a t a b a s ev e r i f yt h a tt h ep r e s e n t e da p p r o a c hi sf a s t e rt h a nk f d ai nt e r m so fr e c o g n i t i o n t i m ew h i l er e t a i nt h e i ra c c u r a c y f e a t u r ee x t r a c t i o ni so n eo ft h em o s te s s e n t i a lp r o b l e m si np a t t e r nr e c o g n i t i o n k e r n e l f i s h e rd i s c r i m i n a n ta n a l y s i s ( k f d a ) i st h o r o u g h l ys t u d i e di nt h ep a p e r ae q u i v a l e n tb u t m o r e s i m p l en o n l i n e a rf e a t u r ee x t r a c t i o nm e t h o d i sf o u n d t h em a i ni d e ao ft h i sm e t h o di s t h a tt h eo r i g i n a li n p u ts p a c er ni st r a n s f o r m e di n t oal o w e rd i m e n s i o n a lf e a t u r es p a c er n w i t hnt h en u m b e ro ft h et r a i n i n gs a m p l e sa n dn n i nw h i c hl i n e a rf i s h e rd i s c r i m i n a n t a n a l y s i si sp e r f o r m e df o re x t r a c t i o n o fo p t i m a ld i s c r i m i n a n tf e a t u r e s o nt h i sb a s i s ，a g e n e r a lm o d e l f o rf e a t u r ee x t r a c t i o ni sp r o p o s e d ，b yw h i c h , am a t r i xs i m i l a r i t yb a s e df e a t u r e e x t r a c t i o na i g o r i t h mi sd e v e l o p e d f i n a l l y , t h ee x p e r i m e n t a lr e s u t so no r li n d i c a t et h a tt h e p r o p o s e d m o d e li se f f e c t i v e a t w o s t a g e sk e r n e lf e a t u r ee x t r a c t i o nm e t h o d s f o rf a c er e c o g n i t i o ni sd e v e l o p e di n t h i s p a p e r _ t h ea l g o r i t h mi n c l u d e st w os t a g e s ：f i r s t l y , t h ec l a s s i c a 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 ( c - p c a ) i se m p l o y e dt oc o n d e n s et h ed i m e n s i o no fi m a g ev e c t o r w h a tf o l l o w s ， k e r n e lf i s h e rd i s c f i m i n a n t a n a l y s i s ( k f d a ) o r k p c aa r e a p p l i e d t ot h er e d u c e d d i m e n s i o n a l t r a i n i n gs a m p l e s o n t h i s b a s i s ，a m o r ee f t c i e n t m e t h o d ，c a l l e d i - p c a + k f d a i p c a + k p c a , a r ep r o p o s e d d i f f e r e n tf r o mt h ep r e v i o u sm e t h o dw h e r e c p c ai sb a s e do nv e c t o r s ，i - p c ai st oe x p l o i t si m a g em a t r i c e st od i r e c t l yc o n s t r u c tt h e 糍南章蹊j 太季i l l a b s t r a c t 博士论文 i m a g e t o t a ls c a t t e rm a t r i x f i n a l l y , t h e e x p e r i m e n t a lr e s u l t so no r l f a c ed a t a b a s e si n d i c a t e t h a tt h ep r o p o s e dm e t h o d si sm o r ee f f i c e n tt h a nk f d a w h i l e r e t a i n i n g t h es a m e r e c o g n i t i o n a c c u r a c y c l u s t e r i n gi sau n s u p e r v i s e dl e a r n i n gt e c h n i q u ew i d e l ya p p l i e dt ot h ef i e l do fp a t t e r n r e c o g n i t i o n t o s o l v et h e s c a l a b i l i t y f o rk e r n e l m e t h o d s ，an o v e lm e t h o d f o r d i m e n s i o n a l i t yr e d u c t i o no f k e r n e lm a t r i xi sp r e s e n t e di nt h e p a p e r i t sm a i ni d e ai st h a tt h e o r i g i h a li n p u ts p a c ei sf i r s tt r a n s f o r m e dt oah i 曲d i m e n s i o n a lf e a t u r es p a c ev i aan o n l i n e a r m a p p i n g 巾t h e k - m e a n sc l u s t e r i n g a l g o r i t h m i su s e dt or e d u c et h en u m b e ro ft h e t r a n s f o r m e dt r a i n i n gs a m p l e sa n dar e d u c e ds e t ，a l s oc a l l e dr e p r e s e n t a t i v es e t ，i sd e r i v e d b a s e do nt h er e p r e s e n t a t i v es e t ，as e to fo r t h o g o n o r m a lb a s i sv e c t o r si so b t a i n e da n du s e dt o f o r man e wl o w e rd i m e n s i o n a lp r o j e c t i o n s u b s p a c e 1 1 h 。p r o p o s e dm e t h o di s t e s t e do n c e n p a r m i h a n d w r i t i n gd i g i td a t a b a s eo fc o n c o r d i au n i v e r s i t y t h ee x p e r i m e n t a lr e s u l t s s h o wt h ep r o p o s e dm e t h o dc a ns i g n i f i c a n t l yr e d u c ec o m p l e x i t yo ft h ef o u n dc l a s s i f i e r s w h i l e r e t a i n i n gt h e i ra c c u r a c y t h ep a p e rd e v e l o p e san o v e ln o n l i n e a rf e a t u r ee x t r a c t i o nm e t h o db a s e do nw a v e l e t f e a t u r e s i t sm a i ni d e ai st h a tw a v e l e tt r a n s f o r mi sf i r s te m p l o y e dt op r e p r o c e s st h eo r i g i n a l t r a i n i n gi m a g e s b e f o r et h en o n l i n e a rm a p p i n ga n dt h r e eg r o u p so fw a v e l e t f e a t u r e s ，l o w e s t f r e q u e n c ys u b i m a g e ，h o r i z o n t a ld e t a i l a n dv e r t i c a ld e t a i l ，a r ed e r i v e dr e s p e c t i v e l y w h a t f o l l o w s ，k e r n e lf i s h e rd i s c d m i n a n ta n a l y s i s ( k f d a ) i sp e r f o r m e do nt h r e ec l a s s e so f w a v e l e tf e a t u r e s ef i n a ld i s c r i m i n a n tf e a t u r ev e c t o r sa r eo b t a i n e df r o mw h i c haf e a t u r e f u s i n gm e t h o di sd e v e l o p e d f i n a l l y , n ee x p e r i m e n t a lr e s u l t s o no r lf a c ed a t a b a s e s i n d i c a t et h a tt h ep r o p o s e dm e t h o di sm o r ee f f e c t i v et h a nt h ec u r r e n tk f d a a n d ，m o r e i m p o r t a n t l y , i t sc o n s u m e dt i m ei nf e a t u r ee x t r a c t i o ni so n l yo n et h i r t e e n t ho ft h a to fk f d a m o r e o v e r , t h ee x p e r i m e n t sa l s od e m o n s t r a t et h a tt h i sm e t h o di sr o b u s ti nu n c o n t r o l l e d l i g h t i n gc o n d i t i o n t r a d i t i o n a lp c a b e l o n g s t oa nk le x t e n s i o nm e t h o dw h i c hi sb a s e do nt h et o t a l c o v a r i a n c em a t r i x i tf a i l st ou t i l i z et h el a b e li n f o r m a t i o no ft r a i n i n gs a m p l e s ( i n c l u d i n g k p c a ) d u e t ot h el i n e a r i t yo fp c ai ne s s e n c e ，n o n eo fn o n l i n e a rf e a t u r e sa r ee x t r a c t e d i n a d d i t i o n ，p c as e l e c t st h ep r i n c i p a lc o m p o n e n t so ft r a i n i n gs a m p l e sb u tc a n c e l so u ts o m e u s e f u lm i n o rc o m p o n e n t sf o rc l a s s i f i c t i o n c o n s i d e r i n gt h ea b o v ew e a k n e s so fp c a , k e r n e l - b a s e do p t i m a ld i s c r i m i n a n tk - lt r a n s f o r m a t i o nw i t ht h eo p t i m a ld i s c r i m i n a n tp o w e r i sp r e s e n t e di nt h ep a p e r n ep r o p o s e dm e t h o di sn o to n l ya b l et oe x t r a cn o n l i n e a rf e a t u r e s w h i c hb e n e f i tc l a s s i f i c a t i o n m o r e f i n a l l y , t h ee x p e r i m e n t a l r e s u l t st e s t e do no r lf a c e d a t a b a s e si n d i c a t et h a tt h ep r o p o s e dm e t h o di se f f e c t i v ef o rc l a s s i f i c a t i o np e r f o r m a n c e k e yw o r d s ：k e r n e lm e t h o d ，k e r n e lp r i n c i p a la n a l y s i s ，k e r n e l f i s h e rd i s e r i m i n a n t a n a l y s i s ，k - m e a nc l u s t e r i n g ，w a v e l e tt r a n s f o r m a t i o n ，f e a t u r ee x t r a c t i o nm o d e l ，f e a t u r es p a c e ， f a c er e c o g n i t i o n ，h a n d w r i t t e nd i 百t a lr e c o g n i t o n i v 辩由幸攫j 走筝 博士论文 基于核的非线性特征抽取与图象识别研究 第一章绪论 特征抽取是模式识别研究的最基本问题之一对于图象识别而言，抽取有效的 图象特征是完成图象识别的首要任务汴 征抽取的目的是为了有效地实现分类识别， 将原始数据映射( 变换) 到某低维空间，得到最能反映分类本质的特征。迄今为止， 已经提出了大量的、有效的线性特征抽取方法，其中，线性投影分析，包括主分量 分析( 或称k - l 变换) 和f i s h e r 鉴别分析，是线性特征抽取算法中最为经典和广泛 使用的方法。尽管现有的线性特征抽取方法在模式识别和图象处理领域取得了成功， 但上述特征抽取方法是基于样本模式的一阶矩和二阶矩，无法抽取图象模式的高阶 信息；并且它们本质上都是基于线性变换，通常无法表达诸如人脸等图象的复杂的 非线性分布结构。 最近，基于核的非线性特征抽取技术，受到了广泛关注，正成为当前模式识别 领域中一个迅猛发展的新方向。它最初是由v v a p n i 牌出并应用于支持向量机 ( s v m ) 中。s v m 方法是建立在统计学习理论的v c 维理论和结构风险最小原理基 础上的，根据有限的样本信息在模型的复杂性( 即对特定训练样本的学习精度， a c c u r a c y ) ：和学习能力( 即无错误地识另口任意样本的能力) 之间寻求最佳折衷。以期获 得最好的推广能力( g e n e r a l i z a f i n a b i l i t y ) 。为了解决非线性可分问题，支持向量机算 法将实际问题通过非线性变换转换到高维的特征空间( f e a t u r es p a c e 砑，在高维空间中 构造线性判别函数来实现原空间中的非线性判别函数，为了避免“维度灾难”，这种 非线性映射是通过定义适当的内积函数实现的，这种特殊性质能够保证机器有较好 的推广能力，同时它巧妙地解决了维数问题，其算法复杂度与样本维数无关，通常 这种技巧称为核方法或核映射方法。后来，由s c h 0 1 k o p f 等人1 6 1 5 2 , 7 0 j 将该思想首先应 用于特征抽取中，提出了核主分量分析r ( k p c a ) 。之后，m i k a 等人【6 3 ，6 4 ，6 5 ，6 刚、b a u d a t 和a n o u a r l 7 1 】以及r o t h 和s t e i l l a g e 【7 2 】利用核方法将f i s h e r 线性鉴别分析进一步拓广 到非线性情形，提出了核h s h c r 鉴别分析( k f d a ) 方法。目前，核方法已经成为 模式识别领域新的研究热点，在模式识别、回归估计、概率密度函数估计等方面都 有应用。例如，在模式识别方面，对于手写数字识别、语音识别、人脸图象识别、 文章分类等问题，核特征抽取和分类算法在精度上已经超过传统的特征抽取和分类 算法或与之不相上下。 目前，国际上对基于核的特征抽取理论的讨论和进一步研究正逐渐广泛，而国 速露弗幸锺1 走拳1 第一章绪论博士论文 内在此领域研究刚刚开始，因此我们需要及时学习掌握有关理论，开展有效的研究 工作，使我们在这一有着重要意义的领域中能够尽快赶上国际先进水平。 1 。1 线性特征抽取方法概述 主分量分析( f c a ) 在最小协方差意义下给出了模式样本的最优表示。p c a 的两 大优点是：一、消除了模式样本之间的相关性；二、实现了模式样本的维数压缩。 k - l 变换能将高维的模式样本压缩为更易于处理的低维样本，换而言之，p c a 给出 了高维数据的一种简约的表示。由于以上优点，p c a 广泛地应用于模式识别，数据 压缩等领域。尽管关于p c a 的研究可谓源远流长，但将其用于解决人脸识别问题却 是最近十年的事。直到二十世纪九十年代初，k i r b y 和s i r o v i c h 7 1 等人才讨论了利用 p c a 进行人脸图象的最优表示问题。接着，t u r k 和p e n t l a n d 4 0 “j 探讨了这种表示的 物理意义。他们惊奇的发现，k l 展开后的特征向量在还原成图象矩阵时，竟然是 一张张标准化的人脸! 采用k - l 展开表示人脸的本质被揭示了出来，即用一系列标 准的人脸图象( 由特征向量构成，故被形象地称为特征脸，即e i g e n f a c e ) 通过加权 叠加来表示人脸。用这些表示系数作为人脸的特征进行分类识别。这就是著名的特 征脸( e i g e n f a c e s ) 方法。 关于线性鉴别分析( l d a ) 的研究应追溯到f i s h e r 在1 9 3 6 发表的经典论文【1 9 1 ， 其基本思想是选择使得f i s h e r 准则函数达到极值的向量作为最佳投影方向，从而使 得样本在该方向上投影后，达到最大的类间离散度和最小的类内离散度。在f i s h e r 思想的基础上，w i l k s 2 0 l ，和d u d a 2 1 】分别提出了鉴别矢量集的概念，即寻找一组鉴 别矢量构成子空间，以原始样本在该子空间内的投影矢量作为鉴别特征用于识别。 该方法被称为经典的f i s h e r 线性鉴别分析方法。目前该方法仍然广泛应用于人脸识 别等领域。除了经典的f i s h e r 线性鉴别分析方法外，在1 9 7 0 年，s a m m o n 提出了基 于f i s h e r 鉴别准则的最佳鉴别平面【2 2 1 的概念，随后，f o l e ya n d s a m m o n1 2 3 1 进一步 提出了采用一组满足正交条件的最佳鉴别矢量集进行特征抽取的方法。该方法被命 名f o l e ya n ds a m m o n 鉴别分析。在文献【2 3 】中，f o l e y 给出了求解两类问题的最佳鉴 别矢量集的具体算法。d u c h e n ea n dl e c l e r c q l t m 给出了多类情况下最佳鉴别矢量集的 计算公式。最近，z j i na n dj y y a n g 2 6 - 3 0 l 等从统计不相关的角度，提出了具有统 计不相关性的最优鉴别矢量集的概念。与f o l e y s a m m o n 鉴别矢量集不同的是，具 有统计不相关性的最优鉴别矢量集是满足共轭正交条件的。j i n a n d y a n g 的方法被称 为不相关的鉴别分析或j i n y a n g 线性鉴别法。j i n a n d y a n g 在文献 2 6 , 2 7 l 中给出了求解 最佳鉴别矢量集的精确算法，但该算法的弱点是过程较为复杂，所耗费的计算量较 2 姆南章瑶 史擘 博士论文 基于核的非线性特征抽取与图象识别研究 大。j i n 在文献1 28 j 中就一种特殊情况，即f i s h e r 准则函数所对应的广义特征方程的 特征值互不相等的条件下，给出了求解不相关的最佳鉴别矢量集的一种简捷算法， 并指出在该条件下不相关的线性鉴别分析与经典的f i s h e r 鉴别法【2 1 】是等价的。 以上提到的各种方法仅适用于类内散布矩阵非奇异( 可逆) 的情形，但实际中 确实存在着大量的典型的小样本问题，比如在人脸等图象识别问题中，类内散布矩 阵经常是奇异的。这是因为待识别的图象矢量的维数一般较高，而在实际问题中难 以找到或根本不可能找到足够多的训练样本来保证类内散布矩阵的可逆性。因此， 在小样本情况下，如何抽取f i s h e r 最优鉴别特征成为一个公认的难题1 3 3 , 4 0 】。近几年 来关于小样本情况下线性鉴别分析方法的研究激起了人们的广泛兴趣，不少解决该 类问题的方法相继提出。概括起来，这些方法可分为以下两类： 一、基于变换的( t r a n s f o r mb a s e d ) 方法。即在采用线性鉴别分析之前，通过事先 给定的线性变换来达到降低图象向量的维数从而消除类内散布矩阵奇异性的目的。 基于变换的典型方法有：b e l h u m e u r 等提出的f i s h e r f a c e s 方法【”j ，d l s w e t s 等人提 出的最具有鉴别能力的特征抽取方法( m o s td i s c r i m i n a t o r yf e a t u r e s ) 1 3 4 和c j “u 等 提出的增强f i s h e r 线性鉴别模型法( e n h a n c e df i s h e r l i n e a rd i s c r i m i n a n tm o d e l s ， e f m ) 3 5 1 。这三种方法的共同点是，均采用主分量分析( p c a ) 来事先降低图象向量的 维数，在p c a 变换后的特征空间内，再采用f i s h e r 线性鉴别分析做二次特征抽取。 最近，j i n 2 6 删采用另外一种k l 变换方法( 以训练样本的类间相关矩阵作为k - l 变换的产生矩阵) 作首次特征抽取，然后再使用不相关的鉴别分析进一步抽取鉴别 特征。 二、基予算法的( a l g o r i t h mb a s e d ) 方法。即从算法本身入手，通过发展直接针对 于小样本问题的算法来解决问题。h o n g 3 蚋，l i u 4 0 1 ，g u o 4 ”，c h e r t 3 6 j 等人分别在这方面 进行了探索，他们所建立的算法理论无疑为这一问题的彻底解决奠定了基础。h o n g 等提出的扰动法【3 9 】的基本思想是，当类内散布矩阵奇异时，通过对之进行一个小的 扰动，使得扰动后的矩阵变为非奇异的，以扰动后的矩阵代替原来的类内散布矩阵 进行鉴别矢量的求解，从而将问题转化为可逆的情形加以解决。明显地，h o n g 的方 法是一个近似算法。与之不同的是，k l i u 给出了一个精确算法，称为正交补空间 法1 4 1 。该方法首先证明了，小样本情况下的最优鉴别矢量必存在于原始样本空间的 一个子空间的正交补空间内，进而通过空间变换，基于变换后的f i s h e r 准则求解最 优鉴别矢量。g u o 4 1 , 1 1 6 l 从鉴别准则函数的角度发展了k 工j u 的方法，提出了一个广 义的f i s h e r 鉴别准则函数，并给出了求解基于该准则函数的最优鉴别矢量集的算法。 事实上，c h e n 的零空间法只是郭跃飞【4 2 】方法的一个特例，即在类内散布矩阵的零空 辩南章理j 天掌 3 第一章绪论 博士论文 问内寻找极大化类间散布量的一组标准正交的特征向量并将其作为投影轴。该方法 抛弃了零空问之外的鉴别信息。最近，c a r n e g i em e l l o nu n i v e r s i t y 的h y ua n dj y a n g 【3 8 】提出了一种直接的线性鉴别分析方法( d i r e c tl d a ) 。该方法在本质上与文献 1 1 7 的方法等价。 1 。2 基于核的非线性特征抽取方法的研究与发展 1 2 1 核方法产生的理论背景 首先通过两个例子了解为什么现有的线性分类算法不能有效地求解许多分类和 回归问题。 例1 不能用线性鉴射函数进行分类的最简单的例子是布尔异或函数： v = r 黯队屯锄“托。1 懈2 叫 该问题的几何表示见图1 1 。 图1 1 异或分类问题 显而易见，我们找不到任何条直线能够将两个正例( ”+ ”) 和负例( o ”) 分开， 因此，该问题是线性不可分的。对于一个如此简单的问题，但却找不到一个线性的 学习算法。解决此问题的一种方法就是采用多级线性鉴别函数，但是我们希望可以 找到另外一种不同的但更为简单的方法来解决此非线性可分问题。对初始的模式向 量进行扩展，使之包括新的特征，这些新的特征是原始输入特征的二阶组合。即将 x = ( x l ，x 2 ) 1 映射为巾( x ) = ( x 1 ，x 2 ，x 1 x 2 ) ，设w = ( 一1 ，1 ，2 ) 。，b = 0 5 ，则4 个训练样本能够被 正确地分类。几何上，我们看到点( 1 ，1 ) 在第3 维上升高了，则最终的分布可以很容 易地通过一个平面将这两类样本正确她分开。 4、簿毋章瑶，太掌 博士论文 基于核的非线性特征抽取与图象识别研究 图1 2 非线性可分问题 例2 考虑另一个分类问题：正例( ”+ ”) 位于一个圆内，而负例( “0 ) 位于该圆 外( 见图) ，根据解析几何，我i f 女n 道这两类数据可以通过形如“x ) = s i g n ( # + 工；一1 ) 的判别函数正确地分开，并且，该问题在x 上是非线性可分的，但将x 变换为 中( x ) = ( x 。，x 2 ，x 1 x 2 ，# ，工；) ，令w = ( o ，0 ，0 ，1 ，1 ) ，b = 一1 ，则该问题在巾( x ) 下就变成线性可分 的。这是因为在新的特征空间内的线性鉴别函数包括了非线性鉴别函数，如原始输 入空间中的圆和椭圆。 从上面的两个例子我们看到，如果一个问题在其定义的空间中不是线性可分的， 这时可考虑通过构造新的特征向量，把问题转换到一个新的空间中，这个空问一般 比原空间维数更高，但却可以用线性鉴别函数实现原空间中的非线性鉴别函数。实 际上，对于任意高次鉴别函数，都可以通过适当的变换( 映射) 转化为另一空间中 的线性鉴别函数来处理。通常把这种变换空间中的线性鉴别函数称作原问题的广义 线性鉴别函数。虽然这种变换理论上可以用简单的线性鉴别函数来解决十分复杂的 问题，但由于变换空间中的维数往往很高，容易陷入所谓的“维数灾难”而使得问 题变得实际上不可实现。 但随着s v m 中的核方法( k e r n e lt r i c k ) 的成功应用，为解决广义线性鉴别函数 中存在的所谓“维数灾难”扫清了障碍。核方法的主要思想就是，要解决一个非线 性可分问题，首先设法通过非线性变换巾将原问题转化为另一特征空间中的线性问 题( 见图1 3 ) 。为了避免直接显式地计算由，定义一个核函数( 内积运算) k ，使得 对于任意两个样本模式x , z ，有k ( x ，z ) - - ( 中( x ) ，巾( z ) ) 。我们可以看到，一方面甚至不必 知道采用的非线性变换的形式，只要它的核函数k 即可，另一方面新空间中的线性 蟛南事理j 天擘 5 第一章绪论 博士论文 问题的计算复杂度并没有增加，并且与它的维数无关。 输入空蚵特征空间 图1 3 核映射示意图 定义1 1 核函数是一个函数k ，对于所有的x ，z x ，使得 k ( x ，z ) = ( 1 1 ) 其中，m ：x f 是一个从输入空间x 到特征空问( 内积空问) f 的映射。 根据统计学习理论【3 】和泛函的有关理论，只要一种核函数k ( x ，z ) 满足m e r c e r 条 件，它就对应某一特征空间中的内积。 定理11 3 】( m e r c e r 条件) 对于任意的对称函数k ( x ，x ) ，它是某个特征空间中的 内积运算的充分必要条件是，对于任意的畋x ) * o 且r c p 2 ( x ) d x cm ，有 f f k ( x ： ) 叩( x ) 中( x ) d x d x ，o ( 1 2 ) 根据内积的性质，核函数k 必须是对称的，因此，k = ( k ( x i ，x j ) ) i j 是对称矩阵，可 以改写为如下的形式： k = v a v t ( 1 3 ) 其中，v 是由k 的特征向量构成的标准正交矩阵，a 是由与v 中的特征向量相对应 的特征值构成的对角矩阵。 设k 1 和k 2 是x x x 上的核函数，其中，x r n ，a e r + ，f 是x 上的一实值函数， 中：x r ”( 1 + 4 ) k 3 是r “x r “上的一核函数，b 是一对称半正定的i i n 阶矩阵，则下面的