等距映射

等距映射 (Isometric Mapping, Isomap)

等距映射（Isometric Mapping），简称 Isomap，是流形学习中一种经典的非线性降维算法，由 Tenenbaum、de Silva 和 Langford 于 2000 年在《Science》上提出。Isomap 的核心思想是在保持数据点之间测地距离（geodesic distance）的前提下，将高维数据映射到低维空间。与传统的主成分分析（PCA）和多维尺度分析（MDS）不同，Isomap 能够有效处理非线性流形结构，在保留数据内在几何特征方面显著优于线性方法。

核心原理与算法步骤

Isomap 建立在经典 MDS 的基础之上，但将欧氏距离替换为更能反映流形真实结构的测地距离。算法分为三个核心步骤。

第一步：构建近邻图。 对于给定的高维数据集 $\{x_1, x_2, \ldots, x_n\} \subset \mathbb{R}^D$，对每个数据点确定其 $k$ 个最近邻（k-NN），或设定半径 $\epsilon$ 连接所有距离小于 $\epsilon$ 的点。由此构造加权无向图 $G$，节点为数据点，边的权重为两点之间的欧氏距离 $d(x_i, x_j)$。近邻图是 Isomap 的核心，其连通性决定了算法能否正确捕捉流形结构。

第二步：计算测地距离。 在图 $G$ 上运行最短路径算法（通常使用Dijkstra算法或 Floyd-Warshall 算法），计算所有点对之间的最短路径距离 $d_G(x_i, x_j)$。当近邻图充分稠密时，图上的最短路径距离趋近于流形上的真实测地距离。这一估计的准确性取决于采样密度和近邻参数 $k$ 或 $\epsilon$ 的选择。

第三步：低维嵌入。 将测地距离矩阵 $D_G = [d_G(x_i, x_j)]$ 输入经典多维尺度分析（classical MDS），求解如下优化问题：寻找低维嵌入 $y_i \in \mathbb{R}^d$（$d \ll D$），使得

经典 MDS 通过对距离矩阵进行双中心化和特征分解得到解析解：设 $B = -\frac{1}{2} H D_G^2 H$（其中 $H$ 为中心化矩阵），保留 $B$ 的 $d$ 个最大正特征值 $\lambda_1 \ge \cdots \ge \lambda_d > 0$ 及对应特征向量，嵌入坐标为 $Y = V_d \Lambda_d^{1/2}$。

关键参数与局限性

Isomap 有两个关键参数需谨慎选择。近邻数 $k$（或半径 $\epsilon$）过小会导致近邻图不连通，测地距离估计失败；过大则会使测地距离退化为欧氏距离，丧失非线性降维优势，即出现"短路"（short-circuit）问题。目标维数 $d$ 可通过特征值谱的下降趋势（残差方差法）或交叉验证来估计。

Isomap 的主要局限包括：对噪声和离群点敏感，近邻图易被破坏；不能处理非凸流形（图最短路径可能穿越"空洞"）；计算量为 $O(n^3)$（全对最短路径），不适合超大规模数据；无法对新样本进行天然的外推（out-of-sample extension），需要额外近似方法（如 Landmark Isomap）。尽管如此，Isomap 作为流形学习的里程碑方法，在计算机视觉、图像处理、生物信息学等领域的非线性数据结构分析中有着广泛的应用。