Evaluating Clustering in Subspace Projections of High Dimensional Data

Emmanuel Müller, Stephan Günnemann, Ira Assent, Thomas Seidl

TL;DR

This paper tackles the challenge of comparing different subspace clustering algorithms, which aim to find clusters in projections of high-dimensional data. The authors propose a systematic framework and a comprehensive set of evaluation measures to benchmark existing paradigms, revealing their strengths, weaknesses, and scalability issues. Their work provides a much-needed common ground for future research in this critical area of data mining.

What Problem Does This Paper Address?

Clustering high-dimensional data is a significant challenge in data mining. Traditional clustering methods struggle with the "curse of dimensionality," where distances become less meaningful as the number of dimensions increases. Subspace clustering (or projected clustering) offers a solution by identifying clusters within specific projections (subspaces) of the data, where dimensions might have locally varying relevance. However, the field has seen a proliferation of diverse algorithms and evaluation metrics without a standardized comparison framework. This makes it difficult to understand the true performance of different approaches, compare results across studies, and identify the most promising directions for future research. The authors aim to bridge this gap by providing a systematic evaluation of major subspace clustering paradigms.

Methods

The paper categorizes existing subspace clustering algorithms into three main paradigms:

  • Cell-based approaches: These methods approximate the data space with cells and identify clusters as dense regions within these cells. They often rely on discretization and counting objects.
  • Density-based approaches: Inspired by DBSCAN, these algorithms define clusters as dense regions based on distance metrics within relevant subspaces. They are sensitive to the choice of distance function and neighborhood parameters.
  • Clustering-oriented approaches: These paradigms focus on optimizing global properties of the entire clustering result (e.g., number of clusters, average dimensionality) rather than defining individual cluster structures.

The authors implemented a comprehensive set of algorithms representing these paradigms within a unified, open-source framework (OpenSubspace, built on WEKA). They then evaluated these algorithms using a diverse set of measures, including object-based (Entropy, F1, Accuracy) and object- and subspace-based measures (RNIA, CE), which account for both object grouping and relevant dimensions. This multi-faceted evaluation allows for a thorough comparison of clustering quality and efficiency.

Datasets

The authors utilized a combination of:

  • Synthetic datasets: These datasets were generated with known hidden subspace clusters, allowing for precise evaluation using measures that consider both object grouping and relevant dimensions. The dimensionality of these datasets varied from 5 to 75 dimensions, with varying percentages of dimensions defining the hidden clusters (50%, 60%, 80%).
  • Real-world datasets: A collection of publicly available datasets from the UCI repository and other sources were used. These datasets typically have class labels, which were used to infer hidden clusters for object-based evaluation measures. The authors note that information about relevant dimensions for real-world clusters is usually unavailable, leading to a preference for object-based measures in these cases.

Key Insights and Ideas

  • No single best paradigm: The evaluation reveals that no single paradigm consistently outperforms others across all metrics and datasets. Each has distinct strengths and weaknesses.
  • Scalability is a major hurdle: Density-based approaches and some cell-based methods (like CLIQUE) struggle significantly with high-dimensional data, often failing to detect clusters within practical time limits.
  • Clustering-oriented approaches are sensitive to noise: While offering good scalability and easy parameterization, these methods can be heavily impacted by noisy data, leading to decreased quality.
  • Recent representatives show promise: Newer algorithms within each paradigm (e.g., MINECLUS for cell-based, INSCY for density-based) generally perform better and scale more effectively than their foundational counterparts.
  • The importance of relevant dimensions: Measures like CE and RNIA, which consider the relevant dimensions of clusters, provide a more nuanced and meaningful evaluation, especially for synthetic data, compared to purely object-based measures.
  • The trade-off between quality and runtime: Many algorithms demonstrate a clear trade-off: achieving higher clustering quality often comes at the cost of significantly increased computation time, particularly with increasing dimensionality and dataset size.

Key Results

  • Cell-based approaches (especially MINECLUS): Generally showed good performance in terms of clustering quality (CE measure) and scalability, outperforming other paradigms in many scenarios.
  • Density-based approaches: Exhibited poor scalability to high dimensions, with runtimes becoming prohibitive.
  • Clustering-oriented approaches (especially PROCLUS): Demonstrated reasonable runtimes and easy parameterization, but their quality was significantly affected by noise. PROCLUS, surprisingly, performed well in many comparisons.
  • Basic algorithms (CLIQUE, SUBCLU): Often produced an excessively large number of clusters, leading to lower quality scores on measures like CE and RNIA, despite potentially good F1/Accuracy scores.
  • Runtime limitations: For some algorithms, runtimes exceeded practical limits (e.g., several days), preventing their evaluation on larger or higher-dimensional datasets.

Limitations and Future Work

  • Limited evaluation of specific features: The authors note that measures for evaluating specific algorithmic properties like redundancy removal or the consideration of relevant subspaces in real-world data are still lacking.
  • Parameter tuning: While extensive parameter sweeps were performed, the authors acknowledge that finding optimal parameters can be challenging and data-dependent.
  • Future work: The paper's contribution of a unified framework, comprehensive evaluation measures, and baseline results is intended to serve as a foundation for future research. The authors encourage further work on developing algorithms that balance quality and efficiency, especially for high-dimensional and noisy data, and on creating more sophisticated evaluation measures.

Summary updated

BibTeX
@article{muller2009evaluating,
  author = {Emmanuel Müller and Stephan Günnemann and Ira Assent and Thomas Seidl},
  title = {{Evaluating Clustering in Subspace Projections of High Dimensional Data}},
  journal = {Proc. VLDB Endow.},
  year = {2009},
  url = {https://openreview.net/forum?id=TI5a98j2UM},
}
Figure