Some methods for classification and analysis of multivariate observations

This paper describes a number of applications of the 'k-means', a procedure for classifying a random sample of points in E sub N. The procedure consists of starting with k groups which each consist of a single random point, and thereafter adding the points one after another to the group whose mean each point is nearest. After a point is added to a group, the mean of that group is adjusted so as to take account of the new point. Thus at each stage there are in fact k means, one for each group. After the sample is processed in this way, the points are classified on the basis of nearness to the final means. The portions which result tend to be fficient in the sense of having low within class variance. Applications are suggested for the problems of non-linear prediction, efficient communication, non-parametric tests of independence, similarity grouping, and automatic file construction. The extension of the methods to general metric spaces is indicated. (Author)