kmeans() — k-Means clustering

Groups points into k clusters around moving centres.

kmeans(k, X)

Key idea

• A cluster is a group of nearby points; a centre (centroid) is just the average position of a group. Pick k, send each point to its nearest centre, then move each centre to its group's middle. Repeat. (e.g. assign -> update -> assign -> ...)
• Every pass lowers the within-cluster spread (how far points sit from their centre), so it always settles.
• The answer depends on the random starting centres, so it is run several times. (e.g. different seeds -> different clusters)
• It is unsupervised: no correct labels are given, just the geometry — and it favours round, similar-sized blobs.

Definition

$$\arg \underset{C}{\min }\sum _{j=1}^k\sum _{x\in C_j}\Vert x-{\mu }_j{\Vert }^2$$

$k$

how many clusters you ask for

$C_j$

the points in cluster j

${\mu }_j$

the centroid (mean) of cluster j

$\Vert x-{\mu }_j{\Vert }^2$

squared distance to the centroid

In plain words

Drop k flags on a map, send each town to its nearest flag, then move each flag to the middle of its towns. Repeat until the flags stop moving.

Where you'd use it

• Customer segmentation: grouping shoppers by behaviour into a few personas.
• Compressing an image by reducing it to k representative colours.
• Grouping documents or news stories into topics without labels.

Frequently asked questions

How do I choose k?

Try several and use the elbow or silhouette; results also vary with the random starts, so run it a few times.