k-means clustering

What it is

k-means is a clustering method — more precisely, a vector quantisation method — that takes n observations and sorts them into k groups, sending each observation to the group whose mean is nearest to it ^[1]. The k in the name is the number of groups, and the algorithm does not choose it. Because each cluster is represented by a single mean, the method needs only a distance and an average, and squared Euclidean distance is the usual choice ^[1]. The resulting partition cuts the space into Voronoi cells, and the quantity the algorithm minimises is the within-cluster sum of squares ^[1]. The scikit-learn documentation describes the same goal in its own terms: separating samples into n groups of equal variance while minimising a criterion called inertia, which is the within-cluster sum of squares ^[2].

How it works

The algorithm alternates between two steps ^[1]. In the assignment step each observation is sent to the nearest centroid, measured by squared Euclidean distance. In the update step each centroid is recomputed as the mean of the observations currently assigned to it. Then the two steps repeat.

A small example makes the loop concrete. Suppose a set of points on a plane is to be split into 3 groups. Three starting centroids are chosen; every point joins whichever of the three is closest; each centroid then moves to the average position of the points now assigned to it. Because the averages have moved, some points may switch groups on the next pass, and the loop continues until the assignments settle. Every stage of this uses only distances and averages, nothing else.

Convergence follows from the objective itself: the within-cluster sum of squares decreases monotonically over the iterations ^[1]. The method also scales well to large numbers of samples ^[2].

Where it came from

Hugo Steinhaus proposed the idea in 1956 ^[1]. Stuart Lloyd developed the standard algorithm at Bell Labs in 1957, though it was published only in 1982, and that version is known as Lloyd's algorithm ^[1]. James MacQueen first used the term "k-means", in 1967 ^[1].

Where it appears today

One widely used implementation is KMeans in scikit-learn, whose documentation describes the method as separating samples into groups of equal variance while minimising inertia, and notes both that the number of clusters must be specified in advance and that the algorithm scales well to large numbers of samples ^[2]. In other words, k is left to the user, and what the user gets in return is a method that keeps working as the data grow ^[2].

Limits

The first limit is k itself: it must be chosen in advance, and a poor choice produces poor results ^[1]. The second is the starting point: the result is sensitive to the initial centroids and often converges to a local optimum rather than the global one, so the same data can end up partitioned differently ^[1]. The third is shape: the method assumes clusters that are roughly spherical and of similar size, and it is unsuitable for arbitrary distance measures or for non-numeric data ^[1]. k-means++ addresses the initialisation by spreading the initial centres apart, and it carries an O(log k) approximation guarantee ^[1].