Stability of-Means Clustering

Shai Ben-David, Dávid Pál, Hans Ulrich SimonCOLT 2007 · OpenReview

Abstract

We consider the stability of k-means clustering problems. Clustering stability is a common heuristics used to determine the number of clusters in a wide variety of clustering applications. We continue the theoretical analysis of clustering stability by establishing a complete characterization of clustering stability in terms of the number of optimal solutions to the clustering optimization problem. Our results complement earlier work of Ben-David, von Luxburg and Pál, by settling the main problem left open there. Our analysis shows that, for probability distributions with finite support, the stability of k-means clusterings depends solely on the number of optimal solutions to the underlying optimization problem for the data distribution. These results challenge the common belief and practice that view stability as an indicator of the validity, or meaningfulness, of the choice of a clustering algorithm and number of clusters.
BibTeX
@inproceedings{bendavid2007stability,
  author = {Shai Ben-David and Dávid Pál and Hans Ulrich Simon},
  title = {{Stability of-Means Clustering}},
  booktitle = {Conference on Learning Theory},
  year = {2007},
  url = {https://openreview.net/forum?id=dXlrek0xsr},
}

Loading related content...

Figure