Clustering gerarchico in R

Operazioni di pre-processing per il clustering

Ci sono un paio di cose di cui dovresti occuparti prima di iniziare.

• Scaling

È fondamentale normalizzare la scala dei valori delle feature per iniziare il processo di clustering. Questo perché i valori delle feature di ciascuna osservazione sono rappresentati come coordinate in uno spazio n-dimensionale (n è il numero di feature) e poi si calcolano le distanze tra queste coordinate. Se queste coordinate non sono normalizzate, potresti ottenere risultati fuorvianti.

Per esempio, supponi di avere dati su altezza e peso di tre persone: A (6ft, 75kg), B (6ft,77kg), C (8ft,75kg). Se rappresenti queste feature in un sistema di coordinate bidimensionale, altezza e peso, e calcoli la distanza euclidea tra di loro, le distanze tra le seguenti coppie sarebbero:

A-B : 2 unità

A-C : 2 unità

Ebbene, la metrica di distanza indica che entrambe le coppie A-B e A-C sono simili, ma in realtà non è così! La coppia A-B è più simile della coppia A-C. Perciò è importante scalare prima questi valori e poi calcolare la distanza.

Esistono vari modi per normalizzare i valori delle feature: puoi considerare di standardizzare l’intera scala di tutti i valori delle feature (x(i)) tra [0,1] (nota come normalizzazione min-max) applicando la seguente trasformazione:

$ x(s) = x(i) - min(x)/(max(x) - min (x)) $

Puoi usare la funzione normalize() di R per questo, oppure scrivere una tua funzione come:

standardize <- function(x){(x-min(x))/(max(x)-min(x))}

Un altro tipo di scaling può essere ottenuto tramite la seguente trasformazione:

$ x(s) = x(i)-mean(x) / sd(x) $

Dove sd(x) è la deviazione standard dei valori della feature. Questo farà sì che la distribuzione dei valori delle feature abbia media 0 e deviazione standard 1. Puoi ottenerlo tramite la funzione scale() in R.

• Imputazione dei valori mancanti

È anche importante gestire in anticipo i valori missing/null/inf nel tuo dataset. Ci sono molti modi per affrontarli: puoi rimuoverli oppure imputarli con media, mediana, moda o usare tecniche di regressione avanzate. R ha molti pacchetti e funzioni per l’imputazione dei valori mancanti come impute(), Amelia, Mice, Hmisc ecc. Puoi leggere di Amelia in questo tutorial.

Algoritmo di clustering gerarchico

L’operazione chiave nel clustering gerarchico agglomerativo è combinare ripetutamente i due cluster più vicini in un cluster più grande. Ci sono tre domande chiave a cui rispondere per prime:

• Come rappresenti un cluster con più di un punto?
• Come determini la “vicinanza” dei cluster?
• Quando smetti di combinare i cluster?

Speriamo che alla fine di questo tutorial tu riesca a rispondere a tutte queste domande. Prima di applicare il clustering gerarchico, vediamo come funziona:

1. Inizia calcolando la distanza tra ogni coppia di punti di osservazione e la memorizza in una matrice delle distanze.
2. Poi mette ogni punto nel proprio cluster.
3. Quindi inizia a unire le coppie di punti più vicine in base alle distanze della matrice delle distanze e, di conseguenza, il numero di cluster diminuisce di 1.
4. Ricalcola poi la distanza tra il nuovo cluster e quelli vecchi e le memorizza in una nuova matrice delle distanze.
5. Infine ripete i passaggi 2 e 3 finché tutti i cluster non sono uniti in un unico cluster.

Ci sono diversi modi per misurare la distanza tra i cluster per decidere le regole di raggruppamento, spesso chiamati metodi di collegamento (Linkage Methods). Alcuni dei metodi più comuni sono:

• Complete-linkage: calcola la distanza massima tra i cluster prima di unirli.

• Single-linkage: calcola la distanza minima tra i cluster prima di unirli. Questo collegamento può essere usato per rilevare valori alti nel dataset che potrebbero essere outlier, poiché verranno uniti alla fine.

