高维数据的低维表示综述 - 图文

高维数据的低维表示综述

一、研究背景

在科学研究中，我们经常要对数据进行处理。而这些数据通常都位于维数较高的空间，例如，当我们处理200个256*256的图片序列时，通常我们将图片拉成一个向量，这样，我们得到了65536*200的数据，如果直接对这些数据进行处理，会有以下问题：首先，会出现所谓的“位数灾难”问题，巨大的计算量将使我们无法忍受；其次，这些数据通常没有反映出数据的本质特征，如果直接对他们进行处理，不会得到理想的结果。所以，通常我们需要首先对数据进行降维，然后对降维后的数据进行处理。

降维的基本原理是把数据样本从高维输入空间通过线性或非线性映射投影到一个低维空间，从而找出隐藏在高维观测数据中有意义的低维结构。（8）

之所以能对高维数据进行降维，是因为数据的原始表示常常包含大量冗余： · 有些变量的变化比测量引入的噪声还要小，因此可以看作是无关的 · 有些变量和其他的变量有很强的相关性(例如是其他变量的线性组合或是其他函数依赖关系)，可以找到一组新的不相关的变量。（3）

从几何的观点来看，降维可以看成是挖掘嵌入在高维数据中的低维线性或非线性流形。这种嵌入保留了原始数据的几何特性，即在高维空间中靠近的点在嵌入空间中也相互靠近。（12）

数据降维是以牺牲一部分信息为代价的，把高维数据通过投影映射到低维空间中，势必会造成一些原始信息的损失。所以在对高维数据实施降维的过程中如何在最优的保持原始数据的本质的前提下，实现高维数据的低维表示，是研究的重点。（8）

二、降维问题

1．定义

定义1.1降维问题的模型为(X,F)，其中D维数据空间集合X般为RD的一个子集），映射F

F:X?Yx?y?F(x),

??xl?l?1（一

NY是d空间集合（一般是Rd，d??D）的一个子集，我们称F是数据集X（到Y）的降维。

若F为X的线性函数，则称F为线性降维；否则，称为非线性降维。 定义1.2 称映射F?1

F?1:Y?Xy?xF?1(y)

为嵌入映射。（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）

PCA 全局 LDA 降维 线性 LPP NPE 局部 LLTSA ONPP LLE 非线性 早期的 SM SOM PC Kernel 流行学习 概率参数模型 GC LLC Charting 谱分析 全局 HLLE MVU ISOMAP 局部 LE LTSA 线性化 三、常见降维方法

（一）线性

1. 主成分分析(Principal Component Aanlysis PCA) [1]

PCA将方差的大小作为衡量信息量多少的标准，认为方差越大提供的信息越多，反之提供的信息就越少。它是在损失很少的信息的前提下把多个指标转化为几个综合指标的一种多元统计方法。它具有概念简单，计算方便以及最优线性重构误差等优良的特性。

PCA是一种全局算法，它可以较好地揭示具有线性结构的高维数据集的全

局分布。然而对于嵌入在高维空间中具有非线性流形结构的数据，PCA很难学习出隐含在数据集中的低维流形结构。

PCA假设数据之间的关系是线性的。它在保存原始高维数据协方差结构的基础上计算低维表达，也就是最大化总体方差。它的目标函数可以写为：

N2UPCA=argmaxUPCAN?i?1Tyi?ym2

?argmaxtr(UPCASTUPCA)s.t.UUPCATTPCA?argmaxUPCA?i?1mUPCA(xi?x)?1NTmUPCA?Id其中，

Ny?yi，

xm?1N?xi，且

ST为总体离散矩阵：

?dST=?(xi?x)(xi?x)i=1TUPCA=Id，其中Id为d。对转换矩阵做尺度约束UPCA单

位矩阵。则目标函数可以写为：

argmaxtr(UPCASTUPCA)UPCATTUPCA，s.t.UPCA?Id

上式问题可以转化为ST的标准的特征值问题：PCA的最优转换矩阵为ST的d个最大的特征值所对应的d个m维特征向量。

2.线性判别法(Linear Discriminant Analysis LDA) [2]

其基本思想是投影，首先找出特征向量，把这些数据投影到一个低维的方向，使得投影后不同的组之间尽可能的分开，而同一组内的的样本比较靠拢，然后在新空间中对样本进行分类。

