高维数据的低维表示综述

《高维数据的低维表示综述》由会员分享，可在线阅读，更多相关《高维数据的低维表示综述（30页珍藏版）》请在装配图网上搜索。

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

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

3、始数据的本质的前提下，实现高维数据的低维表示，是研究的重点。（8）二、降维问题1定义定义 1.1 降维问题的模型为(,)XF，其中D维数据空间集合1NllXx（一般为DR的一个子集），映射F:FXY(),xyFxY是d空间集合（一般是dR，dD）的一个子集，我们称F是数据集X（到Y）的降维。若F为X的线性函数，则称F为线性降维；否则，称为非线性降维。定义 1.2 称映射1F1:FYX1()yxFy为嵌入映射。（8）2分类针对降维问题的目的和待处理数据集合表象维数的多少，对其进行初步的、粗略的分类如下：硬降维问题：数据维数从几千到几万甚至几十万的变化，此时需要对数据集进行“严厉”的降维，以至于达

4、到便于处理的大小，如图像识别、分类问题以及语音识别问题等。软降维问题：此时数据集合的维数不是太高，降维的需求不是非常的迫切。如社会科学、心理学以及多元统计分析领域皆属于此类。可视化问题：此时数据集合的绝对维数不是很高，但为了便于利用人们的直观洞察力，即为了可视化，我们将其降到 2 或 3 维。虽然我们可以可视化更高维数的数据，但是它们通常难于理解，不能产生数据空间的合理形态。若我们还考虑时间变量的话可以对降维问题进行更加进一步的分类，静态降维问题和动态降维问题。后者对于时间序列来讲是有用的，如视频序列、连续语音信号等的处理。（4）3方法介绍如何将高维数据表示在低维空间中，并由此发现其内在结构是

5、高维信息处理研究的关键问题之一。实际处理中，由于线性方法具有简单性、易解释性、可延展性等优点，使得线性降维在高维数据处理中是一个主要研究方向。已有的线性维数约简方法，主要包括主成分分析(Principal Component Analysis，PCA)16、独立成分分析(Independent Component Analysis，ICA)、线 性 判 别 分 析inear discriminant analysis(LDA)17、Fisher 判别分析(Fisher Discriminant Analysis，FDA)、主曲线(Principal Curves)、投 影 寻 踪(Projec

6、tion Pursuit,PP)、多 维 尺 度 方 法(Multidimensional Scaling，MDS)等。这些方法实际是在不同优化准则之下，寻求最佳线性模型，这也是线性维数约简方法的共性。（10）通过消除数据建模过程中的全局线性假设，Sammon 提出了一种非线性映射，即 Sammon 映射(SM)，该算法能够保持输入样本之间的相关距离；Hastie提出了principal curves(PC)，其定义为通过概率分布或数据中间的光滑曲线；Kohonen 基于自组织神经网络提出了self-organizing map(SOM)用来保存数据空间的拓扑属性；Scholkopf 等应用

7、Mercer 核将 PCA 扩展为 Kernel PCA(KPCA)，该算法在高维空间中计算主分量，而该高维空间由输入空间经某种非线性映射得到。Mika等采用相同的思想来非线性扩展LDA，从而提出了kernel LDA（KLDA）；然而，基于核的方法其难点在于如何选择一个合适的核函数，一个好的核函数可以使数据在特征空间上线性可分或者近似线性可分，但并不是所选核函数对于每一种数据都适用。核函数的选择反映了人们对问题的先验知识，在实际的应用中往往是经验地选择某种核函数，比如径向基函数(Radial Basis Function，RBF)。同时，在使用核函数时不必知道具体的特征空间，使得核函数方法缺

8、乏物理直观性，这也是核函数方法的一个缺点。（10）最近兴起的流形学习算法也是用来维数约减的非线性方法，并且依靠它们在探测嵌入在高维空间中低维流形的能力和灵活性而被广泛应用。具有代表性的流形学习算法包括等距映射(Isometric Mapping，Isomap)、局部线性嵌入方法(Locally Linear Embedding，LLE)、Laplacian 特征映射(Laplacian Eigenmap，LE)、局部切空间排列方法(Local Tangent Space Alignment，LTSA)、Hessian等距映射(Hessian eigenmaps，HLLE)和最大方差展开(max

9、imum variance unfolding，MVU)。其中，LLE 运用线性系数，来表达局部几何，该系数能够重建一个给定的样本点利用其近邻点，然后寻找一个低维空间，在该空间中这些线性系数仍然可以用来重建相应的点；ISOMAP 作为 MDS 的变种，能够保存点对之间的全局的测地线距离；LE 通过对一个描述了点对之间邻域关系的无向图的操作，来保持数据之间的近邻关系。HLLE 先通过估计邻域上的Hessian而构建一矩阵，然后在此矩阵上运用特征值分解而得到最终的低维坐标。LTSA 运用局部切信息作为局部几何的表达，然后将这些切信息在全局中排列从而得到最终的全局坐标。MVU 不是一个绝对的局部方法

