卷起来的二维面怎样被摊平？Isomap 的测地距离与经典 MDS

上一篇的谱聚类把样本变成相似图，再用图拉普拉斯的低频特征向量寻找离散簇。但一卷带颜色的纸并没有天然簇：我们更想恢复纸面上连续的横纵坐标，让相邻颜色仍相邻、沿纸面很远的点也不要被折叠误导。

等距映射（Isometric Mapping，Isomap）把这个问题拆成三步：**用近邻图限制可走的局部边，用最短路近似沿流形的测地距离，再用经典多维尺度分析恢复低维坐标。**本文只讲透这条数据流。

01 PCA 为什么会把卷起来的纸压扁？#

主成分分析（Principal Component Analysis，PCA）只能寻找一个全局线性子空间。对瑞士卷（Swiss Roll）式数据，纸面上相距很远的两层可能在三维空间中几乎贴在一起：

纸面真实顺序                  卷起后的三维截面

A—B—C—D—E—F                  C ··· D
沿纸面距离逐步增加           B       E
                             A ··· F

A 到 F：沿纸面很远           A 到 F：直线穿过空气却很近

text

直接保存原空间欧氏距离会把 A—F 误当近邻；PCA 的直线投影也可能把不同层叠在一起。Isomap 的流形假设（Manifold Assumption）是：高维观测位于一个低维、局部近似平坦的曲面上。小范围欧氏距离可信，全局距离必须沿曲面累加。

02 从高维样本到低维坐标经历什么？#

设输入 $X\in\mathbb R^{N\times D}$ ，近邻数为 $K$ ，输出维数为 $d$ ：

X [N,D]
  │ 每点找 K 个近邻
  ▼
G [N,N] 稀疏加权图：局部边权 = 原空间距离
  │ 全源最短路
  ▼
D_geo [N,N]：图上的测地距离估计
  │ 平方、双中心化
  ▼
B = -1/2 H (D_geo ⊙ D_geo) H [N,N]
  │ 最大 d 个正特征值/特征向量
  ▼
Y = V_d Λ_d^(1/2) [N,d]

text

$G$ 只允许沿局部边移动； $D_{geo,ij}$ 是从 $i$ 到 $j$ 的最短路径长度。经典多维尺度分析（Classical Multidimensional Scaling，Classical MDS）再寻找一组点，使其两两欧氏距离尽量复现 $D_{geo}$ 。

03 近邻图怎样决定“能走哪里”？#

常见做法是把每个样本连到 $K$ 个最近邻，边权保留原始距离：

w_{ij}=\lVert x_i-x_j\rVert_2

注意这里的权重是距离，越小越近；上一篇谱聚类的 affinity 是相似度，越大越近。无边位置应视为 $+\infty$ ，不能填 0。

有向 K 近邻关系通常会被对称化。 $K$ 太小，图会断开，跨分量距离为无穷； $K$ 太大，近邻边可能从卷的一层穿到另一层，形成短路（Short Circuit）。因此 $K$ 不是普通的“越大越平滑”，而是在连通性与局部性之间取舍。

04 最短路如何近似测地距离？#

设四个点沿一条弯曲细带依次相邻，每条局部边长度为 1：

A ━1━ B ━1━ C ━1━ D

text

虽然高维坐标里 A 与 D 可能靠得很近，近邻图没有 A—D 穿透边。Dijkstra 或 Floyd–Warshall 算法得到：

D_{geo}=\begin{bmatrix} 0&1&2&3\\ 1&0&1&2\\ 2&1&0&1\\ 3&2&1&0 \end{bmatrix}

例如 $D_{geo}(A,D)=1+1+1=3$ 。采样足够密、图边确实局部时，许多小弦长度之和可逼近曲面上的弧长；采样稀疏或噪声大时，这个近似会失真。

05 经典 MDS 怎样从距离恢复坐标？#

坐标若已中心化，Gram 矩阵 $B=YY^\top$ 保存内积。距离平方满足：

d_{ij}^2=B_{ii}+B_{jj}-2B_{ij}

令中心化矩阵

H=I-\frac1N\mathbf1\mathbf1^\top

对距离平方矩阵做双中心化，可消去每行、每列的未知平方范数：

B=-\frac12H(D_{geo}\odot D_{geo})H

对上面的四点链，结果恰为：

B=zz^\top,\qquad z=[-1.5,-0.5,0.5,1.5]^\top

它只有一个正特征值 5。取对应单位特征向量 $v$ ，坐标 $y=v\sqrt5$ 就恢复了 $z$ （整体翻转也等价）。原本弯曲的四点被摊成等间距直线。

若 $B=V\Lambda V^\top$ ，取最大的 $d$ 个正特征值：

