高维数据的低维表示综述

1、高维数据的低维表示综述一、研究背景在科学研究中，我们经常要对数据进行处理。而这些数据通常都位于维数较 高的空间，例如，当我们处理200个256*256的图片序列时，通常我们将图片拉 成一个向量，这样，我们得到了 65536*200的数据，如果直接对这些数据进行处 理，会有以下问题：首先，会出现所谓的“位数灾难”问题，巨大的计算量将使 我们无法忍受；其次，这些数据通常没有反映出数据的本质特征，如果直接对他 们进行处理，不会得到理想的结果。所以，通常我们需要首先对数据进行降维， 然后对降维后的数据进行处理。降维的基本原理是把数据样本从高维输入空间通过线性或非线性映射投影 到一个低维空间，从而找出隐

2、藏在高维观测数据中有意义的低维结构。（8）之所以能对高维数据进行降维，是因为数据的原始表示常常包含大量冗余：有些变量的变化比测量引入的噪声还要小，因此可以看作是无关的有些变量和其他的变量有很强的相关性（例如是其他变量的线性组合或是 其他函数依赖关系），可以找到一组新的不相关的变量（3）从几何的观点来看，降维可以看成是挖掘嵌入在高维数据中的低维线性或非 线性流形。这种嵌入保留了原始数据的几何特性，即在高维空间中靠近的点在嵌 入空间中也相互靠近（12）数据降维是以牺牲一部分信息为代价的，把高维数据通过投影映射到低维空 间中，势必会造成一些原始信息的损失。所以在对高维数据实施降维的过程中如 何在最优

