Modified Multidimensional Scaling and High Dimensional Clustering

Qiang SunarXiv 2018 · arXiv

TL;DR

This paper introduces Modified Multidimensional Scaling (MMDS), a novel dimension reduction technique that significantly improves clustering performance on high-dimensional, noisy data. MMDS outperforms classical Multidimensional Scaling (CMDS) by applying a nonlinear transformation to sample eigenvalues, leading to more accurate cluster recovery, especially in challenging scenarios.

What Problem Does This Paper Address?

Clustering high-dimensional data is a persistent challenge due to the "curse of dimensionality." As the number of features increases, distances between data points become less meaningful, and many attributes become noisy, hindering the effectiveness of traditional clustering algorithms like K-means. While Multidimensional Scaling (MDS) offers a way to reduce dimensionality by preserving pairwise distances, its theoretical performance in high dimensions and noisy settings is not well-understood. This paper addresses this gap by proposing MMDS, a robust alternative to CMDS that explicitly accounts for noise and high dimensionality to achieve better clustering outcomes.

Methods

The core of this work is the Modified Multidimensional Scaling (MMDS) algorithm. Unlike classical MDS (CMDS), which directly uses eigenvectors of the centered distance matrix, MMDS applies a nonlinear transformation to the sample eigenvalues before embedding the data. This transformation is designed to be robust to noise and depends on the sample size, dimensionality, and noise characteristics. The authors provide a unified theoretical framework that covers low, moderate, and high-dimensional regimes. They also propose a novel method for estimating the number of clusters, which in turn helps determine the embedding dimension, without needing to estimate the intrinsic dimensionality of the data. The paper then analyzes the theoretical properties of MMDS and its performance when combined with various standard clustering algorithms, demonstrating its ability to achieve "exact recovery" (correctly identifying all cluster labels with high probability).

Datasets

The paper evaluates its methodology on two real-world datasets:

  • TCGA Microarray Gene Expression Dataset: This dataset comprises gene expression data from glioblastoma multiforme (GBM) and lung squamous cell carcinoma (LUSC) tissues.
  • A High Dimensional Dataset with 16 Clusters (dim512): This dataset is a benchmark for clustering algorithms, featuring 16 distinct Gaussian clusters.

Key Insights and Ideas

  • Noise Robustness is Key: The paper highlights that classical MDS struggles with noisy high-dimensional data because noise can distort the sample eigenvalues and eigenvectors. MMDS's nonlinear transformation is specifically designed to mitigate this issue.
  • Eigenvalue Transformation Matters: The core innovation of MMDS lies in its nonlinear transformation of sample eigenvalues. This step is crucial for separating signal from noise and improving the quality of the embedded data.
  • Estimating Cluster Count as Embedding Dimension: A surprising and practical insight is that estimating the number of clusters can directly inform the embedding dimension for MDS, simplifying a common challenge in MDS applications.
  • Theoretical Guarantees in High Dimensions: The paper provides strong theoretical guarantees for MMDS, showing its effectiveness across various dimensional regimes, including the challenging high-dimensional setting (d >> N).

Key Results

  • Improved Clustering Performance: Numerical simulations and real-data applications demonstrate that MMDS consistently outperforms CMDS and clustering on original (unreduced) data, especially as noise levels increase.
  • Exact Recovery Achieved: MMDS, when combined with standard clustering algorithms (K-means, single linkage, complete linkage, average linkage, centroid linkage), achieves "exact recovery" of cluster labels with high probability.
  • Sharper Bounds: The paper establishes sharper $l_\infty$ perturbation bounds for the MMDS embedding matrix compared to CMDS, indicating a more accurate representation of the data structure.
  • Robustness to Noise: Tables and figures show that MMDS-based clustering maintains good performance even with significant noise, while CMDS-based methods degrade more rapidly.

Limitations and Future Work

  • Suboptimality in Perturbation Analysis: The authors acknowledge that their $l_\infty$ bounds might be suboptimal due to the combination of perturbation analysis and random matrix theory. They suggest that further improvements might be possible by exploring more advanced random matrix theory techniques.
  • Distinct Eigenvalues Assumption: The theoretical results are primarily derived under the assumption that the signal eigenvalues are distinct. The paper notes that the theorems still hold if some eigenvalues are equal, but this might require a rotation matrix.
  • Non-linear Dimensionality Reduction: The authors suggest exploring non-linear extensions of MDS, such as the Isomap algorithm, which uses geodesic distances, as a future research direction. This could be beneficial for datasets with non-linear manifold structures.

Summary updated

BibTeX
@misc{sun2018modified,
  author = {Qiang Sun},
  title = {{Modified Multidimensional Scaling and High Dimensional Clustering}},
  year = {2018},
  eprint = {1810.10172},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1810.10172},
}
Figure