Il clustering agglomerativo è uno dei migliori strumenti di clustering nella scienza dei dati, ma le implementazioni tradizionali non riescono a adattarsi a set di dati di grandi dimensioni.
In questo articolo ti illustrerò alcune informazioni di base sul clustering agglomerativo, un’introduzione al clustering agglomerativo reciproco (RAC) basato su Ricerca 2021 di Googleun confronto di runtime tra RAC++ E scikit-learndell’AgglomerativeClustering e infine una breve spiegazione della teoria alla base del RAC.
Fondamenti sul clustering agglomerativo
Nella scienza dei dati, è spesso utile raggruppare i dati senza etichetta. Con applicazioni che vanno dal raggruppamento dei risultati dei motori di ricerca, alla classificazione dei genotipi, al rilevamento di anomalie bancarie, il clustering è un elemento essenziale del toolkit di un data scientist.
Il clustering agglomerativo è uno degli approcci di clustering più popolari nella scienza dei dati e, per una buona ragione:
✅ È facile da usare con una regolazione dei parametri minima o nulla
✅ Crea tassonomie significative
✅ Funziona bene con dati ad alta dimensione
✅ Non è necessario conoscere in anticipo il numero di cluster
✅ Crea ogni volta gli stessi cluster
In confronto, metodi di partizionamento come K-Means richiedono al data scientist di indovinare il numero di cluster, il metodo molto popolare basato sulla densità DBSCAN richiede alcuni parametri relativi al raggio di calcolo della densità (epsilon) e alla dimensione minima del quartiere, e Gaussian mixture models fare ipotesi forti sulla distribuzione dei dati del cluster sottostante.
Con il clustering agglomerativo, tutto ciò che devi specificare è una metrica di distanza.
Ad alto livello, il clustering agglomerativo segue l’algoritmo seguente:
Identify cluster distances between all pairs of clusters (each cluster begins as a single point)Merge the two clusters which are closest to one anotherRepeat
Il risultato: un bellissimo dendrogramma che può quindi essere suddiviso in base alle competenze del dominio.
In campi come la biologia e l’elaborazione del linguaggio naturale, i cluster (di cellule, geni o parole) seguono naturalmente una relazione gerarchica. Il clustering agglomerativo consente quindi una selezione più naturale e basata sui dati del limite finale del clustering.
Nella foto sotto c’è un esempio di raggruppamento agglomerato dei famosi Set di dati dell’iride.
Allora perché non utilizzare il clustering agglomerativo per ogni problema di classificazione non supervisionata?
❌ Il clustering agglomerativo ha a terribile runtime man mano che i set di dati aumentano di dimensioni.
Sfortunatamente, il tradizionale clustering agglomerativo non è scalabile. Il tempo di esecuzione è O(n³) O O(n²log(n)) se implementato con un heap minimo. Ancora peggio, il clustering agglomerativo viene eseguito in sequenza su un single-core e non può essere ampliato con il calcolo.
Nel campo della PNL, il clustering agglomerativo è uno dei migliori risultati… per piccoli set di dati.
Clustering agglomerativo reciproco (RAC)
Il clustering agglomerativo reciproco (RAC) è a metodo proposto da Google per estendere i vantaggi del tradizionale clustering agglomerativo a set di dati più grandi.
RAC riduce la complessità del runtime parallelizzando al tempo stesso le operazioni per utilizzare un’architettura multi-core. Nonostante queste ottimizzazioni, RAC produce esattamente gli stessi risultati del tradizionale clustering agglomerativo quando i dati vengono archiviati completamente connesso (vedi sotto).
Nota: dati completamente connessi significa che è possibile calcolare una metrica di distanza tra qualsiasi coppia di punti. I set di dati non completamente connessi hanno vincoli di connettività (solitamente forniti sotto forma di matrice di collegamento) per cui alcuni punti sono considerati disconnessi.
Anche con vincoli di connettività (dati non completamente connessi), il RAC e il clustering agglomerativo sono ancora tipicamente identici, come visto nel secondo Set di dati Swiss Roll esempio sopra.
Tuttavia, possono emergere ampie discrepanze quando i cluster possibili sono molto pochi. IL Set di dati Lune rumorose ne è un buon esempio:
RAC++ si adatta a set di dati più grandi rispetto a scikit-learn
Possiamo confrontare RAC++ (un’implementazione del clustering agglomerativo reciproco) alla sua controparte, Clustering agglomerativoIn scikit-learn.
Generiamo alcuni dati di esempio con 25 dimensioni e testiamo quanto tempo impiega il clustering agglomerativo racplusplus.rac contro sklearn.cluster.AgglomerativeClustering per set di dati di dimensioni comprese tra 1.000 e 64.000 punti.
Nota: sto utilizzando una matrice di connettività per limitare il consumo di memoria.
import numpy as np
import racplusplus
from sklearn.cluster import AgglomerativeClustering
import time
points = (1000, 2000, 4000, 6000, 10000, 14000, 18000, 22000, 26000, 32000, 64000)
for point_no in points:
X = np.random.random((point_no, 25))
distance_threshold = .17
knn = kneighbors_graph(X, 30, include_self=False)
# Matrix must be symmetric – done internally in scikit-learn
symmetric = knn + knn.T
start = time.time()
model = AgglomerativeClustering(
linkage=”average”,
connectivity=knn,
n_clusters=None,
distance_threshold=distance_threshold,
metric=’cosine’
)
sklearn_times.append(time.time() – start)
start = time.time()
rac_labels = racplusplus.rac(
X, distance_threshold, symmetric,
batch_size=1000, no_cores=8, metric=”cosine”
)
rac_times.append(time.time() – start)
Di seguito è riportato un grafico dei risultati di runtime per ciascun set di dati di dimensione:
Come possiamo vedere, ci sono drastiche differenze nel runtime tra RAC++ e il tradizionale clustering agglomerativo.
Con poco più di 30.000 punti, RAC++ è circa 100 volte più veloce! Ancora più importante, scikit-learnIl clustering agglomerativo di raggiunge un limite di tempo a ~ 35 mila punti, mentre RAC++ potrebbe raggiungere centinaia di migliaia di punti nel momento in cui raggiunge un limite di tempo ragionevole.
RAC++ può scalare fino a dimensioni elevate
Possiamo anche confrontare quanto bene RAC++ si adatta a dati ad alta dimensione rispetto alla sua controparte tradizionale.
Tempo impiegato per generare cluster rispetto alla dimensionalità per 3.000 punti
Per 3.000 punti possiamo vedere che il clustering agglomerativo tradizionale è più veloce ma scala linearmente mentre RAC++ è quasi costante. Lavorare con incorporamenti dimensionali da 768 o 1536 è diventata la norma nel campo della PNL, quindi è importante ridimensionare la dimensionalità per soddisfare tali requisiti.
RAC++ ha un tempo di esecuzione migliore
I ricercatori di Google ha dimostrato che RAC ha una durata di O(nk) Dove k è il vincolo di connettività e nè il numero di punti— un tempo di esecuzione lineare. Tuttavia, questo esclude il calcolo della matrice della distanza iniziale che è O(n²) — un runtime quadratico.
I nostri risultati, eseguendo un vincolo di connettività costante di 30 vicini, confermano un O(n²) tempo di esecuzione:
+ — — — — — — -+ — — — — — +
| Data points | Seconds |
+ - - - - - - -+ - - - - - +
| 2000 | 0.051 |
| 4000 | 0.125 |
| 6000 | 0.245 |
| 10000 | 0.560 |
| 14000 | 1.013 |
| 18000 | 1.842 |
| 22000 | 2.800 |
| 26000 | 3.687 |
| 32000 | 5.590 |
| 64000 | 22.499 |
+ - - - - - - -+ - - - - - +
Raddoppiare i punti dati significa aumentare di 4 volte il tempo.
Un runtime quadratico limita le prestazioni di RAC++ man mano che i set di dati diventano davvero enormi, tuttavia, questo runtime rappresenta già un grande miglioramento rispetto al tradizionale O(n³) o ottimizzato per heap minimoO(n²log(n)) tempo di esecuzione.
Nota: gli sviluppatori di RAC++ stanno lavorando per passare la matrice delle distanze come parametro da dare RAC++ un tempo di esecuzione lineare.
Come funziona il RAC
Perché RAC++ è così veloce? Possiamo ridurre l’algoritmo sottostante a pochi passaggi:
Pair clusters with reciprocal nearest neighborsMerge the pairs of clustersUpdate neighbors
Tieni presente che l’unica differenza tra questo e il tradizionale algoritmo di clustering agglomerativo è che ci assicuriamo di accoppiare vicini più prossimi reciproci insieme. Da qui il nome Reciprocal Agglomerative Clustering (RAC). Come vedrai, questo accoppiamento reciproco ci consente di parallelizzare la fase più costosa dal punto di vista computazionale del clustering agglomerativo.
Accoppia i cluster con i vicini reciproci più vicini
Per prima cosa procediamo per trovare cluster con vicini reciproci, il che significa che i loro vicini più vicini sono tra loro (ricorda, la distanza può essere direzionale!).
Unisci coppie
RAC è parallelizzabile perché non importa in quale ordine vengono fusi i reciproci vicini più vicini, purché il metodo di collegamento sia riducibile.
Un metodo di collegamento è la funzione che determina la distanza tra due cluster, in base alle distanze a coppie tra i punti contenuti in ciascun cluster. UN riducibile Il metodo di collegamento garantisce che il nuovo cluster unito non sia più vicino a nessun altro cluster dopo l’unione.
Fortunatamente, i quattro metodi di collegamento più popolari sono riducibili:
- Collegamento singolo: distanza minima
- Collegamento medio — media delle distanze
- Collegamento completo: distanza massima
- Collegamento dei reparti: minimizzare la varianza
Poiché sappiamo che le nostre coppie reciproche identificate sono le reciproche coppie vicine più vicine l’una dell’altra, e sappiamo che le fusioni di collegamenti riducibili non renderanno mai un cluster appena unito più vicino a un altro cluster, possiamo unire in sicurezza tutte le coppie reciproche vicine più vicine insieme contemporaneamente. Ciascuna coppia del vicino più vicino può essere inserita in un thread disponibile per essere unita in base al metodo di collegamento.
Il fatto che possiamo unire i reciproci vicini più vicini allo stesso tempo è fantastico, perché unire i cluster è il passo più costoso dal punto di vista computazionale!
Aggiorna i vicini più vicini
Con il collegamento riducibile, anche l’ordine in cui i vicini più vicini vengono aggiornati dopo la fusione non ha importanza. Pertanto, con una progettazione intelligente, possiamo aggiornare parallelamente anche i vicini rilevanti.
Conclusione
Con alcuni set di dati di prova, lo abbiamo dimostrato RAC++ produce esattamente gli stessi risultati del tradizionale clustering agglomerativo (es. sklearn) per set di dati completamente connessi con un runtime molto migliore. Con la comprensione delle metriche di collegamento riducibili e una conoscenza di base della programmazione parallela, possiamo comprendere la logica che crea RAC++ molto più veloce.
Per una comprensione (e dimostrazione) più completa dell’algoritmo RAC++ha adottato in open source, dai un’occhiata a ricerca originale di Google era basato su.
Il futuro
Porter Hunley ha iniziato a creare RAC++ per creare tassonomie per gli endpoint dei termini clinici prodotti tramite incorporamenti BERT ottimizzati. Ciascuno di questi incorporamenti medici aveva 768 dimensioni e tra i numerosi algoritmi di clustering provati, solo il clustering agglomerativo ha dato buoni risultati.
Tutti gli altri metodi di clustering su larga scala richiedevano la riduzione della dimensionalità per fornire risultati coerenti. Sfortunatamente non esiste un modo infallibile per ridurre la dimensionalità: perderesti sempre informazioni.
Dopo aver scoperto la ricerca di Google sul RAC, Porter ha deciso di creare un’implementazione di clustering open source personalizzata per supportare la sua ricerca sul clustering di termini clinici. Porter è stato responsabile dello sviluppo e io ho co-sviluppato parti di RAC, in particolare racchiudendo l’implementazione C++ in Python, ottimizzando il runtime e confezionando il software per la distribuzione.
RAC++ consente tonnellate di applicazioni di clustering che sono troppo lente utilizzando il tradizionale clustering agglomerativo e alla fine saranno scalabili a milioni di punti dati.
Sebbene RAC++ possa già essere utilizzato per raggruppare set di dati di grandi dimensioni, ci sono miglioramenti da apportare… RAC++ è ancora in fase di sviluppo: contribuisci per favore!
Autori che contribuiscono:
SCOPRI LA NOSTRA GUIDA COMPLETA: COME CREARE UN’INTELLIGENZA ARTIFICIALE CON PYTHON
