2
$\begingroup$

In matlab and python, when running k-means, it is possible to set several repetitions (with random init) so that all of them in the end are combined to have stable global result? I am wondering how these several outputs are combined? If they have different inits then it can happen that the corresponding cluster labels between different runs are different. How are they combined, then?

$\endgroup$
  • $\begingroup$ What do you mean by "stable global result?" The only information you could get by combining clusters is the overall "distribution" of centroids for a given group. By definition however, making any switch for a given centroid assignment will make the assignment worse for a given solution to k-means $\endgroup$ – Alex R. Oct 22 '15 at 21:12
  • $\begingroup$ By this I mean converging to the global maximum instead of local one that could be the case for the stand-alone k-means. $\endgroup$ – fractile Oct 22 '15 at 21:27
  • $\begingroup$ It's not so easy to converge to the global maximum. The optimization is nonlinear, and sampling twice with the usual random algorithm will in no way "converge" to the global min. The state space grows exponentially: when you have $g$ groups and $k$ clusters, there are $g^k$ possible assignments. $\endgroup$ – Alex R. Oct 22 '15 at 22:38
  • $\begingroup$ Thanks for the explanation. Ok, lets not use "global maximum" for this. But my main question was how do they combine the clustering results? $\endgroup$ – fractile Oct 23 '15 at 9:33
3
$\begingroup$

This is an optimization problem, so the way they are combined is simply to pick the one with the best result. For k-means it would be the minimum total sum of squares of points to the centroids of their assigned cluster. This is true in MATLAB, and I suspect also for Python or anything else.

$\endgroup$
2
$\begingroup$

As Alex R. said, k-means in general is an NP-hard problem. So combining polynomially many clusterings in any way cannot give you the globally optimal solution. However, good approximate solutions can be obtained via good initializations, see e.g. k-means++ or this paper for a summary of various methods.

Regarding k-means in particular, you may find what you want via Genetic k-means, which does has a crossover function that can combine two clusterings, but I would not recommend this approach. Genetic algorithms are zero-order optimization methods (i.e. they don't use the gradient information) and are probably overkill for such a problem where the objective function is explicitly known. You'd be better off doing multiple restarts and "combining" them by picking the one with the best objective value.

If you want to combine clusterings in general to improve them, this qualifies as a research problem which hasn't been explored in detail. You'd need to look at research papers, for example Li et al 2009, Lu et al 2008 or Topchy et al 2003

$\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.