10、而是一个介于局部和全局之间的方法，因为 MVU 不仅保存近邻点之间的几何关系而且在它的目标函数中考虑了全局点对之间的距离。除了基于谱分析的流形学习的算法，基于概率参数模型，Rowels提 出 了global coordination(GC)；Teh 和Roweis 开 发 了locally linear coordination(LLC)；Brand 提出了 manifold charting(Charting)。这些方法也属于流形学习的重要范畴。然而，这些非线性的算法却不能够为样本提供一个外在的映射，也就是说，它们很难被应用于识别问题。但是，一些基于谱分析的算法由于其具有特殊的特征分解机制而

11、能够较为容易的扩展为线性算法，其线性化可以通过在解决优化的过程中施加线性逼近来实现。Locality preserving projection(LPP)作为 LE 的线性化 是 其 中 最 早 提 出 的 算 法。后 来 提 出 的 还 包 括 neighborhood preserving embedding(NPE)，LLE 的线性化扩展，和orthogonal neighborhood preserving projections(ONPP)，LLE 的正交线性化扩展。这种线性化扩展使流形学习的思想更能够应用到现实世界中。图1.1 给出了以上所提提及的降维算法的分类图。在谱方法的线性化

12、扩展中，LPP 可以被看作为基于图结构的最具代表性的算法，在接下来的几年中，又不断地有这种基于图的算法被提出，从而进一步完善了这种基于图的框架。Cai 等对 LPP 算法分别对监督设置和非监督设置两种情况作了系统的分析，并且将LDA 用这种基于图的框架重新公式化。Yan 等提出了一种一般性的框架即“图嵌入”，来统一各种各样的降维算法。基于此种框架，一种新的线性算法，marginal fisher analysis（MFA）将开发出来。MFA 不同于 LPP其只用一个图来描述数据的几何结构，该算法采用了两个图，其中一个为固有图（intrinsic graph），它用来刻画数据的类内紧凑性；而另一

13、个图为惩罚图（penalty graph），用来描述数据类间的分离性。因此，MFA 比 LPP 更具有判别性。Chen等同时提出的 local discriminant embedding（LDE）算法在本质上与MFA 的思想是相同的。（5）非线性降维方法与线性降维方法相比的一个显著特点是，分析中的局部性(数据集合经常满足的一个简单假设)。原因在于对数据集合的内蕴结构而言，有下列特性：由泰勒定理，任何可微函数在一点的充分小的邻域之内满足线性性。形象的来讲，相当于认为曲面流形可由大小不一的局部线性块拼接而成；数据流形经常是由许多可分割的子流形所组成；数据流形的本征维数沿着流形不断的发生变化，只有

14、局部性才能抓住其根本特性。（4）三、常见降维方法（一）线性1.主成分分析(Principal Component Aanlysis PCA)1 PCA 将方差的大小作为衡量信息量多少的标准，认为方差越大提供的信息越多，反之提供的信息就越少。它是在损失很少的信息的前提下把多个指标转化为几个综合指标的一种多元统计方法。它具有概念简单，计算方便以及最优线性重构误差等优良的特性。PCA 是一种全局算法，它可以较好地揭示具有线性结构的高维数据集的全降维线性流行学习概率参数模型全局谱分析局部全局局部早期的非线性PCA MVU ISOMAP Charting LLC Kernel PC SM SOM GC

15、LDA LPP NPE LLE LLTSA ONPP LE LTSA HLLE 线性化局分布。然而对于嵌入在高维空间中具有非线性流形结构的数据，PCA 很难学习出隐含在数据集中的低维流形结构。PCA 假设数据之间的关系是线性的。它在保存原始高维数据协方差结构的基础上计算低维表达，也就是最大化总体方差。它的目标函数可以写为：2121=arg m axarg max()arg m ax().P C AP C AP C ANmP CAiUiNTmTTP CAiP CATP CAP CAP C AdUUiUyyUxxtr US Us t UUI其 中，1miyyN，1mixxN，且TS为 总 体 离

16、散 矩 阵：i=1=()()TNTiiSxxxx。对转换矩阵做尺度约束d=TPC APC AUUI，其中dI为dd单位矩阵。则目标函数可以写为：arg max()P C ATP C ATP CAUtrUS U，.TP C APC Ads t UUI上式问题可以转化为TS的标准的特征值问题：PCA 的最优转换矩阵为TS的d 个最大的特征值所对应的d 个 m 维特征向量。2.线性判别法(Linear Discriminant Analysis LDA)2 其基本思想是投影，首先找出特征向量，把这些数据投影到一个低维的方向，使得投影后不同的组之间尽可能的分开，而同一组内的的样本比较靠拢，然后在新空间

17、中对样本进行分类。通过最小化类内离散矩阵WS的秩而最大化类间离散矩阵BS的秩，来寻找一个子空间来区分不同的类别。WS和BS分别定义如下：()()()()i=11=()()iNCiiiiTWjjjSxmxm()()1()()CiiTBiiSNmmmm其中，iN是第 i 个类中样本的个数；()ijx是第 i 个样本中第 j 个样本。()im为第 i 个类的质心；m用来表示所有样本的质心，C为样本的类别数。LDA则有以下的优化准则：arg m ax()()TL DABLD ATLD AWLD Atr US Utr US U.TLD ALD Ads t UUI上述的优化可以转化为求解一个广义的特征分解

