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 schemi 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'uso di un heap possa ridurre i tempi di calcolo, i requisiti di memoria aumentano. Sia il clustering divisivo che quello agglomerativo sono "avidi", il che significa che l'algoritmo decide quali cluster unire o dividere facendo la scelta localmente ottimale in ogni fase del processo. È anche possibile applicare un criterio di arresto, in cui l'algoritmo interrompe l'agglomerazione o la suddivisione dei cluster quando raggiunge un numero predefinito di cluster.

Un diagramma ad albero chiamato dendrogramma³ viene spesso utilizzato per visualizzare la gerarchia dei cluster. Visualizza l'ordine in cui i cluster sono stati uniti o divisi e mostra la similarità o la distanza tra i punti dati. I dendrogrammi possono anche essere intesi come una lista annidata di liste⁴ con attributi.

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

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

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

Esploriamo i metodi di linkage basati sulla distanza euclidea più comuni. Esempi di altre metriche di distanza che possono essere utilizzate includono le distanze di Minkowski, Hamming, Mahalanobis, Hausdorff e Manhattan. È importante notare che ogni metodo di linkage genera cluster differenti dallo stesso set di dati. La scelta del metodo di clustering basato sul linkage appropriato dipende da fattori come il tipo di dati da raggruppare, la densità dei dati, la forma dei cluster e la presenza di outlier o rumore nel set di dati.

Il metodo del single linkage analizza le distanze a coppie tra gli elementi di due cluster e poi utilizza la distanza minima tra i cluster. Il metodo min gestisce bene le forme di cluster non ellittiche, ma può essere influenzato dal rumore e dagli outlier. Ha una limitazione nota come effetto catena⁶. Pochi punti che creano un ponte tra due cluster possono far sì che i due cluster si uniscano in uno solo. I criteri di min linkage 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 max linkage spesso produce cluster più sferici rispetto al min linkage. Il max linkage 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 di punti in tutti i possibili accoppiamenti all'interno dei cluster. L'algoritmo può essere il metodo UPGMA (Unweighted Pair Group Method with Arithmetic mean) o il metodo WPGMA (Weighted Pair Group Method with Arithmetic mean). Il significato di "unweighted" (non ponderato) qui è che tutte le distanze contribuiscono in modo uguale 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 passaggio per formare un nuovo cluster dall'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 o i centroidi del cluster. 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 introdusse il metodo MISSQ (Minimal Increase of Sum of Squares)⁸ negli anni '60. Ogni punto dati inizia nel proprio cluster. Questo approccio significa che la somma dei quadrati delle distanze tra i punti dati è inizialmente pari a zero, per poi aumentare man mano che i cluster vengono uniti. Il metodo di Ward minimizza la somma delle distanze al quadrato dei punti dai centri dei cluster man mano che vengono uniti. Il metodo di Ward è una buona scelta per variabili quantitative⁹ e risulta meno influenzato da rumore o 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 cluster. L'algoritmo utilizza un criterio di clustering tramite linkage selezionato basato su una matrice di dissimilarità per decidere quale coppia di cluster unire. L'algoritmo risale nella gerarchia e continua a unire i cluster fino a quando tutto non è stato collegato, creando una serie gerarchica di cluster annidati. In parole povere, le fasi del clustering agglomerativo sono:

1. Calcolare la matrice di dissimilarità 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 delle distanze.

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 clustering gerarchico divisivo sono stati sviluppati da Macnaughton-Smith e altri¹¹ nel 1964 e ulteriormente esplorati da Kaufman e Rousseeuw con il loro algoritmo DIANA (Divisive ANAlysis clustering)¹² nel 1990. Il clustering divisivo utilizza l'approccio opposto al clustering agglomerativo. Tutti i punti dati iniziano in un singolo cluster che viene ripetutamente suddiviso in più cluster. La divisione continua fino a quando tutti i cluster rimanenti non sono singoli o viene raggiunto un criterio di arresto, come un numero predefinito di cluster. I metodi divisivi sono più efficaci nell'identificare grandi cluster¹³ e possono essere più precisi rispetto ai metodi agglomerativi, poiché l'algoritmo considera l'intera distribuzione del set di dati fin dall'inizio del processo.

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

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

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 binario). L'asse x nel dendrogramma rappresenta i punti dati e l'asse y, o altezza delle linee, mostra la distanza tra i cluster quando sono stati uniti.

È possibile utilizzare un dendrogramma per decidere quanti cluster¹⁶ saranno presenti nel modello di clustering finale. Una strategia consiste nell'identificare il punto di interruzione naturale nell'albero in cui i rami si riducono e si allungano. In alternativa, il numero di cluster è dato dal numero di linee verticali incrociate quando una linea orizzontale taglia il dendrogramma.

Nell'immagine di esempio mostrata qui, la linea orizzontale H1 taglia due linee verticali. Ciò dimostra che a questo punto del processo sono presenti due cluster: 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 sarà la selezione di questo numero di cluster per il modello di clustering. Nell'esempio seguente, la linea orizzontale H2 seleziona quattro cluster. H2 non riesce a spostarsi verso l'alto e verso il basso quanto H1 prima di tagliare altre linee orizzontali. Questo scenario mostra che la scelta dei due cluster (H1) è probabilmente più appropriata per questo modello di clustering.

Un solido modello di clustering¹⁷ crea cluster con elevata similarità intraclasse e bassa similarità interclasse. Tuttavia, può essere difficile definire la qualità del cluster, e la scelta del criterio di linkage e del numero di cluster può influenzare significativamente i risultati. Pertanto, quando si crea un modello di clustering è consigliabile provare diverse opzioni e scegliere quelle che aiutano meglio a esplorare e rivelare schemi 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 metriche di dissimilarità 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 del 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 informazioni 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 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.

I gruppi di pazienti per la ricerca clinica possono arrivare a migliaia. Il clustering gerarchico aiuta a categorizzare popolazioni miste in gruppi più omogenei²⁰ utilizzando, ad esempio, criteri diagnostici, risposte fisiologiche o mutazioni del DNA. Può anche essere applicato per raggruppare le specie in base a caratteristiche biologiche al fine di 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 offre la funzione AgglomerativeCluster²¹ (vedi anche gli esempi di clustering agglomerativo²² su sklearn), mentre SciPy offre una funzione per tracciare dendrogrammi²³. Pacchetti come dendextend²⁴ potenziano le funzionalità dei dendrogrammi in R, migliorando l'analisi di sensibilità e consentendo di confrontare e manipolare diversi dendrogrammi. Per un'esperienza pratica, consulta i nostri tutorial passo-passo: come implementare il clustering gerarchico in Python e come implementare il clustering gerarchico in R.