Hierarchical clustering meets key fairness axioms that flat clustering cannot
Hierarchical Clustering Can Jointly Satisfy Richness, Consistency, and Scale Invariance
Machine Learning
Summary
Clustering is about grouping similar things together, but experts have shown that with simple groups it's impossible to meet three important fairness rules at the same time. This paper shows that when you use hierarchical clustering, which organizes groups within groups, it is possible to satisfy all three rules together. The authors also build different methods that follow these rules and show there are many diverse ways to do this while sharing some common structure. This expands our understanding of how to fairly organize complex data.
What this means in practice
- •For data engineers: Design hierarchical clustering pipelines that guarantee fairness properties previously unachievable with flat clustering.
- •For machine learning practitioners: Build interpretable hierarchical models that respect scale and consistency principles in data grouping.
A theory result. No direct application yet.
Authors
Daichi Kuroda, Maximilien Dreveton, Matthias Grossglauser, Patrick Thiran
Abstract
Despite its ubiquity, clustering lacks a universally accepted definition of what is a cluster. Kleinberg's Impossibility Theorem formalizes this difficulty by showing that no flat clustering method can simultaneously satisfy three natural axioms: scale invariance, richness, and consistency. In this paper, we ask whether this impossibility persists when the output is a hierarchy rather than a single partition. We show that, in contrast to the flat clustering setting, the hierarchical analog of these axioms are jointly satisfiable. In fact, there exist uncountably many hierarchical clustering methods satisfying these axioms, which we call admissible. We explicitly construct several admissible methods, including methods based on well-separated clusters and a non-binary version of single linkage. For certain pairs of admissible methods, the hierarchy produced by one always refines that produced by the other. This refinement relation defines a partial order on the class of admissible methods. This partially ordered set has no greatest element and contains uncountably many pairwise incompatible maximal elements, revealing substantial diversity among admissible methods. Nevertheless, this diversity is constrained: every admissible method contains a hierarchy of sufficiently well-separated clusters, and every finite collection of admissible methods shares such a nontrivial common backbone.