Serie di Apprendimento Non Supervisionato Esplorare il Clustering Gerarchico

'Unsupervised Learning Series Exploring Hierarchical Clustering'

Esploriamo come funziona la clustering gerarchica e come costruisce i cluster basati sulle distanze a coppie.

Nel mio ultimo post della serie Unsupervised Learning, abbiamo esplorato uno dei metodi di clustering più famosi, il Clustering K-means. In questo post, discuteremo i metodi di un’altra importante tecnica di clustering: la clustering gerarchica!

Questo metodo si basa anche sulle distanze (euclidee, manhattan, ecc.) e utilizza una rappresentazione gerarchica dei dati per combinare i punti dati. A differenza di K-means, non contiene alcun iperparametro riguardante il numero di centroidi (come k) che i data scientist possono configurare.

In generale, la clustering gerarchica può essere divisa in due gruppi: clustering agglomerativo e clustering divisivo. Nel primo, i punti dati sono considerati unità singole e vengono aggregati ai punti dati vicini in base alle distanze. Nel secondo, consideriamo tutti i punti dati come un singolo cluster e iniziamo a dividerli in base a determinati criteri. Poiché la versione agglomerativa è la più famosa e ampiamente utilizzata (l’implementazione integrata di sklearn segue questo protocollo), questo è il tipo di clustering gerarchico che esploreremo in questo post.

In questo post del blog affronteremo la Clustering Gerarchica Agglomerativa in due fasi:

• Samsung adotta l’AI e il Big Data, rivoluziona il processo di produzione dei chip.
• Modello SARIMA per la previsione dei tassi di cambio valuta.
• Suggerimenti su Matplotlib per migliorare istantaneamente le tue visualizzazioni dei dati – Secondo Storytelling with Data

• In primo luogo, faremo un’analisi passo passo di come vengono costruite le gerarchie, utilizzando il clustering agglomerativo con il metodo medio (uno dei metodi che possiamo utilizzare per costruire la gerarchia dei punti dati).
• Poi, vedremo alcuni esempi di come adattare un clustering gerarchico su un dataset reale utilizzando l’implementazione di sklearn. Qui dettaglieremo anche altri metodi che possiamo utilizzare per costruire le nostre gerarchie (ward, minimo, ecc.)

Cominciamo!

Esempio di Clustering Agglomerativo – Passo dopo Passo

Nel nostro esempio passo dopo passo, utilizzeremo un dataset immaginario con 5 clienti:

Immaginiamo di gestire un negozio con 5 clienti e vogliamo raggruppare questi clienti in base alle loro somiglianze. Abbiamo due variabili che vogliamo considerare: l’età del cliente e il loro reddito annuo.

Il primo passo del nostro clustering agglomerativo consiste nel creare distanze a coppie tra tutti i nostri punti dati. Facciamo proprio questo rappresentando ogni punto dati con le loro coordinate in formato [x, y]:

• Distanza tra [60, 30] e [60, 55]: 25.0
• Distanza tra [60, 30] e [30, 75]: 54.08
• Distanza tra [60, 30] e [41, 100]: 72.53
• Distanza tra [60, 30] e [38, 55]: 33.30
• Distanza tra [60, 55] e [30, 75]: 36.06
• Distanza tra [60, 55] e [41, 100]: 48.85
• Distanza tra [60, 55] e [38, 55]: 22.0
• Distanza tra [30, 75] e [41, 100]: 27.31
• Distanza tra [30, 75] e [38, 55]: 21.54
• Distanza tra [41, 100] e [38, 55]: 45.10

Anche se possiamo utilizzare qualsiasi tipo di metrica di distanza che vogliamo, useremo quella euclidea per la sua semplicità. Dalle distanze a coppie che abbiamo calcolato sopra, quale distanza è la più piccola?

La distanza tra i clienti di mezza età che guadagnano meno di 90.000 dollari all’anno – i clienti alle coordinate [30, 75] e [38, 55]!

Rivedendo la formula per la distanza euclidea tra due punti arbitrari p1 e p2:

Visualizziamo la nostra distanza più piccola sul grafico 2D collegando i due clienti più vicini:

Il passo successivo della clustering gerarchica è considerare questi due clienti come il nostro primo cluster!

Successivamente, calcoleremo nuovamente le distanze tra i punti dati. Ma questa volta, i due clienti che abbiamo raggruppato in un singolo cluster saranno trattati come un singolo punto dati. Ad esempio, consideriamo il punto rosso qui sotto che si posiziona nel mezzo dei due punti dati:

