多维缩放算法（MDS）

算法思想

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

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

MDS算法

假设 m m $m$个样本在原始空间中的距离矩阵为D∈Rm∗m$D\in R^{m\ast m}$$D \in R^{m*m}$， distij d i s t i j $dist_{ij}$为 xi x i $x_i$和 xj x j $x_j$之间的距离，我们的目标就是获得样本在 d′ d ′ $d'$维空间中的表示 Z∈Rd′∗m,d′≤d Z ∈ R d ′ ∗ m , d ′ ≤ d $Z \in R^{d'*m}, d' \leq d$且 ||zi−zj||2=distij | | z i − z j | | 2 = d i s t i j $||z_i - z_j||^2 = dist_{ij}$,即两个空间中，样本间距离保持不变。

令 B=ZZT B = Z Z T $B = ZZ^T$为降维后的内积矩阵, 则 Bij=zizTj B i j = z i z j T $B_{ij} = z_iz_j^T$

dist2ij=||zi−zj||2=||zi||2+||zj||2−2zTizj=bii+bjj−2bij d i s t i j 2 = | | z i − z j | | 2 = | | z i | | 2 + | | z j | | 2 − 2 z i T z j = b i i + b j j − 2 b i j $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 Z $Z$做过中心化，即∑mi=1zi=0$\sum _{i=1}^m{z}_i=0$$\sum_{i=1}^m z_i = 0$，则有矩阵B的行和列的和均为0，即：

∑mi=1bij=∑mj=1bij=0 ∑ i = 1 m b i j = ∑ j = 1 m b i j = 0 $\sum_{i=1}^m b_{ij} = \sum_{j=1}^m b_{ij} = 0$

因此有：

∑mi=1dist2ij=∑mi=1||zi−zj||2=∑mi=1bii+∑mi=1bjj−2∑mi=1bij=tr(B)+mbjj−0 ∑ i = 1 m d i s t i j 2 = ∑ i = 1 m | | z i − z j | | 2 = ∑ i = 1 m b i i + ∑ i = 1 m b j j − 2 ∑ i = 1 m b i j = t r ( B ) + m b j j − 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$

∑mj=1dist2ij=tr(B)+mbii ∑ j = 1 m d i s t i j 2 = t r ( B ) + m b i i $\sum_{j=1}^{m}dist_{ij}^2 = tr(B) +mb_{ii}$

所以：

∑mi=1∑mj=1dist2ij=∑mi=1tr(B)+m∑mi=1bii=2mtr(B) ∑ i = 1 m ∑ j = 1 m d i s t i j 2 = ∑ i = 1 m t r ( B ) + m ∑ i = 1 m b i i = 2 m t r ( B ) $\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)$

令：

dist2i⋅=1m∑mj=1dist2ij d i s t i ⋅ 2 = 1 m ∑ j = 1 m d i s t i j 2 $dist_{i \cdot}^2 = \frac{1}{m} \sum_{j=1}^{m} dist_{ij}^2$

dist2⋅j=1m∑mi=1dist2ij d i s t ⋅ j 2 = 1 m ∑ i = 1 m d i s t i j 2 $dist_{\cdot j}^2 = \frac{1}{m} \sum_{i=1}^{m} dist_{ij}^2$

dist2⋅⋅=1m2∑mi=1∑mj=1dist2ij d i s t ⋅ ⋅ 2 = 1 m 2 ∑ i = 1 m ∑ j = 1 m d i s t i j 2 $dist_{\cdot \cdot}^2 = \frac{1}{m^2} \sum_{i=1}^{m}\sum_{j=1}^{m} dist_{ij}^2$

有：

bii=1m(∑mj=1dist2ij−tr(B)) b i i = 1 m ( ∑ j = 1 m d i s t i j 2 − t r ( B ) ) $b_{ii} = \frac{1}{m} (\sum_{j=1}^{m} dist_{ij}^2 - tr(B))$

bjj=1m(∑mi=1dist2ij−tr(B)) b j j = 1 m ( ∑ i = 1 m d i s t i j 2 − t r ( B ) ) $b_{jj} = \frac{1}{m} (\sum_{i=1}^{m} dist_{ij}^2 - tr(B))$

所以有：

bij=12(bii+bjj−dist2ij)=−12(dist2ij−bii−bjj)=−12(dist2ij−dist2i⋅−dist2⋅j+2mtr(B)) b i j = 1 2 ( b i i + b j j − d i s t i j 2 ) = − 1 2 ( d i s t i j 2 − b i i − b j j ) = − 1 2 ( d i s t i j 2 − d i s t i ⋅ 2 − d i s t ⋅ j 2 + 2 m t r ( 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)=12m∑mi=1∑mj=1dist2ij t r ( B ) = 1 2 m ∑ i = 1 m ∑ j = 1 m d i s t i j 2 $tr(B) = \frac{1}{2m} \sum_{i=1}^{m}\sum_{j=1}^{m}dist_{ij}^2$

所以有：

bij=−12(dist2ij−dist2i⋅−dist2⋅j+dist2⋅⋅) b i j = − 1 2 ( d i s t i j 2 − d i s t i ⋅ 2 − d i s t ⋅ j 2 + d i s t ⋅ ⋅ 2 ) $b_{ij} = -\frac{1}{2} (dist_{ij}^2 - dist_{i \cdot}^2 - dist_{ \cdot j}^2 + dist_{\cdot \cdot}^2)$

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

B=PΛPT$B=P\mathrm{\Lambda }{P}^T$$B = P \Lambda P^T$

可以得到：

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

矩阵 Z Z <script type="math/tex" id="MathJax-Element-61">Z</script>就是样本在低维空间的映射