🤖 machine learning

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

Questo articolo dimostra che, a differenza del clustering piatto che è vincolato dal Teorema di Impossibilità di Kleinberg, il clustering gerarchico può soddisfare simultaneamente gli assiomi di ricchezza, coerenza e invarianza di scala attraverso l'esistenza di un numero incontabile di metodi ammissibili che condividono un comune spina dorsale strutturale nonostante la loro diversità.

Autori originali: Daichi Kuroda, Maximilien Dreveton, Matthias Grossglauser, Patrick Thiran

Pubblicato 2026-09-11

📖 5 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Daichi Kuroda, Maximilien Dreveton, Matthias Grossglauser, Patrick Thiran

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Nel mondo della scienza dei dati, esiste un compito fondamentale chiamato clustering. Immaginate di avere una collezione di oggetti—forse un misto di frutta, o un gruppo di persone, o un insieme di documenti—e volete suddividerli in gruppi significativi in base a quanto sono simili tra loro. Non avete un'etichetta che vi dice quale mela sia quale; avete solo una misura di quanto ogni elemento sia diverso da ogni altro. L'obiettivo è lasciare che i dati parlino da soli e rivelino la loro struttura nascosta. Per decenni, i ricercatori hanno cercato di definire il modo perfetto per fare questa classificazione. Hanno proposto un insieme di regole basilari che qualsiasi buon metodo di ordinamento dovrebbe seguire. Una regola è che il metodo non dovrebbe preoccuparsi delle unità di misura; che si misuri la distanza in metri o in miglia, i gruppi dovrebbero rimanere gli stessi. Un'altra regola è che il metodo debba essere abbastanza flessibile da trovare qualsiasi raggruppamento possibile, se i dati sono adatti. Una terza regola è che, se rendete gli elementi all'interno di un gruppo più simili tra loro e rendete gli elementi tra i gruppi più diversi, il metodo non debba improvvisamente decidere di rompere quel gruppo.

Per molto tempo, si è creduto che nessun singolo metodo potesse soddisfare tutte e tre queste regole contemporaneamente. Un celebre risultato nel campo ha dimostrato che, se siete costretti a tagliare i vostri dati in un unico strato piatto di gruppi—come smistare un mazzo di carte nei singoli semi—avrete inevitabilmente dovuto violare una delle regole. Potreste dover ignorare la scala dei dati, oppure potreste dover ignorare certi raggruppamenti validi, oppure potreste dover essere instabili quando i dati cambiano leggermente. Questo ha creato un senso di limitazione, come se la natura stessa di smistare i dati in gruppi piatti fosse difettosa. Ma cosa succederebbe se la soluzione non fosse forzare i dati in un singolo strato, ma lasciarli dispiegare in un albero? E se, invece di dire solo "questi sono i gruppi", poteste dire "questi sono i gruppi, e all'interno di quei gruppi, ci sono gruppi più piccoli, e all'interno di questi, altri ancora più piccoli"? Questa è l'idea del clustering gerarchico, dove l'output è una struttura nidificata piuttosto che un elenco piatto.

Un team di ricercatori dell'École Polytechnique Fédérale de Lausanne e dell'Université Gustave Eiffel ha ora dimostrato che questo approccio gerarchico cambia tutto. Hanno preso le tre regole rigide che rendevano impossibile il clustering piatto e si sono chiesti se potessero essere soddisfatte se l'output fosse una gerarchia. La risposta è un sì definitivo. Hanno dimostrato che non esiste solo un modo per farlo, ma un numero incontabile di metodi che possono soddisfare tutte e tre le regole simultaneamente. In effetti, hanno scoperto che lo spazio di questi metodi validi è incredibilmente vasto e diversificato. È così grande che non è nemmeno possibile elencarli tutti, e all'interno di questa vasta collezione, esistono molti metodi che sono fondamentalmente incompatibili tra loro. Non si può semplicemente scegliere il "migliore" che faccia tutto perfettamente, perché non esiste un singolo metodo che sia il vincitore ultimo in grado di perfezionare tutti gli altri.

