数据降维方法介绍：

第一种方法：多维尺度分析算法（三）

姓名：何源学号：21011210073 学院：通信工程学院

【嵌牛导读】多维尺度分析算法

【嵌牛提问】如何实现多维尺度分析算法

【嵌牛正文】

当我们已知美国十个城市'Atl','Chi','Den','Hou','LA','Mia','NYC','SF','Sea','WDC'之间的距离时，如下图所示

图1-美国十个城市之间的距离（单位：公里）

根据距离信息构建距离矩阵： $D=[d_{ij} ]_{N\times N}$

假设所有城市的相对坐标为 $Z=[z_{1}^T, z_{2}^T...z_{N}^T ]_{N\times 2}^T$ 且令 $\sum_{i=1}^N z_{i} =0$ ，即相对坐标系的中心为坐标原点。

令 $B=ZZ^T=[b_{ij}]_{N\times N}=[z_iz_{j}^T ]_{N\times N}$ ,称 $B$ 为内积矩阵，则 $B$ 满足

$\sum_{i=1}^N b_{i j}=\sum_{ =1}^N z_i z_{j}^T=(\sum_{i=1}^N z_i) z_{j}^T=0,\sum_{i=1}^N b_{i j}=\sum_{ =1}^N z_i z_{j}^T=z_i(\sum_{i=1}^N z_{j}^T)=0,$

已知 $d_{ij}=||z_j-z_i||$ ,两边平方得到

$d_{ij}^2=||z_j-z_i||^2=||z_j||^2+||z_i||^2-2z_iz_{j}^T （1）$

又 $b_{ij}=z_iz_{j}^T$ ,则式（1）可以表示为

$d_{ij}^2=b_{jj}+b_{ii}-2b_{ij} （2）$

对式（2）左边对 $i$ 求和得

$\sum_{i=1}^N d_{ij}^2=\sum_{i=1}^N b_{jj}+\sum_{i=1}^N b_{ii}-2\sum_{i=1}^N b_{ij}=Nb_{jj}+tr(B) （3）$

对式（2）左边 $j$ 求和得

$\sum_{j=1}^N d_{ij}^2=\sum_{j=1}^N b_{jj}+\sum_{j=1}^N b_{ii}-2\sum_{j=1}^N b_{ij}=Nb_{ii}+tr(B) （4）$

对式（2）左边 $i$ 和 $j$ 求和得

$\sum_{i=1}^N \sum_{j=1}^Nd_{ij}^2=\sum_{i=1}^N \sum_{j=1}^Nb_{jj}+\sum_{i=1}^N \sum_{j=1}^N b_{ii}-2\sum_{i=1}^N \sum_{j=1}^N b_{ij}=2Ntr(B) （5）$

其中 $tr(B)=\sum_{i=1}^N b_{ii} =\sum_{j=1}^N b_{jj}$ 表示矩阵的迹

由式（5）可得

$tr(B)=\frac{1}{2N} \sum_{i=1}^N\sum_{j=1}^Nd_{ij}^2 （6）$

将式（6）代入式（3）和式（4）计算 $b_{ii}和b_{jj}得$

$b_{ii}=\frac{1}{N}\sum_{j=1}^N d_{ij}^2-\frac{1}{2N^2}\sum_{i=1}^N \sum_{j=1}^N d_{ij}^2,b_{jj}=\frac{1}{N}\sum_{i=1}^N d_{ij}^2-\frac{1}{2N^2}\sum_{i=1}^N \sum_{j=1}^N d_{ij}^2 （7）$