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}$，第 $i$ 行存放点 $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$ 正交，所以相应坐标仍然中心化。

对于正交的 $k\times k$ 矩阵 $Q$，$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 判别与类别散布 借助类别标签选择投影方向。 课程阅读书目集中列出课程使用的书籍。