• Average-linkage: calcola la distanza media tra i cluster prima di unirli.

• Centroid-linkage: trova il centroide del cluster 1 e il centroide del cluster 2 e calcola la distanza tra i due prima di unirli.

La scelta del metodo di collegamento dipende interamente da te e non esiste un metodo rigido che dia sempre buoni risultati. Metodi di collegamento diversi portano a cluster diversi.

Dendrogrammi

Nel clustering gerarchico, gli oggetti vengono organizzati in una gerarchia simile a un diagramma ad albero chiamato dendrogramma. La distanza di divisione o unione (chiamata altezza) è mostrata sull’asse y del dendrogramma qui sotto.

Nella figura sopra, per primi 4 e 6 sono combinati in un cluster, diciamo cluster 1, poiché erano i più vicini in distanza, seguiti dai punti 1 e 2, cioè cluster 2. Successivamente 5 è stato unito nello stesso cluster 1, seguito da 3, ottenendo due cluster. Infine, i due cluster sono uniti in un unico cluster e qui si ferma il processo di clustering.

Una domanda che potresti esserti posto a questo punto è: come decidi quando smettere di unire i cluster? Dipende dalle conoscenze di dominio che hai sui dati. Per esempio, se stai raggruppando i calciatori in campo in base alle loro posizioni, che rappresentano le coordinate per il calcolo delle distanze, sai già che dovresti finire con soli 2 cluster, perché in una partita di calcio ci sono solo due squadre.

Ma a volte non hai nemmeno quell’informazione. In tali casi, puoi sfruttare i risultati del dendrogramma per approssimare il numero di cluster. Tagli l’albero del dendrogramma con una linea orizzontale a un’altezza in cui la linea può attraversare la massima distanza su e giù senza intersecare il punto di unione. Nel caso sopra sarebbe tra le altezze 1,5 e 2,5 come mostrato:

Se effettui il taglio come mostrato, otterrai solo due cluster.

Nota che non è necessario tagliare solo in quei punti: puoi scegliere qualsiasi punto come livello di taglio a seconda di quanti cluster vuoi. Per esempio, un taglio sotto 1,5 e sopra 1 darà 3 cluster.

Nota non è una regola rigida per decidere il numero di cluster. Puoi anche considerare grafici come il Silhouette plot, l’elbow plot, o misure numeriche come l’indice di Dunn, il gamma di Hubert, ecc., che mostrano la variazione dell’errore al variare del numero di cluster (k), e scegliere il valore di k in cui l’errore è minimo.

Valutare la bontà dei cluster

Forse la parte più importante in qualsiasi compito di apprendimento non supervisionato è l’analisi dei risultati. Dopo aver eseguito il clustering con qualsiasi algoritmo e set di parametri, devi assicurarti di aver fatto bene. Ma come lo determini?

Esistono molte misure per farlo; forse la più popolare è il Dunn's Index. L’indice di Dunn è il rapporto tra la distanza inter-cluster minima e il diametro intra-cluster massimo. Il diametro di un cluster è la distanza tra i suoi due punti più lontani. Per avere cluster ben separati e compatti dovresti puntare a un indice di Dunn più alto.

Clustering gerarchico in pratica

Ora applicherai le conoscenze acquisite per risolvere un problema reale.

Applicherai il clustering gerarchico al dataset seeds. Questo dataset consiste in misurazioni di proprietà geometriche di cariossidi appartenenti a tre diverse varietà di grano: Kama, Rosa e Canadian. Ha variabili che descrivono le proprietà dei semi come area, perimetro, coefficiente di asimmetria, ecc. Ci sono 70 osservazioni per ciascuna varietà di grano. Puoi trovare i dettagli sul dataset qui.

Inizia importando il dataset in un dataframe con la funzione read.csv().

Nota che il file non ha intestazioni ed è separato da tabulazioni. Per mantenere la riproducibilità dei risultati devi usare la funzione set.seed().

