算法思想

MDS算法思想很简单，一句话就是保持样本在原空间和低维空间的距离不变。

因为距离是样本之间一个很好的分离属性，对于大多数聚类算法来说，距离是将样本分类的重要属性，因此当我们降维后，保持距离不变，那么就相当于保持了样本的相对空间关系不变。

MDS算法

假设 $m$ 个样本在原始空间中的距离矩阵为 $D \in R^{m*m}$ ， $dist_{ij}$ 为 $x_i$ 和 $x_j$ 之间的距离，我们的目标就是获得样本在 $d'$ 维空间中的表示 $Z \in R^{d'*m}, d' \leq d$ 且 $||z_i - z_j||^2 = dist_{ij}$ ,即两个空间中，样本间距离保持不变。

令 $B = ZZ^T$ 为降维后的内积矩阵, 则 $B_{ij} = z_iz_j^T$

$dist_{ij}^2 = ||z_i - z_j||^2 = ||z_i||^2 + ||z_j||^2 -2z_i^Tz_j = b_{ii} + b_{jj} -2b_{ij}$

当我们对 $Z$ 做过中心化，即 $\sum_{i=1}^m z_i = 0$ ，则有矩阵B的行和列的和均为0，即：

$\sum_{i=1}^m b_{ij} = \sum_{j=1}^m b_{ij} = 0$

因此有：

$\sum_{i=1}^{m}dist_{ij}^2 = \sum_{i=1}^{m}||z_i - z_j||^2 = \sum_{i=1}^{m}b_{ii} + \sum_{i=1}^{m}b_{jj} -2\sum_{i=1}^{m}b_{ij} = tr(B) +mb_{jj} - 0$ $\sum_{j=1}^{m}dist_{ij}^2 = tr(B) +mb_{ii}$

所以：

$\sum_{i=1}^{m}\sum_{j=1}^{m}dist_{ij}^2 = \sum_{i=1}^{m}tr(B) +m\sum_{i=1}^{m}b_{ii} = 2mtr(B)$

令：

$dist_{i \cdot}^2 = \frac{1}{m} \sum_{j=1}^{m} dist_{ij}^2$ $dist_{\cdot j}^2 = \frac{1}{m} \sum_{i=1}^{m} dist_{ij}^2$ $dist_{\cdot \cdot}^2 = \frac{1}{m^2} \sum_{i=1}^{m}\sum_{j=1}^{m} dist_{ij}^2$

有：

$b_{ii} = \frac{1}{m} (\sum_{j=1}^{m} dist_{ij}^2 - tr(B))$ $b_{jj} = \frac{1}{m} (\sum_{i=1}^{m} dist_{ij}^2 - tr(B))$

所以有：

$b_{ij} = \frac{1}{2}(b_{ii} + b_{jj} - dist_{ij}^2) = -\frac{1}{2} (dist_{ij}^2 - b_{ii} - b_{jj}) = -\frac{1}{2} (dist_{ij}^2 - dist_{i \cdot}^2 - dist_{ \cdot j}^2 + \frac{2}{m} tr(B))$

而：

$tr(B) = \frac{1}{2m} \sum_{i=1}^{m}\sum_{j=1}^{m}dist_{ij}^2$

所以有：

$b_{ij} = -\frac{1}{2} (dist_{ij}^2 - dist_{i \cdot}^2 - dist_{ \cdot j}^2 + dist_{\cdot \cdot}^2)$

因此我们可以通过矩阵 $D$ 求得矩阵 $B$ ，而 $B = ZZ^T$ ，对 $B$ 做特征分解，有：

$B = P \Lambda P^T$

可以得到：

$Z = \Lambda^{\frac{1}{2}} P^T$

矩阵 $Z$ 就是样本在低维空间的映射