硕士学位论文 第2章 流形学习

2.1引言

随着信息技术的发展，出现了大量高维非线性数据，如文本数据、语音数据、图像数据等。因此，如何有效地对这些高维数据进行维数约减成为研究的一个热点。维数约减不仅可以避免维数灾难，而且能够发现数据集的内在规律并可直观感知理解。目前维数约减方法可分为线性和非线性方法，其中线性维数约简方法很难直接分析和处理高维非线性人脸数据。一方面是传统降维方法有严格的前提假设，如数据集具有全局线性，高斯分布等；另一方面，受光照、表情、姿态等影响，人脸数据集实质上呈现一种非线性结构。实验发现，大多高维采样数据是由少数隐含变量来决定的，这些隐含变量通过嵌套在高维空间的组合非线性流形而存在。

流形（Manifold）是一个数学概念，如不同维数的曲线曲面等，是局部可坐标化的拓扑空间。流形学习[37]的目标是从高维采样数据集去重构它的低维流形和低维嵌入映射，旨在挖掘高维数据集分布的内在规律性。由于流形不是欧氏几何空间，不满足全局线性结构。因而流形学习更注重局部信息，可通过局部的学习来得到全局非线性结构。流形学习的数学定义描述如下[38]。

定义2.1 在Rn空间（d<

{yi|i?1,..m.?,}Y，经过某个函数f:Y?Rd可以映射为观测空间中的数据集

{xi?f(yi)|i?1,...,m}?Rn。

由流形学习的定义可知，流形学习能够挖掘一般意义上数据集的本质属性，不受数据间线性独立、满足正态分布等先验假设的约束。相比传统的维数约减算法，流形学习更能体现事物的本质，更好地解决在机器学习中维数约减的问题，便于对数据的理解和进一步处理。

自2000年在《Science》上发表了两篇关于流形学习的文章为起点[19,20]，掀起了研究流形学习方法的高潮。本章主要介绍流形学习的相关知识、三种经典算法。主要包括等距映射方法（Isomap）、局部线性嵌入方法（LLE）、拉普拉斯特征映射法（LE）。

2.2等距映射

2000年Tenebaum[19]等人提出的等距映射（Isometric Mapping，Isomap）是一种非线性降维方法，该算法以多维尺度分析（MDS）为基础，通过数据之间的测地距离取代欧氏距离来保持内在几何特性。MDS和ISOMAP区别在于

11

人脸识别中基于流形学习的特征提取方法研究 数据点间距离的计算方法不同，MDS是通过欧氏距离来表示样本点间的关系，而ISOMAP构造的距离矩阵反映流形中样本点对的测地距离，如图2.1所示。图2.1（a）中虚线表示三维欧氏空间中两点间的欧氏距离，而实线是通过流形距离（测地距离）连接两点间的最短曲线。显然，虚线所表示的欧氏距离不能有效反映数据点在流形上的关系。在图2.1（b）中，两点间的流形距离是用邻接图上的最短距离来逼近。图2.1（c）将三维空间的数据投影到二维空间中，相当于原来空间中弯曲的曲面拉平，两点在参数空间中的距离用蓝色直线表示，而红色曲线表示了两点在邻接矩阵上相应的最短路径。

（a） （b） （c）

图2.1 ISOMAP映射示意图

ISOMAP把数据从高维空间映射到低维空间，旨在保持映射前后的数据点对之间的距离不变，即将近邻的数据点保持近邻关系，远离的数据点保持远离。因此，ISOMAP的关键是如何估计出采样空间样本之间的测地距离。ISOMAP的测地距离可通过这样的方法来计算：当样本点对相距很近时，可以使用欧氏距离来代替测地距离，当样本点对相距较远时，可通过流形上它们之间的最短距离来代替。