set.seed(786)
file_loc <- 'seeds.txt'
seeds_df <- read.csv(file_loc,sep = '\t',header = FALSE)Offerto da

Poiché il dataset non ha nomi di colonna, assegnerai tu stesso i nomi delle colonne a partire dalla descrizione dei dati.

feature_name <- c('area','perimeter','compactness','length.of.kernel','width.of.kernal','asymmetry.coefficient','length.of.kernel.groove','type.of.seed')
colnames(seeds_df) <- feature_nameOfferto da

È consigliabile raccogliere alcune informazioni di base utili sul dataset, come dimensioni, tipi di dato e distribuzione, numero di NA, ecc. Lo farai usando le funzioni str(), summary() e is.na() in R.

str(seeds_df)
summary(seeds_df)
any(is.na(seeds_df))Offerto da

Nota che questo dataset ha tutte le colonne come valori numerici. Non ci sono valori mancanti da pulire prima del clustering. Tuttavia, le scale delle feature sono diverse e devi normalizzarle. Inoltre, i dati sono etichettati e hai già l’informazione su quale osservazione appartenga a quale varietà di grano.

Ora salverai le etichette in una variabile separata ed escluderai la colonna type.of.seed dal dataset per eseguire il clustering. In seguito userai le etichette vere per verificare quanto sia riuscito il tuo clustering.

seeds_label <- seeds_df$type.of.seed
seeds_df$type.of.seed <- NULL
str(seeds_df)Offerto da

Come noterai, hai rimosso la colonna delle etichette vere dal dataset.

Ora userai la funzione scale() di R per scalare tutti i valori delle colonne.

seeds_df_sc <- as.data.frame(scale(seeds_df))
summary(seeds_df_sc)Offerto da

Nota che la media di tutte le colonne è 0 e la deviazione standard è 1. Ora che hai pre-processato i dati, è il momento di costruire la matrice delle distanze. Poiché qui tutti i valori sono numerici continui, userai il metodo di distanza euclidean.

dist_mat <- dist(seeds_df_sc, method = 'euclidean')Offerto da

A questo punto dovresti decidere quale metodo di collegamento usare e procedere con il clustering gerarchico. Puoi provare tutti i tipi di metodi di collegamento e decidere in seguito quale ha funzionato meglio. Qui procederai con il metodo di collegamento average.

Costruirai il tuo dendrogramma tracciando l’oggetto di cluster gerarchico che creerai con hclust(). Puoi specificare il metodo di collegamento tramite l’argomento method.

hclust_avg <- hclust(dist_mat, method = 'average')
plot(hclust_avg)Offerto da

Nota come è costruito il dendrogramma e come ogni punto dati alla fine confluisce in un unico cluster con l’altezza (distanza) mostrata sull’asse y.

Successivamente puoi tagliare il dendrogramma per creare il numero desiderato di cluster. Poiché in questo caso sai già che potrebbero esserci solo tre tipi di grano, sceglierai il numero di cluster k = 3; oppure, come puoi vedere nel dendrogramma, con h = 3 ottieni tre cluster. Userai la funzione cutree() di R per tagliare l’albero con hclust_avg come primo parametro e l’altro parametro come h = 3 o k = 3.

cut_avg <- cutree(hclust_avg, k = 3)Offerto da

Se vuoi vedere visivamente i cluster sul dendrogramma puoi usare la funzione abline() di R per tracciare la linea di taglio e sovrapporre compartimenti rettangolari per ciascun cluster sull’albero con la funzione rect.hclust() come mostrato nel seguente codice:

plot(hclust_avg)
rect.hclust(hclust_avg , k = 3, border = 2:6)
abline(h = 3, col = 'red')Offerto da

Ora puoi vedere i tre cluster racchiusi in tre riquadri di colore diverso. Puoi anche usare la funzione color_branches() della libreria dendextend per visualizzare l’albero con rami di colori diversi.

Ricorda che puoi installare un pacchetto in R usando il comando install.packages('package_name', dependencies = TRUE).

