Modal Clustering in a Class of Product Partition Models

Bayesian Analysis (2009) 4, Number 2, pp. 243{264
Modal Clustering in a Class of Product
Partition Models
⁄David B. Dahl
Abstract. This paper deflnes a class of univariate product partition models for
which a novel deterministic search algorithm is guaranteed to flnd the maximum
a posteriori (MAP) clustering or the maximum likelihood (ML) clustering. While
the number of possible clusterings of n items grows exponentially according to
the Bell number, the proposed mode-flnding algorithm exploits properties of the
modeltoprovideasearchrequiringonlyn(n+1)computations. NoMonteCarlois
involved. Thus, thealgorithmflndstheMAPorMLclusteringforpotentiallytens
of thousands of items, whereas it can only be approximated through a stochastic
search. Integrating over the model parameters in a Dirichlet process mixture
(DPM) model leads to a product partition model. A simulation study explores
the quality of the clustering estimates despite departures from the assumptions.
Finally, applications to three speciflc models | clustering means, probabilities,
and variances | are used to illustrate the variety of applicable models and mode-
flnding algorithm.
Keywords: Bayesian nonparametrics, Dirichlet process mixture model, model-
basedclustering,maximumaposterioriclustering,maximumlikelihoodclustering,
product partition models
1 Introduction
This paper considers a class of univariate product partition models (Hartigan 1990;
Barry and Hartigan 1992) whose properties are such that a proposed ...