假设数据集X?[x1,x2,的实现步骤如下：

（1）构造邻域关系图G(V,E)：对每个xi(i=1,2,...,m)，通过k近邻法或者?邻域法计算其近邻点，记为Ni?{xik|i?1,2,...,m}，以xi为顶点，样本点xi、xj之间的欧氏距离dX(xi,xj)为边，构造邻域关系图G(V,E)。

（2）估计测地距离矩阵DG：用邻域关系图G(V,E)上点之间最短路径距离来估计流形M上的测地距离。定义如下：如果初始时xi与xj之间存在连线，则dG(xi,xj)?dX(xi,xj)；否则,dG(xi,xj)??。对所有的k=1,2,...,m，依次更新

dG(xi,xj)的值：dG(xi,xj)?mind{(,jGxix,xm]，同时数据集位于非线性流形M上。ISOMAP

d)G,xi(?xk,得到的矩阵)dGxk(，x所jDG(xi,xj)? {dG(xi,xj)}表示了图G(V,E)中任意两点间的最短距离。

（3）计算低维嵌入：将经典MDS方法应用到距离矩阵DG?{dG(xi,xj)}中，寻找保持拓扑空间本征结构的低维嵌入Y?[y1,y1, 12

,ym]，可通过最小化式（2.1）

硕士学位论文 误差方程得到：

E??(DG)??(DY)L2 （2.1）

其中,DY是低维数据点的欧氏距离矩阵DY(dY(yi,yj)?y?yj)?m，im矩阵变

2换算子?D??HSH/2，H为集中矩阵，即{Hxixj??xixj?1/N}，S为平方距离矩阵，

2即{Sxixj?Dx}。可通过求解矩阵?(DG)的前d个最大特征值所对应的特征向量ixj来完成对式（2.1）的最小化。

ISOMAP是一种全局优化的非线性算法，能够反映高维空间数据点对之间的流形距离，可以得到比较理想的嵌入结果。在单一流形结构中，ISOMAP具有能够使用距离保持的程度来判定数据的内在维数的优点，在手形数据集和人脸数据集中取得了理想的验证结果。但是，ISOMAP具有一些不足之处。该算法采用全局搜索方法在全体数据集的图模式中计算最短距离，其时间复杂度相对较高。同时，当流形上存在空洞时，所计算出的路径会发生较大偏移，导致计算出的最短距离比真实的最短距离偏大，从而导致嵌入结果发生明显的变形和扭曲。另外，当数据集中存在较大的噪声时，影响对流形内在结构的恢复。

2.3局部线性嵌入

2000年Roweis[20]等在Science上发表了一篇关于局部线性嵌入（Locally Linear Embedding，LLE）算法的文章。LLE的基本思想是在数据集中任意一个数据点和它的邻域点之间构造局部线性坐标，对其建立优化目标函数。一个数据点可以由它的邻域点线性重构，并且假设低维空间的嵌入是在局部线性的前提下，保证重构误差达到最小。对所有数据点都重复以上最优重构权值，保持低维空间中每个数据点与它的邻域点的重构关系不变，可以得到高维向量在低维空间的嵌入。图2.2给出了LLE算法的基本思想示意图。

13

人脸识别中基于流形学习的特征提取方法研究

图2.2 LLE算法过程

假设在非线性流形上给定m个数据点，且xi?Rn，i?1,2,yi?Rd(dn)是xi的低维映射。

,m。

LLE算法可以归结如下：

（1）求取局部邻域点。计算每个向量xi的k个邻域点，构成邻域

Xi?[xi1,xi2,,xik]。如何有效选取k值对保证算法重构低维流形嵌入起到关键的

作用。若k值取的过大，LLE就很难体现出局部特性，使得LLE算法趋向于PCA算法而趋向全局；反之，LLE很难保持样本点在低维空间中的拓扑结构，从而流形的局部与局部之间缺乏联系。

（2）计算重构权值矩阵。在xi的邻域中，计算其局部重构权值矩阵Wij。为了局部线性重构，定义如下代价函数使得总体重构误差最小：

?(W)?min?i?1mxi??Wijxij （2.2）

j?1k2其中：xi是一个样本向量，权值Wij为样本点xi的第j个近邻点xij对xi的重构贡献。为了计算重构权值Wij，增加两个约束条件：其一，如果xj不属于xi的邻域点时，Wij?0；其二，权值矩阵的每一行相加为1，即?Wij?1。

j?1m （3）通过特征映射计算低维嵌入。保持权值Wij不变，求xi在低维空间中的映射yi，使得所构造的代价函数在映射过程中达到最小。其中重构误差为：

?(y)??yi??Wijyiji?1j?1mk2?tr(YT(I?W)T(I?W)Y) （2.3）

其中，yi是xi的低维嵌入向量，yij为yi的k个近邻点。该优化问题可以通

14