（信号与信息处理专业论文）流形学习方法理论研究及图像中应用.pdf

摘要 摘要 科学的进步，尤其是信息产业的发展，把我们带入了一个崭新的信息时代。 在信息时代的科学研究中，不可避免地会遇到大量的高维数据，特别是图像数据。 在实际应用中，用图像数据来表示的观测点可以模拟成可能带有噪声的低维非线 性流形上的样本点或近似这些样本点。因此，流形学习已成为数据挖掘的一个重 要手段，目的是找出图像高维空间中隐藏的低维结构或一些有益的性质。 有一些因素影响着流形学习方法的效率。本征维数估计方法研究是高维图像 数据处理领域的重要研究方向，如何准确地寻求本征维数可以帮助人们认识图像 数据的本征结构，对于高维图像数据的维数约简以及其它的后续处理都具有重要 的指导意义。虽然先前的研究指出了不同流形学习之间的联系，但是在核框架下 来看不同流形学习之间的联系却是一个新的研究方向。黎曼正则坐标包含了流形 中指定点到邻近点的方向和距离信息，如何将这种源于微分几何的技术应用到流 形学习中也是值得研究的课题之一。对于这些问题，本文给出了比较完善的解答。 本文的主要贡献如下： 1 探讨了一种新的图像数据的本征维数估计算法。在没有流形几何或拓扑的 先验知识的条件下，算法的关键在于如何构建一个基于流形切丛的近似单纯复形。 这种算法的一个重要性质就是其计算复杂度只跟流形维数相关，而不是嵌入空间 的维数相关。实验结果说明了本文算法在平面、空间上重建曲线、表面以及人脸 图像本征维数估计中都取得了较好的效果，也分析了一个失败的情况。 2 探讨了一种新的鲁棒流形学习方法。近年来提出的概率子空间混合模型对 于图像流形学习是一种非常有用的方法，其对全局映射的缺乏可以由最近发展起 来的基于局部线性嵌入，也称为局部线性坐标的方法来改善。然而，在很多存在 野值点的实际应用中，这种方法缺乏必要的鲁棒性。这里给出了一种结合概率子 空间混合模型的t 分布的鲁棒混合模型。实验结果表明这种鲁棒子空间混合模型在 图像数据集的密度估计和分类中具有非常好的优势。通过在嵌入步骤中引入重新 定义的加权，很好的解决了局部嵌入坐标中的鲁棒性问题。 3 首先，我们从核技术观点出发，对九种众所周知的流形维数约简算法进行 了说明。i s o m a p ，图l a p l a c i a n 特征映射和局部线性嵌入( l i e ) 都利用一个局部 邻域信息来构建流形的全局嵌入，可以看作基于特别构造的格莱姆矩阵的k p c a ， 摘要 揭示了三种算法之间的相似之处和不同之处。最后，i s o m a p 是一个广泛使用的低 维嵌入方法，是加权图的几何距离跟经典尺度分析( 测度多尺度分析) 相结合。我们 将注意力集中在i s o m a p 中没有考虑到的两个关键问题：( 1 ) 泛化能力；( 2 ) 拓扑稳定 性。我们探讨了一种具备以上两种性质的鲁棒核i s o m a p 方法，将i s o m a p 和m e r c e r 核机器联系起起来。通过k p c a ，泛化能力也就自然呈现出来。对于拓扑稳定性， 观察图中的网络流，我们探讨了一种消除临界野值点的方法。本文方法的泛化能 力和稳定性在( 图像) 数据集的实验结果中也得到了证实。 4 探讨了一种基于黎曼正则坐标的快速流形学习方法。这种坐标系统可以看 成e u c l i d e a n 空间的笛卡尔坐标的一种泛化。借助一些来自微分几何的基本概念以 及使用d i j k s t r a 算法用于计算图最短路径，可以实现高维数据的维数约简。我们希 望本文方法开启一种新的图像处理的分析方法，其中，坐标系统是从高维实验数 据学习获得，而不是事先采用定义好的模型。 关键词：流形学习，本征维数，核技巧，等距特征映射，单纯复形，图像数 据 a b s l r a c t a b s t r a c t w i t ht h ep r o g r e s so fs c i e n c e ，e s p e c i a l l yt h ed e v e l o p m e n to fi n f o r m a t i o ni n d u s t r y , w ee n t e rab r a n d - n e wi n f o r m a t i o na g e w h e nd o i n gr e s e a r c hi ni n f o r m a t i o na g e ，o n ei s i n e v i t a b l yc o n f r o n t e dw i t hl a r g ev o l u m e so fh i g h - d i m e n s i o n a ld a t a , e s p e c i a l l yi m a g e d a t a i nr e a l w o r l da p p l i c a t i o n s ，o b s e r v a t i o n sr e p r e s e n t e da si m a g ed a t ao rv e c t o r sc a l l b em o d e l e da s s a m p l e sl y i n go no rc l o s et oal o w d i m e n s i o n a ln o n l i n e a rm a n i f o l d p o s s i b l yw i t hn o i s e h e n c e ，d a t ar e d u c t i o ne s p e c i a l l yn o n l i n e a rd i m e n s i o n a l i t y r e d u c t i o ni sa ni m p o r t a n tt o o lo fd a t am i n i n g ，a n dt h eg o a lo fd i m e n s i o nr e d u c t i o ni st o f m do u tt h el o wd i m e n s i o n a ls t r u c t u r eo ft h en o n l i n e a rm a n i f o l df r o mt h e h i g h d i m e m i o n a ld a t a s o ，m a n i f o l dl e a r n i n gi s 姐i m p o r t a n tt o o lo fd a t am i n i n g 。a n dt h e g o a lo fi ti st of i n do u tt h eh i d d e nd i m e n s i o n a ls t r u c t u r eo ft h eh i g hd i m e n s i o n a li m a g e d a t a t h e r ea r es o m ec o n l m o ni s s u e st h a td e t e r m i n et h ee f f e c t i v e n e s so ft h em a n i f o l d l e a r n i n g t h er e s e a r c h i n go ni n t r i n s i cd i m e n s i o ne s t i m a t i n gt e c h n i q u e sh a sb e c o m ea l l i m p o r t a n tr e s e a r c hd i r e c t i o ni nt h er e a l mo fh j | g hd i m e n s i o n a li m a g ed a t a h o wt o e x a c t l ye s t i m a t et h ei n t r i n s i cd i m e n s i o ni sh e l p f u lf o rp e o p l et od i s c o v e rt h ei n t r i n s i c c o n f i g u r a t i o no ft h ei m a g ed a t a , a n dp l a yag u i d i n gr o l ei nd i m e n s i o nr e d u c t i o na n d o t h e rs u b s e q u e n tp r o c e s s e s a l lm a n i f o l dl e a r n i n gs h a l eac o m m o nc h a r a c t e r i s t i ci nt h a t t h e yu s eal o c a ls t r u c r l r e o nt h ed a t at o g l o b a l l ym a pt h em a n i f o l dt oal o w e r d i m e n s i o n a ls p a c e a 1 t h o u 曲p r e v i o u ss t u d i e sh a v ep o i n t e do u tr e l a t i o n s h i p sa m o n g v a r i o u sm a n i f o l dl e a r n i n g ，i ti san o v e ld i r e c t i o nt or e l a t et h e mw i t h i nak e r n e l f r a m e w o r k r i e m a n n i a nn o r m a lc o o r d i n a t e sc o n t a i ni n f o r m a t i o na b o u tt h ed i r e c t i o na n d d i s t a n c ef r o mas p e c i f i cp o i n to nam a n i f o l dt oo t h e rp o i n t sn e 舡b y i ti sw o r t ht o t r a n s l a t et h i st e c h n i q u ef r o mi t so r i g i n a ls e t t i n gi nd i f f e r e n t i a lg e o m e t r y , t ot h et a s ko f m a n i f o l d l e a r n i n g t o c o n f r o n tt h e s e p r o p o s e dp r o b l e m s ，w eg i v er e l a t i v e l y c o n s u n l i n 如a n s w e r s t h ec o n t r i b u t i o n so ft h i sp a p e ra r ea sf o l l o w s ： i an e wa l g o r i t h mf o ri n t r i n s i cd i m e n s i o no fi m a g ed a t ai sp r e s e n t e d w i t h o u ta p r i o r ik n o w l e d g eo ft h em a n i f o l d sg e o m e t r yo rt o p o l o g ye x c e p tf o ri t sd i m e n s i o n 。t h e h i a b s l r a c r k e yg o a li st oc o n s t l l l c tas i m p l i c i a lc o m p l e xb a s e do na p p r o x i m a t i o n st ot h et a n g e n t b u n d l eo ft h em a n i f o l d a ni m p o r t a n tp r o p e r t yo ft h ea l g o r i t h mi st h a ti t sc o m p l e x i t y d e p e n d so nt h ed i m e n s i o no ft h em a n i f o l d ，r a t h e rt h a nt h a to ft h ee m b e d d i n gs p a c e s u c c e s s f u le x a m p l e sa p r e s e n t e di nt h ec a s e so fr e c o n s t r u c t i n gc u r v e si nt h ep l a n ea n d s p a c e ，s u r f a c e si ns p a c e ，a n di n t r i n s i ce s t i m a t i n go fh u m a nf a c ei m a g e ；i na d d i t i o n ，a c 撇w h e nt h em g o d t h mf a i l si sa n a l y z e d 2 an e wm e t h o df o rr o b u s tm a n i f o l dl e a r n i n gi sp r e s e n t e d p r o b a b i l i s t i cs u b s p a c e m i x t u r em o d e l s ，a sp r o p o s e do v e rt h el a s tf e wy e a r s ，a r ei n t e r e s t i n gm e t h o d sf o r l e a r n i n gi m a g em a n i f o l d s t h e i rl a c k o fag l o b a lm a p p i n gc a nb er e m e d i e d b yar e c e n t l y d e v e l o p e dm e t h o db a s e do nl o c a l l yl i n e a re m b e d d i n g ，c a l l e dl o c a l l yl i n e a rc o o r d i n a t i o n h o w e v e lf o rm a n yp r a c t i c a la p p l i c a t i o n s ，w h e r eo u t l i e r sa l ec o m m o n ，t h i sm e t h o d l a c k st h e n e c e s s a r yr o b u s t n e s s h e r e ，t h ei d e ao fr o b u s t m i x t u r e m o d e l i n gb y t - d i s t r i b u t i o n si sc o m b i n e dw i t l lp r o b a b i l i s t i cs u b s p a c em i x t u r em o d e l s t h er e s u l t i n g r o b u s ts u b s p a c em i x t u r em o d e li ss h o w ne x p e r i m e n t a l l yt og i v ea d v a n t a g e si nd e n s i t y e s t i m a t i o na n dc l a s s i f i c a t i o no fi m a g ed a t as e t s i ta l s os o l v e st h er o b u s t n e s sp r o b l e m s o fl o c a l l yl i n e a rc o o r d i n a t i o n ，b yi n t r o d u c i n gaw e i g h t e dr e d e f i n i t i o no ft b ee m b e d d i n g s t e p 3 f i r s t , w ei n t e r p r e ts e v e r a lw e l l k n o w na l g o r i t h m sf o rd i m e n s i o n a l i t yr e d u c t i o n o fi n f o l d s 勰k e r n e lm e t h o d s 1 s o m a p 。g r a p hl a p l a e i a ne i g e n m a p ，a n dl o c a l l yl i n e a r e m b e d d i n g ( l l e ) a l lu t i l i z el o c a ln e i g h b o r h o o di n f o r m a t i o nt o c o n s t r u c tag l o b a l e m b e d d i n go ft h em a n i f o l d ，a l ed e s c r i b e da sk e r n e lp c a o ns p e c i a l l yc o n s t r u c t e dg r a m m a t r i c e s ，a n di l l u s t r a t et h es i m i l a r i t i e sa n dd i f f e r e n c e sb e t w e e nt h ea l g o f i t h r a s l a s t ， t s o m a pi so n eo fw i d e l y - u s e dl o w d i m e n s i o n a le m b e d d i n gm e t h o d s ，w h e r eg e o d e s i c d i s t a n c e so n aw e i g h t e dg r a p ha r gi n c o r p o r a t e dw i t ht h ec l a s s i c a ls c a l i n g ( m e t r i c m u l t i d i m e n s i o n a ls c a l i n g ) i nt h i sp a p e rw ep a yo u ra t t e n t i o nt ot w oc r i t i c a li s s u e st h a t w e r en o tc o n s i d e r e di ni s o m a p ，s u c ha s ：( 1 ) g e n e r a l i z a t i o np r o p e r t y , ( 2 ) t o p o l o g i c a l s t a b i l i t y t h e nar o b u s tk e r n e li s o m a pm e t h o d ，a r m e dw i t hs u c ht w op r o p e r t i e s ，i s p r e s e n t e d n ep r o p o s e dm e t h o dw h i c hr e l a t e si s o m a pt om e r c e rk e r n e lm a c h i n e s s o t h a tt h eg e n e r a l i z a t i o np r o p e r t yn a t u r a l l ye m e r g e s ，t h r o u g hk 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 f o rt o p o l o g i c a ls t a b i l i t y , w ei n v e s t i g a t et h en e t w o r kf l o wi nag r a p h ，p r o v i d i n g am e t h o df o re l i m i n a t i n gc r i t i c a lo u t l i e r s t h eg e n e r a l i z a t i o np r o p e r t ya n dt o p o l o g i c a l s t a b i l i t yo ft h er o b u s tk e r n e li s o m a pi sc o n f i r m e dt h r o u g he x p e r i m e n t sw i t hs e v e r a l i v a b s l r a c t ( i m a g e ) d a t as e t s 4 af a s tm a n i f o l dl e a r n i n gb a s e do nr i e m a n n i a nl l o r m a lc o o r d i n a t e si sp r e m e d t h i sc o o r d i n a t es y s t e mi si naw a yag e n e r a l i z a t i o no f c a r t e s i a nc o o r d i n a t e si n e u c l i d e a ns p a c e i no r d e rt or e d u c et h ed i m e n s i o no fh i g hd i m e n s i o n a ld a t a , o u r i m p l e m e n t a t i o nc u r r e n t l yu s e sd i j k s t r a sa l g o r i t h mf o rs h o r t e s tp a t h si ng r a p h sa n ds o m e b a s i cc o n c e p t sf r o md i f f e r e n t i a lg e o m e t r y w ee x p e c tt h i sa p p r o a c ht oo p e n 叩n e w p o s s i b i l i t i e sf o ra n a l y s i so fi m a g ed a t a , w h e r et h e c o o r d i n a t es y s t e mi sl e a r n e x lf r o m e x p e r i m e n t a lh i g h - d i m e n s i o n a ld a t a r a t h e rt h a nd e f m e dm o d e l s k e y w o r d s ：m a n i f o l dl e a r n i n g ，i n t r i n s i cd i m e n s i o n ，k e r n e l 仃i c l 【i s o m a p ，s i m p l i c i a l c o m p l e x ，i m a g ed a t a v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：眚后宏签名：里：昼鲞 日期：2 0 节年弓月弓。日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名： 导师签名：牡 日期：胁7 年玉月5 。日 第一章绪论 第一章绪论 维数约简方法是一个古老而又年轻的研究课题，其基本原理是将样本点从输 入空间通过线性或非线性变换映射到一个低维空间，从而获得一个关于原数据集 紧致的低维表示。传统的线性维数约简方法具有简单性、易解释性和可延展性等 优点，使得其在高维数据处理中是一个主要研究方向。已有的线性维数约简方法， 主要包括主成分分析( p r i n c i p a lc o m p o n e n ta n a l y s i s ，简称p c a ) 【1 】，独立成分分 析( i n d e p e n d e n tc o m p o n e n ta n a l y s i s ，简称i c a ) 田、f i s h c r 判别分析( f i s h e r d i s c r i m i n a n ta n a l y s i s ，简称f d a ) p 】、主曲线( p r i n c i p a lc u r v e s ) 1 4 1 、投影寻踪 ( p r o j e c t i o np u r s u i t ，简称p p ) 四、多维尺度方法( m u l t i d i m e n s i o n a ls c a l i n g ，简称 m d s ) 嘲等。这些方法实际是在不同优化准则之下，寻求最佳线性模型，这也是 线性维数约简方法的共性。 然而，随着信息时代的到来，不可避免地出现了大量的高维非线性数据，尤 其是高维图像数据。传统的线性维数约简方法难以直接用于分析源于真实世界的 高维非线性数据，其主要原因有：膨胀的维数导致计算量迅速上升；高维导致样 本点数相对较少，使得某些统计上的渐近性质受到破坏；传统方法在处理高维数 据时不满足稳健性要求等。因此，研究高维非线性数据面临诸多困难c 7 】，这主要是 高维带来了数据的稀疏和维数灾难，而非线性使得现有的快速成熟的线性模型不 再适用。目前主要存在两类非线性维数约简方法：一类是基于核的方法；另一类 是基于流形的方法。前者利用m e r c e r 核及其对应的再生核希尔伯特空i 间( r e p r o d u c t k e r n e lh i l b e r ts p a c e ，简称r k h s ) ，不用创建复杂的假设空间( h y p o t h e s i ss p a c e ) ， 通过定义m e r c e r 核隐式地定义特征空间。因此，大部分线性维数约简方法都有其 对应的基于核的非线性维数约简方法，比如k p c a m 、k i c a l 9 、核特征映射( k e r n e l e i g e n m a p s ) 聊等。然而，基于核的方法其难点在于如何选择一个合适的核函数， 一个好的核函数可以使数据在特征空间上线性可分或者近似线性可分，但并不是 所选核函数对于每一种数据都适用。核函数的选择反映了人们对问题的先验知识， 在实际的应用中往往是经验地选择某种核函数，比如径向基函数( r a d i a lb a s i s f u n c t i o n ，简称r b f ) 。同时，在使用核函数时不必知道具体的特征空间，使得核 函数方法缺乏物理直观，这也是核函数方法的一个缺点。后者就是近年发展起来 的基于流形学习的非线性维数约简方法，主要包括等距映射( i s o m e t r i cm a p p i n g ， 电子科技大学博士学位论文 简称i s o m a p ) 【1 l j 、局部线性嵌入方法( l o c a l l yl i n e a re m b e d d i n g ，简称l l e ) 1 2 1 、 l a p l a c i a n 特征映射( l a p l a c i a n e i g e n m a p ，简称l e ) 【l3 1 、局部切空间排列方法( l o c a l t a n g e n ts p a c ea l i g n m e n t ，简称l t s a ) 1 哪等。 流形学习中非线性维数约简方法跟线性维数约简方法相比的一个显著特点是 分析中的局部性。对数据集的内蕴结构而言，有如下特性：1 ) 由泰勒定理可知， 任意可微函数在一点的充分小的邻域内满足线性条件，形象地说，曲面流形由大 小不一的局部线性块拼接而成；2 ) 流形由许多可分割的子流形所组成；3 ) 流形 的本征维数沿着流形不断的发生变化，只有局部性才能抓住其本质特性。 1 1 流形学习 1 1 1 数学基础 流形是现代数学的概念，其严格数学定义如下： 定义1 1 ：设肘是一个h a u s d o r f f 拓扑空间，若对每一点p 肘，都有p 的一 个开邻域u 和r 4 中的一个开子集同胚，则称肘是d 维拓扑流形，简称d 维流形。 假定伊( u ) c - r 。与【，同胚，则( u ，矿) 称作流形 f 的坐标卡，烈p ) 在r 4 中的坐标称 为点p 在m 上的坐标。 有了对流形的定义，就可以概括流形学习中维数约简过程：假设数据是均匀 采样于一个高维欧式空间中的低维流形，流形学习就是从高维采样数据中恢复出 低维流形结构，即找到高维空间中的低维流形，并求出相应的嵌入映射，以实现 维数约简或者数据可视化。流形学习是从观测到的现象中寻找事物的本质，找到 产生数据的内在规律。 维数约简数学定义如下： 定义1 2 ：给定，1 个数据点：x = t l f = l ， 玉r 。 ，给出映射 ，：r o _ ，d d ；或者给出弱一些的结果：y = y i i f - 1 ，n ，) ，f r 。 ，d d 。 定义1 3 ：一个拓扑空间就是一个集对( x ，7 - ) ，其中，集合x 为一非空集合， 拓扑丁是x 的满足一下性质的子集族： ( 1 ) 下关于属于它的任意多元素的并运算是封闭的； ( 2 ) 7 关于属于它的有限多元素的交运算是封闭的； ( 3 ) 下含有空集和x 本身作为其元素。 定义1 4 ：如果对x 中任意两个不同点工，y ，都存在x 的邻域u 以及y 的邻域y 2 第一章绪论 使得u n y = 。此时，称( x ，丁) 为h a u s d o r f f 空间。 定义1 5 ：一个d 维流形就是一对( m ，a ) ，其中，j i f 为d 维流形， a = ( 以，) 】。为一c 1 的微分结构，满足以下条件： ( 1 ) ( 局部欧氏性) 以：口a 】构成膨的一个开覆盖，：_ ( 叱) c 为同胚映射； ( 2 ) ( c 相容性) 若睨n u ，则双射。：铷( u 。n ) 一纯( 吼n ) 和它的逆映射都是七次可微的，则称( ，) 与( u ，) 是相容的； ( 3 ) ( 最大性) 若u 为m 中的开集，缈：【，- 矿( 【，) c r 4 与a 中的每个( ，) 都相容，则( u ，妒) a 当r 时，称m 为光滑流形。若工u ，则称( 【，伊) e a 为工处的一个局部坐 标系，u 为坐标邻域，矿为坐标函数。 定义1 6 ：设m 和n 为两个光滑流形，g ：m - n 是连续映射。设工m ，若 存在j l f 在点工处的局部坐标系( u ，妒) 及在点g ( 工) 处的局部坐标系( y ，矿) ，使得 矿。g 。矿1 ：矿( u n 暑。( y ) ) 一矿( y ) 是在点妒( 工) 处光滑的映射，则称映射g 在点x 处 是光滑的。处处光滑的映射称为光滑映射。这种光滑映射的全体记为c 。( m ，n ) 。 当= r 时，记c 。( 肘) = c - ( m ，r ) 为光滑流形肘上的光滑函数的全体。 定义1 7 ；光滑流形m 在点工的切向量就是一个映射v 。：c - ( m ) - r ，且对 v g ， c ”( 肘) ，a ，6 r 满足： ( 1 ) 心( a g + b h ) = 叱( 占) + b y , ( ) ； ( 2 ) v ( g h ) = ( 工) 吃( g ) + g ( 工) 心( h ) 假设( u ，妒) 为点石的一个局部坐标系，则映射 吼暑_ ( 乱- 掣卜， 为点工的一个切向量。光滑流形的切向量是曲线的切向量的一种推广。点工的 切向量全体记为( m ) ，它是一个实线性空间，称之为m 在点工的切空问。 定义1 8 ：如在光滑流形m 的每个切空间( m ) 中都给定了内积，则称肘为 黎曼流形。 定义1 9 ：设c ( t 1 ，4 t 6 是黎曼流形肘中的条曲线，在c 上每点的切向 量记为u ，则可以定义曲线c 的弧张s ( c ) 为s ( c ) = 硎u 出。 定义1 1 0 ：设p 、鼋是黎曼流形m 中任意两点，则这两点间的测地距离 九( p ，q ) 为肘中连接p 、g 的所有分段光滑曲线的弧长的下确界。 电子科技大学博士学位论文 定义1 n ：设m 为d 维黎曼流形，若存在光滑映射g ：m - r 4 满足： ( 1 ) g ：肘_ g ( m 1 为同胚； ( 2 ) 对任意的n 日m ，有九( p ，q ) = 0 9 ( p ) 一占( 日) 则称m 为d 维等距流形。 1 1 2 流形学习发展历史 自从t e n e n b a u m 、r o w e i s 、s a u l 和b a l a s u b r a m a n i a n 等人2 0 0 0 年在s c i e n c e ) ) 杂志上相继发表关于流形学习的初步研究成果后【1 1 】【12 】【阍，利用流形的特性进行维 数约简的研究就成为热门的研究话题。早在1 9 9 6 年，n a y a r 等人就提出了高维图 像具有低的本征维数的现象【1 6 l 。s e u n g 等人从神经生理学的角度提出了感知以流形 的形式存在【l 。”，从认知学的角度支持了图像数据是高维空间中的流形这一观点。 d o n o h o 等人还拓展了u 正方法，提出i - i l l e 方法【l 酊，能够发现流形上局部的潜 在等距映射参数。张长水等人在u 正的基础上提出一种从低维嵌入空间向高维空 间映射的方法【l 明，并在多姿态人脸图像的重构实验中得到有效的验证，进一步完 善了非线性维数约简方法。s a u l 等人在u 正方法的基础上，结合流形的微分几何 特征，发展出基于半正定规划的流形方法例适用于不同类型的流形。b e l k m 等人 提出了u 步”，并成功地将其应用于半监督的r i e m a n n i a n 流形学习【2 1 】和流形规则 化【捌。意识到以i s o m a p ，l e e ，l e 为代表的维数约简方法只是对训练集中的样本 点给出嵌套空间中的位置嵌入，缺少从高维空间到低维空间的映射，并且依赖于 样本点集之间的关系，对噪声非常敏感，特征值分解又加剧了这种不稳定性， r o w e i s 等人提出，通过局部空间学习获得一个线性映射，并使用e m 算法解决优 化问题【8 。b r a n d 继续发展了这一思想，对流形上的邻域用g a u s s i a n 分布建模， 并给出了闭合解的形式。这一领域的巨大发展不仅引起了计算机科学研究人员的 注意，同时也引起了数学家和物理学家的兴趣。赵连伟等人】完善了i s o m a p 的理 论基础，给出了连续流形与其低维参数空间等距映射的存在性证明，并区分了嵌 入空间维数、高维数据的固有维数与流形维数这些容易混淆的概念，证明如果高 维数据空间存在环状流形，流形维数要小于嵌入空间维数，同时，还给出了一种 有效的环状流形发现方法，以得到正确的低维参数空间。何力等人瞄】提出了一种 从方法因子和延伸方向两方面显示观测空间的高维数据与维数约简后的低维数据 之间的联系的方法，并且比较了l s o m a p 和u 正方法的性能。z h a n g 等人提出了一 种局部切空间排列( l o c a lt a n g e n ts p a c ea l i g n m e n t ，简称l t s a ) 方法【1 4 】，通过逼 4 第一章绪论 近每一样本点的切空间来构建低维流形的局部几何，然后利用局部切空间排列求 出整体低维嵌入坐标。由于用于特征值分解的矩阵的阶数等于样本点数，因此， 当样本点集较大时将无法处理，此外，该方法不能有效处理新来的样本点。一种 基于划分的局部切空间排列方法田l 被提出以改善这些缺点，它建立在主成分分析 算法和l t s a 方法的基础上，解决了主成分分析算法不能求出整体低维坐标和 l t s a 中大规模矩阵的特征值分解问题，能够有效处理新来的样本点。 1 1 3 常见几种流形学习分析 关于流形学习方面最具影响力的文章是2 0 0 0 年t e n e n b a u m 和r o w e i s 等人在 s c i e n c e 同一期上发表的两篇文章，他们提出了各自的流形学习方法：i s o m a p ) 【1 1 】 和u 甘1 2 1 。 i s o m a p 建立在m d s 的基础上，力求保持数据点的内在几何性质，即保持两点 间的测地距离【1 1 1 。它用流形上点玉和x ；的测地距离取代经典的m d s 方法中的欧氏 距离d ( 玉，算，1 。测地距离的近似计算方法如下：样本点和它的邻域点之间的测地 距离用它们之间的欧氏距离来代替；样本点石和它的邻域外点之间的测地距离用 它们之间的最短路径来代替。i s o m a p 是一种全局优化算法，对于等距流形，它能 够给出低维投影。由于测地距离的整体性，i s o m a p 的维数约简效果在整体性上把 握得很好，即使流形不完全是等距的。但i s o m a p 有如下缺点： ( 1 ) i s o m a p 要求所对应的低维等距子集是一个凸集。当这个低维子集非凸时， 由于非凸性导致了无法得到测地距离的可接受的逼近，i s o m a p 无法得到理想的嵌 入结果。 ( 2 ) 当样本点的密度不稠密，或分布不均匀时，测地距离的计算可能有较大 的误差，这使得i s o m a p 的计算结果出现空洞现象。 ( 3 ) 计算流形距离的逼近的计算量较大，导致算法实现所需的时间较多，这 一点在样本点数目较多的时候特别明显。 u 正的基本思想是在样本点和它的邻域点之间构造一个重构权向量，并在低 维空间中保持每个邻域中的权值不变，即假设嵌入映射在局部线性的条件下，重 构误差最小【12 】。u 正认为所构造的重构权能掌握局部邻域本质上的几何性质，即 平移、旋转、缩放中保持不变。u 正首先在每个样本点寻找它的最近邻域，然后 通过求解一个有约束的最j 、- - 乘问题以获得重构权。在求解最小二乘问题时，u 正 将其转化成求解一个可能奇异的线性方程组，并通过引入一个小的正则因子来保 5 电子科技大学博士学位论文 证线性方程组系数矩阵的非奇异性。求出重构权后，利用这些重构权可以构造一 个稀疏矩阵，l l e 通过求解这个稀疏矩阵最小的几个特征向量来获得全局的低维 嵌入。同i s o m a p 相比，求解特征值所涉及到的只是一个稀疏矩阵，给计算带来了 很大的便利。此外，u 正并不需要计算样本点之间的测地距离，而只需要在每个 邻域求解一个小的线性方程组，所需要的计算时间和计算量小的多。但u 正也有 不足之处，由于u 正保持邻近点的几何性质，对于有噪声、样本点密度稀疏或者 相互关联较弱的数据集，相隔较远的点之间的关联会减弱，这样在从高维到低维 的映射过程中，很可能会将相隔较远的点映射到邻近点的位置。而i s o m a p 由于保 持样本点间的测地距离而不会出现这样的情况。另外，u 正通常不能恢复出与流 形等距的低维嵌入。 在l s o m a p 和u 正之后，发展出许多新的流形学习方法，如l e e l 3 】、i - i l l e 嘲、 l t s a t l4 l 等。l e 维数约简目标是在高维空间中离得很近的点投影到低维空间中的 像也应该离得很近。它通过样本点构建近邻图，图的顶点为样本点，每个样本点工 同它的邻域点工。之间有边连接。然后给每条边赋予权值，权值为1 或者p 十一州”。 最后通过计算拉普拉斯算子的广义特征向量来得到低维嵌入结果。l e 利用拉普拉 斯贝尔特拉米算子的性质来构造流形的嵌入映射，这个映射试图保持一些局部性 质，而这个性质通常不是局部的等距性。对于一个同低维空间等距的流形，l e 并 不一定能得到等距的嵌入结果。u 正所面临的将远距离点映射到近距离的问题在 l e 中也可能会出现。此外，l e 还涉及到参数盯的选取，不同的参数盯，其嵌入 结果可能不同。 l t s a 基本思想是利用样本点邻域的切空间来表示局部的几何结构，然后将这 些局部切空间排列起来构造流形的全局坐标1 1 4 】。首先，l t s a 寻找出样本点的局部 邻域，并在每个邻域作p c a ，以获得样本点的切空间及邻域在这个切空间上的投 影坐标。其次，l t s a 认为理想的低维嵌入同局部的投影坐标之间应该只相差一个 仿射变换，并由此构造一个最小重构误差。而求解这个最小重构误差问题也可以 转化成求解一个稀疏矩阵的特征值问题。同u 正和l e 相比，l t s a 能很好的恢复 出等距流形的低维嵌入。但它也有一些不足之处，跟i s o m a p 和u 正一样，l t s a 在每个局部邻域计算投影坐标时，会较大程度的受到流形的曲率和样本点密度的 影响，从而导致计算出的局部投影坐标出现偏差，从而影