18、问题：BWSS且最优的解为 d 个特征向量其对应于d 个最大的非零特征值。3.投影寻踪(Projection Pursuit PP)3 基本思想主要来源人们对低维空间几何图形的直观理解，它包含俩个方面的含义：其一是投影(Projection)，把高维空间中数据投影到低维空间；其二是寻踪(Pursuit)，利用低维空间投影数据的几何分布形念，发现人们感兴趣的数据内在特征和相应的投影方向，同时排除与数据结构和特征无关的或关系比较小的变量干扰。4.多维尺度分析(Multidimensional Scalar，MDS)4 主要思想是：根据数据点间的欧氏距离，构造关系矩阵，为了尽可能地保持每对观测数据点

19、之间的欧氏距离，只需对此关系矩阵进行特征分解，从而获得每个数据在低维空间中的低维坐标。算法步骤：1 计算观测空间中任意两点欧式距离，构造n 阶平方欧式距离矩阵A 2 将矩阵 A 进行双中心化计算，即计算12BH AH。若设nn阶矩阵=e/THIen（常称之为中心化矩阵），将矩阵 H 左乘和右乘 A 的两边（常称之为双中心化）。3 计算低维坐标Y。即将B 奇异值分解，设B 的最大的d 个特征值1d=diag()，对应特征向量1,dUvv，则 d 维坐标为TYU。（二）非线性流形学习旨在发现高维数据集分布的内在规律性，其基本思想是：高维观测空间中的点由少数独立变量的共同作用在观测空间张成一个流形，

20、如果能有效地展开观测空间卷曲的流形或发现内在的主要变量，就可以对该数据集进行降维。现在形式化地概括流形学习这一维数约简过程：假设数据是均匀采样于一个高维欧氏空间中的低维流形，流形学习就是从高维采样数据中恢复低维流形结构，即找到高维空间中的低维流形，并求出相应的嵌入映射，以实现维数约简或者数据可视化。它是从观测到的现象中去寻找事物的本质，找到产生数据的内在规律。用数学语言可以这样描述，令dYR且:DfYR是一个光滑的嵌套，Dd，流形学习的目标是基于DR上的一个给定被观测数据集合ix去恢复Y和f，在Y中隐藏的数据iy被随机地产生，然后被f映射到观测空间，使得()iixfy。（12）1.局部线性嵌入

21、方法LLE(Locally Linear Embedding)5 LLE 在保存原始高维数据邻域线性结构的基础上计算低维表达。（5）是一种局部方法，它试图保持数据的局部几何特征，就本质上来说，它是将流形上的近邻点映射到低维空间的近邻。（9）图 2 非线性降维实例B 是从 A 中提取的样本点（三维），通过非线性降维算法LLE 将数据映射到二维空间中（C），从 C 图中的颜色可以看出通过LLE 算法处理后的数据能很好的保持原有数据的邻域特性(引用文献 6)主要思想：对一组具有嵌套(流形)的数据集，在嵌套空问与内在低维空间局部邻域问的关系应该不变，即在嵌套空间中每个采样点可以用它的近邻点线性表示，在

22、低维空间中保持每个邻域中的权值不变，重构原数据点，使重构误差最小。(8)LLE 的实现过程步骤：LLE 方法可以归结为三步：(1)寻找每个样本点的k 个近邻点；把相对于所求样本点距离最近的k 个样本点规定为所求样本点的k 个邻近点。k是一个预先给定值。距离的计算既可采用欧式距离也可采用Dijkstra 距离。Dijkstra 距离是一种测地距离，它能够保持样本点之间的曲面特性。(2)由每个样本点的近邻点计算出该样本点的局部重建权值矩阵；这里定义一个成本函数，如下式，来测量重建误差：2()iijjjwxw x解得11/iiijjklmklmwGG，1,jijxNwjxN时0ijw其中()()ij

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

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

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

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

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

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

29、器学习和模拟识别等领域。NPE 假定每个局部近邻都是线性的。算法步骤：1 近邻选择，构造邻接图G 2 计算近邻重建权 W 3 计算投影向量：a求低维坐标对应近邻重建的目标函数最小化，即211.:nkiijijYijTM inyWyS tYYIb 代入线性变换Tyx,得211x.:nkTTiijijijTTM inW xS tXXIc.:TTTTM inXM XS tXXI其中()()TMIWIWd 求解下列广义特征方程的d 个最小特征值对应的特征向量作为d 个投影向量：=TTXM XXX故 由 上 述 特 征 方 程 的d 个 最 小 特 征 值12d,对 应 特 征 向 量12d,，构成保持

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

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

32、AP 可认为是 MDS 算法的变种。（5）图 3 ISOMAP 算法示意图使用前提条件：高维数据所在的低维流形与欧氏空间的一个子集是整体等距的；与数据所在的流形等距的欧氏空问的子集是一个凸集。主要步骤：(1)构造局部邻域。首先对数据集12,nXxxx，计算任意两个样本向量ix和jx的欧式距离(,)xijdxx，将每一个点与所有的点进行比较，当两点之间的距离小于固定的半径（或 i 是 j 的 K-邻域）时，我们就认为它们是相邻的，将其连接起来，该边的长度(,)xijdxx,则得到邻域图 G。(2)计算最短距离。在图G 中，设任意两个样本向量ix和jx之间的最短距离为(,)Gijdxx。若ix和j

