Multiple Dimensional Scaling.

多维缩放(Multiple Dimensional Scaling, MDS)是一种常用的基于距离度量的降维方法，其基本思想是原始空间中样本之间的相对位置关系(距离)在低维空间得以保持。

1. MDS建模

假设在维度为$d$的原始空间中的$N$个样本表示为$X \in \Bbb{R}^{d \times N}$，目标是获得样本在$k$维空间中的降维表示$Z \in \Bbb{R}^{k \times N}$，且$k<d$。

记样本在原始空间中的距离矩阵(也叫不相似矩阵) $D \in \Bbb{R}^{N \times N}$，其$i$行$j$列元素$d_{ij}$表示样本$x_i$到$x_j$的距离。多维缩放要求任意两个样本$x_i$, $x_j$在降维后的空间中的欧式距离等于原始空间中的距离，即$||z_i-z_j||=d_{ij}$。

值得一提的是，原始空间中的样本距离可以选用任意度量方式，只要能获得距离矩阵$D$即可；而降维空间后的距离度量采用欧式距离。

注意到约束$||z_i-z_j||=d_{ij}$是没有唯一解的，对于任意两个满足条件的降维结果$z_i$, $z_j$，将其同时平移$z_0$后仍然满足上式：

因此直接求解降维结果$Z$比较困难。

2. 求解MDS

MDS并不直接求解降维结果$Z \in \Bbb{R}^{k \times N}$，而是求解降维后的样本的内积矩阵$B=Z^TZ \in \Bbb{R}^{N \times N}$。由于矩阵$B$是实对称矩阵，对其进行特征值分解：

因此求得$B$后可以通过特征值分解得到降维矩阵$Z$。

若记矩阵$B$中的元素$b_{ij}=z_i^Tz_j$，则距离约束$||z_i-z_j||=d_{ij}$可以表示为

为了便于讨论，令降维后的样本被中心化，即$\sum_{i=1}^{N}z_i=0$。 因此有$\sum_{i=1}^{N}b_{ij}=\sum_{j=1}^{N}b_{ij}=0$，并记矩阵$B$的迹$\text{tr}(B)=\sum_{i=1}^{N}b_{ii}=\sum_{i=1}^{N}||z_i||^2$，则有：

解上述方程组，则内积矩阵$B$中的元素$b_{ij}$计算为：

因此可根据距离矩阵$D$求得内积矩阵$B$。进一步对内积矩阵$B$进行特征值分解：

选择前$k$个最大的非零特征值构成对角矩阵$\tilde{\Lambda}=\text{diag}(\lambda_1,\lambda_2,…,\lambda_k)$，相应的特征向量矩阵为$\tilde{V}$，则可以求得样本的降维表示$Z$:

3. 实现MDS

① MDS from scratch

由上述介绍，MDS的一般步骤如下：

1. 给定输入样本$X \in \Bbb{R}^{d \times N}$和降维维度$k$;
2. 计算距离矩阵$D \in \Bbb{R}^{N \times N}$；
3. 计算降维后的内积矩阵$B=Z^TZ \in \Bbb{R}^{N \times N}$：$b_{ij} = \frac{1}{2}(\frac{1}{N}\sum_{j=1}^{N}d_{ij}^2+\frac{1}{N}\sum_{i=1}^{N}d_{ij}^2-\frac{1}{N^2}\sum_{i=1}^{N}\sum_{j=1}^{N}d_{ij}^2-d_{ij}^2)$;
4. 对矩阵$B$进行特征值分解：$B=V \Lambda V^T$；
5. 选择前$k$个最大特征值矩阵$\tilde{\Lambda}$对应的特征向量矩阵$\tilde{V}$;
6. 降维：$Z = \tilde{\Lambda}^{\frac{1}{2}}\tilde{V}^T \in \Bbb{R}^{k \times N}$。

def MDS(data, k):
    d, N = data.shape
    D = np.zeros([N, N])
    # 计算距离矩阵D
    for i in range(N):
        for j in range(N):
            D[i, j] = np.sqrt(np.sum((data[:,i]-data[:,j])**2))
    # 计算内积矩阵B
    T1 = np.sum(D**2, axis=0, keepdims=True)/N
    T2 = np.sum(D**2, axis=1, keepdims=True)/N
    T3 = np.sum(D**2, keepdims=True)/N**2
    B = (T1+T2-T3-D**2)/2
    # 计算特征值和特征向量
    eig_values, eig_vectors = np.linalg.eig(B)
    # 选择前k个最大的特征值标号
    index = np.argsort(-eig_values)[:k]
    # 选择对应的特征值和特征向量
    MDS_values = eig_values[index]
    MDS_vectors = eig_vectors[:, index] # (N, k)
    # 降维
    reduced_data = np.diagflat(MDS_values**0.5).dot(MDS_vectors.T) # (k, N)
    return reduced_data

② MDS from sklearn

MDS也可以通过sklearn库快速实现：

from sklearn.datasets import load_digits
from sklearn.manifold import MDS
import matplotlib.pyplot as plt

digits = load_digits()
X_mds = MDS(n_components=2, dissimilarity='euclidean').fit_transform(digits.data)

plt.figure(figsize=(10, 5))
plt.scatter(X_mds[:, 0], X_mds[:, 1], c=digits.target,label="MDS")
plt.legend()
plt.show()