通过最小化类内离散矩阵SW的秩而最大化类间离散矩阵SB的秩，来寻找一个子空间来区分不同的类别。SW和SB分别定义如下：

CNiSW=?i=1?(xj?1(i)j?m(i))(xj(i)?m(i))T

CSB??i?1Ni(m(i)?m)(m(i)?m)

T其中，Ni是第i个类中样本的个数；xj(i)是第i个样本中第j个样本。m(i)为第i个类的质心；m用来表示所有样本的质心，C为样本的类别数。LDA则有以下的优化准则：

argmaxtr(Utr(UTLDATLDASBUSWULDALDA))

s.t.ULDAULDA?IdT

上述的优化可以转化为求解一个广义的特征分解问题：

SB???SW?

且最优的解为d个特征向量其对应于d个最大的非零特征值。

3.投影寻踪(Projection Pursuit PP) [3]

基本思想主要来源人们对低维空间几何图形的直观理解，它包含俩个方面的含义：其一是投影(Projection)，把高维空间中数据投影到低维空间；其二是寻踪(Pursuit)，利用低维空间投影数据的几何分布形念，发现人们感兴趣的数据内在特征和相应的投影方向，同时排除与数据结构和特征无关的或关系比较小的变量干扰。

4. 多维尺度分析(Multidimensional Scalar ，MDS) [4]

主要思想是：根据数据点间的欧氏距离，构造关系矩阵，为了尽可能地保持每对观测数据点之间的欧氏距离，只需对此关系矩阵进行特征分解，从而获得每个数据在低维空间中的低维坐标。

算法步骤：

1计算观测空间中任意两点欧式距离，构造n阶平方欧式距离矩阵A 2将矩阵A进行双中心化计算，即计算B若设n?n阶矩阵H=I?ee/nT??12HAH。

（常称之为中心化矩阵），将矩阵H左乘和右

乘A的两边（常称之为双中心化）。

3计算低维坐标Y。即将B奇异值分解，设B的最大的d个特征值

?=diag(?1，??d)，对应特征向量U?[v1,?vd]，则

d维坐标为Y??UT。

（二）非线性

流形学习旨在发现高维数据集分布的内在规律性，其基本思想是：高维观测空间中的点由少数独立变量的共同作用在观测空间张成一个流形，如果能有效地展开观测空间卷曲的流形或发现内在的主要变量，就可以对该数据集进行降维。

现在形式化地概括流形学习这一维数约简过程：假设数据是均匀采样于一个高维欧氏空间中的低维流形，流形学习就是从高维采样数据中恢复低维流形结

构，即找到高维空间中的低维流形，并求出相应的嵌入映射，以实现维数约简或者数据可视化。它是从观测到的现象中去寻找事物的本质，找到产生数据的内在规律。

用数学语言可以这样描述，令YD?d?Rd且

f:Y?RD是一个光滑的嵌套，

，流形学习的目标是基于RD上的一个给定被观测数据集合?xi?去恢复Y和

ff，在Y中隐藏的数据?yi?被随机地产生，然后被

?f(yi)?。（12）

映射到观测空间，使得

?xi1.局部线性嵌入方法 LLE (Locally Linear Embedding) [5]

LLE在保存原始高维数据邻域线性结构的基础上计算低维表达。（5）是一种局部方法，它试图保持数据的局部几何特征，就本质上来说，它是将流形上的近邻点映射到低维空间的近邻。（9）

图2 非线性降维实例 B是从 A中提取的样本点（三维），通过非线性降维算法 LLE将数据映射到二维空间中（C），从C图中的颜色可以看出通过 LLE算法处理后的数据能很好的保持原有数据的邻域特性(引用文献[6])

主要思想：对一组具有嵌套(流形)的数据集，在嵌套空问与内在低维空间局

部邻域问的关系应该不变，即在嵌套空间中每个采样点可以用它的近邻点线性表示，在低维空间中保持每个邻域中的权值不变，重构原数据点，使重构误差最小。(8)

LLE的实现过程

步骤：LLE方法可以归结为三步： (1) 寻找每个样本点的k个近邻点；

