（计算机软件与理论专业论文）数据降维中若干问题的研究及应用.pdf

数据降维中若干问题的研究及应用 专业：计算机软件与理论 姓名：陈国明 导师：印鉴教授 摘要 如何降低数据的维数而不损失原有数据的内在信息是数据挖掘和机器学习 领域中的经典问题，降维是指样本从高维输入空间通过线性或非线性映射投影到 一个低维空间，从而找出隐藏在高维观测数据中有意义的低维结构，解决高维数 据的维数“灾害问题 。基于子空间的学习和流形学习算法吸引了大量研究者， 成为本领域的热点问题。 本文主要讨论了数据降维过程中的三个方面的问题： 1 在图嵌入框架的基础上提出一种新的降维分析算法i k l d a ( i m p r o v e dk e r n e l l i n e a rd i s c r i m i n a n ta n a l y s i s ) ，不仅使得隐藏在图像的信息能被区分出来， 而且大大降低了数据的维数，理论分析及实验结果表明i k l d a 的降维隐写分 析是有效的，比其它传统降维方法效果要好，并且进一步推进了数据挖掘可 视化方法在隐写分析的应用。 2 在数据集的内在维数的确定方面提出一种以反向k 近邻为基础的最大似然维 数估计算法，弥补了低维流形在七近邻中形成短路问题的不足之处以及数据 密度不均匀给维数估计带来偏差问题，在人造数据集和真实数据集的维数估 计中，取得了较好的效果。与此同时，提出了一种基于粒子群优化算法的维 数及近邻大小的参数优化策略p s o l l e ，通过智能计算来估计数据的内在维 数和近邻的大小。 3 提出一种基于纹理特征的非线性降维算法g a b o r l l e ，对中文手写笔迹进行 分析处理。首先对手写笔迹图像进行预处理，然后用g a b o r 滤波器提取出特 征，最后用流形学习算法l l e 进行降维分类，取得了较好的效果。 关键词：降维，维数估计，流形学习，可视化 r e s e a r c ha n da p p l i c a t i o no fs e v e r a l p r o b l e m si nd a t ad i m e n s i o n a l i t yr e d u c t i o n m a j o r ：c o m p u t e rs o f t w a r et h e o r y n a m e ：c h e ng u o m i n g s u p e r i s o r ：p r o f y i n j i a n a b s t r a c t r e d u c i n gt h ed i m e n s i o n a l i t yo fd a t aw i t h o u tl o s i n gi n t r i n s i ci n f o r m a t i o ni sa h o t s p o ti nm a c h i n el e a r n i n ga n dd a t am i n i n g d i m e n s i o n a l i t yr e d u c t i o ni s a n a p p r o a c h t on o n - l i n e a ra n dl i n e a r m a p p i n gh i g h d i m e n s i o n a l d a t ai n t oa l o w d i m e n s i o n a l s p a c e i t c a nd i s c o v e ri n t r i n s i c m e a n i n g f u l l o w d i m e n s i o n a l m a n i f o l de m b e d d e di nt h eh i g h d i m e n s i o n a ld a t as e ta n ds o l v et h ec u r s e so f d i m e n s i o n a l i t yp r o b l e m i n h i g h d i m e n s i o n a ld a t a d i m e n s i o n a l i t yr e d u c t i o nv i a s u b s p a c ea n dm a n i f o l dl e a r n i n gh a sa t t r a c t e dm u c ha t t e n t i o nf r o mt h er e s e a r c h e r s a n dh a sb e e nah o tr e s e a r c ht o p i c i nt h i sp a p e rw ep r o p o s ean e wd 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 m sc a l l i k l d a ( i m p r o v e dk e r n e ll i n e a rd i s c r i m i n a n ta n a l y s i s ) o nt h eg r o u n d o fg r a p h e m b e d d i n gf r a m e w o r k o u rm e t h o dn o to n l yc a nd e t e c tt h ei n f o r m a t i o nh i d d e ni n d 酒t a li m a g e s b u ta l s or e d u c et h ed i m e n s i o n a l i t y t h e o r e t i c a l a n a l y s i s a n d e x p e r i m e n t ss h o wt h a to u rn e wi k l d aa l g o r i t h mi se f f e c t i v ei ns t e g a n a l y s i sa n di s m o r ep r e c i s et h a nt h eo t h e rt r a d i t i o n a ld i m e n s i o n a lr e d u c t i o nm e t h o d s f u r t h e r m o r e ， o u rm e t h o dp r o m o t e sd e v e l o p m e n to fv i s u a l i z a t i o ni nt h ea p p l i c a t i o ni ns t e g a n a l y s i s w ep r o p o s ea na l g o r i t h mf o re s t i m a t i n gt h ei n t r i n s i cd i m e n s i o no fad a t as e t d e r i v e db y a p p l y i n gt h em a x i m u ml i k e l i h o o de s t i m a t o ra n da n a l y z i n gb o t hkn e a r e s t n e i g h b o ra n dr e v e r s ekn e a r e s tn e i g h b o r s w h i c hc a no v e r c o m et h el i m i t a t i o n so f s h o r t c u tp r o b l e ma n db i a sc a u s e db ya b n o r m a ls a m p l i n gd e n s i t yd i s t r i b u t i o nw h e n u s i n go n l ykn e a r e s tn e i g h b o r i tp r o d u c e sg o o dr e s u l t so ns o m es i m u l a t e da n dr e a l d a t a s e t s a tt h es a m et i m e , am e t h o do fe s t i m a t i n gt w oi n p u tp a r a m e t e r so f d 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 m sb a s e do np a r t i c l es w a r mo p t i m i z a t i o ni s p r o p o s e d b yt h i sw a y , t h ei n t r i n s i cd i m e n s i o no fad a t as e ta n dt h en e i g h b o r h o o ds i z e c a nb ee s t i m a t e da n dt h es i m u l a t i o nr e s u l t ss h o wt h em e t h o dh a sg o o dp e r f o r m a n c e w ep r o p o s ean 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 nm e t h o db a s e do nt e x t u r a l f e a t u r et oi d e n t i f yd i f f e r e n tw r i t e r sb yt h e i rh a n d w i t i n g w h i c hi n c l u d ed i g i t a li m a g e p r e p o c e s s i n g ，f e a t r u ee x t r a c t i o nb yg a b o rf i l t e r i n g , d i m e n s i o n a l i t yr e d u c t i o na n d c l a s s i f i c a t i o n a n dt h i sm e t h o dh a sag o o dv i s u a l i z a t i o nr e s u l t k e yw o r d s ：d i m e n s i o n a l i t yr e d u c t i o n , d i m e n s i o ne s t i m a t i o n ，m a n i f o l d l e a r n i n g ，v i s u a l i z a t i o n v 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体己经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：陈l 蛩桶 只期：2 0 0 9 年月日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学 位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查 阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、速印或其 它方法保存学位论文。 学位论文作者签名：脒l 虱哕寻 日期：2 0 0 9 年 月 日 i i 导师签名： 日期：2 0 0 9 年月日 1 1 问题概述 第一章绪论 可视化数据挖掘通常指用数据或知识可视化技术从大的数据集中发现隐含 的和有用的知识，可以用来对数据的属性、模式、孤立点等进行综合分析。与此 同时，数据挖掘后得到的知识和结果也可用可视化的形式表示出来。自从基于子 空间学习方法和流形学习算法提出来以后，由于其能在某种意义上保持原有数据 的属性信息的基础上把高维空间的数据集降到一个低维的空间。如果此时维数不 高于三维，高维数据的内在关系就可在不高于三维的空间中展示出来，使得人们 能够直观地认识高维数据的内在规律，并了解影响数据集内在结构的主要因素的 变化规律，大大推动了数据挖掘可视化研究体系的发展。对于维数大于三维的数 据集，则可以借助辅助的工具分析降维的j 下确性。 数据降维是指样本从高维输入空间通过线性或非线性映射投影到个低维 空l 、h j ，从而找出隐藏在高维观测数据中有意义的低维结构。在减少数据维数的同 时，尽量减少或去除次要的冗余信息，并且保留或增强有意义的信息，使得降维 之后的信息损失最小。大多数高维数据集在观测空间中呈现非线性，从扭曲的欧 氏空间中获得数据集中的隐含信息，一个合理的思路就是将数据集视为嵌入在欧 氏空间中的低维流形，从而将降维问题转化为流形学习问题。子空间分析方法是 将数据投影到指定的特征空间以最大化某些指标如类间距离与类内距离比等。现 有的流形学习降维算法多数是无监督的算法，如何将其推广到半监督以及有监督 的情形下，提高算法的泛化性能，利用类别信息进行分类也是流形学习重要研究 方向。流形学习在半监督学习方面的应用有估计手腕旋杯的旋转度数，判断视频 序列图像中人的手腕与肘部的位置，而半监督学习本身的优越性就体现在其能够 同时利用大量的无标签样本和少量的有标签样本帮助学习。在无监督学习的应用 中文献【1 l 通过计算每个单词与每篇论文的互信息，用流形学习降维算法d i f f u s i o n m a p 结合k 均值聚类对8 类1 1 6 1 篇科技新闻文章中的关键词做聚类，取得了与 单词语意高度相关的聚类结果。在有监督的学习应用中，在人脸识别模式分类问 题中，每类样本均能够用一个流形很好地描述。对每类样本学习一个流形，在分 1 类时，计算样本到每个流形的距离，将其分类到与其最近的流形所在的类别。“重 构误差最小化”、“保持相似度”和“保持近邻图或远离图的邻域关系 是常用的 流形学习降维的度量准则。现有算法大多基于小的邻域，而小的邻域往往较难获 取全局的性质，将全局与局部的学习方法结合起来，是一个非常有意义的课题。 以流形学习为基础的降维研究领域中还有待研究的问题，例如对于一个数据 集，到底降至什么维数才是合适的。很多流形学习降维算法中有两个参数需要预 先设定，一个是邻域参数，另一个参数是数据集的内在维数。高维空间中的数据 具有相似性和冗余性，有可能依赖于或近似依赖于低维的流形，在进行各种降维 算法之前，必须寻找高维空间数据内在的维数。由于这些参数值只是预估值，在 未知数据集内部特性的情况下并没有一个科学的方法去判断，只知道它们与数据 集本身性质有很大关系。最初提出内在维数估计方法的是b e n n e t 【2 】，他利用全局 或局部p c a 计算出的协方差矩阵的特征值估计具有一定线性结构数据的内在维 数。t 饥饥b a1 3 1 等提出i s o m a p 的残差内在维数估计法，通过寻找使得维数增 加而变化明显的残差曲线肘部拐点来估计数据集的内在维数。随着流形降维技术 的不断发展，对内在维数也有了更深刻的认识，陆续出现了极大似然估计方法【4 l ， 包数方法( p a c k i n gn u m b e r ) i s ，几何熵图估计方法 6 1 ，t e n s o rv o t i n g 方法f 7 1 ，分 形方法i s l ，k - 近邻图方法 9 1 ，以及针对于专门环状数据流形的内在维数估计法。 此外还有基于高阶统计量的嵌入维数估计方法、拓扑学中单纯复形的内在维数估 计方法和拓扑等距离映射法等。 1 2 研究的目的与意义 流形学习降维算法研究范畴涉及机器学习、数据挖掘、模式识别、拓扑学 和图论等交叉学科。发掘出高维数据内在几何结构以及隐藏在内部的起决定因素 的隐含变量是流形学习降维的基本目标。流形学习降维开始主要应用于以人脸识 别为主的生物特征识别，一幅图像要求很大的存储空间和计算时间，人脸的分类 识别存在困难，但人脑能在瞬间识别人脸在不同光照条件、姿态发生变化后情形， 原因在于大脑感知了以像素为单位高维人脸图像的内在低维结构，并以流形方式 存在，将人脸图像按照从左到右姿态、从上到下姿态，以及光照强度及方向分为 若t 模式进行存储。这种把高维数据映射成为低维嵌入空间的流形学习算法随后 2 在手写的数字字符的识别中也取得较好的效果。今后，流形学习有望在多媒体数 据挖掘、多媒体信息安全、机器视觉、医学图像处理、生物学基因工程、遥感数 据、金融数据分析等应用领域中不断涌现出新的学习方法，针对这些不同的高维 数据集，不同的流形学习降维算法将被利用来感知数据集的内在规律。在图像检 索领域的发展过程中，如何发现隐藏于图像空问的子流形成为近年来的研究热点 问题。在传统的基于内容的图像检索( c o n t e n t b a s e di m a g er e t r i e v a l ，简称c b i r ) 中，低层视觉特征由于其存在没有语义特征的缺点，以往常常引入相关反馈来克 服低层特征与高层语义特征之间的“语义鸿沟 。但上述方法假定图像位于欧氏 空间中，在实际应用中，高维空间的图像数据呈现复杂的非线性流形分布，因而 流形学习降维方法更易于揭示这种变化的影响。基于流形学习的图像检索主要任 务是学习嵌入于高维图像的低维子流形，然后对低维子流形进行相似性度量。 n e t 旧l 使用l a p l a c i a ne i g e n m a p s 通过保持图像之问的距离得到图像的低维子流 形来进行检索。与此同时，他还把基于相关反馈的保局投影( f e e d b a c k - b a s e d l o c a l i t yp r e s e r v i n gp r o j e c t s ) 的增量流形学习方法【1 1 】应用到图像检索领域中去。 在图像内容的认证方面及数字水印的研究领域，流形学习方法也有望在低维空间 中获取有意义的特征。可以预见不久将来，发现隐藏在图像、声音、视频等高维 空间的子流形将会成为重要的研究方向，微分几何、拓扑学和图论等基础理论的 发展在流形学习的框架中将转化为生产力，进一步推动各种应用领域的发展。 2 0 0 0 年最著名的综合类科技期刊( ( s c i e n c e ) ) 上发表了两篇关于非线性降维 算法研究成果的文章：一篇是s r o w e i 与l s a u l 的( ( n 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 nb yl o c a l l yl i n e a re m b e d d i n g ) ) 【1 2 l ，另一篇是j t e n e n b a u m ，v d es i l v a 与j l a n g f o r d 的ag l o b a lg e o m e t r i cf r a m e w o r kf o rn 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 f i o n 【3 】，自从这两篇文章推出对非线性降维算法研究的成果以来，利用流 形学习来进行数据降维就迅速发展起来。这两篇文章中提出的基于矩阵的特征分 解的方法，具有计算简易，不容易陷入局部极小点，只需计算矩阵的特征值等优 点，克服了传统非线性降维算法的缺点。实验结果表明这一类算法的潜在威力和 广泛应用前景，因而这一领域的研究受到了越来越多的研究人员的青睐。近年来， 机器学习的顶尖会议，如i c m l ( i n t e r n a t i o n a lc o n f e r e n c eo nm a c h i n el e a r n i n g ) ， n i p s ( n e u r a li n f o r m a t i o np r o c e s s i n gs y s t e m ) 等，数据挖掘的顶级会议k d d 3 ( k n o w l e d g ed i s c o v e r ya n dd a t am i n i n gc o n f e r e n c e ) ，i e e et r a n s a c t i o n o ni m a g e p r o e e s s i n g ，i e e et r a n s a c t i o no ns y s t e m s ，m a na n dc y b e r n e t i e s ，i e e et r a n s a c t i o n s o np a t t e r na n a l y s i sa n dm a c h i n ei n t e l l i g e n c e ，j o u m a lo fm a c h i n el e a r n i n gr e s e a r c h 等等，每年都有很多关于流形学习的学术文章发表。 1 3 本文的工作 一、提出一种新的隐写分析方法：i k l d a 1 在图嵌入框架的基础上提出了 一种新的基于核技术的有监督学习算法i k l d a 来解决隐写分析这个分类问题，成 功的把原始图像和隐密图像区分开来，理论分析和实验结果表明，新方法比传统 的降维算法有更高的分类准确度；2 提出一种可行有效的先融合特征后再降维的 隐写分析方法；3 估算数据集特征空间的内在维数，推动数据挖掘可视化技术在 隐写分析中的应用。 二、提出一种以反向k 近邻为理论基础的基于流形相似因子与流形相异因子 的最大似然维数估计算法，弥补了低维流形在k 近邻中形成短路问题的不足之处， 在人造数据集和真实数据集的维数估计中，取得了较好的效果。与此同时，提出 了一种基于粒子群优化算法的维数及近邻大小的参数优化策略lo s 一儿e ，模仿 生物学习过程，利用人们决策过程中使用的两类重要信息：自身的经验和他人的 经验来进行智能计算从而估计数据的内在维数和近邻的大小。 三、提出一种基于纹理特征的流形学习算法g a b o r 一剧z ，对基于小样本的 中文手写笔迹进行分析处理。先对手写笔迹进行预处理，然后用g a b o r 滤波器提 取出特征，最后用子空间流形学习算法l l e 进行降维分类，取得了较好的效果。 1 4 本文的组织 第1 章为绪论，介绍了降维的目的和研究意义，分析线性降维和非线性降维 的区别。然后介绍了流形学习的理论基础、研究现状和尚存在的问题。 第2 章为流形的概述。介绍流形学习的数学基础以及分类的方式。并进一步 介绍了几种具有代表性的流形学习算法，分析了各种算法优缺点及计算复杂度。 第3 章在图嵌入的基础上提出了一种基于i k l d a 的隐写分析算法。首先介 绍了隐写分析的研究现状，然后阐述了图嵌入的研究框架，最后系统地介绍了该 4 算法以及通过实验比较分析得出算法的有效性。 第4 章首先介绍了了几种具有代表性的维数估计算法，然后在基于反向k 近 邻的理论基础上提出了流形相似因子与流形相异因子的最大似然维数估计算法， 充分考虑数据的空间分布特征。与此同时，还提出一种基于粒子群算法的维数确 定算法及邻域估计算法，为流形学习中内在维数及邻域参数的选取提供了参考。 第5 章介绍了基于汉字手写体笔迹的降维分析。提出了以纹理特征为基础的 流形学习算法g a b o r - l l e ，构建了笔迹分析的预处理以及g a b o r 滤波器为核心的特 征提取方案，最后通过流形学习算法进行降维，进行笔迹分析。 第6 章对论文主要工作做了总结，并对将来的工作目标和需要完善之处做了 展望。 5 2 1 引言 第二章流形学习降维方法的概述 数据降维是数据挖掘和机器学习领域中的经典问题，通常用来把数据从高维 数据空间映射到低维的数据空间。基于子空间的流形学习算法在多媒体数据挖掘 中具有重要前景。高的维数也意味着高的计算复杂性及存储的复杂性。这些算法 分析如何用尽可能的保持原有数据特性的基础上用低维的特征空间去描述维数 巨大的多媒体信息。并且在图像和声音的信号处理中成功用于聚类和分类。在低 维空间中进行分析避免了维数灾害的问题。降维广泛也用于揭示潜在的语义变量 来解释观察的现象。一个潜在的假设是高维空间的样本在低维空间张成一张流 形。数据降维的目的是把高维的数据投影到一个更加紧至的表示但仍然能够保持 原有空间的数据属性。例如高维空间中的数据集合，图2 1 中每幅1 2 8 1 2 8 像素 的人脸图像的维数是1 6 3 8 4 ，产生严重的维数灾害，在高维空间中处理数据非常 困难，但高维数据的采样往往受到一些关键的隐含因素的影响，如图2 1 人脸的 图像由光照的强度及人脸的姿态朝向等因素决定。经典的流形降维算法多数在寻 找某个满足某种准则的最优线性子空间，通过将高维数据投影到这个子空间中， 从而达到数据降维的目的。然而研究表明，这些关键因素共同变化时观测变量的 变化并非各关键因素各自变化后的线性叠加，即很多数据之间的关系很难用线性 的方法表示，传统的线性降维算法p c a 与l d a 等存在很大的局限性。非线性维 数约简( n 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 ，简称n l d r ) 被提出专门用来处理 非线性和弯曲形变的数据。 二十世纪微分几何得到高速发展，对高维空间和对曲线、曲面整体性质的研 究，使微分几何学同黎曼几何，拓扑学等有了密切的关系。微分几何发展的意义 不仅在于本身，更重要是它为研究新的机器学习算法提供了坚实的理论基础。流 形学习理论就是在这样的背景下产生的，它以微分几何学作为理论基础，结合神 经科学提供的生物学依据，研究机器学习所面临的新问题。 6 图2 1 人脸数据集 2 2 流形学习降维的数学基础 流形是现代数学中的概念，这旱先给出与流形学习( m a n i f o l dj e a m i n g ) 相关的 一些数学定义。流形是微分几何学的概念，而微分几何学与拓扑学又有密切的关 系。在介绍流形学习之前有必要先介绍与流形相关的数学理论，下面是一些与流 形相关的拓扑学和微分几何学的概念。 拓扑学是研究拓扑空间在拓扑变换下的不变性质和不变量的学科。拓扑空 问，是欧式空制的一种推广。给定任意一个集合，为它的每一个元素赋予一种确 定的近邻结构便构成了一个拓扑空问m l 。下面足拓扑空间的数学定义： 给定集合f ，它的一个子集族r 构成x 上的一个拓扑结构，简称拓扑，是 指，满足下述三个条件： 1 空集d 和x 都属于， 2 t 中任意多个元素的井集仍属于r 3t 中任意有限个元素的交集仍属于r 集合x 连同它上面的一个拓扑丁构成一个拓扑空间，记为( x ，丁) 连续映射和同胚： 设f ：xj 】，是拓扑空间【x ，瓦) 到拓扑空间( 】，弓) 的映射，称厂是连续映射 是指对空间( y ，墨) 的每个开集g ，其原像仍然是( x ，瓦) 的一个开集。如果厂满 足下述三个条件： 1 厂既是单射又是满射 2 厂是连续映射 3 厂的逆映射g = f 。1 也是连续映射 这时就称厂是同胚映射，两个拓扑空间( x ，巧) 和( y ，互) 同胚。同胚性是拓 扑空间的同构，两个同胚的拓扑空间具有相同的拓扑性质。 h a u s d o r f f 空间： ( x ，r ) 是拓扑空间，设x , y 是( x ，r ) 中的点，如果存在x 的邻域【，和y 的邻 域v 使得u 和y 是不相交的，即unv = 矽，则称x 和y 可以由邻域分离，如果x 的任意两个点工，y ( x y ) 可以由邻域分离，则称x 是h a u s d o r f f 空间 流形的概念是欧式空间的推广，是局部具有欧式空间性质的空间。欧式空间 就是最简单的流形实例。粗略的说，流形在每一点的近傍和欧式空间的一个开集 是同胚的，因此在每一点的近傍可以引进局部坐标系，流形正是一块块的“欧式 空间”粘起来的结果1 4 1 。下面是流形的数学定义： 设m 是h a u s d o r f f 空间，若对任意一点工m ，都有工在m 中的一个邻域u 同胚于m 维欧式空间尺”的一个开集，则称m 是一个m 维流形。设定义中的同胚 映射是：u 一纯( u ) ，这里弛( u ) 是尺脚中的开集，则称( u ，仇) 是m 的一个 坐标卡。 因此，流形是一个局部可坐标化的拓扑空间。 8 2 3 流形学习降维的目标 假设m 是嵌入在高维空问中的一个低维流形，粗略的说，流形学习的目标 是发现m 并在保持流形拓扑或连接特性的前提下把m 表示在某个较低维的空 间中，这种表示也称为嵌入映射。下面是流形学习的数学定义。 高维观测数据集x = “，x 2 ，h ) ，其中r d ，假设数据集x 的点位于或 近似位于尺d 空间的流形m 上，定义嵌入映射f ：mcr d r d 。流形学习是根 据有限的离散的观测数据集x 发现嵌入映射厂，并找到与高维观测数据一一对 应的数据集y = y l ，y 2 ，y | ) 1 5 i 。 通常，嵌入在高维空间中的流形的几何结构跟内在维数都是未知的，因此， 要利用流形学习进行维数约简就必须对高维观测数据的某些属性进行假定，比如 是数据集的内在维数。有了流形学习的数学定义，流形学习中维数约简过程就是 假设数据是均匀采样于一个高维欧式空间中的低维流形，从高维采样数据中找到 高维空问中的低维流形，并求出相应的嵌入映射。 流形学习的有效性建立在几个基本条件上，首先要求两个采样点足够近时， 它们之间的距离与其低维嵌入之间的距离近似等同，此要求为局部同胚假设；另 外还要求所有采样点足够稠密地覆盖整个流形，称为稠密性假设。这两条假设一 方面确保了流形的基本形状能够被数据近似表达，另一方面保证了数据点之间的 距离( 包括欧氏距离或测地距离) 可由邻域图中间最短路径近似，进而保障流形学 习算法映射结果的有效性；另外，数据所处的流形被默认为光滑连续，这是由局 部同胚假设与低维嵌入的连续性导出的自然结论，为连续性假设。 2 4 流形学习降维算法的分类 流形学习的降维方法如图2 2 大致分为线性和非线性两大类。再细分下去可 以分成5 个类别。传统的线性技术( p c a 1 6 l ，l d a 1 7 1 ) ；全局非线性技术( m d s 18 1 ， s p e 19 1 ，i s o m a p 3 1 ，f a s tm v u 2 0 1 ，k e r n e lp c a 2 ，g d a 【2 2 1 ，d i f f u s i o n m a p s ，s n e t 2 4 1 ，m u l t i l a y e ra u t o e n c o d e r s 2 5 】) ；局部非线性技术( l l e 【1 2 1 ，l a p l a c i a n e ig e n m a p 26 1 ，he s s ia n l l e t 27 1 ，l tsa 28 】) ；局部非线性技术的扩展 9 ( m v u 2 9 1 ，l p p 3 0 1 ，l l t s a t 3 1 】) ，线性模型的排列( l l c 【3 2 1 ，m a n i f o l dc h a r t i n g t 3 3 】) 。 图2 2 降维方法 主成分分析p c a 的核心思想源于k l 变换，主要目的通过线性变换寻找一 组最优单位正交向量基的线性组合重构样本，使得重构前后的误差最小。而且鉴 于p c a 是无监督的学习，较难用于描述不同样本之间的差异。l d a 则刚好相反， 是一种有监督的学习方法，通过寻找线性变化使得类内散度矩阵最小且类间散度 最大。但它要避免由于样本维数远大于样本数所带来的奇异值问题。由于p c a 和l d a 都是基于样本的二阶统计信息，忽视了高阶统计信息的不足。独立成分 分析i c a 则解决了这个问题，在样本中找一组独立的基来描述样本数据，主要 应用于盲信号分离。i s o m a p 从保持数据的全局结构出发，用图论进行降维。 l l e 从保持数据局部线性结构出发，用局部区域的近邻点来表示数据样本点，并 且不考虑远点的距离，具有旋转、尺度和平移不变性等优点。i s o m a p 保持的是 测地线距离，具有较小形变，不足之处在于i s o m a p 基本假设是全局等距离映射 和凸参数空间。在l a p l a c i a ne i g e n m a p 方法中，流形上的l a p l a c e - b e l t r a m i 算子 可以看作图的l a p l a c i a n 的逼近，l a p l a c i a n 最前面的特征向量就是流形上 l a p l a c e b e l t r a m i 算子特征函数的逼近，在拉普朗斯特征映射算法中，由于流形 结构的描述由近邻图来近似，通过选择适当的边权重，l a p l a c e b e l t r a m i 算子可 1 0 通过邻接图的热核函数来近似，于是高维数据集的低维嵌入映射可以近似定义为 整个流形上的l a p l a c e b e l t r a m i 算子的内在特征映射。i s o m a p 、l l e 、l a p l a c i a n e i g e n m a p 都属于非线性的流形学习降维算法，揭示了数据低维空间流形的几何 结构，但不能解决新样本的低维表示。b e n g i o t 3 4 】等提出了基于核方法来解决新样 本的“o u to f e x a m p l e 问题。此外还有其他学者提出的流形学习降维方法，如l e e 【3 5 j 提出基于非负矩阵分解( n o n n e g a t i v em a t r i xf a c t o r i z a t i o n ) 算法的数据降维方法， 在矩阵均为非负值的情况下对其进行非负的分解。在数据挖掘领域，i s o m a p 、 l l e ：- l a p l a c i a ne i g e n m a p 等无监督的机器学习方法适合解决聚类问题。而间隔 分析方法f i s h e r 和l d a 则适合解决分类的问题。某种流形学习降维算法不可能 在所有情形下对其他算法具有绝对的优越性，算法的性能与样本数据的分布以及 要解决的问题的类型密切相关。l l e 、l e 、l t s a 等非线性流形学习方法，尽管 可以发现隐藏在高维数据中的非线性流形结构，但它们没有直接的映射函数，仅 仅定义在训练样本的数据上，在面对人脸识别此类模式识别问题时存在不能直接 获取新样本嵌入坐标的缺点，即不能有效解决样本p b ( o u t o f - e x a m p l ep r o b l e m ) 学 习问题。h e 【3 0 】提出一种名为保局投影l p p 算法，该算法为l a p l a c i a ne i g e n m a p 算法的线性近似，通过近似流形的l a p l a c i a n b e l t r a m i 算子的特征函数得到直接 的映射函数，从而实现将新的测样本映射到学习得到的特征空间上，从而有效解 决新样本的问题。l p p 算法是线性流形学习算法的线性化的一个标志性算法。此 外还出现了保局嵌入n p e 算法，线性局部切空间排列l l t s a 算法。 流形学习中的全局方法要求流形所对应的低维空间的子集是凸的，这样才能 保证所构造的流形上距离较远的点之间的联系准确，而且为了找出远距离点之间 的联系，需要较多的计算时间；局部方法无需考虑远距离点之间的关系，因而计 算复杂度要小于全局方法；局部模型的全局排列方法在对局部模型进行学习时， 需采用e m 算法估计其参数，容易产生局部极值的问题，而且算法参数较多。此 外，由于局部方法只需要考虑流形邻近点之间的关系，无需考虑流形所对应的低 维空间的子集是凸的，所以有更广泛的应用前景。但正是由于局部方法只考虑流 形上的邻近点，当邻域之间的交叠不够的时候，流形上远距离点之间的联系较弱。 此时会出现将流形上远距离点映射到低维空间近距离点的现象，这种现象在邻域 1 i 关系只是通过单一权值来确立的l l e 和l e 上更加的明显。而且，由于局部方法 中流形上较远的点之间的关系不明确，因此，全局方法的嵌入结果要比局部方法 的嵌入结果有着更直接的意义，从上述分析可得知，如何有效的同时对局部与全 局流形结构进行保持，即近邻的高维数据点映射到内在低维空间后仍为近邻点， 远点的高维数据点映射到内在低维空间继续保持其远点的关系显得尤为重要。 投影寻踪( p r o j e c t i o np u r s u i t ) 是一种可用于高维数据降维分析的方法，它是 由f r i e d m a n 和t u k e y t 3 6 】将整体离散程度和局部凝聚程度结合起来形成新指标来 做聚类和分类分析。该方法能成功的克服高维数据的“维数灾害”，寻找最优的投 影方向将高维数据投影到低维空间上，再对投影后的低维数据进行分析，比较不 同低维投影结果，从而最大限度地揭示了数据的某种内在规律。该方法虽然是以 数据的线性投影为基础，但它找的是线性投影中的非线性结构，可用来解决一定 程度的非线性问题。 互信息就是在最近邻区域和流形图上，假设交互信息是对被观察空间与被 嵌入空间之间的不同概率分布的测量。从信息论的角度来看，在观测空间数据集 和嵌套空间数据集中，近邻数据间概率的信息熵应该最小。随机近邻映射s n e 2 4 】 是一种通过最小化被观察空闻与被嵌入空间之间概率分布差异的方法，它通过迭 代技术尝试保留低维流形数据间点对距离，不足之处是采用迭代法使损失函数最 小化容易陷入局部最小，因而存在进一步改善的可能。 2 5 经典流形学习降维算法 2 5 1 主成分分析 主成分分析( p c a ) 也被称为k - l 变换( k a r h u n e n l o e v et r a n s f o r m ) ，在全局 最小重构误差的意义下构建一个高维数据的低维数据表示，而数据点协方差矩阵 最大几个特征值所对应的特征向量生成的子空间正好满足这个条件。p c a 是一 种理论完善且算法上可行有效的线性降维方法，但是其有效性建立在假设数据嵌 入在全局线性或近似线性的低维子流形上p c a 能够在概率框架重写，能通过e m 算法执行p c a 。p c a 大量成功运用在模式识别领域，p c a 主要的缺点在于随着 维数的升高，协方差矩阵成比例地增长，特征向量的计算量会很高。 1 9 4 6 年，k a r h u n e n 和l o e v e 提出了k - l 变换，指出了k l 变换是在线性 条件下的最优变换，这就是p c a ( p r i n c i p l ec o m p o n e n ta n a l y s i s ) 方法的前身。 p c a 方法主要的优点是计算简单，去除噪声，能彻底消除相关。p c a 通过找到 数据集在低维中的一个线性的、变异最大的主要成分，使得重新构造数据集的误 差最小，尽可能多地表示原数据集中的变异。 p c a 算法的主要步骤如下： ( 1 ) 计算数据x = ( 而，恐，) 的协方差矩阵， s = ( x ，- ) ( x ，- ) r = l i n g r i = 1 ( 2 ) 对矩阵s 进行特征值分解j = w a ，这里w = ( m ，m ) ， a = a i a g ( 2 1 ，五，丸) ( 3 ) 使用前d 个特征值作为子空间的基底即高维数据x = ( 而，而，) 可以用薯在d 个基底上的投影来得到，只= 町薯，= ( m ，) ，而用所来 重建薯，可以用毫= 眠来得到。 p c a 已经在在需要处理大量数据的领域取得相当成功的应用，如人脸识别、 地震分析学。而p c a 的最大缺点是协方差矩阵的大小与数据样点集的维数成比 例。所以，特征向量的计算可能并不适用于所有的高维数据集( 假设n d 的情 况下) 。相似的解决方法，如s i m p l ep c a 通过使用一个反复h e b b i a n 逼近估计协 方差的主要特征向量，可以很好的地处理这个问题。 2 5 2 等距映射 等距映射( i s o m a p ) 是一种优秀的全局保持的流形学习算法。在介绍i s o m a p 算法前先介绍一个经典的维数约简算法一多维尺度变换( m d s ) 。i s o m a p 算法就是 以m d s 为基础的。 多维尺度变换( m d s ) 的思想：将高维空间中的数据映射到低维空间后尽 可能保持成对数据点之间的距离与它们的原像在高维空间中的距离相等，m d s 通过计算高维空间中样本之问的相似性，并把这种相似性尽可能的在低空间得到 保持，通过这种表示空间的转换，能有效降低高维空间中的数据表示。m d s 是 一种优秀的数据降维方法，而且它的思想已经被应用到多种流形学习算法中。目 前，m d s 被广泛的应用于高维数据的可视化应用，例如核磁共振功能成像分析 和分子模拟。m d s 的前提假设：数据点之间的相似性与它们的欧式距离密切相 关，距离越小的越相似。因此它保持的是数据点的欧氏距离，而没有考虑数据点 的近邻分布问题。 实现：通过定义目标函数来表示数据降维后在低维空间对高维空间中距离 的重构误差，然后最小化目标函数，有两种误差函数：r a ws t r e s s 函数( 】，) 和 s a m m o n 损失函数烈】，) ： 烈l ，) = ( 0 葺一_ | | - 0 所一乃i i ) 2 ( 2 1 ) = 豇习1 否 ( 2 2 ) 其中i k x 州是高维空间数据点的而和x ，的欧氏距离，i y ，一j ，是高维空 间数据点的y ，和乃的欧氏距离，公式( 2 1 ) 、( 2 2 ) 都是用来表示重构误差，低 维映射通