Continuiamo con la presentazione degli algoritmi più famosi per il clustering delle informazioni.
Il clustering gerarchico è un altro metodo molto utilizzato e, rispetto a quanto visto per il k-means, non richiede di definire a priori il numero di cluster da ricercare.
Ne esistono due versioni:
- Agglomerativo: si parte assegnando un cluster diverso per ogni singolo dato in ingresso. Fatto questo, si procede iterativamente ad agglomerare più cluster insieme (sfruttando metriche opportune) fino a quando si arriva ad avere un unico cluster che contiene tutti i dati.
- Divisivo: nella pratica è l’esatto contrario dell’agglomerativo. Si parte con un unico cluster che contiene tutti i dati e poi, iterativamente, si procede a suddividere i cluster esistenti in più sottocluster, anche in questo caso affidandosi a metriche opportune.
In entrambi i casi, quindi, si esplorano tutte le possibili combinazioni di cluster, da un estremo (un unico cluster) all’altro (un cluster per dato) e viceversa.
Nella pratica la versione agglomerativa è quella più utilizzata, per motivi più che altro di efficienza computazionale.
Ora, la domanda è: ok, una volta svolte tutte queste operazioni, che ce ne facciamo di questi cluster?
Il risultato può essere meglio compreso se, mentre otteniamo i cluster, andiamo a costruire il dendrogramma. Si tratta di un grafico ad albero dove sull’asse delle ordinate è riportata la “distanza” tra i cluster e sull’asse orizzontale vengono riportati i vari dati in ingresso.
In questo diagramma, inoltre, le righe verticali corrispondono ad un cluster, quelle orizzontali ad operazioni di unione (se si usa la versione agglomerativa dell’algoritmo, che si legge dal basso verso l’alto) o di divisione (se si usa la versione divisiva dell’algoritmo, che si legge dall’alto verso il basso).
Interessante… ma quindi? Quindi, il dendrogramma rappresenta una sorta di “memoria” dei cluster e visualizza come questi cambiano in funzione della distanza massima che vogliamo applicare ai nostri dati, distanza che funzionerà come una soglia.
Osserviamo l’animazione seguente.
Si nota che a distanza 0 avremo un cluster per ogni dato in ingresso (p0, p1, .., p6). Il motivo è intuitivo in quanto l’unico punto (nello spazio delle features) che ha distanza 0 da un punto p sarà p stesso.
Ora innalziamo la soglia di distanza a 1,7. Seguendo il dendrogramma si nota che a quell’altezza avrò i punti p0, ..,p3 come singoli cluster, mentre p5 si fonde con p6 a formare un nuovo cluster (intorno a valori di distanza di 0,7), il quale a sua volta, poco più sopra (circa 1,3) si fonde anche con p4. Il risultato sarà quindi un insieme di 5 cluster.
Alziamo ancora la soglia a 3,1. Notiamo che p1 e p2 si fondono a circa 2,2, poi questo nuovo cluster si fonde a sua volta con p1 a circa 2,9. Il resto rimane invariato. Il risultato finale sarà quindi un insieme di 3 cluster.
Cosa ci dice tutto questo? Che una volta calcolate tutte le combinazioni di cluster, possiamo sbizzarrirci a modificare la soglia di clusterizzazione senza dover poi rieseguire nuove elaborazioni, ma semplicemente utilizzando il dendrogramma.
Questa flessibilità, in ogni caso, si paga con un costo di elaborazione molto più elevato di quello necessario con il k-means, proprio perchè per creare il dendrogramma dovrò elaborare tutte le combinazioni.
Le metriche utilizzate per misurare la “distanza” tra i cluster (sono sempre cluster, anche quando questi corrispondono ai singoli punti!) sono diverse a seconda del caso.
Le più comuni sono riassunte nell’immagine seguente.
- single linkage: la distanza tra i cluster è data dalla distanza minima tra i punti che li formano
- complete linkage: la distanza sarà quella massima tra i punti
- average linkage: la distanza sarà quella media tra i punti
- centroids linkage: la distanza sarà quella tra i centroidi
- ward’s linkage: la distanza sarà la somma dei quadrati delle distanze tra i punti
Codice Python
NOTA: il codice di questo esempio lo trovi qui
Creiamo un dataset random, sfruttando la funzione make_blobs di SciKitLearn. In questo caso mi interessano solo i dati in ingresso X e non i target Y e quindi ignoro il secondo array del risultato utilizzando il simbolo “underscore“, come da prassi Python.
# creo un dataset random, ignoro il target ed uso un random_state per poter replicare i risultati
X, _ = make_blobs(n_samples=50, centers=5, cluster_std=0.5, random_state=1234)
Visualizzo il risultato, dove si notano le 5 “nuvole” di dati.
Quindi, già da qui potremmo capire che dovremo utilizzare 5 cluster. In effetti corrisponde al valore del parametro centers che abbiamo fornito alla funzione make_blobs… Nel mondo reale, in generale, le cose non sono così semplici, per cui vediamo di analizzare i dati in modo più scientifico.
Visualizziamo il dendrogramma, sfruttando due funzioni della libreria SciPy. Costruiamo innanzitutto la linkage matrix che è una versione “macchina” del dendrogramma e contiene, per ogni riga, gli identificativi dei cluster agglomerati, la distanza misurata con la metrica indicata (useremo la Ward’s) ed il numero di dati contenuti nel nuovo cluster generato.
# costruisco una matrice di associazioni (linkage), usando il Ward's linkage
# che è una versione "macchina" del dendrogramma
link_matrix = linkage(X, method="ward")
# visualizzo la matrice di linkage
# imposto il nome delle colonne per chiarire i valori che contengono
pd_lnk_mtx = pd.DataFrame(link_matrix, columns=["cluster ID_A", "cluster ID_B", "distanza", "numero dati"])
print(pd_lnk_mtx)
cluster ID_A cluster ID_B distanza numero dati
0 0.0 49.0 0.041826 2.0
1 6.0 7.0 0.089505 2.0
2 28.0 35.0 0.107674 2.0
3 17.0 25.0 0.124217 2.0
4 44.0 50.0 0.161144 3.0
5 3.0 24.0 0.169438 2.0
6 16.0 29.0 0.172384 2.0
7 11.0 21.0 0.176212 2.0
.........
.........
44 46.0 89.0 2.639539 10.0
45 91.0 94.0 10.194683 20.0
46 92.0 95.0 18.042524 30.0
47 90.0 93.0 40.519703 20.0
48 96.0 97.0 57.122423 50.0
Leggiamo che al passo 0 il cluster con ID 0 si è unito con il cluster 49 con una distanza di 0,041826 ed il nuovo cluster contiene 2 dati. Al passo 1 il cluster 6 si è unito con il 7 ad una distanza di 0,089505 ed il nuovo cluster contiene 2 dati. E così via fino ad arrivare al passo 48 in cui il cluster 96 si è unito al cluster 97 ad una distanza di 57,122423 e l’ultimo cluster contiene 50 dati (l’intero nostro dataset).
Certo che interpretare una tabella del genere non è facile (tra l’altro i dati in gioco sono estremamente pochi!). Quindi grafichiamola sottoforma di dendrogramma, sempre tramite la libreria SciPy.
# visualizzo il dendrogramma
dendrogram(link_matrix)
plt.show()
Come si può notare da questo dendrogramma, a partire da una distanza di circa 3 o 4, abbiamo 5 cluster e per avere una ulteriore agglomerazione si deve arrivare sopra la distanza 10.
Questo conferma quanto visto in precedenza: per il nostro dataset il numero ottimale di cluster è 5.
Nell’asse delle ascisse notiamo anche che i cluster 6 e 7 si uniscono, così come il 0 ed il 49, come avevamo letto nella linkage matrix nei primi livelli. Notiamo che non appaiono gli ID superiori al 49 (ad esempio il 96 ed il 97 dell’ultima riga della linkage matrix) perchè creati nuovi da agglomerazioni.
Ora procediamo alla clusterizzazione vera e propria. In questo caso torniamo ad usare SciKitLearn che mette a disposizione la classe AgglomerativeClustering il cui unico difetto è quello di richiedere il numero di cluster in fase di addestramento e non sfrutta il dendrogramma appena creato, richiedendo quindi una successiva fase di addestramento nel caso volessimo modificare il numero di cluster (lavora per cluster e non per soglia di distanza). Useremo anche in questo caso una metrica Ward’s linkage. Da notare che, a differenza di quanto visto fin’ora con le classi di SciKitLearn, in questo caso esiste un solo metodo per fare sia addestramento che predizione.
# ora che ho idea della soglia da utilizzare, posso creare il modello di clustering agglomerativo
# NOTA: in SciKitLearn è necessario indicare subito il numero di cluster, quindi si va a perdere
# l'utilità del dendrogramma...
agglom_clustering = AgglomerativeClustering(n_clusters=5, linkage="ward")
# in un unico passaggio addestro il modello ed elaboro la predizione
y = agglom_clustering.fit_predict(X)
Infine andiamo a visualizzare il risultato del clustering ottenendo il risultato in figura.
See you soon!
Come al solito vi invito ad allenarvi modificando i vari parametri delle funzioni viste (numero di esempi, deviazione standard delle “nuvole” di dati, numero di cluster, metriche utilizzate, eccetera), in modo da rendervi conto di come si modificano i risultati.
Noi ci rivediamo alla prossima!
Bye!