title: Bayesian k-Means as a "maximization-expectation" algorithm.
abstract: We introduce a new class of "maximization-expectation" (ME) algorithms where we maximize over hidden variables but marginalize over random parameters. This reverses the roles of expectation and maximization in the classical expectation-maximization algorithm. In the context of clustering, we argue that these hard assignments open the door to very fast implementations based on data structures such as kd-trees and conga lines. The marginalization over parameters ensures that we retain the ability to infer model structure (i.e., number of clusters). As an important example, we discuss a top-down Bayesian k-means algorithm and a bottom-up agglomerative clustering algorithm. In experiments, we compare these algorithms against a number of alternative algorithms that have recently appeared in the literature.
authors.affiliation: Department of Computer Science, Tokyo Institute of Technology, Meguro-ku, Tokyo 152-8552, Japan. kurihara@mi.cs.titech.ac.jp
authors.forename: Kenichi
authors.initials: K
authors.lastname: Kurihara
authors.forename: Max
authors.initials: M
authors.lastname: Welling
mesh_terms: D000465:Algorithms; D001185:Artificial Intelligence; D001499:Bayes Theorem; D008959:Models, Neurological