🤖 machine learning

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

Dit artikel toont aan dat, in tegenstelling tot platte clustering die wordt beperkt door de onmogelijkheidstelling van Kleinberg, hiërarchische clustering gelijktijdig kan voldoen aan de axioma's van rijkdom, consistentie en schaalinvariantie door de existentie van onaftelbaar veel toelaatbare methoden die, ondanks hun diversiteit, een gemeenschappelijke structurele ruggengraat delen.

Oorspronkelijke auteurs: Daichi Kuroda, Maximilien Dreveton, Matthias Grossglauser, Patrick Thiran

Gepubliceerd 2026-09-11

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Daichi Kuroda, Maximilien Dreveton, Matthias Grossglauser, Patrick Thiran

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

In de wereld van data science is er een fundamentele taak genaamd clustering. Stel je voor dat je een verzameling objecten hebt—misschien een mix van fruit, of een groep mensen, of een set documenten—en je wilt ze sorteren in betekenisvolle groepen op basis van hoe ze op elkaar lijken. Je hebt geen label dat je vertelt welke appel welke is; je hebt alleen een maatstaf voor hoe verschillend elk item is van elk ander item. Het doel is om de data voor zichzelf te laten spreken en de verborgen structuur ervan te onthullen. Decennialang hebben onderzoekers geprobeerd de perfecte manier te definiëren om dit sorteren te doen. Ze hebben een reeks basisregels voorgesteld waaraan elke goede sorteermethode moet voldoen. Eén regel is dat de methode niet om moet geven aan de eenheden van meting; of je afstand nu meet in meters of mijlen, de groepen moeten hetzelfde blijven. Een andere regel is dat de methode flexibel genoeg moet zijn om elke mogelijke groepering te vinden als de data daar geschikt voor is. Een derde regel is dat als je de items binnen een groep meer op elkaar laat lijken en de items tussen groepen meer van elkaar laat verschillen, de methode niet plotseling besluit die groep weer uit elkaar te trekken.

Lama lang werd geloofd dat geen enkele methode aan al deze drie regels tegelijkertijd kon voldoen. Een beroemd resultaat in het vakgebied toonde aan dat als je gedwongen wordt om je data in slechts één platte laag van groepen te snijden—zoals een stok kaarten sorteren in een enkele stapel kleuren—je onvermijdelijk één van de regels zult breken. Je zult ofwel de schaal van de data moeten negeren, of je zult bepaalde geldige groeperingen moeten negeren, of je zult onstabiel zijn wanneer de data licht verandert. Dit creëerde een gevoel van beperking, alsof de aard van het sorteren van data in platte groepen inherent gebrekkig was. Maar wat als de oplossing niet was om de data in een enkele laag te dwingen, maar om het toe te laten zich te ontvouwen tot een boom? Wat als je, in plaats van alleen te zeggen "dit zijn de groepen", ook kon zeggen "dit zijn de groepen, en binnen die groepen zijn er kleinere groepen, en binnen die weer nog kleinere groepen"? Dit is het idee van hiërarchische clustering, waarbij de output een geneste structuur is in plaats van een platte lijst.

Een team van onderzoekers van de École Polytechnique Fédérale de Lausanne en de Université Gustave Eiffel heeft nu aangetoond dat deze hiërarchische aanpak alles verandert. Ze namen de drie strikte regels die platte clustering onmogelijk maakten en vroegen zich af of ze voldaan konden worden als de output een hiërarchie was. Het antwoord is een definitief ja. Ze bewezen dat er niet slechts één manier is om dit te doen, maar een onaftelbaar groot aantal methoden die alle drie de regels tegelijkertijd kunnen vervullen. Sterker nog, ze ontdekten dat de ruimte van deze geldige methoden ongelooflijk groot en divers is. Het is zo groot dat je ze niet eens allemaal kunt opsommen, en binnen deze enorme collectie zijn er veel methoden die fundamenteel onverenigbaar met elkaar zijn. Je kunt niet simpelweg de "beste" methode kiezen die alles perfect doet, omdat er geen enkele methode is die de ultieme winnaar is die alle anderen verfijnt.

