草稿
Isomap
保留邻居图上的行走距离，让弯曲流形能展开成低维地图。
algorithm intermediate machine-learningdimensionality-reductionmanifold-learning
钩子问题：直线可能穿过折叠
想象点落在一张卷曲的纸面上。两个点可能隔空很近，但如果必须沿纸面走，其实很远。
原始 MDS 使用直线距离，所以可能把错误的近邻压在一起。Isomap 用邻居图上的行走距离来修补这个问题。
在弯曲表面上过于冒进
近似测地距离
对图最短路做 MDS，而不是对原始直线距离做 MDS。
第一个朴素想法：直接对欧氏距离做 MDS
如果结构本来就是平的，这样可行。结构弯曲时就会痛苦，因为欧氏距离会穿过空白空间抄近路。
核心发明：先局部图，再布局
Isomap 有三步：
- 把每个点连接到附近邻居；
- 计算图最短路距离，记作
$D_{geo}(i,j)$； - 对测地距离表做 MDS。
邻居图背后的赌注是：局部距离可信，长距离应该由一段段局部行走拼出来。
追踪实验室
欧氏距离可能穿过弯曲流形抄近路，因此 Isomap 先构造邻居图。
只保留局部边
实现草图
build a k-nearest-neighbor graph;
weight each edge by local distance;
run all-pairs shortest paths on the graph;
apply MDS to the graph-distance matrix;常见混淆
- Isomap 对邻居参数很敏感。
- 邻居图不连通时，最短路距离表会坏掉。
- 它保留的是流形距离，不是任意类别分离。
保留中心化数据变化最大的方向。
摆放点，让低维距离尽量模仿原始距离表。
先用邻居图最短路估计流形距离，再做类似 MDS 的布局。
利用标签寻找投影方向，让类均值分开，同时让类内保持紧。
让每个类别保留自己的协方差，形成二次边界，而不是一个共享投影。
匹配高维与低维中的邻居概率。
用低维重尾相似度修补 SNE 的拥挤问题。
构造模糊邻居图，再优化具有相似成员强度的低维图。
练习
- Isomap 为什么不信任长直线距离？
- 如果邻居图不连通，会发生什么？
- Isomap 的哪一步继承自 MDS？
图谱连接 : Isomap