Interactive demo · Bayesian and Probabilistic Machine Learning · Chapter 9

K-means and EM for Gaussian mixtures on Old Faithful

Both algorithms alternate two steps. K-means assigns every point to its nearest centre (E step) and then moves every centre to the mean of its points (M step); the distortion J, the sum of squared distances to the centres, can only go down. EM does the same with soft assignments: the E step computes each point's responsibilities (its colour is the mix of the component colours) and the M step refits the mixing weights, means and covariances (ellipses: one standard deviation); the log likelihood can only go up. The right-hand panel records J or ln p(X) after every half step, as in Figure 9.2 of Bishop (2006).

Algorithm

Number of clusters K

Start

Steps

EM options

every covariance fixed at εI (Section 9.3.2)

variance floor: every eigenvalue of Σ_k at least 0.01

Scoreboard

Try these

The data are standardised: each variable minus its mean, divided by its standard deviation, as in the book. The poor start puts the centres at (1.4, −1) and (−1.4, 1), read off Figure 9.1(a) (for other K, evenly spaced between them); EM starts with covariances 0.6I and equal weights. A random start uses K data points chosen by a seeded generator, so everyone sees the same run. “One on an outlier” keeps the poor start for K − 1 components and puts the last one, with covariance 0.001I, on the most isolated data point.

In the lecture notes

Chapter 9 notes: Section 9.1 (K-means: the distortion J, the E and M steps and why they converge), Section 9.2.1 (maximum likelihood for mixtures and its singularities), Section 9.2.2 (EM for Gaussian mixtures) and Section 9.3.2 (K-means as the small-variance limit of EM).
Why EM never decreases the likelihood: the companion demo the lower bound L(q, θ) and the KL gap.
Python code: code/ch09_mixture_em.py (functions kmeans and em_gmm, Figures 9.1, 9.2 and 9.8) and the checks in code/checks_ch09.py.