MDS降维实例展示

作者: icfg66 | 来源:发表于2020-07-03 11:43 被阅读0次

MDS降维实例展示
（十一）MDS算法
Spark Mllib PCA降维
统计-降维：多维尺度变化MDS和PCoA
高维数据可视化方法——T-SNE
单细胞笔记5-tSNE和UMAP
mds维护8条命令
浅谈“降维打击”思维
降维打击，升级认知
知识碎片2（含日记）

理论推导可以参看图像降维之MDS特征抽取方法
样例来自Multidimensional scaling

前言

MDS的理论推导已经有很多了，基本上来自周志华老师的西瓜书，但其中的细节还有许多不明白，因此希望通过matlab实例来理清所有脉络。

需要解释几点

1、输入数据

输入数据是距离矩阵D，而不是原始的m个d维向量，说明有数据的信息量缺失，但它们的相对位置关系是明确的。实例中的距离矩阵如下：

距离矩阵D
也就是有4组数据，但它们的维度不知道，姑且认为较大吧，我们的任务是找4组二维的数据，让它们间的距离和上述距离相等。

2、计算Z的内积矩阵

通过两者距离相等的关系，我们希望可以求出Z的内积矩阵 $B=ZZ^T$ 的各个元素(这里和西瓜书不一样，因为这里的Z由行向量组成，每行表示一组数据)，具体的公式有点复杂：
$b_{ij}=-\frac{1}{2}(distt^2_{ij}-distt^2{i.}-distt^2{.j}+dist^2)$
但幸运的是，这都是纸老虎，在matlab具体计算的时候，其实各部分很简单，详见后面matal代码部分。

3、由内积矩阵获得Z

因为 $B_{m\times m}$ 是是对称阵，可以得到m个特征值和特征向量(这里西瓜书写的是原数据的维度d，应该是不对的)，特征向量从大到小排序：
$B=V \Lambda V^T=V \Lambda ^{1/2} (V\Lambda ^{1/2})^T=ZZ^T$
所以 $Z_{m\times m}=V\Lambda^{1/2}$ 。
为了实现降维，我们提取前d'个特征值和特征向量，即: $V_*=V_{m\times d'}$ ， $\Lambda_*=\Lambda_{d'\times d'}$ 。得到
$Z_{m\times d'}=V_*\Lambda_*^{1/2}$

matlab代码

clear;clc;
%输入的欧式距离对称矩阵
D=[0 3.1416 0.7854 1.5708;3.1416 0 2.3562 1.5708;
   0.7854 2.3562 0 2.3562;1.5708 1.5708 2.3562 0];
%距离平方对称阵
D2=D.*D; %每个元素为distt(ij)^2
%获得B矩阵
distt2i=mean(D2);    %对列求平均1*4矩阵
distt2j=mean(D2,2);  %对行求平均4*1矩阵
dist2=mean(mean(D2));      %所有距离的平均1*1矩阵
%matlab可以自动展开成4*4矩阵并做加减计算
B=-1/2*(D2-distt2i-distt2j+dist2);
%B=VAV'
[V,A]=eig(B);
%翻转特征向量，从特征值大到小排序
V=fliplr(V);A=wrev(diag(A));
%% 提取前两个最大的特征值，和特征向量，计算Z，实现降维
Z=V(:,1:2)*diag(sqrt(A(1:2)))

结果如下：