（计算机软件与理论专业论文）基于局部线性分析的降维算法研究.pdf

。， 学位论文独创性声明 7 删i l | ir舢舢irul|fillii i 删i ! 【y 18 9 0 4 5 。1 ” 本人承诺：所呈交的学位论文是本人在导师指导下所取得的研究成果。论文中除特别加以标注 和致谢的地方外，不包含他人和其他机构已经撰写或发表过的研究成果，其他同志的研究成果对本 人的启示和所提供的帮助，均已在论文中做了明确的声明并表示谢意。 学位论文作者签名：列慨 学位论文版权的使用授权书 本学位论文作者完全了解辽宁师范大学有关保留、使用学位论文的规定，及学校有 权保留并向国家有关部门或机构送交复印件或磁盘，允许论文被查阅和借阅。本文授权 辽宁师范大学，可以将学位论文的全部或部分内容编入有关数据库并进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文，并且本人电子文档的内容和纸质 论文的内容相一致。 保密的学位论文在解密后使用本授权书。 学位论文作者繇型丝指导教师签名 签名日期：2 口lf 年占月j 日 辽宁师范大学硕士学位论文 摘要 随着信息、多媒体及数字化技术的迅猛发展，高维数据时代随之到来，并已成为描 述客观世界的一个有力工具，如基因的表达、视频追踪、医学图像处理、高维时间序列 分析等，与此同时，传统的分类、聚类等算法已经无法应用于高维数据的处理中，因此 迫切需要寻求一种数据降维方法，而流形学习的出现为高维数据降维提供了一个很好的 途径。 流形学习在十余年的发展历程中，在国内外众多学者的努力下，已经开始趋于成熟， 并涌现出了许多值得借鉴的方法。例如：等距映射、局部线性嵌( l l e ) 入以及局部切 空间排列( l t s a ) 算法等。 l l e 及l t s a 都基于局部近似可线性化的假设而提出的非线性降维方法，在真实世 界的高维数据中可以得到较好的效果。但在很多时候，局部的数据往往存在高曲率分布 及噪音，而局部的方法对上述情况非常敏感，此时l l e 及l t s a 就无法获得正确的低 维嵌入，如何解决此类问题成为流形学习研究的一个重要分支。 本文主要针对以上流形学习中的重要问题提出相应的解决方法： ( 1 ) 分析局部切空间的几何性质，在此基础上提出一种自适应的邻域选取方法，并 将l t s a 算法加以改进。 ， ( 2 ) 分析噪音及高曲率对低维空间的影响，并将噪音进行分类，提出一种抗噪能力 较强的角度全局嵌入算法。 ( 3 ) 以l l e 算法为例，对局部可线性化问题展开讨论，给出一种近似的可线性化 标准，同时在源数据是稀疏分布的情况下，给出一种基于稀疏嵌入分析的降维方法。 最后，实验证实了文中所提出方法的有效性。 关键词：高维数据降维；流形学习；局部线性化；局部切空间 b 一 基于局部线性分析的降维算法研究 r e s e a r c ho nd 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 dl o c a l l yl i n e a r a n a l y s i s a b s t r a o t a sr a p i dd e v e l o p m e n to fi n f o r m a t i o n ，m u l t i m e d i aa n dd i g i t a lt e c h n o l o g y , h i 曲 d i m e n s i o n a ld a t aa p p r o a c hh a sb e c o m eap o w e r f u lt o o lt od e s c r i b et h eo b j e c t i v ew o r l d ，s u c h a sg e n ee x p r e s s i o n ，v i d e ot r a c k i n g , m e d i c a li m a g ep r o c e s s i n g ，h i g h d i m e n s i o n a lt i m es e r i e s a n a l y s i sa n ds oo n m e a n w h i l e ，t r a d i t i o n a lc l a s s i f i c a t i o n , c l u s t e r i n ga l g o r i t h m sc o u l dn o tb e e f f i c i e n t l ya p p l i e dt oh i g h d i m e n s i o n a ld a t a , s oi t i s u r g e n t t os e e ka n a p p r o a c hf o r d i m e n s i o n a l i t yr e d u c t i o n t h ee m e r g e n c eo fm a n i f o l dl e a r n i n gp r o v i d e sa na p p r o p r i a t ew a y f o rd i m e n s i o n a l i t yr e d u c t i o no fh i g h - d i m e n s i o n a ld a t a 。 m a n i f o l dl e a r n i n gh a sb e c o m em a t u r eu n d e rt h ee f f o r t so fm a n yd o m e s t i ca n df o 而印 s c h o l a r si nt h ec o u r s eo fm o r et h a nad e c a d e ，a n dm a n ye f f i c i e n tl e a r n i n gm e t h o d sa r e p r o p o s e d s u c ha si s o m a p ，l o c a l l yl i n e a re m b e d d i n ga n dl o c a lt a n g e n ts p a c ea l i g n m e n t a l g o r i t h m ，e t c w i t ht h ea s s u m p t i o nt h a tl o c a ld a t aa r ea p p r o x i m a t e l yl i n e a r i z e d ，l l ea n dl t s ac a ng e t b e t t e rr e s u l t si nt h er e a lw o r l do fh i 。g hd i m e n s i o n a ld a t a , w h i c ha r en o n - l i n e a rl e a r n i n g m e t h o d s h o w e v e r , t h ed a t ai so f t e nw i t hh i g hl o c a lc u r v a t u r ed i s t r i b u t i o no rn o i s ei nm a n y a p p l i c a t i o n s ，w h i l et h el o c a la l g o r i t h m sa r ev e r ys e n s i t i v et ot h a t a tt h i sp o i n t ，l l ea n d l t s ac a nn o to b t a i nt h ee o r r e c tl o w d i m e n s i o n a le m b e d d i n g ，t h a tp r o b l e mi sa l li m p o r t a n t b r a n c ho fm a n i f o l dl e a r n i n g i nt h i sp a p e r , t h ec o r r e s p o n d i n gm e t h o d sa r ep r o p o s e df o r t h ep r o b l e m sa b o v ei n m a n i f o l dl e a r n i n g ， ( 1 ) p r o p o s e da na d a p t i v en e i g h b o r h o o ds e l e c t i o na l g o r i t h mb ya n a l y z i n gt h eg e o m e t r i c p r o p e r t i e so ft h el o c a lt a n g e n ts p a c e ，a n dm o d i f i e dl t s a ( 2 ) a n a l y z e dt h ei n f l u e n c eo fn o i s ea n dh i 曲c u r v a t u r et ol o w d i m e n s i o n a ls p a c ea n d c l a s s i f i e dt h en o i s e s ，t h e np r o p o s e da na n g l eg l o b a le m b e d d i n ga l g o r i t h mw i 也p o w e r f u ln o i s e i m m u n i t y ( 3 ) d i s c u s s e dt h el i n e a r i z a t i o no fl o c a ld a t ab a s e do nt h el l ea l g o r i t h m ，a n dp r o v i d e da s t a n d a r do fa p p r o x i m a t e l yl i n e a r i z a t i o n a d d r e s s i n gt h es i t u a t i o nt h a ts p a r s ed i s t r i b u t i o ni n t h es o u r c ed a t a , a ne m b e d d i n gd i m e n s i o nr e d u e t i o na l g o r i t h mb a s e do ns p a r s ea n a l y s i si s p r o p o s e d f i n a l l y , t h ee x p e r i m e n t sh a v ep r o v e dt l l a tt h ep r o p o s e dm e t h o d sa r ee f f e c t i v e 一i i 辽宁师范大学硕士学位论文 k e yw o r d s ：h i g hd i m e n s i o n a ld a t a s e tr e d u c t i o n ；m a n i f o l dl e a r n i n g ；l o c a l l yl i n e a r ；l o e a l t a n g e n ts p a c e i i i 基于局部线性分析的降维算法研究 目录 摘要i a b s t r a c t j 。：i i 1 绪论l 1 1 研究背景及问题的提出。1 1 2 流形学习的国内外研究现状2 1 3 流形及流形学习。4 1 3 1 流形的概念及其相关的数学定义_ 4 1 3 2 流形学习的出现6 1 4 流形学习的主要参数及确定8 1 5 本文的主要研究内容8 1 6 本文的组织结构9 2 一种自适应的邻域选取算法及改进的l t s a 1 0 2 1 引言。1 0 。2 2 数据的正交投影：。1 1 2 2 1 正交投影的角度1 1 2 2 2 曲率的计算。1 2 2 3 自适应邻域的选取新方法1 2 2 4 基于偏离度的自适应邻域选取的局部切空间排列算法( d a l t s a ) 1 5 2 5 实验结果16 2 6 硝、结18 3 一种全局的角度优化嵌入算法j 。2 0 3 1 引言：2 0 3 2 协方差阵的更新2 1 3 3 子空间分析。2 2 3 4a o g e 算法2 3 3 5 实验结果与分析2 5 3 5 1 不规则m 数据实验2 5 3 5 2f r e yf a c e 表情分类2 6 3 5 3 手写体识别2 8 3 5 4a r 人脸识别2 9 3 5 5 手工流形数据3 0 辽宁师范大学硕士学位论文 3 5 6 实验结果分析3 1 3 6 j 、结3 2 4 一种基于稀疏嵌入分析的降维方法3 3 4 1 引言3 3 4 2l l e 算法的介绍3 4 4 3 可线性化分析3 5 4 4 一种排列的稀疏l l e 算法3 8 4 5 实验结果分析4 0 4 5 1 手工流形实验4 0 4 5 2f r e y 表情2 d 可视化。j - 4 2 4 6 、结4 3 5 结论j - 4 4 5 ：1 总结4 4 5 2 展望。4 4 参考文献4 5 附录a 1 引理3 1 证明4 9 附录a 2 定理3 1 证明5 0 攻读硕士学位期间发表学术论文情况5 2 致谢5 3 一v 一 辽宁师范大学硕士学位论文 1 绪论 1 1 研究背景及问题的提出 随着信息技术飞速发展及数字化水平的提高，为了更加细致的描述现实世界中的各 种现象，高维数据开始渐渐活跃起来，并给许多行业带来了新的生机，比如在影视动画 及体育运动训练中，为了对已捕获的人体运动数据进行检索、合成新风格，我们需要考 虑对人体运动捕捉【l 】等为背景的高维时间序列进行分析；农业的信息化和精细农业的发 展，需要农业信息采集、遥感图像分析、气象学等的农业高维数据【2 1 ；在些安全系统 中，需要人脸、手写体等以图像为背景的高维数据【3 1 ；生物领域中基因表达谱数据是以 基因数据为背景的高维数据【4 巧】；在医学中为了对疾病做出更准确的描述和判断，需要 c t 以及病理图像为背景的非线性高维数据【6 】，此外，还有入侵检测的高维数据【_ 7 8 】等。 可见，信息时代的到来，使得高维数据已经出现在与我们生活息息相关的各个方面，同 时高维数据也为我们更丰富的描述自然界的各种复杂现象打下了良好的基础，与之应运 而生的流形学习开始逐步渗透到科学技术的各个领域。 但由于高维数据与低维数据本质上的不同【9 】，以往许多处理低维数据的算法将不再 适用。不仅如此，b e l l m a n 指出数据维数过高将导致“维数灾难”【1 0 1 ，即出现在给定精 度时，描述一个多元函数所需的样本量随着变量个数的增加呈指数形式增长，就是说出 现高维数据的同时，也同样面临由此带来的海量数据及小样本数据【1 l 】等问题。以上问题 成为许多聚类、分类及检索算法的瓶颈；如何解决高维数据的问题，成了近十年来许多 学者研究的焦点。 幸运的是，流形学习概念【1 2 d 3 】的提出，提供了处理高维数据的新途径。流形学习 把高维数据看成是由少数几个低维空间的变量衍生出的高维现象，其目的是找到高维数 据潜在的低维流形结构，最终达到降维的目的。同期的s c i e n c e 上还有一篇文章提出“感 知以流形的方式存在 【1 4 】的观点，为流形学习的应用前景奠定了基础。流形学习不仅 是一种处理高维数据的方法，而且更有其潜在的哲学意义：通过对高维数据集的分析， 我们发现，某个数据集仅仅分布在高维空间的某个区域，并且在这些高维数据集包含了 许多冗余的信息及噪音，通过适当的变换，用很少的变量就可以描述数据集几乎全部的 信息，也就是说，高维的采样数据是自然界表现出事物的“现象，我们希望能够透过 这个“现象 找到恰当的方法能够寻其“本质 ，这里恰当的方法即适当的变换，本质 即引导高维现象的少数变量。 基于局部线性分析的降维算法研究 1 2 流形学习的国内外研究现状 早期的方法如主成分分析【1 5 1 ( 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 6 1 ( 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 ) 等算法可视为线性流形学习算法。p c a 考虑整体流形是线性或近似线性的，通过计算中心化样本的协方差阵最大化方差来寻找 主成分进行降维；m d s 是通过寻找样本间的距离矩阵，通过最大化样本内积的相似程 度来达到降维的目的，尽管它和p c a 目标函数的含义不同，但在一定条件下它们可以 相互转化。这样的转化是有意义的【1 。7 1 ，当样本数远远高于样本维数或维数远远高于样本 数时，这样的转化可以大大减小计算量。但这些线性算法处理非线性流形的效果并不理 想。 流形学习的明确提出始于2 0 0 0 年s c i e n c e 上的两个比较成熟的非线性流形学习算 法：s a i n t r o w e i s 等人的局部线性嵌入【1 2 】( l o c a l l yl i n e a re m b e d d i n g ，简称l l e ) 及j o s h u a b t e n e n b a u m 等人的等距映射【1 3 1 ( i s o m a p ) 。l l e 算法无论在思想上和形式上都堪称经 典，也是流形学习中出现的第一个非线性算法，它的出现，为今后流形学习的发展提供 了理论指导。l l e 的主要思想是通过计算每个样本的k 最近邻( 或施邻) 邻域寻求该局部 的线性关系并由此重建权值，进而构建出权值矩阵，它希望这个权值在降维过程中保持 不变，从而在保持原来拓扑结构的基础上，映射到低维流形；l l e 每个点的近邻权值保 证了在平移、旋转及伸缩尺度上的不变性，但该算法在计算权值阵时需要近似，很可能 导致最后整体低维坐标重建的误差偏大，出现几何变形，而且l l e 过多的考虑了数据 间的局部信息，没有一个很明确的整体把握；对l l e 来说局部的线性假设是重要的， 正因如此，它要求稠密采样，对于稀疏数据集u 正的效果并不理想。与l l e 类似，而 后的大多数的非线性算法都需要寻找k 最近邻( 或衍邻) 邻域，从考虑局部出发，最终构 建出一个统一的整体结构。i s o m a p 的出现并非偶然，它的理论基础源于m d s ，也需要 计算距离矩阵。即便如此，该算法仍有其独特之处，尽管i s o m a p 需要寻找近邻近 邻点处的距离采用两点的欧氏距离，近邻之外的点考虑应用d i j k s t r a 寻找最短路径，用 得到的路径长度来近似代替两点间的测地线距离，这是一个考虑整体的非线性思想，所 以i s o m a p 的学习效果比m d s 要好得多，美中不足是当样本太多会在寻找最短路径时耗 费大量的时间，而当样本分布不连续即流形假设不被满足时，该算法及l l e 等许多非 线性算法都难以奏效。在这一点上，文贵华等人提出了邻域参数动态变化的局部线性嵌 入【l 引，比较好解决了样本分布不连续的学习问题。 有了以上的基础，而后涌现出了很多优良的流形学习算法，l a p l a c e 特征映射【1 9 】( l e ) 利用高斯核函数构造样本近邻图，得到稀疏的邻接矩阵，使目标函数通过保持这种图结 构达到寻求低维流形的目的，它也可以看作权值矩阵的另夕卜种描述。而后出现了基于 辽宁师范大学硕士学位论文 切空间的流形学习方法，首先由d o n o h o 等人提出了h e s s i a nl l e 2 0 】( 简称h l l e ) ，利 用h e s s i a n 矩阵的能表达数据曲率几何性质的特点，通过计算样本局部切空间坐标并将 其进行g r a m s c h m i d t 正交化来构建近似的h e s s i a n 阵，得到最小化高维样本曲率的优化 模型并嵌入到其潜在的低维流形。w a n l im i n 等人在几何上进一步证明局部p c a 低维空 间可以逼近以邻域均值为中心的切空洲2 1 1 ，这为基于切空间的流形学习算法提供了可靠 的理论依据。z h a n g 和z h a 提出了局部切空间排列算法【碉( 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 ) ，在局部计算出以样本均值为中心的高维样本数据的协方差阵进而利用p c a 寻找局部的低维空间，将所有局部切空间的坐标进行整合，从而得到低维空间的整体坐 标。由于l t s a 很难进行增量学习，时间复杂度也很高，杨剑等人【2 3 】改进了l t s a ，使 之具有更强的学习能力。 以上都是基于距离度量的流形学习方法，还有一些基于其他度量的流形学习方法， 例如漫散射洲( d i f f u s i o nm a p s ，简称d m ) 一种基于动力学理论的流形学习方法， 该算法利用高斯核函数来计算全连接图矩阵，认为规范化的图矩阵即转移矩阵，应用随 机游走的向前概率定义d i f f u s i o n 距离，并根据马尔科夫链的谱分析，得到最终的低维 嵌入。s t r o w e i s 等希望降维前后保持数据点之间的远近关系，提出了随机邻域嵌入【2 5 】 ( s t o c h a s t i c n e i g h b o r e m b e d d i n g ，简称s n e ) 算法，由此定义了一种新的能描述这种关 系的概率，利用k u l l b a c k l e i b l e r 散度构建目标函数，最小化目标函数可通过梯度下降 法迭代求解，但是收敛速度和初始点的选取有关，有时甚至收敛到局部最小解。 为了更好的解决实际问题，近几年涌现出局部保持投影【2 6 j ( l o c a l i t yp r e s e r v i n g p r o j e c t i o n ，简称l p p ) 、邻域保持嵌入【2 7 】( n e i g h b o r h o o dp r e s e r v i n ge m b e d d i n g ，简称 n p e ) 、正交的邻域保持投影【2 列( o r t h o g o n a ln e i g h b o r h o o dp r e s e r v i n gp r o j e c t i o n ，简称 o n p p ) 以及线性的局部切空间排列算法( l i n e a rl o c a lt a n g e n ts p a c ea l i g n m e n t ，简称 l l t s a ) 【2 9 】等能够提取局部信息的线性流形学习算法，这些算法都对应于已有的非线性 算法，将高维数据映射到低维子空间的非线性隐式映射明确为一种线性映射而得到的。 尽管这些算法都能很好的把握局部信息，但都无法进行含有噪音的学习，而真实世界的 数据不可避免的要引入噪音，这对流形学习算法带来了挑战。 由于现实世界的丰富多彩，用来描述世界的数据集种类也比较繁多，一个方法不可 能适用于所有数据集，正因意识到这一点，近些年也有很多学者针对不同数据集自身的 特点，提出了与之相适应的流形学习算法，并在相关方面取得了一定的成果。主要表现 在以下几个方面： i 关于含有噪音的数据，国内外已经有了一些成果，如鲁棒p c a 3 0 】( r o b u s tp c a ) ， 它可以看作是由一个加权p c a 衍生而来，与p c a 不同，它不以最大方差作为优化的目 基于局部线性分析的降维算法研究 标，而是考虑样本在低维空间的投影与该样本的相似度的重构误差最小作为优化的目 标，通过迭代直到优化的低维空间基底的变化满足一定的精度为止，而权值的确定主要 利用h u b e r 函数【3 1 1 。鲁棒p c a 考虑重构误差越大的样本点很可能是异常点，应该赋予 较小的权重对这种异常进行处理以降低其重构误差；利用这种思想，h o n gc h a n g 等人 提出了鲁棒的l l e 算法【3 2 1 ，该算法将局部的鲁棒p c a 应用于l l e ，用来降低奇异点给 l l e 带来的重构误差，进而达到能够对有噪音的数据进行流形学习的目的。除了上述两 种方法外，还有一些能够处理含有奇异点的流形学习方法如j i n h y e o n gp a r k 等人的局部 光滑流形学习【3 3 1 ，不过这些算法都是以加权p c a 为基础，以寻找奇异点为前提来进行 学习，这就不免要增大时间消耗，而在海量样本数据集中这个缺点尤为明显。 i i 上面的叙述曾提到对于稀疏数据集很多流形学习算法都难以奏效，这主要是由源 数据集的信息量不足造成的，近些年也有人在涉足相关方面的工作。如将样本内积的核 函数引入l l e 的框架结构中，通过核函数的映射来近似稀疏数据的真实测地距离【3 4 】。 宋欣等人利用l a p l a c e 特征映射优化函数的结构，将其低维嵌入坐标看成高维样本在流 形的主延伸方向的投影，增加了梯度的近似信息【35 1 ，以此来保证源数据集在流形学习的 过程中不会因信息缺乏造成数据分布的形变。 i i i 有些数据集并不满足流形潜在连续性的假设，需要提出特殊的方法来学习这样的 数据集，如自相交流形【3 6 】，在其相交区域附近，对当前流形样本的延伸方向需要做出选 择；环状流形则需要解决样本沿流形主方向“行走 始点与终点有重合的情况，这需要 考虑如何打开环结构，进行有效的降维【3 7 】。这种不满足流形假设的情况还体现在多流形 中，而多流形并非个例，如人脸的识别，需要很多人的样本，但每个人的样本集独立成 为一个流形【3 8 1 ，这就需要我们考虑多流形的学习方法来降维。多流形近几年也逐渐得到 了人们的重视，主要是基于已有的算法进行多流形学习，如马瑞等人提出的基于l l e 的多流形学习算法【j 圳。 1 3 流形及流形学习 1 3 1 流形的概念及其相关的数学定义 早在1 8 5 4 年，流形的概念就已经被r i e m a n n 提出，但当时并没有对度量空间或拓 扑空间上的点通过恰当的方式进行表述，后续的研究者把它建立在拓扑结构之上，使其 定义更加完备。所以本文首先介绍拓扑学中的一些基本概念m 】： 拓扑及拓扑空间 设x 是一个集合，f 是x 中某些子集族，如果f 满足以下性质： ( 1 ) f 内任意个集合的并仍属于f ，即f 对任意的并运算封闭； 辽宁师范大学硕士学位论文 ( 2 ) f 内有限个集合的交仍属于f ，即f 对有限的交运算封闭。i ( 3 ) x 及0 属于f 。 则称f 是x 的一个拓扑。集合x 装备了拓扑结构f 以后，就称( x ，f ) 是拓扑空间。同一 个集合装备的拓扑结构不同，得到的拓扑空间也不同。 同胚映射及同胚 设( z ，r x ) 及( 】，0 ) 是两个拓扑空间，厂是从x 到y 的双射同时又是连续映射( 则_ 1 存在) ，厂- 1 是从】，到x 的连续映射，则称厂是同胚映射，当两个拓扑空间之间存在一 个同胚映射时，称这两个空间同胚。 h a u s d o 厂纤公理及h a u s d o r 厅空间 、设( x ，f ) 是拓扑空间，若对内的任意两元素x 、y ( x y ) ，总存在两个开集( 这里的开 集即邻域) q 和d ，其中qn d ，= a ，并_ rx q ，y q ，则称( x ，f ) 满足h a u s d o r f f 公理，此时( x ，f ) 为h a u s d o r f f 空间。 有了以上的定义，我们可以很容易的得到流形的概念： 流形 设m 是一个拓扑空间，并且是h a u s d o r f f 空间， ) 是m 的开覆盖。如果对每一 个开集。联系着一个映射：一圪，圪是n 维欧氏空间内的一个非空开集，也可 以不妨假设它是刀维开球或，l 维开矩，并且是同胚映射，即虬和圪同胚，就称m 是 一个n 维拓扑流形，简称n 维流形。 微分流形 直观地，在，z 维流形上加入“微分结构 就可以使之成为微分流形。为了更进一步 的介绍微分流形的概念，我们直接引入c 7 流形： 设m 为一个n 维流形，则m 存在开覆盖 虬 ，并且每个以联系着一个映射： ：一圪，是同胚映射。若虬何都在 ) 内，且虬n 彩，设点 p n u p ，在仇的作用下将p 映射为点工r 4 ，在的作用下将p 映射为点y r ”， 则对点p 而言，既可用z 也可用y 表示，于是x 和j ，之间存在如下的映射： 铷。既1 ：( 眈n ) _ ( 虬n ) 为c r ( ，1 ) 的多元向量值函数，则称m 为n 维的c 7 流形。 基于局部线性分析的降维算法研究 如果所有的映射都是c o ( 连续) 的，则称为m 拓扑流形。当，= 0 0 时，即映射无限次 可微，称m 为，z 维的c 。流形。 此时称玩为坐标邻域，为坐标映射，( ，) 为坐标图， ( 玩，纯) ) 为m 的坐标 图册。 这就好比一幅世界地图册，可以反映整个地球的全貌。虬为地球的某一区域，则 将地球的这一区域映射到地图的某页( ，) ， ( ，纯) ) 就是这本地图册。我们所研究 的流形都假设其为微分流形。下面是一些手工流形的例子：瑞士卷、三叶草形、双峰形 等( 如图1 1 ) 。 ( a ) s w i s s - r o l l ( d ) h e l i x( e ) t w i np e a k s( f ) s e l f - i n t e r s e c t i o n 图1 1 六种手工流形 f i g 1 1 s i xm a n u a lm a i l i f o l d s 1 3 2 流形学习的出现 从流形的定义可以看出，流形定义本身已经为流形学习创造了条件，不妨考虑三维 欧式空间中的半球，由流形的定义可以发现总存在那样一个映射，使得半球面上的每一 点都与二维空间上某一区域的点一一对应( 如图1 2 ) ，故半球面是一个二维流形；也 就是说，沿着半球面能够获得的信息，在与之对应的二维流形上一样可以得到，由此考 虑更高维空间中的数据是其内在本质低维流形所衍生出来的想象。 辽宁师范大学硕士学位论文 更进一步地，在文献【1 4 】中提到：流形是人类感知的基础，我们的大脑会找到某些方 式来反映这些流形。尽管如何反映这些流形到目前还没有定论，但最自然的反映就是大 量神经元的编码，而这样大量的编码可由收集神经元的放电频率得到，所有神经元放电 一次，就会反映在抽象空间中的一个点上( 这个点所在的空间维数与大脑神经元数目相 等) ，而这些神经元的放电频率则可以体现在由少数变量决定嵌入在较低维数的光滑函 数中。 图1 2 三维欧式空间的半球对应于一个二维流形 f i g 1 2 a h e m i s p h e r ei n3 de u c l i d e a ns p a c ec o r r e s p o n d 、珩ma2 dm a n i f o l d 同样的，人类在识别人脸图像时，已经把人脸图像空间转化为一种稳定的神经活跃 模式，并以流形的方式存储，不同人的图像对应不同的流形，人类在识别人脸的过程， 也就是在匹配这些潜在流形的过程。这就是前面所叙述的多流形学习的必要性。如下图 1 3 为手工多流形。 0 1 0 ( a ) t w os w i s s r o l l ( b ) t w o s u r f a c e 图1 3 手工多流形 f i g1 3 m a n u a lm u l t i - m a n i f o l d s 基于局部线性分析的降维算法研究 1 4 流形学习的主要参数及确定 在流形学习过程中，尤其是局部的非线性算法，学习效果的好与坏不仅取决于学习 的思路及设计的算法，还与目标维数及邻域参数的大小有关。关于邻域参数的选取目前 涉足的人尚少。选取过大将导致局部的短路现象( 如图1 4 ) ，选取过小将导致邻接信 息不足无法正确降维。而目标维数可以更进一步的称之为本征维数，它反映了描述该数 据集需要的最恰当的维数维数过高会出现信息冗余，维数过低则出现信息量不足， 都会影响算法的效果。本征维数的确定早在上世纪七十年代已经有人开始研究】，随着 流形学习的兴起，人们发现目标维数成为流形学习过程的瓶颈，使其再度得到广泛关注， 如极大似然估计法【4 l 】，包数方法【4 2 】等，都能很有效的估计流形的本征维数。 ， 1 ”。，i 卜 。，茂 飞鬻一爹，_ o - ：迂o ：7 此外，还有一些从其他角度考虑的流形学习算法，比如流形学习的增量算法、监督 及半监督算法【4 3 】等。可以看到，流形学习经过近十年的发展和众多学者的努力已经趋于 成熟，但是以上提出的流形学习的不足还有待进一步深入的解决。 1 5 本文的主要研究内容 本文主要针对上面叙述中流形学习的两个不足之处进行深入的研究，并提出了可行 的解决方案： ( 1 ) 以l t s a 为例，对含有噪音的数据集进行了深入分析，并将噪音进行分类， 指出哪些噪音将对流形学习造成较大影响；在l t s a 算法的基础上进行改进，针对含少 量噪音的数据集，提出了一种能够剔除噪音的流形学习算法。 辽宁师范大学硕士学位论文 ( 2 ) 根据噪音对低维子空间的影响的分析，提出一种抗噪能力较强的角度全局嵌 入算法。 ( 3 ) 在源数据集稀疏分布的情况下，以l l e 算法为例，细致的分析了样本点数与 样本间距离的关系，并找到一个可以判断源数据集稀疏与否的依据，在此基础上对l l e 算法进行了改进，得到适用于稀疏数据集的流形学习算法。 1 6 本文的组织结构 第一章，主要阐述了流形学习出现的应用背景，并对流形学习的发展史及国内外研 究现状加以陈述，同时介绍了与之相关领域的发展现状。 第二章，通过分析l t s a 算法在含噪音数据集的表现，找到影响l t s a 算法降维效 果的主要原因，在含有少量噪音时，考虑剔除噪音来改善学习效果，提出一种改进的 l t s a 算法。 第三章，有了第二章的基础，考虑当噪音过多时，通过对噪音的分类及深入分析， 提出了一种能够很好抵抗噪音的角度全局嵌入算法，最后给出实验，说明所提出的算法 在含噪音数据集中是有效的。 第四章，我们将发现大多流形学习算法都无法有效的学习稀疏数据集，所以在第四 章分析了稀疏数据集在进行流形学习时存在的缺点，并以l l e 为例提出了一种适用于 稀疏数据集的流形学习算法，并通过实验验证了算法的有效性。 最后对全文进行了总结和展望。 基于局部线性分析的降维算法研究 2 一种自适应的邻域选取算法及改进的l t s a 基于对局部切空间的几何性质的理论研究结果，本章提出一种基于局部切空间偏离 度的自适应邻域选取算法。该算法利用局部切空间的正交投影计算局部中心化样本点与 ， 其切空间的夹角，更好的刻画了数据所表现出来的局部性质，能够使不同邻域的样本点 得以区分，同时具备更好的抗噪音能力。该算法是对流形学习领域中著名的局部切空间 排列算法的一个有效改进，能够较好的学习局部高曲率的流形。实验证实了本章所提出 的邻域选取算法是有效的。 、 2 1 引言 随着信息、多媒体及数字化技术的高速发展，高维数据的应用越来越广泛，高维数 据的数据量也随之增加，这使得高维数据的维数约简显得尤为重要，流形学习的主要目 的是从高维数据中恢复出其潜在低维流形结构，从而得到信息损失较少的降维效果。主 成分分析( p c a ) 1 5 】对学习数据集的分布呈线性或近似线性的流形很有效，并且方法简 单，执行效率高，应用也比较广泛。但对非线性流形却难以奏效，往往达不到预期的学 ，习效果。 l t s a 【2 2 】是一种行之有效的流形学习算法，它的出现弥补了线性流形学习方法不 足，其主要思想可以概括如下t1 寻找局部近邻，寻找每个样本的k 最近邻点，并对邻 域数据进行局部的p c a 降维，目的是将局部高维数据投影到其局部切空间。2 对样本的 局部坐标进行合适的仿射变换，使其嵌入到全局的低维流形上。但由于局部切空间自身 的几何特性，使得l t s a 对偏离切空间较大的噪音十分敏感，除此之外，对局部线性化 程度低的高维数据，其恢复的效果也不是很理想。等距映射算法( i s o m a p ) 【1 3 】是多维尺 度变换( m d s ) 【1 6 】的深入改进，它利用最短路径的方法估计侧地距离来代替m d s 中的 欧式距离，这样可以对邻域做出更好的选择，在全局降维的同时引入了局部信息，但样 本点足够多时，最短路径计算量很大。a d a p t i v el t s a 4 5 】在l t s a 的基础上，在局部 数据降维时引入了曲率，克服了l t s a 对线性化程度低的局部数据恢复效果不好的缺点。 虽然利用切空间可以自适应的进行邻域选取，但由于局部切空间反映的是邻域的整体信 息，故无法充分利用近邻样本信息，进而在估计某个近邻点测地线曲率时，会因为其它 近邻点或噪音带来的偏差而增大该近邻点曲率的误差；而且估计任何一点的曲率都需要 进行一次s v d 分解，增加了算法的时间复杂度。 本章的基于局部切空间偏离度的白适应邻域选取算法对局部切空间的几何性质进 行了深入研究，给出了相关的理论研究结果。在理论研究的基础上提出了一种基于局部 辽宁师范大学硕士学位论文 切空间偏离度的自适应邻域选取算法( d a l t s a ) 。该算法利用局部切空间的正交投影 来计算中心化样本与其切空间的夹角，能更好的描述局部切空间的几何性质，进而区分 出本不属于该邻域的样本，同时该算法具有很好的抗噪能力，是对流形学习领域中著名 的l t s a 算法的一个有效改进。本章中基于局部切空间偏离度的自适应邻域选取算法充 分利用了局部切空间的几何性质及其近邻点的几何信息，在邻域选取和消除噪音两方面 取得了到较好效果。实验证实了本章的邻域选取算法是有效的。 为了使本章及下一章的条理更加清晰，首先需要讨论高维空间数据到低维空间的正 交投影问题。并给出如下定理。 2 2 数据的正交投影 2 2 1 正交投影的角度 设低维空间的一组基底为： q r m d ，高维样本集为：x = 玉，而，毛 r 胍”， 在这组基下的投影为其低维流形y = q r x ，y = 【y ，y 2 ，虬】r 如”。我们将样本石进行 ，、 中心化膏= x i ，一三1 1 ，i ，其中l = ( 1 ，1 ) 惫，i 为单位阵。由样本空间x 所形成的变换 刀 及正交投影矩阵的定义，我们可以得到如下定理： 定理2 1 经过中心化的某样本曼的正交投影为：q q 7 曼；该点偏离切空间的夹角余弦为： c o s , o =( 2 1 ) 进一步地， = a r c