33、x之间存在连线，(,)Gijdxx的初始值为(,)xijdxx，否则令(,)Gijdxx。对所有的 k=1,2,n(,)m in(,),(,)(,)GijGijGikGkjdxxdxxdxxdxx这样得到矩阵(,)GGijDdxx，它是图 G中所有点对的最短路径组成的。(3)构造 d 维嵌入。用 MDS 方法构造一个保持本征几何结构的d 维嵌入到空间 Y。2*()*()2GGHDHDH 是与GD同阶的单位矩阵，对()GD进行特征分解，取最大的前d 个特征值12,d和对应的特征向量12,dVVV，令ipV为第 p 个特征向量的第 i 个成分，则对应的数据低维表示为1/2iippyV。优点：适用于

34、学习内部平坦的低维流形，ISOMAP 结合了线性算法(如 PCA和 MDS)的主要特征 计算的有效性、全局的优化性和渐进收敛性等。这种用测地距离来代替传统的欧氏距离的方法，可更有效的在低维空间来表达高维空间的数据，减少降维后损失的数据信息。缺点：不适于学习有较大内在曲率的流形。在噪声干扰下，Isomap 用于可视化会有不稳定现象，取较大的邻域会产生短路现象，即低维流形中不同邻域部分的点投影后出现明显的混杂现象。选取较小的邻域，虽然能够保证整体结构的稳定，但低维投影结果会产生大量“空洞”，或使最短路径算法重构的图不连通。降维维数的确定通常是在本质维数未知的情况下进行的，经多次实验绘制残差曲线观察

35、得到。Isomap算法计算图上 2 点间的最短距离可采用Dijkstra 算法，但执行起来仍然比较慢。（12）(l)当与高维流形等距的欧氏空间的子集不是凸型时，即当高维空间存在“空洞”时，要计算高维观测空间上任意样本点之间的距离很有可能发生弯曲异常，如果这样就会影响低维嵌入结果的表示。(2)等距特征映射算法在数据拓扑空间有可能是不稳定的。因为如果选择的邻域过小，就会导致邻域图不连通，如果选择的邻域太大，又可能导致短路。(3)使用 Isomap算法恢复非线性流形的几何结构的时候，所需的计算时间比较多，这主要是花在计算样本点之间的最短路径上。由于已有的流形学习算法对噪音和算法参数都比较敏感，詹德川

36、、周志华 14针对 Isomap 算法，提出了一种新方法，通过引入集成学习技术，扩大了可以产生有效可视化结果的输入参数范围，并且降低了对噪音的敏感性。另外，赵连伟15等人完善了Isomap 的理论基础，给出了连续流形与其低维参数空间等距映射的存在性证明，并区分了嵌入空间维数、高维数据的固有维数与流形维数这些容易混淆的概念，证明如果高维数据空间存在环状流形，流形维数则要小于嵌入空间维数他们还给出一种有效的环状流形发现算法，以得到正确的低维参数空间。特别地，周志华等 16提出了一种方法，可以从放大因子和延伸方向两方面显示出观测空间的高维数据与降维后的低维数据之间的联系，并实验比较了2种著名流形学习

37、算法(Isomap和 LLE)的性能。文献17中，作者提出了一种基于Isomap 的监督算法 Weightedlso。在分类问题中，理想情况下属于同一类的样本在测量空间中应离得近一些，反之，不同类的样本则离得远一些。因此，作者在基本Isomap 算法的第一步，计算各样本点间的欧氏距离时引进了一个常量参数，用来重新度量同一类样本间的距离，使它们离得更近。Weightedlso 算法虽然在一定程度上克服了流形学习方法分类效果较差的缺点，但在引入常量参数重新度量同类样本的距离时，由于噪声的影响，破坏了样本间的本质结构，使其可视化应用效果下降。在分类问题中，权值w 在很大程度上影响着分类的结果，如何选

38、取w 值得进一步研究。由于 Weightedlso的不足，Xin Geng,De Chuan Zhan等18提出了另一种基于Isomap 的监督算法 SIsomap。该方法同样是修改了Isomap算法的第一步，用已知的样本所属类别信息重新定义了样本间的距离。3局部切空间排列算法LTSA(local tangent space alignment)19 LTSA 是一种基于切空间的流形学习方法，它通过逼近每一样本点的切空间来构建低维流形的局部几何，然后利用局部切空间排列求出整体低维嵌入坐标。主要思想：找出每个数据点的近邻点，用邻域中低维切空间的坐标近似表示局部的非线性几何特征，再通过变换矩阵将各

39、数据点邻域切空间的局部坐标映射到一个同一的全局坐标上，从而实现高维数据降维，即从 n 维数据中得到一个全局的 d 维坐标。(8)算法步骤：第一步：构造邻域。对于每个数据点ix，找出它的包括它自身在内的k 个邻域点，构成矩阵1,kiiiXxx。第二步：局部线性投影。对于每个样本点的邻域iX，计算中心化矩阵(/)TiXIeek的最大 d 个奇异值对应的左奇异向量，并将这 d 个左奇异向量组成矩阵iQ。1由(/)TiXIeekUV计算得出左奇异向量U，取出 U的前 d列构成矩阵iQ（iQ即为ix点的切空间的近似）；2 计算各个邻域点在该切空间iQ的投影：()()1(/),TTiiiiikQXIeek

