流形学习及其算法分析

冯灵清+刘艳红+刘宇晶

（山西农业大学信息科学与工程学院， 山西 太谷 030801）

摘 要： 流形学习作为机器学习、数据挖掘及模式识别领域近年来的一个研究热点，其本质在于找出嵌入在高维空间中的低维光滑流形，揭示隐藏在高维数据中的内在低维结构，以实现非线性降维。介绍了流形学习的基本思想，分析、比较了等距映射（Isomap），局部线性嵌入算法（LLE），拉普拉斯特征映射算法（Laplacian Eigenmap）和局部保留投影等几种常用流形学习算法的研究成果及优缺点，提出了流形学习中的一些问题，以利于更好地进行数据的降维与分析。

关键词： 流形学习； 等距离映射； 局部线性嵌入； 拉普拉斯特征映射； 局部保留投影

中图分类号：TP301 文献标志码：A 文章编号：1006-8228（2017）04-01-04

Abstract： In recent years， manifold learning has become a hot issue in the field of machine learning， data mining and pattern recognition. The essence is to find the low dimensional smooth manifold embedded in the high-dimensional data space， reveal the intrinsic low dimensional structures in high dimensional data， in order to realize the nonlinear dimensionality reduction. This paper introduces the fundamental ideas， analyzes and compares the research results and the advantages and disadvantages of four manifold learning algorithms， such as Isomap， Locally Linear Embedding， Laplacian Eigenmap and Locality Preserving Projection， and puts forward some problems in manifold learning. The purpose is to understand the characteristics of these manifold learning algorithms in order to better reduce the data dimension.

Key words： manifold learning； Isomap； Locally Linear Embedding； Laplacian Eigenmap； Locality Preserving Projection

0 引言

隨着信息科学技术的发展和信息时代的到来，信息量越来越大，信息种类越来越复杂，信息数据的维数也越来越高，如何快速的对信息进行有效的处理并能够提取出有效的信息是当今社会的一个重要研究课题。如今数据降维在许多领域起着越来越重要的作用。流形学习的主要思想就是将高维的数据映射到低维，使该低维的数据能够反映原高维数据的某些本质结构特征。流形学习（Manifold learning）是机器学习、模式识别中的一种方法，在维数约简方面具有广泛的应用[1]。

1 流形和流形学习

1.1 流形

流形是线性子空间的一种非线性推广，是一个局部可坐标化的拓扑空间。流形是拓扑学的一个概念，拓扑空间是拓扑学最基本的研究对象：设集合X上的拓扑τ是X的满足以下性质的子集族①τ对属于它的任意多元素的并集是封闭的；②τ对属于它的有限多元素的交集是封闭的；③φ∈τ且X∈τ则称（X，τ）是一个拓扑空间。如果对空间（X，τ）中的任意两点x≠y存在A∈和B∈使得A∩B=φ，则称（X，τ）是一个Hausdorff拓扑空间。设M是一个Hausdorff拓扑空间，若对每一点p∈M都有P的一个开领域U和Rn的一个开子集同胚，则称M为n维拓扑流形，简称为n维流形[2]。

1.2 流形学习

在对流形的定义理解的基础上，我们可以简单概括流形学习这一个降维的过程：假设数据是均匀采样于一个高维欧氏空间中的低维流形，流行学习就是从高维采样数据中恢复低维流形结构，并求出相应的嵌入映射，以实现数据降维。用数学语言描述如下：设Y∈Rd是一个低维流形，f：Y→RD是一个光滑嵌入，其中D>d。数据集{yi}是随机生成的，且经过f映射为观察空间的数据{x=f（yi）}。流形学习就是在给定观察样本{xi}集的条件下重构f和{yi}[3]。如图1所示。

2 流形学习中的经典算法及分析

数据降维方法可以分为两种：线性降维方法和非线性降维方法。线性降维理论主要有Fisher判别分析（FDA）、主成分分析（PCA）、多维尺度分析（MDS）、独立分量分析（ICA）之类。线性方法相对于非线性流形方法计算相对简单，但对于那些非线性结构的数据就无法得到有效的答案。非线性流形方法则可以对非线性结构进行分析计算，产生较可靠的结果。流形学习作为非线性降维的主要方法其研究和发展的空间很大，下面着重介绍等距映射（Isomap）、局部线性嵌入（Locally linear embedding）、拉普拉斯特征映射（Laplacian Eigenmap）、局部保留投影（Locality Preserving Projections）等几种典型的流形学习算法。

2.1 等距离映射

