「Multidimensional Scaling (MDS)」 是一种用于分析高维数据并将其可视化为低维空间的统计方法。它主要用于在保留点之间距离关系的前提下，减少数据的维度，从而方便直观地进行数据探索和模式识别。

应用场景

MDS 的主要优势是能够从复杂的高维数据中提取出易于理解的低维空间表示，使得数据分析和模式发现更加直观。广泛应用于市场研究、社会网络分析、基因表达分析、心理学与认知科学、文本分析、城市与交通规划以及推荐系统等领域。通过将高维数据映射到低维空间，MDS 帮助分析数据点之间的相似性和差异性，使得复杂数据模式更易于理解和可视化，支持各类决策和模式发现。以下是 MDS 的一些典型应用场景：

1. 「市场研究与消费者行为分析」：

通过分析消费者对不同产品或品牌的偏好，将它们投射到二维空间中，观察产品或品牌之间的相似性。比如，研究不同品牌在消费者心目中的定位，帮助企业进行产品定价、市场细分等决策。

2. 「社会网络分析」：

在社会网络中，MDS 可以用于可视化不同个体或群体之间的关系，显示社交群体之间的相似性或差异性。在社交媒体上，通过分析用户之间的互动关系，展示用户群体的分布和聚集情况。

3. 「基因表达分析」：

在生物信息学中，MDS 用于基因表达数据的降维，帮助研究人员发现不同基因样本之间的相似性。

4. 「心理学与认知科学」：

心理学家使用 MDS 研究人们对刺激（如颜色、声音、味道等）的感知差异，并将感知结果进行可视化。

基本原理

MDS 的目的是通过将高维数据映射到二维或三维空间，使得映射后点之间的距离尽可能接近它们在原始高维空间中的距离。换句话说，MDS 试图找到一种低维表示，使得数据点的几何结构（或相似性/距离）得到最大程度的保留。

MDS 算法可以分为度量 MDS (Metric MDS) 和非度量 MDS (Non-metric MDS)两类：

• 「度量 MDS」：假设输入数据中的相似性/差异性可以通过距离度量（如欧几里得距离）来量化，试图使得低维空间中的点对距离与高维空间中的距离成比例。
• 「非度量 MDS」：仅保留数据点相对距离的顺序关系，而不要求保留距离的绝对大小。它对数据进行排序，并在低维空间中保持这种顺序关系。

算法实现

• 「计算距离矩阵」：首先根据数据点之间的相似性或差异性计算距离矩阵。例如，可以使用欧几里得距离、曼哈顿距离或其他适当的距离度量。
• 「选择维度数」：用户选择要将数据映射到的低维空间的维度，通常为 2 维或 3 维。
• 「优化坐标」：MDS 寻找一个点集，使得在低维空间中点之间的距离与原始高维空间中的距离尽可能接近。为此，MDS 通过优化算法来最小化距离失真函数（如应力函数，Stress）。
• 「可视化结果」：低维坐标计算完成后，可以将其用于可视化展示，帮助理解数据的结构和模式。

AntV 实现的 MDS 布局算法采用了 Floyd-Warshall 算法来计算两点距离，对距离矩阵进行平方处理并乘以 -0.5，然后通过双重中心化消除偏移。接着对中心化矩阵执行奇异值分解（SVD），提取特征值和特征向量。最后，将左奇异向量与特征值相乘，得到每个数据点在二维空间中的坐标，实现降维。具体实现如下：

function MDS(distances: Matrix[]) {
  const dimension = 2;
  // 计算负半平方距离矩阵
  const M = mul(pow(distances, 2), -0.5);

  // 对矩阵进行双重中心化
  const rowMeans = M.mean('row');
  const colMeans = M.mean('column');
  const totalMean = M.mean();
  M.add(totalMean).subRowVector(rowMeans).subColumnVector(colMeans);

  // 使用奇异值分解（SVD）获取特征值和特征向量
  const svd = new SingularValueDecomposition(M);
  const eigenValues = sqrt(svd.diagonalMatrix).diagonal();

  // 将数据点映射到二维空间
  return svd.leftSingularVectors.toJSON().map((row: number[]) => {
    return mul([row], [eigenValues])
      .toJSON()[0]
      .splice(0, dimension);
  });
}

优缺点

优点

• 「适用于不同类型的距离矩阵」：MDS 可以处理多种类型的距离度量，包括欧几里得距离、曼哈顿距离以及基于相似性或非欧几里得的度量，因此具有较强的灵活性。
• 「良好的可视化效果」：通过将高维数据降维至二维或三维，MDS 可以直观地展示数据中的模式、聚类或差异性，使复杂的数据结构更易于理解。
• 「保留数据的几何结构」：MDS 通过最小化低维空间中点对距离与高维空间中距离的偏差，尽可能保留了原始数据的相对距离关系，从而能够在降维的同时保留重要的结构信息。
• 「适用于非线性数据」：相比一些线性降维方法（如PCA），MDS 适用于一些非线性数据结构的降维，可更好地捕捉复杂的相似性模式。

缺点

• 「计算复杂度较高」：MDS 需要计算一个完整的距离矩阵，并在迭代过程中优化目标函数（如应力函数），当数据集规模较大时，计算成本和内存消耗都会显著增加。
• 「解释性有限」：降维后的低维空间坐标缺乏明确的物理或统计意义，特别是在非度量 MDS 中，映射后的坐标仅保留了相对顺序，可能难以解释具体的坐标值。
• 「对噪声敏感」：MDS 依赖于相似性或距离矩阵，如果原始数据中含有噪声或异常值，这些偏差可能会影响距离矩阵的准确性，进而导致降维结果不理想。
• 「维度选择困难」：MDS 需要预先选择目标维度（通常是 2D 或 3D），但该选择并不总是直观的。如果选择不当，可能会导致信息丢失或扭曲数据结构。

参考文献

[1] Chapman, Alan & Laskowski, Andrew. (2019). Detrital zircon U-Pb data reveal a Mississippian sediment dispersal network originating in the Appalachian orogen, traversing North America along its southern shelf, and reaching as far as the southwest United States. Lithosphere. 11. 10.1130/L1068.1.

[2] Floyd R W. Algorithm 97: shortest path[J]. Communications of the ACM, 1962, 5(6): 345-345

[3] American Journal of Political Science Vol. 19, No. 2 (May, 1975), pp. 343-390 (48 pages) Published By: Midwest Political Science Association

[4] Cooper, L. G. (1983). A Review of Multidimensional Scaling in Marketing Research. Applied Psychological Measurement, 7(4), 427–450. doi:10.1177/014662168300700404

[5] Tzeng, J., Lu, H.HS. & Li, WH. Multidimensional scaling for large genomic data sets.BMC Bioinformatics 「9」, 179 (2008). https://doi.org/10.1186/1471-2105-9-179

[6] Lee, Hanjun & Suh, Yongmoo. (2014). Social media comparative analysis based on multidimensional scaling. Journal of the Korean Data and Information Science Society. 25. 665-676. 10.7465/jkdi.2014.25.3.665.