5.6　多维度尺度分析与等距映射

等距映射（isometric mapping，ISOMAP）是多维尺度分析（multidimensional scaling，MDS）利用测地距离在流形数据上的扩展，因此把它们放在一起介绍。5.4节的LLE算法侧重从局部出发，进而保证降维后的数据仍然保留原始数据的局部邻接关系。而MDS与ISOMAP则是从全局角度出发对数据降维。MDS的基本出发点是保证降维后的数据仍然保留原始数据的任意两点间的距离关系，即原始空间中距离很近的点在低维映射后仍然离得很近，距离很远的点降维后仍然离得很远。

因此对于MDS来说，输入类表示为输入点xk与xl的距离。输出类表示为输出点yk与yl的距离。显而易见是很难保证的，但类一致性准则要求一个好的应该满足如下目标函数：

也就是说类输入表示和类输出表示应该尽可能一致，由此可得MDS的目标函数：

其中距离度量可以采用传统的欧氏距离，即。下面给出MDS的求解过程。

给定矩阵T∈ℝN×N，且

其中为均值向量。同时易得

把式（5.44）～式（5.47）代入式（5.43），得

由式（5.48）可得两向量的内积可以只用两者之间的距离表示。若输入矩阵X已经去均值化，则式（5.48）可以写成矩阵的形式

其中，1为全1向量，DX为由原始输入数据得出的距离矩阵，这里注意，此时DX中的元素。可以证明，当采用欧氏距离时，T

为半正定矩阵。同时目标函数（5.42）可以写成如下形式

求解问题（5.50）只需对T进行特征分解T=UΛUT，若把数据降到d维，只需提取T的前d个特征向量，记为U'，并使即可。

根据MDS的原理，ISOMAP为MDS在流型数据上的一个扩展，其与MDS最主要的不同是ISOMAP使用测地距离代替欧氏距离来构造距离矩阵。这是由于对于非线性的流形结构，如我们在球体上测量两点的距离，两点的欧氏距离往往并不合适，我们更关注两点沿着球体表面的实际距离。因此ISOMAP利用测地距离更擅长捕捉此类结构。