等距离映射（Isomap）算法可以高效且有效地进行高维数据的低维嵌入以及利用数据降维的方法避免“维数灾难”的发生。Isomap主要是通过分析现有的高维流形，得到高维流形所对应的低维嵌入，从而让高维流形上数据点间的近邻结构在低维嵌入中得到较完整的重现。该算法以MDS（Multidimensional Scaling）算法为分析工具，主要思想是：先计算流形上的测地线距离，然后利用计算出来的测地线来代替欧氏距离，应用MDS算法，从而发现嵌入在高维空间里的低维坐标，这样Isomap就通过数据间的测地线距离，保留了数据固有的几何分布结构。Isomap中的测地线距离则使用的是最近邻接图中的最短路径[4]。

算法流程如下。

⑴ 确定流形M上哪些点是邻近的，两点（i，j）之间距离用Dx（i，j）表示；i，j点皆属于空间X；Dx（i，j）距离定义为Euclidean距离[5]，邻接关系可以设为固定的半径e或K最近邻。

⑵ 通过计算图G上两点间的最短路径DG（i，j）估计流形M上测地线距离DM（i，j）。应用经典MDS构建一个在d维欧氏空间Y中保留最为完整的内在嵌入流形几何[5]。

Isomap算法的优点是利用了流形上的测地线距离来代替欧氏距离，可以较好的保留数据的空间结构，适用于学习内部平坦的低维流形；缺点是Isomap算法具有拓扑不稳定性；若产生短环路则会严重影响其执行；并且对流形具有一定的限制要求，不适于学习有较大内在曲率的流形，若流形不是凸的，则会发生变形；另外，若有空洞出现在流形上，Isomap算法也不能解决这个问题[6-7]。

2.2 局部线性嵌入

局部线性嵌入（LLE）是一种非线性降维算法[8]，与Isomap算法不同，局部线性嵌入（LLE）是一种局部算法，LLE假设采样数据所在的低维流形局部是线性的，并假设每個采样点均可以利用其近邻样本进行线性重构表示。LLE的学习目标是：低维空间中保持每个邻域中的重构权值不变；在嵌入映射为局部线性的条件下，最小化重构误差；最终形式化为特征值分解问题。它能够使降维后的数据较好地保持原有流形结构。LLE可以说是流形学习方法最经典的工作之一。很多后续的流形学习、降维方法都与LLE有密切联系。如图2所示，使用LLE将三维数据（B）映射到二维（C）之后，映射后的数据仍能保持原有的数据流形（红色的点互相接近，蓝色的也互相接近），说明LLE有效地保持了数据原有的流行结构。

算法流程如下。

⑴ 计算每一个点的近邻点，一般采用K近邻或者ε邻域。

⑵ 计算权值Wij使得把Xi用它的K个近邻点线性表示的误差最小，即通过最小化来求出。

⑶ 保持权值Wij不变，求Xi在低维空间的象Xj，使得低维重构误差最小。。

LLE算法的优点是该算法可以学习任意维的局部线性的低维流形并能够归结为稀疏矩阵特征值计算，计算复杂度相对较小。但是LLE在有些情况下并不适用，如果数据分布在整个封闭的球面上，LLE则不能将它映射到二维空间，且不能保持原有的数据流形。那么我们在处理数据中，首先假设数据不是分布在闭合的球面或者椭球面上。

2.3 拉普拉斯特征映射

拉普拉斯特征映射（LE）[9]算法的基本思想是，在高维空间中离得很近的点投影到低维空间中的象也应该离得很近，LE算法就是将处于流形上的数据，在尽量保留原数据间相似度的情况下，映射到低维下表示。该算法可以反映出数据内在的流形结构。其求解方法就是求解图拉普拉斯算子的广义特征值问题。

Laplacian Eigenmap算法流程如下。

⑴ 从样本点构建一个近邻图，图的顶点为样本点，离得很近两点用边相连（K近邻或ε邻域）。

⑵ 给每条边赋予权值，如果第i个点和第j个点不相连，权值为0，否则Wij=1。

⑶ 计算图拉普拉斯算子的广义特征向量，求得低维嵌入。令D为对角矩阵，L=D-W，L是近邻图上的拉普拉斯算子，求解广义特征值问题Lf=λDf。

LE（Laplacian Eigenmap）算法的优点是局部非线性方法，与谱图理论有很紧密的联系；算法通过求解稀疏矩阵的特征值问题，解析地求出整体最优解，效率非常高；算法使原空间中离得很近的点在低维空间也离得很近，可以用于聚类。LE算法的缺点是同样对算法参数和数据采样密度较敏感，不能有效地保持流形的全局几何结构。

Isomap，LLE，Laplacian Eigenmap算法有效的原因是它们都是非参数的方法，不需要对流形的很多的参数假设。它们是非线性的方法，都基于流形的内在几何结构，更能体现现实中数据的本质。它们的求解简单，都转化为求解特征值问题，而不需要用迭代算法。

