Source-linked AI summary
A Uniqueness Theorem for Clustering
Reza Bosagh Zadeh, Shai Ben-David
TL;DR
Clustering is widely used, but general principles for distinguishing and choosing among clustering paradigms remain limited. The paper develops an axiomatic framework by restricting attention to algorithms that take the number of clusters as input, then characterizes Single-Linkage through abstract properties. It also proposes a taxonomy of clustering functions and identifies future work on characterizing other functions.
Problem
General principles for comparing clustering paradigms and guiding algorithm choice have received little research despite clustering’s broad use.
Source: §1 · p. 1Method
The paper adapts Kleinberg’s axiomatic framework by restricting clustering functions to those taking the number of clusters as input, then studies additional abstract properties.
Source: §1 · pp. 1–2Results
Takeaways & Limitations
The proposed properties support a taxonomy intended to guide users toward clustering functions suited to their applications.
Source: §1 · p. 1, §4 · p. 8The paper leaves characterization of other clustering functions, including Min-Sum k-clustering, for future work.
Source: §4 · p. 8
Abstract
from arXiv · showhide
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.
1 Introduction
Clustering is widely used but remains ill-defined, with little work on general principles for comparing paradigms or guiding their choice. The paper adopts an axiomatic framework and characterizes Single-Linkage through properties tied to minimum spanning trees and path distances.
1 Introduction
- The paper addresses a gap in general principles for comparing clustering paradigms and guiding users’ choices among them.It seeks to reason independently of particular algorithms, objective functions, and generative models.Source: §1 · p. 1
More related work
- Restricting clustering functions to take k as input relaxes Kleinberg’s framework and yields a consistent set of axioms that common algorithms, including Single-Linkage and Min-Sum k-clustering, satisfy.The paper also notes that Jardine and Sibson’s related uniqueness result is limited to hierarchical functions and uses an implicit Single-Linkage optimization criterion; the present properties do not.Source: §1 · pp. 1–2, More related work · p. 3
Formal Preliminaries
- For a weighted graph, Single-Linkage obtains its k-partition by computing a minimum spanning tree and cutting its k −1 most expensive edges.The paper states that the MST contains all information needed to compute the graph’s Single-Linkage k-partitioning.Source: §1 · p. 2
1 Introduction
- Single-Linkage is characterized as the only clustering function satisfying the stated axioms together with path-distance coherence.Path-distance coherence requires the same clustering whenever two distance measures induce the same path distances.Source: §1 · p. 2
- The paper presents path-distance coherence as useful when small-distance substitutions may represent shared ancestry, citing DNA sequences and repeatedly copied folklore documents as examples.In this setting, it recommends Single-Linkage as the clustering choice.Source: §1 · p. 2
2 Uniqueness Theorem
The section characterizes Single-Linkage using consistency, k-richness, MST-coherence, and order-consistency. Among the minimum-spanning-tree-cut functions, Single-Linkage is the only consistent member.
2 Uniqueness Theorem
- Consistency preserves a partition when within-cluster distances shrink and between-cluster distances expand; order-consistency requires the output to depend on edge ordering.Order-consistency implies scale-invariance, so the paper does not list scale-invariance separately alongside it.Source: §2 · pp. 3–4
- Table 1 summarizes which discussed partitioning functions satisfy the properties; only Single-Linkage can have a check in every column.This follows from the uniqueness theorem.Source: Table 1 · p. 5, MST-Coherence and the MST Cuts family · p. 6
MST-Coherence and the MST Cuts family
- MST-coherence requires identical weighted minimum spanning trees to produce the same partition, thereby excluding dependence on redundant edges.The proof transforms an input while preserving its output, using consistency, edge reordering, and MST-coherence before matching the original edge ordering.Source: MST-Coherence and the MST Cuts family · pp. 5–7
- MST Cuts functions compute a minimum spanning tree and cut k −1 edges selected by their positions in the tree’s edge ordering.Cutting the k −1 most expensive edges gives Single-Linkage; the family varies which positions are cut.Source: MST-Coherence and the MST Cuts family · p. 5
- Consistency is necessary within MST Cuts: the family is MST-coherent, k-rich, and order-consistent, but only Single-Linkage is consistent.The theorem also identifies k-richness as necessary to characterize Single-Linkage.Source: MST-Coherence and the MST Cuts family · pp. 5–6
- The Constant function shows k-richness is necessary: it ignores distances and cannot produce k-partitions without singleton clusters.It is nevertheless MST-coherent, consistent, and order-consistent.Source: MST-Coherence and the MST Cuts family · p. 6
- Single-Linkage is the unique partitioning function satisfying consistency, k-richness, MST-coherence, and order-consistency.The characterization holds for partitioning functions with a fixed number of clusters k.Source: §2 · p. 4, MST-Coherence and the MST Cuts family · p. 6
3 Building a taxonomy of clustering functions
The section examines which axioms Min-Sum k-clustering satisfies and uses a constructed example to show where it differs from Single-Linkage’s properties.
3 Building a taxonomy of clustering functions
- The analysis focuses on the Min-Sum k-clustering objective itself, leaving variations of that objective for future work.Source: §3 · p. 7
- Min-Sum k-clustering is Consistent, k-Rich, and Scale-invariant, but neither Order-Consistent nor MST-Coherent.Source: §3 · p. 7
- Consistency follows because, for fixed k, the set of k-partitionings forms an anti-chain; scale invariance follows from the objective’s invariance to linear scaling.For k-Richness, setting within-cluster distances to 1 and between-cluster distances to 2 suffices to obtain the target partition.Source: §3 · pp. 7–8
- For sufficiently large even n, Min-Sum returns {A, B} on the constructed two-part dataset, but raising its largest edge above 3n separates its endpoints and changes the partition.The edge increase is both an Order-Consistent and an MST-Coherent transformation, so the changed output violates both properties.Source: §3 · p. 8
4 Conclusions & future directions
The conclusion proposes an axiomatic taxonomy to guide clustering-method choice and presents a consistent axiomatic basis that characterizes Single-Linkage. It leaves characterizing other clustering functions as future work.
4 Conclusions & future directions
- The proposed taxonomy aims to use prior domain knowledge to help users choose a clustering method suited to a task.Source: §4 · p. 8
- Under a consistent axiomatic basis, the paper gives properties that characterize Single-Linkage and connect it to Minimum Spanning Trees.Source: §4 · p. 8
- In the proposed taxonomy, Single-Linkage is the only Consistent member of the Minimum Spanning Tree Cuts family; the uniqueness result follows from ignoring redundant edges.Source: §4 · p. 8
- Characterizing other clustering functions, including Min-Sum k-clustering, remains future work.Source: §4 · p. 8