K-Means: The Forgotten Algorithm That Clusters Everything
K-means was published in an IBM report that almost no one read for 20 years.
James MacQueen presented what he called "k-means" at a 1967 Berkeley statistics symposium. The algorithm was simple: assign each data point to the nearest of K cluster centres, update the cluster centres to be the mean of their assigned points, repeat until nothing changes. The name followed directly from the mechanics: K clusters, defined by their means. MacQueen proved convergence. He filed no patent. He published in conference proceedings that almost nobody read.
The same core idea had been discovered independently multiple times. Hugo Steinhaus described a similar method in 1956. Stuart Lloyd at Bell Labs developed an equivalent algorithm in 1957 for pulse-code modulation, it circulated as an internal technical report and wasn't published until 1982. Forgy published a version in 1965. K-means is one of science's great cases of parallel independent discovery, where the same elegant idea occurred to several people without coordination.
The algorithm's simplicity hid a profound limitation: it requires you to specify K in advance. How many clusters are in your data? You have to guess, or try different values of K and evaluate. And k-means finds local optima, not global ones. Different random initialisations can produce different results. David Arthur and Sergei Vassilvitskii addressed the initialisation problem in 2007 with K-Means++, which seeds the initial centres to be spread out, significantly improving both speed and result quality.
Despite its limitations, k-means remains one of the most widely used algorithms in data science, four decades after MacQueen's forgotten conference paper. It clusters customer segments, compresses images through vector quantisation, groups documents, identifies cell types in genomics data, and segments satellite imagery. The computational efficiency, O(nKd) per iteration, makes it usable at any scale, which more sophisticated methods often can't match.
K-means is also, in a sense, the progenitor of a key step in modern LLMs. Vector quantisation, using k-means to map continuous embeddings to a finite codebook, was central to early image generation and audio synthesis. VQ-VAE and its descendants built on the same principle MacQueen described at Berkeley in 1967. The forgotten algorithm in the IBM report found its way into systems MacQueen couldn't have imagined, doing things nobody in 1967 would have called clustering.
What it actually meant
K-means was independently discovered four times because it is the natural answer to the question of how to group similar things. Its ubiquity is not marketing. It is convergence on the simplest correct solution to a fundamental problem. Simple algorithms that solve fundamental problems survive not by force but by fitness.
What enterprises get wrong today
Data science teams run k-means with a default K, never evaluate whether the clusters mean anything, and ship segment definitions into dashboards nobody questions. Customer segments created by an algorithm, used in presentations, and never validated against actual behaviour differences are not insights. They are artefacts.
Related capabilities
More from Algorithms
Ask about this story
K-means was published in conference proceedings that almost nobody read for 20 years. The same idea was independently discovered at least four times. And yet it's still one of the most used algorithms in data science. What would you like to explore?