（交通信息工程及控制专业论文）基于流形学习的数据降维技术研究.pdf

删 y 1 8 8 4 嘈。y j c j i i s t u d y o fd a t ar e d u c t i o nt e c h n i q u eb a s e do nm a n i f o l dl e a r n i n g b y h u p e n g b e ( h u n a nu n i v e r s i t yo fa r t sa n ds c i e n c e ) 2 0 0 7 at h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e r e q u i r e m e n t sf o rt h ed e g r e eo f m a s t e ro fe n g i n e e r i n g t r a f f i ci n f o r m a t i o ne n g i n e e r i n g & c o n t r o l c h a n g s h au n i v e r s i t yo fs c i e n c e & t e c h n o l o g y 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 ry a n ga np i n g a p r i l ，2 0 1 1 取 何 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名：胡 q 日期：加j ，年厂月之re l 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。同时授权中国科学技术信息研究所将本论文收录到 中国学位论文全文数据库，并通过网络向社会公众提供信息服务。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密d 。 ( 请在以上相应方框内打“”) 作者签名：觏 够日期：，年j 。月加日 新签名：渤旰 吼剐年5 月加日 t ! 卜。i 摘要 自然界中的数据大都以高维非结构化的形式存在，信息化技术的高速发展使 得获取这些数据成为了可能。高维数据不仅难以被人们直观理解，也难以被现有 机器学习和数据挖掘算法有效处理。降维操作已经成为处理这些数据的一个重要 手段，经过几十年的发展，降维技术已经取得了长足的进步，出现了如p c a 、l d a 等一系列经典方法，但在当下的线性与非线性降维领域仍然存在许多具有挑战性 的问题。2 1 世纪的头十年里，以i s o m a p 、l l e 为代表的流形降维方法突发猛进， 成为了当下最为热门方向之一 论文从广义流形学习定义出发，围绕线性流形与非线性流形降维算法展开， 从全局线性流形降维、全局非线性流形降维、局部非线性流形降维对流形学习算 法进行了一些研究，主要工作有： 针对线性判别分析在实际识别任务中计算消耗大、内存需求多，易出现“小 样本问题”的缺点，将传统线性判别分析的方法放到图嵌入的框架下进行分析， 结合正则化技术，设计了一种图嵌入正则化的线性判别分析方法。首先构造了非 监督最优类可分准则，通过图嵌入理论得出一种求解该判别准则下最优投影向量 的方法，最后将求解传统l d a 中投影向量的复杂特征值分解过程转化成为一个简 单的特征值分解和一个正则化拟合问题。 针对局部线性嵌入算法对近邻点个数的选择依赖性较强，不适应处理稀疏数 据源的缺点，提出了一种基于几何距离摄动的局部线性嵌入算法。从几何直观的 角度，提出了一种根据几何摄动值来判定流形结构上的两个点是否处于同一线性 平面的方法，根据这一方法，提出了一种基于几何摄动的分块算法，将原始流形 数据划分为一组最大线性分块的组合；在进行局部嵌入的过程中通过线性块内的 点来确定局部线性嵌入算法中近邻点的选择范围，从而保证局部线性嵌入算法局 部线性特性这一假设条件得到满足。 关键词：流形学习；线性降维；非线性降维；图嵌入；局部线性嵌入；几何摄动； 最大线性块 a b s t r a c t t h ed a t ai nn a t u r em o s t l yi nt h ef o r mo fh i g h - d i m e n s i o n a la n du n s t r u c t u r e d f o r me x i s t i n g w i t ht h er a p i dd e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g y ，i ti sp o s s i b l e t oo b t a i nt h e s ed a t a h i g hd i m e n s i o n a ld a t ai sn o to n l yd i f f i c u l tt op e o p l ei n t u i t i v e l y u n d e r s t a n d ，b u ta l s ot om a c h i n el e a r n i n ga n dd a t am i n i n ga l g o r i t h m st od e a lw i t h e f f e c t i v e l y d i m e n s i o n a l r e d u c t i o nh a sb e c o m ea ni m p o r t a n tm e a n so fd e a l i n gw i t h t h e s ed a t a a f t e rs e v e r a ly e a r so fd e v e l o p m e n t ，d i m e n s i o n a l i t yr e d u c t i o nt e c h n o l o g y h a sm a d eg r e a tp r o g r e s s ，t h e r eh a sb e e ns u c ha sp c a ，l d aa n das e r i e so fc l a s s i c a l m e t h o d s b u ti nt h ep r e s e n tf i e l do fl i n e a ra n dn 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 f i e l d ，t h e r ea r es t i l lm a n yc h a l l e n g i n gi s s u e s i nt h ef i r s td e c a d eo ft h e21 s tc e n t u r y , t a k ei s o m a p 、l l ea s r e p r e s e n t a t i o n ，m a n i f o l d m e t h o d sd e v e l o p m e n ta d v a n c e r a p i d l y b e c o m eo n eo ft h em o s tp o p u l a rc o n t e m p o r a r y d i m e n s i o nr e d u c t i o n m e t h o d s p a p e r sf r o mt h eg e n e r a l i z e dd e f i n i t i o no f m a n i f o l dl e a r n i n gs t a r t i n g ，a r o u n dt h e l i n e a rm a n i f o l da n dn 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 na l g o r i t h me x p a n d e d f r o m t h eg l o b a ll i n e a rm a n i f o l dr e d u c t i o n ，n o n l i n e a rm a n i f o l dg l o b a ld i m e n s i o nr e d u c t i o n ， l o c a ln o n l i n e a rm a n i f o l dd i m e n s i o n a l i t yr e d u c t i o n ，c a r r i e do u ts o m er e s e a r c ho nt h e m a n i f o l dl e a r n i n ga l g o r i t h m t h em a i nw o r ko ft h i sd i s s e r t a t i o nc a nb es u m m a r i z e d a sf o l l o w s ： i no r d e rt os o l v et h el d a s m a l ls a m p l e l a r g ec o n s u m p t i o nc a l c u l a t i o na n d m e m o r yr e q u i r e m e n t sd i s a d v a n t a g e s t a k e t h et r a d i t i o n a ll i n e a rd i s c r i m i n a n t a n a l y s i s m e t h o di n t ot h ef r a m e w o r ko f g r a p h e m b e d d e d c o m b i n e dw i t h r e g u l a r i z a t i o n ，an e wl d aa l g o r i t h mb a s e do ng r a p he m b e d d i n ga n dr e g u l a r i z a t i o n t h eu n s u p e r v i s e do p t i m a lc l a s ss e p a r a t ec r i t e r i o nh a v eb e e nb u i l t ，t h e np r o p o s e da m e t h o dt og e tt h i sd i s c r i m i n a n tv e c t o rb yg r a p he m b e d d i n gt h e o r y a tl a s t ，t h e c o m p l e xe i g e n v a l u ed e c o m p o s i t i o ni nt h eo r i g i n a ll d ab ec o n v e r tt oas i m p l e e i g e n v a l u e sd e c o m p o s i t i o na n dr e g u l a r i z a t i o nf i t t i n gp r o c e s s l l ea l g o r i t h mi ss e n s i t i v ef o rt h en u m b e ro fn e a r e s tn e i g h b o r s ，a n df a i l so n s p a r s es o u r c ed a t a i no r d e rs o l v et h ep r o b l e m ，al l ea l g o r i t h mb a s e do ng e o m e t r i c p e r t u r b a t i o nh a v eb e e np r o p o s e d a tf i r s t ，t h eo r i g i n a ld a t a s e th a v eb e e ns e ti n t o s o m em a x i m a ll i n e a rp a t c ha c c o r d i n gt ot h eg e o m e t r i cd i s t a n c ep e r t u r b a t i o n t h e l l ew i l lb e a p p l yt o t h i sm a x i m a ll i n e a rp a t c ht oc o m p l e t et h ee m b e d d i n g i i d i m e n s i o n a l r e d u c t i o n k e y w 。r d s ：m a n i f o l dl e a r n i n g ；l i n e a r 9 m e n s i o n i n r g e d ；u e t o l 。n c ；a l l n y o n l l i i n n e e a 叠r d i m e n s i o n a l i t y r e d u c t i o n ；g r a p h e m d e a a r l g ； 1 u 4 1 1 了 “。 e m b e d d i n g ；g e o m e t r i cp e r t u r b a t i o n ；m a x i m a ll i n e a rp a t c h i i i 目录 摘j i i 兽i a b s t r a c t ：【i 第一章绪论 1 1 研究背景1 1 2 研究意义和应用情况3 1 3 本文的实验平台及实验用数据简介4 1 4 论文的组织架构5 第二章流形学习降维算法介绍 2 1 流形学习的数学含义。7 2 2 流形学习方法的分类7 2 3 线性流形降维典型方法8 2 ：i 1p c a 8 2 3 2 经典多维尺度分析9 2 3 3f i s h e r 线性判别分析9 2 4 非线性流形降维方法l o 2 4 1 核主成分分析l l 2 4 2 等距映射算法。1 2 2 4 3 局部线性嵌入算法1 3 2 4 4l a p l a c i a n 特征映射算法1 4 2 4 5h e s s i a n 特征映射1 5 2 5 局部切空间排列1 7 2 6 流形学习算法小结18 第三章一种图嵌入正则化的线性判别分析方法 3 1 引言2 l 3 2 正则化线性判别分析r l d a 2 2 3 3 图嵌入正则化判别分析2 3 3 3 1 谱图理论- 2 3 3 3 2 图嵌入线性判别分析一2 4 3 3 3 正则化最小二乘拟合2 5 3 3 4 图嵌入正则化人脸判别分析2 6 3 3 5 算法计算复杂度分析2 7 3 4 实验2 8 3 5 本章小结3 0 第四章基于几何距离摄动的局部线性嵌入算法 4 1 局部线性嵌入l l e 3 1 4 2 基于几何摄动的l l e 算法3 3 4 2 1 非线性度与几何距离摄动3 4 4 2 2 基于几何摄动的最大线性块3 5 4 2 3 最大线性分块算法。3 6 4 2 4 最大线性分块下的局部嵌入算法3 6 4 3 实验3 7 4 3 1 人造数据集上降维实验3 7 4 3 2u c i 数据上分类实验3 8 4 4 本章小结3 9 总结与展望 参考文献4 2 致谢4 7 附录( 攻读硕士学位期间发表录用论文) 4 8 1 1 研究背景 第一章绪论 作为模式识别的关键技术之一，降维是该领域中亘古不变的研究主题。伴随 着现代信息技术的高速发展，海量高维数据的有效获取已经成为当下模式识别领 域的一个突出特点。一方面，我们能够获取的信息量越来越大，信息种类也越来 越多；另一方面，信息数据的维数越来越高，数据结构也越来越复杂。如何对这 些高维数据进行切实有效的降维处理，尽可能多的提取出有价值的信息，显得尤 为重要【l 2 l 。 数据降维的目的是在保持数据信息足够完整的前提下尽可能合理地约简数 据集，以满足实际设备的存储要求和人的感知需求。原本呈现高维结构的原始数 据集经过有效降维操作后，在数据维度大大降低的同时使原始数据集的内在结构 及规律性能得到更佳的描述。 正是由于降维技术在各种数据应用场合的重要性，降维技术在过去的几十年 里得到了长足的发展，相关算法也层出不穷【，l 。作为最先出现的一类降维方法， 线性降维技术在该领域一直扮演着十分重要的角色。线性降维方法基于样本数据 全局线性的假设，以欧氏距离作为相似性刻度，并假设各样本数据点间相互独立， 这样通过降维所得到的低维数据能与原始高维数据之间保持线性的变换关系。对 于全局线性数据来说，这种线性的降维方法被证明是有效的，其中具有代表性的 方法，如主成分分析( 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 ) 、线性判别分析( l i n e a r d i s c r i m i n a n ta n a l y s i s ，l d a ) 等都在许多领域得到了广泛应用 4 1 。但是，这种传统 的线性降维方法大都要求假设数据集存在于全局的线性结构中，即要求构成数据 集的各个变量之间是相互独立的。只有当数据确实符合这类方法要求的全局线性 的假设条件时，才能够有效地学习出线性结构，当数据呈现非线性结构时也能在 一定程度上用全局的线性结构去近似非线性结构，得到比较理想的结果。但当数 据呈现出高度非线性结构或者强属性相关时，全局线性的近似效果就很不理想， 难以表达数据集的真实结构，降维效果很难满足实际需要。遗憾的是，现实世界 中的大多数数据恰恰都是这种高度非线性结构或者是强属性相关的，而且这些数 据都具有尚不为人知的复杂结构。所以，传统的线性降维方法因其线性假设的特 性不再适应更深层次的数据处理的需要，降维效果需要进一步提高。于是研究者 们开始转向能对在原始空间中呈现非线性结构的数据进行有效降维处理技术一 非线性降维技术的研究了。 为了能对非线性数据进行有效的降维处理，研究者们进行了大量的工作，经 过多年的发展，相关方法也不断涌现。这其中，产生于上世纪4 0 年代，到8 0 年 代基本成熟的人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k s ，a n n ) 是就是一种用于非 线性降维的典型方法，自组织特征映射算法( s e l f - o r g o n i z i n gf e a t u r em a p ) ，或称 拓扑有序映射( t o p o l o g i c a l l yo r d e r e dm a p ) 、k o h o e n 自组织映射就是在a n n 上产 生的典型算法，它的核心思想是假定输入信号能够由神经网络映射至低维空间， 并使得在输入空间中结构相近的数据点在低维中依然具有相近的邻近关系【s 1 而 h a s t i e 等人也在研究直线加速器时提出了主曲线( p r i n c i p a lc u r v e s ) 的概念，作为 线性主成分的非线性推广，取得了一定的成果，但上述两种方法都未能在非线性 降维领域中产生十分巨大的影响，研究者们不得不继续寻找新的处理方法【t l 。9 0 年代，基于统计学习理论中核方法( k e r n e lm e t h o d ) 在支持向量机中的成功应用， 为基于核的非线性降维提出了另外一种有效的途径，在此基础上出现了核主成分 分析( k e r n e lp r i n c i p a lc o m p o n e n ta n a l y s i s ，k p c a ) 和核判别分析( k e r n e ll i n e & d i s c r i m i n a n t a n a l y s i s ，k l d a ) 等，通过核函数的引入将原本适用于线性数据的降 维方法通过核映射至核特征空间进行非线性降维成为了9 0 年代风靡一时的方 法，在一定程度上取得了成功【7 】。然而上述三类方法都因其各自的缺点未能完全 有效地解决非线性数据的降维处理问题：a n n 本质上是一种黑箱方法，而主曲 线在从几何角度去估计内在结构时，不可避免的要采用迭代思想，从而使得设计 的算法极易产生局部极小状况；核方法的非线性是通过选择的核函数来实现的， 如何选择适当的核函数问题还有待进一步研究，而且核选择问题通常不能直接体 现数据的内在结构，并不利于人的感知和直接理解。所以，上述种种劣势促使人 们寻求新的降维方法。 进入2 l 世纪后，神经学科的研究发展有力推动了非线性降维技术的发展。 s e u n g 等神经学家的研究成果指出，非线性流形是人类感知的基础，经过自然界 长期进化的人脑能够以非线性流形的方式表达出对外界对象的感知【。】。这样就说 明自然界中的高维信息形式存在的外界对象实际上很可能存在于一个非线性低 维流形上，对该对象进行认知的过程在很大程度上就是通过这种非线性低维流形 表示来识别事物。比如，同一个人在不同环境、条件下的人脸图像集合就可以看 作是以年龄、光照、姿态等为参数的嵌入在高维空间的低维流形，而现实中人们 能够快速识别这些人脸图像正是取决于这些少数的参数。这样的事实说明非线性 低维流形表示在人的认知过程中具有重要的意义，基于非线性流形表示的降维和 识别是合理的，所以，通过有效的算法来对这些呈现非线性流形结构数据进行有 效降维的思路叩开了非线性流形学习的大门f 9 】。 作为非线性流形降维方法的开山算法，等距映射( i s o m e t r i cm a p p i n g ， i s o m a p ) 和局部线性嵌入( l o c a ll i n e a re m b e d d i n g ，l l e ) 一经出现就引起了研究 2 者们的广泛关注【- o 1 l 】。i s o m a p 在手写数字与手势上的降维实验表明i s o m a p 算 法能够学习出蕴含在高维数据中的非线性低维嵌入坐标，从而对非线性流形数据 进行有效的降维；而l l e 在人脸图像数据集上的降维实验同样表明l l e 能够学 习出蕴含在图像空间中的人脸内在参数一姿态和表情。自此之后，非线性流形降 维的方法就如雨后春笋般大量出现，局部切空间排列算法( l o c a lt a n g e n ts p a c e a l i g n m e n t ，l t s a ) 、拉普拉斯特征映射( l a p l a c i a ne i g e n m a p s ，l e ) 、海塞特征映 射( h e s s i a ne i g e n m a p s ，h e ) 是这里面的典型算法d 2 t 4 1 。随着研究的不断深入及相 关的应用推广，非线性流形学习也从最初的非监督学习扩展到了监督学习和半监 督学习，并在不少领域得到了应用，为降维领域开创了一个新的学派。与此同时， 随着研究的不断深入和推广，越来越多亟待解决的问题也纷纷出现：比如现有流 形学习算法对噪声敏感、要求原始数据稠密取样、泛化能力差等，虽然当下已经 有不少新的算法能在一定程度上解决上述问题，但是还需要进一步充实和完善， 距离该类算法在实际中的应用还有一段比较长的路要走。 1 2 研究意义和应用情况 数据降维一直是模式识别、数据挖掘等领域的关键问题，进入2 1 世纪之后， 不断有其他学科的研究工作表明了流形结构存在的必然性，作为线性降维方法的 非线性推广，以发掘数据中内在几何结构为目标的流形降维技术可能可以更加有 效地处理实际问题。与此同时，流形结构理论的深入开展有力的推动着流形降维 技术的发展：人类感知与非线性流形可能一致性；微分几何学的快速发展等都为 基于流形学习的降维技术研究提供了强有力的理论支撑。而且，流形降维算法已 经在许多模式识别的任务中取得了多方面的成功。这里简单介绍部分应用情况： ( 1 ) 交通信息：随着电子技术的不断成熟，图像及视频数据大量涌现，基于 车辆信息采集的智能交通系统对于诸如车型信息采集、各种条件下车牌的识别、 驾驶员疲劳状态的检测、根据道路交通流各项参数预测道路交通状况等方面的需 求越来越多，目前流形降维的方法已经开始应用用上述任务中，并取得了一定的 进展。 ( 2 ) 机器视觉：信息技术的不断发展同样使得流形降维的技术在计算机视觉 方面具有广阔前景。目前基于流形的降维技术已经在医学信息处理、生产控制、 视频监控、基于生物特征的身份识别等方面得到了广泛应用，流形学习算法的各 种思想也为对图像和视频数据的处理提供了新的思路，并已被成功用于其中。例 如图像超分辨、人脸识别、步态分析、视频分析、医学图像分割等。 ( 3 ) 数据可视化：对于人类来说，当面对现实世界中的各种数据时，方面 人不能直接感知高于三维的数据，从这方面讲，这类数据对人来说是“不可视 的，因此对数据进行降维处理以使得其对人“可见 十分必要；另一方面，在数 据低维条件下，人的智能分析处理能力要强于计算机。所以，将高维数据投影至 二、三维空间，能结合人与计算机在处理数据中各自的优势，也便于人对数据作 进一步的分析。流形学习方法以发现数据中的内在几何为目标，为数据可视化提 供了新的思路。 ( 4 ) 数据建模：对数据进行建模表示一直是数据处理中的核心问题之一。常 见的如基因序列的建模蛋白质是由氨基酸为基本单位组成的序列，而组成蛋白 质的氨基酸分子的个数从几十个到成千上万不等。具有相同空间结构但氨基酸捧 列不同的蛋白质，被分为同一组中，这就是所谓的蛋白质组( 类似于基因组) 通 过蛋白质组模型可以了解不同蛋白质组的特殊性质，能够有助于辨别和发现新 组。但由于蛋白质组特征的维数很高，这给辨别和分析带来了很大的困难。通过 有效的数据降维，就可以用很好的简单变量来反映蛋白质组的性质，来帮助判别 和分析 如上所述，正是流形降维技术的重要性、有效性、前瞻性、可扩展性等一系 列特点及在应用方面的最大潜力，本研究从广义流形学习的角度对降维技术进行 了一些研究，期冀能对该领域的技术发展进行一些有意义的工作。 1 3 本文的实验平台及实验用数据简介 论文中所有实验都是在一个采用m a t l a b 语言完成的实验平台上进行的。 m a t l a b 是矩阵实验室( m a t r i xl a b o r a t o r y ) 之意，它除了具备卓越的数值计算能 力之外，还提供了专业水平的符号计算，文字处理，可视化建模仿真和实时控制 等功能。矩阵是m a t l a b 的基本数据单位，它的指令表达式与数学工程中常用 的形式十分相似，故用m a t l a b 来解算问题要比用c ，f o r t r a n 等语言进行相同 的任务要简捷得多。在新的版本中还加入了对c ，f o r t r a n ，c + + ，j a v a 的支持， 这样的开放性使得m a t l a b 广受用户欢迎。除内部函数外，所有m a t l a b 主包 文件和各种工具包都是可读可修改的文件，用户可以对源程序进行修改或加入自 己编写的程序构造新的专用工具包。由于m a t l a b 软件的强大计算能力尤其是 矩阵处理能力，以及其简单易用的程序语言，出色的图形处理能力等原因， m a t l a b 在计算机视觉、图形处理等领域中都取得了广泛的应用。本文中的使 用的是m a t l a b 7 1 版本。 论文的实验所采用的数据集主要有人工“s 流形数据集、u c i 数据集和常 用的人脸数据库o r l 、y a l e 、f e r e t 等【1 。人工“s ”流形数据集如图1 1 所示： 4 图1 1 “s 流形人造数据集 u c i 数据集是目前模式识别、机器领域应用得最为著名的数据集之一共有 1 9 9 个子集，包含了医学疾病诊断、文字识别、天气预测等多种数据。本研究中 人脸数据库选择目前应用最多的y a l e 、o r l 、p i e 人脸库。y a l e 人脸库是由耶 鲁大学计算机视觉与控制中心创建，包含1 5 个人1 6 5 张多姿态、多光照图像； o r l 人脸库由英国剑桥大学创建，包含4 0 个人4 0 0 张灰度图像，单类图像间包 括时间、光照、姿态、表情、人脸细节的变化；f i e 人脸库是美国卡耐基梅隆大 学创建，包括6 8 个人4 1 3 6 8 张多姿态、光照、表情的灰度人脸图像，图1 2 是 从上述3 个库中摘选出来的例子。 一一冒囝 1 4 论文的组织架构 图1 2 常见人脸库图例 第一章为引言，主要介绍了降维技术的研究背景与现状，流形降维技术的发 展与应用情况，从而指出本论文的研究意义；并对本论文中所用实验工具及所采 用的数据集进行了一些简单的介绍； 第二章，按照广义的流形学习的概念将流形降维技术划分成线性流形与非线 性流形降维算法，并对一些经典的线性、非线性流形算法进行了全面、简单的介 绍，而且简要阐述了现有算法中的主要问题，并探讨了一些可能的研究方向； 第三章，在线性流形降维中引入图论的思想，设计了一种图嵌入正则化的人 5 脸线性判别方法。首先构造了非监督的最优类可分准则，并在图嵌入框架下提出 了一种求解该判别准则下最优投影向量的方法。该方法在非监督的图嵌入框架下 充分利用样本局部类别信息提高识别率的同时克服了矩阵计算复杂度，降维了计 算消耗。通过典型人脸数据库上的实验，证明了该方法的有效性。 第四章，针对非线性流形降维中的l l e 算法进行了较为详细的分析，针对 传统l l e 方法对近邻点个数依赖性较强，不适应处理稀疏数据源的缺点，结合 最大线性块的划分，提出了一种基于几何距离摄动的局部线性嵌入算法。首先将 原始流形数据根据构造的几何摄动条件划分为一组最大线性分块的组合，然后在 每一个局部线性块上应用l l e 算法完成嵌入降维，既从理论上又从实践上证明 了该处理方法的有效性。 第五章，。总结与展望。对本研究的工作进行了详细的总结，并对未来可能进 行的工作进行了探讨和展望。 6 第二章流形学习降维算法介绍 本章将对现存主要流形降维算法进行简单的介绍，首先介绍了流形学习的普 遍性数学定义，接着按照一定的规则对这些方法进行一个分类，然后重点介绍了 获得广泛应用的几种流形方法，并对现有算法中的优缺点进行了一些简明的阐 述，最后给出了简单的总结及指出了一些可能的研究方向。 2 1 流形学习的数学含义 流形是微分几何中的一个基本概念【舯l ，2 0 世纪，微分几何学和拓扑几何的 迅猛发展使其在其他学科中得到了广泛的应用。流形学习就是建立在微分几何和 拓扑几何的数学方法上来研究感知模型的新思路。流形学习的目标在于有效挖掘 高维数据分布的内在规律，其核心思想是：高维观测空间中的点是由少数独立变 量的共同作用在观测空间张成的一个流形，如果能有效地展开观测空间卷曲的流 形或发现内在的主要变量，就能够对该数据集进行降维。作为三维空间中曲线和 曲面的抽象和推广，流形的概念同时也是欧氏空间的推广。从微观上来看，流形 结构可看成是欧氏空问的组合，即流形数据集在原始空间中每一点的邻域，都与 欧氏空间的一个区域同胚。 对流形的数学定义如下：设m 是具有可数基的h a u s d o r f f 空间。如果v p 膨， 有p 的邻域“，使“与r - ( 刀维欧氏空间) 或日。( 半个欧氏空间) 的某个开域同胚，则 称膨是万维拓扑流形，简称刀维流形。有了对流形的定义，形式化地概括流形学 习这一降维( 维数约简) 的过程如下：假设数据是均匀采样于一个高维欧氏空间中 的低维流形，流形学习的目标就是从高维采样数据中恢复低维流形结构，并求出 相应的嵌入映射来实现数据降维，用数学语言描述如下：令y ，且厂：y 寸掣是 一个光滑的嵌套( 其中d 是高维观测数据的维数，d 是流形的本征维数) ，流形学 习的目标就是基于r 。上的一个给定被观测数据集合 五l ：去恢复y 与，。 2 2 流形学习方法的分类 流形学习的主要目标是发现嵌入在高维数据空间中观测数据的低维光滑流 形。它是一个具有基础性和前瞻性的研究方向，由于有着广阔的应用前景，近年 来已经成为机器学习、模式识别、数据挖掘等领域的研究热点之一，形成了大量 的研究方法。广义流形学习方法包括线性方法和非线性方法，其线性方法主要是 线性降维技术，如p c a 、多维尺度分析( m u l t i p l yd i m e n s i o n a ls c a l i n g ，m d s ) 、线 7 值分 成。 数据 性方法则 形与非线 空间的低 原始p c a 数据最大 的保持原 2 3 2 经典多维尺度分析 经典多维尺度分析( c l a s s i c a lm u l t i d i m e n s i o n a ls c a l i n g ，c m d s ) 是线性流形降 维中另一经典方法【i ，l 。与其他多维尺度技术一样，该方法所处理的也是原始空间 中两点之间欧氏距离所构成的矩阵d ，d 中的元素屯表示原始高维空间中的数据 点毛和i ，之间的欧氏距离。而c m d s 算法寻求线性映射m 使得下面的损失函数最 小： ( y ) ；等( 露一y ，一y ，i ) ( 2 3 ) l y ，- y ，1 1 2 是降维投影后的点y ，和y ，欧氏距离之差的平方限制条件对于任意的 _ ，需满足i i m 斤= l 。很明显，最小化上述损失函数的值可以通过对原始空间中样 本数据的g r a m 矩阵k ：x x r 进行特征值分解来求得。g r a m 矩阵的元素可以通过 下式求得： b z 一三( 一丢刃一i 万z d + 吉若) ( 2 4 ) 于是，最小化式( 2 3 ) 所表示的损失函数就能通过g r a m 矩阵的特征值分解来 实现。c m d s 与p c a 的相似之处在于一个是利用样本协方差矩阵的特征向量， 一个是利用g r a m 矩阵的特征向量，而协方差矩阵x r x 和g r a m 矩阵x x 7 的特征值 v 和特征向量u ，能够通过等式瓜= x u ，联系起来。 p c a 和c m d s 算法已经成功应用于多个识别任务，如人脸识别、硬币分类、 s e i s m i cs e r i e sa n a l y s i s 等，但这两种方法仍具有下面两个主要的缺点： 在p c a 中，协方差矩阵的大小与样本数据的维度密切相关，这样，当面临 样本数据是极高维度的时候，对协方差矩阵进行特征值分解计算将变得不可行。 等式( 2 3 ) 所描述的损失函数表示p c a 和c m d s 算法注重的对较大的点点距 离斫的保持，而实际上较小的彰往往会扮演着更为重要的角色。 2 3 3f i s h e r 线性判别分析 p c a 是一种无监督的降维方法，寻求的是在线性重构误差最小意义下的最优 子空间。而l d a 则是从首次从分类的角度提出的线性降维方法，f i s h e r 在1 9 3 6 年提出著名的f i s h e r 准则【2 0 】。对于二分类( 分别称为正类与负类) 问题，希望投影 后得到的y = w t z 能够使得如下j ( w ) 最大： 2 _ ，( w ) ：堪( 2 5 ) 。 o ；+ d i 其中码，m ：分别是正、负样本在投影方向上的均值，q 和吼是正、负类样本 在投影方向上的方差。将其推广到多类问题，此时希望找到的优化投影方向是使 9 尽量分离，从而保留丰富的 w d ( 2 6 ) ( 2 7 ) 这里h ，w 2 ，1 是对应于矩阵蹄品的前d 个最大特征值的特征向量，即通过求解 下面的特征值伺题就可以求出最优投影方向h ，w 2 ，】： 品= 昂m ，i = l ，d ( 2 8 ) 注意这里d c 一1 求出特征向量【w l ，w 2 ，1 后，测试样本在这里特征向量上的投影系数就是对 测试样本所提取出的特征向量，即低维嵌入坐标。l d a 算法就是求出一个线性 子空间，使得所有样本在这个子空间中，类内样本散度最小，类间样本散度最大， 从而使得经过l d a 降维后得到的嵌入坐标非常有利于进行样本的分类。 作为最早出现的有监督的线性降维方法，l d a 在简单的识别任务中取得了 令人耳目一新的效果，其影响力直至今日依然巨大。当l d a 用于诸如人脸识别 这类较为复杂的识别任务中时，极易出现“小样本 问题而导致算法失效，于是 研究者们对该算法进行了大量的改进，也形成了一批有影响力的方法 2 4 , 2 5 l 。 2 4 非线性流形降维方法 针对线性流形算法对复杂空间中问题处理的不足，研究人员提出来了多种非 线性流形学习。自从r o w e i s 和t e n e n b a u m 在s c i e n c e 上发表了关于非线性流形 学习的初步研究成果后 i o 川，利用非线性流形特性来降维的研究就成为一个热门 的研究话题。 谱方法是数学领域的一种经典分析和代数方法，在高维数据的低维表示和聚 类问题 2 6 2 7 1 中有着广泛的应用。算法首先根据给定的样本数据集定义个描述成对 数据点间相似度的关系矩阵，并计算此矩阵的特征值和特征向量；然后选择合适 的特征向量，投影到数据的低维嵌入坐标。如果相似度矩阵定义在一个给定的图 上，比如为图上的邻接矩阵、l a p l a c i a n 矩阵等，则称为谱图方法。谱理论通过 研究依据图定义的矩阵的谱，进一步研究图中包含的信息，并通过几何、分析和 1 0 代数的技术在离散空间和连续空间之间建立联系【2 l 】 一个图g = ( v ，e ) 包含两个集合：y 为顶点集，为边的集合。对于取样自d 维 流形上的样本数据集x 。首先在数据点和图g 的顶点之间建立一一对应，并定义 成对数据点的相似度为图上的边，这样就根据数据点建立了一个与之对应的图。 图与流形有许多相似的性质，最重要的一点是两者都可以嵌入到欧氏空间。所以 许多研究人员都使用图的方法逼近流形，并利用图的理论来求解低维嵌入，对于 流形来说，一个与之对应的图就是一个拓扑对象，其拓扑性质通过变的权值来体 现，如果数据集足够大且噪音较小，合理定义图上边的权重可以充分逼近嵌入流 形。 谱图理论在流形学习中有着广泛的应用，前面介绍的经典全局线性降维方法 p c a 可以看成是谱分析的应用。其通过求取数据协方差的谱，利用谱的特征值的 序关系来描述数据集的整体结构，并基于谱半径的序结构来描述数据集的主要结 构和实现降维。谱图理论除了在全局流形降维方法中得到应用外，不少非线性流 形学习算法也是基于谱方法来完成降维的，包括核主成分分析k p c a ，等距映射 方法i s o m a p ，局部线性嵌入l l e ，l a p l a c i a n 特征映射及h e s s i a n 特征映射等。 2 4 1 核主成分分析 k p c a 算法是将原始的p c a 算法通过核函数的一种最为直接的拓展。近些 年，这种采用“核技巧 来拓展线性技术的方式产生了许多成功的非线性降维技 术，如核岭回归和支持向量机等。k p c a 算法摈弃了