把相对于所求样本点距离最近的k个样本点规定为所求样本点的k个邻近点。k是一个预先给定值。距离的计算既可采用欧式距离也可采用Dijkstra距离。Dijkstra距离是一种测地距离，它能够保持样本点之间的曲面特性。

(2)由每个样本点的近邻点计算出该样本点的局部重建权值矩阵； 这里定义一个成本函数，如下式，来测量重建误差：

?(w)?xi??2jwijxj

?0解得wij其中Gijk??kGjki?1/?lmGlmi?1，?xj?Nwij?1,xj?N时wij

?(xi??j)(xi??k)，?j和?k是xi的近邻点；

为了使重建误差最小化，权重wij服从一种重要的对称性，即对所有特定数据点

来说，它们和它们邻居点之间经过旋转、重排、转换等变换后，它们之间的对称性是不变的。由此可见重建权重能够描述每个邻居本质的几何特性。因此可以认为原始数据空间内的局部几何特征同在流形局部块上的几何特征是完全等效的。

（3）由该样本点的局部重建权值矩阵和其近邻点计算出该样本点的输出值。 映射条件满足如下成本函数：

?(Y)??iYi??2jwijYj

要使低维重构误差最小，计算得出，Y等价于求M的特征向量，其中

M?(I?W)(I?W)T在处理过程中，将M的特征值从小到大排列，第一个特征

值几乎接近于零，那么舍去第一个特征值。通常取第2到m+l之间的特征值所对应的特征向量作为输出结果。

优点：LLE算法可以学习任意维的局部线性的低维流形，就是用局部性——用局部的的线性来逼近全局的非线性，保持局部的几何结构不变，通过相互重叠的局部邻域来提供整体的信息，从而保持整体的几何性质。LLE既有非线性的特点又具有线性方法的优点。（8）同时由重构成本函数最小化得到的最优权值遵循对称特性，每个点的近邻权值在平移、旋转、伸缩变换下是保持不变的LLE算法有解析的全局最优解，不需迭代，低维嵌入的计算归结为稀疏矩阵特征值的计算，这样计算复杂度相对较小。

缺点：LLE算法要求所学习的流形只能是不闭合的且在局部是线性的，还要求样本在流形上是稠密采样的。另外，该算法的参数选择不确定，对样本中的噪音很敏感。（12）此外，(1)对于一个新样本点。没有显式的方法把该点嵌入到低维空间中，这在检索应用中不适用。(2)新空间的维数没有显式准则进行确定，只有通过经验的方法。(3)LLE没有利用数据点的类信息。在分类问题中，对于有类标号的样本数据，LLE无能为力。

SLLE算法[7]

Dick和Robert提出一种针对有监督的 LLE算法，即Supervised linear locally embedding (SLLE)传统的LLE算法在第一步时是根据样本点间的欧氏距离来寻找k个近邻点，而SLLE在处理这一步时增加了样本点的类别信息，SLLE算法的其余步骤同LLE算法是一致的。

SLLE算法在计算点与点之间的距离时有两种方法。

SLLE1：第一种方法是采用下式来修正点与点之间的距离公式如下所示

D??D??max(D)?

其中：D?是计算后的距离D是最初采用的距离；max(D)是表示类与类之间的最大距离；?取0或者1，当两点属于同类时，?取为0，否则取1；?是控制点集之间的距离参数，??[0,1]，是一个经验参数。当?取为零时，此时的SLLE

和 LLE 算法相同。这个方法引入了一个参数?，它是一种经验参数，对实验的结果有很大的影响，下面介绍一种非参数的方法。

SLLE2：求解点与点之间的距离，目的在于是寻找样本点的近邻点。SLLE2的方法在寻找近邻点时，不是在全局样本中寻找近邻点，而是在每个点所在类的样本中寻找近邻点，也就是说，在类内中寻找样本点的近邻点。这个方法固然没有采用参数的方法，但是如果某一类的样本个数小于k，那么这种方法必将失败，则每个类的样本个数在相当多的情况下 可以采用这种方法。

RLLE算法[8]

当在做聚类分析且采用LLE算法对数据进行降维时，如果数据中存在着许多离异点的情况，那么降维后的结果将会发生变异，通常是第一维或者是第二维的数据发生跳跃式的变化，或者分布在某几条直线上，这将会给聚类带来很大的麻烦，其实当离异点超过LLE算法中的k值时，这种现象将会发生。

