2.2 經典與非度量多維尺度分析

有些資料描述的是物件之間的關係，而非各個物件的特徵。我們可能知道每對 物件相距多遠，卻沒有合適的座標表示。多維尺度分析（MDS）把這些成對關係 轉成低維歐氏空間中的位置。經典 MDS 從距離平方重建內積；非度量 MDS 則透過單調轉換擬合相異度的次序。兩者所說的「好地圖」，對應不同的目標。

動機

PCA 從特徵資料表出發，在特徵空間中選方向。MDS 的輸入則是比較物件對的 方形表格；其中一行列出某物件與其他物件的關係，並非一組測得的特徵。 直接對這些行做 PCA，求解的問題便與重現指定距離不同。

設 $D=(d_{ij})\in\mathbb R^{n\times n}$，$n\ge2$。我們要找座標矩陣 $X\in\mathbb R^{n\times k}$，每一行存放一個點 $x_i\in\mathbb R^k$， 使行與行之間的歐氏距離表達 $D$ 的成對資訊。畫圖通常只用一維或二維， 代數分析則能指出精確重建究竟需要多少維。

距離表不能決定絕對原點。對每一行加上同一個 $c\in\mathbb R^k$，兩點之差 完全不變。因此可選擇每列平均為零的居中表示。這固定了原點，但未固定 座標軸的方向。

定義

定義

相異度表、度量與歐氏距離表

本節的相異度表要求對稱、非負且對角為零，即 $d_{ij}=d_{ji}\ge0$、 $d_{ii}=0$。度量還要求不同物件的距離為正，並對每個三元組滿足 $d_{ij}\le d_{i\ell}+d_{\ell j}$。若存在一組點使

$$d_{ij}=\|x_i-x_j\|_2.$$

則稱 $D$ 為歐氏距離表。這一定義容許點重合，重合標籤之間的距離為零。 單憑三角不等式，還不足以判定距離表能否嵌入歐氏空間。

經典 MDS 先把每個元素各自平方，再引入居中矩陣：

$$E=D^{(2)},\qquad E_{ij}=d_{ij}^2, \qquad H=I_n-\frac1n\mathbf1\mathbf1^T.$$

所以 $E$ 並非矩陣乘積 $DD$。矩陣 $H$ 對稱，滿足 $H^2=H$、 $H\mathbf1=0$；$HX$ 會從每一行減去座標平均。再定義 $E$ 的行平均與總平均：

$$r_i=\frac1n\sum_j E_{ij},\qquad g=\frac1{n^2}\sum_{i,j}E_{ij}.$$

這些都是距離平方的平均。由於 $E$ 對稱，列平均等於行平均。雙重居中會 同時減去兩組平均，再把總平均加回一次。

定理與命題

定理

居中 Gram 矩陣與精確歐氏重建

對稱、非負、對角為零的 $D$，令

$$B=-\frac12HEH,\qquad b_{ij}=-\frac12(E_{ij}-r_i-r_j+g).$$

$D$ 是歐氏距離表，當且僅當 $B$ 半正定。此時正特徵值部分的分解給出居中座標

$$B=V_+\Lambda_+V_+^T,\qquad X=V_+\Lambda_+^{1/2},\qquad XX^T=B.$$

最小精確嵌入維數是 $\operatorname{rank}(B)$，至多為 $n-1$；秩為零表示全部點重合。

命題

正譜截斷與經典 strain

把 $B$ 的特徵值由大至小排列。在所有居中、半正定且秩至多為 $k$ 的 Gram 矩陣 $G$ 中，保留最大的至多 $k$ 個正特徵值，可使 $\|B-G\|_F^2$ 最小。 若 $I_k$ 是保留部分的指標，則

$$G_k=\sum_{j\in I_k}\lambda_jv_jv_j^T, \qquad X_k=V_{I_k}\Lambda_{I_k}^{1/2}, \qquad \|B-G_k\|_F^2=\sum_{j\notin I_k}\lambda_j^2.$$

負特徵值在正 Gram 近似中造成無法消除的誤差。重複特徵值可產生多個同樣 最優的座標方向，或不同的保留子空間。

第二個結果的誤差常稱為經典 strain。它比較內積，與直接比較成對距離的 平方誤差不同。低維經典圖優化的是 Gram 準則；解讀圖形時，仍要查看所得 距離，以及哪些譜方向已被捨去。

雙重居中的推導

