I'm playing with the K-Means clustering (Documents Clustering) but i realised that the partitions are changing with each execution because the initial nodes are taken by the kmean++ algorithm. I would like to know if there is some method to find the "Average" partitioning scheme. I mean, after 100 executions, take the 100 observations, and calculate the average partitioning scheme.

Is there some method to do this?


First of all, there is a big definition question about what is an average partitioning scheme. Nevertheless,

I guess, there are two possible intentions for this question:

  1. Improve the quality of the partitioning that the kmeans++ provides by using $N$ runs with different initial and intermediate seeds.
  2. Have reproducible (at least on one machine) result.

If the latter is the concern, fixing the seed of the random number generator that is being used by your (or library) implementation should do the trick. You'll get the same result every run.

For a real kmeans problem, it will be hard to know if you ended up with an optimal solution (as you are still finding local minima as opposed to global ones; however, kmeans++ improves the approximation to $\mathcal O (\log k)$.

So, finding the average of the obtained results for multiple runs means that you are trying to find an average of local minimums, which I don't think can contribute in any way to improving the quality of the partitioning.

In this question, they discuss how we can compare the partitionings obtained from several kmeans runs. But this is in no way an average.

In summary, it is very common to launch such heuristics with different starting criteria to obtain a better result, I do not see why one might want to calculate the average, no matter what that means. However, one might want to see how the obtained solutions differ from each other with each run and what kind of error do they provide.


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.