A Uniqueness Theorem for Clustering

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.

Appears in Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence (UAI2009)

Cited by in corpus (18)

• Axioms for graph clustering quality functions
• A Mathematical Theory for Clustering in Metric Spaces
• Asymptotic nonparametric statistical analysis of stationary time series
• Clusters and water flows: a novel approach to modal clustering through Morse theory
• Clustering processes
• Incremental Clustering: The Case for Extra Clusters
• Hierarchical Clustering: Objective Functions and Algorithms
• Towards an Axiomatic Approach to Hierarchical Clustering of Measures
• Excisive Hierarchical Clustering Methods for Network Data
• Meta-Unsupervised-Learning: A supervised approach to unsupervised learning
• Towards Continuous Consistency Axiom
• FADO: A Deterministic Detection/Learning Algorithm
• Parallel Graph Algorithms in Constant Adaptive Rounds: Theory meets Practice
• Unsupervised Representation Learning with Minimax Distance Measures
• Characterizing Properties for Q-Clustering
• A Fixed point view: A Model-Based Clustering Framework
• Communities in Preference Networks: Refined Axioms and Beyond
• When is Clustering Perturbation Robust?