Clustering with k-means

Learning without labelsabout 9 minutes

Most of the world's data has no labels. Unsupervised learning looks for structure in it anyway: groups of similar customers, topics in documents, the few directions in which images actually vary. The simplest and most used clustering method is k-means (Lloyd's algorithm, devised in 1957 and published in 1982).

The objective

Choose $k$ centres $μ_{1}, \dots, μ_{k}$ and assign each point to one of them, so that the total squared distance from points to their centres, the within-cluster sum of squares (inertia), is as small as possible:

J = i = 1 \sum n ∥ x_{i} - μ_{c (i)} ∥^{2}

Lloyd's algorithm

Initialise $k$ centres, for example at $k$ randomly chosen data points.
Assign each point to its nearest centre.
Update each centre to the mean of the points assigned to it.
Repeat steps 2–3 until the assignments stop changing.

Step through k-means. Each assignment and each update can only lower the objective, so it always settles.

Each step can only decrease $J$ (assigning to the nearest centre can't increase any distance; the mean is the point minimising squared distance to a set), and there are finitely many assignments, so the algorithm always converges. But only to a local minimum: a bad start can leave two centres sharing one cluster. Standard practice is several random restarts and keeping the best, plus k-means++ initialisation (Arthur & Vassilvitskii, 2007), which spreads initial centres apart.

Choosing k, and what k-means assumes

The objective always falls as $k$ grows ( $k = n$ gives $J = 0$ ), so you can't minimise it over $k$ . Look for an elbow where adding clusters stops helping much, or use the silhouette score, which compares each point's distance to its own cluster with the nearest other one.
k-means favours round, similarly sized clusters, because it uses Euclidean distance to a single centre. Elongated or nested shapes need other methods (Gaussian mixtures, DBSCAN, spectral clustering).
Scale features first, as with k-NN.

try itedit the code and run it, nothing can break

python sleeps until you press run

k-means alternates "assign to the nearest centre" and "move each centre to its points' mean". It always converges, but to a local optimum that depends on the start.

← Metrics and folds