De onderzoekers hebben deze methoden niet alleen bewezen door hun bestaan; ze hebben er ook enkele gebouwd om te laten zien hoe ze werken. Ze keken naar veelvoorkomende manieren van data sorteren, zoals de methode die altijd eerst de twee dichtstbijzijnde items samenvoegt. Ze ontdekten dat een specifieke versie van deze methode, die toestaat om meer dan twee groepen tegelijk samen te voegen wanneer ze even dichtbij liggen, perfect werkt. Ze hebben ook nieuwe methoden uitgevonden op basis van hoe goed de groepen van elkaar gescheiden zijn. De ene methode zoekt naar groepen waar de items binnen de groep veel dichter bij elkaar liggen dan bij iets buiten de groep. Een andere methode kijkt naar een iets ander soort scheiding. Ze lieten zien dat deze methoden allemaal geldig zijn, maar toch verschillende resultaten produceren. Sommige methoden zijn zeer strikt en vinden alleen de meest voor de hand liggende, goed gescheiden groepen. Andere zijn toleranter en vinden veel subtielere verbanden.

Ondanks deze wilde diversiteit ontdekten de onderzoekers een verborgen orde. Hoewel de methoden van mening verschillen over de fijnere details, zijn ze het eens over de meest voor de hand liggende, goed gescheiden structuren. Als je twee willekeurige geldige methoden neemt en naar de groepen kijkt waar ze het allebei over eens zijn, zul je een gemeenschappelijke ruggengraat van zeer duidelijke, onderscheidende clusters vinden. Dit betekent dat hoewel de methoden kunnen verschillen in hoe ze omgaan met de rommelige, middelste zone van de data, ze allemaal een solide fundament respecteren. De onderzoekers verkenden ook wat er gebeurt als je een vierde regel toevoegt: dat als de data al een perfecte boomstructuur in zich heeft, de methode precies die boom moet vinden. Zelfs met deze striktere vereiste blijft de enorme diversiteit van methoden bestaan, maar nu is er een enkele, meest grove methode die dient als startpunt voor alle anderen.

Dit werk herstructureert ons begrip van hoe we data kunnen organiseren. Het laat zien dat de onmogelijkheid om aan al onze wensen voor een sorteermethode te voldoen niet een fundamenteel gebrek is aan het universum, maar een beperking van het dwingen van data in een enkele, platte laag. Door de data een verhaal te laten vertellen van geneste groepen, kunnen we zowel de ene als de andere kant op. We kunnen een methode hebben die schaalinvariant, flexibel en stabiel is, allemaal tegelijkertijd. De onderzoekers toonden ook aan dat deze methoden robuust zijn tegen de gebruikelijke manieren waarop we data voorbewerken, zoals het veranderen van de eenheden of het transformeren van de getallen voordat we sorteren. Dit suggereert dat het raamwerk niet slechts een wiskundige curiositeit is, maar een praktisch instrument dat kan worden gebruikt in real-world pipelines. De studie laat ons een beeld achter van een landschap vol talloze geldige manieren om de wereld te sorteren, waarvan ze allemaal de belangrijkste kenmerken erkennen, maar tegelijkertijd een rijk scala aan perspectieven bieden op de details.

Technische Samenvatting: Hiërarchische Clustering kan Rijkdom, Consistentie en Schaalinvariantie gezamenlijk bevredigen

Probleemstelling
Clustering mist een universeel geaccepteerde definitie van een "cluster", een moeilijkheid die is geformaliseerd door Kleinberg's Onmogelijkheidsstelling (Kleinberg, 2002). Deze stelling toont aan dat geen enkele platte clusteringsmethode (die dissimilariteiten afbeeldt op een enkele partitie) gelijktijdig drie natuurlijke axioma's kan bevredigen: schaalinvariantie (onafhankelijkheid van de meeteenheden), rijkdom (het vermogen om elke mogelijke partitie te produceren bij een passende input), en consistentie (de eigenschap dat het versterken van intra-cluster dissimilariteiten en het verzwakken van inter-cluster dissimilariteiten de output-partitie niet zou mogen veranderen). De spanning ontstaat omdat consistentie de creatie van nieuwe substructuren binnen een cluster toestaat, wat een platte partitie niet kan uitdrukken zonder het axioma te schenden.

