Stability of K -Means Clustering
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.
Cite
Text
Ben-David et al. "Stability of K -Means Clustering." Annual Conference on Computational Learning Theory, 2007. doi:10.1007/978-3-540-72927-3_4Markdown
[Ben-David et al. "Stability of K -Means Clustering." Annual Conference on Computational Learning Theory, 2007.](https://mlanthology.org/colt/2007/bendavid2007colt-stability/) doi:10.1007/978-3-540-72927-3_4BibTeX
@inproceedings{bendavid2007colt-stability,
title = {{Stability of K -Means Clustering}},
author = {Ben-David, Shai and Pál, Dávid and Simon, Hans Ulrich},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2007},
pages = {20-34},
doi = {10.1007/978-3-540-72927-3_4},
url = {https://mlanthology.org/colt/2007/bendavid2007colt-stability/}
}