40、()()jiTjiiiQxx第 三 步：局 部 坐 标 系 统 的 排 列。对 每 个 邻 域 的 局 部 切 空 间 坐 标()()()12(,)(1,2,)iiiikiN，构造转换矩阵ddiiLR。通过最小化2(/)TiiiTIeekL的求解，最后化解可通过计算一个矩阵从第2 小到第 d+1小的特征值所对应的特征向量。其中i是的广义 Moor-Penrose逆。优缺点：LTSA 能够有效地学习体现数据集低维流形结构的整体嵌入坐标，但它也存在两方面的不足：一方面算法中用于特征值分解的矩阵的阶数等于样本数，样本集较大时将无法处理；另一方面算法不能有效处理新来的样本点。（12）对此，提出了一些相

41、应的改进算法。但 LTSA 也面临着同 HLLE 类似的一些问题：LTSA 所反映的局部结构是它的局部 d 维坐标系统，因此，由于噪声等因素的影响，当数据集的局部低维特征不明显或者不是d 维的时候，它的局部邻域到局部切空间的投影距离往往并不小。此时，构造的重建误差也不会小，这样LTSA 可能就无法得到理想的嵌入结果。此外，LTSA 对样本点的密度和曲率的变化的影响比较敏感，样本点的密度和曲率的变化使得样本点到流形局部切空间的投影产生偏差，而 LTSA 构造排列矩阵的模型并没有将这种偏差计入考虑范围。这使得对于样本点密度和曲率变化较大的流形，LTSA 的嵌入结果可能会出现扭曲现象。线性局部切空问

42、排列(LLTSA)针对 LTSA 算法不能为新的测试样本提供一个明确的从高维到低维的映射，也就是所谓的“Out of Sample”问题。提出了一个新的线性算法，线性局部切空问排列(LLTSA)20。该算法运用切信息作为数据的局部表达，然后将这些局部信息在可以用线性跌射得到的低维空间中排列。它先将每一个样本点邻域的切空间表示为流形的局部几何，再经线性映射实现样本数据从高维空间降维到低维空间，最终将整体嵌入坐标的求解问题转化为矩阵的广义特征值的求解问题。算法步骤：1 近邻选择，构造邻接图G 2 计算局部切坐标3 计算投影向量：a求低维坐标对应近邻重建的目标函数最小化，即i2,.:iikiiLTi

43、TM inY HLS tYYIkH是 k 阶中心化矩阵且/TkHIeek。b 代入线性变换i()TiYX H，且由2HH得i2,().:iTikiiLTiTTM inX HLS tXXIc.:TTTTM inXH BH XS tXH XI其中TTBSWWS,近邻 选择 矩阵1i,nSSSS使 得iiYSY，并 且12(,)nWdiagWWW,且i()kiiWHI。d 求解下列广义特征方程的d 个最小特征值对应的特征向量作为d 个投影向量：=TTXH BH XXH X故由上述特征方程的d 个最小特征值12d,对应特征向量12d,，构成保持近邻重建特性的线性变换矩阵。数据样本的类别信息对于入脸识别

44、是非常重要的资源，但是LLTSA 算法是非监督的学习方法，没有充分利用类别信息。为了提高算法的识别能力，需要对LLTSA 算法的目标函数进行修改，以增加有关判别信息的限定，使原来无监督的学习方法发展为有监督的学习方法。而且为了提高数据的重建能力，算法应将解出的人脸子空间正交化，可称这种流形学习算法为正交判别的线性局部切空间排列(orthogonal discriminant linear local tangent space alignment，ODLLTSA)。21 由于用于特征值分解的矩阵的阶数等于样本点数，因此，当样本点集较大时将无法处理，此外，该方法不能有效处理新来的样本点。一种基于

45、划分的局部切空间排列方法（partitional local tangent space alignment,PLTSA）22被提出以改善这些缺点，它建立在主成分分析算法和LTSA 方法的基础上，解决了主成分分析算法不能求出整体低维坐标和LTSA 中大规模矩阵的特征值分解问题，能够有效处理新来的样本点。PLTSA 是一种非监督的流形学习方法，不能充分利用数据的类别信息，而在人脸识别中数据样本的类别信息是非常重要的资源。为了提高算法的识别能力，需要对 PLTSA 算法进行改进，以增加判别信息的限定，使无监督的学习方法发展为有监督的学习方法。因此提出了一种基于划分的有监督局部切空间排列法（part

46、itional supervised local tangent space alignment PSLTSA）23。4.拉普拉斯特征映射法LE(Laplacian Eigenmap)24 LE 方法将微分流形、谱图论的知识应用于降维之中，使人们对降维过程的认识产生了又一个新的飞跃，拓展了实际中降维方法的应用。基本思想是：在高维空间中距离相隔很近的点投影到低维空间中像也应该相距很近，最终求解归结到求拉普拉斯算子的广义特征值问题。（8）实际上是使用有权图的Laplace矩阵来逼近DR空间中的 Laplace Beltrami 算子，以期达到最优投影的降维算法算法步骤：第一步，构造近邻图G。在数据

