Che cos'è il clustering gerarchico?

Il clustering è una tecnica di machine learning non supervisionato, utilizzata nell'analisi dei dati per rilevare e raggruppare oggetti simili. L'analisi gerarchica dei cluster (HCA), o clustering gerarchico, raggruppa gli oggetti in una gerarchia di cluster senza imporre un ordine lineare al loro interno. Molte discipline, come la biologia, l'analisi delle immagini e le scienze sociali, utilizzano metodi di clustering gerarchico per esplorare e riconoscere i modelli nei set di dati. I casi d'uso includono la categorizzazione delle popolazioni nella ricerca clinica, la segmentazione dei clienti e il rilevamento di comunità di nodi nei modelli di rete.

Esistono due tipi di clustering gerarchico:

- Approccio agglomerativo o bottom-up¹ che unisce ripetutamente i cluster in gruppi più grandi fino a formare un unico cluster.

- Approccio divisivo o top-down che² inizia con tutti i dati in un singolo cluster e continua a suddividere i cluster successivi fino a quando tutti i cluster sono singoli.

L'analisi gerarchica dei cluster ha costi computazionali elevati. Sebbene l'utilizzo di un heap possa ridurre i tempi di calcolo, i requisiti di memoria aumentano. Sia il tipo di clustering divisivo che quello agglomerativo sono "avidi", il che significa che l'algoritmo decide quali cluster unire o dividere facendo la scelta ottimale a livello locale in ogni fase del processo. È anche possibile applicare un criterio di arresto, in cui l'algoritmo interrompe l'agglomerazione o la divisione dei cluster quando raggiunge un numero predeterminato di cluster.

Un diagramma ad albero chiamato dendrogramma³ viene spesso utilizzato per visualizzare la gerarchia dei cluster. Mostra l'ordine in cui i cluster sono stati uniti o divisi e mostra la somiglianza o la distanza tra i punti dati. I dendrogrammi possono anche essere intesi come un elenco annidato di^elenchi4 con attributi.

Gli algoritmi di clustering gerarchico utilizzano il concetto di matrice di dissomiglianza per decidere quali cluster unire o dividere. La dissomiglianza è la distanza tra due punti dati, misurata tramite il metodo di linkage scelto. I valori in una matrice di dissomiglianza esprimono:

- La distanza⁵, ad esempio una distanza euclidea, tra singoli punti in un insieme

- Un criterio di clustering basato sul linkage, che specifica la dissomiglianza come funzione delle distanze a coppie tra i punti nei vari set

Esploriamo i metodi di linkage della distanza euclidea più comuni. Esempi di altre metriche di distanza che possono essere utilizzate includono Minkowski, Hamming, Mahalanobis, Hausdorf e la distanza di Manhattan. È importante notare che ogni metodo di linkage genera cluster diversi dallo stesso set di dati. La selezione del metodo di clustering di linkage appropriato dipende da fattori come il tipo di dati da raggruppare, la densità dei dati, la forma del cluster e la presenza di valori anomali o anomalie nel set di dati.

Il metodo di linkage singolo analizza le distanze a coppie tra gli elementi in due cluster e quindi utilizza la distanza minima tra i cluster. Il metodo min gestisce bene le forme dei cluster non ellittiche, ma sarà influenzato dal rumore e dagli outlier. Ha una limitazione nota come effetto di concatenamento⁶. Alcuni punti che creano un ponte tra una coppia di cluster danno vita alla fusione di due cluster in uno. I criteri di linkage minimo possono essere rappresentati come:

 mina∈A,b∈Bd(a,b)

dove A e B sono due insiemi di osservazioni e d è una funzione di distanza.

Le distanze tra i cluster possono anche essere calcolate in base ai punti che sono più lontani tra loro. Il metodo max è meno sensibile al rumore e agli outlier rispetto al metodo min, ma il suo utilizzo può distorcere i risultati quando ci sono cluster globulari o di grandi dimensioni. Il linkage massimo spesso produce cluster più sferici rispetto al linkage minimo. Il linkage massimo può essere rappresentato dalla formula:

 maxa∈A,b∈Bd(a,b)

dove A e B sono due insiemi di osservazioni e d è la distanza.

Questi metodi, introdotti da Sokal e Michener⁷ , definiscono la distanza tra i cluster come la distanza media tra le coppie su tutte le coppie di punti dei cluster. L'algoritmo può essere il metodo dei gruppi di coppie non ponderati con media aritmetica (UPGMA) o il metodo dei gruppi di coppie ponderati con media aritmetica (WPGMA). Qui, il significato di "non ponderato" è che tutte le distanze contribuiscono equamente a ciascuna media.

UPGMA è rappresentato dalla formula

 1∣A∣·∣B∣∑a∈A∑b∈Bd(a,b)

