多维缩放 MDS 是什么？根据两两距离把对象画到低维地图上

多维缩放（Multidimensional Scaling，MDS），也叫多维尺度分析，是一种降维和数据可视化的方法。它的输入是一组对象两两之间的距离或差异程度，输出是这些对象在一个低维空间，通常是二维或三维中的坐标，并且要求在这个低维空间中，各对象之间的距离尽可能地保持原来的距离关系。

一个直观的例子

假设我们只有一张表格，记录着中国若干个城市两两之间的距离，但没有任何城市的经纬度坐标。多维缩放能够根据这张距离表，在平面上为每个城市找到一个位置，画出一张“地图”，使得地图上城市之间的距离与表格中的距离基本一致。画出来的地图可能是旋转过的或者翻转过的，因为仅凭距离无法确定东南西北的方向，但城市之间的相对位置关系会被正确地还原出来。

多维缩放的强大之处在于，它处理的距离不一定是真正的地理距离，可以是任何形式的差异程度。比如在心理学研究中，让人们评价若干种饮料两两之间有多相似，多维缩放可以把这些饮料画在一张图上，口味相似的饮料会靠在一起。研究者可以从图中发现，人们在判断饮料时主要依据的是哪几个维度，比如甜度和是否含碳酸。

几种主要的类型

经典多维缩放：由沃伦·托格森在 1952 年提出，也叫主坐标分析。它假设输入的是欧氏距离，通过一系列的矩阵运算，把距离矩阵转换为样本之间的内积矩阵，再对它进行特征值分解，取最大的几个特征值和对应的特征向量，就得到了低维的坐标。当输入的距离是欧氏距离时，经典多维缩放的结果与主成分分析是等价的。它的计算简单，有解析解。

度量多维缩放：不要求输入是欧氏距离，而是通过优化的方法，让低维空间中的距离尽可能接近输入的距离。衡量两者差距的指标叫作“应力”，应力越小，说明低维的表示越好地保持了原来的距离。

非度量多维缩放：由约瑟夫·克鲁斯卡尔等人在 20 世纪 60 年代发展起来。它不要求保持距离的具体数值，只要求保持距离的大小顺序：如果 A 和 B 的差异大于 C 和 D 的差异，那么在低维空间中 A 和 B 的距离也应该大于 C 和 D 的距离。这特别适合处理那些只有相对意义的数据，比如人们对相似程度的主观评分，评分的具体数值可能没有严格的意义，但大小顺序是可信的。

应用和意义

多维缩放最早在心理学中发展起来，用于研究人们如何感知颜色、声音、味道等事物之间的相似性。后来被广泛用于市场研究，分析消费者心目中各个品牌之间的相对位置；生态学中比较不同地点的物种组成；生物信息学中展示不同样本的基因表达差异；社会科学中分析投票行为、文化差异等。在机器学习中，多维缩放是一种重要的降维方法，也是很多流形学习方法的基础：比如 Isomap 方法，就是先沿着数据的流形计算样本之间的测地距离，再用经典多维缩放把它们嵌入到低维空间中。

多维缩放的局限在于：需要计算和存储所有对象两两之间的距离，当对象数量很多时，计算的开销会很大；而且对于新加入的对象，通常需要重新计算整个嵌入。