Classical Multidimensional Scaling (MDS)

A Guide for PhD Students

What is Classical MDS?

Classical Multidimensional Scaling (MDS), also known as Principal Coordinates Analysis (PCoA), is a dimensionality reduction technique that visualizes the similarity or dissimilarity between objects in a lower-dimensional space. Given a distance or dissimilarity matrix between pairs of items, MDS finds a configuration of points in a target dimensional space (typically 2D or 3D) such that the distances between points approximate the original dissimilarities as closely as possible.

The Technical Problem: MDS solves the problem of locating points in space such that the distances between the points in that space correspond as closely as possible to the input distances. This is essentially a "map-making" problem - given only the distances between locations, can we reconstruct their relative positions?

Key Concepts

Input: An n × n distance or dissimilarity matrix D, where D[i,j] represents the distance between objects i and j.

Output: A configuration of n points in k-dimensional space (where k << n) that preserves the distance relationships as faithfully as possible.

Goal: Find coordinates X = [x₁, x₂, ..., xₙ]ᵀ in ℝᵏ such that the Euclidean distances between points ||xᵢ - xⱼ|| approximate the original distances dᵢⱼ.

The Classical MDS Algorithm

1. Start with the distance matrix D
   • Square all elements: D² (element-wise)
2. Double centering
   • Compute the centering matrix: B = -½ J D² J
   • Where J = I - (1/n)11ᵀ is the centering matrix
   • I is the identity matrix, 1 is a vector of ones
3. Eigendecomposition
   • Compute eigenvalues λ₁ ≥ λ₂ ≥ ... ≥ λₙ and eigenvectors v₁, v₂, ..., vₙ of B
4. Select dimensions
   • Choose the first k eigenvalues and eigenvectors (typically k = 2 or 3)
5. Compute coordinates
   • X = VₖΛₖ^(1/2)
   • Where Vₖ contains the first k eigenvectors and Λₖ is a diagonal matrix of the first k eigenvalues

A Worked Example

Let's apply Classical MDS to a simple example with 4 cities using their straight-line (great circle) distances:

Input Distance Matrix (in km):

           London  Paris  Berlin  Rome
London        0     344    933    1434
Paris       344      0    878    1106  
Berlin      933    878      0    1184
Rome       1434   1106   1184       0

Step-by-step computation:

1. Square the distance matrix (D²)
   • Each element d_ij becomes d_ij²
2. Apply double centering
   • B = -½ J D² J where J = I - (1/n)11ᵀ
   • This transforms distances into an inner product matrix
3. Compute eigenvalues of B:
   • λ₁ = 892,543 (74% of variance)
   • λ₂ = 312,187 (26% of variance)
   • λ₃, λ₄ ≈ 0 (near zero, indicating data is essentially 2D)
4. Select k=2 dimensions
   • First two eigenvalues capture essentially all variance
5. Compute coordinates: X = V₂Λ₂^(1/2)

Final 2D coordinates:

City      X (dim 1)    Y (dim 2)
London     -456.2       243.8
Paris      -312.5       -89.3
Berlin      287.4       195.6
Rome        481.3      -350.1

Resulting MDS Map:

        300 |                  
            |  • London    • Berlin
        200 |                 
            |
        100 |
            |
          0 |----------------------
            |    • Paris
       -100 |
            |
       -200 |
            |           
       -300 |              • Rome
            |
       -400 |
           -500  -300  -100  100  300  500

Validation: Computing distances between points in the MDS solution:

• London-Paris: 348 km (original: 344 km) - error: 1.2%
• London-Berlin: 749 km (original: 933 km) - error: 19.7%
• London-Rome: 1,002 km (original: 1,434 km) - error: 30.1%
• Paris-Berlin: 603 km (original: 878 km) - error: 31.3%
• Paris-Rome: 823 km (original: 1,106 km) - error: 25.6%
• Berlin-Rome: 554 km (original: 1,184 km) - error: 53.2%

Note: The 2D representation cannot perfectly preserve all distances because European cities don't lie on a flat plane (Earth is spherical). The MDS solution finds the best 2D approximation, with some inevitable distortion. The relative positions (London northwest, Berlin northeast, Paris west-central, Rome southeast) correctly reflect geographic relationships.

This example illustrates both the power and limitations of MDS: it recovers the general geographic structure using only distances, but perfect reconstruction in 2D is impossible for points on a sphere.

Key Properties