Dit artikel onderzoekt of deze onmogelijkheid voortduurt wanneer de output een hiërarchie is (een geneste familie van clusters) in plaats van een platte partitie. De auteurs vragen zich af of hiërarchische analogen van Kleinberg's axioma's gezamenlijk bevredigd kunnen worden.

Methodologie en Definities
De auteurs definiëren een hiërarchische clusteringsmethode als een afbeelding $T$ van een verzameling dissimilariteitsfuncties $D(X)$ naar de verzameling hiërarchieën $T(X)$ , waarbij een hiërarchie een laminaire familie van clusters is die de volledige verzameling $X$ en alle singletonen bevat. Zij formuleren vier axioma's voor hiërarchische clustering:

Schaalinvariantie: $T(\beta d) = T(d)$ voor elke schaleringsfactor $\beta > 0$ .
Partitie-rijkdom: Voor elke partitie $\mathcal{C}$ van $X$ bestaat er een dissimilariteit $d$ zodanig dat $\mathcal{C} \subseteq T(d)$ . (Opmerking: De hiërarchie moet de partitie bevatten als een deelverzameling van haar clusters).
Partitie-consistentie: Als een partitie $\mathcal{C}$ een deelverzameling is van $T(d)$ , en $d'$ is een $\mathcal{C}$ -versterking van $d$ (interne afstanden nemen af, externe afstanden nemen toe), dan is $\mathcal{C} \subseteq T(d')$ .
Permutatie-invariantie: De output hangt alleen af van de dissimilariteitsstructuur, niet van de etikettering van de punten.

Een methode die aan alle vier voldoet, wordt admisibel genoemd. De auteurs overwegen ook een sterkere voorwaarde, exactheid op ultrametrische metrieken, die vereist dat indien de input een ultrametrische metriek is, de methode de canonieke hiërarchie geassocieerd met die metriek herstelt.

Belangrijkste Bijdragen en Resultaten

1. Bereikbaarheid van Admisibiliteit
In tegenstelling tot de platte clustering-setting bewijzen de auteurs dat er admissible hiërarchische methoden bestaan. Sterker nog, er zijn onaftelbaar veel dergelijke methoden.

Expliciete Constructies: Het artikel construeert verschillende admissible methoden:
- Niet-binaire Single Linkage ( $T_{SL}$ ): In tegen tegenover de standaard binaire single linkage, is de niet-binaire variant (het gelijktijdig samenvoegen van alle gebonden clusters) admissible.
- Scheidingsmethoden: Twee families van methoden, $T_{glob}^\eta$ en $T_{loc}^\eta$ , gebaseerd op globale en lokale scheidingsmarges. Deze definiëren clusters waar interne dissimilariteiten voldoende klein zijn in vergelijking met externe dissimilariteiten.
- Bryant-Berry Stabiele Clusters ( $T_{stable}$ ): Een methode gebaseerd op combinatorische stabiliteitscriteria, samen met de power-transformatie varianten $T_{stable}^{(p)}$ .
Onmogelijkheid voor Andere Linkages: Niet-binaire varianten van complete, average, Ward, centroid en median linkage blijken ten minste één axioma te schenden.

2. Structurele Analyse van Admissible Methoden
De verzameling admissible methoden, aangeduid als $H_{\alpha_{adm}}(X)$ , wordt geanalyseerd onder de verfijningsorde ( $T_1 \sqsubseteq T_2$ als $T_1(d) \subseteq T_2(d)$ voor alle $d$ ).

