多维尺度分析 | ReConcept Lab

钩子问题：表格不是地图

设想你在比较五个校园学习地点：Library（图书馆）、Lab（实验室）、Cafe（咖啡馆）、Dorm（宿舍）和 Gym（体育馆）。你没有可靠的原始坐标，只知道每两个地点作为学习地点有多不相似。

电子表格能回答“Library 和 Gym 相差多远？”，但它不能给出地图那种一眼可见的空间判断。**多维尺度分析（Multidimensional Scaling，MDS）**要做的是：构造低维坐标，让地图上的可见距离尽量模仿这张表。

距离表想变成一张地图输入是对称的不相似度表 D，而不是原始特征列。

校园学习地点不相似度表 D。对称位置重复同一个承诺；对角线为 0，并在计算中忽略。
从 / 到	图书馆	实验室	咖啡馆	宿舍	体育馆
图书馆	0	1.4	2	3.2	3.6
实验室	1.4	0	1.6	2.7	2.4
咖啡馆	2	1.6	0	1.5	2.7
宿舍	3.2	2.7	1.5	0	2.2
体育馆	3.6	2.4	2.7	2.2	0

约定：条目非负；D 对称；stress 中每个满足 i < j 的无序样本对只计一次。

把这张表读作固定输入 $D$ 。表中条目非负。对角线为 0 或被忽略，因为一个项目到自己的距离为 0。表是对称的，所以 Library -> Lab 和 Lab -> Library 是同一个距离承诺。MDS 计算 stress 时，每个无序样本对只计一次，常用约定是 $i < j$ 。

这里使用“不相似度（dissimilarity）”这个宽泛说法：数字可以来自评分、编辑距离、问卷回答、图距离，也可以是真实欧氏测量。MDS 仍然可以尝试画地图，但有些表无法在二维中完美放下。

第一个朴素想法：先摆最近的点

最近的一对很容易。把 Library 和 Lab 摆成约 1.4 个单位远。再把 Cafe 放在它们附近。痛点从 Dorm 和 Gym 加入时开始：每个新点都要同时满足好几个距离。

朴素摆点追踪这个确定性追踪使用与距离表相同的图书馆、实验室、咖啡馆、宿舍、体育馆示例。

步骤 1/4: 读取固定距离表

每个无序样本对都有一个目标距离。对角线忽略，同一张表会用来评分每个候选地图。

总 stress12.39

每个候选布局都针对同一张固定表 D 打分。

选中样本对残差
样本对	目标	地图	残差	平方贡献
图书馆 - 实验室	1.4	1.4	0 几乎匹配	0
图书馆 - 咖啡馆	2	1.22	-0.78 太近 / 被压缩	0.61

凭感觉画图没有一个统一规则来决定哪个距离承诺应该获胜。把 Gym 从 Library 拉远，它可能又离 Dorm 太近。移动 Dorm，其他几个距离也会跟着改变。

成对承诺会互相拉扯朴素布局满足一个承诺，却会压缩或拉长其他承诺。

图书馆 - 实验室目标: 1.4朴素地图: 1.4

几乎匹配 (0)

图书馆 - 体育馆目标: 3.6朴素地图: 2.15

太近 / 被压缩 (-1.45)

宿舍 - 体育馆目标: 2.2朴素地图: 1

太近 / 被压缩 (-1.2)

注意图中的轴标签：布局 x 和 布局 y。这些是地图发明出来的坐标。它们不是“噪声水平”或“步行时间”这样的原始测量特征，除非输入表本来就来自这些量，并且解恰好与它们对齐。

核心发明：把不匹配变成可计量的分数

MDS 修补“凭感觉摆点”的办法，是让每个候选地图接受同一个评分。把项目 $i$ 放到低维点 $y_i$ 。然后把每对点在地图上的距离，与原始目标距离比较。

Stress 累积成对不匹配残差约定：地图距离 - 目标距离。

residual = 地图距离 - 目标距离。正值表示太远 / 被拉长；负值表示太近 / 被压缩。