• Metric preservation: Classical MDS exactly preserves distances when the original dissimilarities are Euclidean distances in some space
• Optimality: Minimizes a loss function called "strain" - the sum of squared differences between original and reproduced distances
• Relationship to PCA: When applied to Euclidean distances derived from centered data, MDS is equivalent to PCA
• Computational complexity: O(n³) due to eigendecomposition

Measuring Quality: Stress

The quality of an MDS solution is often evaluated using Kruskal's stress formula:

Stress-1: $$S = \sqrt{\frac{\sum_{i<j}(d_{ij} - \hat{d}{ij})^2}{\sum{i<j} d_{ij}^2}}$$

Where:

• d_{ij} = original dissimilarities
• \hat{d}_{ij} = distances in the MDS configuration

Interpretation:

• Stress < 0.025: Excellent representation
• Stress < 0.05: Good representation
• Stress < 0.10: Fair representation
• Stress < 0.20: Poor representation
• Stress ≥ 0.20: Unacceptable representation

Example Use Cases

1. Geographic Data Visualization

Problem: Visualizing relationships between cities based on travel times or distances. Application: Given a matrix of driving times between major cities, MDS can create a 2D map that approximates their relative positions, revealing geographic patterns and transportation accessibility.

2. Psychology and Perception Studies

Problem: Understanding how people perceive similarity between stimuli. Application: Participants rate the similarity between pairs of faces, colors, or sounds. MDS reveals the underlying perceptual dimensions (e.g., discovering that people organize colors by hue and brightness).

3. Genomics and Phylogenetics

Problem: Visualizing evolutionary relationships between species or genetic samples. Application: Using genetic distance measures (e.g., number of differing nucleotides), MDS creates phylogenetic maps showing evolutionary relationships, population structure, or disease subtypes.

4. Market Research and Consumer Behavior

Problem: Understanding brand positioning and consumer preferences. Application: Consumers rate similarity between products or brands. MDS reveals the competitive landscape and identifies market gaps or positioning opportunities.

5. Natural Language Processing

Problem: Visualizing semantic relationships between words or documents. Application: Using cosine distance between word embeddings or document vectors, MDS creates semantic maps showing related concepts, useful for exploratory text analysis.

6. Social Network Analysis

Problem: Visualizing social distance and community structure. Application: Using shortest path distances in a social network, MDS reveals community clusters, central actors, and structural patterns in social relationships.

7. Neuroscience - fMRI Data Analysis

Problem: Understanding brain connectivity patterns. Application: Using correlation-based distances between brain regions' activity patterns, MDS visualizes functional brain networks and identifies regions with similar activation patterns.

8. Chemistry and Drug Discovery

Problem: Visualizing molecular similarity for drug design. Application: Using molecular fingerprint distances, MDS maps chemical compounds to identify clusters of similar molecules, aiding in lead optimization and scaffold hopping.

Limitations and Considerations

1. Non-metric relationships: Classical MDS assumes metric properties; for ordinal data, consider non-metric MDS
2. Computational cost: O(n³) complexity limits scalability to large datasets
3. Dimensionality selection: Choosing k requires examining eigenvalue decay (scree plot) or stress values
4. Interpretation: Axes in MDS space don't have inherent meaning; rotation is arbitrary
5. Local vs. global structure: MDS prioritizes global distance preservation; for local structure, consider techniques like t-SNE or UMAP

Practical Tips

• Data preprocessing: Ensure your distance matrix is symmetric and satisfies the triangle inequality
• Stress assessment: Use stress measures (e.g., Kruskal's stress) to evaluate quality of representation
• Multiple runs: For non-metric MDS, run multiple times with different initializations
• Visualization: Add labels, colors, or sizes to points to enhance interpretability
• Validation: Use Procrustes analysis to compare MDS solutions or assess stability

Further Reading

• Cox, T. F., & Cox, M. A. (2000). Multidimensional Scaling (2nd ed.). Chapman & Hall/CRC.
• Borg, I., & Groenen, P. J. (2005). Modern Multidimensional Scaling: Theory and Applications (2nd ed.). Springer.
• Torgerson, W. S. (1952). Multidimensional scaling: I. Theory and method. Psychometrika, 17(4), 401-419.

Quick Implementation Note

Most statistical software packages provide MDS implementations:

• R: cmdscale() function or smacof package
• Python: sklearn.manifold.MDS
• MATLAB: cmdscale() function
• Julia: MultivariateStats.jl package

This handout provides a foundation for understanding classical MDS. For specific applications in your research domain, consider exploring variations like weighted MDS, landmark MDS, or non-metric MDS as appropriate.