47、集 X 中，计算每个样本点ix同其余样本点之间的欧式距离，构造近邻图。寻找相对于每个样本点ix的欧式距离最近的 k 个样本点规定为所求点的近邻点，若数据点ix与jx是邻接的，则图中点ix与jx之间存在一条边。第二步，选择权值，构造权值矩阵W。在近邻图中，为每一条边选择一个权值,ijw，构造权值矩阵W。权值的选择有两种选择方式：1）若点ix与jx是邻接的，则设边的权值为2,ex p(|/)ijijwxxt，否则设,ijw=0；t 是一个比例参数。2）若点ix与jx是邻接的，则设变得权值为,ijw=1，否则设,ijw=0。在方法 1）中，需要选择比例参数t，方法 2）不用选择比例参数t，比较简单。

48、第三步，进行特征映射，计算d 维嵌入。对数据集X 构造的近邻图 G，映射到一条直线，用 y 表示，使得邻接的点尽可能的靠近。设12(,)TNyyyy是一个未知的投影，可以通过在一定约束下，使得下面的目标函数达到最小来求解。2()ijijijyyw用 D 表示对一个对角矩阵，它的每个对角元素为权值矩阵W 的每行所有元素的和，即,i iijjDw，L=D-W是邻接图的Laplacian 矩阵。对任意的y 有222()(2)2Tijijijijijijijyywyyy ywyLy给定约束条件Ty D y=1，以消除坐标尺度对映射y 的影响，最小化上式的和函数，利用矩阵迹的性质和拉格朗日乘子法，即可求

49、解。相当于利用下式计算特征值和特征向量的问题LyD y上述特征方程的最小的d 个非零特征值对应的特征向量12,dyyy，则数据X的低维嵌入表示为12,TdYyyyLE 是局部的非线性方法，其突出特点是与谱图理论有着很紧密的联系。从算法描述中可以看到，拉普拉斯映射和LLE 算法类似，待定参数相同，求解的是稀疏矩阵的广义特征值问题，它能使输入空间中离得很近的点在低维空间也离得很近，故可用于聚类。（12）缺点类似 LLE。LPP局部保留投影（Locality preserving projection，LPP）LPP局部保留投影（Locality preserving projection，LPP）

50、作为 LE 的线性化是其中最早提出的算法。25 LPP算法的主要问题在于建立k 近邻域图，使它能很好地表现数据流形的局部结构。然后，根据建立的 k 邻图来获得图像的投影，最终在投影得到的子空问中进行特征识别。算法把非线性变换转换成了近似的线性形式。所以，一个测试样本要转换到新空间中去，只要乘以从训练集计算得到的线性矩阵即可。这解决了LLE、LE等算法不能显式表示的问题，实际上这种显式转换是非线性流行空间的一种线性回归和近似。与前述全局最优算法相比，这些算法保持了局部信息，同时给出了简便的变换形式，可以说是全局最优和局部最优间的折衷。算法步骤：1 近邻选择，构造邻接图G 2 计算近邻相似度 W

51、3 计算投影向量：a求低维坐标对应近邻重建的目标函数最小化，即2,1()2.:ijijYijTM inyyWS tYYIb 代入线性变换Tyx,得2,1()2.:TTijijYijTTM inxxWS tXXIc.:TTTTM inXL XS tXXI其中 L=D-W,而对角矩阵 D 的对角线元素iiijjDWd 求解下列广义特征方程的d 个最小特征值对应的特征向量作为d 个投影向量：=TTXLXXX故 由 上 述 特 征 方 程 的d 个 最 小 特 征 值12d,对 应 特 征 向 量12d,，构成保持近邻重建特性的线性变换矩阵。5.Hessian 等距映射(HLLE)26Dohono等人

52、拓展了局部线性嵌入(LLE)方法，提出了 Hessian LLE 方法，能够发现流形上局部的潜在等距映射参数。HLLE 先通过估计邻域上的Hessian而构建一矩阵，然后在此矩阵上运用特征值分解而得到最终的低维坐标。Donoho等人认为 Isomap算法要求参数空间的概率测度有凸支撑，进行全局等距映射这个条件过于严格，而局部等距更加合理，从而提出来一种Hessian特征映射算法(Hessian Eigenmap，简称 HLLE)。Hessian特征映射与 Laplacian特征映射的理论框架非常相似，只是使用Hessian算子代替了 Laplacian 算子。算法步骤：1 选择邻域。2 获得切

53、空间坐标。对每个样本点的邻域，计算中心化矩阵TiiXx的最大d 个奇异值对应的右奇异向量，并将这d 个右奇异向量组成矩阵iV。这里kR是一个全 1 的列向量。3 估计 Hessian矩阵iH。4 构造二次型。利用每个邻域的 Hessian矩阵iH，1,2,iN来构造对称矩阵 H，它的元素为(1)/2,11()()ddNllijr irjlrHHH5 计算 H的零空间。计算 H 的最小 d+1 特征值对应的特征向量，去掉对应0特征值的常数向量，剩下的d 个向量21,duu即为所求零空间。6 计算嵌入结果。记矩阵1,1,2,ijl iljlJRUUijd其中1J表示某个样本点的邻域。则1/2TYR

