K-Means ClusteringK-Means Clustering

In 1957, Stuart Lloyd, an engineer at Bell Labs, was thinking about how to transmit a signal like a human voice using as few bits as possible. His solution was to place a set of representative points and repeatedly nudge each one toward the average of the samples nearest to it.

That simple loop, assign every point to its closest center, then move each center to the mean of its assigned points, is the algorithm the world now calls k-means. Lloyd's write-up circulated inside Bell Labs but was not formally published until 1982.

The name arrived from elsewhere. In 1967 James MacQueen coined the term 'k-means' in a statistics paper, and closely related ideas appeared independently in the work of Hugo Steinhaus and Edward Forgy. It is one of those methods that several people discovered because it was almost the obvious thing to do.

K-means is unsupervised: nobody tells it what the groups are. You choose k, the number of clusters, and the algorithm finds a partition that minimizes the total squared distance from points to their centers, the same least-squares idea that runs through much of statistics.

Its weaknesses are well known. The result depends on where the centers start, it assumes clusters are roughly round and similar in size, and you have to guess k in advance. Yet it is fast, easy to explain, and often good enough.

Nearly seventy years later, k-means is still one of the first tools reached for whenever someone needs to find structure in unlabeled data, from customer segments to image compression, the very problem Lloyd started with.