Unsupervised learning: clusters and anomalies

On 31 July 1957 a draft by Stuart Lloyd, a mathematician at Bell Laboratories, was logged by the lab's mathematics research department. It tackled a telephone-engineering problem: when a continuous signal is reduced to a limited set of levels for pulse-code modulation, where should the levels sit to keep the error smallest?

His answer was a loop. Assign every value to its nearest level, move each level to the centre of the values assigned to it, and repeat. The numerical work was never finished and the paper stayed unpublished for 25 years, until IEEE Transactions on Information Theory printed it in March 1982.

By then the loop had a name. James MacQueen had called a method of this kind k-means in 1967, and it had become the standard way to find groups in data that nobody has labelled.