dove *A* e *B* sono due serie di osservazioni e *d* è la distanza.

WPGMA è rappresentato dalla formula

 d(i∪j,k)=d(i,k)+d(j,k)2

dove i e j sono i cluster più vicini che vengono combinati in ogni fase per formare un nuovo cluster dell'unione di i e j. Possiamo quindi calcolare la distanza da un altro cluster k, che è la media aritmetica delle distanze medie tra i punti dati in k e i e k e j.

Qui utilizziamo la distanza tra i centri dei cluster o centroidi. La distanza tra i centroidi viene calcolata utilizzando una funzione di distanza:

∥μA-μB∥2

dove μ_A è il centroide di A e μ_B è il centroide di B.

Joe H. Ward ha introdotto il metodo⁸ dell'aumento minimo della somma dei quadrati (MISQ) negli anni '60. Ogni punto dati inizia nel proprio cluster. Questo approccio significa che la somma dei quadrati tra i punti dati è inizialmente pari a zero, poi aumenta via via che uniamo i cluster. Il metodo di Ward riduce al minimo la somma delle distanze quadrate dei punti dai centri del cluster via via che vengono uniti. Il metodo di Ward è una buona scelta per le variabili quantitative⁹ ed è meno influenzato dal rumore o dagli outlier. Può essere rappresentato come:

 ∣A∣·∣B∣A∪B∥μA-μB∥2=∑x∈A∪B∥x-μA∪B∥2-∑x∈A∥x-μA∥2-∑x∈B∥x-μB∥2

dove la media di A e la media di B sono rispettivamente i centroidi di A e B, e x è un punto dati che appartiene all'unione di A e B

Il metodo della varianza minima di Ward può essere perfezionato utilizzando un algoritmo di Lance-Williams. Questi algoritmi utilizzano una formula ricorsiva per aggiornare le distanze dei cluster e trovare la coppia di cluster ottimale più vicina da unire.

Nel clustering gerarchico agglomerativo, noto anche come annidamento agglomerativo (AGNES), ogni punto dati inizia come un cluster. L'algoritmo utilizza un criterio di clustering di linkage selezionato, basato su una matrice di dissomiglianza, per decidere quale coppia di cluster unire. L'algoritmo sposta la gerarchia e continua ad associare i cluster finché tutto non è stato collegato, creando una serie gerarchica di cluster nidificati. In breve, le fasi del cluster agglomerativo¹⁰ sono:

1. Calcolare la matrice di dissomiglianza utilizzando una particolare metrica di distanza.

2. Assegnare ogni punto dati a un cluster.

3. Unire i cluster in base a un criterio di linkage per la similarità tra i cluster.

4. Aggiornare la matrice della distanza.

5. Ripetere i passaggi 3 e 4 finché non rimane un singolo cluster o non viene soddisfatto un criterio di arresto.

I principi alla base del cluster gerarchico divisivo sono stati sviluppati da Macnaughton-Smith e altri¹¹ nel 1964 ed esplorati ulteriormente da Kaufman e Rousseeuw con il loro algoritmo DIANA (Divisive ANAlysis cluster)¹² nel 1990. Il cluster divisivo utilizza l'approccio opposto al cluster agglomerativo. Tutti i punti dati iniziano in un singolo cluster che viene ripetutamente suddiviso in più cluster. La suddivisione avviene fino a quando tutti i cluster rimanenti non sono singoli o non viene soddisfatto un criterio di arresto, ad esempio un numero predefinito di cluster. I metodi divisivi sono migliori nell'identificare cluster di grandi dimensioni¹³ e possono essere più accurati dei metodi agglomerativi, perché l'algoritmo considera l'intera distribuzione del set di dati dall'inizio del processo.

Per migliorare l'efficienza, i metodi divisivi utilizzano algoritmi di clustering piatto come k-means per suddividere il set di dati in cluster. Il numero di cluster deve essere specificato in anticipo. L'algoritmo k-means divide i cluster riducendo al minimo la somma dei quadrati all'interno del cluster tra i punti baricentrici. Questo è noto come criterio di inerzia¹⁴. Le fasi¹⁵ del cluster divisivo sono:

1. Iniziare con tutti i punti dati per un set di dati di dimensione N (d1, d2, d3... dN) in un unico cluster.

2. Dividere il cluster in due cluster dissimili o eterogenei utilizzando un metodo di clustering piatto come l'algoritmo k-means.

3. Ripetere il passaggio 2, scegliendo il cluster migliore da dividere e rimuovendo gli outlier dal cluster meno coeso dopo ogni iterazione.

4. Interrompere quando ogni esempio è nel suo singolo cluster, altrimenti ripetere il passaggio 3.

