Metraipolis › archive › dc_e751a7b667ed
Hierarchical Clustering Can Jointly Satisfy Richness, Consistency, and Scale Invariance — arXiv:2609.11173
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.11173
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T05:54:55.508Z
- SHA-256 of the archived text
435abe283c73a6280eecc18e0ecca3c96e8f1382b08852cbd95be1ca12e9f6bb- Stable URL of this page
https://metraipolis.com/documento/dc_e751a7b667ed
How to cite
Hierarchical Clustering Can Jointly Satisfy Richness, Consistency, and Scale Invariance — arXiv:2609.11173 — arXiv (en), https://arxiv.org/abs/2609.11173 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e751a7b667ed (Metraipolis archive dc_e751a7b667ed, sha256 435abe283c73a6280eecc18e0ecca3c96e8f1382b08852cbd95be1ca12e9f6bb)
BibTeX
@misc{dce751a7b667ed,
title = {Hierarchical Clustering Can Jointly Satisfy Richness, Consistency, and Scale Invariance — arXiv:2609.11173},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.11173},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e751a7b667ed; sha256 435abe283c73a6280eecc18e0ecca3c96e8f1382b08852cbd95be1ca12e9f6bb},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.11173. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-11 in cs.LG). Categorie arXiv: Machine Learning (cs.LG) ; Methodology (stat.ME); Machine Learning (stat.ML). Pagina del lavoro: https://arxiv.org/abs/2609.11173 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-16T05:44:24.984Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-11?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).