一、概述

流形学习（Manifold Learning）是指通过从高维采样数据中恢复低维流形结构，即找到高维空间中的低维流形，并求出相应的嵌入映射，以实现降维或者数据可视化。拿地球举例来说就是地球的表面可以认为是一个二维平面被塞到了三维空间中，那么欧氏距离（Euclidean Distance）就只能在短距离内成立，在较远的距离就不再成立：

                             地球

再举一个例子，在下图中可以认为一个二维平面被扭曲放入一个三维空间中，在很小的距离内欧式举例是成立的：

                        短距离

而如果距离太远的话则可能欧氏距离就不成立，如下图所示，黑点到蓝点的欧氏距离比到红点的欧氏距离更小，但是从数据分布上来看黑点和红点更加相似一些，这时欧式距离就没有意义了：

                   远距离

对于上面的例子，流形学习要做的就是学习数据在低维空间的表示形式，通俗来说，就是将上图中的数据“展开”：

                       数据

这样的数据显然更容易用来进行聚类或者其他的监督学习方法。接下来的部分介绍几种流形学习的方法。

二、Locally Linear Embedding（LLE）

Locally Linear Embedding（LLE）是一种非线性降维算法，可以使降维后的数据保持比较好的原有的流形结构。

                                                    原数据

                                               降维后的数据

在使用LLE进行降维时，选择邻域内的几个点是一个可以调整的超参数，选用过少或过多的点效果都不会太好，选择过多邻居的局限性在于这样会考虑进一些距离较远的点，而欧氏距离在远距离的效果不太好。下图展示了不同数量的邻近点的效果：

                                                效果

三、Laplacian Eigenmaps

1. 简介

拉普拉斯特征映射（Laplacian Eigenmaps）是一种基于图的降维算法，依赖于平滑性假设（Smoothness Assumption），其希望降维后的点（图中有边相连的点）在降维后的空间中能够相互接近，从而保持其原有的数据结构。

2. 图的构建

具体地，假定在高维空间中有下图的数据点，则两个红色数据点之间的距离使用欧氏距离来度量的话是没有意义的，数据点之间在流形中的距离才可以表明其相似的程度。

                                      数据

使用拉普拉斯特征映射的方法首先需要构建一张图，构建的方法就是将相似度高的点之间连一条边，可以设置一个阈值，每个点与其相似度达到阈值的点之间连接一条边，边的权重就是相似度，也可以将每个点与固定 个最相似的点连接起来。相似度可以采用径向基函数或者余弦相似度等等。

得到的图如下：

                                         图

两个数据点在流形中的距离可以用图中的距离来近似：

                                    距离

3. 类比半监督学习

参考以下链接中平滑性假设基于图的方法这一部分：半监督学习|深度学习（李宏毅）（九）

在半监督学习平滑性假设基于图的方法中，通过给损失函数添加一个正则化 项可以利用无标签数据进行半监督学习， 用来评估标签的相关性，这个正则化项为：

 

                                           图的度矩阵

4. Laplacian Eigenmaps

对降维后的数据再进行聚类就是谱聚类（Spectral Clustering）算法。

这里的拉普拉斯特征图的降维方法可以参考以下更详细的讲解：谱聚类|机器学习推导系列（二十）。

四、T-distributed Stochastic Neighbor Embedding（-SNE）

1. 上述方法的问题

在上面描述的邻域嵌入方法中存在的问题是，在重建低维空间中的表示时只考虑了让较高相似度的样本点要尽可能地接近，而没有考虑让低相似度的样本点要尽可能地远，这样会导致不同类别的样本点会集中在一起，也就是拥挤问题。下图展示了使用LLE处理MNIST和COIL-20数据集时的效果，COIL-20是一个图片数据集，里面的样本是某件物品（玩具车、杯子等）旋转不同角度拍下的照片：

                                                LLE

可以看到不同类别的样本被挤到了一起，这就是上述问题导致的结果。

2. t-SNE

在求解时使用梯度下降对 微分即可。需要说明的是t-SNE是对所有的数据进行计算相似度，如果维度过高则会需要巨大的计算量，因此通常的做法是先使用PCA等方法进行降维然后再使用t-SNE继续降维，比如先使用PCA降到50维，再使用t-SNE继降到2维。

同时需要说明的是t-SNE降维后，如果一个新的数据进来，我们无法获得该数据的降维表示，因此t-SNE不适用于train-test的模式，这种方法通常用于数据的可视化。

3. 相似度的度量

选用上述相似度度量也就可以避免拥挤问题，原因使用下面的图来说明。在下图中横轴表示两个样本点的距离，纵轴表示概率分布。在优化时我们会让原来的数据的概率与降维后的数据的概率相等，可见如果原来的数据中的两个样本点距离很近时，在降维后的数据中距离也会很近，而如果原来的数据中的两个样本点距离很远，则在降维后的数据中其距离会被拉伸地更远：

                                                拥挤问题

4. 效果

下图展示了t-SNE在MNIST和COIL-20数据集上的效果：

                                                      效果

可以看到t-SNE取得了一个比较直观的可视化效果，不同类别的样本被区分地很明显。