2.4 局部保留投影

局部保留投影（LPP）算法[10]是在LE算法的基础上，假设一个从原空间到流形空间的映射矩阵P，然后通过某种方法求出P，最后得到一个显示的投影映射。LPP是一种新的子空间分析方法，它是非线性方法Laplacian Eigenmap 的线性近似，既解决PCA等传统线性方法难以保持原始数据非线性流形的缺点，又解决了非线性方法难以获得新样本点低维投影的缺点。在受控环境的人脸识别中获得了成功的应用。局部保持投影LPP和PCA、LDA等方法类似，局部保持投影（LPP）通过一定的性能目标来寻找线性变换w以实现对高维数据的降维。下面简单介绍其实现过程。

LPP在一定程度上能够反映数据分布的非线性特征。LPP算法有着明晰的投影矩阵，这个性质对于解决新样本的特征提取是非常重要的。因此可以首先用训练样本求取投影矩阵，然后将样本投影到这个矩阵上即可完成特征提取。然而LPP方法仍然属于无监督学习方法，未能有效的利用样本的类别信息，因此 Yang等提出了一种基于非局部保持投影（Non-locality Preserving Projecting，NLPP）的特征抽取方法。2006年，庞彦伟等[11]提出了一种新的基于核子空间的方法用于人脸识别特征抽取，即基于核的非局部保持投影（KNLPP）。2008 年，Li 等[12]提出了一种有效的克服了小样本和样本外点问题的局部线性判别嵌入法（LLDE）。

3 流形学习算法中有待进一步研究的问题

随着人们对流形学习研究的不断深入和推广，从解决实际问题的角度，流形学习方法为探索非线性流形分布数据的内在结构提供了一种有效的途径。然而在实际应用中，流形学习方法仍然存在一些问题有待进一步研究[13]。

⑴ 流形学习算法中的噪声问题有待解决；

⑵ 如何将流形学习推广到半监督以及有监督的情况用于模式识别等多领域；

⑶ 当采样数据很稀疏时，怎样进行有效的学习；

⑷ 本征维数的确定仍是流形学习算法中的一个研究难点；

⑸ 如何将统计学习理论引入流形学习对其泛化性能进行研究；

⑹ 如何确定低维目标空间的维数；

这些也将是非线性降维研究的主要方向。

4 结束语

流形学习方法作为一类新兴的非线性维数约简方法，主要目标是获取高维观测数据的低维紧致表示，探索事物的内在规律和本征结构，已经成为数据挖掘、模式识别和机器学习等领域的研究热点。本文介绍了几种主要的流形学习算法，并对其优缺点作了算法分析，并探讨了其在理论和应用中有待进一步研究的问题。

参考文献（References）：

[1] 王自强，钱旭，孔敏.流形学习算法综述[J].计算机工程与应用，

2008.44（35）：9-12

[2] M Berger， B Gostiaux. Differential Geometry： Manifolds，

Curves and Surfaces， GTM115. Springer-Verlag，1974.

[3] 陳维桓，微分流形初步（第二版）[M].高等教育出版社，2001.

[4] 赵连伟，罗四维，赵艳敞等.高维数据流形的低维嵌入及嵌入

维数研究[J].软件学报，2005.16（8）：1423-1430

[5] Roweis ST，Saul LK.Nonlinear dimensionality analysis by

locally linear embedding.Science，2000.290（12）：323-2326

[6] J.B.Tenenbaum，V.de Silva and J.C.Langford，A Global

Geometric Framework for Nonlinear Dimensionality Reduction.Science，2000.290（5500）：2319-2323

[7] 吴晓婷，闫德勤.数据降维方法分析与研究[J].计算机应用研

究，2009.8：2833-3835

[8] Roweis S，Saul LK. Nonlinear dimensionality reduction by

local-y linear embedding. Science，2000.290：2323-2326

[9] Belkin M，Niyogi P. Laplacian eigenmaps for dimensionality

re-duction and data representation. Neural Computation，2003.15（6）：1373-1396

[10] He X， Yan S， Hu Y， Niyogi P， and Zhang H J. Face

recognition using Laplacian faces. IEEE Trans. on Pattern Anal. Machine Intelli.，2005.27（3）：328-340

[11] 庞彦伟， 俞能海， 沈道义， 刘政凯.基于核邻域保持投影的

人脸识别[J].电子学报，2006.34（8）：1542-1544

[12] Bo Li， D.S.Huang. Locally linear discriminant embedding：

An efficient method for facerecognition. Pattern Recognition，2008.41（12）：3813-3821

[13] 高小方.流形学习方法中的若干问题分析[J].计算机科学，

2009.36（4）：25-28