A Uniqueness Theorem for Clustering

Reza Bosagh Zadeh, Shai Ben-David
Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, PMLR R7:639-646, 2009.

Abstract

Despite the widespread use of Clustering, there is distressingly little general theory of clustering available. Questions like "What distinguishes a clustering of data from other data partitioning?", "Are there any principles governing all clustering paradigms?", "How should a user choose an appropriate clustering algorithm for a particular task?", etc. are almost completely unanswered by the existing body of clustering literature. We consider an axiomatic approach to the theory of Clustering. We adopt the framework of Kleinberg, [Kle03]. By relaxing one of Kleinberg’s clustering axioms, we sidestep his impossibility result and arrive at a consistent set of axioms. We suggest to extend these axioms, aiming to provide an axiomatic taxonomy of clustering paradigms. Such a taxonomy should provide users some guidance concerning the choice of the appropriate clustering paradigm for a given task. The main result of this paper is a set of abstract properties that characterize the Single-Linkage clustering function. This characterization result provides new insight into the properties of desired data groupings that make Single-Linkage the appropriate choice. We conclude by considering a taxonomy of clustering functions based on abstract properties that each satisfies.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR7-zadeh09a, title = {A Uniqueness Theorem for Clustering}, author = {Zadeh, Reza Bosagh and Ben-David, Shai}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {639--646}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/zadeh09a/zadeh09a.pdf}, url = {https://proceedings.mlr.press/r7/zadeh09a.html}, abstract = {Despite the widespread use of Clustering, there is distressingly little general theory of clustering available. Questions like "What distinguishes a clustering of data from other data partitioning?", "Are there any principles governing all clustering paradigms?", "How should a user choose an appropriate clustering algorithm for a particular task?", etc. are almost completely unanswered by the existing body of clustering literature. We consider an axiomatic approach to the theory of Clustering. We adopt the framework of Kleinberg, [Kle03]. By relaxing one of Kleinberg’s clustering axioms, we sidestep his impossibility result and arrive at a consistent set of axioms. We suggest to extend these axioms, aiming to provide an axiomatic taxonomy of clustering paradigms. Such a taxonomy should provide users some guidance concerning the choice of the appropriate clustering paradigm for a given task. The main result of this paper is a set of abstract properties that characterize the Single-Linkage clustering function. This characterization result provides new insight into the properties of desired data groupings that make Single-Linkage the appropriate choice. We conclude by considering a taxonomy of clustering functions based on abstract properties that each satisfies.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T A Uniqueness Theorem for Clustering %A Reza Bosagh Zadeh %A Shai Ben-David %B Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2009 %E Jeff Bilmes %E Andrew Y. Ng %F pmlr-vR7-zadeh09a %I PMLR %P 639--646 %U https://proceedings.mlr.press/r7/zadeh09a.html %V R7 %X Despite the widespread use of Clustering, there is distressingly little general theory of clustering available. Questions like "What distinguishes a clustering of data from other data partitioning?", "Are there any principles governing all clustering paradigms?", "How should a user choose an appropriate clustering algorithm for a particular task?", etc. are almost completely unanswered by the existing body of clustering literature. We consider an axiomatic approach to the theory of Clustering. We adopt the framework of Kleinberg, [Kle03]. By relaxing one of Kleinberg’s clustering axioms, we sidestep his impossibility result and arrive at a consistent set of axioms. We suggest to extend these axioms, aiming to provide an axiomatic taxonomy of clustering paradigms. Such a taxonomy should provide users some guidance concerning the choice of the appropriate clustering paradigm for a given task. The main result of this paper is a set of abstract properties that characterize the Single-Linkage clustering function. This characterization result provides new insight into the properties of desired data groupings that make Single-Linkage the appropriate choice. We conclude by considering a taxonomy of clustering functions based on abstract properties that each satisfies. %Z Reissued by PMLR on 04 October 2026.
APA
Zadeh, R.B. & Ben-David, S.. (2009). A Uniqueness Theorem for Clustering. Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R7:639-646 Available from https://proceedings.mlr.press/r7/zadeh09a.html. Reissued by PMLR on 04 October 2026.

Related Material