The -MEANS clustering algorithm implements the standard -MEANS algorithm, as detailed in Section 2 of . This takes an iterative improvement over an initial random clustering, which is provided by the above random clustering algorithm. Each iteration computes the representatives of the cluster as the mean of the points in the cluster, and then using these representatives computes a clustering, where each point is assigned to the cluster of its closest representative.
It runs in time, however, often doesn't produce good quality clusterings. It requires the desired number of clusters, , to be specified on the command line.