Introduzione al clustering gerarchico in Python

Motivazione

Immagina di essere un Data Scientist che lavora per un'azienda retail. Il tuo capo ti chiede di segmentare i clienti nei seguenti gruppi: clienti low, average, medium o platinum in base al comportamento di spesa, per finalità di marketing mirato e raccomandazioni di prodotto.

Dato che non esistono etichette storiche associate a questi clienti, come è possibile classificarli? 

È qui che il clustering può aiutare. È una tecnica di machine learning non supervisionata utilizzata per raggruppare dati non etichettati in categorie simili. 

Questo tutorial si concentrerà sull'approccio del clustering gerarchico, una delle tante tecniche del machine learning non supervisionato. Inizierà fornendo una panoramica di cosa sia il clustering gerarchico, per poi confrontarlo con alcune tecniche esistenti.

Infine ti guiderà in un'implementazione passo passo in Python usando la popolare libreria Scipy.

Definizione di clustering gerarchico

Un approccio di clustering gerarchico si basa sulla determinazione di cluster successivi a partire da cluster precedentemente definiti. È una tecnica pensata per raggruppare i dati in un albero di cluster chiamato dendrogramma, che rappresenta graficamente la relazione gerarchica tra i cluster sottostanti.

Confronto del clustering gerarchico con altre tecniche di clustering

Il clustering gerarchico è un algoritmo potente, ma non è l'unico, e ogni tipo di clustering ha i suoi vantaggi e svantaggi. 

Vediamo come si confronta con altri tipi di clustering, come K-means e il clustering basato su modelli. Esistono molte altre tecniche, ma queste due, insieme al clustering gerarchico, sono ampiamente utilizzate e offrono un quadro utile per comprendere meglio le altre. 

Puoi approfondire il tema del clustering nel machine learning in un articolo dedicato, che copre cinque algoritmi di clustering essenziali. 

Clustering gerarchico vs clustering K-means

A differenza del clustering gerarchico, il clustering K-means cerca di suddividere i punti dati originali in gruppi o cluster “K”, dove l'utente specifica in anticipo il valore di “K”. 

L'idea generale è cercare cluster che minimizzino la distanza euclidea al quadrato di tutti i punti dai centroidi su tutti gli attributi (variabili o feature) e unire quegli individui in modo iterativo. 

Il nostro tutorial K-means Clustering in Python con Scikit-learn ti aiuterà a capire il funzionamento interno di K-means con un interessante caso di studio.

Vantaggi 

• È computazionalmente efficiente rispetto al clustering gerarchico e può essere usato per analizzare set di dati di grandi dimensioni. 
• K-means è più facile da comprendere e da implementare. 

Svantaggi

• È meno flessibile del clustering gerarchico perché costringe l'utente a specificare in anticipo il numero di cluster, cosa che in alcune situazioni potrebbe non essere evidente.  
• Il risultato non è stabile e cambia da un'iterazione all'altra per lo stesso set di dati.
• È più sensibile agli outlier, perché la loro presenza nei dati influenza la media del cluster. 
• Sia K-means sia il clustering gerarchico non possono gestire direttamente dati categorici e possono non funzionare bene con dati non continui o con varianza molto elevata.

Nonostante le sue limitazioni, il clustering K-means resta un metodo popolare per la sua semplicità d'uso ed efficienza computazionale. Viene spesso usato come punto di riferimento per confrontare le prestazioni di altre tecniche di clustering. 

Clustering basato su modelli

Sia K-means che il clustering gerarchico usano una matrice delle distanze per rappresentare le distanze tra tutti i punti del dataset. Il clustering basato su modelli, invece, applica tecniche statistiche per identificare cluster nei dati. Di seguito il processo generale: 

• Decidere il modello statistico da usare e scegliere il numero di cluster. 
• Fittare il modello sui dati. 
• Identificare i cluster in base ai parametri del modello.

Vantaggi 

• Il clustering basato su modelli è più flessibile del clustering gerarchico, perché consente di usare modelli diversi per individuare differenti tipi di cluster. 
• Funziona meglio con dati dalle forme o strutture complesse.

Svantaggi

