（概率论与数理统计专业论文）基于流形学习的数据降维方法及其在人脸识别中的应用.pdf

独创性声明 本人郑重声明：所提交的学位论文是本人在导师指导下独立进行研究1 ：作所取 得的成果。据我所知，除了特别加以标注和致谢的地方外，论文中不包含其他人已 经发表或撰写过的研究成果。对本人的研究做出重要贡献的个人和集体，均已在文 中作了明确的说明。本声明的法律结果由本人承担。 学位论文作者签名：r 期：墨! 1 2 ：墨： 学位论文使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位论文的规 定，即：东北师范大学有权保留并向国家有关部门或机构送交学位论文的 复印件和电子版，允许论文被查阅和借阅。本人授权东北师范大学可以将 学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或其它复制手段保存、汇编本学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 学位论文作者毕业后去向： 工作单位： 通讯地址： 指导教师签名： 日期： 电话： 邮编： 鲞 摘要 近年来，随着科学技术的发展，人们对于各种数据的获取较之以往更为方便 和普遍。然而，在很多实际应用问题中，我们所采集到的数据往往具有高维数、 非线性等特征。这些特征一方面导致了“维数灾难”现象的出现，另一方面，不 利于人们直接理解及发现数据集所蕴含的内在规律。因此，利用降维技术对高维 数据进行处理就显得尤为重要。传统的降维方法( 例如主成分分析、独立成分分 析、线性判别分析等) 能够有效地处理具有线性结构和高斯分布的数据集。但当 数据集具有非线性结构时，这些方法却难以发现隐藏在高维数据中的内在低维信 息。基于流形学习的数据降维方法假设高维观测数据位于嵌入到高维欧式空间的 低维流形上，因此可以有效地发现和保持在高维空间中呈现高度扭曲数据集的内 在几何结构。目前，流形学习算法已经成为了数据挖掘、模式识别、统计机器学 习等相关领域研究的热点。 本文对基于流形学习的数据降维方法进行了深入地研究，提出了3 种基于流 形学习的数据降维和特征提取方法，并将其应用于具体的人脸识别问题中。通过 仿真实验和与其它算法的比较，验证了文中算法的有效性。主要工作和创新成果 集中在以下几个方面： 1 、对现有的线性及非线性降维算法进行总结，并对流形学习的定义、研究 现状、应用领域进行介绍。通过对人脸识别技术的分析，指出了将流形学习应用 于人脸识别问题的合理性和可行性。 2 、为了解决传统主成分分析( p c a ) 算法无法应用于非线性结构数据的缺 点，提出了一种基于局部p c a 和低维坐标排列的流形学习算法。在本方法中， 首先利用测地线距离的约束和最小集覆盖方法将数据所在的整体非线性流形划 分成若干个互相重叠的最大线性贴片( m a x i m u ml i n e a rp a t c h ，m l p ) 。由于得到 的每个最大线性贴片所包含的数据具有线性结构，因此，我们可以利用传统的主 成分分析( p c a ) 方法对每个最大线性贴片中的数据进行降维，得到其局部低维 坐标。最后，将坐标排列( a l i g n m e n t ) 技术和最大间隔准则( m a x i m u mm a r g i n c r i t e r i o n ) 结合，对所有最大线性贴片的局部低维坐标进行排列，得到整体数据 集的全局降维结果。由于本方法在降维的过程中同时考虑到了数据的流形结构和 类别信息，因此，在人脸识别的实验中取得了较好的结果。 3 、提出了一种自适应加权的子模式局部保持投影算法( a w s p l p p ) 。与传 统的局部保持投影( l p p ) 算法不同，a w s p l p p 首先将输入的高维原始数据划 分成若干个子模式，然后利用l p p 算法对得到的每个子模式集合分别进行降维， 得到可以保持各个子模式集合局部结构的低维特征。此外，为了增强算法的鲁棒 性，采用一种自适应的方法计算每个子模式对于识别的权重。通过将a w s p l p p 算法应用于人脸识别问题，可以看出该方法不仅能够提高传统l p p 的计算效率， 在识别的准确率方面也要优于其它的子模式算法。 4 、提出了一种结构保持的投影算法( s p p ) 。在本方法中，我们同样将原始 高维数据划分成若干个子模式。但与前面提到的a v e s p l p p 和其它基于子模式的 方法不同，s p p 在对每个子模式进行降维的过程中，不仅考虑到了它所在子模式 集合的流形结构，还考虑到了它与来自于同一样本的其它子模式之间的关系。通 过s p p 算法，我们可以在保持各个子模式集合的非线性流形结构的同时保持每 个输入样本内在结构。与前面提到的两种基于流形学习的降维算法相同，我们将 s p p 算法应用于人脸识别问题并在标准人脸数据库上验证了算法的有效性。从实 验结果可以看出，s p p 算法要优于其它全局和局部识别方法。 关键词：模式识别；数据降维；流形学习；人脸识别；监督流形学习 i j a b s t r a c t i nr e c e n ty e a r s ，w i t ht h ed e v e l o p m e n to fs c i e n c ea n dt e c h n o l o g y , i ti sm o r ee a s y a n dc o n v e n i e n tf o ru st oo b t a i nv a r i o u sd a t a h o w e v e r t h ed a t as e t sc o l l e c t e df r o mt h e r e a l a p p l i c a t i o np r o b l e m sa r ea l w a y sw i t ht h ec h a r a c t e r so fh i g h d i m e n s i o n a la n d n o n l i n e a r o nt h eo n eh a n d t h e s ec h a r a c t e r sc a u s et h e “c u r s eo fd i m e n s i o n a l i t y ” p h e n o m e n o n ；o nt h eo t h e rh a n d i ti s h a r df o ru st ou n d e r s t a n da n dd i s c o v e rt h e i n t r i n s i cs t r u c t u r eo ft h ed a t as e t a sar e s u l t ，u s i n gd i m e n s i o n a l i t yr e d u c t i o n t e c h n i q u e sf o rd a t ap r o c e s s i n gb e c o m e se x t r e m e l yi m p o r t a n t a l t h o u g ht h et r a d i t i o n a l d i m e n s i o n a l i t yr e d u c t i o nm e t h o d s ( s u c ha sp r i n c i p a lc o m p o n e n ta n a l y s i s ，i n d e p e n d e n t c o m p o n e n ta n a l y s i sa n dl i n e a rd i s c r i m i n a n ta n a l y s i s ) c a ne f f e c t i v e l yd e a lw i t ht h e d a t as e tw i t hl i n e a rs t r u c t u r ea n dg a u s s i a nd i s t r i b u t i o n t h e yc a n n o td i s c o v e rt h e i n t r i n s i cn o n l i n e a ri n f o r m a t i o nh i d d e ni nt h e h i g h - d i m e n s i o n a l d a t as e t t h e d i m e n s i o n a l i t yr e d u c t i o nm e t h o d sb a s e do nm a n i f o l dl e a r n i n ga s s u m et h a t t h e h i g h d i m e n s i o n a l o b s e r v a t i o n sc a nb em o d e l e da sd a t a p o i n t s r e s i d eo na l 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 ，w h i c hi se m b e d d e di n t oah i g h - d i m e n s i o n a l e u c l i d e a ns p a c e t h e r e f o r e ，t h em a n i f o l dl e a r n i n gm e t h o d sc a ne f f e c t i v e l yd i s c o v e r a n dp r e s e r v et h ec u r v es t r u c t u r eo ft h ei n p u td a t a a tp r e s e n t ，m a n i f o l dl e a r n i n gh a s b e c o m eah o tr e s e a r c ht o p i ci nt h ef i e l d so fd a t am i n i n g ，p a t t e r nr e c o g n i t i o n ，m a c h i n e l e a r n i n g ，e t c i nt h i st h e s i s ，w ea n a l y z et h em a n i f o l dl e a r n i n ga n dp r o p o s et h r e en o v e lm a n i f o l d l e a r n i n gm e t h o d sf o rd i m e n s i o n a l i t yr e d u c t i o na n df e a t u r ee x t r a c t i o n ，a n da p p l yt h e m t ot h ef a c er e c o g n i t i o np r o b l e m 办ee f f i c i e n c yo ft h ep r o p o s e da l g o r i t h m si s d e m o n s t r a t e db ye x t e n s i v ee x p e r i m e n t sa n dc o m p a r i s o nw i t ho t h e ra l g o r i t h m s t h e m a i nw o r ka n dc o n t r i b u t i o n so ft h i st h e s i sa r es u m m a r i z e da sf o l l o w s ： 1 as u r v e yo ft h ee x i s t i n gd i m e n s i o n a l i t yr e d u c t i o nm e t h o d si sg i v e n ，a n dab r i e f i n t r o d u c t i o no nt h e d e f i n i t i o na n da p p l i c a t i o n so fm a n i f o l dl e a r n i n gi sa l s om a d e t h r o u g ht h ea n a l y s i so f t h ef a c er e c o g n i t i o np r o b l e m ，t h er a t i o n a l i t ya n df e a s i b i l i t yo f u t i l i z i n gt h em a n i f o l dl e a r n i n gm e t h o d sf o rf a c er e c o g n i t i o na r ej u s t i f i e d 2 as u p e r v i s e dm a n i f o l dl e a r n i n ga l g o r i t h mb a s e do np a t c h e sa l i g n m e n ti s p r o p o s e d i nt h i sa l g o r i t h m ，w ef n s tc h o o s e sa s e to fo v e r l a p p i n gp a t c h e sw h i c hc o v e r a l ld a t ap o i n t su s i n gam i n i m u ms e tc o v e ra l g o r i t h mw i t hg e o d e s i cd i s t a n c ec o n s t r a i n t 1 l l t h e n ，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 ) i sa p p l i e do ne a c hp a t c ht oo b t a i nt h e d a t a sl o c a lr e p r e s e n t a t i o n s f i n a l l y , p a t c h e sa l i g n m e n tt e c h n i q u ec o m b i n e dw i t h m o d i f i e dm a x i m u mm a r g i nc r i t e r i o n ( m m c ) i su s e dt oy i e l dt h ed i s c r i m i n a n tg l o b a l e m b e d d i n g t h ep r o p o s e dm e t h o dt a k e sb o t hl a b e l i n f o r m a t i o na n ds t r u c t u r eo f m a n i f o l di n t oa c c o u n t ，t h u si tc a nm a x i m i z et h ed i s s i m i l a r i t i e sb e t w e e nd i f f e r e n t c l a s s e sa n dp r e s e r v ed a t a si n t r i n s i cs t r u c t u r e ss i m u l t a n e o u s l y e x p e r i m e n t a lr e s u l t s s h o wt h a tt h ep r o p o s e da l g o r i t h ma c h i e v e sb e t t e rr e c o g n i t i o nr a t e st h a ns o m ee x i s t i n g m e t h o d sf o rf a c er e c o g n i t i o n 3 a na d a p t i v e l yw e i g h t e ds u b - p a t t e r nl o c a l i t yp r e s e r v i n gp r o j e c t i o n ( a w s p l p p ) a l g o r i t h mi sp r o p o s e d u n l i k et h et r a d i t i o n a ll p pa l g o r i t h mw h i c ho p e r a t e sd i r e c t l y o nt h ew h o l ei n p u tp a t t e r n sa n do b t a i n sag l o b a lf e a t u r e st h a tb e s td e t e c t st h ee s s e n t i a l n o n l i n e a rm a n i f o l ds t r u c t u r e ，t h e p r o p o s e da w - s p l p pm e t h o do p e r a t e s o b s u b - p a t t e r n sp a r t i t i o n e df r o m a no r i g i n a lw h o l ep a t t e r n sa n ds e p a r a t e l ye x t r a c t s c o r r e s p o n d i n gl o c a ls u b - f e a t u r e sf r o mt h e m f u r t h e r m o r e ，t h ec o n t r i b u t i o no fe a c h s u b p a t t e r n c a nb ea d a p t i v e l yc o m p u t e d b ya w - s p l p pi no r d e rt oe n h a n c et h e r o b u s m e s so ft h ep r o p o s e dm e t h o d t h r o u g ha p p l y i n gt h ea w - s p l p pt of a c e r e c o g n i t i o n ，i tc a nb e s e e nt h a tt h ep r o p o s e dm e t h o dc a nn o to n l yr e d u c et h e c o m p u t a t i o nc o m p l e x i t yo ft h et r a d i t i o n a ll p p , b u ta l s oi m p r o v et h er e c o g n i t i o n p e r f o r m a n c e s 4 an o v e ll o c a lm a t c h i n gm e t h o dc a l l e ds t r u c t u r e - p r e s e r v e dp r o j e c t i o n s ( s p p ) i s p r o p o s e d u n l i k em o s te x i s t i n gl o c a lm a t c h i n gm e t h o d sw h i c hn e g l e c tt h ei n t e r a c t i o n s o fd i f f e r e n ts u b - p a t t e ms e t sd u r i n gf e a t u r ee x t r a c t i o n ，i e ，t h e ya s s u m ed i f f e r e n t s u b p a t t e ms e t sa r ei n d e p e n d e n t ；s p pt a k e st h eh o l i s t i cc o n t e x to ft h eo r i g i n a lw h o l e p a t t e r n si n t oa c c o u n ta n d c a n p r e s e r v et h ec o n f i g u r a ls t r u c t u r eo fe a c hi n p u tp a t t e r ni n s u b s p a c e m o r e o v e r , t h ei n t r i n s i cm a n i f o l ds t r u c t u r eo ft h es u b p a t t e r ns e t sc a na l s o b ep r e s e r v e di no u rm e t h o d l i k et h et w oa f o r e m e n t i o n e da l g o r i t h m s ，w ea l s oa p p l y t h es p pt of a c er e c o g n i t i o np r o b l e m t h ee f f i c i e n c yo ft h ep r o p o s e da l g o r i t h mi s d e m o n s t r a t e db ye x t e n s i v ee x p e r i m e n t so nt h r e es t a n d a r df a c ed a t a b a s e s ( y a l e ， e x t e n d e dy a l e ba n dp i e ) e x p e r i m e n t a lr e s u l t ss h o wt h a ts p po u t p e r f o r m so t h e r h o l i s t i ca n d1 0 c a lm a t c h i n gm e t h o d s k e yw o r d s ：p a t t e r nr e c o g n i t i o n ；d i m e n s i o n a l i t yr e d u c t i o n ；m a n i f o l dl e a r n i n g ； f a c er e c o g n i t i o n ；s u p e r v i s e dm a n i f o l dl e a m i n g w 目录 摘要i a b s t r a c t i i i 目录v 第一章绪论1 1 1 研究背景1 1 2 流形学习3 1 2 1 基本概念3 1 2 2 流形学习的定义4 1 2 3 流形学习的基本问题5 1 2 4 流形学习的研究进展。5 1 2 5 流形学习的应用8 1 3 本文主要工作和组织结构9 第二章降维算法简介1 1 2 1 线性方法1 】 2 1 1 主成分分析1 1 2 1 2 多维尺度变换13 2 1 3f i s h e r 线性判别分析1 4 2 1 4 非负矩阵分解1 5 2 2 流形学习方法17 2 2 1 等距映射1 7 2 2 2 局部线性嵌入19 2 2 3 拉普拉斯特征映射2 2 2 2 4 局部切空i 、b j 排列2 4 2 2 5 最大方差展开2 5 2 3 降维算法在人脸识别中的应用2 6 2 - 3 1 人脸识别简介2 6 2 3 2 基于子空间的人脸识别2 7 第三章基于低维坐标排列的流形学习3 0 3 1 流形分解3 1 3 1 1 构建最大线性贴片3 1 3 1 2 最小集覆盖：3 3 3 2 局部低维坐标排列3 4 3 2 1 局部主成分分析3 4 3 2 2 坐标排列3 5 3 - 3 实验结果3 7 3 4 有监督扩展4 0 v 3 4 1 最大间隔准则4 0 3 4 2 有监督坐标排列算法4 1 3 5 实验结果4 2 3 5 1o r l 数据库4 2 3 5 2y r a l e 数据库一4 6 3 5 3c m up i e 数据库4 7 3 5 4 结果分析4 9 3 6 小结5 0 第四章自适应加权的子模式局部保持投影51 4 1 基于子模式的人脸识别5 2 4 2 自适应加权子模式l p p 5 3 4 2 1 人脸图像划分5 3 4 2 2 子模式l p p 和权值计算5 4 4 2 3 分类。- 5 7 4 3 计算复杂度分析5 8 4 4 实验结果。j 5 8 4 4 1y a l e 数据库5 8 4 4 2e x t e n d e dy a l e b 数据库6 2 4 4 3c m up i e 数据库6 4 4 5 小结6 6 第五章结构保持投影算法6 7 5 1 结构保持投影6 8 5 1 1 入脸图像划分一6 8 5 1 2s p p 算法6 9 5 1 3 分类一7 3 5 2 实验结果7 4 5 2 1y a l e 数据库7 4 5 2 2e x t e n d e dy a l e b 数据库7 7 5 2 3c m up i e 数据库7 9 5 2 4 讨论81 5 3 小结8 1 第六章总结与展望8 2 6 1 全文工作总结8 2 6 2 未来展望8 3 参考文献8 5 致谢9 4 在学期间公开发表论文及著作情况9 5 v l 东北师范大学博士学位论文 1 1 研究背景 第一章绪论 随着科学的发展和技术的进步，人们可以越来越方便地获取大规模的数据。 特别是在科学研究领域，为了对客观现象或事物进行丰富、细致的描述，科学家 们往往需要大量的数据信息。这些海量数据在带给人们便利的同时，也产生了新 的问题：在很多实际应用中，如生物信息学、计算机图像处理、信息检索、文本 分析、生物信息认证等，人们所采集到的大量数据通常是繁杂的、高维的以及非 结构化的。这就导致了隐藏在数据背后的内在关系和规律难以被直观的发现，在 一些文献中，把这种无法有效地挖掘隐含在海量数据中的知识的现象称为“数据 爆炸但知识匮乏”现象。 如何从数据中发现有价值的信息和内在规律，并根据现有数据对事物未来 的发展趋势进行预测，是统计机器学习及其相关领域所关注的主要目标之一。但 当面对高维数据时，传统的数据分析方法往往遇到以下问题。首先，高维数据会 导致“维数灾难”( c u r s eo fd i m e n s i o n a l i t y ) 2 1 现象的出现。所谓“维数灾难”， 就是指在缺乏简化数据的前提下，要在给定的精度下准确地对某些变量的函数进 行估计，我们所需要的样本数量会随着样本维数的增加而呈指数形式增长。其次， 与“维数灾难 所对应的一个几何现象被称为“空空间现象”( e m p t ys p a c e p h e n o m e n o n ) 【3 】，“空空间现象”指出，因为我们获得的样本数量往往是有限的， 所以高维空间本质上是稀疏的。比如：随着数据维数的显著增加，高斯分布中的 3 仃法则将不再适用，即在高维空间中，大多数数据不再处于在高斯函数的中间， 而是集中在函数的边界。此外，有研究者已经证明，在高维空间中，数据更多的 分布在超球的表面而不是球的中心【4 j 。在这种现象下，相对低密度的区域包含了 大部分的数据，而高密度区域反而数据缺乏，这就造成了很难利用一般的多元数 据分析方法对高维空间的密度和几何性质进行直接地分析。最后，近期的研究又 发现了高维数据处理中的另一个问题，即高维空间中测度的“集中现象” ( c o n c e n t r a t i o np h e n o m e n o n ) 1 5 j 【6 j 。“集中现象表明，样本点之问距离测度的可 区分性会随着维数的增加而减弱。这导致一些基于距离测度的分析算法( 如最近 邻分类算法等) 难以在高维空间取得较好的效果。 由于存在以上的种种问题，对高维数据进行降维处理就成了数据分析中非常 重要的一个步骤和组成部分。降维主要指将样本从高维观测空间通过线性或非线 东北师范大学博士学位论文 性方法投影到一个低维特征空间，从而发现隐藏在高维数据中的有意义低维结 构。利用降维技术对高维数据进行处理，主要有以下好处【57 】：( 1 ) 可以对数据进 行有效压缩，以节省存储空间；( 2 ) 在一定程度上消除数据中存在的噪声：( 3 ) 便于从数据中提取特征，以完成后续的分类或识别任务；( 4 ) 通过将数据投影到 低维空间( 2 维或3 维) ，可以实现数据集的可视化。 对于数据降维( 或称维数约简) 技术的研究是一个既古老又年轻的课题。说 其古老，是因为早在2 0 世纪初，h o t e l l i n g 就提出了主成分分析方法( p r i n c i p a l c o m p o n e n t a n a l y s i s ，p c a ) 【7 j ，并将其应用于心理学数据的统计分析。随后，一 些基于不同优化准则的数据降维方法被相继提出，比如：多维尺度变换 ( 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 ) 【8 1 、独立成分分析( i n d e p e n d e n tc o m p o n e n t a n a l y s i s ，i c a ) 【9 1 、f i s h e r 线性判别分析( l i n e a rd i s c r i m i n a t a n a l y s i s ，l d a ) 1 1 0 等。这些算法具有实现简单、容易计算、解释性强等特点，并且已经在很多领域 得到了成功的应用。然而，随着信息时代的到来，人们逐渐发现，在很多实际应 用问题中，我们所采集到的样本在高维空间中往往呈现高度的非线性结构。因此， 传统的基于线性模型的降维方法将不再适用。为了有效地处理这一问题，非线性 降维方法应运而生。 在非线性降维方法中，比较具有代表性的是基于核的方法和基于流形学习的 方法。其中，基于核的降维方法利用核方法( k e r n e lt r i c k ) 将原始数据隐式地映 射到更高维的特征空间，并期望在原始空间中呈非线性结构的数据集可以在核空 间利用线性方法进行处理。由于这类方法不用创建复杂的假设空间( h y p o t h e s i s s p a c e ) ，所以很多已有的线性降维算法都可以被扩展为对应的基于核的非线性方 法，如：核主成分分析( k p c a ) 1 5 】、核线性判别分析( k d a ) 【l6 】、核独立成分 分析( k i c a ) 1 1 7 】等。虽然基于核的方法在处理非线性数据时较之线性方法具有 一定的优势，但也存在一定的局限性。首先，由于在算法中引入了核方法，如何 选择合适的核函数并对函数中的参数进行适当的设置，就成为了一个难点。恰当 的核函数会给数据分析带来便利，但并不是对所有数据集均适用。因此，在实际 应用中，人们经常需要根据某些经验和先验知识对核函数的类型进行选择。其次， 由于在算法中采用的映射是隐式的，人们并不知道数据集在核特征空间中的具体 表达。因此，基于核的降维算法往往解释性不强。 基于流形学习的降维方法是最近几年发展起来的一项技术，这类方法的主要 特点是假设分布在高维空间中的样本点处于或者近似地处于非线性流形上，而流 形学习的目标就是发现数据集中的非线性流形结构并在降维的同时尽可能地保 持这些结构信息。目前，比较有代表性的流形学习算法主要包括：等距映射 ( i s o m e t r i cm a p p i n g ，i s o m a p ) 1 1 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 】、拉普拉斯特征映射( l a p l a c i a ne i g e n m a p ，l e ) 1 3 】、局部切空间排列 2 东北师范大学博士学位论文 ( 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 】等。 1 2 流形学习 1 2 1 基本概念 首先，我们对流形学习中所涉及到的几个基本数学概念和定义进行介绍。流 形是现代数学中的一个概念，它将拓扑、几何、代数等相关领域结合起来，已经 成为现代科学技术中对许多自然现象进行描述的重要工具。其具体定义如下： 定义1 1 ：设m 为一个h a u s d o r f f 空i 司，若对于m 中的每一个点p em ，都 有p 的一个邻域u 和d 维欧式空间中的一个开集同胚，则称肘为d 维拓扑流 形，简称d 维流形。 从定义1 1 可以看出，d 维欧式空间本身就是一个平凡的d 维拓扑流形。此 外，d 维拓扑流形的任意非空开子集也是一个d 维拓扑流形。定义1 1 中涉及到 的一些其它概念定义如下： 定义1 2 ：一个拓扑空间可以定义为一个集对( x ，彳) ，其中，x 为一非空集 合，f 是x 的满足以下条件的子集族：( 1 ) f 关于属于它的任意多元素的并是封闭 的；( 2 ) f 关于属于它的有限元素的交是封闭的；( 3 ) f 中的元素包含空集和x 。 定义1 3 ：如果对集合x 中的任何两个不同点五y ，都存着x 的邻域u 和y 的邻域y ，使得ur 、v = 彩。则称( x ，f ) 为h a u s d o r f f 空间。 定义1 4 ：对于两个拓扑空间x 和y ，如果存在映射 卜y 是一一映射， 并且厂及其逆映射f 一都是连续映射，则称x 和】，同胚。 除了拓扑流形，人们还进一步定义了微分流形和黎曼流形的概念。 定义1 5 ：设m 是d 维拓扑流形，u 是肘的非空开子集，y 是的开子集， 矿：u v 是同胚映射，则将有序数对妙，认u ) ) 称为m 上的一个局部坐标系，也可 以称为m 上的坐标卡或图片( c h a r t ) ，其中，u 称为局部坐标邻域，9 称为局部坐 标映射。 定义1 6 ：设妙口，) 和移卢，即j 是拓扑流形m 上的两个局部坐标系，如果 nu p = o 或当u 口r 、u 声a 时，坐标变换o 啄1 和即。1 都是c 类的( 即 映射的k 阶导数存在且连续) ，则称缈口，) 和( v b ，珊) 是c 相容的。 定义1 7 ：设m 是d 维拓扑流形，假定a = ( u 口，) ) 舵彳是m 上坐标卡的集 合且满足以下条件： ( 1 ) 覆盖性：m = u u 口； 口 ( 2 ) 相容性：属于彳的任意两个坐标卡都是c 相容的； 东北9 币范大学博士学位论文 ( 3 ) 最大性：若存在( u ，缈) 与彳中的每个坐标卡都是c t 相容的，则 ( u ，矽) a 。 则称a 是流形m 上的一个c 微分结构。 定义1 8 ：设m 是d 维拓扑流形，彳是流形m 上的一个c 微分结构，则称( m ，a ) 为一个d 维c 微分流形。当露= 时，c 微分流形称为光滑流形。 定义1 9 ：设肘是d 维c ”微分流形，则对m 上的点p 处的切向量可以定义 为映射x 口：c ”- r ，且对于任意厂，g c ”( p ) ，比r 具有如下性质： ( 1 ) x p ( 矽+ 詹) = t x 】t p ( 厂) + 屈v ，( g ) ； ( 2 ) x p ( 厂g ) = f ( p ) x p 【g ) + g 【p ) x p ( f ) ； ( 3 ) 若在包含p 的开邻域u 上有厂= g ，则x p ( ) = x p ( g ) 。 m 上的点p 所有切向量的集合记为t p ( m ) ，称为m 在p 点的切空间。， 定义1 1 0 ：如果在光滑流形m 的每个切空间中都给定了内积，则称m 为黎 曼流形( r i e m a nm a n i f o l d ) 。 定义1 1 l ：设p ，q 为黎曼流形m 上的任意两点，则m 中连接p ，q 的所有 分段光滑曲线的弧长的下界被称为测地距离，记为如仞，g ) 。 1 2 2 流形学习的定义 “流形学习 ( m a n i f o l dl e a r n i n g ) 一词，最早出现在b r e g l e r 和o m o h u n d r o 于1 9 9 5 年发表的关于可视化语音识别和数字图像处理的两篇论文中【1 9 】【2 0 1 。简单 的说，流形学习就是通过获取数据集内所蕴含的几何信息来进行数据分析的技 术，因此，可以定义为：由有限样本点集合来计算嵌入在高维欧式空间中的低维 流形的问题【18 1 。换句话说，从数据集的内蕴几何出发，获取与其内蕴几何相一致 的低维表示的过程即为流形学习。2 0 0 2 年，s i l v a 和t e n e n b a u m 在他们发表的 “g l o b a lv e r s u sl o c a lm e t h o d si nn o n l i n e a rd i m e n s i o n a l i t yr e d u c t i o n ”一文中1 2 ，给 出了流形学习的具体数学描述如下 定义1 1 2 ：给定数据集x = 扛，f = 1 9 49 j r u ，并假设x 中的样本是由低 维空间中的数据集y = 抄，f = 1 ，j r 口通过某个非线性变换厂所生成，即： x f = f l y f ) + 岛，其中，冰 d ，f ：尺d r d 是c ”嵌入映射。那么流形学习的 目的就是通过给定的观测数据集尼( 1 ) 获取低维表示y = 抄f ，江1 ， r 口； ( 2 ) 构造高维到低维的非线性映射叫：尺u 一只口。 4 东北师范大学博士学位论文 1 2 3 流形学习的基本问题 根据流形学习的定义，在流形学习中所要研究的基本问题可以概括为以下几 个方面： ( 1 ) 内在维数估计：所谓内在维数( i n t r i n s i cd i m e n