🤖 machine learning

Hierarchical Clustering Can Jointly Satisfy Richness, Consistency, and Scale Invariance

Cet article démontre que, contrairement au partitionnement plat qui est contraint par le théorème d'impossibilité de Kleinberg, le partitionnement hiérarchique peut satisfaire simultanément les axiomes de richesse, de cohérence et d'invariance d'échelle grâce à l'existence d'une infinité non dénombrable de méthodes admissibles qui partagent une structure commune malgré leur diversité.

Auteurs originaux : Daichi Kuroda, Maximilien Dreveton, Matthias Grossglauser, Patrick Thiran

Publié 2026-09-11

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Daichi Kuroda, Maximilien Dreveton, Matthias Grossglauser, Patrick Thiran

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Dans le monde de la science des données, il existe une tâche fondamentale appelée le partitionnement de données (clustering). Imaginez que vous avez une collection d'objets — peut-être un mélange de fruits, ou un groupe de personnes, ou un ensemble de documents — et que vous souhaitez les trier en groupes significatifs basés sur leur similitude. Vous n'avez pas d'étiquette vous indiquant quel fruit est quelle pomme ; vous disposez seulement d'une mesure de la différence entre chaque objet et tous les autres. Le but est de laisser les données parler d'elles-mêmes et de révéler leur structure cachée. Depuis des décennies, des chercheurs tentent de définir la méthode parfaite pour effectuer ce tri. Ils ont proposé un ensemble de règles de base que toute bonne méthode de tri devrait suivre. L'une de ces règles est que la méthode ne doit pas se soucier des unités de mesure ; que vous mesuriez la distance en mètres ou en miles, les groupes doivent rester les mêmes. Une autre règle est que la méthode doit être assez flexible pour trouver n'importe quel groupement possible si les données s'y prêtent. Une troisième règle est que si vous rendez les éléments au sein d'un groupe plus similaires entre eux et rendez les éléments entre les groupes plus différents, la méthode ne doit pas soudainement décider de briser ce groupe.

Pendant longtemps, on a cru qu'aucune méthode unique ne pouvait satisfaire ces trois règles à la fois. Un résultat célèbre dans ce domaine a montré que si vous êtes contraint de découper vos données en une seule couche de groupes — comme trier un jeu de cartes en un seul tas de couleurs — vous devrez inévitablement transgresser l'une des règles. Vous devrez peut-être ignorer l'échelle des données, ou vous devrez peut-être ignorer certains groupements valides, ou vous devrez peut-être être instable lorsque les données changent légèrement. Cela a créé un sentiment de limitation, comme si la nature même du tri de données en groupes plats était défaillante. Mais et si la solution n'était pas de forcer les données dans une seule couche, mais de les laisser se déployer sous forme d'arbre ? Et si, au lieu de simplement dire « voici les groupes », vous pouviez dire « voici les groupes, et au sein de ces groupes, il y a des groupes plus petits, et au sein de ceux-ci, encore d'autres plus petits » ? C'est l'idée du partitionnement hiérarchique, où le résultat est une structure imbriquée plutôt qu'une liste plate.

Une équipe de chercheurs de l'École Polytechnique Fédérale de Lausanne et de l'Université Gustave Eiffel a maintenant démontré que cette approche hiérarchique change tout. Ils ont pris les trois règles strictes qui rendaient le partitionnement plat impossible et ont cherché à savoir si elles pouvaient être satisfaites si le résultat était une hiérarchie. La réponse est un oui définitif. Ils ont prouvé qu'il n'existe pas seulement une façon de faire, mais un nombre indénombrable de méthodes capables de satisfaire simultanément ces trois règles. En fait, ils ont découvert que l'espace de ces méthodes valides est incroyablement vaste et diversifié. Il est si vaste que vous ne pouvez même pas toutes les énumérer, et au sein de cette vaste collection, il existe de nombreuses méthodes fondamentalement incompatibles entre elles. On ne peut pas simplement choisir la « meilleure » méthode qui ferait tout parfaitement, car aucune méthode unique n'est la grande gagnante qui affine toutes les autres.