Diversiteit: De verzameling vormt een partiële geordende verzameling (poset) met onaftelbare hoogte, breedte en cellulariteit.
Geen Grootste Element: Er is geen enkele "fijnste" admissible methode die alle andere verfijnt.
Incompatibiliteit: Er bestaan onaftelbaar veel onderling incompatibele maximale elementen (methoden die niet gezamenlijk verfijnd kunnen worden door een andere admissible methode). Specifiek vormt de familie $\{T_{stable}^{(p)} : p > 0\}$ een sterke upward antichain.
Gemeenschappelijke Ruggengraat: Ondanks deze diversiteit, dwingen de axioma's een niet-triviale gemeenschappelijke structuur af. Elke admissible methode verfijnt een hiërarchie van voldoende goed gescheiden clusters ( $T_{glob}^\eta$ voor een marge-sequentie $\eta$ ). Bovendien deelt elke eindige collectie van admissible methoden een gemeenschappelijke ruggengraat.
Geen Kleinste Element: De triviale methode (die alleen singletonen en de root teruggeeft) is het infimum in de ruimte van alle hiërarchische methoden, maar is niet admissible omdat zij faalt op partitie-rijkdom. Daarom heeft de admissible klasse geen kleinste element.

3. Sterke Admisibiliteit en Ultrametrische Metrieken
Wanneer het axioma van exactheid op ultrametrische metrieken wordt toegevoegd, wordt de klasse sterk admissible ( $H_{\alpha_{adm}^+}(X)$ ).

Deze klasse blijft onaftelbaar en behoudt de diversiteit van maximale elementen.
Cruciaal is dat, in tegenstelling tot de reguliere admissible klasse, de sterk admissible klasse een kleinste element heeft: $T_{glob}$ (de methode met marge-sequentie $\eta = \mathbf{1}$ ). Dit levert een meest grove sterk admissible methode op.

4. Preprocessing en Compositie
Het artikel bestudeert preprocessing-transformaties $\mu: D(X) \to D(X)$ die vóór de clustering worden toegepast.

Behoudscondities: De auteurs leiden algemene condities af waaronder een transformatie de axioma's behoudt (bijv. schaling commuteert met $\mu$ , en versterkingen mappen naar versterkingen).
Voorbeelden:
- Minimax-pad (Subdominante Ultrametrische Metriek): De transformatie $B^*$ die een dissimilariteit afbeeldt op zijn subdominante ultrametrische metriek behoudt schaalinvariantie, permutatie-invariantie en ultrametrische exactheid. Dit leidt tot de factorisatie $T_{SL} = T_{glob} \circ B^*$ , wat aantoont dat single linkage een compositie is van een ultrametrische transformatie en een scheidingsmethode.
- PCA en HDBSCAN: Het artikel analyseert PCA en mutual-reachability preprocessing, waarbij wordt aangetoond dat zij schaal- en permutatie-invariantie behouden, maar over het algemeen falen in het behoud van rijkdom of consistentie.

Betekenis
Het artikel toont aan dat de fundamentele onmogelijkheid om Kleinberg's axioma's te bevredigen een artefact is van het beperken van de output tot platte partities. Door over te stappen naar hiërarchische outputs, kunnen de axioma's gezamenlijk worden bevredigd, wat de deur opent naar een uitgestrekt landschap van admissible methoden.

Het werk onthult dat hoewel de ruimte van admissible methoden extreem divers is (het ontbreken van een unieke optimale oplossing), deze niet ongestructureerd is. De axioma's dwingen een "conservatieve" ruggengraat van goed gescheiden clusters af die alle admissible methoden moeten respecteren, terwijl ze vrijheid laten in hoe fijnere structuren worden opgelost. Dit biedt een principieel kader voor het begrijpen van de trade-offs in hiërarchische clustering en suggereert dat de keuze voor een specifieke methode binnen de admissible klasse afhangt van de gewenste balans tussen gevoeligheid voor ruis en de granulariteit van de output, in plaats van een schending van fundamentele axiomatische principes.

De auteurs merken op dat dit kader aansluit bij eerder werk van Carlsson en Mémoli (2010) en Ackerman en Ben-David (2016), maar verschilt door de focus op ongewogen hiërarchieën en het behoud van de volledige kracht van Kleinberg's consistentie-axioma, wat resulteert in een bredere, meer diverse klasse in plaats van een karakterisering van een enkel algoritme.

Meer zoals dit