A.Hadid和M.Pietik?inen提出一种 Robust Locally Linear Embedding (RLLE)方法。它是针对存在有离异点的情况下，对样本的一种无监督的非线性降维方法。

邻域保持嵌入算法NPE算法[9]

NPE从本质上说是局部线性嵌入(local linear embedding，LLE)的线性逼近。给定数据集X，采用与LLE相同的方法构建数据集上的近邻图。NPE针对LLE算法的out-of-sample问题提出的，该算法通过最小化局部相似离散度寻找投影方向，有效的保持了数据间的相似几何结构，取得了不错效果，已被广泛地应用到文档分析、机器学习和模拟识别等领域。NPE假定每个局部近邻都是线性的。

算法步骤：

1近邻选择，构造邻接图G 2计算近邻重建权W

3计算投影向量：

a求低维坐标对应近邻重建的目标函数最小化，即

nk??Min?yi??Wijyij?Yi?1j?1?T?S.t.:YY?I2

b代入线性变换y??x,得

Tnk?TT?Min?xi??Wijxij???i?1j?1?TT?S.t.:?XX??I2

c

??M?in?XMX??TT??S.t.:?XX??ITTT

其中M?(I?W)(I?W)d求解下列广义特征方程的d个最小特征值对应的特征向量作为d个投影向量：

XMX?=?XX?TT

故由上述特征方程的d个最小特征值?1,?2,?,?d对应特征向量

?1,?2,?,?d，构成保持近邻重建特性的线性变换矩阵。

缺点：NPE在保持数据空间的局部相似信息时，不能较有效地保持差异信息，特别是高维非线性数据间的差异信息。如在人脸识别应用中，人脸图像的识别容易受光照、表情等非理想条件变化的影响，这些非理想情况会使得同一个人的不同图像之间的差异大于不同人图像之间的差异，从而导致识别错误。

NPE算法通过式xi?yi?AxiT实现了数据到新空间的线性变换。显然，这

种线性变换实现的数据变换是一种显式形式，这样就解决了LLE算法没有显式映射函数的问题。

LLE算法是非监督的学习方法，没有充分利用类别信息，为了提高算法的识别能力，于是有了LLE的正交线性化扩展，orthogonal neighborhood preserving projections(ONPP)[10][ 11]。

张长水等人[12]在LLE的基础上提出一种从低维嵌入空间向高维空间映射

的方法，并在多姿态人脸图像的重构实验中得到有效的验证，进一步完善了非线性降维方法。

2. 等距映射法 ISOMAP (Isometric Map) [13]

ISOMAP认为当数据集具有嵌入流形结构时，可以根据保距映射来获得观测空间数据集在低维结构的对应描述。

基本思想：ISOMAP通过测地线距离来描述各点之间的相互关系，在全局意义下，通过寻找各点在图意义下的最短路径来获得点与点之间的距离，然后利用经典的MDS算法得到低维的嵌入坐标。因此．ISOMAP可认为是MDS算法的变种。（5）

图3 ISOMAP算法示意图

使用前提条件：高维数据所在的低维流形与欧氏空间的一个子集是整体等距的；与数据所在的流形等距的欧氏空问的子集是一个凸集。

主要步骤：

(1)构造局部邻域。首先对数据集Xxi??x1,x2,?,xn?，计算任意两个样本向量

和xj的欧式距离dx(xi,xj)，将每一个点与所有的点进行比较，当两点之间的距

离小于固定的半径?（或i是j的K-邻域）时，我们就认为它们是相邻的，将其连接起来，该边的长度dx(xi,xj),则得到邻域图G。

(2)计算最短距离。在图G中，设任意两个样本向量xi和xj之间的最短距离为dG(xi,xj)。若xi和xj之间存在连线，dG(xi,xj)的初始值为dx(xi,xj)，否则令

dG(xi,xj)??。对所有的k=1,2,…,n

dG(xi,xj)?min{dG(xi,xj),dG(xi,xk)?dG(xk,xj)}

这样得到矩阵DG?{dG(xi,xj)}，它是图

