MDS

Multiple Dimensional Scaling(MDS)

MDS被称为多维缩放算法，是一种经典的特征降维算法。

相关背景

MDS一般被用在已知空间中点与点之间的距离，而点的精确坐标与维度是未知的。即给定一个实对称的距离矩阵$D \in \mathbb R^{N \times N}$($d_{ij} = d_{ji}$)，将其投影到更低维空间中。

• 低维空间中的点经过平移(translation)，旋转(rotation)和对称(reflection)后，点与点之间的距离是不不变的。

MDS计算过程

1. 得到一个距离矩阵$\mathbf D$，通过$\mathbf B = -\frac {1}{2} JDJ$计算内积矩阵$B$，其中:

$\mathbf J = \mathbf I_N - \frac {1}{N} \mathbf e \mathbf e^T$, $e = (1,1,...,1)^T$

1. 将$\mathbf B$做特征值分解，得：

   $B = V\Lambda V^T$

2. 将特征值从小到大排序，可知后面的特征值基本为零，因此取前$D^{‘}$个特征值以及其对应的特征向量$\tilde{\Lambda}$。

3. 得到低维空间中的表示：

   $Z = \tilde {\Lambda}^{\frac {1}{2}} \tilde {V}^T \in \mathbb R^{D^{'} \times N}$

其中，$Z^TZ = R \in \mathbb R^{N \times N}$

推导过程

定义

已知距离矩阵$D$，先将其投影到低维空间，得$Z \in \mathbb R^{D^{‘} \times N}$。Z是在低维空间中样本点的表示($z_i, z_j$,…$为$Z$的列向量，可以将其近似理解为每个点在空间的矢量)。在此低维空间中，点与点之间的欧式距离可以表示为：

$dist_{ij} = \parallel{z_i - z_j}\parallel$

上式为MDS最重要的前提。

MDS形式化

首先，需要对样本进行中心化（必须进行的一步），之后的推导中利用前提$\sum_{i=1} ^N z_i = 0$来进行。

将$z_{ij}$与$d_{ij}$互相表示，方便之后推导直接代入。

内积矩阵

• 定义内积矩阵$B = ZZ^T$，其中$B \in \mathbb R^{N \times N}$，即$b_{ij} = z_i^Tz_j$。

• 利用距离矩阵$D$表示内积矩阵$B$。

$b_{ij}$完全可以用$d_{ij}$来表示，因此，用矩阵表示为：

$B = -\frac {1}{2} JDJ$

接着，将$B$进行特征值分解：

由于$\Lambda$为对角矩阵，因此$\Lambda ^{\frac {1}{2}}$即为对角上特征值取根号的矩阵。