特征抽取 等距离映射Isomaptype
status
date
slug
summary
tags
category
icon
password
Property
它所采用的核心算法和MDS是一致的，区别在于原始空间中的距离矩阵的计算上。很多数据是非线性结构，不适合直接采用PCA算法和MDS算法。在非线性数据结构中，流形上距离很远（测地线距离）的两个数据点，在高维空间中的距离（欧式距离）可能非常近，如下图所示：
蓝色虚线为两个点的欧式距离，蓝色实线为两个点的测地线距离。但是测地线距离也不好测量，因此采用另一种路径近似代表测地线距离。
构建一个连通图，其中每个点只和距离这个点最近的 个点直接连接，和其他的点不直接连接。这样可以构建邻接矩阵，进而求出图中任意两个点的最短路径，代替测地线距离。蓝色点代表两个点之间的测地线距离，红色线代表图中两点的最短路径，两者距离相近，因此我们使用后者替代前者。进而引出isomap算法。
Isomap算法总共分为三步：
- 为每个数据点确定邻居，有两种方式，一种是把最近的个作为邻居，一种是把半 内的所有点作为邻居。可以得到加权图，边上的权重表示两点之间的输入空间距离
- 对任意两个点对，计算最短路径距离为测地线距离的估计，可以采用Dijkstra算法计算最短路径
- 把根据最短路径确定的距离矩阵作为MDS算法的输入，得到低维空间中最好地保留流形的本质结构的数据表示。
在计算近邻时，如果邻域范围指定得较大，那么距离较远的点可能被认为是近邻，造成“短路”问题；如果邻域范围指定的小，那么图中某些区域可能和其他区域不连通，出现“断路”问题。短路或者断路都会给后面计算最短路径造成误导。
降维过程中保留距离信息不变，这是不是意味着任意两点在低维空间中的测地线距离应该和高维空间中的测地线距离相同？但是如果用MDS，那么高维空间中的距离度量用的是测地线距离，而低维空间用的是欧氏距离，和目标不一致了怎么办？
答：低维空间中使用欧氏距离，是因为此时欧氏距离是测地线距离的一个近似。就像高维空间中用最短路径距离近似测地线距离一样。
代码