G中所有点对的最短路径组成的。

(3)构造d维嵌入。用MDS方法构造一个保持本征几何结构的d维嵌入到空间Y。

?(DG)??H*(DG)*H22

H是与DG同阶的单位矩阵，对?(DG)进行特征分解，取最大的前d个特征值?1,?2,?,?d和对应的特征向量V1,V2,?,Vd，令Vpi为第p个特征向量的第i个成分，则对应的数据低维表示为yi??pVp1/2i。

优点： 适用于学习内部平坦的低维流形，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)[19]

LTSA是一种基于切空间的流形学习方法，它通过逼近每一样本点的切空间来构建低维流形的局部几何，然后利用局部切空间排列求出整体低维嵌入坐标。

主要思想：找出每个数据点的近邻点，用邻域中低维切空间的坐标近似表示局部的非线性几何特征，再通过变换矩阵将各数据点邻域切空间的局部坐标映射到一个同一的全局坐标上，从而实现高维数据降维，即从n维数据中得到一个全局的d维坐标。(8)

算法步骤：

第一步：构造邻域。对于每个数据点xi，找出它的包括它自身在内的k个邻

域点，构成矩阵Xi?[xi,?,xi]。

1k第二步：局部线性投影。对于每个样本点的邻域

Xi(I?ee/k)的最大

TXi，计算中心化矩阵

d个奇异值对应的左奇异向量，并将这d个左奇异向量组成

矩阵Qi。 1由Xi(I?ee/k)?U?VTQi计算得出左奇异向量U，取出U的前d列构成矩阵Q（i即为xi点的切空间的近似）；

2计算各个邻域点在该切空间Qi的投影：

?i?QiXi(I?ee/k)?[?1,?,?k]

TT(i)(i)?(i)j?Qi(xi?xi)

Tj第三步：局部坐标系统的排列。对每个邻域的局部切空间坐标

?i?(?1,?2,?,?k)(i?1,2,?,N)(i)(i)(i)，构造转换矩阵Li??i?R?d?d。通过最小化

?Ti(I?ee/k)?Li?iT2的求解，最后化解可通过计算一个矩阵从第2小到第d+1

小的特征值所对应的特征向量。其中?i?是?的广义Moor-Penrose逆。

优缺点：LTSA能够有效地学习体现数据集低维流形结构的整体嵌入坐标，但它也存在两方面的不足：一方面算法中用于特征值分解的矩阵的阶数等于样本数，样本集较大时将无法处理；另一方面算法不能有效处理新来的样本点。（12）对此，提出了一些相应的改进算法。

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

线性局部切空问排列(LLTSA)

针对LTSA算法不能为新的测试样本提供一个明确的从高维到低维的映射，也就是所谓的“Out of Sample”问题。提出了一个新的线性算法，线性局部切空问排列(LLTSA)[20]。该算法运用切信息作为数据的局部表达，然后将这些局部信息在可以用线性跌射得到的低维空间中排列。它先将每一个样本点邻域的切空间表示为流形的局部几何，再经线性映射实现样本数据从高维空间降维到低维空间，最终将整体嵌入坐标的求解问题转化为矩阵的广义特征值的求解问题。

算法步骤：

1近邻选择，构造邻接图G 2计算局部切坐标? 3计算投影向量：

a求低维坐标对应近邻重建的目标函数最小化，即

??Min?YiHk?Li?i?Li,Tii?T?S.t.:YY?I2

Hk是k阶中心化矩阵且Hk?I?ee/k。

Tb代入线性变换Yi??(XiH)，且由HT22?H得

?T?Min??(XiHk)?Li?i?Li,Tii?TT?S.t.:?XX??I

c

??M?in?XHBHX??TT??S.t.:?XHX??IB?SWWSTTTT

S?[S1,?,Si,?,Sn]使得YSi?Y，并且i?其中,近邻选择矩阵

W?diag(W1,W2,?,Wn),且Wi?Hk(I??i?i)。

d求解下列广义特征方程的d个最小特征值对应的特征向量作为d个投影向量：

XHBHX?=?XHX?TT

故由上述特征方程的d个最小特征值?1,?2,?,?d对应特征向量?1,?2,?,?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) [24]

