（计算机应用技术专业论文）非线性维数约减算法中若干关键问题的研究.pdf

中文摘要 维数约减是处理多维数据的一个重要步骤，是机器学习中的一个重要研究课 题，尤其是非线性维数约减技术已经成为机器学习中的一个研究热点。本文针对 非线性维数约减算法中的若干关键问题进行了研究。 首先，分析和比较了基于应力函数的评价模型、基于剩余方差的评价模型和 基于d y - d x 表示法的评价模型，提出了一种基于距离比例方差的评价模型。实 验结果表明，利用该模型不但可以评判同一算法在不同参数下的映射效果，而且 可以比较不同算法之间的嵌入质量。同时还讨论了如何利用应力函数、剩余方羞 和距离比例方差来确定邻域参数和低维空间的维数。 其次，研究了增量式非线性维数约减算法问题，通过改进增量式i s o m a p 算法得到了基于距离保持的增量式算法，提出了基于拓朴保持的增量式算法和基 于k 近邻投影的增量式算法，这三种算法都可以较为中肯地将训练集之外的样本 映射至帅维空间中。理论分析和实验结果表明，基于距离保持的增量式算法具有 较好的映射质量，基于拓朴保持的增量式算法具有较高的效率，但它们都只是对 i s o m a p 算法的扩展。而基于k 近邻投影的增量式算法同时具有较好的映射质量 和较高的计算效率，而且可以作为任一种非线性维数约减算法的扩展。对于含噪 声的数据，由于新样本的低维嵌入与训练集的低维坐标无关。基于拓朴保持的增 量式算法对噪声不太敏感。而其他两种算法只要在映射训练样本时较好地处理了 噪声，就可以忽略噪声的影响。 最后，本文讨论了非线性维数约减算法在分类和聚类中的应用。在指纹 分类和文本分类中的实验结果表明，通过结合非线性维数约减算法和分类技 术，在保证分类精度的前提下，极大地提高了分类算法的执行效率，降低了 分类算法的空间需求。对聚类算法的实验结果表明，基于非线性维数约减的 聚类算法可以发现任意形状的类，聚类质量明显优于k 均值算法的聚类结果。 关键词：非线性维数约减，评价模型，增量式算法，分类，聚类 a b s t i 溘c t d i m e n s i o n a l i t yr e d u c t i o ni so n eo ft h em o s ti m p o r t a n tr e s e a r c ht a s k si nm a c h i n e l e a r n i n g w h i c hi s as i g n i f i c a n tp r o c e d u r et od e a lw i t hm u l t i - d i m e n s i o n a ld a t a p a r t i c u l a r l y , 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 o r lt e c h n i q u e sh a v e b e e na f o c u s e dr e s e a r c hf i e l d i nt h i sp a p e r , af e wk e yi s s u e si nn d r a l g o r i t h m sa l es t u d i e d f i r s t l y , w ea n a l y z ea n dc o m p a r et h r e ee v a l u a t i o nm o d e l s ：b a s e do nt h es t r e s s f u n c t i o n ，b a s e do nt h er e s i d u a lv a r i a n c ea n db a s e do nd y - d xr e p r e s e n t a t i o n a n e v a l u a t i o nm o d e lb a s e do nt h ev a r i a n c eo fd i s t a n c er a t i o si sp r o p o s e d e x p e r i m e n t s i l l u s t r a t et h a tt h i sm o d e ln o to n l yc a ne v a l u a t er e s u l t sf r o mt h es a m ea l g o r i t h mw i t h d i f f e r e n tp a r a m e t e r s ，b u ta l s oc a nc o m p a r er e s u l t sf r o md i f f e r e n tm e t h o d s m o r e o v e r , i t i sd i s c u s s e dh o wt ou s et h es t r e s sf u n c t i o n , t h er e s i d u a lv a r i a n c ea n dt h ev a r i a n c eo f d i s t a n c er a t i o st os e l e c tt h en e i g h b o r h o o dp a r a m e t e ra n dt h ed i m e n s i o no ft h el o w d i m e n s i o n a ls p a c e s e c o n d l y , f o rt h ei n c r e m e n t a la l g o r i t h mi s s u e , w eo b t a i na ni n c r e m e n t a la l g o r i t h m b a s e do nd i s t a n c ep r e s e r v i n g ( i a d p ) b yi m p r o v i n gt h ei n c r e m e n t a li s o m a pa n d p r e s e n t a ni n c r e m e n t a l a l g o r i t h mb a s e do nt o p o l o g yp r e s e r v i n g ( i a t p ) a n da n i n c r e m e n t a la l g o r i t h mb a s e do nkn e a r e s tn e i g h b o rp r o j e c t i n g ( i a k n n p ) t h e yc a na l l p e r t i n e n t l ym a po b j e c t so u t s i d et r a i n i n g s e t si n t ot h ee m b e d d e ds p a c e t h e o r e t i c a l a n a l y s i sa n de x p e r i m e n t ss h o wt h a tr e s u l t sf r o mi a d pa r eb e t t e rw h i l et h ee f f i c i e n c y o fi a t pi sh i g h e r h o w e v e r , t h e ya r eb o t ho n l ye x t e n s i o n so fi s o m a p i a k n n pi sa g e n e r a l i z a t i o no fa n yn d rm e t h o db e s i d e sw i t l lb e t t e rr e s u l t sa n dh i g h e re f f i c i e n c y f o rt h ee m b e d d e dc o o r d i n a t e so fn e wd a t aa r ei r r e l a t i v et ot h ee m b e d d i n g so ft r a i n i n g s e t s ，i a t pi si n s e n s i t i v et on o i s e f o rt h eo t h e rt w om e t h o d s ，t h ee f f e c tc a nb ei g n o r e d w h e nn o i s ei nt r a i n i n gs e t si sp r o p e r l yt r e a t e d l a s t l y , i ti sd i s c u s s e dt oa p p l yn d rt e c h n i q u e st oc l a s s i f i c a t i o na n d c l u s t e r i n ga n a l y s i s e x p e r i m e n t s i n f i n g e r p r i n t a n dt e x t c l a s s i f i c a t i o n s d e m o n s t r a t et h a tt h ee f f i c i e n c yo fa l g o r i t h m si si m p r o v e da n dm e m o r y r e q u i r e m e n t s a r er e d u c e du n d e rw i t h o u tl o s so ft h ea c c u r a c yb yc o m b i n i n gn d r a l g o r i t h m sw i t h c l a s s i f y i n gt e c h n i q u e s e x p e r i m e n t si nc l u s t e r i n ga n a l y s i s i n d i c a t et h a tt h e c l u s t e r i n ga l g o r i t h mb a s e do nn d rm e t h o d sc a l lf i n dc l u s t e r sw i t ha n ys h a p e a n dr e s u l t sa r es u p e r i o rt ot h o s ef r o mk m e a n sa l g o r i t h m k e yw o r d s ：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 , e v a l u a t i o nm o d e l ，i n c r e m e n t a l a l g o r i t h m s ，c l a s s i f i c a t i o n ，c l u s t e r i n g 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得墨盗盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：乃i l 氩 醢 签字日期： d 6 年1 月2 7 日 学位论文版权使用授权书 本学位论文作者完全了解墨鲞盘茎有关保留、使用学位论文的规定。 特授权鑫鲞盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：研函缸 导师签名： a 可丞庑 签字日期： p 6 年1 月1 日 签字目期： d 6 年2 月2 7 同 第一章绪论 i 1 选题背景 第一章绪论 在当今的信息时代，随着计算机应用及互联网的日益普及，人类对科学和 社会问题的研究变得更加地复杂和庞大，有效地收集与分析数据以便从中提取信 息和获取知识变得越发地须臾不可离。而且随着数据采集技术的不断提高，人们 对于数据的获取变得越来越容易，数据正在里爆炸式增长。为了从堆积如山的 数据中获取有用的信息和知识，人们必须对其进行加工处理，由此催生了大 量的数据处理方法，如归纳、分类、聚类等，并已经取得了巨大的成就。然 而，计算机所处理的数据均来自于现实世界，由于现实世界中事物的复杂性， 使得获得的数据的结构变得越来越复杂，突出表现就是数据的属性很多或维数 很高，经常高达数千乃至数万维。例如： d n a 微阵列数据：微阵列( m i c r o f l r r a y ) 是生物学中的一项突破性 技术，它可以同时对单个细胞样本中的基因进行定量研究。在d n a 微阵列数据中，每行代表一个基因，每列代表一个样本。由于细胞 中基因的个数数千甚至数以万计，如果把每个样本看作是高维空间 中的一个点，那么这一空间的维数将达数千甚至数万。 - w e b 文档数据：在信息检索领域中，经常用向量空间模型来表示文 档。在向量空间模型中，每个文档被表示成一个特征词向量，向量 中的每个元素表示某个特征词在该文档中出现的频率或对该文档的 贡献。向量空间模型中的特征词经常达到数万甚至数十万个，也就 是说表示文档的向量通常会达到数万甚至数十万维。 一图象数据：在图象识别中，处理的数据通常是珊x n 大小的灰度图象。 如果把每幅图象看作是图象空间中的一个点，那么该空间的维数将 是m h 维。例如，当e = n = 6 4 时，维数将达4 0 9 6 。 _ 购物篮数据：购物篮数据指零售商业中客户所购商品的交易数据，记 录客户的交易记录，一个客户的一次购物行为就是一个交易数据。在交 易数据库中，每列代表一种商品，每行代表一个客户的一次购物行为。 第一章绪论 通常商品的种类都非常地多( 几千一几万种) ，如果将购物篮数据看作 是以商品种类为维、以交易数据为记录的多维数据，那么购物篮数据将 是一种维数为数千甚至数万的高维数据。 面对如此复杂的数据，一方面，并非所有的属性对随后进行的数据处理 都是重要的、有意义的，高维数据可能会大大增加机器的处理时间而仅产生 与维数小得多的数据相近的结果。另一方面，研究发现高维数据的特性完全不 同于低维数据，数据维数的大幅度提高给随后的数据处理工作带来了前所未有的 困难，产生了所谓的“维数灾难”问题。因此，必须寻求一种处理高维数据 的新方法。由于高维数据中的信息往往主要包含在一个或几个低维结构中，因此 可以首先将数据的维数降低到一个合理的大小，然后再将降维后的数据进行处 理。目前，数据降维即数据维数约减方法尤其是非线性维数约减方法已经成 为机器学习中的一个研究热点，其目的是找出隐藏在高维数据中的低维结 构，获取有意义且便于理解的低维表示。维数约减较为中肯地把握了人类归纳学 习和抽象思维过程的形式特征。 1 2 维数约减的概念 数据维数约减是指通过线性或非线性映射将样本从高维空间映射到个低 维空间中，从而获得一个关于原数据集紧致的低维表示的过程。一方面，利用维 数约减技术，可以得到数据在低维空间中的可视化投影，从而发现数据集的聚类、 空间分布等结构特性。另一方面，维数约减技术也可以作为一种数据预处理技术， 将高维数据转换成更易处理的低维数据。数据维数约减问题基于这样的基本假 设：高维数据实际上或者说至少是非常近似地存在于一个维数比原空间的维数小 得多的流形上，维数约减的目的就是获得这一流形的低维坐标表示p 】。例如，图 1 - l ( a ) 中的h u r r i c a n e 数据集 4 1 ( 5 0 0 个数据点) 和图1 - 2 ( a ) 中的s w i s sr o l l 数据集 5 1 ( 1 0 0 0 个数据点) ，它们实际上分别位于图1 - l ( b ) 中所示的一维流形和图1 - 2 c o ) 中所示的二维流形上。 设集合x = i l ，x 2 ，x ，) 是高维空间r d 中的一个d 维样本集，集合 y = y l ，y 2 ，y _ ) 是d ( d “d ) 维空间r 4 中的一个数据集，维数约减问题的定 义如下【3 】： 定义1 1 设f 是x 叶y 的一个映射，f 是y x 的一个映射，如果它们满足： 第一章绪论 1 ) 对任意f ，y l = f ( x f ) ，i ：f i f t y f ) ，f ；l 2 ，； j v 2 ) 以，i ；) 最小，巩) 是欧式距离 t = l 则称f 是数据集x 到y 的一个维数约减映射。 ( a ) 三维数据 ( b ) 一维流形 图1 1 包含5 0 0 个样本的h u r r i c a n e 数据集的三维分布和一维流形 ( a ) 三维数据( ”二维流形 图1 2 包含1 0 0 0 个样本的s w i s sr o l l 数据集的三维分布和二维流形 根据维数约减映射形式的不同，数据维数约减可以分为线性和非线性两类。 一种情况是f 为线性映射，此时称为线性维数约减算法，如主成分分析法、因子 分析法和经典多维标度变换法等；另一种情况是f 为非线性映射，即非线性维数 约减算法，如等距特征映射法、局域线性嵌入法，拉酱拉斯算子特征映射法和自 组织等距嵌入法等。 第一章绪论 1 3 国内外研究现状分析 数据维数约减是处理多维数据的一个重要步骤，是机器学习中的个重要研 究课题，已经在诸多科学和技术领域中得到了成功的应用。目前，已经有许多种 维数约减算法，而且这一研究领域仍然在不断的发展之中。可以从不同的角度对 维数约减算法进行分类，如果从处理的数据的性质角度考虑可以将维数约减算法 分为线性的和非线性的，如果从算法的执行过程看可以分为基于特征值求解的方 法和迭代方法，如果从几何结构保持的角度考虑可以分为全局算法和局部算法。 本文按照处理的数据的性质进行分类，即将维数约减算法分为线性和非线性两大 类。 目前，线性维数约减算法仍旧是数据分析中使用最为广泛的降维方法，主要 包括主成分分析法( 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 ) 、因子分析 法( f a c t o ra n a l y s i s ，缩写为f a ) m 和经典多维标度变换法( c l a s s i c a l m 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 ) ”等。主成分分析法是由h o t e l l i n g 于1 9 3 3 年提出的，又被称为h o t e l l i n g 变换，其基本原理是许多高维数据中的 大多数变量经常能用少数几个隐变量来解释。在主成分分析法中，低维空间由高 维数据的协方差矩阵的最大的p 个特征值对应的特征向量确定。因子分析法起源 于2 0 世纪早期一些学者对智力的定义和测定问题的研究。因子分析的目的是用 几个潜在的但不能观察的随机量去描述许多变量之间的协方差关系，这些随机量 称为因子。经典多维标度变换法的目标是将原始高维数据映射到一个低维空间 中，使得由维数减少而引起的任何几何变形都保持最小，也就是尽可能地保持所 有的点对间的距离或相似性。如果使用欧式距离，那么度量性m d s 和p c a 是等价 的。m d s 传统上用于高维数据的可视化。 这些线性维数约减算法具有实现简单、计算效率高等特点，并且能够保证发 现嵌入在高维输入空间中的线性子空间上的数据集的真实的几何结构口】。这些优 点也正是线性算法得到广泛应用的原因。然而，这些方法都有一个基本的假定： 数据处于高维空间中的一个线性或几乎线性子空间中。显然，这种假设太严格了， 因为来自现实世界中的许多数据都是非线性的。 为了处理非线性数据，人们分别从不同的角度对线性技术加以改进，提出了 各种不同的改进算法。这些算法主要从以下几个角度对线性算法进行了改进。 第一章绪论 第一，从局部线性重构全局数据的角度出发，将全局非线性转换为局部线性， 通过组合局部线性来表达全局信息，即混合局部线性的方法，如文献【9 - 1 6 。这 类算法认为非线性高维数据是局部线性的，先为局部区域学习一个线性模型，然 后再将这些局部线性模型组合成一个全局维数约减模型。然而这些算法有几个共 同的缺点：首先，这类算法必须面对的一个问题是如何将从局部线性模型中获得 的低维坐标组合在个一全局的低维坐标系统中；其次，由于大多数算法都使用 聊( e x p e c t a t i o nm a x i m i z a t i o n ) 算法进行学习，不可避免地会陷入局部极小；再 有，这些算法的计算效率都不高，同时有些算法还要求较多的自由参数。 第二，从核函数的概念出发，得到了核主成分分析法( k e r n e lp c a ，缩写为 k p c a ) 【m 。在核主成分分析法中，不再直接对原始的高维数据进行降维，而是先 用一个非线性核函数将原始数据映射到一个更高维的线性特征空间中，随后在该 特征空间中执行p c a ，从而得到数据的嵌入坐标。在算法的实际实现中，并不真 正将原始数据映射到特征空间中，只是计算核函数的点积，因此大大地简化了计 算。核函数可以是线性函数、多项式函数、径向基函数、或者s i g m o i d - 函数等， 使用不同的核函数，就可以得到不同形式的核主成分分析法。尽管核主成分分析 法可以较好地处理非线性数据，然而在实际使用时面对不同的问题如何选择核函 数仍然是一个难题，需要对多个不同的核进行比较。 最后，将白组织神经网络和线性技术结合起来处理非线性数据，曲线主成分 法( c u r v i l i n e a rc o m p o n n e ta n a l y s i s ，缩写为c c a ) “8 是其中典型的算法。 该方法先用竞争学习算法啪1 得到数据的拓朴结构，再将输入数据映射到低维空间 中。在学习高维数据的低维坐标时使用了一个新的目标函数和快速的迭代方法。 学习低维坐标的过程可以简单认为是c m d s 的一个迭代版本，只是目标函数不同 而已。尽管c c a 宣称与其他的c m d s 迭代版本”不同，可以避免局部极小，但并 没有从理论上证明这一点。 最近几年，出现了一类新的非线性维数约减技术：流形学习算法，它包含了 一个非常活跃的研究领域，引起了越来越多的研究者的兴趣。它们不再是对线性 算法的简单的改进和补充，而是从一个全新的角度来解决高维数据的降维问题， 它们强调算法的简单实现且避免局部极小的优化问题的困扰。比较典型的算法有 等距特征映射法( i s o m e t r i cf e a t u r em a p p i n g ，缩写为i s o m a p ) 瓯”、局域线性 嵌入法( l o c a l l yl i n e a re m b e d d i n g ，缩写为l l e ) 。2 5 1 、拉普拉斯算子特征映 第一章绪论 射法( l a p l a c i a ne i g e n m a p s ) ”圳等。 i s o m a p 算法是c i d s 算法的推广，是一种将p c a 和c m d s 结合起来的全局优化 算法。i s o m a p 算法的基本思想是用测地线距离( 测地线是曲面上每个点的曲率都 为零的一条曲线，曲线上两点间的距离即为测地线距离。它代表了两点在流形上 的实际距离。例如我们在地面上以直线行走，实际上走的是地球球体表面的大圆 上的一段弧，这段弧就是测地线。这是地球表面最接近直线的轨迹。) 代替欧式 距离，试图保持数据的内在的几何特性。算法的关键是估计数据点之间的测地线 距离。为了计算点间的测地线距离，需要在高维空间建立数据点的邻域图，图中 每个点只与距离其最近的七个点或某个邻域半径，内的所有点连接。对于邻域点， 可由输入空间直接得到其测地线距离；对于非邻域点，其测地线距离可以用邻域 图上两点间的最短路径来近似。c d a ( c u r v i l i n e a rd i s t a n c ea n a l y s i s ) ”1 则将 测地线距离的概念引入了c c a 算法中，可以认为是i s o j f a p 算法的一个迭代版本。 l l e 算法通过捕捉复杂的嵌入流形的局部几何特征来得到一个全局的低维坐 标表示。l l e 算法的基本假设是每个数据点和它的邻居点位于流形的一个线性或 几乎线性区域中，在这样的基本假设下将全局非线性转化为局部线性，而互相重 叠的局部邻域能够提供全局结构的信息，从而得到一个低维全局坐标表示。实际 的嵌入计算可以简化为求解一个稀疏矩阵的特征向量问题。 l a p l a c i a ne i g e n m a p s 算法是基于谱图理论( s p e c t r a lg r a p ht h e o r y ) 。1 的算 法，它将从数据集得到的图形拉普拉斯算子近似为流形上的拉普拉斯一贝尔特拉 米算予( l a p l a c e b e l t r a m io p e r a t o r ) 。该算法首先构造一个邻域图，图中每个 点只与距离其最近的尼个点或某个邻域半径，内的所有点连接，接着图中所有边 的权值用热核方程确定或简单地标记为1 ，最后通过求解一个推广的特征值问题 得到数据的低维表示。 这些流形学习算法都是通过求解一个特征值问题来得到数据的低维表示，不 仅算法实现简单，而且能够确保发现隐藏在高维数据中的非线性流形，同时也避 免了困扰迭代算法的局部最优问题。这些算法的出现引起了许多学者的极大兴 趣，对它们从不同的角度进行了分析和总结，并提出了许多种改进算法。1 ，这 些算法主要在计算效率、对噪声敏感性等方面进行了改进。例如，文献 4 2 和 4 3 中将这些非线性算法解释为核p c a 的扩展，为基于特征值求解的流形学习算法建 立了一个统一的模型。基于标志点的m d s 算法( l a n d m a r km d s ，缩写为l m d s ) ”1 、 第一章绪论 基于拓朴保持网络的非线性维数约减算法( t o p o l o g yr e p r e s e n t i n gn e t w o r k s ， 缩写为t r n ) o ”和随机相似嵌入算法( s t o c h a s t i cp r o x i m i t ye m b e d d i n g ，缩写 为s p e ) 畹1 都在计算效率方面对i s o m a p 算法进行了改进。l 鼢s 通过仅仅保持每 个点到一些标志点的测地线距离来降低算法的时间和空间复杂度。t r n 通过竞争 规则得到数据的拓朴结构，在拓朴结构上执行i s o m a p 算法，从而加速了算法 的执行速度。s p e 基于一个点到另一个点的测地线距离总是大于欧式距离这样的 事实，利用自组织算法仅仅保持每个点到其邻域内的点的距离，避免了测地线距 离的计算，极大地降低了算法的时间复杂度。局部保持投影( l i n e a rp r e s e r v i n g p r o j e c t i o n ，缩写为l p p ) 利用局部线性改进了拉普拉斯算子特征映射法。局 部不变投影通过结合l l e 算法和l a p l a c i a ne i g e n m a p s 算法，既保持了数据的 几何结构，又保持了数据的拓朴结构。而自组织等距嵌入法( s e l f - o r g a n i z i n g i s o m e t r i ce m b e d d i n g ，缩写为s i e ) 结合了i s o m a p 算法和自组织算法的优势，回 避了特征值问题的计算，不但提高了算法的执行效率，而且降低了对噪声数据的 敏感性，但s i e 算法容易陷入局部极小和引起过适应问题。 与线性技术及其改进算法相比，尽管这些非线性维数约减算法及其改进算法 都可以较好地发现隐藏在高维数据中的低维嵌入，然而它们都面临着一些共同的 问题： 第一，非线性维数约减算法的嵌入质量的评价问题。由于高维数据的不直观， 使得对不同非线性维数约减方法进行分析和评价比较困难。m d s 算法中使用的应 力函数和i s o m a p 算法中使用的剩余方差都可以用来衡量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 s 算法， 更无法对各种算法的性能进行比较。c c a 算法和c d a 算法中使用的d y d x 表示法 “4 嘲，尽管形象直观，但缺乏量化指标。因此为了对各种非线性维数约减算法的 嵌入性能进行评价，非常有必要建立非线性维数约减算法的统一的评价模型，利 用该模型不但可以比较每种算法在不同参数下的嵌入效果，而且可以对不同的非 线性维数约减算法进行比较。 其次，增量式非线性维数约减算法问题。由于多数非线性维数约减算法都是 针对静态数据集的，没有建立一个映射模型，因此对新样本的处理比较困难。文 献【4 9 】中提出从核函数的角度将非线性维数约减算法推广到测试样本中，但该方 第一章绪论 法计算较为复杂且依赖于训练集的核矩阵，而且没有考虑对噪声数据的处理。文 献 5 0 】中提出了一个适应动态数据环境的增量式i s o m a p 算法，然而在映射新数 据点到低维空间的过程中需要估计新样本的范数，且没有考虑对噪声数据的处 理。文献【5 1 】中提出了基于最近邻线性投影的方法，利用新样本的最近邻的局部 线性关系来映射新数据点到低维空间中，但该方法仅仅用最近邻来重构新样本， 常导致新样本错误的局部投影方向，且经常出现病态矩阵现象。因此如何将训练 集之外的样本有效地映射到低维空间中也是非线性维数约减算法急需解决的问 题。 第三，这些算法都涉及到嵌入维数、邻域参数及其他参数的确定，尤其是邻 域参数的选择对低维嵌入的质量至关重要，然而这些参数一般都是根据先验知识 确定的。i s o m a p 算法中使用崖底碎石图1 5 】来确定低维空间的维数，但对其他算 法不一定适合。一些算法 5 1 - 5 6 垛讨了如何确定邻域参数和嵌入维数，但这些算法 不是过于复杂而不适合实际问题，就是在由经验给定的一个参数区间内进行最优 选择。总之来说，目前还没有一个简单而有效的方法来确定算法的嵌入维数和邻 域参数。 再有，这些算法的前提都是假定高维数据位于一个连通的流形中，即得到的 邻域图是连通的。然而，实际数据经常包含多个子流形。当高维数据集中包含多 个子流形时，需要在每个子流形上执行相应的算法，但是没有将这些不同的子流 形映射到同一个低维空间中的方法。文献 5 7 1 q h 通过修改目标函数来使m d s 算法 和i s o m a p 算法适应包含多个子流形的数据集，但其计算过于复杂并不实用。文 献【5 8 】中建立了依赖于两个子流形中最近点的映射算法，但当高维数据中包含较 多的子流形时，计算量呈指数增长，且得到的低维映射有较大的扭曲。 第五。维数约减的逆问题1 5 9 1 ，即如何将嵌入空间中的数据映射回原始的高维 空间中。p c a 算法给出了一个线性模型，利用该模型可以将数据在高维空间和低 维空间之间进行转换。然而多数非线性维数约减算法只是给出了如何将高维数据 嵌入到低维空间中的方法，没有解决将嵌入数据映射回高维空间中的问题。如果 能够将低维数据映射回高维空间中，那么对非线性维数约减算法的嵌入质量评价 问题将大有帮助。 最后，尽管非线性维数约减算法已经被应用到一些领域中【6 ”刖，但维数约减 的初衷是数据的可视化，研究非线性维数约减算法与现有数据处理技术的结合也 第一章绪论 是一个非常迫切的问题。 1 4 本文的工作和主要创新 目前，在数据挖掘、模式识别、机器学习等领域的研究和应用中，大都 涉及到高维数据问题。由于“维数灾难”的影响，使得许多原来用于低维数 据的方法不能直接用于高维数据。为了处理高维数据，可以先对原始的高维 数据进行维数约减，从中识别出最重要的特性，然后再对此典型数据加以处理。 本文较为全面地研究了数据维数约减技术，分析了目前存在的多数非线性维数约 减算法中存在的问题，并针对一些关键问题，如低维嵌入质量的评价、增量式算 法、参数的选择、应用等进行了研究，主要包括以下几点： 首先，本文深入研究了非线性维数约减算法的性能评价问题，分析和比较了 基于应力函数的评价模型、基于剩余方差的评价模型以及基于d y - d x 表示法的 评价模型，提出了基于距离比例方差的非线性维数约减算法的评价模型。与前三 种评价模型相比，利用该模型不但可以评判同一算法在不同参数下的嵌入结果， 而且可以在不同的算法之间进行比较，同时对噪声数据也不太敏感。此外还讨论 了如何利用应力函数、剩余方差和距离比例方差选择邻域参数及确定低维空间的 维数。 其次，对于样本集之外的点的映射问题，本文研究了增量式非线性维数约减 算法，通过改进增量式i s o m a p 算法得到了基于距离保持的增量式算法，并提出 了基于拓朴保持的增量式算法和基于k 近邻投影的增量式算法，它们都可以将一 个新样本映射到嵌入空间中。基于距离保持的增量式算法具有较高的映射质量， 而基于拓朴保持的增量式算法具有较高的效率，但这两种算法都只是对i s o m a p 算法的扩展，不能应用到其他非线性算法中。基于k 近邻投影的增量式算法在映 射质量和计算效率方面都有较好的表现，而且可以作为任何一种非线性维数约减 算法的扩展。在噪声处理方面，由于新样本的低维嵌入与训练集的低维坐标无关， 基于拓朴保持的增量式算法对噪声不太敏感。而基于距离保持的增量式算法和基 于k 近邻投影的增量式算法只要在映射训练样本时较好地处理了噪声数据，就可 以忽略噪声的影响。 最后，在非线性维数约减算法的应用方面，本文研究了它们在模式分类 和聚类分析中的应用。在指纹分类和文本分类中对结合了非线性维数约减技 第一章绪论 术的分类算法进行了仿真实验，在几个公用的数据集上测试了基于非线性维 数约减的聚类算法的性能。 1 5 论文组织结构 第一章是全文的绪论，介绍了本文所做工作的研究背景，对相关的研 究工作做了一个简单的回顾，并且概要地介绍了本文的主要工作和创新点 第二章描述了具有代表性的维数约减算法，包括线性算法和非线性算 法。线性维数约减算法主要介绍了主成分分析法、因子分析法和多维标度变 换法，非线性维数约减算法主要介绍了等距特征映射法、局域线性嵌入法、拉 普拉斯算子特征映射法和自组织等距特征嵌入法，最后对这几种非线性维数约减 算法进行了比较。 第三章讨论了非线性维数约减算法的性能评价问题，分析和比较了基 于应力函数的评价模型、基于剩余方差的评价模型及基于d y - d x 表示法的评 价模型，提出了基于距离比例方差的非线性维数约减算法的评价模型，在 s w i s sr o l l 和s - c u r v e 数据集上比较了这几种模型，并探讨了如何利用应力 函数、剩余方差和距离比例方差确定邻域参数和低维空间的维数。 第四章探讨了如何利用非线性维数约减算法将训练集之外的样本的映 射到低维空间中，通过改进增量式i s o m a p 算法得到了基于距离保持的增量式 算法，提出了基于拓朴保持的增量式算法和基于k 近邻投影的增量式算法， 并比较了这三种算法的优缺点。 第五章介绍了非线性维数约减算法在模式分类和聚类分析中的应用， 并对基于非线性维数约减的多类分类算法和基于非线性维数约减的聚类算 法进行了仿真实验。 最后，是对全文工作的总结和今后工作的展望。 第二章典型的维数约减算法 第二章典型的维数约减算法 机器学习中的许多问题都涉及某种形式的维数约减，目前已经提出许多 种维数约减算法，它们大致可以分为线性的和非线性的两类。本章主要介绍 几种具有代表性的维数约减算法，包括线性算法中的主成分分析法、因子分 析法及多维标度变换法和非线性算法中的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 s 算法。由于s i e 算法具有较好的噪声处理能力，因此本章也对其进行 了详细的讨论，并对这几种非线性维数约减算法进行了比较。 2 1 线性维数约减算法 2 1 1 主成分分析法 主成分分析法是常用的线性维数约减技术之一，已被广泛应用到图象分析、 数据压缩、数据挖掘和模式识别等领域。它是一种通过维数约减技术把多个变 量化为少数几个主成分即综合变量的统计分析方法。这些主成分能够反映原始 变量的绝大部分信息，它们通常表示为原始变量的线性组合。为了使这些主成 分所含信息互不重叠，应要求它们相互独立。 设x = ( x l ，x 2 ，x d ) 7 是一个d 维随机向量，其均值向量和协方差矩阵分 别为p ；e ( x ) 和z = t a r ( x ) 。考虑如下的线性变换： y j = 口1 1 x i + a 2 i x 2 + + 口d l x d = a r x y 2 - - - - - - a 1 2 x l + 吒2 x 2 一+ 口。2 x d = a t x ( 2 - 1 ) ： y b = 口l d x l + g 2 d x 2 + + 口x d = 曩五x 显然，r a t ( y f ) = _ ；勖f ，c o y ( v , ，y ，) = a ；勘，i , j = 1 , 2 ，d 。 。 如果希望用y 1 代替原来的d 个变量，就要求y 1 尽可能多地反映原来d 个 变量的信息，这通过方差来表达，即方差v a r ( y i ) 越大表示y 1 包含的信息越多。 但由于对任意常数k 有胁( 妇f x ) = k 2 r a r ( a r x ) ，因此为消除这种不确定性必须 对_ 。加以限制。常用的限制是a f a l = l ，希望在此约束条件下寻求向量a 1 使得 砌( y 1 ) = a f z a l 达到最大，y 】就是第一主成分。如果第一主成分不足以表达原来 第二章典型的维数约减算法 d 个变量的绝大部分信息，则需考虑使用x 的第二个线性组合，为了使y 所含 的信息与y 1 不重叠，应要求c o y ( y 1 ，y 2 ) = a 盈a 2 = o 。于是在约束条件a 2 r a 2 = 1 和 c o y ( y l ，y 2 ) = a l r p a 2 = o 下寻找向量a 2 使得v a r ( y 2 ) = a ；翻2 达到最大，y 2 就是第 二主成分。类似地，我们可以再定义第三主成分、第四主成分等。一般来说，x 的第f 个主成分指在约束条件a ；4 l = 1 和c o y ( y ：，y ) = a t z a f = o , j i 下，寻找向 量a ，使得v a r ( y ，) = _ ；a ，达到最大。由此得到主成分的定义。 从代数学的观点看，主成分是d 个原始随机变量x 】，x2 一，x d 的一些特殊 的线性组合；而从几何学的观点看，这些线性组合代表选取一个新的坐标系统， 它是以x l ，x2 ，x d 为坐标轴的原坐标系旋转后得到的。新坐标轴代表数据变异 性最大的方向，并且提供对协方差结构的一个较为简单而精练的刻画。 上边求第一主成分y 1 = _ i x 的问题，就是寻求向量a 使得在约束条件 a f a l - l 下砌( y 1 ) = a f - l 达到最大，这是条件极值问题。可以用拉格郎日乘子 法求解，令 l ( a 1 ) = v a r ( y z ) - , c ( a ；a l - 1 ) = a i 4 i 一五( a ：a l 1 ) ( 2 2 ) 对a ，和a 分别求偏导得 因a ，0 ，故l 一刎= 0 ，求上述方程组，其实就是求的特征值和特征向量。设 五= 是的最大特征值，则相应的特征向量a l 即为所求。一般地，求x 的第f 个主成分可通过求z 的第f 大特征值所对应的特征向量得到，x = a ；x 的方差 v a t ( x ) 就是z 的特征值丑。 主成分分析的目的是为了减少变量的个数，因而在实际应用中一般不会使用 所有d 个主成分，而选取聊( m = 1 1 x ，一x 眨 2 ( x i x j ) 。( x l x ) ( 2 1 3 ) = x ；x l 一2 x ；x ，+ x x = b i f 一2 b h + b0 设维向量甲= ( x l x f ，x 2 x ；，x x 磊) 7 ，e 是全l 向量，则d 可表示为 d ：甲e r 一2 x 7 x + e 甲7佗1 4 ) 平方距离矩阵不能直接作为多维标度变换法的输入，必须对平方距离矩阵进行双 中心化，即令j = i 一7 n ，则 b = 一j d j 2 = x 7 x ( 2 - 1 5 ) 这说明b 就是x 的内积矩阵，那么如何通过b 得到x 呢? 注意这里b = x7 x ，与 主成分分析法中求s = x x 7 不同。设i i ，和v f 分别是矩阵s 和b 的特征向量，则 x x 7 i l l i = 丑u ， x 7 x v ，= v ， 在第二个公式的两边同时左乘x 得 第二章典型的维数约减算法 x x 7 x v f = x v ， x x 7 ( x v f ) = ( x v ，) 令= x v l ，则上式变为x x 7 u ，= 丑u f 。这与主成分分析法中的特征值问题相同， 只是特征向量需要乘上x 。假设矩阵b 的特征向量 v 。 是正交单位向量，数据x 的 第i 个成分可表示为= 毋，即 根据特征向量 v ，) ( x 7 x ) v f = x 7 x = 的正交特性有 = 【f lf 2 一 ( 2 - 1 6 ) = 丑v f( 2 - 1 7 ) 多维标度变换的目的并不是重构原始数据x ，而是它的一个低维表示y 。令 如乃是矩阵b 的d 个最大的特征值，v l , v 2 ，v d 是对应的d 个特征向 量，则d 维嵌入坐标为 y