在之前已經介紹過資料降維的基礎概念 以及使用進行PCA示範，因此這篇要來談的是另一種降維方式 MDS，並敘述相關理論推導。

Introduction

MDS全名為Multidimensional Scaling，和之前使用過的PCA一樣是非常經典的演算法， 現在也衍生如出許多進階版本，在本篇我們將主要介紹放在古典MDS演算法內容。

MDS主要概念為透過保持資料間歐式距離（Euclidean distance）關係， 也就是希望轉換後的低維資料中每筆資料間的距離，盡可能和高維資料的資料間距離保持差異最小化。 假設現在有一存在\(n\)筆資料的資料集\(A=\{a_1,a_2,\ldots,a_n\}\)，經過MDS轉換後成為新資料集 \(B=\{b_1,b_2,\dots,b_n\}\)，則

\[d(a_i,a_j) \approx d(b_i,b_j)\]

兩點間的歐式距離\(d(x, y)\)為

\[d(x, y) = \sqrt{(x-y)(x-y)^T}\]

Matrix Form

假如現在有一資料集\(X\)並將其表示為\(m \times n\)矩陣，其中\(m\)為資料數量，\(n\)為資料維度，則矩陣表示式如下：

\[X=\begin{bmatrix}X_1 \\ \vdots \\ X_m\end{bmatrix}=\begin{bmatrix}x_{11} & \cdots & x_{1n} \\ \vdots & & \vdots \\ x_{m1} & \cdots & x_{mn}\end{bmatrix}\]

而降維後的資料矩陣 \(Z\) 為 \(m \times k\) 與 \(k \leq n\)，則

\[Z=\begin{bmatrix} Z_1 \\ \vdots \\ X_m \end{bmatrix} = \begin{bmatrix} z_{11} & \cdots & z_{1k} \\ \vdots & & \vdots \\ z_{m1} & \cdots & z_{mk} \end{bmatrix}\]

定義\(X\)與\(Z\)的\(m \times m\)歐式距離矩陣為\(D\)與\(P\)，其中

\[D_{ij}=d(X_i, X_j)\]

\[P_{rs}=d(Z_r, Z_s)\]

假定\(Z\)中所有資料相加為零，即\(\sum\limits_{r}{}Z_r=0\)，經推導後\(Z\)的內積矩陣\(B\)可轉換為

\[B=-\frac{1}{2}HDH=ZZ^T\]

其中

\[H=I-\frac{1}{m}11^{'}\]

對\(B\)進行特徵根分解可得

\[B=V\Lambda V^T=(V\Lambda^{\frac{1}{2}})(V\Lambda^{\frac{1}{2}})^T=ZZ^T\]

由上式可知

\[Z=V\Lambda^{\frac{1}{2}}\]

其中\(\Lambda\)為\(B\)的特徵根對角矩陣，\(\Lambda_{ii}=\lambda_i\)。\(V\)為特徵向量矩陣 ，\(V=[v_1, v_2,\dots,v_m]\)。且 \(\lambda_1 \geq \lambda_2 \dots \lambda_m \geq 0\)

Algorithm

由以上的推導可知，降維資料\(Z\)可由以下步驟加以求得

  • 計算原始資料距離矩陣\(D=[d_ij]\)

  • 轉換爲Centering Matrix \(B=-\frac{1}{2}HDH\)，其中\(H=I-\frac{1}{m}11^{'}\)

  • 求出\(B\)的最大\(k\)個特徵根\(\lambda_{1}, \lambda _{2},...,\lambda _{k}\)，與其對應的特徵向量\(e_{1},e_{2},..., e_{k}\)

  • 因此\(Z\)可由\(Z=E_{k}\Lambda_{k}^{\frac{1}{2}}\)求得， 其中\(\Lambda_{k}^{\frac{1}{2}}\)為\(k \times k\)的特徵根對角矩陣，而 \(E_{k}\)為對應的\(m \times k\)特徵向量矩陣。

Code

以下為將Iris flower dataset與scikit-learn套件，進行MDS降維與結果展示

# 匯入相關 Package
import matplotlib.pyplot as plt
from sklearn import datasets
from sklearn.manifold import MDS

# 取得 Iris data set
iris = datasets.load_iris()
iris_label = iris.target

# 設定 MDS Model參數並對 dataset進行降維
mds_coeff = MDS(n_components=2)
mds_result = mds_coeff.fit_transform(iris.data)

# 繪製資料2D表示圖，並將不同類別加上顏色標示
for idx, label in enumerate(iris_label):
    if label == 0:
        color = 'ro'
    elif label == 1:
        color = 'go'
    elif label == 2:
        color = 'bo'
    else:
        continue
    x = mds_result[idx, 0]
    y = mds_result[idx, 1]
    plt.plot(x, y, color)

下圖為執行結果，可看data set中的各類別，在降低到2維仍有明確的群聚關係。

Iris-MDS-2d