In sintesi, per le prossime iterazioni della nostra soluzione gerarchica non considereremo le coordinate dei punti dati originali (emoji) ma il punto rosso (la media tra quei punti dati). Questo è il modo standard per calcolare le distanze sul metodo di linkage medio.

Altri metodi che possiamo utilizzare per calcolare le distanze basate sui punti dati aggregati sono:

• Massimo (o linkage completo): considera il punto dati più lontano nel cluster relativo al punto che stiamo cercando di aggregare.
• Minimo (o linkage singolo): considera il punto dati più vicino nel cluster relativo al punto che stiamo cercando di aggregare.
• Ward (o linkage di Ward): minimizza la varianza nei cluster con l’aggregazione successiva.

Facciamo una breve pausa sulla spiegazione passo-passo per approfondire un po’ i metodi di linkage poiché sono cruciali in questo tipo di clustering. Ecco un esempio visivo dei diversi metodi di linkage disponibili nella clustering gerarchica, per un esempio fittizio di 3 cluster da unire:

Nell’implementazione di sklearn, saremo in grado di sperimentare alcuni di questi metodi di linkage e vedere una differenza significativa nei risultati di clustering.

Tornando all’esempio, ora generiamo le distanze tra tutti i nostri nuovi punti dati – ricorda che ci sono due cluster che vengono trattati come uno solo da ora in poi:

• Distanza tra [60, 30] e [60, 55]: 25.0
• Distanza tra [60, 30] e [34, 65]: 43.60
• Distanza tra [60, 30] e [41, 100]: 72.53
• Distanza tra [60, 55] e [34, 65]: 27.85
• Distanza tra [60, 55] e [41, 100]: 48.85
• Distanza tra [34, 65] e [41, 100]: 35.69

Qual è la distanza più breve? È il percorso tra i punti dati sulle coordinate [60, 30] e [60, 55]:

Il passo successivo è, naturalmente, unire questi due clienti in un singolo cluster:

Con questo nuovo paesaggio di cluster, calcoliamo di nuovo le distanze a coppie! Ricorda che stiamo sempre considerando la media tra i punti dati (a causa del metodo di linkage che abbiamo scelto) in ciascun cluster come punto di riferimento per il calcolo della distanza:

• Distanza tra [60, 42.5] e [34, 65]: 34,38
• Distanza tra [60, 42.5] e [41, 100]: 60,56
• Distanza tra [34, 65] e [41, 100]: 35,69

Interessantemente, i prossimi punti dati da aggregare sono i due cluster poiché si trovano sulle coordinate [60, 42,5] e [34, 65]:

Infine, terminiamo l’algoritmo aggregando tutti i punti dati in un unico grande cluster:

Tenendo presente questo, dove ci fermiamo esattamente? Probabilmente non è una grande idea avere un unico grande cluster con tutti i punti dati, giusto?

Per sapere dove ci fermiamo, ci sono alcune regole euristiche che possiamo usare. Ma prima, dobbiamo familiarizzare con un altro modo di visualizzare il processo che abbiamo appena fatto – il dendrogramma:

Sull’asse y, abbiamo le distanze che abbiamo appena calcolato. Sull’asse x, abbiamo ogni punto dati. Salendo da ogni punto dati, raggiungiamo una linea orizzontale – il valore dell’asse y di questa linea indica la distanza totale che collegherà i punti dati sui bordi.

Ricorda i primi clienti che abbiamo connesso in un singolo cluster? Quello che abbiamo visto nel grafico 2D corrisponde al dendrogramma poiché sono esattamente i primi clienti connessi utilizzando una linea orizzontale (salendo il dendrogramma dal basso):

Le linee orizzontali rappresentano il processo di fusione che abbiamo appena fatto! Naturalmente, il dendrogramma termina in una grande linea orizzontale che connette tutti i punti dati.

Dopo esserci familiarizzati con il dendrogramma, siamo pronti per verificare l’implementazione di sklearn e utilizzare un vero dataset per capire come possiamo selezionare il numero appropriato di cluster basandoci su questo fantastico metodo di clustering!

Implementazione Sklearn

Per l’implementazione di Sklearn, userò il dataset sulla qualità del vino disponibile qui.