• È più costoso dal punto di vista computazionale rispetto al clustering gerarchico, specialmente su dati di grandi dimensioni. 
• Richiede una migliore comprensione delle tecniche di modellazione statistica, dato che la scelta del modello può influire sul risultato finale. 
• Analogamente al clustering K-means, richiede di specificare in anticipo il numero di cluster. 

Applicazioni del clustering gerarchico

Il clustering gerarchico ha un'ampia gamma di applicazioni nella vita di tutti i giorni, tra cui (ma non solo) biologia, elaborazione di immagini, marketing, economia e analisi delle reti sociali.

Biologia

Il clustering delle sequenze di DNA è una delle sfide più grandi nella bioinformatica. 

I biologi possono sfruttare il clustering gerarchico per studiare le relazioni genetiche tra organismi e classificarli in gruppi tassonomici. Questo è utile per un'analisi rapida e per visualizzare le relazioni sottostanti.  

Elaborazione di immagini

Nel campo dell'elaborazione di immagini si può applicare il clustering gerarchico per raggruppare regioni o pixel simili di un'immagine in termini di colore, intensità o altre caratteristiche. Ciò può essere utile per compiti successivi come segmentazione, classificazione di immagini e riconoscimento di oggetti.

Marketing

Gli specialisti di marketing possono usare il clustering gerarchico per delineare una gerarchia tra diversi tipi di clienti in base alle loro abitudini di acquisto, così da progettare strategie migliori e raccomandazioni di prodotto. Ad esempio, nel retail si possono raccomandare prodotti diversi ai clienti a seconda che siano piccoli, medi o grandi spendaccioni.

Analisi delle reti sociali

I social network sono una grande fonte di informazioni preziose quando vengono sfruttati in modo efficiente. Il clustering gerarchico può essere usato per identificare gruppi o comunità e comprendere le loro relazioni reciproche e la struttura della rete nel suo complesso.

L'algoritmo di clustering gerarchico

In questa sezione vedremo tre concetti principali: i passaggi dell'algoritmo gerarchico, una panoramica dei due tipi di clustering gerarchico (agglomerativo e divisivo) e, infine, alcune tecniche per scegliere la giusta misura di distanza.

Passaggi dell'algoritmo di clustering gerarchico

L'algoritmo di clustering gerarchico utilizza misure di distanza per generare i cluster. Questo processo di generazione prevede i seguenti passaggi principali: 

Preprocessa i dati rimuovendo i valori mancanti e applicando eventuali attività aggiuntive per rendere i dati quanto più puliti possibile. Questo passaggio è piuttosto generale per la maggior parte dei compiti di machine learning. 

1. Calcola la matrice delle distanze contenente la distanza tra ogni coppia di punti dati utilizzando una metrica specifica come distanza euclidea, distanza di Manhattan o similarità coseno. La metrica predefinita è quella euclidea.

2.Unisci i due cluster più vicini in termini di distanza. 

3. Aggiorna la matrice delle distanze rispetto ai nuovi cluster.  

4. Ripeti i passaggi 1, 2 e 3 finché tutti i cluster non vengono uniti in un unico cluster. 

Esempi di clustering gerarchico 

Possiamo considerare il clustering agglomerativo e quello divisivo come speculari. Vediamo più da vicino come opera ciascuno, insieme a un esempio di clustering gerarchico e a una visualizzazione grafica. 

Clustering gerarchico agglomerativo

Questo primo scenario corrisponde all'approccio spiegato sopra. Si parte considerando ogni osservazione come un cluster singoletto (cluster con un solo punto dati). Poi si uniscono iterativamente i cluster finché non se ne ottiene uno solo. Questo processo è detto anche approccio bottom-up. 

Come mostrato nell'illustrazione seguente: 

• Partiamo considerando ogni animale come il proprio cluster unico.  
• Quindi generiamo tre cluster diversi a partire da quegli animali unici in base alle loro somiglianze: 
• Uccelli: Aquila e Pavone
• Mammiferi:  Leone e Orso
• Animali con più di tre zampe: Ragno e Scorpione.
• Ripetiamo il processo di fusione per creare il cluster Vertebrati unendo i due cluster più simili: Uccelli e Mammiferi.
• Dopo questo passaggio, i due cluster rimanenti, Vertebrati e Più di tre zampe, vengono uniti per creare un unico cluster Animali. 