suppressPackageStartupMessages(library(dendextend))
avg_dend_obj <- as.dendrogram(hclust_avg)
avg_col_dend <- color_branches(avg_dend_obj, h = 3)
plot(avg_col_dend)Offerto da

Ora aggiungerai i risultati di clustering ottenuti al dataframe originale nella colonna cluster con mutate() del pacchetto dplyr e conterai quante osservazioni sono state assegnate a ciascun cluster con la funzione count().

suppressPackageStartupMessages(library(dplyr))
seeds_df_cl <- mutate(seeds_df, cluster = cut_avg)
count(seeds_df_cl,cluster)Offerto da

Potrai vedere quante osservazioni sono state assegnate in ciascun cluster. Nota che, in realtà, dai dati etichettati avevi 70 osservazioni per ciascuna varietà di grano.

È comune valutare l’andamento tra due feature in base al clustering effettuato per estrarre informazioni più utili dai dati cluster per cluster. Come esercizio, puoi analizzare l’andamento tra perimeter e area del grano per cluster con l’aiuto del pacchetto ggplot2.

suppressPackageStartupMessages(library(ggplot2))
ggplot(seeds_df_cl, aes(x=area, y = perimeter, color = factor(cluster))) + geom_point()Offerto da

Nota che per tutte le varietà di grano sembra esserci una relazione lineare tra perimetro e area.

Poiché hai già le etichette vere per questo dataset, puoi anche considerare di verificare i risultati del clustering usando la funzione table().

table(seeds_df_cl$cluster,seeds_label)Offerto da

Se osservi la tabella generata, vedi chiaramente tre gruppi con 55 elementi o più. Nel complesso, puoi dire che i tuoi cluster rappresentano adeguatamente i diversi tipi di semi, perché originariamente avevi 70 osservazioni per ciascuna varietà di grano. I gruppi più grandi rappresentano la corrispondenza tra i cluster e i tipi reali.

Nota che in molti casi non hai effettivamente le etichette vere. In quei casi, come già discusso, puoi puntare ad altre misure come massimizzare l’indice di Dunn. Puoi calcolare l’indice di Dunn usando la funzione dunn() della libreria clValid. Inoltre, puoi considerare di convalidare incrociatamente i risultati creando train e test set, proprio come fai in altri algoritmi di machine learning, ed eseguire poi il clustering quando disponi delle etichette vere.

Confronto con l’algoritmo di clustering K-means

Probabilmente hai sentito parlare dell’algoritmo di clustering k-means; in caso contrario, dai un’occhiata a questo tutorial. Ci sono molte differenze fondamentali tra i due algoritmi, sebbene in casi diversi uno possa funzionare meglio dell’altro. Alcune differenze sono:

• Distanza usata: il clustering gerarchico può gestire virtualmente qualsiasi metrica di distanza, mentre k-means si basa sulle distanze euclidee.
• Stabilità dei risultati: k-means richiede uno step casuale in fase di inizializzazione che può produrre risultati diversi se il processo viene rieseguito. Questo non accade nel clustering gerarchico.
• Numero di cluster: mentre in k-means puoi usare elbow plot, Silhouette plot, ecc. per trovare il numero giusto di cluster, anche il gerarchico può usare tutti questi, con il vantaggio aggiuntivo di sfruttare il dendrogramma allo stesso scopo.
• Complessità computazionale: k-means è meno costoso computazionalmente del clustering gerarchico e può essere eseguito su dataset di grandi dimensioni in tempi ragionevoli, che è il principale motivo per cui k-means è più popolare.

Conclusione

Complimenti! Sei arrivato alla fine di questo tutorial. Hai imparato come pre-processare i dati, le basi del clustering gerarchico e le metriche di distanza e i metodi di collegamento su cui si basa, insieme al suo utilizzo in R. Sai anche in cosa il clustering gerarchico differisce dall’algoritmo k-means. Ben fatto! Ma c’è sempre molto altro da imparare. Ti suggerisco di dare un’occhiata al nostro corso Unsupervised Learning in R.