Multidimensional Scaling and Data Clustering

Thomas Hofmann, Joachim M. BuhmannNeurIPS 1994 · OpenReview

Abstract: This paper introduces a unified framework for visualizing and grouping data using only pairwise dissimilarities, even when those distances are "messy" and non-metric. By applying principles from statistical mechanics, the authors develop an algorithm that simultaneously clusters data and embeds it into Euclidean space. Furthermore, they introduce an "active selection" strategy to discover structure using significantly less data than random sampling.

The Challenge of Pairwise Dissimilarity Data

In many fields—from genetics to linguistics—researchers deal with data that isn't defined by standard coordinates (like $x, y$ points on a graph) but by pairwise dissimilarities (how different item A is from item B). Analyzing this type of data presents three major challenges:

  1. Non-Metric Data: Real-world dissimilarities often violate the rules of geometry. For example, they might violate the triangle inequality, where the direct distance from A to C is longer than the path from A to B to C.
  2. Computational Complexity: Finding the best way to group (cluster) or visualize (embed) this data is a non-convex optimization problem. Algorithms easily get stuck in local traps rather than finding the best global solution.
  3. The $O(N^2)$ Wall: As the number of data points ($N$) grows, the number of pairs you need to measure grows quadratically. Measuring every single pair quickly becomes prohibitively expensive.

The authors aim to solve these issues by treating data points like particles in a physical system, using the "Maximum Entropy" principle to find robust, stable structures.

A Statistical Mechanics Approach

The authors leverage the Maximum Entropy principle, a concept borrowed from statistical mechanics, to rethink how we map and group data.

  • The Gibbs Distribution: They treat the coordinates of data points as random variables. Instead of looking for one "perfect" set of coordinates, they look for a probability distribution of coordinates that minimizes "free energy." This probabilistic approach helps the algorithm avoid getting stuck in poor local minima.
  • Simultaneous Optimization: Traditionally, researchers might cluster data first and then try to visualize it, or vice versa. This paper derives a system of equations to do both at once. The embedding (the visual map) is explicitly constrained to respect the cluster structure.
  • Mean-Field Approximation: To make the math tractable, they use a "mean-field" approach. This simplifies the complex interactions between all pairs of points into an average "field" that acts on each point individually, leading to an efficient Expectation-Maximization (EM) style algorithm.
  • Active Data Selection: This is the "smart query" component. Instead of picking pairs to measure at random, the algorithm calculates which missing dissimilarity value would most reduce the uncertainty (variance) of the system's total energy. It then actively "queries" that specific data point.

Datasets

The paper evaluates the approach on two real-world datasets:

  1. Protein Sequences: 145 sequences from the globin family. Dissimilarities were calculated via sequence alignment, reflecting biochemical and structural similarity.
  2. Linguistic Data: 54 word fragments generated by a dynamic programming algorithm.

Key Insights and Results

By treating clustering as a problem of minimizing free energy, the authors can use "temperature" (an inverse weighting parameter $\beta$) to control the optimization. High temperatures allow the algorithm to explore the space, while low temperatures force it to settle into a stable structure. This allows the method to successfully embed non-metric data into a $D$-dimensional Euclidean space; even if the input data "breaks the rules" of geometry, the algorithm finds the best-fitting physical representation.

Crucially, the authors demonstrate that you don't need a complete distance matrix to understand a dataset. If you have a rough idea of the clusters, you can infer missing distances by looking at how other members of the same cluster behave.

Clustering results and active selection performance

The results highlight several major improvements over classical methods:

  • Efficiency Gains: The Active Selection strategy is remarkably efficient. For the protein dataset, the algorithm inferred the complete cluster structure using only 3,300 queries, whereas a random selection strategy required 6,500 queries to reach the same quality (as seen in panel d above).
  • Superior Embedding: The authors' multidimensional scaling (MDS) solution for the protein data was roughly twice as accurate (in terms of the cost function) as classical MDS programs, which often rely on simpler linear projections.
  • Robustness: The visualization shows clear "squares" along the diagonal of the sorted dissimilarity matrix (panel a), indicating that the algorithm successfully recovered known biological families (hemoglobin, myoglobin, etc.) without prior labels.

Limitations and Future Work

While active selection saves significantly on data acquisition, calculating the "relevance" of every missing pair involves solving systems of linear equations. This computational overhead could become a bottleneck for extremely large datasets ($N$). Additionally, to keep complexity low, the authors assume that the change in cluster centroids is negligible when updating individual point coordinates. While effective here, this approximation might be less accurate in very small or highly volatile datasets.

Future work will investigate extensions to other types of MDS cost functions beyond the standard squared-error approach, potentially broadening the framework's applicability.

Summary updated

Abstract

Visualizing and structuring pairwise dissimilarity data are difficult combinatorial op(cid:173) timization problems known as multidimensional scaling or pairwise data clustering. Algorithms for embedding dissimilarity data set in a Euclidian space, for clustering these data and for actively selecting data to support the clustering process are discussed in the maximum entropy framework. Active data selection provides a strategy to discover structure in a data set efficiently with partially unknown data.
BibTeX
@inproceedings{hofmann1994multidimensional,
  author = {Thomas Hofmann and Joachim M. Buhmann},
  title = {{Multidimensional Scaling and Data Clustering}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1994},
  url = {https://openreview.net/forum?id=Hy4O-OZu-H},
}
Figure