Dendrogramma dell'approccio di clustering agglomerativo

Clustering divisivo

Il clustering divisivo, invece, è top-down perché parte considerando tutti i punti dati come un unico cluster. Poi li separa finché tutti i punti dati non sono unici.

Dal grafico dell'approccio divisivo: 

• Notiamo che l'intero dataset di animali è considerato come un unico blocco. 
• Poi dividiamo quel blocco in due cluster: Vertebrati e Più di 3 zampe. 
• Il processo di divisione viene applicato iterativamente ai cluster creati in precedenza finché non otteniamo animali unici. 

Dendrogramma dell'approccio di clustering divisivo

Scegliere la giusta misura di distanza

La scelta della misura di distanza è un passaggio critico nel clustering e dipende dal problema che stai cercando di risolvere. Considerando il seguente scenario, potremmo raggruppare gli studenti in base a diversi criteri, ad esempio: 

• Paese di origine
• Genere, maschio o femmina
• Precedente background accademico.

Sono tutti cluster validi, ma differiscono per significato. 

Benché la distanza euclidea sia la più utilizzata nella maggior parte dei software di clustering, esistono anche altre misure di distanza come la distanza di Manhattan, la distanza di Canberra, la correlazione di Pearson o Spearman e la distanza di Minkowski.

Come misurare i cluster prima di unirli

Le distanze menzionate in precedenza sono legate agli elementi. In questa sezione vedremo tre modalità standard (non esaustive) per misurare la coppia di cluster più vicina prima di unirli: (1) Single linkage, (2) Complete linkage e (3) Average linkage. 

Single linkage

Tra tutte le distanze a coppie tra gli elementi nei due cluster C1 e C2, il single linkage prende come distanza tra i cluster la distanza minima. 

Distanza (C1, C2) = Min { d(i, j), dove l'elemento i è in C1 e l'elemento j è in C2}

Tra tutte le coppie di elementi dei due cluster, quelle evidenziate in verde hanno la distanza minima. 

Illustrazione del single linkage

Complete linkage

Tra tutte le distanze a coppie tra gli elementi nei due cluster C1 e C2, il complete linkage prende come distanza tra i cluster la distanza massima. 

Distanza (C1, C2) = Max { d(i, j), dove l'elemento i è in C1 e l'elemento j è in C2}

Tra tutte le coppie di elementi dei due cluster, quelle evidenziate in verde hanno la distanza massima.

Illustrazione del complete linkage

Average linkage

Nell'average linkage, la distanza tra due cluster C1 e C2 corrisponde alla media delle distanze tra tutte le coppie di elementi nei due cluster.

Distanza (C1, C2) = Somma{ d(i, j) } / Numero totale di distanze

Illustrazione dell'average linkage

​Quindi l'average linkage viene eseguito come segue 

d(a,j) + d(a,h) + d(a,n) + d(d,j) + d(d,h) + d(d,n)  

—-----------------------------------------------------------, dove il numero totale di distanze = 6

  Numero totale di distanze

Implementare il clustering gerarchico in Python

Ora hai compreso come funziona il clustering gerarchico. In questa sezione ci concentreremo sull'implementazione tecnica in Python.

Se ti interessa di più l'implementazione con il linguaggio R, il nostro tutorial Clustering gerarchico in R è il punto di partenza.

Configurare l'ambiente 

Per iniziare, devi avere installato Python sul tuo computer, insieme alle seguenti librerie:

• Pandas per caricare il data frame. 
• Scikit-learn per eseguire la normalizzazione dei dati.
• Seaborn e matplotlib per la visualizzazione.
• Scipy per applicare il clustering.

Puoi installare queste librerie usando pip, il gestore pacchetti di Python, come segue:

pip install scikit-learn
pip install pandas

pip install matplotlib seaborn

pip install scipy

Successivamente, importiamo i moduli necessari e carichiamo il dataset. Useremo il dataset iris integrato in scikit-learn, che contiene informazioni su diversi tipi di fiori di iris.