假設居中座標存在。其 Gram 矩陣為 $B=XX^T$，元素為 $b_{ij}=\langle x_i,x_j\rangle$。展開兩點距離得到

$$E_{ij}=b_{ii}+b_{jj}-2b_{ij}.$$

令 $a=(b_{11},\ldots,b_{nn})^T$，矩陣形式便是 $E=a\mathbf1^T+\mathbf1a^T-2B$。左右乘 $H$，由 $H\mathbf1=0$ 消去前兩項。 居中又給出 $HX=X$，故 $HBH=B$，最終得到 $HEH=-2B$。於是只用距離表 便能重建 Gram 矩陣；元素平均公式就是展開此矩陣乘積的結果。

證明

半正定為何亦足夠

若座標存在，對每個 $z$ 都有 $z^TBz=\|X^Tz\|_2^2\ge0$，所以 $B$ 半正定。 反過來，若構造出的 $B$ 半正定，可用譜分解寫成 $XX^T$。由 $B\mathbf1=0$， 正特徵值的特徵向量均與 $\mathbf1$ 正交，因此各座標列平均為零。

$E$ 的對角為零，元素公式便給出 $b_{ii}=r_i-g/2$。所以

$$b_{ii}+b_{jj}-2b_{ij} =(r_i-g/2)+(r_j-g/2)+(E_{ij}-r_i-r_j+g) =E_{ij}.$$

重建點的距離平方恰等於 $E$，而 $D$ 非負，故距離亦恰好等於 $D$。 $k$ 維座標的 Gram 秩至多為 $k$；上述分解則每個正特徵值只用一列，從而證明 最小維數的結論。

譜截斷的理由是 Frobenius 範數在正交變換下不變，故可在 $B$ 的特徵基中 比較。譜低秩近似原理把有限的非負特徵值分配給最大的正方向；每個獲選方向 的最佳數值就是 $\lambda_j$。其他方向留下特徵值平方作誤差。正方向又與 $\mathbf1$ 正交，因此保留後的座標仍然居中。

若 $Q$ 是正交的 $k\times k$ 矩陣，$XQ$ 與 $X$ 有相同的 Gram 矩陣與成對 距離。因此旋轉、鏡射、特徵向量符號的改變，都是同一幾何的有效表示。 比較兩幅圖時，應比較相對位置與距離，而不是某條軸的正負號。

例題

例題

例題一：重建三個共線點

取

$$D=\begin{bmatrix}0&1&3\\1&0&2\\3&2&0\end{bmatrix}, \qquad E=\begin{bmatrix}0&1&9\\1&0&4\\9&4&0\end{bmatrix}.$$

距離平方的行平均為 $10/3$、$5/3$、$13/3$，總平均為 $28/9$。雙重居中得到

$$B=\frac19\begin{bmatrix}16&4&-20\\4&1&-5\\-20&-5&25\end{bmatrix}.$$

令 $u=(-4,-1,5)^T$，便有 $B=uu^T/9$。唯一正特徵值為 $\|u\|_2^2/9=14/3$，所以一個座標已足夠：

$$X=\begin{bmatrix}-4/3\\-1/3\\5/3\end{bmatrix}.$$

座標平均為零，三對距離在指定位置分別是 $1$、$2$、$3$。每個座標加上 $4/3$，便得到 $0$、$1$、$3$；鏡射後也同樣有效。這顯示距離表沒有提供 絕對位置與方向。

$B$ 的部分非對角元素為負，只代表相應內積為負，與半正定並不矛盾。 半正定檢查的是二次型或特徵值，不是逐一檢查元素的符號。

例題

例題二：滿足度量條件卻不能歐氏嵌入

考慮四條單位邊組成的環，以最短路徑長度作距離：

$$D=\begin{bmatrix}0&1&2&1\\1&0&1&2\\2&1&0&1\\1&2&1&0\end{bmatrix}, \qquad B=\frac14\begin{bmatrix}3&1&-5&1\\1&3&1&-5\\-5&1&3&1\\1&-5&1&3\end{bmatrix}.$$

三角不等式成立：相對的兩點相距 $2$，可經兩條長 $1$ 的相鄰邊到達； 任何繞路都不會比最短路更短。然而 $B$ 的特徵值是 $2$、$2$、$0$、$-1$。 例如 $(1,-1,1,-1)^T$ 對應特徵值 $-1$。因此任何維數都不能精確重現這個 歐氏距離要求。

保留兩個正方向，得到