54、U为嵌入结果。Hessian 特征映射具有如下优点：首先，计算较简单，因其考虑局部邻近信息，求解过程为稀疏矩阵的特征值问题，且其解能反映数据集所在低维流形上的内在局部几何信息；其次，其出发点就是针对局部等距于低维欧氏空间中开连通的子集的流形，同时对于这样的开子集并没有要求是凸的。对于这样的流形，HLLE 可以恢复出与流形等距的低维嵌入。该算法合理性建立在其与Laplacian特征映射的关系上，仅使用2 阶的 Hessian算子代替了 Laplacian算子。HLLE 也有一些缺点：HLLE 获取切空间坐标时需要知道流形的本征维数d；对噪声比较敏感，因其使用二阶的Hessian算子，需要估计局部

55、邻域内的二阶导，这对于高维数据样本是很困难的，当流形噪声分布不一致或流形局部低维特征不明显时，获取的切空间坐标可能有较大的偏差，从而影响嵌入结果。由于HLLE选取零空间中一组在某个邻域内保持正交性的基作为嵌入结果，对于不同的邻域，嵌入结果有可能不同。5.最大方差展开(maximum variance unfolding，MVU)27 该算法可看成是PCA 和 MDS 的思想推广后提出的一种非线性流形学习算法。主要思想是：使得远离的数据点其低维坐标展开得尽可能的远，并且约束保持局部近邻点的欧氏距离不变；这个目标可以通过半定规划(SDP)技术学习一个Gram 内积矩阵，然后对这个内积矩阵进行特征分

56、解获得全局低维坐标。算法步骤：1 计算邻接图。2 通过计算半定规划（SDP）求内积矩阵 K。设输 入观 测到 的高 维 数 据(1,2,)DixRin，目 标 输 入 为 低 维 坐标(1,2,)diyRin，要使得远离的数据点其低维坐标展开的尽可能远，并且约束保持局部近邻点的距离，最直观的目标函数定义为使得地位坐标保持局部近邻的距离而最大化任意两点间的距离之和，即：2,2212.:,nijijijijijM axyyns tyyxxxx如 果的 其 中 一 点 为 另 一 点 的 k 近 邻化简2,111=tr()2nnnTijiiiiijiiyyyyKKn2222TTTijijiijjij

57、iijjijyyxxyyyyyyKKK优化问题转化为：保证局部等度规、中心化和半正定等3 个约束条件下使得内积矩阵的迹最大化，即2,i,jax()(1)2,x,.:(2)0(3)0iijjijijiji jMtrKKKKxxxks tKK如 果其 中 一 点 为 另 一 点 的近 邻，即 半 正 定通过半定规划(SDP)学习内积矩阵丘使得保持局部近邻距离和低维数据点中心在原点，实现最大方差展开，如上式。3 对内积矩阵 K 进行特征分解求内在低维坐标：求K 的最大的 d 个特征值1d，(令1d=diag()，)对 应 的 特 征 向 量1,dUvv,则 d 维 坐 标 为TYU。优点：首先，MV

58、P 忠实的保存了类间几何特征和类内几何特征，该算法是基于流形学习的算法。其次，MVP 具备判别能力，适用于分类问题。缺点：MVU 在 SDP 步的时间复杂度大，数据点数就2000 个时目前普通的PC机也要计算几个小时1491。6.非负矩阵分解（Non-negative Matrix actorization，NMF）由于实际问题中矩阵数据很庞大，其中存放的信息分布往往不均匀，因此直接处理这样的矩阵效率低下，就失去了实用意义。为高效处理这些通过矩阵存放的数据，一个关键的必要步骤便是对矩阵进行分解操作。通过矩阵分解，一方面将矩阵的维数进行削减，另一方面也可以对大量的数据进行压缩和概括。NMF 直接

59、将非负分解问题作为带约束的非线性规划问题。NMF 子空间要求子空间的基以及样本在子空间上的投影系数都是非负的，这一约束限制了投影到子空间的数据只能是子空间基的加性组合，而不存在减运算。因此，所获得的对数据表示的非负基所张成的子空间是非正交的和部分无界的，这使得其对数据的表示更为紧凑和更少冗余，表示效率更高，即对数据具有更好的夹逼性，从而更有利于对数据的表示。NMF具有下列特点：(1)分解的结果不含负值，具有明确的物理意义和可解释性，非常适合非负数据处理；(2)能够发现数据内部潜在结构特征，还能够降低数据特征的维数，节省存储和计算资源，这在处理高维数据时就有很明显的优势；(3)NMF 的心理学和

60、生理学构造依据是人眼对整体的感知是由对部分的感知组成的(纯加性的)，即整体是部分的非负线性组合，因此具有智能数据描述的特性；(4)非负性的限制还导致分解结果具有一定的稀疏性，相对稀疏的表示方式能够在一定程度上抑制外界变化(部分遮挡、光照变化、图像旋转)给特征提取带来的不利影响。此外，将 NMF 和一些常用的流行学习方法结合会在分类问题上取得较好的结果。如 Ruicong Zhi 等考虑原始面部图像稀疏表征和邻近结构保留，为面部特征提取提出了一种新算法GSNMF（Graph-Preserving Sparse Nonnegative Matrix Factorization），利用了局部保留投影

