Evolutionary Monte Carlo Methods for Clustering

Gopi Goswami, Jun S. Liu, Wing Hung WongJournal of Computational and Graphical Statistics 2007 · DOI

TL;DR

This paper introduces a novel population-based Markov Chain Monte Carlo (MCMC) algorithm called Population Based Clustering (PBC) for various clustering tasks. PBC employs new "crossover moves" that efficiently explore the complex space of cluster assignments, outperforming traditional methods like Gibbs sampling and K-means in escaping local optima and achieving better sample quality.

What Problem Does This Paper Address?

Clustering, the task of grouping similar observations, is fundamental in many fields. Traditional methods like K-means often get stuck in local optima, failing to find the globally best clustering. While MCMC methods like Gibbs sampling and Metropolis-Hastings can explore the solution space more broadly, they also struggle with multimodal distributions and can be inefficient. The authors aim to develop a more robust and efficient sampling-based approach for clustering that can effectively navigate complex, multimodal posterior distributions and identify optimal clusterings.

Methods

The core of this paper is the Population Based Clustering (PBC) algorithm, which is a population-based MCMC approach similar to parallel tempering and Evolutionary Monte Carlo (EMC). PBC works by maintaining a population of candidate clusterings across different "temperatures" (representing different levels of exploration vs. exploitation). The key novelty lies in three new "crossover moves":

  • SCSC:TWO-NEW: This move takes two parent clusterings and swaps intersections of their sub-clusters to create two new "child" clusterings. This is a more drastic move that perturbs both parents.
  • SCSC:ONE-NEW: This move uses one parent and one "child" clustering to create a single new child clustering by reallocating members of sub-cluster intersections. This is a less drastic move that perturbs only one parent.
  • SCRC (Sub Cluster Reallocation Crossover): Similar to SCSC:ONE-NEW, but instead of swapping, it randomly redistributes members of sub-cluster intersections. This is considered less drastic than SCSC moves.

These moves are designed to leverage the structure of clustering problems and facilitate efficient exploration of the solution space, aiming to improve upon existing MCMC techniques.

Datasets

The paper evaluates the PBC algorithm on several simulated datasets and a real-world dataset:

  • Bernoulli-Beta Clustering: Simulated data generated from a Bernoulli distribution with a conjugate Beta prior.
  • Motif Clustering: A simplified version of a motif clustering problem using biological sequence data.
  • Normal Clustering: Simulated multivariate Normal data.
  • Variable Selection: Simulated data for a variable selection problem.

The authors do not introduce new benchmark datasets but rather apply their method to established problem settings.

Key Insights and Ideas

  • Population-based MCMC for Clustering: The paper demonstrates that a population-based approach, by maintaining multiple states at different temperatures, is highly effective for navigating the complex, multimodal landscape of clustering problems.
  • Novel Crossover Moves: The SCSC and SCRC moves are a significant contribution, offering a middle ground between drastic "split-merge" operations and simpler Gibbs sampling updates. They are designed to exploit the specific structure of cluster indicator vectors.
  • Escaping Local Optima: PBC, particularly with its new moves, shows a strong ability to escape local modes, a common pitfall for algorithms like K-means and even standard MCMC methods. This is crucial for finding globally optimal or near-optimal clusterings.
  • Efficiency vs. Sample Quality: While PBC algorithms might require more computational effort per sample than simpler methods, they produce higher quality samples (as measured by AIAT and AMLD) and are more effective optimizers, making them a valuable alternative when sample quality is paramount.

Key Results

  • Performance Improvement: PBC algorithms consistently outperformed Gibbs sampling, Metropolis-Hastings, and K-means in terms of escaping local modes and achieving better sample quality (lower AIAT and AMLD) across various clustering tasks.
  • Bernoulli-Beta Clustering: PBC methods achieved significantly lower AIATs and AMLDs compared to Gibbs and MH, despite producing fewer samples in the same amount of CPU time.
  • Motif Clustering: PBC algorithms again showed superior performance in terms of AIAT and AMLD, outperforming Gibbs and MH. The acceptance rates of the new moves varied, with some being problem-specific.
  • Normal Clustering: K-means was shown to get stuck in local modes frequently, while PBC methods consistently found better clusterings.
  • Variable Selection: PBC algorithms and EMC performed comparably well, both achieving the same minimum BIC value, outperforming other methods.

Limitations and Future Work

  • Computational Cost: Implementing PBC is described as a "challenging programming exercise," and the algorithms can be computationally more demanding per sample than simpler methods.
  • Parameter Tuning: The performance of PBC can be sensitive to the choice of temperature ladder and mutation rate, which require careful tuning.
  • "True" Cluster Indicator Recovery: With limited data, it can be difficult to recover the exact "true" cluster indicator vector, even with advanced methods, due to sampling variability.
  • IAT as a Measure: The authors question the sole reliance on Integrated Autocorrelation Time (IAT) as a measure of sampler performance, suggesting it can be misleading if a sampler moves freely within a local mode.
  • Future Research: The authors suggest further research into the choice of temperature ladder, the design of new moves, and addressing the challenge of providing meaningful "confidence intervals" for cluster indicators. They also highlight the need for better metrics beyond IAT for evaluating sampler performance.

Summary updated

Abstract

The problem of clustering a group of observations according to some objective function (e.g., K-means clustering, variable selection) or a density (e.g., posterior from a Dirichlet process mixture model prior) can be cast in the framework of Monte Carlo sampling for cluster indicators. We propose a new method called the evolutionary Monte Carlo clustering (EMCC) algorithm, in which three new “crossover moves,” based on swapping and reshuffling sub cluster intersections, are proposed. We apply the EMCC algorithm to several clustering problems including Bernoulli clustering, biological sequence motif clustering, BIC based variable selection, and mixture of normals clustering. We compare EMCC's performance both as a sampler and as a stochastic optimizer with Gibbs sampling, “split-merge” Metropolis–Hastings algorithms, K-means clustering, and the MCLUST algorithm.
BibTeX
@article{goswami2007evolutionary,
  author = {Gopi Goswami and Jun S. Liu and Wing Hung Wong},
  title = {{Evolutionary Monte Carlo Methods for Clustering}},
  journal = {Journal of Computational and Graphical Statistics},
  year = {2007},
  doi = {10.1198/106186007x255072},
}
Figure