A Uniqueness Theorem for Clustering

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 SingleLinkage the appropriate choice. We conclude by considering a taxonomy of clustering functions based on abstract properties that each satisfies.

Authors

• Reza Zadeh
• Shai Ben-David

Keywords

No keywords are indexed for this paper.