3
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – ttnphns Apr 17 '16 at 7:04
  • 1
    $\begingroup$ 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. $\endgroup$ – ttnphns Apr 17 '16 at 7:15
  • $\begingroup$ 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. $\endgroup$ – Florian Apr 17 '16 at 7:34
  • $\begingroup$ 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? $\endgroup$ – Florian Apr 18 '16 at 6:12
  • 1
    $\begingroup$ 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). $\endgroup$ – ttnphns Apr 18 '16 at 6:34
2
$\begingroup$

What you are discussing sounds more like nearest neighbor classification to me, i.e. assign every point to the nearest "training" object. Essentially, you are describing classification, not clustering.

You appear to be doing only "half an iteration". A full iteration would also update the cluster centroids. The task of clustering is to discover structure in the data - in the case of k-means the structure are the centroids. In other algorithms it is usually the set of points that makes up the cluster.

Now to the "helipad" example. K-means does not minimize average distances. It minimizes the average squared distance. For a purely cost-driven approach that is worse, centroid-linkage is maybe better. For the helipad emergency it's better to have fewer extreme distance; but one may want to optimize the maximum instead. That is easier to formuate with hierarchial clustering, e.g. using minimax linkage. Furthermore, k-means may be placing the centers in the ocean, or in a lake... (this does not happen with minimax) if you had to connect all point with a point-to-point radio network, single-linkage is meaningful, because it is the minimum spanning tree. And Ward linkage optimizes squared deviations, just like k-means. This shows a key benefit of hierarchical clustering: it's flexibility. It allows both different objectives (linkages) and arbitrary distance functions (e.g. haversine distance). K-means does neither.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Florian Apr 18 '16 at 6:04
  • $\begingroup$ It sure is nearest-neighbor classification! The distance is not given, but the number of nearest neighbors to look at (here, it's 1). Majority when you only have 1 training example each can be ignored. Also, Google why k-(means) cannot be used with arbitrary metrics, it only converges for Bregman divergences. Try to prove some properties of k-means, and you'll quickly notice that the mean is an important aspect of k-means and not compatible with other distances. In particular, k-means does not minimize Euclidean distances, only squared Euclidean (=Variance). $\endgroup$ – Anony-Mousse Apr 18 '16 at 6:11
  • $\begingroup$ Nearest-neighbor classification can be used with arbitrary dissimilarities, or similarities. It does not require any special properties. $\endgroup$ – Anony-Mousse Apr 18 '16 at 6:12
  • $\begingroup$ The k-means algorithm is not restricted to use Euclidean distance as the distance metric, and surely not to (squared) Euclidean distance. See, for example, "K-means with Three different Distance Metrics", International Journal of Computer Applications 67, 2013. (research.ijcaonline.org/volume67/number10/pxc3886785.pdf) They write: "During the implementation of k-means with three different distance metrics, it is observed that selection of distance metric plays a very important role in clustering. So, the selection of distance metric should be made carefully." $\endgroup$ – Florian Apr 19 '16 at 15:04
  • $\begingroup$ You are right that the convergence properties of the algorithm when using different metrics are different and you may be right that for some metrics, it does not converge at all. This does not mean, however, that one must use the squared Euclidean distance when applying k-means. $\endgroup$ – Florian Apr 19 '16 at 15:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.