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 EM algorithm. In the context of clustering, we argue that the hard assignments from the maximization phase 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 select the model structure. As an important example we discuss a top-down “Bayesian k-means” algorithm and a bottomup agglomerative clustering algorithm. In experiments we compare this algorithm against a number of alternative algorithms that have recently appeared in the literature.