高维数据的低维表示综述.doc

高维数据的低维表示综述一、研究背景在科学研究中，我们经常要对数据进行处理。而这些数据通常都位于维数较高的空间，例如，当我们处理200个256*256的图片序列时，通常我们将图片拉成一个向量，这样，我们得到了65536*200的数据，如果直接对这些数据进行处理，会有以下问题：首先，会出现所谓的“位数灾难”问题，巨大的计算量将使我们无法忍受；其次，这些数据通常没有反映出数据的本质特征，如果直接对他们进行处理，不会得到理想的结果。所以，通常我们需要首先对数据进行降维，然后对降维后的数据进行处理。降维的基本原理是把数据样本从高维输入空间通过线性或非线性映射投影到一个低维空间，从而找出隐藏在高维观测数据中有意义的低维结构。（8）之所以能对高维数据进行降维，是因为数据的原始表示常常包含大量冗余： 有些变量的变化比测量引入的噪声还要小，因此可以看作是无关的 有些变量和其他的变量有很强的相关性(例如是其他变量的线性组合或是其他函数依赖关系)，可以找到一组新的不相关的变量。（3）从几何的观点来看，降维可以看成是挖掘嵌入在高维数据中的低维线性或非线性流形。这种嵌入保留了原始数据的几何特性，即在高维空间中靠近的点在嵌入空间中也相互靠近。（12）数据降维是以牺牲一部分信息为代价的，把高维数据通过投影映射到低维空间中，势必会造成一些原始信息的损失。所以在对高维数据实施降维的过程中如何在最优的保持原始数据的本质的前提下，实现高维数据的低维表示，是研究的重点。（8）二、降维问题1定义定义1.1降维问题的模型为，其中维数据空间集合（一般为的一个子集），映射是空间集合（一般是，）的一个子集，我们称是数据集（到）的降维。若为的线性函数，则称为线性降维；否则，称为非线性降维。定义1.2 称映射为嵌入映射。（8）2分类针对降维问题的目的和待处理数据集合表象维数的多少，对其进行初步的、粗略的分类如下：硬降维问题：数据维数从几千到几万甚至几十万的变化，此时需要对数据集进行“严厉”的降维，以至于达到便于处理的大小，如图像识别、分类问题以及语音识别问题等。软降维问题：此时数据集合的维数不是太高，降维的需求不是非常的迫切。如社会科学、心理学以及多元统计分析领域皆属于此类。可视化问题：此时数据集合的绝对维数不是很高，但为了便于利用人们的直观洞察力，即为了可视化，我们将其降到2或3维。虽然我们可以可视化更高维数的数据，但是它们通常难于理解，不能产生数据空间的合理形态。若我们还考虑时间变量的话可以对降维问题进行更加进一步的分类，静态降维问题和动态降维问题。后者对于时间序列来讲是有用的，如视频序列、连续语音信号等的处理。（4）3方法介绍如何将高维数据表示在低维空间中，并由此发现其内在结构是高维信息处理研究的关键问题之一。实际处理中，由于线性方法具有简单性、易解释性、可延展性等优点，使得线性降维在高维数据处理中是一个主要研究方向。已有的线性维数约简方法，主要包括主成分分析(Principal Component Analysis，PCA)16、独立成分分析(Independent Component Analysis，ICA)、线性判别分析inear discriminant analysis(LDA) 17、Fisher 判别分析(Fisher Discriminant Analysis，FDA)、主曲线(Principal Curves)、投影寻踪(Projection Pursuit, PP)、多维尺度方法(Multidimensional Scaling，MDS)等。这些方法实际是在不同优化准则之下，寻求最佳线性模型，这也是线性维数约简方法的共性。（10）通过消除数据建模过程中的全局线性假设，Sammon提出了一种非线性映射，即Sammon映射(SM)，该算法能够保持输入样本之间的相关距离；Hastie提出了principal curves(PC)，其定义为通过概率分布或数据中间的光滑曲线；Kohonen基于自组织神经网络提出了self-organizing map(SOM)用来保存数据空间的拓扑属性；Scholkopf等应用Mercer核将PCA扩展为Kernel PCA(KPCA)，该算法在高维空间中计算主分量，而该高维空间由输入空间经某种非线性映射得到。Mika等采用相同的思想来非线性扩展LDA，从而提出了kernel LDA（KLDA）；然而，基于核的方法其难点在于如何选择一个合适的核函数， 一个好的核函数可以使数据在特征空间上线性可分或者近似线性可分，但并不是所选核函数对于每一种数据都适用。核函数的选择反映了人们对问题的先验知识，在实际的应用中往往是经验地选择某种核函数，比如径向基函数 (Radial Basis Function，RBF)。同时，在使用核函数时不必知道具体的特征空间，使得核函数方法缺乏物理直观性，这也是核函数方法的一个缺点。（10）最近兴起的流形学习算法也是用来维数约减的非线性方法，并且依靠它们在探测嵌入在高维空间中低维流形的能力和灵活性而被广泛应用。具有代表性的流形学习算法包括等距映射 (Isometric Mapping，Isomap)、局部线性嵌入方法(Locally Linear Embedding，LLE)、Laplacian 特征映射(Laplacian Eigenmap，LE)、局部切空间排列方法( Local Tangent Space Alignment，LTSA)、Hessian等距映射(Hessian eigenmaps，HLLE)和最大方差展开(maximum variance unfolding，MVU)。其中，LLE运用线性系数，来表达局部几何，该系数能够重建一个给定的样本点利用其近邻点，然后寻找一个低维空间，在该空间中这些线性系数仍然可以用来重建相应的点；ISOMAP作为MDS的变种，能够保存点对之间的全局的测地线距离；LE通过对一个描述了点对之间邻域关系的无向图的操作，来保持数据之间的近邻关系。HLLE先通过估计邻域上的Hessian而构建一矩阵，然后在此矩阵上运用特征值分解而得到最终的低维坐标。LTSA运用局部切信息作为局部几何的表达，然后将这些切信息在全局中排列从而得到最终的全局坐标。MVU不是一个绝对的局部方法而是一个介于局部和全局之间的方法，因为MVU不仅保存近邻点之间的几何关系而且在它的目标函数中考虑了全局点对之间的距离。除了基于谱分析的流形学习的算法，基于概率参数模型，Rowels提出了global coordination(GC)；Teh和Roweis开发了locally linear coordination(LLC)；Brand提出了manifold charting(Charting)。这些方法也属于流形学习的重要范畴。然而，这些非线性的算法却不能够为样本提供一个外在的映射，也就是说，它们很难被应用于识别问题。但是，一些基于谱分析的算法由于其具有特殊的特征分解机制而能够较为容易的扩展为线性算法，其线性化可以通过在解决优化的过程中施加线性逼近来实现。Locality preserving projection(LPP)作为LE的线性化是其中最早提出的算法。后来提出的还包括neighborhood preserving embedding(NPE)，LLE的线性化扩展，和orthogonal neighborhood preserving projections(ONPP)，LLE的正交线性化扩展。这种线性化扩展使流形学习的思想更能够应用到现实世界中。图1.1给出了以上所提提及的降维算法的分类图。在谱方法的线性化扩展中，LPP可以被看作为基于图结构的最具代表性的算法，在接下来的几年中，又不断地有这种基于图的算法被提出，从而进一步完善了这种基于图的框架。Cai等对LPP算法分别对监督设置和非监督设置两种情况作了系统的分析，并且将LDA用这种基于图的框架重新公式化。Yan等提出了一种一般性的框架即“图嵌入”，来统一各种各样的降维算法。基于此种框架，一种新的线性算法，marginal fisher analysis（MFA）将开发出来。MFA不同于LPP其只用一个图来描述数据的几何结构，该算法采用了两个图，其中一个为固有图（intrinsic graph），它用来刻画数据的类内紧凑性；而另一个图为惩罚图（penalty graph），用来描述数据类间的分离性。因此，MFA比LPP更具有判别性。Chen等同时提出的local discriminant embedding（LDE）算法在本质上与MFA的思想是相同的。（5）非线性降维方法与线性降维方法相比的一个显著特点是，分析中的局部性(数据集合经常满足的一个简单假设)。原因在于对数据集合的内蕴结构而言，有下列特性：由泰勒定理，任何可微函数在一点的充分小的邻域之内满足线性性。形象的来讲，相当于认为曲面流形可由大小不一的局部线性块拼接而成；数据流形经常是由许多可分割的子流形所组成；数据流形的本征维数沿着流形不断的发生变化，只有局部性才能抓住其根本特性。（4） 降维线性流行学习概率参数模型全局谱分析局部全局局部早期的非线性PCAMVUISOMAPChartingLLCKernelPCSMSOMGCLDALPPNPELLELLTSAONPPLELTSAHLLE线性化三、常见降维方法（一）线性 1. 主成分分析(Principal Component Aanlysis PCA) 1PCA将方差的大小作为衡量信息量多少的标准，认为方差越大提供的信息越多，反之提供的信息就越少。它是在损失很少的信息的前提下把多个指标转化为几个综合指标的一种多元统计方法。它具有概念简单，计算方便以及最优线性重构误差等优良的特性。PCA是一种全局算法，它可以较好地揭示具有线性结构的高维数据集的全局分布。然而对于嵌入在高维空间中具有非线性流形结构的数据，PCA很难学习出隐含在数据集中的低维流形结构。PCA假设数据之间的关系是线性的。它在保存原始高维数据协方差结构的基础上计算低维表达，也就是最大化总体方差。它的目标函数可以写为：其中，且为总体离散矩阵：。对转换矩阵做尺度约束，其中为单位矩阵。则目标函数可以写为：，上式问题可以转化为的标准的特征值问题：PCA的最优转换矩阵为的d个最大的特征值所对应的d个m维特征向量。2.线性判别法(Linear Discriminant Analysis LDA) 2其基本思想是投影，首先找出特征向量，把这些数据投影到一个低维的方向，使得投影后不同的组之间尽可能的分开，而同一组内的的样本比较靠拢，然后在新空间中对样本进行分类。通过最小化类内离散矩阵的秩而最大化类间离散矩阵的秩，来寻找一个子空间来区分不同的类别。和分别定义如下：其中，是第i个类中样本的个数；是第i个样本中第j个样本。为第i个类的质心；用来表示所有样本的质心，C为样本的类别数。LDA则有以下的优化准则： 上述的优化可以转化为求解一个广义的特征分解问题：且最优的解为d个特征向量其对应于d个最大的非零特征值。3.投影寻踪(Projection Pursuit PP) 3基本思想主要来源人们对低维空间几何图形的直观理解，它包含俩个方面的含义：其一是投影(Projection)，把高维空间中数据投影到低维空间；其二是寻踪(Pursuit)，利用低维空间投影数据的几何分布形念，发现人们感兴趣的数据内在特征和相应的投影方向，同时排除与数据结构和特征无关的或关系比较小的变量干扰。4. 多维尺度分析(Multidimensional Scalar ，MDS) 4主要思想是：根据数据点间的欧氏距离，构造关系矩阵，为了尽可能地保持每对观测数据点之间的欧氏距离，只需对此关系矩阵进行特征分解，从而获得每个数据在低维空间中的低维坐标。算法步骤：1计算观测空间中任意两点欧式距离，构造n阶平方欧式距离矩阵A2将矩阵A进行双中心化计算，即计算。若设阶矩阵（常称之为中心化矩阵），将矩阵H左乘和右乘A的两边（常称之为双中心化）。3计算低维坐标Y。即将B奇异值分解，设B的最大的d个特征值，对应特征向量，则d维坐标为。（二）非线性流形学习旨在发现高维数据集分布的内在规律性，其基本思想是：高维观测空间中的点由少数独立变量的共同作用在观测空间张成一个流形，如果能有效地展开观测空间卷曲的流形或发现内在的主要变量，就可以对该数据集进行降维。现在形式化地概括流形学习这一维数约简过程：假设数据是均匀采样于一个高维欧氏空间中的低维流形，流形学习就是从高维采样数据中恢复低维流形结构，即找到高维空间中的低维流形，并求出相应的嵌入映射，以实现维数约简或者数据可视化。它是从观测到的现象中去寻找事物的本质，找到产生数据的内在规律。用数学语言可以这样描述，令且是一个光滑的嵌套，流形学习的目标是基于上的一个给定被观测数据集合去恢复和，在中隐藏的数据被随机地产生，然后被映射到观测空间，使得。（12）1.局部线性嵌入方法 LLE (Locally Linear Embedding) 5LLE在保存原始高维数据邻域线性结构的基础上计算低维表达。（5）是一种局部方法，它试图保持数据的局部几何特征，就本质上来说，它是将流形上的近邻点映射到低维空间的近邻。（9）图2 非线性降维实例 B是从 A中提取的样本点（三维），通过非线性降维算法 LLE将数据映射到二维空间中（C），从C图中的颜色可以看出通过 LLE算法处理后的数据能很好的保持原有数据的邻域特性(引用文献6)主要思想：对一组具有嵌套(流形)的数据集，在嵌套空问与内在低维空间局部邻域问的关系应该不变，即在嵌套空间中每个采样点可以用它的近邻点线性表示，在低维空间中保持每个邻域中的权值不变，重构原数据点，使重构误差最小。(8)LLE的实现过程步骤：LLE方法可以归结为三步：(1) 寻找每个样本点的k个近邻点；把相对于所求样本点距离最近的k个样本点规定为所求样本点的k个邻近点。k是一个预先给定值。距离的计算既可采用欧式距离也可采用Dijkstra距离。Dijkstra距离是一种测地距离，它能够保持样本点之间的曲面特性。(2)由每个样本点的近邻点计算出该样本点的局部重建权值矩阵；这里定义一个成本函数，如下式，来测量重建误差：解得，时其中，和是的近邻点；为了使重建误差最小化，权重服从一种重要的对称性，即对所有特定数据点来说，它们和它们邻居点之间经过旋转、重排、转换等变换后，它们之间的对称性是不变的。由此可见重建权重能够描述每个邻居本质的几何特性。因此可以认为原始数据空间内的局部几何特征同在流形局部块上的几何特征是完全等效的。（3）由该样本点的局部重建权值矩阵和其近邻点计算出该样本点的输出值。映射条件满足如下成本函数：要使低维重构误差最小，计算得出，Y等价于求M的特征向量，其中在处理过程中，将M的特征值从小到大排列，第一个特征值几乎接近于零，那么舍去第一个特征值。通常取第2到m+l之间的特征值所对应的特征向量作为输出结果。优点：LLE算法可以学习任意维的局部线性的低维流形，就是用局部性用局部的的线性来逼近全局的非线性，保持局部的几何结构不变，通过相互重叠的局部邻域来提供整体的信息，从而保持整体的几何性质。LLE既有非线性的特点又具有线性方法的优点。（8）同时由重构成本函数最小化得到的最优权值遵循对称特性，每个点的近邻权值在平移、旋转、伸缩变换下是保持不变的LLE算法有解析的全局最优解，不需迭代，低维嵌入的计算归结为稀疏矩阵特征值的计算，这样计算复杂度相对较小。缺点：LLE算法要求所学习的流形只能是不闭合的且在局部是线性的，还要求样本在流形上是稠密采样的。另外，该算法的参数选择不确定，对样本中的噪音很敏感。（12）此外，(1)对于一个新样本点。没有显式的方法把该点嵌入到低维空间中，这在检索应用中不适用。(2)新空间的维数没有显式准则进行确定，只有通过经验的方法。(3)LLE没有利用数据点的类信息。在分类问题中，对于有类标号的样本数据，LLE无能为力。SLLE算法7Dick和Robert提出一种针对有监督的 LLE算法，即Supervised linear locally embedding (SLLE)传统的LLE算法在第一步时是根据样本点间的欧氏距离来寻找k个近邻点，而SLLE在处理这一步时增加了样本点的类别信息，SLLE算法的其余步骤同LLE算法是一致的。SLLE算法在计算点与点之间的距离时有两种方法。SLLE1：第一种方法是采用下式来修正点与点之间的距离公式如下所示其中：是计算后的距离D是最初采用的距离；max(D)是表示类与类之间的最大距离；取0或者1，当两点属于同类时，取为0，否则取1；是控制点集之间的距离参数，是一个经验参数。当取为零时，此时的SLLE和 LLE 算法相同。这个方法引入了一个参数，它是一种经验参数，对实验的结果有很大的影响，下面介绍一种非参数的方法。SLLE2：求解点与点之间的距离，目的在于是寻找样本点的近邻点。SLLE2的方法在寻找近邻点时，不是在全局样本中寻找近邻点，而是在每个点所在类的样本中寻找近邻点，也就是说，在类内中寻找样本点的近邻点。这个方法固然没有采用参数的方法，但是如果某一类的样本个数小于k，那么这种方法必将失败，则每个类的样本个数在相当多的情况下 可以采用这种方法。RLLE算法8当在做聚类分析且采用LLE算法对数据进行降维时，如果数据中存在着许多离异点的情况，那么降维后的结果将会发生变异，通常是第一维或者是第二维的数据发生跳跃式的变化，或者分布在某几条直线上，这将会给聚类带来很大的麻烦，其实当离异点超过LLE算法中的k值时，这种现象将会发生。A.Hadid和M.Pietikinen提出一种 Robust Locally Linear Embedding (RLLE)方法。它是针对存在有离异点的情况下，对样本的一种无监督的非线性降维方法。邻域保持嵌入算法NPE算法9NPE从本质上说是局部线性嵌入(local linear embedding，LLE)的线性逼近。给定数据集X，采用与LLE相同的方法构建数据集上的近邻图。NPE针对LLE算法的out-of-sample问题提出的，该算法通过最小化局部相似离散度寻找投影方向，有效的保持了数据间的相似几何结构，取得了不错效果，已被广泛地应用到文档分析、机器学习和模拟识别等领域。NPE假定每个局部近邻都是线性的。算法步骤：1近邻选择，构造邻接图G2计算近邻重建权W3计算投影向量：a求低维坐标对应近邻重建的目标函数最小化，即b代入线性变换,得c 其中d求解下列广义特征方程的d个最小特征值对应的特征向量作为d个投影向量：故由上述特征方程的d个最小特征值对应特征向量，构成保持近邻重建特性的线性变换矩阵。缺点：NPE在保持数据空间的局部相似信息时，不能较有效地保持差异信息，特别是高维非线性数据间的差异信息。如在人脸识别应用中，人脸图像的识别容易受光照、表情等非理想条件变化的影响，这些非理想情况会使得同一个人的不同图像之间的差异大于不同人图像之间的差异，从而导致识别错误。NPE算法通过式实现了数据到新空间的线性变换。显然，这种线性变换实现的数据变换是一种显式形式，这样就解决了LLE算法没有显式映射函数的问题。LLE算法是非监督的学习方法，没有充分利用类别信息，为了提高算法的识别能力，于是有了LLE的正交线性化扩展，orthogonal neighborhood preserving projections(ONPP)10 11。 张长水等人12在LLE的基础上提出一种从低维嵌入空间向高维空间映射的方法，并在多姿态人脸图像的重构实验中得到有效的验证，进一步完善了非线性降维方法。 2. 等距映射法 ISOMAP (Isometric Map) 13ISOMAP认为当数据集具有嵌入流形结构时，可以根据保距映射来获得观测空间数据集在低维结构的对应描述。基本思想：ISOMAP通过测地线距离来描述各点之间的相互关系，在全局意义下，通过寻找各点在图意义下的最短路径来获得点与点之间的距离，然后利用经典的MDS算法得到低维的嵌入坐标。因此ISOMAP可认为是MDS算法的变种。（5）图3 ISOMAP算法示意图使用前提条件：高维数据所在的低维流形与欧氏空间的一个子集是整体等距的；与数据所在的流形等距的欧氏空问的子集是一个凸集。主要步骤：(1)构造局部邻域。首先对数据集，计算任意两个样本向量和的欧式距离，将每一个点与所有的点进行比较，当两点之间的距离小于固定的半径（或i是j的K-邻域）时，我们就认为它们是相邻的，将其连接起来，该边的长度,则得到邻域图G。(2)计算最短距离。在图G中，设任意两个样本向量和之间的最短距离为。若和之间存在连线，的初始值为，否则令。对所有的k=1,2,n这样得到矩阵，它是图G中所有点对的最短路径组成的。(3)构造d维嵌入。用MDS方法构造一个保持本征几何结构的d维嵌入到空间Y。H是与同阶的单位矩阵，对进行特征分解，取最大的前d个特征值和对应的特征向量，令为第p个特征向量的第i个成分，则对应的数据低维表示为。优点： 适用于学习内部平坦的低维流形，ISOMAP结合了线性算法(如PCA和MDS)的主要特征计算的有效性、全局的优化性和渐进收敛性等。这种用测地距离来代替传统的欧氏距离的方法，可更有效的在低维空间来表达高维空间的数据，减少降维后损失的数据信息。缺点：不适于学习有较大内在曲率的流形。在噪声干扰下，Isomap用于可视化会有不稳定现象，取较大的邻域会产生短路现象，即低维流形中不同邻域部分的点投影后出现明显的混杂现象。选取较小的邻域，虽然能够保证整体结构的稳定，但低维投影结果会产生大量“空洞”，或使最短路径算法重构的图不连通。降维维数的确定通常是在本质维数未知的情况下进行的，经多次实验绘制残差曲线观察得到。Isomap算法计算图上2点间的最短距离可采用Dijkstra算法，但执行起来仍然比较慢。（12）(l)当与高维流形等距的欧氏空间的子集不是凸型时，即当高维空间存在“空洞”时，要计算高维观测空间上任意样本点之间的距离很有可能发生弯曲异常，如果这样就会影响低维嵌入结果的表示。(2)等距特征映射算法在数据拓扑空间有可能是不稳定的。因为如果选择的邻域过小，就会导致邻域图不连通，如果选择的邻域太大，又可能导致短路。(3)使用Isomap算法恢复非线性流形的几何结构的时候，所需的计算时间比较多，这主要是花在计算样本点之间的最短路径上。由于已有的流形学习算法对噪音和算法参数都比较敏感，詹德川、周志华14针对Isomap算法，提出了一种新方法，通过引入集成学习技术，扩大了可以产生有效可视化结果的输入参数范围，并且降低了对噪音的敏感性。另外，赵连伟15等人完善了Isomap的理论基础，给出了连续流形与其低维参数空间等距映射的存在性证明，并区分了嵌入空间维数、高维数据的固有维数与流形维数这些容易混淆的概念，证明如果高维数据空间存在环状流形，流形维数则要小于嵌入空间维数他们还给出一种有效的环状流形发现算法，以得到正确的低维参数空间。特别地，周志华等16提出了一种方法，可以从放大因子和延伸方向两方面显示出观测空间的高维数据与降维后的低维数据之间的联系，并实验比较了2种著名流形学习算法(Isomap和LLE)的性能。文献17中，作者提出了一种基于Isomap的监督算法Weightedlso。在分类问题中，理想情况下属于同一类的样本在测量空间中应离得近一些，反之，不同类的样本则离得远一些。因此，作者在基本Isomap算法的第一步，计算各样本点间的欧氏距离时引进了一个常量参数，用来重新度量同一类样本间的距离，使它们离得更近。Weightedlso算法虽然在一定程度上克服了流形学习方法分类效果较差的缺点，但在引入常量参数重新度量同类样本的距离时，由于噪声的影响，破坏了样本间的本质结构，使其可视化应用效果下降。在分类问题中，权值w在很大程度上影响着分类的结果，如何选取w值得进一步研究。由于Weightedlso的不足，Xin Geng,De Chuan Zhan等18提出了另一种基于Isomap的监督算法SIsomap。该方法同样是修改了Isomap算法的第一步，用已知的样本所属类别信息重新定义了样本间的距离。3局部切空间排列算法 LTSA (local tangent space alignment)19LTSA是一种基于切空间的流形学习方法，它通过逼近每一样本点的切空间来构建低维流形的局部几何，然后利用局部切空间排列求出整体低维嵌入坐标。主要思想：找出每个数据点的近邻点，用邻域中低维切空间的坐标近似表示局部的非线性几何特征，再通过变换矩阵将各数据点邻域切空间的局部坐标映射到一个同一的全局坐标上，从而实现高维数据降维，即从n维数据中得到一个全局的d维坐标。(8)算法步骤：第一步：构造邻域。对于每个数据点，找出它的包括它自身在内的k个邻域点，构成矩阵。第二步：局部线性投影。对于每个样本点的邻域，计算中心化矩阵的最大d个奇异值对应的左奇异向量，并将这d个左奇异向量组成矩阵。1由计算得出左奇异向量U，取出U的前d列构成矩阵（即为点的切空间的近似）；2计算各个邻域点在该切空间的投影：第三步：局部坐标系统的排列。对每个邻域的局部切空间坐标，构造转换矩阵。通过最小化的求解，最后化解可通过计算一个矩阵从第2小到第d+1小的特征值所对应的特征向量。其中是的广义Moor-Penrose逆。优缺点：LTSA能够有效地学习体现数据集低维流形结构的整体嵌入坐标，但它也存在两方面的不足：一方面算法中用于特征值分解的矩阵的阶数等于样本数，样本集较大时将无法处理；另一方面算法不能有效处理新来的样本点。（12）对此，提出了一些相应的改进算法。但LTSA也面临着同HLLE类似的一些问题：LTSA所反映的局部结构是它的局部d维坐标系统，因此，由于噪声等因素的影响，当数据集的局部低维特征不明显或者不是d维的时候，它的局部邻域到局部切空间的投影距离往往并不小。此时，构造的重建误差也不会小，这样LTSA可能就无法得到理想的嵌入结果。此外，LTSA对样本点的密度和曲率的变化的影响比较敏感，样本点的密度和曲率的变化使得样本点到流形局部切空间的投影产生偏差，而LTSA构造排列矩阵的模型并没有将这种偏差计入考虑范围。这使得对于样本点密度和曲率变化较大的流形，LTSA的嵌入结果可能会出现扭曲现象。线性局部切空问排列(LLTSA)针对LTSA算法不能为新的测试样本提供一个明确的从高维到低维的映射，也就是所谓的“Out of Sample”问题。提出了一个新的线性算法，线性局部切空问排列(LLTSA)20。该算法运用切信息作为数据的局部表达，然后将这些局部信息在可以用线性跌射得到的低维空间中排列。它先将每一个样本点邻域的切空间表示为流形的局部几何，再经线性映射实现样本数据从高维空间降维到低维空间，最终将整体嵌入坐标的求解问题转化为矩阵的广义特征值的求解问题。算法步骤：1近邻选择，构造邻接图G2计算局部切坐标3计算投影向量：a求低维坐标对应近邻重建的目标函数最小化，即 是k阶中心化矩阵且。b代入线性变换，且由得c 其中,近邻选择矩阵使得，并且,且。d求解下列广义特征方程的d个最小特征值对应的特征向量作为d个投影向量：故由上述特征方程的d个最小特征值对应特征向量，构成保持近邻重建特性的线性变换矩阵。数据样本的类别信息对于入脸识别是非常重要的资源，但是LLTSA算法是非监督的学习方法，没有充分利用类别信息。为了提高算法的识别能力，需要对LLTSA算法的目标函数进行修改，以增加有关判别信息的限定，使原来无监督的学习方法发展为有监督的学习方法。而且为了提高数据的重建能力，算法应将解出的人脸子空间正交化，可称这种流形学习算法为正交判别的线性局部切空间排列(orthogonal discriminant linear local tangent space alignment，ODLLTSA)。21由于用于特征值分解的矩阵的阶数等于样本点数，因此，当样本点集较大时将无法处理，此外，该方法不能有效处理新来的样本点。一种基于划分的局部切空间排列方法（partitional local tangent space alignment ,PLTSA）22被提出以改善这些缺点，它建立在主成分分析算法和LTSA方法的基础上，解决了主成分分析算法不能求出整体低维坐标和 LTSA 中大规模矩阵的特征值分解问题，能够有效处理新来的样本点。PLTSA是一种非监督的流形学习方法，不能充分利用数据的类别信息，而在人脸识别中数据样本的类别信息是非常重要的资源。为了提高算法的识别能力，需要对PLTSA算法进行改进，以增加判别信息的限定，使无监督的学习方法发展为有监督的学习方法。因此提出了一种基于划分的有监督局部切空间排列法（partitional supervised local tangent space alignment PSLTSA）23。4.拉普拉斯特征映射法 LE (Laplacian Eigenmap) 24LE方法将微分流形、谱图论的知识应用于降维之中，使人们对降维过程的认识产生了又一个新的飞跃，拓展了实际中降维方法的应用。基本思想是：在高维空间中距离相隔很近的点投影到低维空间中像也应该相距很近，最终求解归结到求拉普拉斯算子的广义特征值问题。（8）实际上是使用有权图的 Laplace矩阵来逼近 空间中的 Laplace Beltrami 算子，以期达到最优投影的降维算法算法步骤：第一步，构造近邻图G。在数据集X中，计算每个样本点同其余样本点之间的欧式距离，构造近邻图。寻找相对于每个样本点的欧式距离最近的k个样本点规定为所求点的近邻点，若数据点与是邻接的，则图中点与之间存在一条边。第二步，选择权值，构造权值矩阵W。在近邻图中，为每一条边选择一个权值，构造权值矩阵W。权值的选择有两种选择方式：1）若点与是邻接的，则设边的权值为，否则设=0；t是一个比例参数。2）若点与是邻接的，则设变得权值为=1，否则设=0。在方法1）中，需要选择比例参数t，方法2）不用选择比例参数t，比较简单。第三步，进行特征映射，计算d维嵌入。对数据集X构造的近邻图G，映射到一条直线，用y表示，使得邻接的点尽可能的靠近。设是一个未知的投影，可以通过在一定约束下，使得下面的目标函数达到最小来求解。用D表示对一个对角矩阵，它的每个对角元素为权值矩阵W的每行所有元素的和，即，L=D-W是邻接图的Laplacian矩阵。对任意的y有给定约束条件=1，以消除坐标尺度对映射y的影响，最小化上式的和函数，利用矩阵迹的性质和拉格朗日乘子法，即可求解。相当于利用下式计算特征值和特征向量的问题上述特征方程的最小的d个非零特征值对应的特征向量，则数据X的低维嵌入表示为LE是局部的非线性方法，其突出特点是与谱图理论有着很紧密的联系。从算法描述中可以看到，拉普拉斯映射和LLE算法类似，待定参数相同，求解的是稀疏矩阵的广义特征值问题，它能使输入空间中离得很近的点在低维空间也离得很近，故可用于聚类。（12）缺点类似LLE。LPP局部保留投影（Locality preserving projection，LPP）LPP局部保留投影（Locality preserving projection，LPP）作为LE的线性化是其中最早提出的算法。25LPP算法的主要问题在于建立k近邻域图，使它能很好地表现数据流形的局部结构。然后，根据建立的k邻图来获得图像的投影，最终在投影得到的子空问中进行特征识别。算法把非线性变换转换成了近似的线性形式。所以，一个测试样本要转换到新空间中去，只要乘以从训练集计算得到的线性矩阵即可。这解决了LLE、LE等算法不能显式表示的问题，实际上这种显式转换是非线性流行空间的一种线性回归和近似。与前述全局最优算法相比，这些算法保持了局部信息，同时给出了简便的变换形式，可以说是全局最优和局部最优间的折衷。算法步骤：1近邻选择，构造邻接图G2计算近邻相似度W3计算投影向量：a求低维坐标对应近邻重建的目标函数最小化，即b代入线性变换,得c 其中L=D-W,而对角矩阵D的对角线元素d求解下列广义特征方程的d个最小特征值对应的特征向量作为d个投影向量：故由上述特征方程的d个最小特征值对应特征向量，构成保持近邻重建特性的线性变换矩阵。5. Hessian等距映射(HLLE) 26Dohono等人拓展了局部线性嵌入(LLE)方法，提出了Hessian LLE方法，能够发现流形上局部的潜在等距映射参数。HLLE先通过估计邻域上的Hessian而构建一矩阵，然后在此矩阵上运用特征值分解而得到最终的低维坐标。Donoho等人认为Isomap算法要求参数空间的概率测度有凸支撑，进行全局等距映射这个条件过于严格，而局部等距更加合理，从而提出来一种Hessian特征映射算法(Hessian Eigenmap，简称HLLE)。Hessian特征映射与Laplacian特征映射的理论框架非常相似，只是使用Hessian算子代替了Laplacian算子。算法步骤：1选择邻域。2获得切空间坐标。对每个样本点的邻域，计算中心化矩阵的最大d个奇异值对应的右奇异向量，并将这d个右奇异向量组成矩阵。这里是一个全1的列向量。3估计Hessian矩阵。4构造二次型。利用每个邻域的Hessian矩阵，来构造对称矩阵H，它的元素为5计算H的零空间。计算H的最小d+1特征值对应的特征向量，去掉对应0特征值的常数向量，剩下的d个向量即为所求零空间。6计算嵌入结果。记矩阵其中表示某个样本点的邻域。则为嵌入结果。Hessian特征映射具有如下优点：首先，计算较简单，因其考虑局部邻近信息，求解过程为稀疏矩阵的特征值问题，且其解能反映数据集所在低维流形上的内在局部几何信息；其次，其出发点就是针对局部等距于低维欧氏空间中开连通的子集的流形，同时对于这样的开子集并没有要求是凸的。对于这样的流形，HLLE可以恢复出与流形等距的低维嵌入。该算法合理性建立在其与Laplacian特征映射的关系上，仅使用2阶的Hessian算子代替了Laplacian算子。HLLE也有一些缺点：HLLE获取切空间坐标时需要知道流形的本征维数d；对噪声比较敏感，因其使用二阶的Hessian算子，需要估计局部邻域内的二阶导，这对于高维数据样本是很困难的，当流形噪声分布不一致或流形局部低维特征不明显时，获取的切空间坐标可能有较大的偏差，从而影响嵌入结果。由于HLLE选取零空间中一组在某个邻域内保持正交性的基作为嵌入结果，对于不同的邻域，嵌入结果有可能不同。5.最大方差展开(maximum variance unfolding，MVU) 27该算法可看成是PCA和MDS的思想推广后提出的一种非线性流形学习算法。主要思想是：使得远离的数据点其低维坐标展开得尽可能的远，并且约束保持局部近邻点的欧氏距离不变；这个目标可以通过半定规划(SDP)技术学习一个Gram内积矩阵，然后对这个内积矩阵进行特征分解获得全局低维坐标。算法步骤：1计算邻接图。2通过计算半定规划（SDP）求内积矩阵K。设输入观测到的高维数据，目标输入为低维坐标，要使得远离的数据点其低维坐标展开的尽可能远，并且约束保持局部近邻点的距离，最直观的目标函数定义为使得地位坐标保持局部近邻的距离而最大化任意两点间的距离之和，即：化简优化问题转化为：保证局部等度规、中心化和半正定等3个约束条件下使得内积矩阵的迹最大化，即通过半定规划(SDP)学习内积矩阵丘使得保持局部近邻距离和低维数据点中心在原点，实现最大方差展开，如上式。3对内积矩阵K进行特征分解求内在低维坐标：求K的最大的d个特征值(令)对应的特征向量,则d维坐标为。优点：首先，MVP忠实的保存了类间几何特征和类内几何特征，该算法是基于流形学习的算法。其次，MVP具备判别能力，适用于分类问题。缺点：MVU在SDP步的时间复杂度大，数据点数就2000个时目前普通的PC机也要计算几个小时1491。6.非负矩阵分解（Non-negative Matrix actorization，NMF）由于实际问题中矩阵数据很庞大，其中存放的信息分布往往不均匀，因此直接处理这样的矩阵效率低下，就失去了实用意义。为高效处理这些通过矩阵存放的数据，一个关键的必要步骤便是对矩阵进行分解操作。通过矩阵分解，一方面将矩阵的维数进行削减，另一方面也可以对大量的数据进行压缩和概括。NMF 直接将非负分解问题作为带约束的非线性规划问题。NMF 子空间要求子空间的基以及样本在子空间上的投影系数都是非负的，这一约束限制了投影到子空间的数据只能是子空间基的加性组合，而不存在减运算。因此，所获得的对数据表示的非负基所张成的子空间是非正交的和部分无界的，这使得其对数据的表示更为紧凑和更少冗余，表示效率更高，即对数据具有更好的夹逼性，从而更有利于对数据的表示。NMF具有下列特点：(1) 分解的结果不含负值，具有明确的物理意义和可解释性，非常适合非负数据处理；(2)能够发现数据内部潜在结构特征，还能够降低数据特征的维数，节省存储和计算资源，这在处理高维数据时就有很明显的优势；(3) NMF的心理学和生理学构造依据是人眼对整体的感知是由对部分的感知组成的(纯加性的)，即整体是部分的非负线性组合，因此具有智能数据描述的特性；(4)非负性的限制还导致分解结果具有一定的稀疏性，相对稀疏的表示方式能够在一定程度上抑制外界变化(部分遮挡、光照变化、图像旋转)给特征提取带来的不利影响。此外，将NMF和一些常用的流行学习方法结合会在分类问题上取得较好的结果。如Ruicong Zhi等考虑原始面部图像稀疏表征和邻近结构保留，为面部特征提取提出了一种新算法GSNMF（Graph-Preserving Sparse Nonnegative Matrix Factorization），利用了局部保留投影算法LPP，保留局部结构，加上不可控制的稀疏性约束，在人脸识别中提高了识别率。对图像识别任务主要就是为了获得更好的分类，将原始数据通过基矩阵进行投影映射，因此就是对基矩阵产生了约束，获得更好的局部特征。与有监督算法需要用到所有训练样本的先验信息(如样本所属类别、样本低维坐标等信息)不同，半监督学习算法只需要用到部分样本的类别或其低维信息，更接近实际中的问题，因此与有监督算法相比具有一定优势。但也因为如此，其算法的推广也有一定难度，目前的研究还比较有限。拉普拉斯特征映射算法的作者Belkin等2l将拉普拉斯特征映射算法推广到了半监督学习问题中，首先利用拉普拉斯特征映射算法求出低维嵌入流形，然后在流形上利用标记样本训练分类器进行分类，其对手写字体识别和文本分类的实验证明了算法的有效性。XinYang等22给出了半监督的LLE和LTSA算法，在通过传统算法得到各样本间的关系矩阵后，利用可获得的部分样本的先验低维坐标信息来求解剩余样本的低维坐标，得到了更精确的低维结果，并验证了该算法解决可视化和视频序列中人的运动手臂跟踪等问题。ZhenyueZhang等23分析了基于谱方法的半监督学习，给出了较详细的数学基础和推导，分析了LTSA算法中的特征值问题在半监督学习中的关系，通过实验比较了所提出算法与现有算法，证实了其优越性。冯海亮等24将半监督的LLE算法用于人脸和人脸表情识别，构造样本间距离矩阵时利用部分样本的类别信息来得到一个更能反映样本间关系的矩阵，然后再通过求解该矩阵的特征值、特征向量问题求解低维结果，取得了优于传统流形学习算法的分类效果。四、降维方法总结高维数据集合的降维过程(包括线性、非线性降维)可分解为既相互独立又相互关联的三个阶段：1）数据集结构的描述；2）数据集结构的度量准则：3）基于结构的降维准则。降维方法的提出和形成同样主要包含三个方面的工作，1）建立研究问题的相应数学模型，数据集结构模型；2）对该模型提出相应的度量准则或选择规则；3）建立基于数据集结构的降维准则或损失规则。（4）如何自动判断数据集的非线性是由内在曲率还是映射模型造成的，如何处理断续流形与非断续流形或者变维数流形，目前还没有好的解决方法，这也是流形学习中需要进一步研究的问题。另外，流形学习可以视为数据处理的一个中间过程，要完成最终的目标，需要与其他领域的知识或算法相结合，如与分类算法k-NN，SVM，HMM等相结合实现分类识别目的。目前的流形学习方法存在的主要不足有：(1) 流形学习算法计算复杂度高现有流形学习的一个很大瓶颈就是计算复杂度太高，这阻碍了其在实际中的应用。虽然其对非线性数据具有较好的降维效果，但如何有效降低计算量，甚至推广其线性化算法是一个研究热点。线性化是一个很好的方法，但是线性化以后对于高度的非线性问题也一样束手无策。如何得到可处理非线性数据的线性化流形学习方法值得进一步研究。(2) 流形学习算法的分类能力较弱在处理分类问题时，多数情况下流形学习算法的性能较传统方法要差。因为，流形学习算法在恢复内在不变量时采用了局部邻域思想，算法本身的稳定性与邻域选择有关，如何在分类意义下获得适当的邻域参数需要进一步的研究。另外，算法中采用了k-NN来获得流形结构在观测空间的有限描述，这一方法假定了数据集不存在异常噪声，如果噪声较大时，算法可能覆盖过多的非支撑域以外的空间，从而使得随后的分类算法产生错误的几何投影距离。(3) 本征维数的估计我们对流形学习方法的非参数化问题进行了研究，如何自适应的确定流形学习算法中需要的参数，而不是依据经验或人为设定，也是需要解决的问题。在非线性降维过程中，原始数据本征维数d都是由经验已知或人为设定的，其设定值的大小对低维空间的映射结果有很大影响。d值过大使映射结果含有过多噪声；d值过小，本来不同的点在低维空间可能会彼此交