K-Means Clustering Algorithm

K-means clustering is an algorithm that partitions a set of data points into a chosen number of groups, or clusters, by assigning each point to whichever cluster's center, or centroid, is nearest to it and choosing centroids that minimize the total squared distance between points and their assigned cluster center. The standard algorithm alternates between two steps until the assignment stops changing: it assigns every point to its nearest current centroid, and it then recomputes each centroid as the average position of the points currently assigned to it. The underlying method was developed by Stuart Lloyd at Bell Labs in 1957 for a signal-processing application, though it was not published until 1982, and Edward Forgy independently proposed essentially the same procedure in 1965, so the algorithm is sometimes called the Lloyd-Forgy algorithm; the term k-means itself was introduced by James MacQueen in 1967. K-means is fast and widely used in practice, but as a heuristic it can converge to a local rather than a globally optimal grouping and requires the number of clusters to be chosen in advance.