The clustering method born at Bell Labs waited 25 years for publication
In 1957 Stuart Lloyd of Bell Labs devised a simple loop for squeezing signals into fewer values: sort points to their nearest centre, move each centre to the average of its points, repeat. It did not appear in a journal until 1982. Today that loop, k-means, is one of the best-known tools in data analysis.
The goal is to split a set of observations into a chosen number of groups, k, so that each point sits with the cluster whose average, or centroid, is closest. Formally, it minimises the total squared distance from points to their centroids, the within-cluster variance. Because overall variance is fixed, that is the same as pushing different clusters as far apart as possible. The result carves space into regions called Voronoi cells.
Several people found the idea independently. Hugo Steinhaus sketched it in 1956, Lloyd built the standard algorithm the next year for pulse-code modulation, Edward Forgy published essentially the same method in 1965, and James MacQueen coined the name k-means in 1967. Early uses were in signal processing and compression, representing analogue signals with a small set of discrete values. As computers grew faster, its simplicity made it a staple of pattern recognition and early machine learning.
The standard algorithm alternates two steps. In the assignment step every point joins its nearest centroid; in the update step each centroid is recalculated as the mean of its members. Each round can only lower the total squared distance, so the process always settles, but not necessarily on the best answer. Results depend on the starting centres, which may be picked as random data points or by randomly labelling everything first. Because the method is usually fast, it is common to run it several times from different starts.
Finding the truly optimal clustering is computationally hard, even with only two clusters in general spaces. The method also struggles with clusters that are not roughly round and tends to produce groups of similar size. That has inspired variants such as fuzzy c-means, where points can belong partly to several clusters, and kernel k-means for curved boundaries. It is often confused with k-nearest neighbours, a quite different supervised classifier.
Source: K-means clustering
