浅谈流形学习及其算法

郝晨辉

摘 要：流形学习是借助几何学中子流形的概念，利用流形的结果和性质来挖掘嵌入在高维空间中的数据集的真实的低维结构。本文在介绍流形学习具体算法的基础上，通过MATLAB分析了不同算法的特点，对不同算法之间的关系进行了比较。基于此分析，我们对现有流行学习的缺点及局限提出了优化方法及改进方法。

关键词：流形学习；算法；映射；数据集

中图分类号：TP301.6 文献标识码：A 文章编号：1671-2064（2018）01-0219-04

1 引言

对于如今的机器学习来说，面临着所需处理的数据量、数据特征递增的趋势，但是有效的数据特征相对较少，为了减轻不必要的时间消耗，在处理数据之前都要对数据的特征进行稀疏化，一种方法是直接对数据的维数进行降维，来达到重要特征提取的目的。另一种是对数据的特征进行稀疏化，把没用的特征信息都设置为零，从而达到特征稀疏的目的。本文主要从降维这个角度来进行探讨。

早期主要的降维方法是线性降维算法主成分分析法PCA[6]，其主要过程是研究一个线性降维映射，将高维空间中的样本点集投影到低维空间中。PCA[6]通过最大化数据点集之间的协方差矩阵来选取数据点集分布的最主要的特征，从而达到降维的目的。这种算法适用于处理的数据集呈现线性分布。但是针对分布呈现复杂的非线性分布，PCA很难达到较好的降维效果。非线性分布的高维样本点集，其所在的非线性空间可以看成是嵌入在高维空间的低维非线性子空间。在机器学习中通常采用kernel函数的方法来进行处理，称之为kernel PCA[7]。这种算法存在的问题是很难选择一个合适的kernel函数，如果kernel选择的不合适反而会对学习过程造成很大的影响，增加学习的时间消耗，且最终的降维效果也不会很好。

针对复杂的非线性分布的数据点集，虽然全局结构无法获得，但我们可以看出数据点集的很小的局部邻域结构还是呈现出线性分布结构。对于这种局部呈现出线性结构而全局呈现出非线性结构的数据点，我们将其假设成分布在某个流形上，其降维过程称为流形学习。

流形学习是一类借鉴拓扑流形概念的降维方法。“流形”是在局部与欧氏空间同胚的空间，直观上来说“流形”的局部邻域可以近似的看成是欧氏空间结构。根据流形的这个性质所设计出的流形学习算法都是从流形的局部结构出发通过保持流形的局部线性结构来对高维样本点集进行降维。当然流形的全局结构也是从局部结构出发来获取全局的结构。流形学习算法，大致可以分为两大类，都是在假设流形的局部邻域为线性空间基础上进行的。一类是保持全局结构的非线性降维算法，如Isomap[2]：Isomap又称为等距映射算法，目的是保持降维前后任意两点之间的真实的距离结构。在流形上，任意两点之间的真实的距离不是两点之间的欧氏距离，而是两点之间的测地线距离。所以Isomap旨在保持任意两点之间的测地线距离。另一类是保局部结构的降维算法，如LLE[1]，LEP[3]，LPP[9]，LTSA[5]，HLLE[4]等。LLE算法旨在保持样本点局部邻域的线性组合结构，通过假设高维样本点的局部邻域是线性结构，然后计算每个样本点与其邻域点之间的线性相关系数，由此在低维空间中邻域点之间还保持相同的线性相关性。LEP算法旨在保持局部样本点之间的结构，降维的主要思想是距离较近的点降维后还是距离较近，在算法设计中通过建立样本点集之间的局部邻域图结构，任意两点之间的边赋予相应的权重，通过权重来体现局部邻域点之间的距离关系。LPP继承了LEP算法的思想，给出保持局部结构的线性降维算法。LTSA算法也是将流形的局部邻域假设成线性空间，然后在局部邻域上利用PCA进行降维。

2 基本知识介绍

流形学习算法的共有的前提假设是，所要降维的高维样本点集分布在某个非线性流形F上，此流形是嵌入在高维欧氏空间中的一个子流形。流形学习的目的是从高维空间中挖掘出子流形F的真实的低维表示结构。为了算法的需求，我们假设高维样本点集表示为{x1，x2，…，xN}∈FRD，其中N表示样本点集的个数，D表示高维样本点集的维数。对应的低維样本点集表示为{y1，y2，…，yN}∈YRd，其中d表示低维样本点集的维数。基于此目的，我们给出流形学习的形式化定义。