LE方法将微分流形、谱图论的知识应用于降维之中，使人们对降维过程的认识产生了又一个新的飞跃，拓展了实际中降维方法的应用。

基本思想是：在高维空间中距离相隔很近的点投影到低维空间中像也应该相距很近，最终求解归结到求拉普拉斯算子的广义特征值问题。（8）实际上是使用有权图的 Laplace矩阵来逼近 最优投影的降维算法

算法步骤：

第一步，构造近邻图G。在数据集X中，计算每个样本点xi同其余样本点之间的欧式距离，构造近邻图。寻找相对于每个样本点xi的欧式距离最近的k个

RD 空间中的 Laplace Beltrami 算子，以期达到

样本点规定为所求点的近邻点，若数据点xi与xj是邻接的，则图中点xi与xj之间存在一条边。

第二步，选择权值，构造权值矩阵W。在近邻图中，为每一条边选择一个权值wi,j，构造权值矩阵W。权值的选择有两种选择方式：

1）若点xi与xj是邻接的，则设边的权值为wi,jwi,j=0；t

?exp(?||xi?xj||/t)，否则设

2是一个比例参数。

2）若点xi与xj是邻接的，则设变得权值为wi,j=1，否则设wi,j=0。 在方法1）中，需要选择比例参数t，方法2）不用选择比例参数t，比较简单。

第三步，进行特征映射，计算d维嵌入。对数据集X构造的近邻图G，映射到一条直线，用y表示，使得邻接的点尽可能的靠近。设y?(y1,y2,?,yN)T是

一个未知的投影，可以通过在一定约束下，使得下面的目标函数达到最小来求解。

?ij(yi?yj)wij

2用D表示对一个对角矩阵，它的每个对角元素为权值矩阵W的每行所有元素的和，即Di,i??jwi,j2i，L=D-W是邻接图的Laplacian矩阵。对任意的y有

2T?ij(yi?yj)wij?2?(yij?yj?2yiyj)wij?2yLy

给定约束条件yTDy=1，以消除坐标尺度对映射y的影响，最小化上式的和函数，利用矩阵迹的性质和拉格朗日乘子法，即可求解。相当于利用下式计算特征值和特征向量的问题Ly??Dy

上述特征方程的最小的d个非零特征值对应的特征向量y1,y2,?,yd，则数据X的低维嵌入表示为Y?[y1,y2,?,yd]T

LE是局部的非线性方法，其突出特点是与谱图理论有着很紧密的联系。从算法描述中可以看到，拉普拉斯映射和LLE算法类似，待定参数相同，求解的是稀疏矩阵的广义特征值问题，它能使输入空间中离得很近的点在低维空间也离

得很近，故可用于聚类。（12）缺点类似LLE。

LPP局部保留投影（Locality preserving projection，LPP）

LPP局部保留投影（Locality preserving projection，LPP）作为LE的线性化是其中最早提出的算法。[25]

LPP算法的主要问题在于建立k近邻域图，使它能很好地表现数据流形的局部结构。然后，根据建立的k邻图来获得图像的投影，最终在投影得到的子空问中进行特征识别。

算法把非线性变换转换成了近似的线性形式。所以，一个测试样本要转换到新空间中去，只要乘以从训练集计算得到的线性矩阵即可。这解决了LLE、LE等算法不能显式表示的问题，实际上这种显式转换是非线性流行空间的一种线性回归和近似。与前述全局最优算法相比，这些算法保持了局部信息，同时给出了简便的变换形式，可以说是全局最优和局部最优间的折衷。

算法步骤：

1近邻选择，构造邻接图G 2计算近邻相似度W 3计算投影向量：

a求低维坐标对应近邻重建的目标函数最小化，即

1?2Min(y?y)Wij?ij?Y2i,j?T??S.t.:YY?I

b代入线性变换y??x,得

T21?TTMin(?x??x)Wij?ij?Y2i,j?TT?S.t.:?XX??I?

c

??M?in?XLX??TT??S.t.:?XX??ITT

?其中L=D-W,而对角矩阵D的对角线元素Dii?W

ijjd求解下列广义特征方程的d个最小特征值对应的特征向量作为d个投影向量：

形学习方法值得进一步研究。

(2) 流形学习算法的分类能力较弱

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

