局部保持的流形学习算法对比研究.doc

《局部保持的流形学习算法对比研究.doc》由会员分享，可在线阅读，更多相关《局部保持的流形学习算法对比研究.doc（15页珍藏版）》请在三一办公上搜索。

1、局部保持的流形学习算法对比研究曾宪华 1,2 罗四维 11(北京交通大学计算机与信息技术学院，北京 100044)2(西华师范大学计算机学院，四川，637002) (xianhuazeng)摘要: 局部保持的流形学习通过从局部到整体的思想保持观测空间和内在嵌入空间的局部几何共性，发现 嵌入在高维欧氏空间中的内在低维流形。本文分析了局部保持的流形学习算法的基本实现框架,详细比较了 一些局部保持的流形学习算法的特点，提出了几个有益的研究主题。 关键词：流形学习；局部几何特性；线性投影；内在流形；谱图中图法分类号：TP18Contrasting Research of Local preservin

2、g manifold learning algorithmsZENG Xianhua1,2, LUO Siwei11(School of Computer and Information Technology, Beijing Jiaotong University, Beijing 100044, China)2(School of Computer, China West Normal University, Sichuan 637002,China)Abstract: Local preserving manifold learning algorithms preserve local

3、 geometric properties between observed space and intrinsic embedding space from local to global geometry, and find the intrinsic low-dimensional manifold in the high-dimensional Euclidean space. This paper analyzed the fundamental implementation framework of local preserving manifold learning and co

4、mpared in detail the properties of several classical manifold learning algorithms based on local preserving. Finally, several helpful research directions were proposed.Keywords: Manifold learning; Local geometry property; Linear projection; Intrinsic manifold; Spectral graph1引言流形学习的主要目标是发现嵌入在高维数据空间中

5、观测数据的低维光滑流形。它是一个 具有基础性和前瞻性的研究方向，由于有着广阔的应用前景，近年来已经成为机器学习、模 式识别、数据挖掘等领域的研究热点之一，在流形学习上形成大量的研究方法，按数据处理 的方式、高维数据几何结构的分析方法以及局部几何的表示等将无监督的非线性流形学习算 法按图 1 进行分类13456313742。基于谱图的流形学习研究方法将数据点与一个图的顶点之间建立一一对应，并定义成对 数据点的某种相似度为图中的边，这样就根据数据点建立了一个与之对应的图，利用几何、 代数的方法将发现嵌入流形的目标函数转化为定义在图上的矩阵，通过矩阵的普特征来近似基金项目: 国家自然科学基金项目（6

6、0773016）和（60373029），四川省教育厅重点项目（07ZA121）作者简介：曾宪华，1973年生，博士研究生，主要研究方向为流形学习、人工神经网络、计算机视觉。罗四维，1944年生，博士，博士生导师，北京交通大学计算机与信息技术学院教授，近期主要研究方向包括： 人工神经网络、流形学习、并行处理、多媒体技术及网格计算等.15描述流形的内在主要结构，利用特征向量来表示全局低维坐标。与其它研究方法相比，一个显著的优点是基于谱图的流形学习研究方法是一个能够发现全局最优解的凸优化问题，不会 陷入局部极值3137。在基于谱图的流形学习方法中，全局保持流形学习的方法，要计算 每一个数据点与所有其

7、他数据点的关系，即建立全连接图，例如ISOMAP，在文献5中指出 ISOMAP等度规地保持全局测地距离只对平坦流形（即曲率张量为0）理论上可行；大部分流 形学习算法则利用流形在局部可看作欧氏的观点，通过局部欧氏几何特性的保持，平均意义 下整合对齐局部模型从而发现全局低维坐标，这就是局部保持的流形学习研究方法。由于这 些局部保持的流形学习算法得以广泛的应用，但分散在大量的文献中，没有文献做详细的对 比分析。本文从局部保持的流形学习算法的实现原理为出发点，详细比较了几种典型局部保 持的流形学习算法的实现过程和优缺点以及它们的线性化方法的实现过程，并从实验说明这 些方法发现的内在低维流形的差异。基于