流形学习的目的是挖掘高维样本点集产生的机制，表示为映射f，具体的表示形式如下：f：Y→FRD。

在降维过程中，流形的全局或局部几何结构得到保持。

3 算法描述

3.1 等距映射

Isomap[2]又称等距映射算法，其目的是保持降维前后所有样本点集之间的全局距离结构。Isomap借助MDS[8]来挖掘高维样本点集之间真实的内在结构。MDS[8]是保持降维后高维样本点集之间的欧氏距离结构。而Isomap旨在保持样本点集之间真实的距离结构。在流形上，两点之间真实的距离不是欧氏距离，而是两点之间的测地线距离。在此算法中，通过构造样本点之间的局部图结构，然后任意两点之间的测地线距离通过寻找两点之间的最短路径来获得。

算法步骤如下：

（1）确定原空间每个点的邻域点（找样本点的近邻点方法有两种：1）是规定k的值即取距离样本点最近的k个近邻点。2）是规定一个球的半径E，以样本点为球心，找出这个球覆盖的样本点。）

（2）估算测地线距离（高维空间中较近点之间的测地线距离用欧式距离代替，较远点距离用测地线距离，最短路径逼近，计算公式为dG（i，j）=min{dG（i，k）+dG（k，j）}，其中dG（i，j）表示点i与点j之间的欧氏距离），从而构造所有数据点之间的距离矩阵D。

（3）用MDS在低维欧式空间找到点间距符合第一步中距离的点{y1，y2，…，yN}∈Rd。

MDS算法：

输入主对角线元素为零的距离矩阵D。endprint

（2）计算B矩阵的谱分解

（3）通过求出形成矩阵

（4），我们取矩阵X的前d个列向量所组成的矩阵XN×d作为低维输出。

其中H是半正定矩阵，D是非负对称矩阵，B是格拉姆矩阵

此种算法的优点是：1）具有估计低维空间维数的作用，不用给定低维空间的维数。2）整体等距映射到低维空间，无需考虑局部坐标之间的相容性。3）很好的识别了非线性流形结构。

3.2 局部线性嵌入映射

LLE[1]又称局部线性嵌入映射，此算法假设样本点所在的子流形的局部邻域是线性结构。与Isomap算法不同，LLE算法旨在保持样本点集的局部邻域的线性结构，其基本思想可以简单的表示如下：流形上任意数据点p∈M，都可以用其K-邻域内的K个邻近点近似线性表示，然后在低维欧式空间中重构一组低维样本点表示{y1，y2，…，yN}，使得这些低维样本点集的局部邻域点之间也满足原始数据点之间的线性组合关系。

算法步骤如下：

（1）找每个样本点{x1，x2，…，xN}的近邻点（方法同Isomap）。

（2）计算高维邻域点之间的局部权值矩阵Wij，其中xij为xi的k个近邻点。满足代价函数并满足约束条件。

定义一个误差函数，如下：

误差函数值越小，说明局部权值矩阵重建的越好，说明xi越接近其近邻点的线性组合的点。

（3）在低维空间重构一组样本点{y1，y2，…，yN}，使得其保持高维邻域点之间的线性相关关系。

此种算法的优点是：1）算法中建立的权值矩阵是一个稀疏矩阵，计算量较小；2）算法具有整体最优解（低维欧式空间所对应的所有数据点表示），不需要迭代，减少了计算的复杂性。

3.3 拉普拉斯特征映射

拉普拉斯特征映射（LEM）[3]借助Laplace矩阵的性质来对高维样本点集进行降维。其与LLE算法思想基本相似，保持高维样本点集的局部几何结构。LEM的目的就是寻找原始数据流形在低维欧式空间的对应表示，LEP算法有着很直观的降维目标，即在高维空间中离得很近的点投影到低维空间中的像也应该离得很近，这能够保持局部几何结构不变。基于此，LEM算法所要优化的目标函数为。