Per illustrare meglio il caso d'uso, utilizzeremo i Loan Data disponibili su DataLab. Tutto il codice in questo tutorial è disponibile in questo workbook di DataLab; puoi facilmente crearne una copia tua per eseguire il codice nel browser, senza dover installare alcun software sul tuo computer.

Comprendere i dati

Il dataset contiene 9.500 prestiti con informazioni sulla struttura del prestito, sul mutuatario e sull'eventuale rimborso completo del prestito. Rimuoveremo la colonna target not.fully.paid per rispettare l'aspetto non supervisionato.

import pandas as pd
loan_data = pd.read_csv("loan_data.csv")
loan_data.head()

Prime cinque righe dei dati di prestito

L'istruzione seguente mostra che i dati hanno 9.578 righe e 14 colonne di tipo numerico, tranne purpose, che è di tipo object e fornisce la descrizione testuale dello scopo del prestito. 

loan_data.info()

Informazioni sui dati

Preprocessing dei dati 

Prima di applicare il clustering, i dati vanno preprocessati per gestire le informazioni mancanti, normalizzare i valori delle colonne ed eliminare le colonne irrilevanti.

Gestione dei valori mancanti

Dall'output seguente, notiamo che non ci sono valori mancanti nei dati.

percent_missing =round(100*(loan_data.isnull().sum())/len(loan_data),2)
percent_missing

Percentuale di valori mancanti nei dati

Eliminare colonne indesiderate

Analizzeremo i dati sui prestiti utilizzando tutte le colonne tranne le seguenti: 

• Purpose
• Not.fully.paid, perché è l'etichetta che indica se il mutuatario ha effettuato il rimborso completo o meno.

cleaned_data corrisponde ai dati senza le colonne sopra elencate. 

cleaned_data = loan_data.drop(['purpose', 'not.fully.paid'], axis=1)
cleaned_data.info()

L'immagine seguente mostra le informazioni dei nuovi dati.

Nuovi dati senza le colonne indesiderate

Analisi degli outlier

Una delle debolezze del clustering gerarchico è la sensibilità agli outlier.  La distribuzione di ciascuna variabile è mostrata dal boxplot. 

def show_boxplot(df):
plt.rcParams['figure.figsize'] = [14,6]
sns.boxplot(data = df, orient="v")
plt.title("Outliers Distribution", fontsize = 16)
plt.ylabel("Range", fontweight = 'bold')
plt.xlabel("Attributes", fontweight = 'bold')
   
show_boxplot(cleaned_data)

Boxplot di tutte le variabili nei dati

Il saldo rotativo del mutuatario (revol_bal) è l'unico attributo con punti dati molto distanti dagli altri. 

Usando l'approccio dell'intervallo interquartile, possiamo rimuovere tutti i punti che si trovano al di fuori dell'intervallo definito dai quartili +/-1,5 * IQR, dove IQR è l'InterQuartile Range. 

Questo si ottiene con la seguente funzione di supporto. 

def remove_outliers(data):
   
df = data.copy()
   
for col in list(df.columns):
 
      Q1 = df[str(col)].quantile(0.05)
      Q3 = df[str(col)].quantile(0.95)
      IQR = Q3 - Q1
      lower_bound = Q1 - 1.5*IQR
      upper_bound = Q3 + 1.5*IQR
 
      df = df[(df[str(col)] >= lower_bound) & 

        (df[str(col)] <= upper_bound)]
   
return df

Poi possiamo applicare la funzione al dataset. 

without_outliers = remove_outliers(cleaned_data)

Ora possiamo controllare il nuovo boxplot e confrontarlo con quello precedente alla rimozione degli outlier. 

show_boxplot(without_outliers)

Non ci sono più punti dati al di fuori dell'intervallo interquartile.

without_outliers.shape

La forma dei dati è ora 9.319 righe e 12 colonne. Ciò significa che 259 osservazioni erano outlier e sono state rimosse. 

Riscalare i dati

Poiché il clustering gerarchico usa la distanza euclidea, che è molto sensibile alla presenza di variabili su scale diverse, è opportuno riscalare tutte le variabili prima di calcolare le distanze. 

Questo si fa usando la classe StandardScaler di sklearn. 

