How random are the results of the kmeans algorithm?

I have a question regarding the kmeans algorithm. I know kmeans is a randomized algorithm, but how random is it and what results can I expect. Suppose you have clustered a dataset into $4$ clusters, where each point has identity $1$, $2$, $3$, or $4$ (which tells you what cluster it belongs to). You then perform a second clustering on the same dataset with the same criteria.

1. Will all the points in a specific cluster say during the first clustering be in the same cluster the next time you apply the kmeans algorithm?
2. If not, will they most likely be in the same cluster and is there some measure for this likelihood?

By some output I received in R, I believe that 1. does not hold as I get different cluster sizes for different runs on the same dataset.

All help is greatly appreciated!

There is more than one k-means algorithm.

You probably refer to Lloyds algorithm, which only depends on the initial cluster centers. But there also is MacQueen's, which depends on the sequence i.e. ordering of points. Then there is Hartigan, Wong, Forgy, ...

And of course, various implementations may have implementation and optimization differences. They may treat ties differently, too! For example, many naive implementations will always assign elements to the first or last cluster when tied. Others will preserve the current clustering assignment. So when clustering integer values, where ties are much more common, but also on the Iris data set, you may see artifacts and differences caused by this.

Furthermore, the clusters may end up being reordered by memory address after finishing k-means, so you cannot safely assume that cluster 1 remains cluster 1 even if k-means converged after the first iteration. Others will reorder clusters by cluster size (which actually makes sense for k-means, as this will more likely return the same result on different random initialization)

But assuming that all iterate Lloyd until convergence (which original MacQueen k-means didn't!) they should all at least arrive at a local optimum. There will be only oh-so-many local optima...

Consider for example the data set generated by $p_j=(\sin(2\pi \frac{j}{n}), \cos(2\pi \frac{j}{n}))$, and let $n$ be divisible by $j$. There will be a lot of local optimal solutions. Running k-means with different random seeds will indeed give your very different solutions. For appropriate parameters, I believe the chance of two different elements that were in the same cluster to be in the same cluster again in another result will be somewhere around $50\%$. In higher dimensionality, you can probably further reduce this number. For example in the $n$ dimensional data set where $p_{jj}=1$ and $p_{ij}=0$ for $i\neq j$, all points are equidistant. It's easy to see that this will cause havoc to k-means...

• +1 nicely explained. Concerning your 50% estimate: the chance varies with $i-j \mod n$ and with $k$. For $i = j+1 \mod n$ and $k\gt 1$, that chance will be $1-k/n$ rather than $50$%. For larger distances between $p_i$ and $p_j$ the chance can depend (strongly) on the algorithm. – whuber May 6 '13 at 13:07

K-means is only randomized in its starting centers. Once the initial candidate centers are determined, it is deterministic after that point. Depending on your implementation of kmeans the centers can be chosen the same each time, similar each time, or completely random each time. With MATLAB/R implementations, the choice is random but the result you get is the best run from among 50 or so sets of choices for initial centers. Note with the R stats::kmeans function, the default is to only run one set of initial centers (i.e., nstart = 1). Depending on your data, increasing this value may stabilize cluster assignments across runs and doing so is generally recommended.

To answer your first question, it really depends on what kind of data you have. If it is nicely split into spherical-shaped clusters then you will typically get very very similar clusters. If not, then you might get pretty random clusters each time.

There is no general measure for "likelihood" of being in the same cluster, but if you need one you can come up with one based on any instance's similarity/distance to the others compared to their similarity/distance to other points. Or perhaps you could run a linkage (single or complete) algorithm first and then weigh their "likelihood" of being in the same cluster by their distances to the lowest common ancestor. Or there are a number of other was you could do it depending on what your data looks like and what the application is.