In 2002, Jon Kleinberg published a result that fundamentally altered how we view unsupervised learning. In An Impossibility Theorem for Clustering, he proved that three intuitive properties we expect from any "perfect" clustering algorithm are mathematically incompatible. This discovery transformed clustering from a search for the "best" algorithm into a study of fundamental trade-offs.
The Three Intuitive Pillars
To understand the impossibility, we must first define the three axioms Kleinberg proposed as the minimum requirements for a clustering function:
- Scale-Invariance: If you measure your data in inches instead of centimeters, the resulting clusters shouldn't change. The algorithm should care about the relative geometry, not the absolute units.
- Richness: The algorithm should be capable of producing any possible partition of the data. If a user provides a specific distance matrix, there should be some configuration that allows the algorithm to output any desired grouping.
- Consistency: This is the most subtle axiom. If you "strengthen" a clustering—by shrinking distances between points in the same cluster or expanding distances between points in different clusters—the algorithm should return the same result.
Intuitively, these seem like "must-have" features. However, Kleinberg demonstrated that any algorithm satisfying Scale-Invariance and Consistency is restricted to a very narrow set of outputs (an "antichain" of partitions), making it impossible to satisfy Richness.
Why Consistency is the Culprit
The friction primarily arises from Consistency. While it sounds reasonable that "making a cluster tighter shouldn't break it," this property forces the algorithm to ignore the global context of the dataset.
As Shai Ben-David points out in Clustering - What Both Theoreticians and Practitioners Are Doing Wrong, the core issue is that similarity is not transitive, but cluster membership is. If point A is similar to B, and B is similar to C, it doesn't mean A is similar to C. Yet, in a cluster, they must all share the same label. Consistency effectively locks an algorithm into a specific way of resolving this non-transitivity, preventing it from being "rich" enough to adapt to all possible data structures.
Paths to Redemption
Since the impossibility result, researchers have sought "redemption" by relaxing or refining these axioms to better match practical needs.
- Fixing the Number of Clusters: Reza Bosagh Zadeh and Reza Zadeh showed in A Uniqueness Theorem for Clustering that if you fix the number of clusters ($k$) and introduce a property called "MST-Coherence," Single-Linkage clustering emerges as the unique, optimal solution.
- Refining Consistency: In Clustering Redemption-Beyond the Impossibility of Kleinberg's Axioms, Vincent Cohen-Addad, Varun Kanade, and Frederik Mallmann-Trenn argue that the original consistency axiom is too rigid because it doesn't allow the "natural" number of clusters to change. By refining this axiom, they prove that popular methods like $k$-means actually satisfy a more realistic set of properties.
- Topological Perspectives: Fabio Strazzeri and Ruben Sanchez-Garcia proposed Monotonic Consistency in Possibility results for graph clustering: A novel consistency axiom. They demonstrated that a topology-inspired method called Morse Clustering can satisfy this new axiom alongside richness and scale-invariance.
Moving Beyond Axioms
Other researchers have moved away from static axioms toward more dynamic frameworks. Gunnar E. Carlsson and Facundo Mémoli applied category theory in Classifying Clustering Schemes, arguing that clustering should be "functorial"—meaning it should behave predictably under data transformations.
Perhaps the most radical departure is the "Meta-Unsupervised Learning" approach by Adam Tauman Kalai and Vikas Garg. In Supervising Unsupervised Learning, they suggest that instead of arguing over axioms, we can use a repository of labeled datasets to "teach" an algorithm how to cluster new data. By treating clustering as a supervised task at the meta-level, they bypass the theoretical deadlock of the impossibility theorem entirely.
Ultimately, the "impossibility" of clustering is not a failure of the field, but a clarification of it. It teaches us that because no algorithm can be everything to everyone, the choice of a clustering method must be a deliberate decision about which mathematical properties matter most for a specific domain.