$$X_2=\begin{bmatrix}1&0\\0&1\\-1&0\\0&-1\end{bmatrix}.$$

相對兩點仍相距 $2$，但相鄰距離變成 $\sqrt2$。最小 Gram 平方誤差是 $(-1)^2=1$。負方向指出原幾何的真正障礙，不能把它的平方根當成另一個實 歐氏座標。正 Gram 近似取代了該部分幾何，因此部分距離會改變。

例題

例題三：精確保留次序而不重現原距離

三個物件的相異度為 $d_{12}=1$、$d_{23}=2$、$d_{13}=8$。由 $8>1+2$， 三角不等式不成立。不過一維座標 $0$、$1$、$3$ 的對應距離是 $1$、$2$、$3$， 恰好保留了原來的嚴格次序。

單調轉換可以取

$$f(1)=1,\qquad f(2)=2,\qquad f(8)=3.$$

如需定義觀測相異度之間的函數，可用斜率為正的線段連接以上數值。每個 轉換後相異度都等於擬合歐氏距離。下文定義的正規化 stress 因此為零，分母 $1^2+2^2+3^2=14$ 為正。

圖中次序完全正確，卻沒有重現原來的數值 $8$。序數目標選擇保留的正是這類 次序資訊；相鄰相異度之間的數值間隔可以改變。因此零序數 stress 與精確 重建經典距離，是兩個不同結論。

經典 MDS 的數值計算

以下以對稱特徵分解實作例題一。逐元素平方明確區分輸入距離與 Gram 構造。 此例使用一個小正閾值，把理論上的零特徵值與浮點捨入區分開來。

import numpy as np

D = np.array([[0, 1, 3], [1, 0, 2], [3, 2, 0]], dtype=float)
n = D.shape[0]
H = np.eye(n) - np.ones((n, n)) / n
E = D ** 2
B = -0.5 * H @ E @ H
eigenvalues, eigenvectors = np.linalg.eigh(B)
order = np.argsort(eigenvalues)[::-1]
eigenvalues = eigenvalues[order]
eigenvectors = eigenvectors[:, order]
selected = np.flatnonzero(eigenvalues > 1e-10)[:1]
X = eigenvectors[:, selected] * np.sqrt(eigenvalues[selected])
fitted = np.linalg.norm(X[:, None, :] - X[None, :, :], axis=2)
print(np.round(eigenvalues, 6))
print(np.round(fitted, 6))

特徵值約為 $14/3$、$0$、$0$，重建距離矩陣在數值精度內等於 $D$。程序 返回的座標列可能與手算結果符號相反。處理其他資料時，截斷前應查看負譜； 明顯的負特徵值，量度了正 Gram 近似捨去的資訊。

與 PCA 的連接

若其實也有特徵量測，設居中資料矩陣為 $A\in\mathbb R^{n\times d}$，並用 各行之間的歐氏距離組成 $D$。以上推導便給出

$$B=AA^T=U\Sigma^2U^T,\qquad X_k=U_k\Sigma_k=AV_k.$$

最後一式正是前幾個 PCA 得分的矩陣。因此，從相同歐氏幾何出發，經典 MDS 與 PCA 會產生相同的低維配置：一個以距離為起點，另一個以特徵為起點， 兩者共用居中的內積結構。特徵向量符號及重複特徵空間內的旋轉，會改變 顯示的軸，但不改變此結構。

Gram 特徵值是奇異值的平方，而非樣本協方差特徵值；後者另除以 $n-1$。 若把協方差特徵值的平方根當成 MDS 座標尺度，所有距離都會縮小 $\sqrt{n-1}$ 倍。要重現輸入的數值距離，必須保留正確正規化。

這個比較也區分了兩種誤差來源：捨去正特徵值，是刪去完整歐氏資料實際存在 的方向；捨去負特徵值，則是刪去不可能屬於實歐氏 Gram 分解的方向。兩者 都進入 strain 誤差和，但幾何原因不同。分開查看其大小，才能判斷圖形失真 主要來自維數選擇，還是輸入關係本身的非歐氏結構。

非度量 MDS 與 stress

定義

單調擬合相異度與正規化 stress

給定擬合距離 $\widehat d_{ij}=\|x_i-x_j\|_2$，選取觀測相異度的非遞減 函數 $f$。數值 $f(d_{ij})$ 稱為單調擬合值（disparities）。本節的正規化 stress 定義為

