ML Anthology

The Uniqueness of a Good Optimum for K-Means

Marina Meila
ICML 2006 pp. 625-632
doi:10.1145/1143844.1143923 /icml/2006/meila2006icml-uniqueness/

Abstract

If we have found a "good" clustering C of a data set, can we prove that C is not far from the (unknown) best clustering C opt of these data?Perhaps surprisingly, the answer to this question is sometimes yes. When "goodness" is measured by the distortion of K-means clustering, this paper proves spectral bounds on the distance d(C, C opt ).The bounds exist in the case when the data admits a low distortion clustering.

PDF ICML Semantic Scholar

Cite

Text

Meila. "The Uniqueness of a Good Optimum for K-Means." International Conference on Machine Learning, 2006. doi:10.1145/1143844.1143923

Markdown

[Meila. "The Uniqueness of a Good Optimum for K-Means." International Conference on Machine Learning, 2006.](https://mlanthology.org/icml/2006/meila2006icml-uniqueness/) doi:10.1145/1143844.1143923

BibTeX

@inproceedings{meila2006icml-uniqueness,
  title     = {{The Uniqueness of a Good Optimum for K-Means}},
  author    = {Meila, Marina},
  booktitle = {International Conference on Machine Learning},
  year      = {2006},
  pages     = {625-632},
  doi       = {10.1145/1143844.1143923},
  url       = {https://mlanthology.org/icml/2006/meila2006icml-uniqueness/}
}