8、神经网络的方法(SOM(1980)、Autoencoder(2006),)基于投影的方法(Principal Curves(1984),)流形学习算法基于互信息的方法(SNE(2002) ,)全局保持的方法（ISOMAP(2000) ,MVU（2005）全局排列局部保持的方法(LLC(2003) ,）基于谱图的方法LE (2002)局部保持的方法LLE (2000)LTSA (2005)LMDS (2006, 2008)图 1 流形学习的分类Fig. 1 Taxonomy of manifold learning2局部保持流形学习算法分析局部保持的流形学习主要是基于保持流形的局部几何特性, 外

9、围观测空间近邻数据所 具有的局部几何特性在内在低维空间得以保持，全局几何通过交叠的近邻来展现。这类方法 基于观测空间和内在嵌入空间的局部几何共性的保持，建立两个空间的联系；即通过建立局 部模型刻画局部几何特性，然后在平均意义下整合对齐所有交叠的局部几何模型发现某种内 在全局几何规律，最后通过全局低维坐标表示出来。2.1 局部保持的流形学习算法的基本步骤 流形学习假定观测数据位于或近似位于一个嵌入在高维欧氏空间的内在低维流形上。所观测到的高维数据全局无序，不知道它们的相对邻接关系。由于流形上的数据存在一个局部邻域同胚于欧氏空间，故近邻的观测数据具有近似的欧氏几何性质。局部保持的流形学习算法就通过

10、近邻数据的选取、局部几何特性的模型刻画、保持局部几何求解全局低维坐标等 三大步骤来实现，如图 2 所示，不同的局部几何的表示及其局部几何模型的对齐方法产生 一系列的局部保持流形学习算法。观测数据近邻选择局部几何的表示整合全局低维坐标对齐近邻相似度 或 近邻重建 或局部切空间近似 或 MDS保持局部欧氏 距离图 2 局部保持的流形学习算法的基本步骤Fig.2 The fundamental steps of manifold learning based on preserving local properties2.2 几种典型的局部保持流形学习算法2.2.1拉普拉斯特征映射（LE，Lapla

11、cian Eigenmaps）2001 年 Belkin 和 Niyogi 提出了 Laplacian 特征映射算法5，该算法寻求一个能在平均 意义上保持流形局部特性的映射，直观看来，即近邻的高维数据点映射到内在低维空间后仍 为近邻点。D设给定的高维观测数据点集为 X = x1 ,L, xn ， xi R坐标Y = y1 ,L, yn ，算法具体描述如下：Step 1. 局部近邻选取。，采样自 d 维流形，求低维使用 k 最近邻或 邻域的方法构建邻接图 G；若两点 i, j 近邻，则 Gij = 1 ，否则为 0。Step 2. 定义邻接权矩阵 W。权值使用热核（Heat Kernel）方法，

12、即如果 Gij = 1 ，则Wij = exp否则为 0。或者使用简单方法，如果 Gij = 1 ，令权值Wij = 1，否则为 0。Step 3. 特征映射。假设图 G 为连接图（否则对每一个连接部分），构造目标函数：xi x j2 / 2 2 ， Min L(Y ) = 1( y y)2W= tr(YLY T )2 i , j ijij（1） suject to : YY T = I其中Y = ( y1 , y2 ,., yn ) ， Dii = j W ji ， L = D W 为 Laplacian 矩阵，Laplacian 矩阵为对称的半正定矩阵，(约束条件也可为统一尺度的YDY T

13、 = I )。利用拉格朗日乘数法，求解d 维低维坐标的优化问题等价于计算拉普拉斯矩阵 L 的 d+1 个最小特征值及对应特征向量。令这 d+1 个特征向量为u1 , u2 , u3 ,., ud +1 ，分别对应于从小到大排列特征值。除去最小特iii征值 0 对应的特征向量 u1，x 在低维空间 Rd 的像可以由 (u (2),L, u (d + 1) 给出，即全局23d +1低维坐标为Y = u , u ,., uT 。2.2.2局部线性嵌入（LLE, Locally Linear Embedding）局部线性嵌入算法1是假定观测数据集位于一高维空间的低维嵌入流形上，并且嵌入 空间与内在低维

14、空间对应的局部邻域中数据点保持相同的局部近邻关系。特别地，假定观测 空间中的每一点可以由其局部邻域中的点加权平均近似表示，重建低维流形时，相应的内在低维空间中点由同样的加权邻近点近似表示。根据这个思想，2000 年 Sam Roweis 等人提出D了局部线性嵌入算法。设给定的高维观测数据点集为 X = x1 ,L, xn ，xi R，采样自 d维流形，求低维坐标Y = y1 ,L, yn ，该算法的具体描述如下：Step 1. 局部近邻选取。m对于给定的观测数据集 X = x 1 , x 2 ,L, x i ,L, x n , x i R，根据这些数据点之间欧氏距离搜索数据集中每一数据点 x

15、i 的 k（n）个最近邻x i1 , x i2 ,L, x ik ，其中 x ij X 。Step 2.最小化目标函数：2 nnKiE1 (W) = E1 = xi Wijxij(2)i=1 i=1j=1上式中 Wij 表示数据点 i 的第 j 个近邻的加权，对每一点 x i 求解下面的约束优化问题，1ii2Kij ij Min Ei (W ) = Min x条件:Wij = 1j =1W xj=1 (3)Step 3. 固定 Step 2 获得的权值矩阵 W，最小化下列目标函数求每一 x i 对应的低维向量 y i 。关于低维坐标 Y 的最小化目标函数为：2 nnKiE2 (Y) = E2

16、(yi ) = yi Wijyij(4)i=1 i=1 j=1为了避免数据集在低维时坍塌到坐标原点，约束低维坐标YY T = I ，其中 I 表示n阶单位矩阵。相应的优化问题转化为下列的约束优化问题nK22iiij ijY(5) MinEi (y ) = Miny W y= Min tr(YMYT )i=1 i=1 j=1Subject to: YY T = I上式中 M = (I W)T (I W) ，利用拉格朗日乘数法，上述问题转化为求解M的最小的d+1个特征值对应的特征向量u1 , u2 , u3 ,., ud +1 ，舍弃最小特征向量 u1 后的d个特征向量对23d +1应分量构成观测

17、数据集的低维表示，即全局低维坐标为Y = u , u ,., uT 。2.2.3局部切空间排列（LTSA，Local Tangent Space Alignment）对于非线性流形来说，全局的非线性结构来自于局部线性分析和局部线性信息的全局 整合，根据这个思想 2004 年张振跃等人提出局部切空间整合算法（LTSA）21，该算法通 过逼近每一样本点的切空间来构建低维流形的局部几何，观测数据点在局部切空间的投影获 得局部低维坐标，交叠的局部低维坐标被局部仿射变换后获得全局低维嵌入坐标。D设给定的高维观测数据点集为 X = x1 ,L, xn ， xi R坐标Y = y1 ,L, yn ，LTSA

18、 算法的具体描述如下：Step1. 局部近邻选取。，采样自 d 维流形，求低维对于每一个样本点 xi ，记近邻数据集 X i = xi1 ,L, xik 为包含数据点 xi 本身在内的 k个近邻；Step2. 计算每一个近邻数据集 X i 的d维局部切空间的基向量和观测数据的局部切坐标 i 。为了计算观测数据流形上每一个数据点的d维局部切空间的标准正交基 Qi ，使得近邻数据点在切 空间上的 投影误差 最小，由 文献 40 分 析可知 ,Qi 可由观测数 据矩阵 (1TX i I eeK) 进行SVD分解的d个最大奇异值对应的d个左奇异特征向量给出。而局部坐标T1T由观测数据在基Qi 上的投影

19、坐标给出，即 i = QiStep3. 局部切坐标排列成全局低维坐标iiX i (I ee ) 。K根据 n 个局部投影坐标 i = 1 ,L,k , i = 1,., n ，通过局部仿射变换整合得到全局i i =1 i坐标 y n 。设 L R构误差得到全局坐标：d d和Y = y1 ,L, yn ，Yi = yi1 ,L, yik ，通过最小化全局排列的重min E2 = min Y ( I 1 eeT ) L 2(6)2iLi ,YiiLi ,Yiiiki 1 Ti i 2+iEi 关于局部仿射变换 Li 的最小二乘解 Li = Yi ( I k ee )i ，上述全局目标函数用矩阵表示

20、，对应最优化问题等价于：min YSW= min tr(YSWW T S T Y T )(7)YY其 中S = S1 , S2 ,., Si , ., SN 是 近 邻 选 择 矩 阵 ， 即YSi = Yi，iiW = diag (W ,W ,.,W ,.,W ) ，其中W = ( I 1 eeT12iNik)( I + ) 。在规范性约束YY T = I(单位阵) 的条件下，因此最优d维低维坐标Y由 SWW T S T的第2个到第d+1个最小特征值对应的特征向量 u2 , u3 ,., ud +1 构成(最小特征值为0，舍弃23d +1其特征向量)，即Y = u , u ,., uT 。2

21、.2.4局部多维尺度分析(LMDS, Locally Multidimensional Scaling )2006 年 LiYang 应用经典的 MDS 作为局部模型，然后排列对齐局部模型获得全局低维 坐标, 提出了局部多维尺度分析。局部多维尺度分析算法通过应用 MDS 等度规地保持近邻 高维数据点的局部欧氏距离，从而获得表示局部几何的局部低维坐标，交叠的局部低维坐标 被局部仿射变换后排列成全局低维嵌入坐标3336。因此，LMDS 与 LTSA 在实现方式上 相似，不同在于局部低维坐标的表示，LMDS 是通过经典的 MDS 获得等度规地保持局部欧 氏距离的局部低维坐标，LTSA 是利用 SVD

22、（奇异值分解）近邻观测数据集，通过在近似的 局部切空间的投影获得局部低维坐标。与 LTSA 相比，LMDS 只需要将局部数据点间的欧氏距 离输入局部模型（MDS），不必知道数据点的具体表示。D设给定的高维观测数据点集为 X= xi ,L, xn ， xi R，采样自 d 维流形，求低维坐标Y = y1 ,L, yn ，LMDS 算法的具体描述如下：Step1. 局部近邻选取。对于每一个样本点 xi ，记近邻数据集 X i = xi1 ,L, xik 为包含数据点 xi 本身在内的 k个近邻；Step2. 应用经典 MDS 到每一个近邻数据集 X i 求得其局部低维坐标 Pi 。对于近邻数据集

23、X i ，求得任意两点间的欧氏距离矩阵 Di ，然后对 Di 施加经典 MDSi1k求得局部低维坐标 = p i ,L, p i 。Step3. 局部坐标排列成全局低维坐标Y和 LTSA 一样，假定近邻数据集 X i 对应的全局低维坐标Yi 是由其局部低维坐标 Pi 通过1T局部仿射变换得到，即Yi = Yi k ee+ Li Pi + Ei ，（为了表述一致性，该式是文献36对应公式两边转置得到）。通过最小化全局排列的重构误差得到全局坐标，全局目标函数为：minE2 = min2Y ( I 1 eeT ) L P(8)L YiL Yiki ii , ii2i , i ii 2整理后得到与 L

24、TSA 相同的特征值问题，即min YSW= min tr(YSWW T S T Y T )(9)YY1T+其中W = diag (W1 ,W2 ,.,Wi ,.,WN ) ，且Wi = ( I k ee)( I PiPi ) 。在规范性约束YY T = I(单位阵) 的条件下，因此最优d维低维坐标Y由 SWW T S T 的第2个23d +123d +1到第d+1个最小特征值对应的特征向量 u , u ,., u构成，即Y = u , u ,., uT 。下面我们分析一下 LTSA 和 LMDS 算法中Wi 的数值计算问题：+T在 LTSA 中，由 Moore-Penrose 广义逆的定义，

25、Wi 中的 i i 是一个到由 i 的列张成的子空间上的正交投影变换，它可以通过计算 i 的 d（内在维数）个最大右奇异向量i1diii iV = v ,., v 得到40，即 + = V V T1T；根据 i 的定义，v1 ,., vd 也是 X i ( I k ee ) 的d 个最大右奇异向量，等价于 ( I 1 eeT ) X T X ( I 1eeT ) 的 d 个最大特征向量。可验证1T+1T0kiikk ee i i = k ee Vi =，故(1T )(+)1T+1TTWi =I eeI i ik= I eek i i = I k ee ViVi(10)在 LMDS 中，Wi 中

26、的 Pi 是近邻数据集 X i 通过 MDS 求得局部低维坐标。MDS 算法中将近邻欧氏距离矩阵 Di 双中心化后进行特征分解，即求解下列半正定矩阵= B1 ( I 1 eeT )D ( I 1 eeT )(11)i2kik的 d 个最大特征值 i = diag (1 ,., d ) 及其对应的特征向量Vi = v1 ,., vd ，获得的局部低1维坐标 P = 2V T 。由近邻数据集 X 对应的欧氏距离矩阵 D 与 X ( I 1 eeT ) 对应的欧氏iiiiik距离矩阵相等，通过中心化数据集的欧氏距离矩阵，可以验证(1T )T(1TBi =I eeX ikX i I ee )k+T(1

27、2)故Vi 也是中心化协方差矩阵的特征向量，且 PiPi = ViVi。因此，W = ( I 1 eeT )( I P+ P ) = ( I 1 eeT )( I V V T ) = I 1 eeT V V T(13)ikiiki iki i综上所述，LMDS 与 LTSA 从不同的角度表示局部低维坐标，求得的全局低维坐标是相同的，都是保持局部等度规的流形学习算法，发现的内在流形结构是相同的。2.3 局部保持的流形学习算法对比简表正如图 2 所示，局部保持的流形学习算法通过从局部到整体的思想保持观测空间和内在 嵌入空间的局部几何共性，发现嵌入在高维欧氏空间中的内在低维流形。大体实现步骤分为 三

28、步，但它们在局部几何的表示以及低维重建目标函数的不同又各有差异。2.2.4 节分析了 LTSA 和 LMDS 的实现过程，发现尽管两者的局部模型表示不同，但求低维坐标的目标函数是 相同的，因此它们求得的全局低维坐标是相同的，都是保持局部等度规的流形学习算法，发 现的内在流形结构也是相同的，连算法实现过程中的优缺点也是相似的。因此，本节只对 LE、LLE 和 LTSA 做具体详细比较，如表 1，其中 D 表示样本数据的维数，d 表示内在维数， p 表示稀疏矩阵非零元数的比例，n 表示样本数据的个数，k 为选取的最近邻个数。表 1 局部保持流形学习算法的比较Table 1 Comparisons

29、of local preserving manifold learning algorithms算法特性拉普拉斯特征映射（LA）局部线性嵌入（LLE）局部切空间排列（LTSA）近邻选择K 个最近邻（或者邻域）同左同左局部几何的 表示近邻间欧式距离的热核函数 表示近邻相似度每个样本点由局部邻域内的其 它样本点加权平均表示（重建）局部邻域由局部切空间近似，每个样本点通过局部切坐标 表示整体几何的体现局部邻域的交叠传播同左同左 ijij低维空间几何性质的保 持近邻的高维数据点（相似度大）映射到内在低维空间后仍 为近邻点近邻重建权值保持不变全局低维坐标由局部切坐标 的仿射变换得到求低维坐标 的目标函数

30、 Min 1 ( y y )2W Y2 i , j Subject to : YY T = I2n k Min y W yi=1 j=1TSubjectto : YY = Imin YH L 2 Subjectto : YY T = I最优化过程(条件最小值)一次两次两次局部极值无无无全局低维坐标（d 维）的 求解求对称半正定稀疏局阵的第 2到第 d+1 个最小特征值对应的 特征向量同左同左全局低维坐标 Y 的约束YY T = I同左同左隐含低维坐 标中心化n i是，y = 0i=1 同左同左时间复杂度O( Dn log n) + O( pnD)+O(dpn2 )O( Dn log n) +

31、O(nK 3 )+O(dpn2 )O( Dn log n) + O(nK 3 )+O(dpn2 )计算速度最快次之再次之存储复杂度O( pn2 )O( pn2 )O( pn2 )流形展现（如图 1，2）具有聚类现象（局部序关系保持）复杂流形有轻微形变（局部序关系保持）整体流形展现较好（局部序关系保持）高低维空间之间的映射隐式非线性隐射同左同左线性化流形学习算法的 假设Y = X T A= X T ( , ,., )12d同左同左iY i ij ij Li ,Tii K i i2.4 全局线性化局部保持的流形学习算法前面论述的局部保持的流形学习算法在高维观测空间和内在低维空间之间建立的是隐 式的

32、非线性映射，而且这样的隐式映射只定义在训练数据上，对于新来观测数据点不能快速 明确的映射到低维空间中8。将高低维空间的非线性映射用一个线性映射来近似，使得这 个线性投影变换不但能够保持局部几何特性而且具有线性子空间投影的优点，可以像 PCA、 LDA 一样广泛的应用到模式识别、计算机视觉等领域24，为生物识别提供一些新颖的线性12d子空间技术。何晓飞等人假定低维坐标Y = AT X = ( , ,., )TX ，其中 X 是高维观测数据，将该线性变换分别融入到 LE 和 LLE 中提出了两种新的线性投影技术局部保持投影（LPP）和近邻保持嵌入（NPE），作为非线性的 LE 和 LLE 的线性近

33、似；同样，张天昊等人将线性变换Y = X T A 融合到 LTSA 算法中提出了另一种新的线性维数约减算法线性的局部切空间排列（LLTSA）算法，作为 LTSA 的线性近似，这三种线性投影技术在人脸识别实验中都取得了比 PCA 更好的识别效果122232。表 2 对比列出三种线性投影 技术 LPP、NPE 和 LLTSA 的实现步骤。表 2LPP、NPE 和 LLTSA 的基本步骤Table 2 The fundamental steps of LPP, NPE and LLTSAijijY S ubjectto : Y Y= I Y 2 算法步骤局部保持投影（LPP）近邻保持嵌入（NPE）线

34、性的局 部 切空间排列 （LLTSA）Step 1近邻选择,构造邻接图 G近邻选择,构造邻接图 G近邻选择,构造邻接图 GStep 2计算近邻相似度 W计算近邻重建权 W计算局部切坐标 Step 3计算投影向量:求低维坐标对应近邻保持的 目标函数最小化，即 Min 1( y y )2W Y2 i , j Subjectto : YY T = I代入线性变换 y = T x ，得 Min 1 ( T x T x )2Wi , j S.t. : T XX T = I 其中 L = D W ，而对角矩阵D的 对 角 线 元 素Dii = Wijj求解下列广义特征方程的 d 个最小特征值对应的特征向量

35、 作为 d 个投影向量：XLX T = XX T 计算投影向量:求低维坐标对应近邻重建的 目标函数最小化,即nk2 Min yi Wijyiji=1 j=1 Subjectto : YY T = I代入线性变换 y = T x ，得nK2 Min xi Wij xij TT i=1 j=1TT 其中M = ( I W )T ( I W )求解下列广义特征方程的 d 个最小特征值对应的特征向量 作为 d 个投影向量：XMX T = XX T 计算投影向量:求局部切坐标仿射变换为低 维坐标的重建目标函数最小 化, 即 min Y H L 2 L ,T i k i i i iiTH k 是 k 阶中

36、 心 化矩阵且 H = I eeT k 。k代入变换Y = T ( X H ) ，ii且由 H 2 = H 得min T ( X H ) L 2 L ,Y i k i i i i i S.t. : T XX T = I Min T XHBHX T S.t.： T XHX T = I其中 B = SWW T S T ，近邻选择矩阵S = S1 ,., Si ,., Sn 使得YSi = Yi，并且W = diag (W1 ,W2 , .,Wn ) ，且 W = H ( I + ) 。iki i求解下列广义特征方程的 d 个最小特征值对应的特征向量 作为 d 个投影向量：XHBHX T = XHX

37、 T ijij故由上述特征方程的 d 个最小特征值 1 p 2 p L p d对应特 征向 量 1 ， 2 ，L,d ，构成保持近邻相似度特性的线性变换矩阵：A = 1 ,2 ,L,d 1 ,d T（注：对于约束条件 YY= I ，有时为了删除近邻相似度的尺度影响 ， 实 际 应 用 中 常 采 用 YDY T = I 作为约束条件。）故由上述特征方程的 d 个最小特征值 1 p 2 p L p d对应特 征向 量 1 ， 2 ，L,d ，构成保持近邻重建特性的线性变换矩阵：A = 1 ,2 ,L,d 1 ,d 故由上述特征方程的 d 个最小特征值 1 p 2 p L p d对应特 征向 量

38、1 ， 2 ，L,d ，构成保持局部切坐标特性的线性变换矩阵：A = 1 ,2 ,L,d 1 ,d Step 4低维全局坐标Y = AT X低维全局坐标Y = AT X低维全局坐标Y = AT XH3实验比较本节将上面论述的局部保持的流形学习算法对嵌入在 3 维空间中的 2 维流形进行实验。 在 S-Curve 曲面和 Swiss-roll 曲面上随机采样 2000 个数据点，所有算法的近邻选取参数 k=10，LE 算法计算相似度的热核参数=1，图 3 和图 4 是它们的 2 维可视化效果，为了便于比较 3种新的线性投影技术与传统线性方法的不同，也在 PCA 上作了实验。对于非线性的 LE、L

39、LE和 LTSA 均能发现原始数据的内在流形结构，也可看出 LE 将高维近邻点映射到低维空间尽 可能的接近使得低维流形结构呈现出聚类现象，而 LLE 发现的低维流形会发生一定程度的 扭曲，LTSA 的整体低维流形的展现效果最好。线性投影方法对非线性的数据流形不能有效 的发现全局低维结构，但 PCA 为了实现全局散度最大，数据点之间的序关系已被破坏，而 LPP、NPE 和 LLTSA 作为线性投影方法，却最大程度的保持了原始数据的流形结构，局部 几何特性得以保持，数据点之间的序关系也得以保持。图 3 针对 S-curve 数据集，局部保持的流形学习算法与 PCA 发现 2 维内在结构的比较Fig. 3. Comparisons of 2-dimensional intrinsic structures by using local preserving manifold learning and PCA on S-curve d