$$S(X,f)=\left( \frac{\sum_{i<j}(f(d_{ij})-\widehat d_{ij})^2} {\sum_{i<j}\widehat d_{ij}^2} \right)^{1/2}, \qquad \sum_{i<j}\widehat d_{ij}^2>0.$$

在這個函數約定下，相等的輸入相異度有相等的擬合值。非遞減函數容許水平 區段，所以不同輸入亦可能得到並列的擬合值。

固定 $X$ 時，分母是常數。先按輸入相異度排列物件對，再以非遞減數列擬合 當前的歐氏距離，這就是保序迴歸。若相鄰擬合值違反次序，可在無權最小二乘 步驟中合併一整組，並以該組平均代替其數值。相同輸入則共用一個擬合層級。

固定擬合相異度後，再調整座標以降低選定的 stress。座標問題非凸，因此起點 和這一步的求解進度都影響最後配置。交替兩步描述了一個優化方案；停止條件 令程序結束，並未證明它達到全域最小值。小 stress 表示擬合距離接近單調 擬合值，也不等於每個嚴格距離次序都必定正確。

分母必須為正，所以所有點完全重合、使比值無定義的配置不在定義域內。 對 $a>0$，把 $(X,f)$ 換成 $(aX,af)$，stress 不變。數值方法因此可以在居中 之外，再固定整體尺度。這些選擇消除了無關的位置與尺度自由，仍保留原有 的序數比較。

常見錯誤

常見錯誤

對準要比較的數學物件

雙重居中前，要把 $D$ 的元素平方。應檢查所得 Gram 矩陣是否半正定，而非 要求所有元素非負。合法度量也可能產生不定的居中 Gram 矩陣。經典截斷、 原距離擬合與序數 stress 比較不同物件，它們的數值誤差不能互相替代。

總結

經典 MDS 把成對距離平方轉成居中 Gram 矩陣，其譜決定能否精確歐氏嵌入， 並提供座標或正低秩近似。非度量 MDS 則把擬合距離與相異度的單調轉換 比較。居中固定平移，正交變換保留經典幾何，而座標與擬合相異度一同作 正比例縮放，會保留正規化序數 stress。

練習

思考檢查

練習一：兩個物件相距 $4$。求居中 Gram 矩陣、正特徵值，以及一個居中一維配置。

輸入矩陣對角為零，非對角為 $4$；居中前先把元素平方。

思考檢查

練習二：居中 Gram 矩陣的特徵值為 $5$、$2$、$0$、$-1$。能否精確重建歐氏距離？只保留一個正方向時，最小 Gram 平方誤差是多少？

把歐氏可嵌入性條件與秩一近似條件分開檢查。

思考檢查

練習三：仍取 $d_{12}=1$、$d_{23}=2$、$d_{13}=8$，但把座標固定為 $0$、$2$、$3$。求保序擬合值及所得正規化 stress。

依相異度由小至大排列，當前距離為 $2$、$1$、$3$。合併違反次序的相鄰組。

解答

解答 · 練習一解答

距離平方的每行平均與總平均均為 $8$，因此

$$B=\begin{bmatrix}4&-4\\-4&4\end{bmatrix}.$$

特徵值為 $8$、$0$。座標 $(-2,2)^T$ 平均為零，Gram 矩陣是 $B$，兩點 相距 $4$。正秩為一。

解答 · 練習二解答

負特徵值令任何維數都無法精確歐氏重建。秩一正近似保留 $5$，Gram 平方 誤差為 $2^2+0^2+(-1)^2=5$。保留的座標列，是特徵值 $5$ 的單位特徵向量 乘以 $\sqrt5$。

解答 · 練習三解答

前兩個距離違反非遞減次序，其最小二乘合併值為 $(2+1)/2=3/2$；第三個 擬合值保留為 $3$。所以

$$f(1)=f(2)=\frac32,\qquad f(8)=3,\qquad S=\sqrt{\frac{(3/2-2)^2+(3/2-1)^2+(3-3)^2}{2^2+1^2+3^2}} =\frac1{\sqrt{28}}.$$

非遞減保序迴歸容許這個水平區段。座標仍固定時，距離次序的反轉沒有消失； 後續座標步驟才會處理剩下的不匹配。

相關筆記

奇異值分解與主成分 介紹從特徵量測出發的居中與譜座標。 居中核與核 PCA 以特徵空間內積作起點。 Fisher 判別與類別散佈 利用類別標籤選取投影方向。 課程閱讀書目集中列出本課程使用的書籍。