流形学习Manifold Learning 与Isomap
1.Manifold
“嵌入在高维空间中的低维流形”，最直观的例子通常都会是嵌入在三维空间中的二维或者一维流形。比如说一块布，可以把它看成一个二维平面，这是一个二维的欧氏空间，现在我们（在三维）中把它扭一扭，它就变成了一个流形（当然，不扭的时候，它也是一个流形，欧氏空间是流形的一种特殊情况）。
1.1判断流形的维数：
地球是一个流形，球面上的点，其实就是三维欧氏空间上的点，可以用一个三元组来表示其坐标。但是和空间中的普通点不一样的是，它们允许出现的位置受到了一定的限制，具体到球面，可以看一下它的参数方程：
可以看到，这些三维的坐标实际上是由两个变量 生成的，也可以说成是它的自由度是2，也正好对应了它是一个二维的流形。
1.2.引入测地线
Isomap通过“改造一种原本适用于欧氏空间的算法”，达到了“将流形映射到一个欧氏空间”的目的。
Isomap 所改造的这个方法是MDS，它的目的就是使得降维之后的点两两之间的距离尽量不变。只是 MDS 是针对欧氏空间设计的，对于距离的计算也是使用欧氏距离来完成的。如果数据分布在一个流形上的话，欧氏距离就不适用了。
让我们再回到地球——这个在三维空间中的二维流形，假设我们要在三维空间中计算北极点和南极点的距离，就是两点相连的线段的长度，可是，如果要在这个流形上算距离就不能这样子算了，我们总不能从北极打个洞钻到南极去吧？要沿着地球表面走才行，当然，如果我随便沿着什么路线走一遍，然后数出总共走了多少步作为距离，这是不成的，因为这样一来如果我沿着不同的路线走，岂不是会得到不同的距离值？总而言之，我们现在需要一个新的定义在地球表面（流形）上的距离度量，理论上来说，任意满足测度的 4 个条件的函数都可以被定义为距离，不过，为了和欧氏空间对应起来，这里选择一个直线距离的推广定义。
“两点之间，线段最短”，把线段的概念推广一下，变成“两点之间最短的曲线是线段”，于是流形上的距离定义也就等同于欧氏空间了：流形上两个点之间的距离就是连接两个点的“线段”的长度。虽然只是置换了一个概念，但是现在两者统一起来了，不过，在流形上的线段大概就不一定是“直”的了（于是直线也变成不一定是“直”的了），通常又称作是“测地线”。对于球面这个简单的流形来说，任意一条线段必定是在一个“大圆”上的，于是球面上的直线其实都是一些大圆，也造成了球面这个流形上没有平行线（任意两条直线均相交）。
1.3.可视化测地线
Isomap把 MDS 中原始空间中距离的计算从欧氏距离换为了流形上的测地距离。当然，如果流形的结构事先不知道的话，这个距离是没法算的，于是 Isomap 通过讲数据点连接起来构成一个邻接 Graph 来离散地近似原来的流形，而测地距离也相应地通过 Graph 上的最短路径来近似了。如下图所示：
这个东西叫做 Swiss Roll ，姑且把它看作一块卷起来的布好了。图中两个标黑圈的点，如果通过外围欧氏空间中的欧氏距离来计算的话，会是挨得很近的点，可是在流形上它们实际上是距离很远的点：红色的线是 Isomap 求出来的流形上的距离。可以想像，如果是原始的 MDS 的话，降维之后肯定会是很暴力地直接把它投影到二维空间中，完全无视流形结构，而 Isomap 则可以成功地将流形“展开”之后再做投影。
除了 Isomap 之外，ManifoldEmbedding 的算法还有很多很多，包括 Locally Linear Embedding 、Laplacian Eigenmaps 、Hessian Eigenmaps 、Local Tangent Space Alignment、SemidefiniteEmbedding (Maximum Variance Unfolding) 等。
1.4.Isomap应用于face和hand written digit
2.Isomap
Isomap是一种非线性的降维算法。一种非迭代的全局优化算法。它是一种等距映射算法，也就是说降维后的点，两两之间距离不变，这个距离是测地距离。测地距离，例如在地球上，要从南极到北极，欧式距离就是两点之间直线最短，测地距离则是曲线的长度，更符合实际情况。
Isomap算法是在MDS算法的基础上衍生出的一种算法，MDS算法是保持降维后的样本间距离不变，Isomap算法引进了邻域图，离得很近的点可以用欧氏距离来代替，较远的点可通过最短路径算出距离，在此基础上进行降维保距。
近邻连接图，图中邻近点之间存在连接，而非近邻点不存在连接，于是计算两个点之间测地线距离的问题，就转变成计算近邻连接图上两点之间的最短路径问题。
最短路径这里采用Floyd算法或Dijkstra算法。
2.1.计算流程如下：
Isomap仅是得到了训练样本在低维空间的坐标，对于新的样本，映射到低维空间的解决方案：将训练样本的高维空间坐标作为输入，低维空间坐标作为输出，训练一个回归学习器来对新的样本的低维空间坐标进行预测。
2.2．近邻图的构建方法
1. 指定近邻点个数，例如欧式距离最近的k个点为近邻点，这样得到的近邻图成为k近邻图，本文所使用的流程是这种方法。
2. 指定距离阈值，距离小于阈值的点认为是近邻点，这样得到的近邻图称为近邻图