# Why not terminating the k-means clustering algorithm after one iteration?

Does anybody know whether there are applications of the k-means algorithm with only one iteration? (Of course, you may feel inclined to not call it k-means anymore in that case.)

There is a clear motivation for stopping after one iteration: the centroids of the clusters are easily interpretable, because you can choose them in a way that they are easily interpretable.

There are clear caveats as well: the resulting cluster centroids, which are the values you have chosen initially (the "seeds"), won't have the property that they are the geometrical centers of the clusters. Relatedly, the results may be bad with regard to the "k-means objective function", which aims at placing centroids in the space such that the average distance of data points to their centroids is minimal.

I understand that for certain applications, the caveats are very severe. If I have $n$ cities (with equal populations) in the plane and I must decide where to put the $k < n$ rescue helicopter stations, I may want to place them in a way that the average distance between city and rescue helicopter station is minimal, so that the average time needed to fly to a patient is minimal too. Makes sense.

However, if it is just about data analysis, important competitors to k-means are the so-called hierarchical clustering procedures, which do not lead to clusterings that have any of the properties of k-means. In particular, a hierarchical clustering may lead to very bad values of the "k-means objective function" (assuming that in the hierarchically generated clusters one would define the centroids ex post as their geometric centers).

Hence, what is bad about taking the k-means clusters after the first iteration? Compared to hierarchical clustering, this has the advantages that (a) the clusters have centroids, yielding a nice way to interpret the clusters in terms of Euclidean distance, (b) one does not have to bother about the ratio of cluster variables, number of clusters, and data points, as the sample is partitioned regardless of those values, and each data point is uniquely assigned to one cluster. Does anybody know about practical studies where k-means was stopped after one iteration?

• Many implementations of K-means allow to set the number of iterations to whatever value wished. In SPSS terminology, for example, option "classify only" amounts to assigning every point to its closest initial centre (the latter whatever specified or entered); then the centres get updated and the process terminates. This is "0 iterations". While if you set "1 iteration" limit then the points will also be one time re-assigned to the new centres before the process terminates. – ttnphns Apr 17 '16 at 7:04
• Hierarchical Ward's method has the objective function which can be seen as the same as the k-Means': minimization of SSw. (But K-means is more efficient in respect of that function.) Often Ward and K-means are used in conjunction. For example, Ward produces clusters which centres are saved and used as initial for K-means. – ttnphns Apr 17 '16 at 7:15
• Thank you, ttnphns. Yes, with Stata we can also specify iterate(0) or (1) to stop the readjustment process. Thanks for mentioning that the iterate(0) option exists -- I was thinking about setting iterate(1), but then we will probably have TWO assignments to centroid,and one centroid readjustment, which is one too much. – Florian Apr 17 '16 at 7:34
• Does somebody know what STATA does excaclty when we specify iterate(1)? ttnphns suggested that with SPSS, one would set "0 iterations" to achieve what we want to do. Yet, with STATA it is impossible to set iterate(0). It requires a positive value. There are three possibilities what STATA might do with iterate(1): (1) Data points are assigned to the initial centroids, then centroids are adjusted, then it stops. (2) Data points are assigned to the initial centroids, centroids are adjusted, the assignment is changed again, (maybe) the centroids are adjusted again, then it stops. Does anyone know? – Florian Apr 18 '16 at 6:12
• Florian, dig it in the Stata documentation. If it doesn't help, try to figure out by experimenting or ask a specialized Stata user forum (see stats.stackexchange.com/tags/stata/info). – ttnphns Apr 18 '16 at 6:34

• Thank you, Anony-Mouse. What I suggest is not nearest neighbor classification. For nearest neighbor classification, we would assign a data point $a$ to a cluster $B$ if the majority of other datapoints in a neighborhood of given distance around $a$ are in cluster $B$. Nevertheless, thanks for this suggestion. It is always good to know what other procedures are around. You may be right about the terminology "half an iteration". As far as I know, the k-means procedure is not defined by the used metric. Whether you use L2, squared L2, or even some other metric, its all k-means. – Florian Apr 18 '16 at 6:04