wine_data = pd.read_csv('winequality-red.csv', sep=';')wine_data.head(10)

Questo dataset contiene informazioni sui vini (in particolare i vini rossi) con diverse caratteristiche come l’acido citrico, i cloruri o la densità. L’ultima colonna del dataset riguarda la qualità del vino, una classificazione effettuata da una giuria.

Dato che la clustering gerarchica si occupa di distanze e useremo la distanza euclidea, dobbiamo standardizzare i nostri dati. Inizieremo usando un StandardScaler sui nostri dati:

from sklearn.preprocessing import StandardScalersc = StandardScaler()wine_data_scaled = sc.fit_transform(wine_data)

Con il nostro dataset standardizzato, possiamo adattare la nostra prima soluzione di clustering gerarchico! Possiamo accedere al clustering gerarchico creando un oggetto AgglomerativeClustering:

average_method = AgglomerativeClustering(n_clusters = None,                                          distance_threshold = 0,                                          linkage = 'average')average_method.fit(wine_data_scaled)

Dettaglio gli argomenti che stiamo usando all’interno di AgglomerativeClustering:

• n_clusters=None viene utilizzato come modo per avere la soluzione completa dei cluster (e dove possiamo produrre il dendrogramma completo).
• distance_threshold = 0 deve essere impostato nell’implementazione di sklearn per produrre il dendrogramma completo.
• linkage = 'average' è un iperparametro molto importante. Ricorda che, nell’implementazione teorica, abbiamo descritto un metodo per considerare le distanze tra i cluster di nuova formazione. average è il metodo che considera il punto medio tra ogni nuovo cluster formato nel calcolo delle nuove distanze. Nell’implementazione di sklearn, abbiamo anche altri tre metodi che abbiamo descritto: single, complete e ward.

Dopo aver adattato il modello, è il momento di rappresentare il nostro dendrogramma. Per questo, userò la funzione di supporto fornita nella documentazione di sklearn:

from scipy.cluster.hierarchy import dendrogramdef plot_dendrogram(model, **kwargs):    # Creiamo una matrice di linkage e poi rappresentiamo il dendrogramma    # creiamo i conteggi dei campioni sotto ogni nodo    counts = np.zeros(model.children_.shape[0])    n_samples = len(model.labels_)    for i, merge in enumerate(model.children_):        current_count = 0        for child_idx in merge:            if child_idx < n_samples:                current_count += 1  # nodo foglia            else:                current_count += counts[child_idx - n_samples]        counts[i] = current_count    linkage_matrix = np.column_stack(        [model.children_, model.distances_, counts]    ).astype(float)    # Rappresentiamo il dendrogramma corrispondente    dendrogram(linkage_matrix, **kwargs)

Se rappresentiamo la nostra soluzione di clustering gerarchico:

plot_dendrogram(average_method, truncate_mode="level", p=20)plt.title('Dendrogramma del clustering gerarchico - Metodo medio')

Il dendrogramma non è ottimale poiché le nostre osservazioni sembrano essere un po’ sovrapposte. A volte, il linkage average, single e complete possono produrre dendrogrammi strani, in particolare quando ci sono forti outlier nei dati. Il metodo ward potrebbe essere appropriato per questo tipo di dati, quindi testiamolo:

ward_method = AgglomerativeClustering(n_clusters = None,                                          distance_threshold = 0,                                          linkage = 'ward')ward_method.fit(wine_data_scaled)plot_dendrogram(ward_method, truncate_mode="level", p=20)