朴素布局残差
样本对	目标	地图	残差	平方项
图书馆 - 体育馆	3.6	2.15	-1.45 太近 / 被压缩	2.09
实验室 - 宿舍	2.7	1.41	-1.29 太近 / 被压缩	1.65
咖啡馆 - 宿舍	1.5	0.64	-0.86 太近 / 被压缩	0.74
宿舍 - 体育馆	2.2	1	-1.2 太近 / 被压缩	1.44

较低 stress 布局残差
样本对	目标	地图	残差	平方项
图书馆 - 体育馆	3.6	3.73	+0.13 太远 / 被拉长	0.02
实验室 - 宿舍	2.7	2.67	-0.03 几乎匹配	0.0
咖啡馆 - 宿舍	1.5	1.58	+0.08 太远 / 被拉长	0.01
宿舍 - 体育馆	2.2	1.77	-0.43 太近 / 被压缩	0.19

朴素 stress12.39

改进 stress0.32

本页固定使用这个带符号残差约定：

r_{ij} = \delta_{ij} - d_{ij}

正残差表示地图把这一对放得太远，也就是被拉长（overstretched）。负残差表示地图把这一对放得太近，也就是被压缩（compressed）。

MDS 把这些不匹配累积成 stress：

\text{stress}(Y) = \sum_{i<j}(\delta_{ij} - d_{ij})^2

平方之后，正残差和负残差都会变成误差；大的扭曲也会比小扭曲付出更多代价。

追踪实验室：从表格到较低 stress

完整追踪使用同样的五个地点、同一张距离表和同一个残差约定。它不模拟随机优化；它只是比较一个粗糙布局和一个确定的较低 stress 布局，让评分思想保持可见。

MDS 追踪实验室这个确定性追踪使用与距离表相同的图书馆、实验室、咖啡馆、宿舍、体育馆示例。

步骤 1/5: 读取固定距离表

每个无序样本对都有一个目标距离。对角线忽略，同一张表会用来评分每个候选地图。

总 stress12.39

每个候选布局都针对同一张固定表 D 打分。

选中样本对残差
样本对	目标	地图	残差	平方贡献
图书馆 - 实验室	1.4	1.4	0 几乎匹配	0
图书馆 - 咖啡馆	2	1.22	-0.78 太近 / 被压缩	0.61

较低 stress 布局并不等于“真实布局”。它只是对所选目标和固定表 $D$ 更好。换一个 stress 公式、输出维度或不相似度表，可能会偏好另一张地图。

形式化版本

令 $d_{ij}$ 表示项目 $i$ 与项目 $j$ 之间的原始目标不相似度。令 $Y$ 表示重建出的坐标表， $y_i$ 表示项目 $i$ 在地图中的点。

符号跟着重建流程走D 表示固定距离表；Y 表示 MDS 正在寻找的坐标。

D固定成对距离表
Y候选地图坐标
delta_ij地图显示的距离
r_ij带符号残差
stress(Y)不匹配平方和

同一对点在地图中的距离是：

\delta_{ij} = \lVert y_i - y_j \rVert_2

换句话说， $\delta_{ij}$ 是重建地图对样本对 $i, j$ 显示出来的距离。

残差和 stress 是：

r_{ij} = \delta_{ij} - d_{ij}

\text{stress}(Y) = \sum_{i<j}(\delta_{ij} - d_{ij})^2

MDS 寻找让总不匹配较小的坐标。经典 MDS（classical MDS）在距离满足欧氏假设时有闭式路线。度量 MDS（metric MDS）和非度量 MDS（nonmetric MDS）优化相关的 stress 思想。本节点只关注共同的“从距离重建地图”问题，不展开这些求解器推导。

实现状态

实现中携带的概念不多，但大多数都是成对的：

状态	含义	为什么重要
距离矩阵 $D$	固定输入表，保存 $d_{ij}$	每个候选地图都针对同一组承诺打分
坐标 $Y$	当前低维点 $y_i$	这些是 MDS 会改变的变量
地图距离 $\delta_{ij}$	当前地图内测得的距离	它们会与目标表比较
残差 $r_{ij}$	带符号差值 $\delta_{ij} - d_{ij}$	显示哪些样本对被压缩或拉长
总 stress	残差平方和	给整个布局一个分数
停止或检查	迭代上限、改进很小或人工检查	低 stress 之后仍要看残差