Y=V_{[:,1:d]}\Lambda_{1:d}^{1/2}\in\mathbb R^{N\times d}

负特征值表示输入距离并不能被目标欧氏空间精确实现；大量或很大的负值常提示图短路、噪声、错误度量或目标维数/流形假设不合适。

06 完整训练伪代码#

input: X [N,D], K, d
neighbors = knn(X, K)                         # [N,K]
G = infinity(N,N); diagonal(G) = 0            # [N,N]
for each local edge (i,j):
    G[i,j] = distance(X[i], X[j])
G = symmetric_union(G)

D_geo = all_pairs_shortest_path(G)            # [N,N]
assert every entry is finite
H = I - ones(N,N) / N                          # [N,N]
B = -0.5 * H @ (D_geo ** 2) @ H               # [N,N]
eigenvalues, V = eigh(B)                       # 升序
take largest d positive eigenpairs
Y = V_d * sqrt(eigenvalues_d)                  # [N,d]
return Y, G, D_geo

text

07 用 NumPy 写出手算例的核心#

下面从已知局部图开始，不调用 Isomap。Floyd–Warshall 的三重循环明确展示“是否经过节点 $k$ ”的动态更新：

import numpy as np

inf = np.inf
G = np.array([
    [0.0, 1.0, inf, inf],
    [1.0, 0.0, 1.0, inf],
    [inf, 1.0, 0.0, 1.0],
    [inf, inf, 1.0, 0.0],
])                                                   # [N=4,N=4]

D_geo = G.copy()
for k in range(4):
    D_geo = np.minimum(
        D_geo,
        D_geo[:, k, None] + D_geo[None, k, :],
    )                                               # [N,N]

H = np.eye(4) - np.ones((4, 4)) / 4
B = -0.5 * H @ (D_geo ** 2) @ H
eigenvalues, eigenvectors = np.linalg.eigh(B)
order = np.argsort(eigenvalues)[::-1]
value = eigenvalues[order[0]]
Y = eigenvectors[:, order[:1]] * np.sqrt(value)     # [N,1]

assert np.allclose(D_geo[0], [0, 1, 2, 3])
assert np.allclose(np.sort(np.diff(np.sort(Y[:, 0]))), [1, 1, 1])
assert np.allclose(Y.mean(axis=0), 0)

python

真实数据不应自己写 $O(N^3)$ 的 Python 循环；这段代码只用于验证公式和张量语义。

08 用 scikit-learn 1.9 正确落地#

当前官方 Isomap API ↗ 同时支持近邻数或半径图、不同距离度量、最短路与特征求解器：

import numpy as np
from sklearn.manifold import Isomap, trustworthiness
from sklearn.preprocessing import StandardScaler

scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train)      # [N,D]

isomap = Isomap(
    n_neighbors=12,         # 使用 KNN 时 radius 必须为 None
    radius=None,
    n_components=2,
    metric='minkowski',
    p=2,
    path_method='auto',     # auto / Dijkstra('D') / Floyd-Warshall('FW')
    eigen_solver='auto',    # auto / arpack / dense
    n_jobs=-1,
)
Y_train = isomap.fit_transform(X_train_scaled)      # [N,2]

assert Y_train.shape == (len(X_train), 2)
assert isomap.dist_matrix_.shape == (len(X_train), len(X_train))
assert np.isfinite(isomap.dist_matrix_).all()

local_score = trustworthiness(
    X_train_scaled,
    Y_train,
    n_neighbors=12,
)
global_error = isomap.reconstruction_error()

python

dist_matrix_ 保存训练样本的测地距离矩阵，内存至少是 $O(N^2)$ ；reconstruction_error() 比较测地距离核与嵌入距离核，但不能单独证明下游任务更好。trustworthiness 检查低维近邻中有多少是高维里的虚假近邻，也应与可视化、稳定性和下游验证一起看。

09 新样本怎样进入已有坐标？#

与上一篇的 SpectralClustering 不同，scikit-learn 的 Isomap 提供 transform(X_new)：

X_valid_scaled = scaler.transform(X_valid)          # [Q,D]
Y_valid = isomap.transform(X_valid_scaled)           # [Q,2]

python

对每个查询点，算法先找训练集近邻，把它接入训练测地图，得到它到全部训练点的最短距离，再把由这些距离构造的核投影到训练嵌入特征向量。它不是重新联合优化训练点与新点。

若新点远离训练流形、落在另一个分量或需要超长接入边，输出坐标可能看似正常却不可信。上线应记录最近邻距离、接入边长度和训练分布覆盖，而不只检查 transform 是否报错。

