User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse




Conference Paper

Relating clustering stability to properties of cluster boundaries


von Luxburg,  U
Department Empirical Inference, Max Planck Institute for Biological Cybernetics, Max Planck Society;

There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available

Ben-David, S., & von Luxburg, U. (2008). Relating clustering stability to properties of cluster boundaries. Proceedings of the 21st Annual Conference on Learning Theory (COLT 2008), 379-390.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0013-C83F-8
In this paper, we investigate stability-based methods for cluster model selection, in particular to select the number K of clusters. The scenario under consideration is that clustering is performed by minimizing a certain clustering quality function, and that a unique global minimizer exists. On the one hand we show that stability can be upper bounded by certain properties of the optimal clustering, namely by the mass in a small tube around the cluster boundaries. On the other hand, we provide counterexamples which show that a reverse statement is not true in general. Finally, we give some examples and arguments why, from a theoretic point of view, using clustering stability in a high sample setting can be problematic. It can be seen that distribution-free guarantees bounding the difference between the finite sample stability and the “true stability” cannot exist, unless one makes strong assumptions on the underlying distribution.