Clustering using objective functions and stochastic search

• Published in: Journal of the Royal Statistical Society. Series B, Statistical methodology Statistical methodology, 2008-02, Vol.70 (1), p.119-139
• Main Authors: Booth, James G., Casella, George, Hobert, James P.
• Format: Article
• Language: English
• Subjects: Algorithms; Bayesian method; Bayesian model; Best linear unbiased predictor; Biostatistics; Cell cycle; Cluster analysis; Distribution theory; Exact sciences and technology; General topics; Hastings algorithm; Linear mixed model; Markov analysis; Markov chain Monte Carlo methods; Markov chains; Mathematical vectors; Mathematics; Metropolis; Microarray; Modeling; Monte Carlo simulation; Multivariate analysis; Objective functions; Parametric inference; Parametric models; Probability and statistics; Probability theory and stochastic processes; Quadratic penalized splines; Random walk; Sciences and techniques of general use; Set partition; Statistical methods; Statistics; Studies; Yeast cell cycle; Yeasts
• ISSN: 1369-7412; 1467-9868
• DOI: 10.1111/j.1467-9868.2007.00629.x

A new approach to clustering multivariate data, based on a multilevel linear mixed model, is proposed. A key feature of the model is that observations from the same cluster are correlated, because they share cluster-specific random effects. The inclusion of cluster-specific random effects allows parsimonious departure from an assumed base model for cluster mean profiles. This departure is captured statistically via the posterior expectation, or best linear unbiased predictor. One of the parameters in the model is the true underlying partition of the data, and the posterior distribution of this parameter, which is known up to a normalizing constant, is used to cluster the data. The problem of finding partitions with high posterior probability is not amenable to deterministic methods such as the EM algorithm. Thus, we propose a stochastic search algorithm that is driven by a Markov chain that is a mixture of two Metropolis-Hastings algorithms-one that makes small scale changes to individual objects and another that performs large scale moves involving entire clusters. The methodology proposed is fundamentally different from the well-known finite mixture model approach to clustering, which does not explicitly include the partition as a parameter, and involves an independent and identically distributed structure.