K-means

K-means is a clustering algorithm: you pick the number of groups, k, and it finds k centre points that carve the data into that many clusters.

Imagine planning k water tankers for a drought-hit district. Park them anywhere to start. Each village walks to its nearest tanker. Now look at each tanker's crowd and move the tanker to the centre of that crowd. Villages re-sort to whichever tanker is now nearest; tankers re-centre again. After a few rounds nothing moves — the tankers have settled into the natural population clusters.

That is the whole algorithm:

1. place k centres at random
2. assign every point to its nearest centre
3. move each centre to the mean of its assigned points
4. repeat 2-3 until assignments stop changing

It is fast, scales to millions of points, and is the default first attempt at clustering. Its assumptions are worth knowing because they are also its failures. It looks for roughly round, similar-sized blobs — crescent or ring shapes defeat it. You must choose k yourself (the "elbow" plot of error versus k is the usual guide). Results vary with the random start, so libraries run several starts and keep the best. And since "nearest" is measured with straight-line distance, feature-scaling first is mandatory.

Where to go next#

• Full lesson: Unsupervised learning
• Related terms: clustering, unsupervised-learning, feature-scaling, pca