“云行雨施，品物流形”，这是儒家经典《易经》对万物流变的描述。两千多年之后，“流形”一词被数学家借鉴，用于命名与欧几里得空间局部同胚的拓扑空间。

虽然流形这个词本身有着浓厚的学院派味道，但它的思想你却一点儿不会陌生。最著名的流形模型恐怕非瑞士卷（Swiss roll）莫属。如图所示的瑞士卷是常见的糕点，只是它的名字未必像它的形状一样广为人知。瑞士卷实际上是一张卷起来的薄蛋糕片，虽然卷曲的操作将它从二维形状升级成了三维形状，但这个多出来的空间维度并没有产生关于原始结构的新信息，所以瑞士卷实际上就是嵌入三维空间的二维流形。

瑞士卷（左）与瑞士卷流形（右）示意图

图片来自维基百科与 http://yinsenm.github.io/figure/STAT545/Swiss.png

在机器学习中，流形（manifold）指的是嵌入在高维数据空间中的低维子空间，它的维数是低维数据变化的自由度（degree of freedom of variability），也叫作固有维度（intrinsic dimensionality）。流形学习（manifold learning）正是通过挖掘数据的内在结构实现向固有维度的降维，从而找到与高维原数据对应的低维嵌入流形。

和主成分分析相比，流形可以是线性的，但更多是非线性的。正因如此，流形学习通常被视为非线性降维方法的代表。它不仅能够缓解维数灾难的影响，还具有比线性降维方法更强的特征表达能力。除了非线性外，流形学习的方法一般还是非参数的，这使流形能够更加自由地表示数据的固有维度和聚类特性，但也让它对噪声更加敏感。

要将数据从高维空间映射到低维流形上，首先要确定低维流形的结构，其次要确定高维空间到低维流形的映射关系。可在实际问题中，不管是流形结构还是流形维数都不是已知的，因此有必要做出一些先验假设以缩小问题的解空间。当关于流形的假设聚焦在数据的几何性质上时，就可以得到多维缩放（multiple dimensional scaling）算法。

在确定流形结构时，多维缩放让高维空间上的样本之间的距离在低维空间上尽可能得以保持，以距离重建误差的最小化为原则计算所有数据点两两之间的距离矩阵。根据降维前后距离保持不变的特点，距离矩阵又可以转化为内积矩阵。利用和主成分分析类似的方法可以从高维空间上的内积矩阵构造出从低维空间到高维空间的嵌入，其数学细节在此就不赘述了。

可是，原始高维空间与约化低维空间距离的等效性是不是一个合理的假设呢？想象一下你手边有个地球仪，这个三维的球体实际上也是由二维的世界地图卷成，因而可以约化成一个二维的流形。如果要在流形上计算北京和纽约两个城市的距离，就要在地球仪上勾出两点之间的“直线”，也就是沿着地球表面计算出的两个城市之间的直线距离。但需要注意的是，这条地图上的直线在二维流形上是体现为曲线的。

这样计算出的流形上的距离是否等于三维空间中的距离呢？答案是否定的。北京和纽约两点在三维空间中的欧氏距离对应的是三维空间中的直线，而这条直线位于地球仪的内部——按照这种理解距离的方式，从北京去纽约应该坐一趟穿越地心的直达地铁。这说明多维缩放方法虽然考虑了距离的等效性，却没能将这种等效性放在数据特殊结构的背景下去考虑。它忽略了高维空间中的直线距离在低维空间上不可到达的问题，得到的结果也就难以真实反映数据的特征。

吸取了多维缩放的经验教训，美国斯坦福大学的约书亚·泰宁鲍姆（Joshua Tenenbaum）等人提出了等度量映射的非线性降维方法。等度量映射（isometric mapping）以数据所在的低维流形与欧氏空间子集的等距性为基础。在流形上，描述距离的指标是测地距离（geodesic distance），它就是在地图上连接北京和纽约那条直线的距离，也就是流形上两点之间的固有距离。

在流形结构和维度未知的前提下，测地距离是没法直接计算的。等度量映射对这个问题的解决方法是利用流形与欧氏空间局部同胚的性质，根据欧氏距离为每个点找到近邻点（neighbors），直接用欧氏距离来近似近邻点之间的测地距离。

在这种方法中，测地距离的计算就像是奥运火炬，在每一个火炬手，也就是每一个近邻点之间传递。将每个火炬手所走过的路程，也就是每两个近邻点之间的欧氏距离求和，得到的就是测地距离的近似。

在每一组近邻点之间建立连接就可以让所有数据点共同构成一张带权重的近邻连接图。在这张图上，相距较远的两点的测地距离就被等效为连接这两点的最短路径，这个问题可以使用图论和网络科学中发展非常成熟的Dijkstra 算法来求解。计算出距离矩阵后，等度量映射的运算和多维缩放就完全一致了。

等距离映射原理示意图

图 A 表示测地距离与欧氏距离的区别，图 B 表示利用近邻点近似计算测地距离，图 C 表示真实测地距离与近似测地距离的比较，图片来自 A global geometric framework for nonlinear dimensionality reduction, Science, vol. 290, 2319-2323

等度量映射关注的是全局意义上数据的几何结构，如果只关注数据在某些局部上的结构，其对应的方法就是局部线性嵌入。

局部线性嵌入（locally linear embedding）由伦敦大学学院的萨姆·洛维思（Sam Roweis）等人提出，其核心思想是待求解的低维流形在局部上是线性的，每个数据点都可以表示成近邻点的线性组合。求解流形的降维过程就是在保持每个邻域中的线性系数不变的基础上重构原数据点，使重构误差最小。

局部线性嵌入的实现包括两个步骤：在确定一个数据点的近邻点后，首先根据最小均方误差来计算用近邻点表示数据点的最优权值，需要注意的是所有权值之和是等于 1 的；接下来就要根据计算出的权值来重构原数据点在低维空间上的表示，其准则是重构的近邻点在已知权值下的线性组合与重构数据点具有最小均方误差。对重构映射的求解最终也可以转化为矩阵的特征值求解。

局部线性嵌入原理示意图

图 A 表示为数据点 XiXi