等距映射（Isomap）算法详解与代码实现
等距映射（Isomap）算法详解与代码实现
介绍
等距映射（Isomap，Isometric Mapping）是一种非线性降维算法，属于流形学习方法，用于在保留高维数据几何结构的前提下，将数据降到低维空间。Isomap 是对经典多维缩放（MDS，Multidimensional Scaling）的扩展，通过保留点对点之间的流形距离来实现降维。
高维空间中的数据通常位于低维流形上（如曲面或曲线）。在高维空间中，欧几里得距离可能无法准确反映数据的真实结构，而沿流形的距离（即流形距离）能够更好地描述数据点之间的关系。Isomap 的目标是：
（1）计算高维数据点之间的流形距离；
（2）使用这些流形距离在低维空间中重构数据点的位置。
流形距离
流形距离（Manifold Distance）是数据点沿其所在流形表面之间的最短路径距离。它区别于欧几里得距离，后者是在原始高维空间中测量的直线距离，而流形距离反映了数据在低维流形结构上的真实几何关系。
例如二维曲面上，欧几里得距离只能表示直线距离，而不能表示真实几何关系（曲面）。
以下是数学定义（来源GPT）：
等距映射（Isomap）
建图
流形在局部上与欧几里得空间同胚（定义，局部欧几里得性），所以我们可以对每个点基于欧氏距离找出近邻点，然后建立邻接图，边权为两点间的欧几里得距离。
通常会有两个超参数，一个是最多挑选的近邻点数量k，一个是近邻点的距离阈值ϵ。
寻找最短路和最短流形距离
在图上跑最短路算法（Floyd，Dijkstra），即可找到两个点之间的最短路程，这个路程被称为最短流形距离。
多维缩放（MDS）
在最短流形距离的基础上进行经典MDS。
多维缩放是一种经典的降维方法，旨在从高维数据中提取低维嵌入，同时尽可能保留数据点之间的距离关系。MDS 的核心目标是将高维点的距离关系映射到低维空间中，使得低维空间中的点对之间的距离与原始距离尽可能相似。
输入距离矩阵
D =
\begin{bmatrix}
d_{12} & \cdots & d_{1n}\
\vdots & \ddots & \vdots\
d_{n1} & \cdots & d_{nn}
\end{bmatrix}
指定低维空间维度为m
输出一个n × m的矩阵
Y =
\begin{bmatrix}
y_{1} \
\vdots \
y_{n}
\end{bmatrix}，其中
y_{i} \in \mathbb{R}^{m}，表示一个低维嵌入。
损失函数
S(Y)=\sqrt{\frac{\sum_{i<j}(d_{ij}-d_{ij}^{Y})^2}{\sum_{i<j}d_{ij}^2}}
第一种求解过程（梯度下降）：
初始化低维嵌入
Y^{0}，可以是随机初始化，也可以是启发式（如取PCA的前m个主成分）。
求偏导：
\frac{\partial S(Y)}{\partial \mathbf{y}i} = \frac{1}{S(Y) \cdot \sum{i < j} d_{ij}^2} \sum_{j \neq i} \left(d_{ij} - d_{ij}^Y\right)\frac{\mathbf{y}_i - \mathbf{y}j}{d{ij}^Y}
梯度下降更新：
\mathbf{y}_i^{(t+1)} = \mathbf{y}_i^{(t)} - \eta \frac{\partial S(Y)}{\partial \mathbf{y}_i}，其中
\eta为学习率，
t为迭代次数。
第二种求解过程（特征值分解）：
计算中心化的内积矩阵
B：b_{ij} = -\frac{1}{2} \left( d_{ij}^2 - d_{i\cdot}^2 - d_{\cdot j}^2 + d_{\cdot\cdot}^2 \right)
对
B进行特征值分解：
B=VΛV^{T}，其中
Λ=diag(λ_1,λ_2,…,λ_n)是特征值矩阵，
V=[v_{1},v_{2},...v_{n}]为特征向量矩阵。
构造低维表示：选择前m个最大的正特征值
λ_1,…,\lambda_m，计算低维嵌入
Y=V_{m}Λ_{m}^{1/2}
代码实现
scikit-learn提供现成的模块：
from sklearn.manifold import Isomap
from sklearn.datasets import make_swiss_roll
import matplotlib.pyplot as plt
# 生成三维的瑞士卷数据集
X, color = make_swiss_roll(n_samples=1000, noise=0.05)
# 可视化原始高维数据
fig = plt.figure(figsize=(8, 6))
ax = fig.add_subplot(111, projection='3d')
ax.scatter(X[:, 0], X[:, 1], X[:, 2], c=color, cmap=plt.cm.Spectral)
plt.title("Original 3D Swiss Roll")
plt.show()
# 设置 参数
n_neighbors = 10 # 每个点的邻居数量
n_components = 2 # 降维后的目标维度
# 创建 Isomap 模型
isomap = Isomap(n_neighbors=n_neighbors, n_components=n_components)
# 降维
X_isomap = isomap.fit_transform(X)
# 可视化降维后的结果
plt.figure(figsize=(8, 6))
plt.scatter(X_isomap[:, 0], X_isomap[:, 1], c=color, cmap=plt.cm.Spectral)
plt.title("2D Embedding using Isomap")
plt.xlabel("Component 1")
plt.ylabel("Component 2")
plt.show()