工作之一。很多后续的流形学习、降维方法都与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
相关热词搜索： 流形 算法 分析 学习