基于Isomap算法的流形学习与非线性维数约简

资 源 简 介

本项目完整实现了2000年在Science杂志发表的经典流形学习算法Isomap（Isometric Feature Mapping）。该算法的核心思想是利用流形上的测地线距离代替传统的欧氏距离，从而揭示高维空间中非线性分布数据的内在本质结构。程序首先通过计算数据点间的欧氏距离构建近邻图，仅连接相邻的点以保持局部拓扑结构；随后利用Floyd-Warshall或Dijkstra算法计算图中所有点对之间的最短路径长度，以此作为全局测地线距离的近似估计；最后应用多维尺度变换（MDS）技术，在保持测地线距离矩阵的

详 情 说 明

基于等距映射（Isomap）算法的流形学习与非线性维数约简

项目介绍

本项目实现了经典的流形学习算法——Isomap（Isometric Feature Mapping）。该算法于2000年首次发表在《Science》杂志上，是处理非线性降维任务的里程碑式方法。与传统的线性降维算法（如PCA）不同，Isomap通过构建近邻图并计算图中样本点之间的最短路径来估算流形上的测地线距离（Geodesic Distance），随后利用多维尺度变换（MDS）将高维数据映射到低维空间，从而在低维表达中保留原始高维流形的全局几何结构。本项目以经典的“瑞士卷”（Swiss Roll）三维数据集为例，完整展示了从原始非线性数据到其二维展开流形的演化过程。

---

功能特性

1. 自动生成基准流形数据：内置了三维瑞士卷（Swiss Roll）数据集生成逻辑，能够直观展示非线性流形的结构特征。
2. 高效的距离矩阵计算：基于向量化运算实现样本点间的欧氏距离计算，提高大规模矩阵的处理效率。
3. 鲁棒的近邻图构建：支持K近邻（KNN）图的构建，并强制执行矩阵对称性以确保测地线距离计算的稳定性。
4. 全源最短路径计算：采用Floyd-Warshall算法通过图结构迭代更新所有点对之间的距离，有效近似高维流形的测地线长度。
5. 内积空间映射与MDS分解：通过双重中心化（Double Centering）处理和特征分解，实现从测地距离矩阵到低维坐标的转换。
6. 残差演化分析：计算不同降维维度下的残差值（1 - R²），用于确定数据的内在本质维度。
7. 多维度可视化：包含原始3D流形云图、2D投影结果图以及残差下降曲线图。

---

使用方法

1. 环境准备：确保安装了MATLAB R2016b或更高版本。
2. 参数配置：在主函数脚本顶部可以根据需要修改样本点数量（N）、近邻个数（K）以及目标降维维度（target_dim）。
3. 运行程序：在MATLAB命令行窗口运行主函数。
4. 查看结果：程序会自动弹出可视化窗口，展示三维原始数据、二维降维结果以及残差分析曲线，并在控制台输出当前执行进度。

---

系统要求

• 软件环境：MATLAB 2016b 及以上版本。
• 硬件建议：由于Floyd-Warshall算法的时间复杂度为O(N³)，当样本点N超过1000时，建议增加系统内存或改用更高效的最短路径算法（如Dijkstra）。

---

算法流程与实现细节

1. 数据准备与初始化

程序首先初始化仿真参数，默认生成600个样本点。利用参数方程构建瑞士卷数据集，数据在三维空间中呈现卷曲状态，颜色参数根据流形分布的展开位置进行编码，以便在后续可视化中观察邻接关系是否得到保持。

2. 局部距离计算

通过实现欧氏距离计算逻辑，利用公式 ||a-b||² = ||a||² + ||b||² - 2a'b 的矩阵形式快速生成所有样本点对之间的距离矩阵。为了消除数值计算带来的微小误差，程序对负值进行了截断处理。

3. 连接性与近邻图构建

基于计算出的距离矩阵，程序为每个样本点寻找距离最近的K个点（K=10）。在构建邻接矩阵时，非邻居节点的距离被设为无穷大，并确保了图中边的对称性。这一步旨在捕捉流形的局部线性空间特征。

4. 测地线距离估计

这是Isomap的核心步骤。程序采用Floyd-Warshall算法遍历所有中间点，逐步迭代更新点对间的最短路径。通过这种方式，原本在欧氏空间中距离较近但属于流形不同分支的点，其在图中的测地距离会变得非常大，从而揭示真实的流形路径。

5. 多维尺度变换（MDS）降维

• 距离平方化：将测地线距离转化为平方形式。
• 双重中心化：构造中心化算子矩阵H，并计算内积矩阵B = -0.5 * H * D² * H。
• 特征值分解：对B进行特征分解，并对特征值按照降序排列。
• 坐标重建：提取前d个最大的正特征值及其对应的特征向量，生成低维坐标 Y = V * sqrt(L)。

6. 残差分析与评价

为了评估降维效果，程序计算了重构后的欧氏距离与原始测地线距离之间的相关系数。残差定义为 1 - R²，反映了低维嵌入对原始流行结构保留的丢失程度。程序会测试从1维到10维的残差变化趋势。

---

关键算法逻辑分析

• 数值稳定性处理：在最短路径计算后，程序会自动检查连通性，将部分孤立点产生的无穷大值处理为0，防止MDS分解时产生复数或计算崩溃。
• 特征选择逻辑：在MDS步骤中，算法会预先筛选正特征值，确保sqrt运算的有效性。
• 可视化表达：可视化模块利用颜色映射（Colormap）同步展示了原始空间和嵌入空间中的样本。可以看到，原本卷曲的瑞士卷被平整地“摊开”在二维平面上，且颜色过渡平滑，证明了Isomap在保持全局拓扑结构方面的有效性。