from sklearn.preprocessing import StandardScaler

data_scaler = StandardScaler()

scaled_data = data_scaler.fit_transform(without_outliers)
scaled_data.shape

La forma dei dati rimane la stessa (9.319 righe, 12 colonne) perché la normalizzazione non ne modifica la dimensione. 

Applicare l'algoritmo di clustering gerarchico 

Tutti i requisiti sono soddisfatti per passare all'implementazione dell'algoritmo di clustering. 

A questo punto possiamo decidere quale approccio di linkage adottare per il clustering tramite l'attributo method del metodo linkage(). In questa sezione copriremo tutte e tre le tecniche di linkage usando la distanza euclidea. 

Questo si ottiene con i codici seguenti dopo aver importato le librerie rilevanti.

from scipy.cluster.hierarchy import linkage, dendrogram

complete_clustering = linkage(scaled_data, method="complete", metric="euclidean")
average_clustering = linkage(scaled_data, method="average", metric="euclidean")
single_clustering = linkage(scaled_data, method="single", metric="euclidean")

Una volta calcolati i tre clustering, i relativi dendrogrammi sono mostrati di seguito, a partire dal complete clustering  

dendrogram(complete_clustering)
plt.show()

Dendrogramma dell'approccio di complete clustering

dendrogram(average_clustering)
plt.show()

Dendrogramma dell'approccio di average clustering

dendrogram(single_clustering)
plt.show()

Dendrogramma dell'approccio di single clustering

Interpretare i risultati (visualizzare il dendrogramma, determinare il numero di cluster)

Per ogni approccio di linkage, il dendrogramma mostra come viene costruito e come ogni punto dati finisce in un unico cluster. 

• L'asse x del dendrogramma rappresenta i campioni nei dati.
• L'asse y rappresenta la distanza tra quei campioni. Più alta è la linea, più dissimili sono quei campioni/cluster.
• Otteniamo il numero appropriato di cluster tracciando una linea orizzontale attraverso la linea verticale più alta, e il numero di intersezioni corrisponde al numero di cluster. 

Il numero ottimale di cluster si può ottenere identificando la linea verticale più alta che non interseca altri cluster (linee orizzontali). Una tale linea è evidenziata di seguito con un cerchio rosso e una spunta verde.   

• Per il complete linkage, è la linea blu a destra e genera tre cluster. 

Numero ottimale di cluster dalla distanza più alta senza intersezioni (complete linkage)

• Per l'average linkage, è la prima linea verticale blu e genera due cluster.

Numero ottimale di cluster dalla distanza più alta senza intersezioni (average linkage)

• Per il single linkage, è la prima linea verticale e genera un solo cluster. 

Numero ottimale di cluster dalla distanza più alta senza intersezioni (single linkage)

Dalle osservazioni sopra, l'average linkage sembra essere quello che fornisce il miglior clustering, a differenza del single e del complete linkage che suggeriscono rispettivamente di considerare un cluster e tre cluster. Inoltre, il numero ottimale di cluster pari a due corrisponde alla nostra conoscenza pregressa del dataset, ovvero i due tipi di mutuatari. 

Ora che abbiamo trovato il numero ottimale di cluster, vediamo cosa significano questi cluster in base al credit score del mutuatario.

cluster_labels = cut_tree(average_clustering, n_clusters=2).reshape(-1, )
without_outliers["Cluster"] = cluster_labels

sns.boxplot(x='Cluster', y='fico', data=without_outliers)

Dal boxplot sopra, possiamo osservare che: 

• I mutuatari del cluster 0 hanno i punteggi di credito più alti.  
• Mentre i mutuatari del cluster 1 hanno punteggi di credito più bassi.

Cluster Analysis in Python può essere un buon passo successivo per approfondire K-means e clustering gerarchico usando la libreria Scipy. 

Conclusione

Questo articolo ha trattato che cos'è il clustering gerarchico, i suoi punti di forza e di debolezza e come si confronta con K-means e il clustering basato su modelli. 

Speriamo che l'articolo ti abbia fornito le competenze rilevanti per raggruppare in modo efficace i tuoi dati non etichettati e supportare decisioni operative.