登录Isomap是一种结合主成分分析（PCA）和MDS(multidimensional scaling)的主要算法特征——计算效率，全局最优性和渐近收敛保证——以及灵活性来学习一大类非线性流形的方法。 Isomap方法建立在经典的MDS上，但试图保留数据的固有几何形状。问题的关键在于只给出输入空间距离，如何估计远处点之间的测地距离（geodesic distance）。对于相邻点，输入空间距离提供了近似于测地距离的近似值。对于遥远点，测地距离可以通过在相邻点之间加上一系列“短跳”来近似。这些近似值可通过在连接相邻数据点的边上查找图中的最短路径来高效计算。
完整的等距特征映射或Isomap算法有三个步骤：第一步在输入空间X内根据点对i，j之间的距离dX（i，j）确定哪些点是流形M上的邻点，两个简单的方法是将每个点连接到某个固定半径ε内的所有点，或连接到其所有K个最近邻点。这些邻域关系在数据点上表示为加权图G，相邻点之间的权重为x（i，j）如下图所示：
在Isomap的第一步（K = 7和N = 1000个数据点）中构造的邻域图G将允许我们在步骤2中有效地计算真实测地路径的近似（红色分段），作为G中的最短路径。
在第二步中，Isomap通过计算图G中它们的最短路径距离d_G（i，j）来估计流形M上所有点对之间的测地距离d_M（i，j）。
最后一步将古典MDS应用于图距离矩阵D_G = {d_G（i，j）}，目标是构造一个最能保留流形的内在几何估计的数据在d维欧氏空间Y中的嵌入，如下图所示：
这可以通过选择Y中的点的坐标向量i以最小化成本函数来实现：
其中D_Y表示欧几里得距离矩阵{d_Y（i，j）= || y_i -y_j ||}，|| A ||_{L^2]表示L^2规范\sqrt(\sum_{i,j}A_{ij}^2)。 τ运算符将距离转换为点积，它能唯一地表征数据的几何特征，并且运算高效。 上述方程式的全局最小值可以通过将坐标y_i设置为矩阵τ（D_G）的顶部特征向量来实现。
正如PCA和MDS在理论上讲，给定足够的数据可以恢复线性流形的真实结构，Isomap可以保证渐近地恢复较大数据集的非线性流形的真实维数和几何结构。 像瑞士卷一样，这些流形的内在几何形状是欧几里德空间的凸形区域，但其高维输入空间中的环境几何形状可能高度折叠，扭曲或弯曲。 对于非欧几里德流形，例如半球或甜甜圈的表面，Isomap仍然能够产生全局最优的低维欧几里德表示。
下图对上文提到的三个步骤进行了一个总结：
[图片及描述来源：Tenenbaum, J. B.; de Silva, V.; Langford, J. C. (2000). A Global Geometric Framework for Nonlinear Dimensionality Reduction, Science 290: 2319–2323.]
发展历史
2000年，Joshua B. Tenenbaum，Vin de Silva与John C. Langford提出Isomap，是一种基于MDS与Manifold的降维演算法。 2002年Balasubramanian和Schwartz指出，过大的K值或者数据中的噪声稍微偏离流形很容易导致“短路误差”。
2003年，Joshua B. Tenenbaum，Vin de Silva又提出了LandMark ISOMAP（L-ISOMAP），这是Isomap的一个变体，它比Isomap快。该算法在全部N个数据点中使用n << N个地标点，并且计算每个数据点与地标点之间的测地距离的n×N矩阵。 然后将Landmark-MDS（LMDS）应用于矩阵以找到所有数据点的欧几里得嵌入。他们同时还提出了 C-Isomap，涉及放大高密度区域并缩小低密度的区域。在多维尺度（MDS）中最大化的边缘权重会被修改，其他一切都不会受到影响
2004年Ashutosh Saxena, Abhinav Gupta, Amitabha Mukerjee对Isomap算法进行了改进，使其对稀疏和有噪声的数据集更好地工作。
主要事件
| 年份 | 事件 | 相关论文/Reference |
| 2000 | Joshua B. Tenenbaum，Vin de Silva与John C. Langford提出Isomap | Tenenbaum, J. B.; de Silva, V.; Langford, J. C. (2000). A Global Geometric Framework for Nonlinear Dimensionality Reduction, Science 290: 2319–2323. |
| 2002 | Balasubramanian和Schwartz指出，过大的K值或者数据中的噪声稍微偏离流形很容易导致“短路误差” | Balasubramanian, M.; Schwartz, E. L. (2002). The Isomap Algorithm and Topological Stability. Science. 295(5552): 7. |
| 2003 | Joshua B. Tenenbaum，Vin de Silva又提出了LandMark ISOMAP（L-ISOMAP） | Tenenbaum, J. B.; de Silva, V.. (2003). Global Versus Local Methods in Nonlinear Dimensionality Reduction. Adv Neural Inf Process Syst. 15. |
| 2004 | Ashutosh Saxena, Abhinav Gupta, Amitabha Mukerjee对Isomap算法进行了改进，使其对稀疏和有噪声的数据集更好地工作 | Saxena, A.; Gupta, A.; Mukerjee, A. (2004).Non-linear Dimensionality Reduction by Locally Linear Isomaps. ICONIP2004. pp 1038-1043. |
发展分析
瓶颈
生成的邻域图对临近点的数量k的选择敏感，太大的k值很容易带来“短路误差”，即使是单个短路错误也可以改变测地距离矩阵中的许多条目，这反过来可能导致极大地不同（并且不正确）的低维嵌入。 相反，如果k太小，则邻域图可能变得太稀疏而无法准确地近似测地路径。
未来发展方向
Isomap的优势在于它非常适合十分非线性的数据，并且可以很好地用于可视化，因此具有这两个特征的降维学习都可以考虑Isomap。
Contributor：Yuanyuan Li