(3) 本征维数的估计

我们对流形学习方法的非参数化问题进行了研究，如何自适应的确定流形学习算法中需要的参数，而不是依据经验或人为设定，也是需要解决的问题。在非线性降维过程中，原始数据本征维数d都是由经验已知或人为设定的，其设定值的大小对低维空间的映射结果有很大影响。d值过大使映射结果含有过多噪声；d值过小，本来不同的点在低维空间可能会彼此交叠。

目前本征维数的估计方法主要分为以下三种[32]：(1)特征值或映射方法，(2)几何学习方法，(3)统计学习方法。

(4) 增量学习

目前的大部分流形学习算法只定义在给定的数据集上，通常算法只能得到给定数据集在低维空间中的表示{ 性映射关系

f?1xi }，而不能得到从高维空间到低维空间的非线

:Rm?Rd。缺少这一映射关系将无法在不重新构造图的情况下计

算新样本的低维表示。如何根据新输入的样本修改映射关系而不重新计算，可以节约大量的计算时间和存储空间。

国际上已经有很多学者开始关注这一问题的研究，Law M等[33]提出了一种增量Isomap算法，只是修改了测地距离的计算方式，节省了一定的时间，但对于算法本身并没有好的改进；OlgaK等[34]人在LLE基本算法的基础上提出了一种增量LLE算法以解决样本外问题。

(5) 噪声流形学习问题

目前的大部分流形学习算法在构造邻域图时采用了k-NN准则来获得流形结构在观测空间的有限描述。这一方法假定了数据集不存在异常噪声，如果噪声较

大时，算法可能覆盖过多的非支撑域以外的空间，从而使得随后的分类算法产生错误的几何投影距离。考虑流形学习与全局分析方法的互补性，现有的全局分析方法如主成分或主曲线等在这一方面具有一定的优势，所以在机器学习和模式识别等领域，如何将两者有机地结合起来，互补缺陷，将是一个好的研究方向。当观测数据是对一个光滑流形较好的采样时，使用非线性降维可以找出其内在本质的流形分布。但是，在实际的高维采样数据中由于各种因素经常存在噪声，使得映射到低维空间后会出现对原始数据结构的扭曲和变形。

(6) 寻找淹没子流形的问题

现在的大部分流形学习算法是基于单一流形的假设前提。所以当数据集中存在多个流形时，流形学习算法将失效。它们只能被分别单独应用在各个“聚类”的数据上。而对于模式识别问题，人们关心的是由多个类别构成的数据集中存在着怎样的几何结构。通常，一个类别对应着一个流形，不同类别对应于位于不同位置的流形。不同类别之间的区别在于它们在高维空问所占据的位置不同。面对这种任务，需要一种能同时观察这些不同类别中流形的流形学习算法。目前这一问题还没能得到很好的解决。

(7) 流形重构与有监督学习

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

[1] H.Hotelling,?Analysis of A Complex of Statistical Variables into Prindpal Components,”Journal of Educational Psychology,vol.24,pp.417-441,1933.

[2] R.A.Fisher,“The Use of Multiple Measurements in Taxonomic Problems,”Annals of Eugenics,vol.7,pp.179-188,1936．

[3] P.J.Huber.Projection pursuit.Annals of Statistics,13(2):435 475 (with comments，pp．475 525)，June 1985.

[4] Thomas L.Griffiths and Michael L.Kalish,A Multidimensional scaling approach to mental

multiplication,Memory&Cognition,vol.30(1),pp.97-106,2002

[5] ROWEISS,SAULL.Nonlinear dimensionality reduction by locally linear embedding [J].Science,2000,290(5500):2323-2326．

[6] Lawrence K.Saul, Sam T.Roweis. Think Globally, Fit Locally: Unsupervised Learning of Low Dimensional Manifolds. Journal of Machine Learning Research 4(2003) 119-155

[7] Dick 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 in Computer Science 2714, Springer, 333-341

[8] Hadid A, Pietik?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.

[9] X.He，D.Cai，S.Yan，and H．Zhang,\，”Proc．IEEE Int'l Conf.Computer Vision,pp.1208-1213,2005．

[10] 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．