其中Y表示低维数据点集的矩阵表示形式，矩阵L=D-W是拉普拉斯矩阵。限制条件YTY=I保证优化问题有非奇异解，并且保证映射后的数据点不会被“压缩”到一个小于m维的子空间中。基于这样的算法思想，我们给出LEP算法的基本步骤。

算法步骤：

（1）根据K-邻域法选择每一点处的k个近邻点集。

（2）将每个样本点的k个近邻点连接成邻接图。

（3）构造数据点集上的权值矩阵W，W的每个分量表示相应两点之间的权重。

（4）计算拉普拉斯矩阵L的特征向量与特征值。

使用最小的d个非零特征值对应的特征向量作为降维后的输出结果，其中d表示低维空间的维数。

此种算法的优点是：通过求解稀疏矩阵的特征值可以求出整体最优解。

4 算法实践及分析

分别选取两类数据集对各类流形学习算法的降维效果进行对比分析。一类数据集为仿真数据集，我们分别选取两组仿真数据集：Swiss Roll和Punctured Sphere。另一类数据集为真实世界中的数据集，USPS手写体识别数据集。首先对仿真数据集进行实验分析，然后对USPS数据集进行分析。

4.1 仿真数据集

Swiss Roll以及Punctured Sphere为两组三维数据点集，其每一个数据点都是由一个三维向量进行表示。在本实验中，我们分别采取800个Swiss Roll数据点以及1000个Puncture Sphere数据点进行实验。所有这些数据点所在的非线性流形是嵌入在三維空间中的二维流形。我们分别采用三种流形学习算法对这两组数据集进行降维，将其降维到二维空间中。这三类算法分别为等距映射（Isomap）、局部线性嵌入（LLE）、拉普拉斯特征映射（LEP）。由于这三类算法都受局部邻域因子K值的影响，所以在实验阶段，我们分别选取不同的K值，然后来分析在不同的K值下三类算法的降维效果。

4.1.1 实验过程

首先给出Swiss Roll数据集的实验过程。此数据集包含800个三维数据点，我们分别选取邻域因子K=8，12，16。其对应的降维结果如下图1所示，其中图中第一行表示K=8时三个算法的降维结果，第二行表示K=12时的降维结果，第三行表示K=16时的降维结果。

Puncture Sphere数据集是一组采样与二维球面上的三维数据点集。我们采取1000个数据点，与Swiss Roll相同，我们分别选取K=8，12，16。其相应的降维结果如图2所示。

4.1.2 实验结果

由Swiss Roll图可知，Isomap降维的效果明显好于其他两种算法。LLE和LEP这两种方法降维后的图形较为相似，这是由于两种算法都是假设样本点所在的子流形的局部邻域是线性结构。但我们并不能从LLE和LE两种方法降维后的图形辨认出原始流形，之所以瑞士卷降维后呈现这样的图形是因为这两种算法只是保持了流形的局部结构，对于全局结构没有得到很好的保持，所以降维后的结果只是在局部邻域中效果比较好，从算法来看，这两种算法对流形的全局结构并没有做约束。当K值增大到16时，这两种局部线性嵌入方法降维后的准确度降低，降维的效果变得不好。这是因为K是局部邻域的大小，当K增大时，局部邻域范围就会变大，所以表面上局部邻域已经不呈现出线性结构，但潜在的原因是降维过程中并没有考虑到局部邻域的曲率结构，所以会出现这些结果。

针对Puncture Sphere数据集，LEP算法的降维效果明显好于其余两个算法。且随着K值的增加，LEP的降维效果并没有明显的降低。从算法本身分析其结果我们可以看出，LLE算法目的是要保持降维前后数据点邻域的线性结构，而针对Puncture Sphere数据集，其是采样与球面的数据集，所以每个数据点的局部邻域的线性结构非常的弱。而针对Isomap算法，其是为了保持样本点集降维前后的全局结构，所以从降维结果可以看出，虽然在全局上，降维后的流形依然保持球面的整体结构，但是每个数据点的局部邻域结构在降维过程中并没有得到很好的保持。endprint

4.2 真实世界数据集

对流形学习的算法做进一步实验，用局部线性嵌入（LLE）、主成分分析（PCA）以及拉普拉斯特征映射（LEP）三种方法对USPS手写体的图像数据集进行降维，然后再对降维后的数据点进行分类识别。USPS手写体数据集包含9298个数据点，每个数据点都由一张手写体数字图像表示。此数据集一共包含十类手写体分别为从0到9，每张图像像素经过处理表示为16×16的像素矩阵。所以在降维阶段，我们将每个像素矩阵按行排列成一个256维的行向量来表示一张图像的特征。