I ricercatori non si sono limitati a dimostrare che questi metodi esistono; ne hanno costruiti diversi per mostrare come funzionano. Hanno esaminato i modi comuni di ordinare i dati, come il metodo che unisce sempre i due elementi più vicini per primi. Hanno scoperto che una versione specifica di questo metodo, che consente di unire più di due gruppi alla volta quando sono ugualmente vicini, funziona perfettamente. Hanno anche inventato nuovi metodi basati su quanto i gruppi siano ben separati. Un metodo cerca gruppi in cui gli elementi all'interno sono molto più vicini tra loro rispetto a quanto lo siano con qualsiasi elemento esterno. Un altro cerca un tipo di separazione leggermente diverso. Hanno dimostrato che questi metodi sono tutti validi, eppure producono risultati differenti. Alcuni metodi sono molto severi e trovano solo i gruppi più ovvi e ben separati. Altri sono più permissivi e trovano molte connessioni più sottili.

Nonostante questa selvaggia diversità, i ricercatori hanno scoperto un ordine nascosto. Sebbene i metodi non concordino sui dettagli più fini, concordano tutti sulle strutture più ovvie e ben separate. Se prendete due qualsiasi metodi validi e guardate i gruppi su cui concordano entrambi, troverete un'ossatura comune di cluster molto chiari e distinti. Ciò significa che, mentre i metodi possono differire nel gestire la parte disordinata e intermedia dei dati, rispettano tutti la stessa solida fondamentia. I ricercatori hanno anche esplorato cosa succede se si aggiunge una quarta regola: che se i dati hanno già una struttura ad albero perfetta incorporata in essi, il metodo debba trovare esattamente quell'albero. Anche con questo requisito più rigoroso, la vasta diversità dei metodi rimane, ma ora esiste un unico metodo, il più grossolano, che funge da punto di partenza per tutti gli altri.

Questo lavoro ridefinisce la nostra comprensione di come possiamo organizzare i dati. Dimostra che l'impossibilità di soddisfare tutti i nostri desideri per un metodo di ordinamento non è un difetto fondamentale dell'universo, ma un limite derivante dal forzare i dati in un singolo strato piatto. Permettendo ai dati di raccontare una storia di gruppi nidificati, possiamo avere sia la pappa che la cuccagna. Possiamo avere un metodo che sia invariante alla scala, flessibile e stabile, tutto allo stesso tempo. I ricercatori hanno anche dimostrato che questi metodi sono robusti rispetto ai comuni modi in cui pre-elaboriamo i dati, come cambiare le unità o trasformare i numeri prima dell'ordinamento. Ciò suggerisce che il framework non è solo una curiosità matematica, ma uno strumento pratico che può essere utilizzato in pipeline del mondo reale. Lo studio ci lascia con l'immagine di un panorama pieno di innumerevoli modi validi per ordinare il mondo, tutti concordi sulle caratteristiche più importanti, pur offrendo una ricca varietà di prospettive sui dettagli.

Sintesi Tecnica: Il Clustering Gerarchico può soddisfare congiuntamente Ricchezza, Coerenza e Invarianza di Scala

Problematica
Il clustering manca di una definizione universalmente accettata di "cluster", una difficoltà formalizzata dal Teorema dell'Impossibilità di Kleinberg (Kleinberg, 2002). Questo teorema dimostra che nessun metodo di clustering piatto (che mappa le dissimilarità in una singola partizione) può soddisfare simultaneamente tre assiomi naturali: invarianza di scala (indipendenza dalle unità di misura), ricchezza (la capacità di produrre qualsiasi partizione possibile dato un input appropriato) e coerenza (la proprietà per cui il rafforzamento delle similarità intra-cluster e l'indebolimento delle dissimilarità inter-cluster non dovrebbe alterare la partizione prodotta). La tensione nasce dal fatto che la coerenza permette la creazione di nuove sottostrutture all'interno di un cluster, cosa che una partizione piatta non può esprimere senza violare l'assioma.

