Il clustering gerarchico è una tecnica di clustering utilizzata nell’apprendimento automatico per raggruppare insiemi di dati simili in cluster più ampi, organizzandoli in una struttura gerarchica. Questo metodo di clustering è stato sviluppato principalmente per affrontare problemi di classificazione non supervisionata, dove i dati non sono pre-etichettati e il modello deve trovare autonomamente la struttura nei dati.
Il Clustering Gerarchico
Il clustering gerarchico è un approccio nel machine learning che mira a raggruppare insiemi di dati simili in cluster in base alla loro somiglianza. Questo tipo di clustering costruisce una gerarchia di cluster, organizzandoli in una struttura ad albero. Ci sono due principali approcci nel clustering gerarchico:
- Agglomerativo: Inizia considerando ogni punto come un singolo cluster e successivamente unisce iterativamente i cluster più simili fino a quando tutti i punti sono raggruppati in un singolo cluster.
- Divisivo: Inizia con un unico cluster contenente tutti i punti e successivamente divide iterativamente i cluster in cluster più piccoli finché ogni punto è in un cluster separato.
La storia del clustering gerarchico risale agli anni ’60 e ’70, quando venne introdotto come una delle prime tecniche di clustering. Uno dei primi algoritmi di clustering gerarchico è stato proposto da Ward nel 1963, chiamato “Ward’s method”, che cerca di minimizzare la somma dei quadrati delle differenze tra i punti all’interno di ciascun cluster. Questo algoritmo è ancora comunemente usato oggi.
Negli anni successivi, sono stati sviluppati altri algoritmi per il clustering gerarchico, come il metodo del legame singolo, il metodo del legame completo e il metodo del legame medio. Questi algoritmi differiscono nel modo in cui determinano la distanza tra i cluster e come combinano i cluster adiacenti per formare una gerarchia.
Il clustering gerarchico può essere rappresentato tramite un dendrogramma, un diagramma a forma di albero che mostra la struttura gerarchica dei cluster. Questo permette di visualizzare in modo intuitivo come i dati sono stati raggruppati in cluster più grandi e più piccoli.
Questo approccio è utilizzato in molte aree, come la segmentazione del mercato, la biologia computazionale, l’analisi dei social media e altro ancora. È un’opzione popolare quando non si conosce il numero esatto di cluster desiderati e si desidera esplorare la struttura dei dati in modo più dettagliato.
Per comprendere meglio il clustering gerarchico, iniziamo definendo alcune nozioni fondamentali:
Distanza tra cluster: È necessario definire una metrica di distanza per misurare la somiglianza tra cluster. Una delle metriche più comuni è la distanza euclidea. Tuttavia, altre metriche come la distanza di Manhattan, la distanza di Minkowski, la correlazione di Pearson, possono essere utilizzate a seconda del contesto. La distanza euclidea tra due punti (x) e (y) nello spazio (n)-dimensionale è data da:
Metodo di collegamento: Questo metodo determina come calcolare la distanza tra due cluster basandosi sulla distanza tra i loro punti membri. Alcuni dei metodi comuni includono:
- Single Linkage (minimo): La distanza tra due cluster è la minima distanza tra un punto del primo cluster e un punto del secondo cluster.
- Complete Linkage (massimo): La distanza tra due cluster è la massima distanza tra un punto del primo cluster e un punto del secondo cluster.
- Average Linkage (media): La distanza tra due cluster è la media delle distanze tra i punti di due cluster.
Dendrogramma: È una rappresentazione grafica della gerarchia dei cluster. Mostra come i cluster vengono uniti o divisi a ogni passaggio e la distanza tra di essi.
Con queste nozioni in mente, il processo di clustering gerarchico può essere descritto in termini matematici:
- Inizializzazione: Ogni punto dati è considerato un cluster separato.
- Calcolo della matrice delle distanze: Viene calcolata la matrice delle distanze tra tutti i punti dati.
- Unione dei cluster: Si uniscono iterativamente i due cluster più simili in base al metodo di collegamento scelto.
- Aggiornamento della matrice delle distanze: Si aggiorna la matrice delle distanze tenendo conto della nuova configurazione dei cluster.
- Ripetizione: Si ripetono i passaggi 3 e 4 fino a quando tutti i punti sono stati raggruppati in un unico cluster o fino a quando il numero desiderato di cluster è stato raggiunto.
- Dendrogramma: Si costruisce il dendrogramma per visualizzare la gerarchia dei cluster e aiutare a determinare il numero ottimale di cluster.
Il clustering gerarchico può essere computazionalmente costoso, soprattutto per grandi set di dati, ma fornisce una visione intuitiva della struttura dei dati e può essere utile quando non si conosce il numero esatto di cluster desiderati.
Implementiamo un esempio di Clustering Gerachico con Scikit-learn
Per prima cosa, pensiamo ai dati di partenza. A tal proposito, possiamo utilizzare make_blobs. Questa è una funzione fornita dalla libreria scikit-learn che consente di generare insiemi di dati sintetici utilizzati spesso per scopi di test e dimostrazione in algoritmi di machine learning. Questa funzione genera cluster di punti casuali in uno spazio bidimensionale o tridimensionale, con i centroidi dei cluster specificati e la deviazione standard dei cluster.
In pratica, make_blobs genera un numero specificato di campioni casuali distribuiti intorno a centroidi specificati, con una deviazione standard specificata che controlla la dispersione dei punti all’interno di ciascun cluster.
Questa funzione è utile per creare dataset di prova con diversi livelli di complessità e strutture di cluster, consentendo agli sviluppatori e ai ricercatori di testare e confrontare algoritmi di clustering, classificazione e altre tecniche di apprendimento automatico su dati sintetici prima di applicarli a dati reali.
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs
from sklearn.cluster import AgglomerativeClustering
from scipy.cluster.hierarchy import dendrogram, linkage
# Generate random data using make_blobs function
X, _ = make_blobs(n_samples=300, centers=4, cluster_std=0.60, random_state=0)
# Visualize the generated data
plt.scatter(X[:, 0], X[:, 1], s=50)
plt.title('Generated Data')
plt.xlabel("Feature 1")
plt.ylabel("Feature 2")
plt.show()Eseguendo il codice otterremo la rappresentazione grafica dei punti generati da make_blobs.
Applichiamo ora a tali dati l’algoritmo del Clustering gerachico, riportando il numero dei cluster da individuare, pari a 4.
model = AgglomerativeClustering(n_clusters=4)
model.fit(X)
plt.scatter(X[:, 0], X[:, 1], c=model.labels_, s=50, cmap='viridis')
plt.title("Hierarchical Clustering Results")
plt.xlabel("Feature 1")
plt.ylabel("Feature 2")
plt.show()Eseguendo si ottiene il risultato seguente:
Come possiamo vedere dall’immagine, la clusterizzazione è andata perfettamente. I punti sono stati suddivisi in 4 cluster e identificati con diverse colorazioni.
Vediamo di visualizzare anche il dendrogramma che ne è alla base:
# Build the dendrogram
linked = linkage(X, 'ward') # 'ward' is a common linkage method
plt.figure(figsize=(12, 8))
dendrogram(linked, orientation='top', distance_sort='descending', show_leaf_counts=True, color_threshold=7) # Modify this value according to your requirements
plt.title('Dendrogram with branch coloring')
plt.xlabel('Sample indices')
plt.ylabel('Distance')
plt.show()
cluster_colors = {i: plt.cm.nipy_spectral(float(idx) / model.n_clusters) for i, idx in enumerate(np.unique(cluster_labels))}Eseguendo si ottiene il dendrogramma con i colori corrispondenti ai 4 cluster identificati durante la suddivisione gerarchica dei punti.
Problema del numero di cluster da identificare
Nell’esempio precedente avevamo stabilito come 4 il numero di cluster da identificare nel dataset. Noi eravamo già a conoscenza di questo dato, ma in realtà non è sempre così. Ma allora come valutare il numero di cluster in cui suddividere i dati. Bene, esistono dei metodi appositi, come il metodo del gomito, che applicheremo al caso precedente, facendo finta di non conoscere il numero dei cluster da utilizzare.
A tal proposito implementiamo il codice seguente:
# Calculate the variation of the sum of squared intra-cluster distances
sum_of_squared_distances = []
for k in range(1, 11):
model = AgglomerativeClustering(n_clusters=k)
model.fit(X)
labels = model.labels_
centroids = np.array([X[labels == i].mean(axis=0) for i in range(k)])
distances = np.array([np.sum((X[labels == i] - centroids[i])**2) for i in range(k)])
sum_of_squared_distances.append(np.sum(distances))
# Plot the elbow method
plt.plot(range(1, 11), sum_of_squared_distances, marker='o')
plt.title('Elbow Method')
plt.xlabel('Number of Clusters')
plt.ylabel('Sum of Squared Intra-Cluster Distances')
plt.xticks(range(1, 11))
plt.grid(True)
plt.show()Eseguendo il codice si ottiene il seguente risultato:
Come possiamo vedere dalla curva, il “gomito” corrisponde al valore di 4 cluster, di cui già sapevamo la correttezza.
La somma delle distanze quadrate intra-cluster è una misura della coesione dei cluster. Quando si aggiungono più cluster, questa somma tende a diminuire poiché i cluster diventano più piccoli e più omogenei. Tuttavia, a un certo punto, aggiungere ulteriori cluster potrebbe non portare a una significativa riduzione della somma delle distanze quadrate intra-cluster. Questo punto è spesso chiamato “gomito” nella curva della somma delle distanze quadrate intra-cluster.
L’idea del metodo del gomito è di individuare il punto in cui la diminuzione della somma delle distanze quadrate intra-cluster inizia a diminuire drasticamente, indicando che aggiungere ulteriori cluster non porta a una significativa riduzione della coesione dei cluster. Questo punto può essere considerato come il numero ottimale di cluster da selezionare.
Quindi, quando osserviamo la curva della somma delle distanze quadrate intra-cluster e individuiamo il punto in cui si forma un “gomito”, possiamo considerare quel numero di cluster come un buon candidato per il numero ottimale di cluster da utilizzare nel nostro algoritmo di clustering.
Clustering Gerarchico vs K-Means
Il Clustering Gerarchico ha una struttura gerarchica. Crea una struttura ad albero di cluster che può essere esplorata per ottenere una visione più dettagliata della relazione tra i cluster. Quindi non è necessario specificare a priori il numero di cluster desiderati, poiché il clustering gerarchico costruisce una gerarchia di cluster. E’ robusto al rumore, e può gestire insiemi di dati contenenti outlier o rumore grazie alla sua struttura gerarchica. Purtroppo è computazionalmente costoso e richiede più tempo e risorse computazionali rispetto a K-means, specialmente su grandi set di dati.
K-means è più veloce e scalabile rispetto al clustering gerarchico, rendendolo più adatto per grandi set di dati. Richiede la specifica del numero di cluster a priori, il che potrebbe essere problematico se non si conosce il numero ottimale di cluster. L’esito del clustering può dipendere dalla scelta casuale dei centroidi iniziali, quindi può essere necessario eseguire l’algoritmo più volte con diverse inizializzazioni. È efficace quando i cluster sono ben distinti e separabili. È più adatto per applicazioni in tempo reale dove la velocità di esecuzione è prioritaria rispetto alla comprensione della struttura dei dati.
Quindi il Clustering gerarchico è preferibile quando si desidera una visione gerarchica della struttura dei dati, non si conosce il numero esatto di cluster desiderati e si hanno risorse computazionali sufficienti per gestire l’algoritmo.
Mentre K-means è preferibile quando si conosce il numero di cluster desiderati, si hanno grandi set di dati e si richiede una maggiore efficienza computazionale.
Inoltre, è importante considerare il contesto specifico del problema e le caratteristiche dei dati quando si sceglie tra i due algoritmi di clustering. In alcuni casi, potrebbe essere utile eseguire entrambi gli algoritmi e confrontare i risultati per ottenere una comprensione più completa della struttura dei dati.