Interactive demo · Statistical Methods for Modern Biology · Chapter 5

k-means, k-medoids and PAM, step by step

k-means alternates two steps: assign every point to its nearest centre, then update every centre to the mean of its points. Each step can only lower the objective J = Σ |x − c|², so the algorithm stops after finitely many steps, but possibly in a local minimum. k-medoids uses data points (medoids) as centres and any distance; the alternating version follows the book's description, while PAM (BUILD then SWAP, the algorithm of cluster::pam) tries every exchange of a medoid with a non-medoid and makes the best one. The right panel records the objective after every step.

Data

Algorithm

Distance (medoid methods)

Number of clusters k

Start (k-means, alternating k-medoids)

Steps

Scoreboard

Try these

The poor start puts all k seeds in the lower-left group of the simulation (rows 5, 17, 33, 48, ... of the data, R numbering). A random start uses k distinct data points chosen by a seeded generator, so everyone sees the same run. PAM does not need a start: BUILD chooses the first medoid as the point with the smallest total distance to all others, then adds the point that lowers the total most, until there are k.

In the lecture notes