Molto meglio! Notare che i cluster sembrano essere meglio definiti secondo il dendrogramma. Il metodo di Ward cerca di dividere i cluster minimizzando l’intra-varianza tra i nuovi cluster formati (https://online.stat.psu.edu/stat505/lesson/14/14.7) come abbiamo descritto nella prima parte del post. L’obiettivo è che ad ogni iterazione i cluster aggregati minimizzino la varianza (distanza tra i punti dati e il nuovo cluster da formare).

Di nuovo, cambiare il metodo può essere raggiunto cambiando il parametro linkage nella funzione AgglomerativeClustering!

Dato che siamo soddisfatti dell’aspetto del dendrogramma del metodo ward, utilizzeremo quella soluzione per la profilazione dei cluster:

Riuscite ad indovinare quanti cluster dovremmo scegliere?

In base alle distanze, un buon candidato è tagliare il dendrogramma in questo punto, dove ogni cluster sembra essere relativamente lontano l’uno dall’altro:

Il numero di linee verticali che la nostra linea attraversa sono il numero di cluster finali della nostra soluzione. Scegliere il numero di cluster non è molto “scientifico” e si possono ottenere diverse soluzioni di clustering, a seconda dell’interpretazione del business. Ad esempio, nel nostro caso, tagliare il nostro dendrogramma un po’ più in alto e ridurre il numero di cluster della soluzione finale può essere anche un’ipotesi.

Restiamo con la soluzione a 7 cluster, quindi adattiamo il nostro metodo ward con quei n_clusters in mente:

ward_method_solution = AgglomerativeClustering(n_clusters = 7,                                         linkage = 'ward')wine_data['cluster'] = ward_method_solution.fit_predict(wine_data_scaled)

Poiché vogliamo interpretare i nostri cluster basandoci sulle variabili originali, utilizzeremo il metodo predict sui dati scalati (le distanze sono basate sul dataset scalato) ma aggiungeremo il cluster al dataset originale.

Confrontiamo i nostri cluster utilizzando le medie di ogni variabile condizionata alla variabile cluster:

wine_data.groupby(['cluster']).mean()

Curiosamente, possiamo iniziare ad avere alcune intuizioni sui dati — ad esempio:

• I vini di bassa qualità sembrano avere un grande valore di total sulfur dioxide — notare la differenza tra il cluster di media qualità più alta e il cluster di bassa qualità:

E se confrontiamo la qualità dei vini in questi cluster:

Chiaramente, in media, il Cluster 2 contiene vini di qualità superiore.

Un’altra analisi interessante che possiamo fare è quella di eseguire una matrice di correlazione tra le medie dei dati clusterizzati:

Ci fornisce alcuni buoni suggerimenti su potenziali cose che possiamo esplorare (anche per il learning supervisionato). Ad esempio, a livello multidimensionale, i vini con maggiori quantità di solfiti e cloruri possono essere raggruppati insieme. Un’altra conclusione è che i vini con una maggiore gradazione alcolica tendono ad essere associati a vini di qualità superiore.

Conclusione

Ecco fatto! Grazie per aver dedicato del tempo alla lettura di questo post sul learning non supervisionato. Continuerò ad aggiungere altri algoritmi di learning non supervisionato a questa serie per mostrare diversi tipi di metodi che possiamo utilizzare per conoscere la struttura dei nostri dati.

Naturalmente, la clustering gerarchica ha alcuni pro e contro che possiamo discutere:

• Un grande contro dell’algoritmo è che potrebbe richiedere troppi euristici per raggiungere una soluzione finale. Una combinazione di analisi del dendrogramma, analisi basate sulla distanza o metodi del coefficiente di silhouette può essere applicata per raggiungere un numero di cluster che abbia senso. Inoltre, non bisogna scartare l’incrocio di queste approccio tecnici con alcune conoscenze del business sui dati per evitare di cadere in qualche tipo di trappola di clustering.
• D’altra parte, l’approccio di clustering gerarchico è molto esplicativo, aiutando a scoprire strutture nascoste nei dati.
• Inoltre, la clustering gerarchica non soffre del problema dell’inizializzazione del centroide, il che può essere un vantaggio per alcuni dataset.

La clustering gerarchica è un metodo di clustering molto famoso che è stato applicato per molteplici applicazioni diverse come:

• Segmentazione dei clienti;
• Analisi degli outlier;
• Analisi di dati di espressione genica multidimensionali;
• Clustering di documenti;

È un metodo molto interessante che i data scientist dovrebbero avere nella loro cintura degli attrezzi. Sentiti libero di provarlo nel tuo prossimo progetto e rimani sintonizzato per altri post su questa Serie di Learning Non Supervisionato!

Se vuoi partecipare ai miei corsi di Python, sentiti libero di unirti al mio corso gratuito qui ( Python For Busy People – Introduzione a Python in 2 ore ) o a una versione più lunga di 16 ore ( The Complete Python Bootcamp for Beginners ). I miei corsi di Python sono adatti a principianti/sviluppatori di livello intermedio e sarei felice di averti in classe!

Il dataset utilizzato in questo post è concesso in licenza ai sensi della licenza Creative Commons Attribution 4.0 International (CC BY 4.0), come mostrato nel seguente link: https://archive.ics.uci.edu/dataset/186/wine+quality