I risultati dei cluster sono in genere presentati in un dendrogramma (struttura ad albero binaria). L'asse xnel dendrogramma rappresenta i punti dati e l'asse y, o l'altezza delle linee, mostra la distanza tra i cluster quando sono stati uniti.

Puoi usare un dendrogramma per decidere quanti cluster¹⁶ saranno nel tuo modello di clustering finale. Una strategia consiste nell'identificare il punto di taglio naturale nell'albero in cui i rami diminuiscono e si allungano. In alternativa, il numero di cluster è dato dal numero di linee verticali attraversate quando una linea orizzontale taglia il dendrogramma.

Nell'immagine di esempio mostrata qui, la linea orizzontale H1 taglia due linee verticali. Ciò dimostra che ci sono due cluster a questo punto del processo: un cluster con i punti 5, 8 e 2 e un cluster con i punti rimanenti. Più la linea orizzontale può spostarsi verso l'alto o verso il basso senza tagliare altre linee orizzontali nel dendrogramma, migliore è la selezione di questo numero di cluster per il modello di clustering. Nell'esempio seguente, la linea orizzontale H2 seleziona quattro cluster. H2 non è in grado di spostare su e giù fino a H1 prima di tagliare altre linee orizzontali. Questo scenario mostra che la scelta a due cluster (H1) è probabilmente più appropriata per il suo modello di cluster.

Un modello di clustering robusto¹⁷ crea cluster con elevata somiglianza intraclasse e bassa somiglianza interclasse. Tuttavia, può essere difficile definire la qualità dei cluster, mentre la selezione del criterio di linkage e dei numeri dei cluster può influire in modo significativo sui tuoi risultati. Pertanto, quando crei un modello di cluster, prova diverse opzioni e seleziona quelle che meglio ti aiutano a esplorare e rivelare i modelli nel set di dati per considerazioni future. I fattori da considerare¹⁸ includono:

- Il numero di cluster che sono pratici o logici per il set di dati (date le dimensioni del set di dati, le forme dei cluster, il rumore e così via)

- Statistiche, come i valori medi, massimi e minimi per ogni cluster

- La migliore metrica di dissomiglianza o il miglior criterio di linkage da applicare

- L'impatto di eventuali outlier o variabili di risultato

- Qualsiasi conoscenza specifica del dominio o del set di dati

Altri metodi per determinare il numero ottimale di cluster¹⁹ includono:

- Il metodo a gomito, in cui si traccia la somma dei quadrati all'interno del cluster rispetto al numero di cluster e si determina il "gomito" (il punto in cui il grafico si livella)

- Statistica del gap, in cui si confronta la somma effettiva dei quadrati all'interno del cluster con la somma dei quadrati all'interno del cluster attesa per una distribuzione di riferimento nulla e si identifica il gap più grande.

Il clustering gerarchico fornisce ai data scientist insight sulla struttura e sulle relazioni all'interno dei set di dati e può essere applicato in diversi casi d'uso.

Il clustering gerarchico può aiutare ad analizzare le tendenze e a segmentare i dati dei clienti, ad esempio raggruppandoli per scelta del prodotto, dati demografici, comportamento di acquisto, profilo di rischio o interazioni con i social media.

Le coorti di pazienti per la ricerca clinica possono ammontare a migliaia. Il cluster gerarchico aiuta a classificare le popolazioni miste in gruppi più omogenei²⁰ utilizzando, ad esempio, criteri diagnostici, risposte fisiologiche o mutazioni del DNA. Può essere applicato anche per raggruppare le specie in base alle caratteristiche biologiche, per comprendere lo sviluppo evolutivo.

Il clustering gerarchico viene utilizzato nelle applicazioni di riconoscimento del testo basate su immagini per raggruppare i caratteri scritti a mano in base alla loro forma. Viene anche utilizzato per memorizzare e recuperare informazioni utilizzando determinati criteri o per categorizzare i risultati della ricerca.

Sia Python che il linguaggio di programmazione R sono ampiamente utilizzati nella data science. Python è flessibile e può gestire un ampio spettro di attività. R, invece, è specificamente progettato per il calcolo statistico e offre numerose opzioni per la visualizzazione dell'analisi gerarchica dei cluster.

Python fornisce la funzione AgglomerativeCluster²¹ (vedi anche esempi di cluster agglomerativo²² su sklearn) e SciPy fornisce una funzione per tracciare i dendrogrammi²³. Pacchetti come dendextend²⁴ potenziano la funzionalità dei dendrogrammi di R, migliorando l'analisi della sensibilità e consentendole di confrontare e manipolare diversi dendrogrammi. Per un'esperienza pratica, consulta i nostri tutorial: come implementare il cluster gerarchico in Python e come implementare il cluster gerarchico in R.