10 邻域、尺度和维数怎样选择？#

缩放必须只在训练集拟合：距离由量纲支配时，图语义已经错了；但标准化也未必符合物理距离，应优先使用有意义的度量。
扫描邻域而非押一个 K：记录连通分量数、最长边、测地距离分位数、信任度、重构误差和下游分数。
检查短路边：查看距离特别长却被纳入近邻的边，或利用已知时间/空间拓扑检查跨段连接。
目标维数用证据决定：比较正特征值谱、重构误差和下游交叉验证；二维可视化方便，不代表真实内在维数就是 2。
划分后拟合：若嵌入用于预测，缩放器和 Isomap 都只能在训练折拟合，否则验证样本已参与图和坐标系构造。

11 复杂度、失败场景与调试路径#

Isomap 的主要成本来自近邻搜索、全源最短路和 $N\times N$ 核矩阵的特征分解。官方文档给出的最短路成本可达 $O(N^3)$ ，距离矩阵与核矩阵又需要平方级内存，因此它更适合中小规模离线表示，而不是百万样本默认方案。

常见故障可按以下顺序定位：

出现图不连通警告：先查样本覆盖、尺度与邻域数；不要只为消除警告盲目增大 K。
展开结果被撕裂：K 太小、采样有空洞或异常点切断路径；检查各点度数和最长有限测地距离。
远处区域粘在一起：K 太大或噪声造成跨折叠短路；画出最长/最可疑近邻边。
不同抽样结果差异大：测地距离依赖路径，少数关键点删除就会改写全局；做重采样稳定性与 Procrustes 对齐后比较。
负特征值很大：图距离不近似欧氏低维流形；检查拓扑、目标维数和距离度量。
下游模型变差：无监督几何目标未使用标签；在严格训练折内比较 PCA、原特征和 Isomap，而不是用漂亮散点图代替验证。

分支流形、相交曲面、强噪声、极不均匀密度、稀疏离散特征以及会随时间改变的邻接语义，都可能破坏 Isomap 的假设。

12 与相近方法的边界#

方法	主要保留对象	全局/局部	新样本与主要边界
PCA	全局线性方差与重构	全局线性	可稳定 transform；不能展开弯曲流形
Classical MDS	给定的两两距离	全局	需距离矩阵；Isomap 用测地距离喂给它
Isomap	图最短路近似的测地距离	局部建图、全局距离	sklearn 可 transform；怕短路与断图
LLE	每点由邻居重构的权重	更局部	怕病态邻域；不传播全局最短路误差
t-SNE	邻域概率	强局部、偏可视化	全局距离不可直接解释，通常不作通用特征管线

Isomap 适合“局部欧氏距离可信，并希望保留沿流形的全局距离”的问题。若只关心局部邻域配方，不想让一条错误边污染大量最短路，下一种方法会更自然。

13 今天真正需要记住什么？#

Isomap 先用近邻图阻止距离穿透弯曲流形，再用最短路估计测地距离，最后通过距离平方的双中心化与特征分解恢复低维坐标。它的关键超参数是邻域定义，不是散点图配色；可靠使用必须检查断图、短路、负特征值、平方级资源、新样本接入距离与严格无泄漏评估。

14 思考题与小练习#

在四点链中加入一条权重 1.2 的 A—D 边，重新计算 $D_{geo}$ 。哪些样本对的距离被这条短路改写？
对瑞士卷扫描 n_neighbors={4,8,16,32}，记录连通分量、最长近邻边、reconstruction_error() 与 trustworthiness。找出断图、合理和短路三个区域。
把 Isomap 放进“缩放 → 嵌入 → 回归”流程，比较在全数据先拟合嵌入与每个训练折内拟合的验证差异，解释泄漏来自哪里。

15 下一篇预告#

Isomap 用全局最短路串起局部距离，但一条错误捷径可能改写大量样本对。下一篇将研究局部线性嵌入：每个点只记住“怎样由邻居线性拼出来”，再寻找能保留这些局部重构配方的低维坐标。

01 PCA 为什么会把卷起来的纸压扁？#

02 从高维样本到低维坐标经历什么？#

03 近邻图怎样决定“能走哪里”？#

04 最短路如何近似测地距离？#

05 经典 MDS 怎样从距离恢复坐标？#

06 完整训练伪代码#

07 用 NumPy 写出手算例的核心#

08 用 scikit-learn 1.9 正确落地#

09 新样本怎样进入已有坐标？#

10 邻域、尺度和维数怎样选择？#

11 复杂度、失败场景与调试路径#

12 与相近方法的边界#

13 今天真正需要记住什么？#

14 思考题与小练习#

相关工作#

15 下一篇预告#