Les chercheurs n'ont pas seulement prouvé l'existence de ces méthodes ; ils en ont construit plusieurs pour montrer comment elles fonctionnent. Ils ont examiné des méthodes courantes de tri de données, telles que la méthode qui fusionne toujours les deux éléments les plus proches en premier. Ils ont découvert qu'une version spécifique de cette méthode, qui permet de fusionner plus de deux groupes à la fois lorsqu'ils sont également proches, fonctionne parfaitement. Ils ont également inventé de nouvelles méthodes basées sur la façon dont les groupes sont séparés. Une méthode recherche des groupes où les éléments à l'intérieur sont beaucoup plus proches les uns des autres qu'ils ne le sont de tout ce qui se trouve à l'extérieur. Une autre cherche une forme de séparation légèrement différente. Ils ont montré que ces méthodes sont toutes valides, pourtant elles produisent des résultats différents. Certaines méthodes sont très strictes et ne trouvent que les groupes les plus évidents et les mieux séparés. D'autres sont plus permissives et trouvent de nombreuses connexions plus subtiles.

Malgré cette immense diversité, les chercheurs ont découvert un ordre caché. Bien que les méthodes ne soient pas d'accord sur les détails les plus fins, elles s'accordent toutes sur les structures les plus évidentes et les mieux séparées. Si vous prenez n'importe quelles deux méthodes valides et que vous examinez les groupes sur lesquels elles s'accordent toutes les deux, vous trouverez une colonne vertébrale commune de clusters très clairs et distincts. Cela signifie que si les méthodes peuvent différer dans la gestion de la zone intermédiaire confuse des données, elles respectent toutes la même fondation solide. Les chercheurs ont également exploré ce qui se passe si l'on ajoute une quatrième règle : que si les données possèdent déjà une structure en arbre parfaite intégrée, la méthode doit trouver cet arbre exact. Même avec cette exigence plus stricte, la vaste diversité des méthodes demeure, mais il existe désormais une méthode unique, la plus grossière, qui sert de point de départ à toutes les autres.

Ce travail transforme notre compréhension de la manière dont nous pouvons organiser les données. Il montre que l'impossibilité de satisfaire tous nos désirs concernant une méthode de tri n'est pas un défaut fondamental de l'univers, mais une limitation due au fait de forcer les données dans une seule couche plate. En permettant aux données de raconter une histoire de groupes imbriqués, nous pouvons avoir le beurre et l'argent du beurre. Nous pouvons disposer d'une méthode qui est à la fois invariante par rapport à l'échelle, flexible et stable. Les chercheurs ont également montré que ces méthodes sont robustes aux méthodes courantes de prétraitement des données, comme le changement d'unités ou la transformation des nombres avant le tri. Cela suggère que ce cadre n'est pas seulement une curiosité mathématique, mais un outil pratique pouvant être utilisé dans des pipelines réels. L'étude nous offre l'image d'un paysage rempli d'innombrables façons valides de trier le monde, toutes s'accordant sur les caractéristiques les plus importantes, tout en offrant une riche variété de perspectives sur les détails.

Résumé Technique : Le partitionnement hiérarchique peut satisfaire conjointement la richesse, la cohérence et l'invariance d'échelle

Énoncé du problème
Le partitionnement (clustering) manque d'une définition universellement acceptée d'un « cluster », une difficulté formalisée par le théorème d'impossibilité de Kleinberg (Kleinberg, 2002). Ce théorème démontre qu'aucune méthode de partitionnement plat (mappage de dissimilarités vers une partition unique) ne peut satisfaire simultanément trois axiomes naturels : l'invariance d'échelle (indépendance vis-à-vis des unités de mesure), la richesse (la capacité à produire n'importe quelle partition possible pour une entrée appropriée) et la cohérence (la propriété selon laquelle le renforcement des similitudes intra-clusters et l'affaiblissement des dissimilarités inter-clusters ne devrait pas modifier la partition de sortie). La tension provient du fait que la cohérence permet la création de nouvelles sous-structures au sein d'un cluster, ce qu'une partition plate ne peut exprimer sans violer l'axiome.

