（计算机软件与理论专业论文）基于mle的本征维数估计方法研究.pdf

3 二c 独创性声明 本人郑重声明：所提交的学位论文是本人在导师指导下独立进行研究工作所取得 的成果。据我所知，除了特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果。对本人的研究做出重要贡献的个人和集体，均已在文中作了 明确的说明。本声明的法律结果由本人承担。 学位论文作者签名：谨j 朱聋 日期：2 型2 ：! 学位论文使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位论文的规定，即：东 北师范大学有权保留并向国家有关部门或机构送交学位论文的复印件和电子版，允许 论文被查阅和借阅。本人授权东北师范大学可以采用影印、缩印或其它复制手段保存、 汇编本学位论文。同意将本学位论文收录到中国优秀博硕士学位论文全文数据库 ( 中国学术期刊( 光盘版) 电子杂志社) 、中国学位论文全文数据库( 中国科学技 术信息研究所) 等数据库中，并以电子出版物形式出版发行和提供信息服务。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：倡醢 e t 期：趔坌：4 学位论文作者毕业后去向： 工作单位： 通讯地址： 指导教师签名： 日期： 电话： 邮编： 摘要 自上个世纪以来，随着计算机技术的飞速发展，人们可以更好的处理复杂数据， 与此同时，高维数据分析技术也蓬勃发展。高维数据的本征维数估计问题研究，在高维 数据处理领域中有着重要的地位。对于高维数据处理领域，本征维数的寻求具有重要的 意义。在降维方法中，本征维数是一个需要我们去估计的未知量，准确的估计出高维数 据的本征维数，对接下来的降维处理问题有着重要的指导意义。并且，在数据处理过程 中，准确的本征维数估计对选取合适的邻域大小有很大的帮助，可以避免“维数灾难”。 本文提出一种新的方法一基于m l e 算法的本征维数估计算法。大多数情况下， 数据间的近邻关系能充分的反映数据的局部几何特征。m l e ( m a x i m u ml i k e l i h o o d e s t i m a t i o n ) 估计方法就是通过建立关于近邻间距离的似然函数，从而得到本征维数的 估计值。传统的m l e 方法存在两点不足：一是对同一个邻域内的不同样本点所估计出 的本征维数值，只是简单的求均值作为该邻域的本征维数，受奇异值的干扰较大；二是 在选取k 近邻时，采用传统的欧氏距离，容易出现越层现象。针对以上不足，本文采用 邻域平滑( n e i g h b o r h o o ds m o o t h i n g ) 方法替代原来的均值方法，求出更加可靠的本征维 数值；在选取k 近邻时，采用测地线距离代替欧氏距离，以找到真实的k 近邻点。 本文在模拟数据库和真实数据库上对该方法进行了实现，通过实验证明了改进后算 法的可行性和有效性，文章最后对算法的实验结果进行了分析，实验结果表明，这种新 的方法是有效的，可以估计出更为可靠的本征维数值。 关键字：本征维数；极大似然估计；邻域平滑；测地线距离 a b s t r a c t s i n c et h e2 0 t hc e n t u r y6 0 s ，t h er a p i dd e v e l o p m e n to fc o m p u t e rt e c h n o l o g yp r o v i d e sa p o w e r f u lt o o lf o rd e a l i n gw i t hc o m p l e xd a t a ，w h i c ha l s om a k e st h eh i g h - d i m e n s i o n a ld a t a a n a l y s i st e c h n i q u e sh a v ev i g o r o u sd e v e l o p i n g t h ei n t r i n s i cd i m e n s i o ne s t i m a t i o n o f h i g h - d i m e n s i o n a ld a t a ，i si m p o r t a n ti nt h ef i e l do fh i g h - d i m e n s i o n a ld a t ap r o c e s s i n g i th a sa v e r yh i g hi m p o r t a n c ea n du r g e n c yf o rf i n d i n gt h ei n t r i n s i cd i m e n s i o n i n t r i n s i cd i m e n s i o ni s a nu n k n o w nq u a n t i t yw h i c hn e e d st ob ee s t i m a t e df o rd i m e n s i o nr e d u c t i o na l g o r i t h m s ，i fw e c a nq u i t ea c c u r a t e l yf i n dt h ei n t r i n s i cd i m e n s i o no fh i l g h d i m e n s i o n a ld a t a , t h e r ew a sn o t d o u b tt h a tt h ef i g h td i m e n s i o ne s t i m a t i o nh a sa ni m p o r t a n tg u i d i n gs i g n i f i c a n c ef o rd i m e n s i o n r e d u c t i o na l g o r i t h m s t h ea c c u r a t ei n t r i n s i cd i m e n s i o ne s t i m a t i o na l s op r o f i tt os e l e c ta l l a p p r o p r i a t en e i g h b o r h o o ds i z ei nd a t ap r o c e s s i n gf o ra v o i d i n gd i m e n s i o n a l i t yc u r s e t h i sp a p e rp r o p o s e san e w a p p r o a c hf o ri n t r i n s i cd i m e n s i o ne s t i m a t i o nb a s e do nm l e ( m a x i m u ml i k e l i h o o de s t i m a t i o n ) g e n e r a l l y , n e i g h b o rr e l a t i o n s h i pc a na d e q u a t e l yr e f l e c t t h el o c a lg e o m e t r i cc h a r a c t e r i s t i c so ft h ed a t a m l em e t h o dc o n s t r u c t e dt h el i k e l i h o o d f u n c t i o nb e t w e e nt h ed i s t a n c e so fc l o s en e i g h b o r s ，t og e tt h em a x i m u ml i k e l i h o o de s t i m a t e i n t r i n s i cd i m e n s i o n t h et r a d i t i o n a lm l ea l g o r i t h m sh a st w os h o r t a g e ，o n ei st h a ti tj u s t s i m p l ym a k i n ga na v e r a g ef o rt h ei n t r i n s i cd i m e n s i o ne s t i m a t i o no fd i f f e r e n ts a m p l ep o i n t si n t h es a m en e i g h b o r h o o d ，w h i c hw i l lb es u b j e c t e di n t e r f e r e n c eb e c a u s eo fs i n g u l a rv a l u e ，t h e o t h e ri st h a ti tu s e se u c l i d e a nd i s t a n c et oo p t i o nt h ekn e i g h b o r s ，w h i c hl i k e l ya p p e a r e dl a y e r s p h e n o m e n o n i no r d e rt os o l v et h es h o r t a g e ，w eu s en s ( n e i g h b o r h o o ds m o o t h i n g ) a l g o r i t h m s i n s t e a do fm e a na l g o r i t h m s ，a n du s eg e o d e s i cd i s t a n c ei n s t e a do fe u c l i d e a nd i s t a n c et of i n d t h er e a lk - n e i g h b o rp o i n t sw h e nw es e l e c tk n e i g h b o r s w em a k et h ee x p e r i m e n to ns i m u l a t i o nd a t as e t sa n dr e a ld a t as e t s ，t h er e s u l t ss h o w e d t h a to u rm e t h o di se f f e c t i v e ，i tc a nf i n dm o r er e a s o n a b l ei n t r i n s i cd i m e n s i o n k e yw o r d s ：i n t r i n s i cd i m e n s i o n ； m a x i m u ml i k e l i h o o d e s t i m a t i o n ；n e i g h b o r h o o d s m o o t h i n g ；g e o d e s i cd i s t a n c e 目录 摘要i a b s t i 认c t i i 目录i i i 第一章引言1 1 1 本征维数估计方法背景知识1 1 2 本征维数估计方法的研究目的与意义2 1 3 本征维数估计方法的研究现状2 1 4 本文主要内容2 第二章本征维数估计方法分析4 2 1 包数方法4 2 1 1 相关概念4 2 1 2 基于包数的本征维数估计算法5 2 2k 一近邻图方法7 2 3 极大似然估计方法9 2 4 本章小结1 1 第三章基于m l e 的本征维数估计算法1 2 3 1 邻域平滑1 2 3 2 测地线距离1 2 3 3 算法实现与实验结果分析1 3 3 3 1 实验数据库1 3 3 3 2 实验结果分析1 4 3 4 本章小结1 8 第四章结束语1 9 4 1 总结1 9 4 2 展望1 9 参考文献2 0 致谢2 2 在学期间公开发表论文及著作情况2 3 i i i 东北师范大学硕士学位论文 第一章引言 1 1 本征维数估计方法背景知识 当代世界和人类社会中一直存在着大量的并且越来越多的复杂事物，一直以来，人 们都希望可以找出隐藏在这些复杂事物下的客观规律。计算机技术的飞速发展，为人们 观察和揭示这些复杂事物内部的客观规律提供了有力的工具。直到现在，人们仍在不断 的搜寻更有效的观察技术，仅仅是为了能够观察到复杂事物内部更丰富，更完整的信息。 科学技术的发展给人类带来了各种各样的海量数据，如航天数据，图像数据，生物数据， 气候数据，以及金融数据等，这些数据的表象都是高维的。比如对我们熟悉的天气情况， 可以用温度，湿度，气压，风力，风向，降雨量，辐射强度等作为描述气象特征的一 系列参数。通过这个例子我们可以引出高维数据的定义。一般来说，描述“某一现象 的多变量数据，即高维数据。很显然，随着数据维数的增加，数据可以提供更丰富，更 完整的信息。但是大幅度的提高数据维数会给随后的数据处理工作带来更大的困难。所 以对于很多问题来说，进行数据降维都是必要的，那么该怎样在复杂的数据内部找到数 据的本质规律? 这也是数据降维所要面临和解决的主要问题。 本征维数估计是用来克服“维数灾难 【l 】的有效手段之一。人们通过对离散数据集 合的分析，可以得到嵌入在高维数据空问中的本征低维流形【2 】，从而探求高维数据的本 质规律性。降维的基本原理是把高维数据投影到低维空间中，并把投影后的结果作为原 始数据的低维表示。 当然，降维是要承受一定代价的，不管通过什么样的投影来进行降维，都会造成高 维数据原始信息的损失。那么如何在最优的保持原始高维数据的本质特征规律的情况 下，来得到原始高维数据的最简低维表示，这就是高维数据处理的难点所在。也可以简 单理解为，要在尽量保持数据本质特征规律的条件下，找到一个所能降到的最低维数。 在很多领域中，进行数据降维是对数据后续处理的必须过程。 一直以来，人们没有给出本征维数一致的严格定义，通常情况下，大多数人接受这 样的定义：高维数据实际上是( 或者至少非常近似的) 位于一个维数比原始数据空间小 得多的非线性流形上，这个低维流形的维数就定义为此组高维数据的本征维数f 3 1 。在本 征维数估计过程中，因为我们用来估计本征维数的观察数据是位于高维空间中的有限个 离散向量，而这些观察数据是我们随机选取的，所以估计的结果往往受不同的人对实际 问题所运用的不同准则所影响。因此对于同样的数据集很有可能得出不同的估计结果， 在维数估计领域中。这是较为常见的现象。 东北师范大学硕士学位论文 1 2 本征维数估计方法的研究目的与意义 在高维数据处理领域中，本征维数的寻求具有重要意义。在降维方法中，本征维数 是一个需要我们去估计的未知量，准确的估计出高维数据的本征维数，对接下来的降维 处理问题有着重要的指导意义。并且，在数据处理过程中，准确的本征维数估计对选取 合适的邻域大小有很大的帮助，可以避免“维数灾难 。大多数情况下，先将高维原始 数据降维到一个大小合理的维数，并且还要尽量多的保留原始数据的有用信息，然后再 对降维后的数据进行一系列的处理工作，很多情况下这都是必须的过程。在当前的高维 数据处理研究领域中，本征维数的估计问题，与降维方法的研究问题，都是同等重要的 开放性课题。本文将主要研究本征维数估计问题。 1 3 本征维数估计方法的研究现状 高维数据处理问题的研究在国外开始的较早，发展的也较快，迄今已经有了较为系 统的理论体系，而目前国内学者关于这方面的研究正虽处于起步阶段，也取得了一定的 成果。其中本征维数估计问题的研究，是高维数据处理领域中的重要内容。 b e n n e t t ，r s 最初提出本征维数估计方法，他将全局p c a l 4 j 方法应用在线性数据上 来进行本征维数估计。在他的方法基础上产生了一系列基于p c a 方法的本征维数估计方 法，如b r u s k e 最佳拓扑等距映射【5 j 方法。这一类方法多少都了应用全局或局部p c a 方法 的思想，它们利用p e a 方法所计算出的协方差矩阵的特征值来做出估计，这类方法称之 为特征值方法。但基于p c a 的方法更适用于处理线性数据，对非线性数据的本征维数估 计效果不理想，所以针对非线性数据，出现了大量揭示数据的本征非线性几何结构的估 计方法，称之为几何方法。进入2 1 世纪以来，随着流形学习的不断进步，人们对本征 维数的提法有了更为深刻的认识，提出了包数方法【6 j ，熵估计方法【。7 1 ，t e n s o rv o t i n g 方法【8 】8 ，k 一近邻图方澍9 1 ，极大似然估计方法【1 0 l ，切割球方法【1 1 1 等一系列几何方法。 本征维数估计方法可以分为两大类：一类称为特征值方法：它们把d 维空间中的数 据通过适当的投影映射投影到低维空间，然后计算投影后数据的协方差矩阵的全体特征 值，并考察其中最重要的特征值的个数d ，最后把这个d 作为本征维数的估计值。另一 类称为几何方法：此类方法不需要对数据进行投影，而是直接考察高维数据的局部几何 特征，或者是利用数据点间的邻域结构信息，比如近邻关系等，运用相关的准则给出本 征维数d 的估计值。一般来说，特征值方法适用于线性数据，是全局的本征维数估计方 法，但对于非线性数据往往不能取得令人满意的结果。随着流形学习的发展，几何方法 因为其优越性越来越多的被大家接受。本文主要研究的就是本征维数估计方法中几何方 法。 1 4 本文主要内容 本文着重研究本征维数估计方法中的几何方法。并对其中的极大似然估计方法进行 2 东北师范大学硕士学位论文 了改进，实验证明了改进后算法的可行性与有效性。 文章的内容安排如下： 第一章引言 简要介绍了本征维数估计方法背景知识，阐述了本征维数估计方法的研究目的、意 义、国内外的研究现状，以及本文的主要内容和基本结构框架。 第二章本征维数估计方法分析 这一章对本征维数估计法所涉及到的一些几何方法进行了介绍，简单介绍了碎片形 方法，k - 近邻图方法等近年出现的算法，重点对极大似然估计方法进行了介绍和深入的 分析。 第三章基于m l e 的本征维数估计方法 本文的算法是在极大似然估计方法基础上实现的，主要阐述了极大似然估计方法的 不足之处，并结合了邻域平滑，测地线距离等方法，完成了对原有极大似然估计方法的 改进，通过实验证明了我们改进后算法的可行性与有效性。 第四章结束语 总结全文，归纳要点，对本文算法所存在的不足之处给出建议和展望。 3 东北师范大学硕士学位论文 第二章本征维数估计方法分析 如前所述，本征维数估计方法大致上可以分为两类特征值方法和几何方法。随 着流形学习的发展，特征值方法已经不适用于非线性的数据集，所以人们探求几何方法 来克服特征值方法的不足，几何方法立足于充分发掘数据集内在的几何特性，并且随着 流形学习的不断进步，人们对于本征维数的提法有了更为深刻的认识，提出了一些更为 贴切的本征维数定义，如相关维数，拓扑维数等。在此基础上，出现了包数方法，k 近邻图方法，以及极大似然估计方法等一系列几何方法，下面，详细介绍一下以上的这 些近期提出的几何方法。 2 1 包数方法 上文提到，本征维数严格一致的定义并没有被给出，所以在多数情况下，结合数学 知识和对数据的直观认识或者从实际目的出发，人们给出了适合自己的一些定义，以方 便理解与计算。最近几年，随着相关维数，拓扑维数的定义以及碎片形几何理论【1 2 】的提 出，人们提出了一种新的拓扑维数估计方法包数方法。 2 1 1 相关概念 包数( p a c k i n gn u m b e r s ) 方法是一种求解数据本征拓扑维数的方法。那么什么是拓 扑维数呢? 在介绍拓扑维数之前，先了解一下相关知识，介绍一下精致的概念，设x 为 拓扑空间，s x 是x 的一个子集，c 表示s 的一个开覆盖，则c 为c 的精致是指： 若c 也是s 的一个开覆盖，且对于c 中任一开集，总存在c 中某一开集包含之。了解 这些以后就可以给出拓扑维数的定义， 定义2 1 1 拓扑空间x 的某一子集s 具有拓扑维数d 物，如果对于s 的任一开覆盖 c ，都存在c 的一个精致c 7 ，满足，s 中每一点至多属于c 中的d 印+ 1 个开集，9 诈1 5 1 d 印 是这样的整数中最小的。 因为拓扑维数存在计算复杂度高，难以计算的缺点。所以，在实际情况中，我们并 不采用拓扑维数的定义，更多的时候人们都用其它维数来代替它。在几何方法中，大部 分几何方法都采用相关维数来估计本征维数。相关维数定义如下， 定义2 1 2 对于度量空间x 的某一有限子集s 。；扛1 ，一，工。) ，令相关度c ( r ) ， c ( ，) = ! 鳃志耄喜母, - x j - ：r ) ( 2 1 ) 其中，为指示函数，则相关维数定义为， 东北师范大学硕士学位论文 t l 枷i ml o l g 。c g ，( r ) ，4 ui n o ， ( 2 2 ) 当样本数是有限时，这个极限不能达到，所以该过程通常进行如下改进，可以以l o g c ( r ) 为纵坐标，l o g r 为横坐标，绘出关于这两个参数的一条曲线，然后我们就可以考察该条 曲线光滑部分的斜率型毕9 堕。得到近限相关维数定义如下， d 1 0 9 ， 定义2 1 3 有限子集s 。a 缸1 ，一，x 。) 的近限相关维数( s c a l e - d e p e n d e n tc o r r e l a t i o n d i m e n s i o n ) 定义为， 易一(，l，2)；一logc(r2)-logc(r) ( 2 3 ) l o g r 2 。l o g r l 并把它作为d 一的估计值，即本征维数的估计值。由流形知识我们知道d s d 泖， 然而，当流形上的概率密度为非均匀分布时，d 。会大大低于d 娜，这时会造成本征维 数的严重低估。我们采用容量维数来为了克服这种现象，在此之前首先介绍下相关知识， r 覆盖数( r c o v e r i n gn u m b e r ) 的概念，如下， 定义2 1 4 设( x ，d ) 为度量空间，d 为度量。则子集scx 的r - 覆盖数n ( r ) 定义为， n ( r ) 是可以构成s 的覆盖的开球b o 。，x ) = x e x d ( x 。，x ) ， 的最少个数。 定义2 1 5 度量空间x 的子集5 的容量维数( c a p a c i t yd i m e n s i o n ) 定义为， d 唧一l 圳i m 訾 ( 2 4 ) 容量维数最大的优点就是不依赖于流形上的概率分布。下面介绍的包数算法就是利用容 量维数来估计出本征维数，并且降低了其计算复杂度。 2 1 2 基于包数的本征维数估计算法 当s 是有限集时，计算其r 一覆盖数也很复杂。甚至很难实现，所以我们利用易于计 算的包数重新定义容量维数d 。来解决这个难题。假设( x ，d ) 是度量空间，yc x ，称 v 是r 一分离的，若y 中任意两个不同的点x ，y 满足d ( x ，y ) 苫，。则scx 的r 一包数m ( ，) 定义为s 的所有r 分离集的最大势。覆盖数与包数满足如下基本不等式 l v ( r ) sm ( r ) snr 1 2 ) 。 下面我们利用包数来得容量维数的新的定义， 定义2 1 6 度量空间x 的子集5 的容量维数( c a p a c i t yd i m e n s i o n ) 定义为， 东北师范大学硕士学位论文 - 一l m i m 警 ( 2 5 ) 当样本数是有限时，这个极限同样不能达到。与相关维数的做法类似，如下定义， 定义2 1 7 度量空间x 的有限子集s 。= 忸l 一，石) 的近限容量维数( s c a l e - d e p e n d e n t c a p a c i t yd i m e n s i o n ) 定义为， 刍唧“,r2)；一一logm(r2)-logm(q) ( 2 6 ) l 0 9 1 2 。i o g r l 我们注意到，一旦找到s 。一缸，z 。) 的m ( r ) ，s 。就等同于找到一个最大势的孤立点 集脚( g ，) 和图g ，e ) ，其中顶点集y s 。，边集e 。x i , x j ) p o ；，z ，) 2 ，1 s ，sm ，并且令口= 伽- r ) m ，则下列极限存 l i m 砉r ) d 一 一一* ，l 似一 7 d m 其中以， 是一个与( m ，g ) 和厂无关的常数。性质2 2 1 奠定了给出y 。= ，k ) 本征 维数估计方法的基础。要使得上述极限值为非零有限值，当且仅当通过选出合适的口， 使得当d = m 时，满足a = 仰- r ) m 。并且这个非零有限值是由m 上某密度，的r e n y i 口熵， 7 东北师范大掌硕士掌位论文 日( 厂) 一击1 0 9 j ：，。( ) ，) 肛。) ( 2 9 ) 上一口 ，m 。 决定的。 通过上述分析，得到本征维数的估计过程如下， 令z 。一l o g l ，上( y 。) ，由性质2 2 1 ，z 。可用下式逼近， f 。；al o g n + 6 + s 。( 2 1 0 ) 其中口一伽一r ) m ，bl o g f l , 。砧+ ，聊日，劫( ，) ，s 为方差。 令15 p ， ( 2 1 2 ) 占代入到公式( 2 1 0 ) d p ，就 ( 2 1 3 ) 这就是通过l 【- 近邻图方法求得本征维数估计的过程。 例2 2 1 如图2 2 所示，该数据为人工模拟数据库，分别包括s w i s sr o l l ( 本征 维数为2 ) 以及中心位于( 0 ，0 ，0 ) ，半径为5 ，的球( 本征维数为3 ) 组成。分别在s w i s sr o l l 上随机选取2 0 0 个样本点，在球上随机3 0 0 个样本点，应用4 一近邻图的方法对所选取的 5 0 0 个样本点做本征维数估计，并与m l e 方法做出对比。将结果以直方图的形式给出， 见图2 3 。 可以观察到，4 一近邻图方法与m l e 方法对数据的估计结果类似。并且，在4 一近邻 图的实验直方图中，有些数据点的维数被估计的过高。通过该实验可以看出，m l e 有过 低估计本征维数的趋势，而k 一近邻图方法却有过高估计本征维数的趋势。但通过实验相 对而言，k 一近邻图方法也能够给出很可靠的本征维数估计值。 8 东北师范大学硕士学位论文 图2 2 由s w i s sr o l l 与球组成的流形结构，其中黑色数据点 为s w i s sr o l l ，本征维数为2 ；蓝色数据点为球，本征维数为3 。 ( a ) 4 _ 近邻图方法 ( b ) m l e 方法 图2 3 禾近邻图方法与m l e 方法结果对比直方图 2 3 极大似然估计方法 一般来说，数据关系可以充分的反映数据的局部几何特征。极大似然估计( m l e ) 方 法就是通过建立近邻间距离的似然函数，来得到本征维数的极大似然估计的。 m l e 方法具体如下： 设x 1 一x 。是r d 空间中的随机采样样本，基本思想是对于取定的一个点x ，假设 在以x 为中心，r ( r 足够小) 为半径的球体足僻) 内密度f ( x ) 一常数。那么有下面的非 平稳过程 p ，工) ，0 s ts 埘， 9 东北师范大学硕士学位论文 著，s z ( f ) 】 ( 2 1 4 ) 显然，n ( t ，工) 是x 1 一，x 。落入球s ，0 ) 的样本个数，下面我们用平稳的泊松过程来 逼近这一过程。对于x 1 一，x 。，记瓦 ) 为z ，x 。中x 的第七个近邻到x 的距离，那 么有， ! 一f ( x ) v ( m ) 【瓦o ) r ( 2 1 5 ) 其中v ( m ) 表示肌维单位球的体积。则对于固定的f ，该泊松过程的参数为， a o ) = ，o 少 ) 所f ”1( 2 1 6 ) 则可以看出，a ( t ) 为该泊松过程的强度。记0 一l o g f ( x ) ，我们可以对泊松过程建立对数 似然函数【1 4 1 ， l ( m ，口) ；r l 。g a ( t ) d n ( t ) 一r a o 渺 ( 2 1 7 ) 对公式( 2 1 7 ) 应用极大似然方法，则有似然方程， 堕0 0 = r 科( f ) 一f a ( t ) d t ；( 尺) 一e 8 y 沏) 尺”一o ( 2 1 8 ) 面o l 。鬻p og y 蚪陋+ 器) _ 0 似缈 由公式( 2 1 8 ) ，( 2 1 9 ) 联立，可以解出， 矾叫志1 弘南i 仁2 。， 矾- l 丽荟1 0 9 南i g 2 0 ) 在实际计算中。取k - 邻域比取球形邻域方便的多，因此公式( 2 0 ) 变形为， 一b 1 荟k - i 焉】1 1 ， 对于取定的七，将x 遍历工，x 。，就可以得到咒个局部本征维数的估计值，对这些估 计值取平均就可以得到全局的本征维数，；l 。；为了得到更加准确的全局本征维数疡，我 们选取对一定范围k 重复上述过程，即， 小丢毫懈；，豌= 南驴k 2 仁2 2 ， 疡就是我们通过m l e 方法，估计出来的本征维数。 例2 3 1 如图2 4 所示，图2 4 ( a ) 表示，对于模拟的5 维标准正态分布，随机选取样 本数不同的四组样本，分别为2 0 0 ，5 0 0 ，1 0 0 0 ，2 0 0 0 ，分别计算每组样本的本征维数值， 东北师范大学硕士学位论文 尼的取值范围为七= 4 ，5 ，1 0 0 ，观察到，当选择的k 较小时，所估计的本征维数严重偏 离真实维数，当七达到2 0 左右时，估计出的本征维数值比较接近真实维数。可见k 的选 取对本征维数估计的准确性影响很大。样本个数也是影响本征维数估计准确性的一个因 素，可以看出，样本数越多，估计出的结果越稳定。这是符合现实规律的，因为样本数 越多，所含有的信息就会越多。图2 4 ( b ) 显示的是，对m 维标准正态分布，( m 分别取 2 ，5 ，1 0 ，2 0 ) ，分别随机选取样本数均为1 0 0 0 的样本，采用m l e 方法估计本征维数， m l e 只能在t n 较小时给出可靠的本征维数。一般的，m l e 更适用于ms8 的情况。 l 园j ( a ) 样本数不同的5 维数据 ! 罔i r n - 5 ll 一_ 一- p ，u l li t l竺! 广一 。 。- _ - - - 。- 。： t - 。一。一一一一一 l ( b ) 样本数为1 0 0 0 的不同维数据 图2 4 m l e 估计方法实验结果 2 4 本章小结 本章对目前的本征维数估计方法进行了总结和分析，主要介绍了几何方法中的包数 算法，k - 近邻图方法，以及极大似然估计方法。同时还有些其他本征维数估计方法，比 如切割球方法等未能列入本文。通过实验可以看出，m l e 估计方法无论从计算的简易 性上，还是在性能上，都是比较优秀的。本文前面曾经提过，这些本征维数估计方法的 产生并不是直接从理论上进行推导的，而是在解决具体问题时发现的。随着现在高维数 据的处理越来越多，肯定会出现新的更有效的本征维数估计方法，相信本征维数估计课 题会有更美好的前景。 嚣薹l c童譬馨羞眷 东北师范大学硕士学位论文 第三章基于m l e 的本征维数估计算法 上文中曾经提出，m l e 方法存在一定的不足，主要包括两个方面：第一，对同一 个邻域内的不同样本点所估计出来的本征维数值，只是简单的求均值来获得本征维数， 导致估计的结果受奇异值影响较大；第二，在选取k 近邻时，采用的是传统的欧氏距离， 容易出现越层现象，选择到错误的近邻。针对以上两点不足，本文提出了改进的办法， 首先用邻域平滑方法代替原始的求均值方法，减小现实中奇异值问题所带来的干扰；并 且，用更适合于描述复杂结构的测地线距离代替欧氏距离，以减少出现错误近邻点的可 能。最后将对算法的实现进行介绍，并对算法的实验结果进行分析。 3 1 邻域平滑 在采用m l e 方法估计本征维数的过程中，我们在m l e 方法中加入邻域平滑 ( n e i g h b o r h o o ds m o o t h i n g 简称n s ) t 1 5 】的思想。邻域平滑思想是基于这样的假设的，位于 同一个邻域中的样本点，应该位于同一个子流形上，它们有着最相似的几何特性，所以 也就应该具有相同的本征维数，所以采用一个投票机制来代替简单的均值方法，该投票 机制的具体过程为，对同一个邻域内所有样本点所估计出的本征维数值，都给它们赋予 一个概率，概率的大小定义为该数值在整个邻域内出现的次数与整个邻域内样本点个数 的比值，选取概率最大的数值作为整个邻域的本征维数。即， ，；l = a r g m a x p n f 陋= _ j ( 3 1 ) j 其中刚；为样本；所对应的概率值，j 为样本m 所对应的本征维数估计。 3 2 测地线距离 测地线距离，定义为流形上两个数据点间的最短距离。它描述的是流形上两个样本 点之间在几何特征下的真实距离。通过测地线距离，我们能够找到流形上样本点间的真 实就近邻关系，不会出现越层现象。如图3 1 所示，该图为一个s w i s sr o l l 模型，其中 用红色菱形所标记的样本点为k 近邻中心，我们要在这个流形上找到该样本点的k 一近 邻，用黑色十字标记的样本点表示找到的该中心的k 近邻点。 例3 2 1 图3 1 ( 曲显示的是采用传统的欧氏距离所找到的k 近邻点，图3 1 ( b ) 显示 的是采用测地线距离所找到的k 近邻点。可以看出，图3 1 ( a ) 中出现了越层现象，找到 的并不是真实的k 近邻点，而图3 1 ( b ) 中找到的k 近邻点才是正确的。通过这个例子可 以看出，测地线距离更适合于在流形中寻求k 近邻点。 东北师范大学硕士学位论文 麓 、：蔓 t 一、一 口 _ ，o 1 ( a ) 欧氏距离k 近邻点 麓 簿未 图3 1 欧氏距离与测地线距离选择邻域对比图 3 3 算法实现与实验结果分析 本文对传统的m l e 方法进行了改进，在m l e 方法中，结合了邻域平滑以及测地线 距离两种思想，提出了邻域平滑m l e ( n s m l e ) ，测地线距离m l e ( d m l e ) ，领域平滑测 地线距离m l e ( n s d m l e ) = 种改进后的本征维数估计方法。并在大量的人工模拟数据集 以及真实的数据库上进行了实验，证明了三种方法的可行性。 3 3 1 实验数据库 本文的数据库分为两部分，一部分是模拟数据库，另一部分是真实数据库。其中模 拟数据库包括：s w i s sr o l l ，t w i np e a k s ，g a u s s i a n ，sc u r s e 和p u n c t u r e ds p h e r e 等共5 个数 据集，见图3 2 。对于以上5 个数据集，我们选择的样本数均为n ；2 0 0 0 。并且我们已 经知道，这5 个数据集的本征维数均为2 。真实的数据库包括：h a n dr o t a t i o n 数据库以 及i s o m a pf a c e s 数据库，见图3 3 。其中h a n dr o t a t i o n 数据库中共包含4 8 1 张人手图片， 每张图片大小为4 8 0 x 5 1 2 ，且知其本征维数为1 ；i s o m a pf a c e s 数据库中共包含6 9 8 张 人物石膏脸图片，每张图片的大小为6 4 6 4 ，且知其本征维数为3 。 ( a ) s w i s sd a t as e t s 1 3 c o ) t w i np e a k sd a t as e t s 东北师范大学硕士学位论文 ( c ) g a u s s i a nd a t a s e t s ( e ) p u n c t u r e ds p h e r ed a t as e t s 3 3 2 实验结果分析 ( d ) s _ c l l i s ed a t as e t s 图3 2 人工模拟数据库 霸网黑喇霸 _ 幽豳瞄幽 日目曰图圆 图3 3 真实实据库，上方为h a n dr o t a t i o n 数据库， 下方为i s o m a pf a c e s 人脸数据库。 为了证明本文提出方法的可行性和有效性，本文分别在模拟数据库与真实数据库上 与m l e 方法做了对比实验。实验结果见图3 4 ，及图3 5 。其中，横坐标表示的是k 值， 纵坐标，；l 表示的是所估计出的本征维数值。 1 4 东北师范大学硕士学位论文 ( a ) s w i s s d a t as e t s 实验结果图 ( b ) t w i np e a k sd a t a t s 实验结果图 1 5 东北师范大学硕士学位论文 ( c ) g a u s s i a nd a t as e t s 实验结果图 ( d ) s c u r s ed a t as e t s 实验结果图 1 6 东北师范大学硕士学位论文 ( e ) p u n d u r e ds p h e r cd a t a t s 实验结果图 图3 4 人工模拟数据库实验结果图 h a n dr o t a t i o n 数据库实验结果 东北师范大学硕士学位论文 ( g ) i s o m a pf a c e s 数据库实验结果图 图3 5 真实数据库上实验结果图 从实验结果可以看出，无论是在模拟数据库上还是在真实数据库上，本文提出的方 法都可以比较可靠的估计出本征维数值。相对于m l e 方法，在本文的三种改进方法中， n s m l e 方法一直能起到很好的效果，而d m l e 与n s d m l e 在整体上表现还是不错的， 但在个别数据集上不够稳定，不能令人完全满意。 3 4 本章小结 本章首先对m l e 方法的不足进行分析，然后提出了针对性的解决策略，引入了邻 域平滑和测地线距离的思想。结合m l e 方法，提出了n s m l e ，d m l e ，n s d m l e 三 种本征维数估计算法，通过在模拟数据库与真实数据上对比实验证明，本文提出的基于 m l e 方法的改进算法是比较成功的。 1 8 东北师范大学硕士学位论文 第四章结束语 4 1 总结 本征维数估计方法研究是高维数据处理领域中的一个重要课题，不仅仅对降维问题 有着指导作用，而且也是揭示高维数据内部特征结构的重要手段。有着重要的研究意义 与研究价值。 极大似然估计方法是本征维数估计领域中的重要方法，它不仅仅易于计算，并且又 能有效的估计出本征维数，在本征维数估计领域中有着广泛的应用。 本文提出一种新的方法，将邻域平滑与测地线距离思想引入m l e 中，通过在人工 模拟数据库与真实数据库上的对比实验表明，本文提出的方法可以得到更为准确本征维 数估计。 4 2 展望 本文是对本征维数估计方法的初步研究，在m l e 的基础上，进行了一些改进以获 得更可靠的本征维数估计值。取得了一定的效果。 由于本征维数估计方法往往是在实际问题中发现的，这就要求我们要不断的去探索 高维数据的内部特征结构，针对实际问题，探索新的更有效的估计方法。随着信息时代 的飞速发展，对高维数据的处理已经越来越多，这就要求人们对已有的本征维数估计算 法进行总结和概括，抽象出本征维数估计方法的共性，在更高层次上建立估计理论，在 理论和实践两个方面共同推动高维数据本征维数估计领域的发展。 相信在今后的研究中，随着技术的发展和算法研究的深入，本征维数估计问题会有 更加广阔的前景，在高维数据处理领域中会得到更广泛的应用。 1 9 东北师范大学硕士学位论文 参考文献 【1 】r b e l l m a n a d a p t i v ec o n t r o lp r o c e s s ：ag u i d e dt o u r p r i n c e t o