Questo articolo indaga se tale impossibilità persista quando l'output è una gerarchia (una famiglia nidificata di cluster) piuttosto che una partizione piatta. Gli autori si chiedono se gli analoghi gerarchici degli assiomi di Kleinberg possano essere soddisfatti congiuntamente.

Metodologia e Definizioni
Gli autori definiscono un metodo di clustering gerarchico come una mappa $T$ da un insieme di funzioni di dissimilarità $D(X)$ all'insieme delle gerarchie $T(X)$ , dove una gerarchia è una famiglia laminare di cluster contenente l'intero insieme $X$ e tutti i singleton. Formulano quattro assiomi per il clustering gerarchico:

Invarianza di Scala: $T(\beta d) = T(d)$ per qualsiasi fattore di scala $\beta > 0$ .
Ricchezza della Partizione: Per ogni partizione $\mathcal{C}$ di $X$ , esiste una dissimilarità $d$ tale che $\mathcal{C} \subseteq T(d)$ . (Nota: la gerarchia deve contenere la partizione come sottoinsieme dei suoi cluster).
Coerenza della Partizione: Se una partizione $\mathcal{C}$ è contenuta in $T(d)$ , e $d'$ è un rafforzamento di $d$ rispetto a $\mathcal{C}$ (le distanze intra-cluster diminuiscono, le distanze inter-cluster aumentano), allora $\mathcal{C} \subseteq T(d')$ .
Invarianza di Permutazione: L'output dipende solo dalla struttura di dissimilarità, non dall'etichettatura dei punti.

Un metodo che soddisfa tutti e quattro è definito ammissibile. Gli autori considerano anche una condizione più forte, l'esattezza sugli ultrametrici, che richiede che, se l'input è un ultrametrico, il metodo recuperi la gerarchia canonica associata a tale ultrametrico.

Contributi Chiave e Risultati

1. Raggiungibilità dell'Ammissibilità
Contrariamente al contesto del clustering piatto, gli autori dimostrano che esistono metodi gerarchici ammissibili. In effetti, esistono innumerevoli tali metodi.

Costruzioni Esplicite: Il documento costruisce diversi metodi ammissibili:
- Single Linkage non binario ( $T_{SL}$ ): A differenza del classico single linkage binario, la variante non binaria (che unisce simultaneamente tutti i cluster con valori uguali) è ammissibile.
- Metodi di Separazione: Due famiglie di metodi, $T_{glob}^\eta$ e $T_{loc}^\eta$ , basati su margini di separazione globali e locali. Questi definiscono cluster dove le dissimilarità interne sono sufficientemente piccole rispetto a quelle esterne.
- Cluster Stabili di Bryant-Berry ( $T_{stable}$ ): Un metodo basato su criteri di stabilità combinatoria, insieme alle sue varianti di trasformazione di potenza $T_{stable}^{(p)}$ .
Impossibilità per altri Linkage: Le varianti non binarie di complete, average, Ward, centroid ed median linkage sono mostrate come violanti di almeno un assioma.

2. Analisi Strutturale dei Metodi Ammissibili
L'insieme dei metodi ammissibili, denotato $H_{\alpha_{adm}}(X)$ , è analizzato sotto l'ordine di raffinamento ( $T_1 \sqsubseteq T_2$ se $T_1(d) \subseteq T_2(d)$ per ogni $d$ ).

