1
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ How did you take average of cluster centers for different iterations? $\endgroup$ – gunes May 29 '19 at 18:31
  • $\begingroup$ @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). $\endgroup$ – s__ May 29 '19 at 19:09
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$ – s__ May 29 '19 at 19:28
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$

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.