read or compute the pairwise distance matrix D;
choose output dimension k and initialize coordinates Y;
repeat: evaluate pair residuals and reduce stress;
inspect the largest remaining distortions;

正确性直觉：有用的地图仍会留下痕迹

不变量很简单：不要移动目标。每个候选布局都用同一张固定 $D$ 打分。如果一个布局比另一个布局 stress 更低，它就更符合这个目标。

这句话有明确边界。它不证明当前显示的布局是全局最优。它不恢复原始坐标轴。它也不承诺在距离表有噪声、不是欧氏距离，或二维承载不了全部结构时仍能零失真。

残差检查器选择一个样本对，查看较低 stress 地图仍然怎样扭曲它。

样本对

目标距离 d_ij2.2

地图距离 delta_ij1.77

残差 r_ij-0.43

平方贡献0.19

解释

太近 / 被压缩

不变量

每个候选布局都针对同一张固定 D 打分。较低 stress 表示更符合这个目标，不证明坐标全局最优，也不证明坐标轴是真实原始特征。

所以残差不是事后调试，而是这个概念的一部分。地图之所以有用，是因为它能总结许多成对承诺；剩余残差则告诉你，这个总结在哪里弯曲了事实。

代价：每个点都要和每个点说话

有 $n$ 个项目时，完整距离表大约有 $n(n-1)/2$ 个有用条目。存储这张表是 $O(n^2)$ 。如果输出维度是 $k$ ，一次完整 stress 评估要计算每个地图距离，因此代价是 $O(n^2 k)$ 。

主要工作都是成对的一次完整 stress 扫描会访问每个无序样本对。

D存储 / 读取所有成对距离O(n^2)

Y保存 n 个 k 维地图点O(nk)

delta, r评估每个无序样本对O(n^2 k)

T在多次更新中重复成对工作T * O(n^2 k)

经典 MDS 提醒

经典 MDS 的闭式路线可能需要特征分解，这比一次 stress 扫描更昂贵。

示例拟合

改进地图的归一化 stress：0.005

如果优化器进行了 $T$ 次评估或更新，就要预期这类成对工作会反复出现。经典 MDS 还可能需要特征分解，那是另一种通常比一次 stress 扫描更重的代价。

常见混淆

混淆	修补
“坐标轴一定表示原始特征。”	MDS 轴是布局坐标。它们服务于距离重建，不保证有特征解释。
“低 stress 就是零 stress。”	低 stress 表示累计不匹配较小。一些样本对残差仍可能明显存在。
“MDS 就是 PCA。”	PCA 从坐标出发，保留高方差方向。MDS 从成对距离出发，保留这些距离。
“所有 MDS 变体只是同一个求解器。”	经典、度量、非度量 MDS 在求解路径或距离解释上不同，但共享“从距离画地图”的动机。

图中的连接

PCA 是有用的对照：它有原始坐标，并询问哪些方向保留方差。MDS 可以在坐标已经消失或不适合使用时开始，只要还有有意义的成对距离表。

Isomap 复用 MDS 的布局步骤。它的修补发生在上游：在画地图之前，先用邻居图上的最短路距离替代原始直线距离。

降维学习路径线性投影、保距离地图、监督判别和保邻嵌入分别解决不同痛点。

PCA

保留中心化数据变化最大的方向。

MDS

摆放点，让低维距离尽量模仿原始距离表。

Isomap

先用邻居图最短路估计流形距离，再做类似 MDS 的布局。

LDA

利用标签寻找投影方向，让类均值分开，同时让类内保持紧。

QDA

让每个类别保留自己的协方差，形成二次边界，而不是一个共享投影。

SNE

匹配高维与低维中的邻居概率。

t-SNE

用低维重尾相似度修补 SNE 的拥挤问题。

UMAP

构造模糊邻居图，再优化具有相似成员强度的低维图。

练习

在校园距离表中，为什么只需要计算一次 Library - Lab，不用再计算 Lab - Library？
在残差检查器里选一个负残差。为了让这一对不那么被压缩，你会在地图上做什么移动？哪一对可能因此变差？
为什么较低 stress 的 MDS 布局不能证明两个显示轴就是有意义的原始特征？

图谱连接 : 多维尺度分析