11.2 MDS算法

不管是使用核函数升维还是对数据降维，我们都希望原始空间样本点之间的距离在新空间中基本保持不变，这样才不会使得原始空间样本之间的关系及总体分布发生较大的改变。“多维缩放”（MDS）正是基于这样的思想，MDS要求原始空间样本之间的距离在降维后的低维空间中得以保持。

假定m个样本在原始空间中任意两两样本之间的距离矩阵为D∈R(mm)，我们的目标便是获得样本在低维空间中的表示Z∈R(d’m , d’< d)，且任意两个样本在低维空间中的欧式距离等于原始空间中的距离，即||zi-zj||=Dist(ij)。因此接下来我们要做的就是根据已有的距离矩阵D来求解出降维后的坐标矩阵Z。

3.png

令降维后的样本坐标矩阵Z被中心化，中心化是指将每个样本向量减去整个样本集的均值向量，故所有样本向量求和得到一个零向量。这样易知：矩阵B的每一列以及每一列求和均为0，因为提取公因子后都有一项为所有样本向量的和向量。

4.png

根据上面矩阵B的特征，我们很容易得到等式（2）、（3）以及（4）：

5.png

这时根据(1)—(4)式我们便可以计算出bij，即bij=(1)-(2)(1/m)-(3)(1/m)+(4)*(1/(m^2))，再逐一地计算每个b(ij)，就得到了降维后低维空间中的内积矩阵B(B=Z’*Z)，只需对B进行特征值分解便可以得到Z。MDS的算法流程如下图所示：

6.png