高维数据流形学习分析：ISOMAP等度规映射方法

2.4.1.1　基本思想

Tenenbaum等人提出的等度规映射ISOMAP算法，是建立在多维尺度分析(Multi-Dimensional Scaling，MDS)基础上的一种非线性维数约简方法。ISOMAP利用所有样本点之间的测地距离矩阵来代替MDS中的欧氏距离矩阵，以保持嵌入在高维观测空间中内在低维流形的全局几何特性。ISOMAP算法的关键是计算每个样本点与所有其他样本点之间的测地距离。对于近邻点，利用输入空间的欧氏距离直接得到其测地距离；对于非近邻点，利用近邻图上两点之间的最短路径近似表示其测地距离。然后对于构造的全局测地距离矩阵，利用MDS在高维输入空间与低维嵌入空间之间建立等距映射，从而发现嵌入在高维空间的内在低维表示。

2.4.1.2　算法步骤

(1)构造近邻图

定义一个包含所有样本点的图G，如果样本点Xi和Xj的欧氏距离d(Xi，Xj)小于一个域值ε或者是点Xj是点Xi的k近邻点，那么Xi和Xj之间有边连接，且边长为d(Xi，Xj)。

(2)计算最短路径(www.xing528.com)

如果两个点Xi和Xj有边连接，设置其最短路径距离为dG(Xi，Xj)＝d(Xi，Xj)，否则dG(Xi，Xj)＝∞，然后将l分别设置为1，2，…，n，其中n为样本点数，计算任意两个点之间的最短路径距离:

那么最短路径距离矩阵DG＝{dG(Xi，Xj)}将包含了图G中任意两个点之间的最短路径距离，并将其作为任意两点之间的测地距离。

(3)计算d维嵌入

2.4.1.3　算法分析

ISOMAP算法是一种保持全局几何特性的方法，它的低维嵌入结果能够反映出高维观测样本所在流形上的测地距离。如果高维观测样本所在的低维流形与欧氏空间的一个子集是整体等距的，且与样本所在流形等距的欧氏空间的子集是一个凸集，那么ISOMAP算法能够取得比较理想的嵌入结果。但是当流形曲率较大或者流形上有“孔洞”，即与流形等距的欧氏空间的子集非凸时，流形上的测地距离估计将会产生较大的误差，导致嵌入结果产生变形。从算法的时间复杂度来看，ISOMAP算法有两个地方需要大量计算。第一个是计算最短路径距离矩阵DG。当使用Floyd算法时，计算复杂度为O(n3)；若采用Dijkstra算法，可将计算复杂度降低到O(kn2log n)。第二个是应用MDS方法进行特征分解。由于距离矩阵是稠密的，所以特征分解的计算复杂度为O(n3)。当面对大样本数据时，ISOMAP算法计算代价非常巨大，导致计算效率低下。