Cet article étudie si cette impossibilité persiste lorsque la sortie est une hiérarchie (une famille imbriquée de clusters) plutôt qu'une partition plate. Les auteurs se demandent si des analogues hiérarchiques des axiomes de Kleinberg peuvent être satisfaits conjointement.

Méthodologie et Définitions
Les auteurs définissent une méthode de partitionnement hiérarchique comme une application $T$ d'un ensemble de fonctions de dissimilarité $D(X)$ vers l'ensemble des hiérarchies $T(X)$ , où une hiérarchie est une famille laminaire de clusters contenant l'ensemble complet $X$ et tous les singletons. Ils formulent quatre axiomes pour le partitionnement hiérarchique :

Invariance d'échelle : $T(\beta d) = T(d)$ pour tout facteur d'échelle $\beta > 0$ .
Richesse de partition : Pour toute partition $\mathcal{C}$ de $X$ , il existe une dissimilarité $d$ telle que $\mathcal{C} \subseteq T(d)$ . (Note : La hiérarchie doit contenir la partition comme un sous-ensemble de ses clusters).
Cohérence de partition : Si une partition $\mathcal{C}$ est contenue dans $T(d)$ , et que $d'$ est un renforcement de $d$ par rapport à $\mathcal{C}$ (les distances intra-clusters diminuent, les distances inter-clusters augmentent), alors $\mathcal{C} \subseteq T(d')$ .
Invariance par permutation : La sortie dépend uniquement de la structure de dissimilarité, et non de l'étiquetage des points.

Une méthode satisfaisant ces quatre points est qualifiée d'admissible. Les auteurs considèrent également une condition plus forte, l'exactitude sur les ultramétriques, exigeant que si l'entrée est une ultramétrique, la méthode récupère la hiérarchie canonique associée à cette ultramétrique.

Contributions clés et Résultats

1. Réalisabilité de l'admissibilité
Contrairement au contexte du partitionnement plat, les auteurs prouvent que des méthodes hiérarchiques admissibles existent. En fait, il existe un nombre indénombrable de telles méthodes.

Constructions explicites : L'article construit plusieurs méthodes admissibles :
- Single Linkage non binaire ( $T_{SL}$ ) : Contrairement au single linkage binaire standard, la variante non binaire (fusionnant simultanément tous les clusters liés) est admissible.
- Méthodes de séparation : Deux familles de méthodes, $T_{glob}^\eta$ et $T_{loc}^\eta$ , basées sur des marges de séparation globales et locales. Elles définissent des clusters où les dissimilarités internes sont suffisamment petites par rapport aux dissimilarités externes.
- Clusters stables de Bryant-Berry ( $T_{stable}$ ) : Une méthode basée sur des critères de stabilité combinatoire, ainsi que ses variantes de transformation de puissance $T_{stable}^{(p)}$ .
Impossibilité pour d'autres liens : Les variantes non binaires de complete, average, Ward, centroid et median linkage sont montrées comme violant au moins un axiome.

2. Analyse structurelle des méthodes admissibles
L'ensemble des méthodes admissibles, noté $H_{\alpha_{adm}}(X)$ , est analysé sous l'ordre de raffinement ( $T_1 \sqsubseteq T_2$ si $T_1(d) \subseteq T_2(d)$ pour tout $d$ ).