3、的保持原始数据的本质的前提下，实现高维数据的低维表示，是研究的 重点（8）二、降维问题定义定义1.1降维问题的模型为（X, F），其中D维数据空间集合X = x n （一 / l=1般为RD的一个子集），映射FF : X Y x T y = F(x),Y是d空间集合(一般是Rd , d d，流形学习的目标是基于RD上的一个给定被观测数据集合h去恢复y和 if，在y中隐藏的数据被随机地产生，然后被f映射到观测空间，使得 i七=f（y）。（ 12）局部线性嵌入方法 LLE （Locally Linear Embedding） 5LLE在保存原始高维数据邻域线性结构的基础上计算低维表达（5）是一种

4、局部方法，它试图保持数据的局部几何特征，就本质上来说，它是将流形上的近 邻点映射到低维空间的近邻（9）图2非线性降维实例B是从A中提取的样本点（三维），通过非线性降维算法 LLE将数据映射到二维空间中（C），从C图中的颜色可以看出通过LLE算法处 理后的数据能很好的保持原有数据的邻域特性（引用文献6）主要思想：对一组具有嵌套（流形）的数据集，在嵌套空问与内在低维空间局 部邻域问的关系应该不变，即在嵌套空间中每个采样点可以用它的近邻点线性表 示，在低维空间中保持每个邻域中的权值不变，重构原数据点，使重构误差最小。(8) TOC o 1-5 h z 乙 /oL/g/ ! /y/,F /O Q尊三*

5、:映射到嵌入坐陆B 白LLE的实现过程步骤：LLE方法可以归结为三步：寻找每个样本点的k个近邻点；把相对于所求样本点距离最近的k个样本点规定为所求样本点的k个邻近点。k 是一个预先给定值。距离的计算既可采用欧式距离也可采用Dijkstra距离。Dijkstra距离是一种测地距离，它能够保持样本点之间的曲面特性。由每个样本点的近邻点计算出该样本点的局部重建权值矩阵；这里定义一个成本函数，如下式，来测量重建误差： (w) = x -Z w x 2i j目j解得w =Z Gi-1/Z Gi-1，Z w =1, x.史 N 时w. = 0ijk jk Im lm寸 j司xjN其中G = (x -门)(

6、x -门)，门和门是x的近邻点； jk i j i k j k i为了使重建误差最小化，权重w服从一种重要的对称性，即对所有特定数据点 来说，它们和它们邻居点之间经过旋转、重排、转换等变换后，它们之间的对称 性是不变的。由此可见重建权重能够描述每个邻居本质的几何特性。因此可以认 为原始数据空间内的局部几何特征同在流形局部块上的几何特征是完全等效的。（3）由该样本点的局部重建权值矩阵和其近邻点计算出该样本点的输出值。 映射条件满足如下成本函数：y（Y）=E|y-E wi要使低维重构误差最小，计算得出，Y等价于求M的特征向量，其中 M = （I - W）T（I - W）在处理过程中，将M的特征值从

7、小到大排列，第一个特征 值几乎接近于零，那么舍去第一个特征值。通常取第2到m+l之间的特征值所 对应的特征向量作为输出结果。优点：LLE算法可以学习任意维的局部线性的低维流形，就是用局部性一一 用局部的的线性来逼近全局的非线性，保持局部的几何结构不变，通过相互重叠 的局部邻域来提供整体的信息，从而保持整体的几何性质。LLE既有非线性的特 点又具有线性方法的优点（8）同时由重构成本函数最小化得到的最优权值遵循 对称特性，每个点的近邻权值在平移、旋转、伸缩变换下是保持不变的LLE算 法有解析的全局最优解，不需迭代，低维嵌入的计算归结为稀疏矩阵特征值的计 算，这样计算复杂度相对较小。缺点：LLE算法

8、要求所学习的流形只能是不闭合的且在局部是线性的，还要 求样本在流形上是稠密采样的。另外，该算法的参数选择不确定，对样本中的噪 音很敏感（12）此外，（1）对于一个新样本点。没有显式的方法把该点嵌入到低 维空间中，这在检索应用中不适用。（2）新空间的维数没有显式准则进行确定， 只有通过经验的方法。（3）LLE没有利用数据点的类信息。在分类问题中，对于 有类标号的样本数据，LLE无能为力。SLLE 算法7Dick和Robert提出一种针对有监督的LLE算法，即Supervised linear locally embedding （SLLE）传统的LLE算法在第一步时是根据样本点间的欧氏距离来寻

9、找k个近邻点，而SLLE在处理这一步时增加了样本点的类别信息，SLLE算法 的其余步骤同LLE算法是一致的。SLLE算法在计算点与点之间的距离时有两种方法。SLLE1：第一种方法是采用下式来修正点与点之间的距离公式如下所示D = D +a max(D)A其中：D是计算后的距离D是最初米用的距离；max(D)是表示类与类之间 的最大距离；A取0或者1,当两点属于同类时，A取为0,否则取1； a是控制 点集之间的距离参数，a e 0,1,是一个经验参数。当a取为零时，此时的SLLE 和LLE算法相同。这个方法引入了一个参数a ,它是一种经验参数，对实验的 结果有很大的影响，下面介绍一种非参数的方法

10、。SLLE2:求解点与点之间的距离，目的在于是寻找样本点的近邻点。SLLE2 的方法在寻找近邻点时，不是在全局样本中寻找近邻点，而是在每个点所在类的 样本中寻找近邻点，也就是说，在类内中寻找样本点的近邻点。这个方法固然没 有采用参数的方法，但是如果某一类的样本个数小于k，那么这种方法必将失败， 则每个类的样本个数在相当多的情况下可以采用这种方法。RLLE 算法8当在做聚类分析且采用LLE算法对数据进行降维时，如果数据中存在着许 多离异点的情况，那么降维后的结果将会发生变异，通常是第一维或者是第二维 的数据发生跳跃式的变化，或者分布在某几条直线上，这将会给聚类带来很大的 麻烦，其实当离异点超过L

11、LE算法中的k值时，这种现象将会发生。A.Hadid 和 M.Pietikainen 提出一种 Robust Locally Linear Embedding (RLLE) 方法。它是针对存在有离异点的情况下，对样本的一种无监督的非线性降维方法。邻域保持嵌入算法NPE算法9NPE从本质上说是局部线性嵌入(local linear embedding， LLE)的线性逼近。 给定数据集X，采用与LLE相同的方法构建数据集上的近邻图。NPE针对LLE 算法的out-of-sample问题提出的，该算法通过最小化局部相似离散度寻找投影 方向，有效的保持了数据间的相似几何结构，取得了不错效果，已被广泛

12、地应用 到文档分析、机器学习和模拟识别等领域。NPE假定每个局部近邻都是线性的。算法步骤：1近邻选择，构造邻接图G2计算近邻重建权W3计算投影向量：Min-EMin-Ey i=1W yj=iS.t: YYt = IMin Elx t-Ea i=iMin Elx t-Ea i=iW xtaj=iS.t: atXXta= IMin a tXMXt aaS.t: atXXta= I其中 M = (I - W)t(I - W)d求解下列广义特征方程的d个最小特征值对应的特征向量作为d个投影 向量：XMXt a =X XXt a故由上述特征方程的d个最小特征值七气,气对应特征向量 aa.,气，构成保持近

13、邻重建特性的线性变换矩阵。缺点：NPE在保持数据空间的局部相似信息时，不能较有效地保持差异信息， 特别是高维非线性数据间的差异信息。如在人脸识别应用中，人脸图像的识别容 易受光照、表情等非理想条件变化的影响，这些非理想情况会使得同一个人的不 同图像之间的差异大于不同人图像之间的差异，从而导致识别错误。NPE算法通过式x,t y =而气.实现了数据到新空间的线性变换。显然，这 种线性变换实现的数据变换是一种显式形式，这样就解决了 LLE算法没有显式 映射函数的问题。LLE算法是非监督的学习方法，没有充分利用类别信息，为了提高算法的识 别能力，于是有了 LLE的正交线性化扩展，orthogonal

14、 neighborhood preserving projections(ONPP)10 11。张长水等人12在LLE的基础上提出一种从低维嵌入空间向高维空间映射 的方法，并在多姿态人脸图像的重构实验中得到有效的验证，进一步完善了非线 性降维方法。等距映射法 ISOMAP (Isometric Map) 13ISOMAP认为当数据集具有嵌入流形结构时，可以根据保距映射来获得观测 空间数据集在低维结构的对应描述。基本思想：ISOMAP通过测地线距离来描述各点之间的相互关系，在全局意 义下，通过寻找各点在图意义下的最短路径来获得点与点之间的距离，然后利用 经典的MDS算法得到低维的嵌入坐标。因此.

15、ISOMAP可认为是MDS算法的 变种(5)|1欧氏距惠原wd函匚距拽(b)由瓠点组成的图 (c ffllSOMAP将数据降到两健图3 ISOMAP算法示意图使用前提条件：高维数据所在的低维流形与欧氏空间的一个子集是整体等距 的；与数据所在的流形等距的欧氏空问的子集是一个凸集。主要步骤：构造局部邻域。首先对数据集X = %,%,.,七，计算任意两个样本向量x和工的欧式距离d 3 ,工)，将每一个点与所有的点进行比较，当两点之间的距i jx i j离小于固定的半径 (或i是j的K-邻域)时，我们就认为它们是相邻的，将其 连接起来，该边的长度dx(x,xj，则得到邻域图G。计算最短距离。在图G中，

16、设任意两个样本向量x,和X/之间的最短距离为d (x ,x )。若x和x之间存在连线，d (x ,x )的初始值为d (x ,x )，否则令G i ji jG i jx i jd(x_,x.) = 8。对所有的 k=12.,nd (x ,x ) = mind (x ,x ),d (x ,x ) + d (x ,x )G i jG i j G i k G k j这样得到矩阵Dg = dG(七,Xj)，它是图G中所有点对的最短路径组成的。构造d维嵌入。用MDS方法构造一个保持本征几何结构的d维嵌入到空 间Y。T (D ) = 一 H *( Dg)2*HG2H是与Dg同阶的单位矩阵，对t (Dg)进

17、行特征分解，取最大的前d个特征 值人，人，,人和对应的特征向量V,V，,V，令册为第p个特征向量的第i个成 12d12dp分，则对应的数据低维表示为y二人i/2V。优点：适用于学习内部平坦的低维流形，ISOMAP结合了线性算法(如PCA 和MDS)的主要特征计算的有效性、全局的优化性和渐进收敛性等。这种用 测地距离来代替传统的欧氏距离的方法，可更有效的在低维空间来表达高维空间 的数据，减少降维后损失的数据信息。缺点：不适于学习有较大内在曲率的流形。在噪声干扰下，Isomap用于可 视化会有不稳定现象，取较大的邻域会产生短路现象，即低维流形中不同邻域部 分的点投影后出现明显的混杂现象。选取较小的

18、邻域，虽然能够保证整体结构的 稳定，但低维投影结果会产生大量“空洞”，或使最短路径算法重构的图不连通。 降维维数的确定通常是在本质维数未知的情况下进行的，经多次实验绘制残差曲 线观察得到。Isomap算法计算图上2点间的最短距离可采用Dijkstra算法，但执 行起来仍然比较慢(12)当与高维流形等距的欧氏空间的子集不是凸型时，即当高维空间存在“空 洞”时，要计算高维观测空间上任意样本点之间的距离很有可能发生弯曲异常， 如果这样就会影响低维嵌入结果的表示。等距特征映射算法在数据拓扑空间有可能是不稳定的。因为如果选择的 邻域过小，就会导致邻域图不连通，如果选择的邻域太大，又可能导致短路。使用Is

19、omap算法恢复非线性流形的几何结构的时候，所需的计算时间比 较多，这主要是花在计算样本点之间的最短路径上。由于已有的流形学习算法对噪音和算法参数都比较敏感，詹德川、周志华14 针对Isomap算法，提出了一种新方法，通过引入集成学习技术，扩大了可以产 生有效可视化结果的输入参数范围，并且降低了对噪音的敏感性。另外，赵连伟 15等人完善了 Isomap的理论基础，给出了连续流形与其低维参数空间等距映 射的存在性证明，并区分了嵌入空间维数、高维数据的固有维数与流形维数这些 容易混淆的概念，证明如果高维数据空间存在环状流形，流形维数则要小于嵌入 空间维数.他们还给出一种有效的环状流形发现算法，以得

20、到正确的低维参数空 间。特别地，周志华等16 提出了一种方法，可以从放大因子和延伸方向两方面 显示出观测空间的高维数据与降维后的低维数据之间的联系，并实验比较了 2 种著名流形学习算法(Isomap和LLE)的性能。文献17中，作者提出了一种基于Isomap的监督算法Weightedlso。在分类 问题中，理想情况下属于同一类的样本在测量空间中应离得近一些，反之，不同 类的样本则离得远一些。因此，作者在基本Isomap算法的第一步，计算各样本 点间的欧氏距离时引进了一个常量参数，用来重新度量同一类样本间的距离，使 它们离得更近。Weightedlso算法虽然在一定程度上克服了流形学习方法分类效

21、果较差的缺 点，但在引入常量参数重新度量同类样本的距离时，由于噪声的影响，破坏了样 本间的本质结构，使其可视化应用效果下降。在分类问题中，权值w在很大程 度上影响着分类的结果，如何选取w值得进一步研究。由于 Weightedlso 的不足，Xin Geng,De Chuan Zhan 等18提出 了另一种基于 Isomap的监督算法SIsomap。该方法同样是修改了 Isomap算法的第一步，用已 知的样本所属类别信息重新定义了样本间的距离。局部切空间排列算法 LTSA (local tangent space alignment)19LTSA是一种基于切空间的流形学习方法，它通过逼近每一样本

22、点的切空间 来构建低维流形的局部几何，然后利用局部切空间排列求出整体低维嵌入坐标。主要思想：找出每个数据点的近邻点，用邻域中低维切空间的坐标近似表示 局部的非线性几何特征，再通过变换矩阵将各数据点邻域切空间的局部坐标映射 到一个同一的全局坐标上，从而实现高维数据降维，即从n维数据中得到一个全 局的d维坐标。(8)算法步骤：第一步：构造邻域。对于每个数据点七，找出它的包括它自身在内的k个邻域点，构成矩阵Xj = 土，,七。第二步：局部线性投影。对于每个样本点的邻域X,，计算中心化矩阵X (I -eeT / k)的最大d个奇异值对应的左奇异向量，并将这d个左奇异向量组成 i矩阵Q。1由Xj(I -

23、 eeT /k) = UEV计算得出左奇异向量U，取出U的前d列构成矩阵Q( Q即为土点的切空间的近似)；2计算各个邻域点在该切空间Q的投影：i=QtX (I -eeT /k) = 01(i)，,B(i)0 (i)= Qt (x - x )J 1 lj 1第三步：局部坐标系统的排列。对每个邻域的局部切空间坐标0 = (0(i),0(i),.,0(i)(i = 1,2,.,N)，构造转换矩阵 L =0+g Rd xd。通过最小化i 12ki iz |t, (I - eeT / k) - L.0J2的求解，最后化解可通过计算一个矩阵从第2小到第d+1 小的特征值所对应的特征向量。其中0：是0的广义

24、Moor-Penrose逆。优缺点：LTSA能够有效地学习体现数据集低维流形结构的整体嵌入坐标， 但它也存在两方面的不足：一方面算法中用于特征值分解的矩阵的阶数等于样本 数，样本集较大时将无法处理；另一方面算法不能有效处理新来的样本点(12) 对此，提出了一些相应的改进算法。但LTSA也面临着同HLLE类似的一些问题：LTSA所反映的局部结构是它 的局部d维坐标系统，因此，由于噪声等因素的影响，当数据集的局部低维特征 不明显或者不是d维的时候，它的局部邻域到局部切空间的投影距离往往并不 小。此时，构造的重建误差也不会小，这样LTSA可能就无法得到理想的嵌入结 果。此外，LTSA对样本点的密度和

25、曲率的变化的影响比较敏感，样本点的密度 和曲率的变化使得样本点到流形局部切空间的投影产生偏差，而LTSA构造排列 矩阵的模型并没有将这种偏差计入考虑范围。这使得对于样本点密度和曲率变化 较大的流形，LTSA的嵌入结果可能会出现扭曲现象。线性局部切空问排列(LLTSA)针对LTSA算法不能为新的测试样本提供一个明确的从高维到低维的映射， 也就是所谓的“Out of Sample问题。提出了一个新的线性算法，线性局部切空 问排列(LLTSA)20。该算法运用切信息作为数据的局部表达，然后将这些局部 信息在可以用线性跌射得到的低维空间中排列。它先将每一个样本点邻域的切空 间表示为流形的局部几何，再经

26、线性映射实现样本数据从高维空间降维到低维空 间，最终将整体嵌入坐标的求解问题转化为矩阵的广义特征值的求解问题。算法步骤：1近邻选择，构造邻接图G2计算局部切坐标03计算投影向量：a求低维坐标对应近邻重建的目标函数最小化，即Min Z |YH -L 0 |2LT i k 1 1S.t: YYt = IHk是k阶中心化矩阵且Hk = I - eeT / k。b代入线性变换Y =a t(XH)，且由H2 = H得MinZ|at(XH )-L0 |2L ,T ,i k i 11 i iSt: atXXta= IMin a tXHBHXt aC 0,即半正定=1 lK + K - 2 Kii jj1JL

27、 K = 0i, j i，jK 0,即半正定s.t: s.t: 通过半定规划(SDP)学习内积矩阵丘使得保持局部近邻距离和低维数据点中 心在原点，实现最大方差展开，如上式。3对内积矩阵K进行特征分解求内在低维坐标：求K的最大的d个特征值人，.人(令A=diag(人，人)对应的特征向量U = v ,则d维坐标为1 d1 d1 dY =Aut。优点：首先，MVP忠实的保存了类间几何特征和类内几何特征，该算法是 基于流形学习的算法。其次，MVP具备判别能力，适用于分类问题。缺点：MVU在SDP步的时间复杂度大，数据点数就2000个时目前普通的 PC机也要计算几个小时1491。非负矩阵分解(Non-n

28、egative Matrix actorization，NMF)由于实际问题中矩阵数据很庞大，其中存放的信息分布往往不均匀，因此直 接处理这样的矩阵效率低下，就失去了实用意义。为高效处理这些通过矩阵存放 的数据，一个关键的必要步骤便是对矩阵进行分解操作。通过矩阵分解，一方面 将矩阵的维数进行削减，另一方面也可以对大量的数据进行压缩和概括。NMF直接将非负分解问题作为带约束的非线性规划问题NMF子空间要求子 空间的基以及样本在子空间上的投影系数都是非负的，这一约束限制了投影到子 空间的数据只能是子空间基的加性组合，而不存在减运算。因此，所获得的对数 据表示的非负基所张成的子空间是非正交的和部分无

29、界的，这使得其对数据的表 示更为紧凑和更少冗余，表示效率更高，即对数据具有更好的夹逼性，从而更有 利于对数据的表示。NMF具有下列特点：（1）分解的结果不含负值，具有明确的物理意义和可解 释性，非常适合非负数据处理；（2）能够发现数据内部潜在结构特征，还能够降 低数据特征的维数，节省存储和计算资源，这在处理高维数据时就有很明显的优 势；（3） NMF的心理学和生理学构造依据是人眼对整体的感知是由对部分的感知 组成的（纯加性的），即整体是部分的非负线性组合，因此具有智能数据描述的特 性；（4）非负性的限制还导致分解结果具有一定的稀疏性，相对稀疏的表示方式 能够在一定程度上抑制外界变化（部分遮挡、

30、光照变化、图像旋转）给特征提取带 来的不利影响。此外，将NMF和一些常用的流行学习方法结合会在分类问题上取得较好的结 果。如Ruicong Zhi等考虑原始面部图像稀疏表征和邻近结构保留，为面部特征 提取提出了一种新算法 GSNMF （Graph-Preserving Sparse Nonnegative Matrix Factorization），利用了局部保留投影算法LPP，保留局部结构，加上不可控制的 稀疏性约束，在人脸识别中提高了识别率。对图像识别任务主要就是为了获得更 好的分类，将原始数据通过基矩阵进行投影映射，因此就是对基矩阵产生了约束， 获得更好的局部特征。与有监督算法需要用到所

31、有训练样本的先验信息（如样本所属类别、样本低 维坐标等信息）不同，半监督学习算法只需要用到部分样本的类别或其低维信息， 更接近实际中的问题，因此与有监督算法相比具有一定优势。但也因为如此，其 算法的推广也有一定难度，目前的研究还比较有限。拉普拉斯特征映射算法的作者Belkin等2l将拉普拉斯特征映射算法推广 到了半监督学习问题中，首先利用拉普拉斯特征映射算法求出低维嵌入流形，然 后在流形上利用标记样本训练分类器进行分类，其对手写字体识别和文本分类的 实验证明了算法的有效性。XinYang等22给出了半监督的LLE和LTSA算法，在通过传统算法得到各 样本间的关系矩阵后，利用可获得的部分样本的先

32、验低维坐标信息来求解剩余样 本的低维坐标，得到了更精确的低维结果，并验证了该算法解决可视化和视频序 列中人的运动手臂跟踪等问题。ZhenyueZhang等23分析了基于谱方法的半监督学习，给出了较详细的数 学基础和推导，分析了 LTSA算法中的特征值问题在半监督学习中的关系，通过 实验比较了所提出算法与现有算法，证实了其优越性。冯海亮等24将半监督的LLE算法用于人脸和人脸表情识别，构造样本间距 离矩阵时利用部分样本的类别信息来得到一个更能反映样本间关系的矩阵，然后 再通过求解该矩阵的特征值、特征向量问题求解低维结果，取得了优于传统流形 学习算法的分类效果。四、降维方法总结高维数据集合的降维过

33、程（包括线性、非线性降维）可分解为既相互独立又相 互关联的三个阶段：1）数据集结构的描述；2）数据集结构的度量准则：3）基 于结构的降维准则。降维方法的提出和形成同样主要包含三个方面的工作，1）建立研究问题的 相应数学模型，数据集结构模型；2）对该模型提出相应的度量准则或选择规则; 3）建立基于数据集结构的降维准则或损失规则（4）如何自动判断数据集的非线性是由内在曲率还是映射模型造成的，如何处理 断续流形与非断续流形或者变维数流形，目前还没有好的解决方法，这也是流形 学习中需要进一步研究的问题。另外，流形学习可以视为数据处理的一个中间过 程，要完成最终的目标，需要与其他领域的知识或算法相结合，

34、如与分类算法 k-NN，SVM，HMM等相结合实现分类识别目的。目前的流形学习方法存在的 主要不足有：（1）流形学习算法计算复杂度高现有流形学习的一个很大瓶颈就是计算复杂度太高，这阻碍了其在实际中的 应用。虽然其对非线性数据具有较好的降维效果，但如何有效降低计算量，甚至 推广其线性化算法是一个研究热点。线性化是一个很好的方法，但是线性化以后 对于高度的非线性问题也一样束手无策。如何得到可处理非线性数据的线性化流 形学习方法值得进一步研究。流形学习算法的分类能力较弱在处理分类问题时，多数情况下流形学习算法的性能较传统方法要差。因为， 流形学习算法在恢复内在不变量时采用了局部邻域思想，算法本身的稳

35、定性与邻 域选择有关，如何在分类意义下获得适当的邻域参数需要进一步的研究。另外， 算法中采用了 k-NN来获得流形结构在观测空间的有限描述，这一方法假定了数 据集不存在异常噪声，如果噪声较大时，算法可能覆盖过多的非支撑域以外的空 间，从而使得随后的分类算法产生错误的几何投影距离。本征维数的估计我们对流形学习方法的非参数化问题进行了研究，如何自适应的确定流形学 习算法中需要的参数，而不是依据经验或人为设定，也是需要解决的问题。在非 线性降维过程中，原始数据本征维数d都是由经验已知或人为设定的，其设定值 的大小对低维空间的映射结果有很大影响。d值过大使映射结果含有过多噪声； d值过小，本来不同的点

36、在低维空间可能会彼此交叠。目前本征维数的估计方法主要分为以下三种32： (1)特征值或映射方法，(2) 几何学习方法，(3)统计学习方法。增量学习目前的大部分流形学习算法只定义在给定的数据集上，通常算法只能得到给 定数据集在低维空间中的表示七，而不能得到从高维空间到低维空间的非线 性映射关系f -1： Rm T Rd。缺少这一映射关系将无法在不重新构造图的情况下计 算新样本的低维表示。如何根据新输入的样本修改映射关系而不重新计算，可以 节约大量的计算时间和存储空间。国际上已经有很多学者开始关注这一问题的研究，Law M等33提出了一种 增量Isomap算法，只是修改了测地距离的计算方式，节省了

37、一定的时间，但对 于算法本身并没有好的改进；OlgaK等34人在LLE基本算法的基础上提出了一 种增量LLE算法以解决样本外问题。噪声流形学习问题目前的大部分流形学习算法在构造邻域图时采用了 k-NN准则来获得流形结 构在观测空间的有限描述。这一方法假定了数据集不存在异常噪声，如果噪声较 大时，算法可能覆盖过多的非支撑域以外的空间，从而使得随后的分类算法产生 错误的几何投影距离。考虑流形学习与全局分析方法的互补性，现有的全局分析 方法如主成分或主曲线等在这一方面具有一定的优势，所以在机器学习和模式识 别等领域，如何将两者有机地结合起来，互补缺陷，将是一个好的研究方向。当 观测数据是对一个光滑流

38、形较好的采样时，使用非线性降维可以找出其内在本质 的流形分布。但是，在实际的高维采样数据中由于各种因素经常存在噪声，使得 映射到低维空间后会出现对原始数据结构的扭曲和变形。寻找淹没子流形的问题现在的大部分流形学习算法是基于单一流形的假设前提。所以当数据集中存 在多个流形时，流形学习算法将失效。它们只能被分别单独应用在各个“聚类” 的数据上。而对于模式识别问题，人们关心的是由多个类别构成的数据集中存在 着怎样的几何结构。通常，一个类别对应着一个流形，不同类别对应于位于不同 位置的流形。不同类别之间的区别在于它们在高维空问所占据的位置不同。面对 这种任务，需要一种能同时观察这些不同类别中流形的流形

39、学习算法。目前这一 问题还没能得到很好的解决。流形重构与有监督学习现有的流形学习方法主要应用于聚类与可视化，这是由于数据降维的点对点 嵌入性质决定的。但由于难以得到流形空间与其降维空间的对应映射函数关系， 使其难以广泛用于模式识别和分类等问题。如何找到两个空间的映射关系，包括 线性与非线性映射关系，以重构流形是监督与半监督学习需要解决的关键问题之 一。如果能得到数据降维中观测空间到特征空间的映射，则以训练数据划分空间 对测试数据进行分类的有监督流形学习将成为可能。H.Hotelling, Analysis of A Complex of Statistical Variables into P

40、rindpal Components,Journal of Educational Psychology,xol.24,pp.417-441,1933.R.A.Fisher,“The Use of Multiple Measurements in Taxonomic Problems,”Annals of Eugenics,vol.7,pp.179-188,1936.P.J.Huber.Projection pursuit.Annals of Statistics,13(2):435 475 (with comments pp. 475 525)， June 1985.Thomas L.Gri

41、ffiths and Michael L.Kalish,A Multidimensional scaling approach to mentalmultiplication,Memory&Cognition,vol.30(1),pp.97-106,2002ROWEISS,SAULL.Nonlinear dimensionality reduction by locally linear embeddingJ.Science,2000,290(5500):2323-2326.Lawrence K.Saul, Sam T.Roweis. Think Globally, Fit Locally:

42、Unsupervised Learning of Low Dimensional Manifolds. Journal of Machine Learning Research 4(2003) 119-155Dick de Ridder, Olga Kouropteva, Oleg Okun, et al. Supervised locally linear embedding. Artificial Neural Networks and Neural Information Processing, ICANN/ICONIP 2003 Proceedings, Lecture Notes i

43、n Computer Science 2714, Springer, 333-341Hadid A, Pietika inen M.Efficient locally linear embeddings of imperfect manifolds, Machine Learning and Data Mining in Pattern Recognition, MLDM 2003 Proceedings, Lecture Notes in Computer Science 2734, Springer, 188-201.X.He, D.Cai, S.Yan, and H. Zhang,Nei

44、ghborhood Preserving Embedding, ”Proc. IEEE Intl Conf.Computer Vision,pp.1208-1213,2005.E.Kokiopoulou and Y Saad,Orthogonal Neighborhood Preserving Projections:A Projection-Based Dimensionality Reduction Technique,IEEE Trans.Pattern Analysis and Machine Intelligence,vol.29,no.12,pp.2143-2156,2007.E.

45、 Kokiopoulou and Y. Saad,”Orthogonal Neighborhood Preserving Projections, Proc. IEEE Intl Conf.Data Mining,pp.27-30,2005.Zhang CS, Wang J, Zhao NY, Zhang D. Reconstruction and analysis of multipose face images based on nonlinear dimensionality reduction. Pattern Recognition, 2004, 37(1)： 325-336.TEN

46、ENBAUM J,SILVADD,LANGFORD J.Aglobal geometric framework for nonlinear dimensionality reductionJ.Science,2000,290(5500):2319-2323.詹德川，周志华.基于集成的流形学习可视化J.计算机研究与发展，2005, 42(9)： 1533-1537.赵连伟，罗四维，赵艳敞，等.高维数据的低维嵌入及嵌入维数研究J.软件学报， 2005, 16(8)： 1423-1430.何力，张军平，周志平.基于放大因子和延伸方向研究流形学习算法J.计算机学报， 2005,28(12)：2000-

47、2009.M.Vlaehos,C.Domeniconi,D.Gunopulos ct a1.Non-linear dimensionality reduction techniques for classification and visualization.In Proceedings of 8thSIGKDD,Edmonton,Canada,2002.645-65 1.Geng,X.Zhan,D.C.Zhou,Z.H.Supervised nonlinear dimensionality reduction for visualization and classification.IEEE

48、 Transactions on Systems Man and Cybernetics Prat B.2005,vol.35,1098-1107.ZHANG ZY,ZHA HY.Principal manifolds and nonlinear dimensionality reduction via tangent space alignmentJ.SIAM Journal of Scientific Computing,2005,26(1):313-338.Zhang T,Yang J,Zhao D,et al. Linear local tangent space alignment and application to face recognitionJ.Neumcomputing,2007,70(7-9):1547-1553.李勇周，罗大庸，刘少强等.正交判别的线性局部切空间排列的人脸识别J.中国图象图形 学报 A,2009,1