[11] E．Kokiopoulou and Y．Saad,”Orthogonal Neighborhood Preserving Projections”, Proc．IEEE Int'l Conf.Data Mining,pp.27-30,2005．

[12] Zhang CS，Wang J，Zhao NY，Zhang D．Reconstruction and analysis of multi—pose face images based on nonlinear dimensionality reduction．Pattern Recognition，2004，37(1)：325-336． [13] TENENBAUM J,SILVADD,LANGFORD J.Aglobal geometric framework for nonlinear dimensionality reduction[J].Science,2000,290(5500):2319-2323.

[14] 詹德川，周志华．基于集成的流形学习可视化[J]．计算机研究与发展，2005，42(9)：1533-1537．

[15] 赵连伟，罗四维，赵艳敞，等．高维数据的低维嵌入及嵌入维数研究[J]．软件学报，2005，16(8)：1423-1430．

[16] 何力，张军平，周志平．基于放大因子和延伸方向研究流形学习算法[J]．计算机学报，2005，28(12)：2000-2009．

[17] M.Vlaehos,C.Domeniconi,D.Gunopulos ct a1.Non-linear dimensionality reduction techniques for

classification

and

visualization.In

Proceedings

of

8th

SIGKDD,Edmonton,Canada,2002.645-65 1．

[18] Geng,X.Zhan,D.C.Zhou,Z.H.Supervised nonlinear dimensionality reduction for visualization and

classification.IEEE

Transactions

on

Systems

Man

and

Cybernetics

Prat

B.2005,vol.35,1098-1107.

[19] ZHANG ZY,ZHA HY.Principal manifolds and nonlinear dimensionality reduction via tangent space alignment[J].SIAM Journal of Scientific Computing,2005,26(1):313-338．

[20] Zhang T,Yang J,Zhao D,et al．Linear local tangent space alignment and application to face recognition[J].Neumcomputing,2007,70(7-9):1547-1553.

[21] 李勇周,罗大庸,刘少强等.正交判别的线性局部切空间排列的人脸识别[J].中国图象图形学报A,2009,14(11):2311-2315.

[22] 杨剑，李伏欣，王珏．一种改进的局部切空间排列算法［J］． 软件学报，2005，16(9)： 1584-1590．

[23] 程琨，舒勤，罗伟，张国龙，基于划分的有监督局部切空间排列的人脸识别[J]，计算机应用研究，2011，（06）。

[24] M．Belkin and P．Niyogi，\Clustering,\

[25] X.He and P.Niyogi,”Locality Preserving Projections,”Advances in Neural Information Processing System,vol.16,2004．

[26] D.Donoho,Grmesc.Hessian eigenmaps:new locally linear embedding techniques for high—dimensional data[J].Processing of the National Academy of Sciences ofthe United States ofAmerican,2003:5591-5596.

[27] g．Q．Weinberger and L．k Saul，“Unsupervised Learning of Image Manifolds by Semidefmite Programming”Pmc.IEEE Int'l Conf.Computer Vision and Pattern Recognition,vol.2，pp.988-995,2004．

[28] BeUdn,M.Niyogi,E Using Manifold Structure for Partially Labeled Classification.Advaces in Neural Information Processing Systems.2003,vol.15,953-960．

[29] Yang X Fu,H Zha,H．Barlow,J．Semi-supervised nonlinear dimensionality reduction．Machine learning International Workshop Conference.2006,vol.23,1065.1072.f.

[30] Z Zhang,H Zha,M Zhang.Spectral Methods for Semi-supervised Manifold Learning.IEEE Conference on Computer Vision.2008．

[31] 冯海亮，黄鸿，李见为等．基于Semi-Supervised LLE的人脸表情识别方法．沈阳建筑科技大学学报：自然科学版．2008，vol．24，1109-1113．

[32] Verveer P,Duin R.An evaluation of intrinsic dimensionality estimators.IEEE Trans.On P_wI,1995,vol.17,81-86．

[33] Law M，Jain AK．Incremental nonlinear dimensionality reduction by manifold learning．IEEE Tram.on PAMI,2006,377-391.

[34] Olga KOleg O,Matti P.Incremental locally linear embedding.Pattern Recognition,2005，vol.38,1764-1767．

本文来源：https://www.bwwdw.com/article/muh8.html