61、算法LPP，保留局部结构，加上不可控制的稀疏性约束，在人脸识别中提高了识别率。对图像识别任务主要就是为了获得更好的分类，将原始数据通过基矩阵进行投影映射，因此就是对基矩阵产生了约束，获得更好的局部特征。与有监督算法需要用到所有训练样本的先验信息(如样本所属类别、样本低维坐标等信息)不同，半监督学习算法只需要用到部分样本的类别或其低维信息，更接近实际中的问题，因此与有监督算法相比具有一定优势。但也因为如此，其算法的推广也有一定难度，目前的研究还比较有限。拉普拉斯特征映射算法的作者Belkin等2l将拉普拉斯特征映射算法推广到了半监督学习问题中，首先利用拉普拉斯特征映射算法求出低维嵌入流形，然后在

62、流形上利用标记样本训练分类器进行分类，其对手写字体识别和文本分类的实验证明了算法的有效性。XinYang 等22 给出了半监督的LLE 和 LTSA算法，在通过传统算法得到各样本间的关系矩阵后，利用可获得的部分样本的先验低维坐标信息来求解剩余样本的低维坐标，得到了更精确的低维结果，并验证了该算法解决可视化和视频序列中人的运动手臂跟踪等问题。ZhenyueZhang 等23 分析了基于谱方法的半监督学习，给出了较详细的数学基础和推导，分析了LTSA算法中的特征值问题在半监督学习中的关系，通过实验比较了所提出算法与现有算法，证实了其优越性。冯海亮等 24 将半监督的 LLE算法用于人脸和人脸表情识

63、别，构造样本间距离矩阵时利用部分样本的类别信息来得到一个更能反映样本间关系的矩阵，然后再通过求解该矩阵的特征值、特征向量问题求解低维结果，取得了优于传统流形学习算法的分类效果。四、降维方法总结高维数据集合的降维过程(包括线性、非线性降维)可分解为既相互独立又相互关联的三个阶段：1）数据集结构的描述；2）数据集结构的度量准则：3）基于结构的降维准则。降维方法的提出和形成同样主要包含三个方面的工作，1）建立研究问题的相应数学模型，数据集结构模型；2）对该模型提出相应的度量准则或选择规则；3）建立基于数据集结构的降维准则或损失规则。（4）如何自动判断数据集的非线性是由内在曲率还是映射模型造成的，如何

64、处理断续流形与非断续流形或者变维数流形，目前还没有好的解决方法，这也是流形学习中需要进一步研究的问题。另外，流形学习可以视为数据处理的一个中间过程，要完成最终的目标，需要与其他领域的知识或算法相结合，如与分类算法k-NN，SVM，HMM等相结合实现分类识别目的。目前的流形学习方法存在的主要不足有：(1)流形学习算法计算复杂度高现有流形学习的一个很大瓶颈就是计算复杂度太高，这阻碍了其在实际中的应用。虽然其对非线性数据具有较好的降维效果，但如何有效降低计算量，甚至推广其线性化算法是一个研究热点。线性化是一个很好的方法，但是线性化以后对于高度的非线性问题也一样束手无策。如何得到可处理非线性数据的线性

65、化流形学习方法值得进一步研究。(2)流形学习算法的分类能力较弱在处理分类问题时，多数情况下流形学习算法的性能较传统方法要差。因为，流形学习算法在恢复内在不变量时采用了局部邻域思想，算法本身的稳定性与邻域选择有关，如何在分类意义下获得适当的邻域参数需要进一步的研究。另外，算法中采用了 k-NN 来获得流形结构在观测空间的有限描述，这一方法假定了数据集不存在异常噪声，如果噪声较大时，算法可能覆盖过多的非支撑域以外的空间，从而使得随后的分类算法产生错误的几何投影距离。(3)本征维数的估计我们对流形学习方法的非参数化问题进行了研究，如何自适应的确定流形学习算法中需要的参数，而不是依据经验或人为设定，也

66、是需要解决的问题。在非线性降维过程中，原始数据本征维数d 都是由经验已知或人为设定的，其设定值的大小对低维空间的映射结果有很大影响。d 值过大使映射结果含有过多噪声；d 值过小，本来不同的点在低维空间可能会彼此交叠。目前本征维数的估计方法主要分为以下三种32：(1)特征值或映射方法，(2)几何学习方法，(3)统计学习方法。(4)增量学习目前的大部分流形学习算法只定义在给定的数据集上，通常算法只能得到给定数据集在低维空间中的表示ix，而不能得到从高维空间到低维空间的非线性映射关系1:mdfRR。缺少这一映射关系将无法在不重新构造图的情况下计算新样本的低维表示。如何根据新输入的样本修改映射关系而不重新计算，可以节约大量的计算时间和存储空间。国际上已经有很多学者开始关注这一问题的研究，Law M 等33提出了一种增量 Isomap 算法，只是修改了测地距离的计算方式，节省了一定的时间，但对于算法本身并没有好的改进；OlgaK 等34人在 LLE 基本算法的基础上提出了一种增量 LLE 算法以解决样本外问题。(5)噪声流形学习问题目前的大部分流形学习算法在构造邻域图时采用了k-NN 准则来获得