# Repeating k-means, is it helpful?

I'm working with k-means algorithm, and I'm proceeding in this way:

1. I've run k-means from 2 to n clusters, I plotted the k-means result of the variance, to get the "elbow", to decide the best trade-off between model and number of clusters, the best result is 4;
2. I repeated k-means n times, let's say 20,000 times, each time with 4 clusters;
3. I've stored all the coordinates of the centroids calculated;
4. I've calculated the mean coordinates of each centroids, that is a mean based on all the 20,000 iteration;
5. With the new centroids, I calculated for each point in my dateset the smallest euclidean distance, to get the "best" centroids for each point.

The problem is that I got my points distributed in only 3 centroids, i.e. the fourth is not given to anyone. This is in contrast also with the point 1, but if I decided to have 5,6, etc. cluster, there is always an cluster not used.

I know that this mean that a centroids is too much away from my points, but is it correct? And my procedure, is it meaningful? Should I calculate the variance to see the goodness of fit of the model?

• How did you take average of cluster centers for different iterations? May 29, 2019 at 18:31
• @gunes I got for each iteration a matrix of n×m (n centers, m coords on the variables), by k iteration: the average is by the nth×mth through the k repetitions (sum nth×mth / card k).
– s__
May 29, 2019 at 19:09

Based on your comment, I see that you just take the average of, let's say cluster 1 centers, to come up with the mean of cluster 1 center, i.e. $$\bar{C_{1}}=\frac{1}{n}\sum_{n=1}^{20K} C_{1}^{(i)}$$ which makes your analysis invalid if I'm not missing anything because, even if the k-means algorithm assigns the exact same clusters to your data (i.e. exactly same means), they may come in different order. So, cluster numberings don't possess a specific ordering, which in turn means that their average doesn't make much sense.

There are methods for computing cluster similarities using comembership measures as in cluster_similarity, however even if you get an aligned ordering for iterations $$i$$ and $$j$$, they might differ in subsequent iterations. I can't seem to find a straightforward way to mean these cluster centers. Typically, the best one is chosen.

• That's a valid point (+1). How would you manage that? Is it possible to fix and give the same order or validate the kmeans in other ways? Or is it not necessary?
– s__
May 29, 2019 at 19:28

Apart from the value of k, K-means algorithm is sensitive to initial conditions. You could run the algorithm several times having the same value of k and then put each instance in a unique cluster using a consensus function. This procedure is called Ensemble Clustering and you can find many papers published about it.

Taking the average of cluster centers is a bad idea.

Not only do the cluster numbers change, the average of two local options is simply not necessarily a local optimum (nor a better). If you do many tests with the same k, choose the best result, not the average.