An Impossibility Theorem for Clustering
Abstract
Although the study of clustering is centered around an intuitively compelling goal, it has been very di(cid:14)cult to develop a uni(cid:12)ed framework for reasoning about it at a technical level, and pro- foundly diverse approaches to clustering abound in the research community. Here we suggest a formal perspective on the di(cid:14)culty in (cid:12)nding such a uni(cid:12)cation, in the form of an impossibility theo- rem: for a set of three simple properties, we show that there is no clustering function satisfying all three. Relaxations of these prop- erties expose some of the interesting (and unavoidable) trade-o(cid:11)s at work in well-studied clustering techniques such as single-linkage, sum-of-pairs, k-means, and k-median.
Cite
Text
Kleinberg. "An Impossibility Theorem for Clustering." Neural Information Processing Systems, 2002.Markdown
[Kleinberg. "An Impossibility Theorem for Clustering." Neural Information Processing Systems, 2002.](https://mlanthology.org/neurips/2002/kleinberg2002neurips-impossibility/)BibTeX
@inproceedings{kleinberg2002neurips-impossibility,
title = {{An Impossibility Theorem for Clustering}},
author = {Kleinberg, Jon M.},
booktitle = {Neural Information Processing Systems},
year = {2002},
pages = {463-470},
url = {https://mlanthology.org/neurips/2002/kleinberg2002neurips-impossibility/}
}