Interactive demo · Probabilistic Machine Learning: Advanced Topics · Chapter 31

DP-means clustering

Let the cluster variance of a Dirichlet process mixture shrink to zero while the concentration shrinks with it, and the Gibbs sampler becomes a hard rule: join the nearest centre unless its squared distance exceeds λ, in which case start a new cluster. Then move every centre to the mean of its points, and repeat. The circles show the radius √λ around each centre: a point outside all of them opens a cluster. The algorithm never increases the objective (sum of squared distances) + λK, but it stops at a local minimum.

Data set

Penalty λ per cluster

Run

Try these

Algorithm 31.3: start with one cluster at the overall mean; an assignment pass visits the points in the stored order (new clusters are placed on the point that opens them), then clusters left empty are dropped and the centres are recomputed. It stops when a pass changes no label. The two data sets are simulated stand-ins for those of supplementary Figure 31.6.

In the lecture notes