4.2.1 实验过程

实验过程主要分为两步进行。第一步是利用降维算法对数据集进行降维，在本实验中我们分别采用三类降维算法：PCA，LLE，LEP对数据集进行降维。其中降维后的低维空间维数选择为d=10。第二步是对降维后的数据集进行分类识别，在此步中我们采用K近邻分类器来进行训练，然后采用交叉验证法来进行测试。由于在降维过程中，流形学习算法受邻域因子取值的影响。所以在此实验中，我们同样采取不同的邻域因子K的值来进行实验，其中K=1：5：31。其相应的实验结果表示如下图3所示。

4.2.2 實验结果

从图3可以看出，三种方法中LLE和LEP的识别准确率都随着K值的增大而减小，而PCA算法的准确率则随着Knn的值增大而呈现稳定的状态，其具体的实验分析如下。

LLE算法识别准确率的趋势较为明显，当Knn初始值为5时识别准确率的值为0.9800，随着Knn值的增大识别准确率逐渐降低一直到0.9200（Knn=25）。LEP算法在Knn=5的情况下，数据集的分类准确率最高。而随着邻域因子的增大，其实别准确率也呈现出下降的趋势。PCA算法的目的是学习一个全局的线性降维映射，所以其算法过程与邻域因子之间没有任何关系，所以其在不同的邻域因子下分类的准确率基本上保持不变。

5 结论与展望

本文主要给出了流形学习的三类算法，通过三组实验结果来分析了不同降维算法的降维效果。通过对各个算法的理论分析以及实验结果分析可以看出，这些流形学习算法虽然有很多优点，但是其本身还存在很多的缺点。（1）三类算法都对邻域因子K非常的敏感，当K值非常大的时候，三类算法的降维效果就非常的差。（2）三类算法对流形真实的维度不能进行很好的估计，很多情况下都需要我们事先给定低维维度的取值。这对于挖掘流形真实的几何结构非常的不利。造成这些局限性的一个重要的原因是，这三类算法并没有准确的挖掘流形真实的局部几何结构。如Swiss Roll数据集，当K值非常大的时候，三类算法的降维效果都非常的差，造成这种结果的一个很重要的原因是，三类算法都假定流形的局部邻域为线性空间，而并没有考虑流形真实的曲率结构。

所以针对这些局限性，我们接下来的工作将会尝试设计新的算法，挖掘流形的局部曲率结构，来对传统的流形学习算法进行修正。

参考文献

[1]Roweis， S. And Saul， L. “Nonlinear dimensionality reduction by locally linear embedding”.Science，290（5500）：2323-2326，2000.

[2]Tenenbaum， J.， de Silva， V.， and Langford， J.“A global geometric framework for nonlinear dimensi-onreduction”.Science，290（5500）：2319-2323，2000.

[3]Belkin， M. and Niyogi， P.“Laplacian eigenmaps and spectral technique for embedding and clusteri-ng”.In Advances in Neural Information Processing Systems 14， pp. 585-591，2001.

[4]Donoho，D.L. And Grimes，C.E.“Hessian eigenmaps： Locally linear embedding techniques for hig-h-dimensional data”.Proceedings of the National Academy of Sciences of the United States of America，100（10）：5591-5596，2003.

[5]Z， Zhang and H，Zha.“Principal Manifolds and Nonlinear Dimension Reduction via Local Tangent Space Alignment”.SIAM J. ScientificComputing， vol. 26， no. 1， pp. 313-338， 2005.

[6]Jolliffe， I.T. “Principal Component Analysis”. Springer-Verlag， New York， 1989.

[7]Scholkopf， B.， A. Smola and K.-R. Muller.“Nonlinear component analysis as a kernel eigenvalue problem”， Neural Computation，10（5）：1299-1319.

[8]Cox T. F. and M. A. Cox. “Multidimensional Scaling”. Chapman & Hall/CRC， London， UK.

[9]Xiaofei He，ParthaNiyogi.“Locality Preserving Projections”，Int. Conf. Advances in Neural Information Processing Systems，2003.endprint