Combining multiple partitions created with a graph-based construction for data clustering

L. Galluccio, Olivier Michel, Pierre Comon, Alfred O. Hero, Mark Kliger, Mark Kliger Combining2009

TL;DR

This paper introduces a novel clustering method called EAC-DC that combines graph-based constructions (specifically, Prim's algorithm for Minimum Spanning Trees) with evidence accumulation. This approach effectively handles non-convex cluster shapes and improves clustering accuracy by leveraging the strengths of multiple clustering "weak learners."

What Problem Does This Paper Address?

Data clustering, a fundamental task in unsupervised learning, aims to group similar data points together. However, defining "similarity" and finding optimal clusterings is challenging, especially when clusters have irregular or non-convex shapes. Traditional clustering methods often struggle with these complex structures. Furthermore, different clustering algorithms or initializations can produce vastly different results, leading to the idea of "cluster ensembles" – combining multiple clustering outputs to achieve a more robust and accurate final partition. This paper tackles the problem of effectively combining these multiple clustering results, particularly for datasets with complex cluster geometries.

Methods

The core of the proposed method, EAC-DC (Evidence Accumulation Clustering with Dual rooted Prim tree cuts), involves two main stages:

  1. Graph-Based Co-association Measure: The authors adapt Prim's algorithm, a classic Minimum Spanning Tree (MST) construction algorithm, to create "dual-rooted" and "multi-rooted" trees. By running Prim's algorithm with different initializations and stopping it at various stages, they generate subtrees. The "Droopi" tree, formed by the union of two dual-rooted subtrees, provides a distance measure between pairs of points based on the weight of the last edge connecting the two subtrees. This measure is then used to compute a "co-association measure" between pairs of data points. This measure quantifies how often two points are assigned to the same cluster across multiple runs of the Prim-based clustering.
  2. Spectral Clustering for Ensemble: The computed co-association measures are then used to construct an affinity matrix. This matrix represents the similarity between all pairs of data points based on their co-association. Finally, spectral clustering is applied to this affinity matrix to extract the final cluster partitions. This approach allows for the identification of non-convex clusters, which are difficult for many traditional methods.

The paper also introduces a "multi-rooted tree" extension, which aims to label all data points, unlike the dual-rooted approach that can leave some points unlabeled.

Datasets

The paper evaluates its methods on:

  • Synthetic Datasets:

    • Two rings
    • Two spirals
    • Two half-moons These datasets are specifically chosen to represent non-convex cluster shapes, which are a key challenge the proposed method aims to address.
  • Real-world Datasets:

    • Iris dataset: A standard benchmark dataset with 150 points in 4 dimensions, featuring three classes of flower features.
  • Breast Cancer Wisconsin dataset: A dataset with 683 instances and 9 features, used for binary classification.

Key Insights and Ideas

  • MSTs for Non-Convexity: The paper highlights that graph-based methods, particularly those leveraging MSTs and their properties (like Prim's algorithm), are well-suited for capturing the local geometry of data distributions, making them effective for non-convex cluster shapes.
  • Co-association as a Bridge: The novel co-association measure derived from Prim-based trees acts as a crucial bridge. It aggregates information from multiple weak clustering runs into a single representation that spectral clustering can then effectively process.
  • Ensemble Power: The results strongly suggest that combining multiple clustering results (even from a single, albeit randomized, algorithm like Prim's) significantly improves clustering performance compared to single-run methods.
  • Spectral Clustering's Role: Spectral clustering, when applied to the co-association matrix, proves to be a powerful tool for extracting the final clusters, especially when dealing with the complex relationships captured by the co-association measures.

Key Results

  • Synthetic Data: The proposed EAC-DC method achieved perfect clustering (100% accuracy) on the synthetic datasets representing rings, spirals, and half-moons, outperforming other methods. The multi-rooted tree version also achieved perfect results.
  • Real-world Data (Iris): EAC-DC consistently outperformed other compared methods across various validity indices (Accuracy, Rand, Adjusted Rand, Jaccard, NMI). For instance, the best EAC-DC variant achieved an accuracy of 0.9600, significantly higher than EAC-AL (0.8733).
  • Real-world Data (Breast Cancer Wisconsin): EAC-DC variants again demonstrated superior performance, with EAC-DC 1 achieving an accuracy of 0.9678, outperforming most other methods, including MCLA (0.9575) and RCV (0.9663).

Limitations and Future Work

  • Parameter Tuning: The paper acknowledges that parameters like σ and β in the affinity matrix construction (Section 2.4) need to be adjusted. The optimal choice of these parameters is not deeply explored.
  • Computational Cost: While the paper notes that their method is less computationally intensive than Grikschat's original approach, running multiple Prim constructions and spectral clustering can still be computationally demanding for very large datasets.
  • Relative Contribution: The authors suggest that further study is needed to confirm the relative contribution of the Prim-based co-association measures versus the spectral clustering step in EAC-DC's success.
  • Future Work: The authors mention that further studies will be realized in a larger version of the paper, implying potential for more in-depth analysis and exploration of extensions. The multi-rooted EAC-DC also shows promise for cases with more than two clusters, suggesting further investigation in this direction.

Summary updated

Abstract

6 pages
BibTeX
@misc{galluccio2009combining,
  author = {L. Galluccio and Olivier Michel and Pierre Comon and Alfred O. Hero and Mark Kliger and Laurent Galluccio and Olivier Michel and Pierre Comon and Alfred O. Hero and Mark Kliger Combining and L. Galluccio and O. Michel and P. Comon and A. O. Hero and M. Kliger},
  title = {{Combining multiple partitions created with a graph-based construction for data clustering}},
  year = {2009},
}
Figure