多维缩放MDS降维

多维缩放（MDS）

MDS的目标是在降维的过程中，将数据的dissimilarity(差异性)保持下来， 也可以理解降维让高维空间中的距离关系与低维空间中距离关系保持不变。

距离用矩阵表示， N个样本的两两距离用矩阵A的每一项a_ij表示， 并且假设在低维空间中的距离是欧氏距离。 而降维后的数据表示为z_i，那么就要 a_ij = [图片上传失败...(image-585141-1618586924273)]

右边的三项统一用内积矩阵E来表示[图片上传失败...(image-d62e84-1618586924273)]

去中心化之后，E的每一行每一列之和都是0，从而可以推导得出：

[图片上传失败...(image-26b00d-1618586924273)]

其中[图片上传失败...(image-900843-1618586924273)]

i·和j·是指某列或者某列总和，从而建立了距离矩阵A与内积矩阵E之间的关系。

MDS流程

1. 输入：距离矩阵，上标表示矩阵大小，原始数据是D维，降维到d维；

2. 输出：降维后矩阵

3. 目标：降维的同时保证数据之间的相对关系不变

4. 假设：已知N个样本的距离矩阵。

5. 算出a_i、a_j、a...

6. 计算内积矩阵E

7. 对E做特征值分解

8. 取d个最大特征值构成，对应的特征向量按序排列构成。