2
$\begingroup$

In this paper, a bound on the “error subspace” projection is established, which is then used to show that any two clusterings with small distortion are close. Which immediately follows that, if a good clustering, $C$, is discovered for a given dataset (say manually, or by whatever ssuitable means), then another clustering, $C_1$, is going to be close to the optimal clustering if it minimizes the distortion between the two clusterings.

The paper was presented as optimality for k-means. But I could not find any specific detail that stops it from being applicable to general clustering algorithms. That's why I want to confirm here by asking whether this method of determining existence of an optimal algorithmic clustering applicable to other algorithms beyond k-means.


Meilă, Marina. "The uniqueness of a good optimum for k-means." In Proceedings of the 23rd international conference on Machine learning, pp. 625-632. ACM, 2006.

$\endgroup$
  • $\begingroup$ Please give a complete reference (the title is a good start, but a little more information would be helpful). If for some reason the site you linked to goes down for a period of time the paper should still be easy to find. $\endgroup$ – Glen_b Jun 30 '17 at 9:56
  • $\begingroup$ The answer is yes. Look at her new paper papers.nips.cc/paper/… Maybe she read your question :) $\endgroup$ – Amir Jan 9 at 18:09
1
$\begingroup$

The distortion function they use is highly specific to k-means.

So in essence: if there exist a "good k-means clustering", then most k-means results will be close. If no good result exists (and this is the common case) then they will be much more different.

The takeaway is to try k-means several times. If the results are very different, then none of them is good.

While I do think similar results can exist for other clusterings, it doesn't directly apply to others. In some cases like DBSCAN, the result is (except for some corner cases with identical distances) exactly defined. There is no random initialization involved, and no optimization function to use as "distortion".

$\endgroup$
  • $\begingroup$ I see. How about agglomerative hierarchical clustering? $\endgroup$ – Kristada673 Jun 30 '17 at 19:44
  • $\begingroup$ Deterministic. And what is D? $\endgroup$ – Anony-Mousse Jun 30 '17 at 19:48
  • $\begingroup$ Yeah, "mu" doesn't exist for hierarchical, but i guess a different cost function can be thought of, no? $\endgroup$ – Kristada673 Jun 30 '17 at 19:52
  • $\begingroup$ It's not obvious what the general cost function is, nor if it has the properties required for their proof. $\endgroup$ – Anony-Mousse Jun 30 '17 at 20:17

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.