Diversità: L'insieme forma un insieme parzialmente ordinato (poset) con altezza, ampiezza e cellularità incontabili.
Assenza di un Massimo Elemento: Non esiste un singolo metodo ammissibile "più fine" che sia un raffinamento di tutti gli altri.
Incompatibilità: Esistono innumerevoli elementi massimi a coppie incompatibili (metodi che non possono essere congiuntamente raffinati da nessun altro metodo ammissibile). Nello specifico, la famiglia $\{T_{stable}^{(p)} : p > 0\}$ costituisce una forte antichiazione verso l'alto.
Spina Dorsale Comune: Nonostante questa diversità, gli assiomi impongono una struttura comune non banale. Ogni metodo ammissibile raffina una gerarchia di cluster sufficientemente separati ( $T_{glob}^\eta$ per una certa sequenza di margini $\eta$ ). Inoltre, qualsiasi collezione finita di metodi ammissibili condivide una spina dorsale comune.
Assenza di un Minimo Elemento: Il metodo triviale (che restituisce solo i singleton e la radice) è l'infimo nello spazio di tutti i metodi gerarchici ma non è ammissibile perché fallisce la ricchezza della partizione. Pertanto, la classe ammissibile non ha un minimo elemento.

3. Forte Ammissibilità e Ultrametrici
Quando viene aggiunto l'assioma dell'esattezza sugli ultrametrici, la classe diventa fortemente ammissibile ( $H_{\alpha_{adm}^+}(X)$ ).

Questa classe rimane incontabile e mantiene la diversità degli elementi massimi.
Fondamentalmente, a differenza della classe ammissibile canonica, la classe fortemente ammissibile possiede un minimo elemento: $T_{glob}$ (il metodo con sequenza di margini $\eta = \mathbf{1}$ ). Questo fornisce un metodo più grossolano tra quelli fortemente ammissibili.

4. Pre-processing e Composizione
Il documento studia le trasformazioni di pre-processing $\mu: D(X) \to D(X)$ applicate prima del clustering.

Condizioni di Preservazione: Gli autori derivano condizioni generali sotto le quali una trasformazione preserva gli assiomi (ad esempio, la scala commuta con $\mu$ , i rafforzamenti mappano in rafforzamenti).
Esempi:
- Minimax-path (Ultrametrico Subdominante): La trasformazione $B^*$ che mappa una dissimilarità nel suo ultrametrico subdominante preserva l'invarianza di scala, l'invarianza di permutazione e l'esattezza ultrametrica. Ciò porta alla fattorizzazione $T_{SL} = T_{glob} \circ B^*$ , mostrando il single linkage come composizione di una trasformazione ultrametrica e di un metodo di separazione.
- PCA e HDBSCAN: Il documento analizza il pre-processing PCA e la mutua raggiungibilità (mutual-reachability), mostrando che preservano l'invarianza di scala e di permutazione ma generalmente falliscono nel preservare ricchezza o coerenza.

Significato
Il documento dimostra che l'impossibilità fondamentale di soddisfare gli assiomi di Kleinberg è un artefatto derivante dal limitare l'output a partizioni piatte. Passando a output gerarchici, gli assiomi diventano congiuntamente soddisfacibili, aprendo la strada a un vasto panorama di metodi ammissibili.

Il lavoro rivela che, sebbene lo spazio dei metodi ammissibili sia estremamente diversificato (mancando di una soluzione ottimale univoca), esso non è privo di struttura. Gli assiomi impongono una spina dorsale "conservativa" di cluster ben separati che tutti i metodi ammissibili devono rispettare, pur permettendo libertà nel modo in cui vengono risolte le strutture più fini. Ciò fornisce un quadro principale per comprendere i compromessi nel clustering gerarchico e suggerisce che la scelta di un metodo specifico all'interno della classe ammissibile dipenda dal bilanciamento desiderato tra sensibilità al rumore e granularità dell'output, piuttosto che dalla violazione di principi assiomatici fondamentali.

Gli autori osservano che questo quadro si collega ai lavori precedenti di Carlsson e Mémoli (2010) e Ackerman e Ben-David (2016), ma differisce concentrandosi su gerarchie non pesate e mantenendo la piena forza dell'assioma di coerenza di Kleinberg, risultando in una classe di metodi più ampia e diversificata piuttosto che in una caratterizzazione di un singolo algoritmo.

Articoli simili