When was the k-means clustering algorithm first used? K-means is probably one of the most used algorithms for clustering. I was looking for bibliography for its first use, but it has been around a lot, so what's the first one?  Also, when was the algorithm first named "k-means"?  
 A: To the best of my knowledge, the name 
'k-means' was first used in MacQueen (1967). The name refers to the improved algorithm proposed in that paper and not to the original one. Section 3 of that paper contains an application 
(which is missing from earlier papers such as Steinhaus (1956)). 


*

*J. MacQueen (1967). Some methods for classification and analysis of multivariate observations. Proc. Fifth Berkeley Symp. on Math. Statist. and Prob., Vol. 1 (Univ. of Calif. Press, 1967), 281--297.

*Steinhaus (1956). Sur la division des corps mat ́eriels en parties.
Bulletin de l’Académie Polonaise des Sciences, Classe III, vol. IV, no. 12, 801-804.

A: I have recently reproduced a version of Hugo Steinhaus paper: Sur la division des corps matériels en parties (On the division of material bodies into parts). The conclusion (originally in French) is (somehow):

Diverse questions, for instance those about types in anthropology, or
  others with practical motivations, like those of industrial object
  normalization, require a solution based on the determination of $n$ 
  fictitious representatives  of a numerous population, chosen so as to
  minimize as much as possible the deviations between population
  elements  and those from the sample. The deviation is mesured between
  every actual element and the closest fictitious element.

I can only guess that it was used at least a such closely thereafter, but the history did not keep track. In his paper, H. Steinhaus uses $A_i$ to name centroids (means), and $K_i$ refers to each of the $n$ sub-bodies (possibly from German Körper, the letter $K$ for fields being in use in mathematics since R. Dedekind).
MacQueen's 1967 paper motivated the name:

The $k$-means concept represents a generalization of the ordinary
  sample mean, and one is naturally led to study the pertinent
  asymptotic behavior, the object being to establish some sort of law of
  large numbers for the $k$-means.

A: Another early paper showing K-Means clustering was published by Ball and Hall in 1965 [1].  A K-Means like algorithm was part of their ISODATA algorithm. They went further to implement an iterative cluster split/merge phase in order to arrive at a "best" number of clusters.  Pure K-Means takes the number of centroids as a given.
[1] Ball, G.H. and Hall, D.J. (1965) "ISODATA, a Novel Method of Data Analysis and Pattern Classification." Stanford Research Institute, Menlo Park