Diversité : L'ensemble forme un ensemble partiellement ordonné (poset) avec une hauteur, une largeur et une cellularité indénombrables.
Absence de plus grand élément : Il n'existe pas de méthode admissible unique qui soit la plus fine et qui affine toutes les autres.
Incompatibilité : Il existe un nombre indénombrable d'éléments maximaux mutuellement incompatibles (des méthodes qui ne peuvent être conjointement affinées par une autre méthode admissible). Plus précisément, la famille $\{T_{stable}^{(p)} : p > 0\}$ forme une antichaine ascendante forte.
Épine dorsale commune : Malgré cette diversité, les axiomes imposent une structure commune non triviale. Toute méthode admissible affine une hiérarchie de clusters suffisamment bien séparés ( $T_{glob}^\eta$ pour une certaine séquence de marges $\eta$ ). De plus, toute collection finie de méthodes admissibles partage une épine dorsale commune.
Absence de plus petit élément : La méthode triviale (ne retournant que les singletons et la racine) est l'infimum dans l'espace de toutes les méthodes hiérarchiques mais n'est pas admissible car elle échoue à la richesse de partition. Ainsi, la classe admissible n'a pas de plus petit élément.

3. Admissibilité forte et ultramétriques
Lorsque l'axiome d'exactitude sur les ultramétriques est ajouté, la classe devient fortement admissible ( $H_{\alpha_{adm}^+}(X)$ ).

Cette classe reste indénombrable et conserve la diversité des éléments maximaux.
Crucialement, contrairement à la classe admissible canonique, la classe fortement admissible possède un plus petit élément : $T_{glob}$ (la méthode avec la séquence de marge $\eta = \mathbf{1}$ ). Cela fournit une méthode la plus grossièrement admissible.

4. Prétraitement et composition
L'article étudie les transformations de prétraitement $\mu: D(X) \to D(X)$ appliquées avant le partitionnement.

Conditions de préservation : Les auteurs dérivent des conditions générales sous lesquelles une transformation préserve les axiomes (par exemple, l'échelle commute avec $\mu$ , les renforcements mènent à des renforcements).
Exemples :
- Chemin minimax (Ultramétrique subdominante) : La transformation $B^*$ qui associe à une dissimilarité son ultramétrique subdominante préserve l'invariance d'échelle, l'invariance par permutation et l'exactitude ultramétrique. Cela conduit à la factorisation $T_{SL} = T_{glob} \circ B^*$ , montrant que le single linkage est une composition d'une transformation ultramétrique et d'une méthode de séparation.
- PCA et HDBSCAN : L'article analyse le prétraitement par PCA et par portée mutuelle (mutual-reachability), montrant qu'ils préservent l'invariance d'échelle et de permutation mais échouent généralement à préserver la richesse ou la cohérence.

Signification
L'article démontre que l'impossibilité fondamentale de satisfaire les axiomes de Kleinberg est un artefact de la restriction de la sortie à des partitions plates. En passant à des sorties hiérarchiques, les axiomes deviennent conjointement satisfaisables, ouvrant la porte à un vaste paysage de méthodes admissibles.

Ce travail révèle que, bien que l'espace des méthodes admissibles soit extrêmement diversifié (manquant d'une solution optimale unique), il n'est pas déstructuré. Les axiomes imposent une épine dorsale « conservatrice » de clusters bien séparés que toutes les méthodes admissibles doivent respecter, tout en laissant la liberté de résoudre les structures plus fines. Cela fournit un cadre conceptuel pour comprendre les compromis du partitionnement hiérarchique et suggère que le choix d'une méthode spécifique au sein de la classe admissible dépend de l'équilibre souhaité entre la sensibilité au bruit et la granularité de la sortie, plutôt que d'une violation des principes axiomatiques fondamentaux.

Les auteurs notent que ce cadre se connecte aux travaux antérieurs de Carlsson et Mémoli (2010) et Ackerman et Ben-David (2016), mais s'en distingue en se concentrant sur les hiérarchies non pondérées et en conservant toute la force de l'axiome de cohérence de Kleinberg, ce qui aboutit à une classe plus large et plus diversifiée plutôt qu'à la caractérisation d'un algorithme unique.

Articles similaires