Scaling Agglomerative Clustering for Big Data’ ‘Scalare l’agglomerazione clustering per Big Data

Agglomerative Clustering Scaling for Big Data

Impara come utilizzare il Clustering Agglomerativo Reciproco (RAC) per creare clustering gerarchico di grandi dataset

Introduzione

Il clustering agglomerativo è uno degli strumenti di clustering migliori in data science, ma le implementazioni tradizionali non riescono a scalare su grandi dataset.

In questo articolo, ti guiderò attraverso alcuni concetti di base sul clustering agglomerativo, un’introduzione al clustering agglomerativo reciproco (RAC) basato sulla ricerca del 2021 di Google, un confronto di runtime tra RAC++ e AgglomerativeClustering di scikit-learn, e infine una breve spiegazione della teoria dietro RAC.

Concetti di base sul clustering agglomerativo

In data science, è spesso utile raggruppare dati non etichettati. Con applicazioni che vanno dal raggruppamento dei risultati dei motori di ricerca alla classificazione dei genotipi, al rilevamento delle anomalie bancarie, il clustering è un elemento essenziale nel toolkit di un data scientist.

Il clustering agglomerativo è uno degli approcci di clustering più popolari in data science e per buoni motivi, perché:

• Ricercatori sviluppano un’intelligenza artificiale che consente a un robot di creare piani complessi utilizzando l’intera mano
• Differenziazione automatica con Python e C++ per il Deep Learning
• ChatGPT Enterprise per le grandi aziende sarà lanciato da OpenAI

✅ È facile da usare con poca o nessuna regolazione dei parametri✅ Crea tassonomie significative✅ Funziona bene con dati ad alta dimensionalità✅ Non è necessario conoscere il numero di cluster in anticipo✅ Crea gli stessi cluster ogni volta

In confronto, i metodi di partizionamento come K-Means richiedono al data scientist di indovinare il numero di cluster, il metodo basato sulla densità molto popolare DBSCAN richiede alcuni parametri per il calcolo della densità (raggio epsilon) e la dimensione minima del vicinato, e i modelli di mistura gaussiana fanno forti ipotesi sulla distribuzione dei dati dei cluster sottostanti.

Con il clustering agglomerativo, devi solo specificare una metrica di distanza.

A livello generale, il clustering agglomerativo segue l’algoritmo seguente:

1. Identificare le distanze tra i cluster per tutte le coppie di cluster (ogni cluster inizia come un singolo punto)
2. Unire i due cluster più vicini tra loro
3. Ripetere

Risultato: un bellissimo dendrogramma che può poi essere partizionato in base all’esperienza di 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 punto di taglio finale del clustering.

Nell’immagine sottostante viene mostrato un esempio di clustering agglomerativo con il famoso dataset dell’Iris.

Allora perché non utilizzare il clustering agglomerativo per ogni problema di classificazione non supervisionata?

❌ Il clustering agglomerativo ha un tempo di esecuzione terribile al crescere delle dimensioni dei dataset.

Purtroppo, il clustering agglomerativo tradizionale non scala. Il tempo di esecuzione è O(n³) o O(n²log(n)) se implementato con un min-heap. Ancora peggio, il clustering agglomerativo viene eseguito in modo sequenziale su un singolo core e non può essere scalato con il calcolo.

Nel campo dell’NLP, il clustering agglomerativo è tra i migliori… per piccoli dataset.

Clustering Agglomerativo Reciproco (RAC)

Il Clustering Agglomerativo Reciproco (RAC) è un metodo proposto da Google per scalare i vantaggi del clustering agglomerativo tradizionale a dataset più grandi.

RAC riduce la complessità del tempo di esecuzione e parallelizza le operazioni per utilizzare un’architettura multi-core. Nonostante queste ottimizzazioni, RAC produce gli stessi risultati del clustering agglomerativo tradizionale quando i dati sono completamente connessi (vedi sotto).

Nota: I dati completamente connessi significano che è possibile calcolare una metrica di distanza tra qualsiasi coppia di punti. I dataset non completamente connessi hanno vincoli di connettività (di solito forniti sotto forma di una matrice di collegamento) in cui alcuni punti vengono considerati disconnessi.

Anche con vincoli di connettività (dati che non sono completamente connessi), RAC e l’agglomerazione sono ancora tipicamente identici, come si può vedere nel secondo esempio di dataset Swiss Roll sopra.

Tuttavia, possono emergere grandi discrepanze quando ci sono pochissimi possibili cluster. Il dataset Noisy Moons ne è un buon esempio:

RAC++ scala a dataset più grandi rispetto a scikit-learn

Possiamo confrontare RAC++ (un’implementazione dell’agglomerazione riciproca) con il suo corrispettivo, AgglomerativeClustering, in scikit-learn.

Generiamo alcuni dati di esempio con 25 dimensioni e testiamo quanto tempo richiede l’agglomerazione utilizzando racplusplus.rac rispetto a sklearn.cluster.AgglomerativeClustering per dataset di dimensioni comprese tra 1.000 e 64.000 punti.

Nota: Sto usando una matrice di connettività per limitare il consumo di memoria.

import numpy as npimport racplusplusfrom sklearn.cluster import AgglomerativeClusteringimport timepoints = [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)  # La matrice deve essere simmetrica - fatta internamente 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)

Ecco un grafico dei risultati dei tempi di esecuzione per ogni dimensione del dataset:

Come possiamo vedere, ci sono differenze drastiche nei tempi di esecuzione tra RAC++ e l’agglomerazione tradizionale.

A poco più di 30.000 punti, RAC++ è circa 100 volte più veloce! Ancora più importante, l’agglomerazione di scikit-learn raggiunge un limite di tempo a ~35.000 punti, mentre RAC++ potrebbe scalare fino a centinaia di migliaia di punti entro il raggiungimento di un limite di tempo ragionevole.

RAC++ può scalare a dimensioni elevate

Possiamo anche confrontare quanto bene RAC++ scala rispetto ai dati ad alta dimensionalità rispetto al suo corrispettivo 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 embedding a 768 o 1536 dimensioni è diventato lo standard nel campo del NLP, quindi scalare la dimensionalità per soddisfare tali requisiti è importante.

RAC++ ha un tempo di esecuzione migliore

Ricercatori di Google hanno dimostrato che RAC ha un tempo di esecuzione 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 iniziale della matrice delle distanze che ha un tempo di esecuzione quadratico di O(n²).

I nostri risultati, eseguendo un vincolo di connettività costante di 30 vicini, confermano un tempo di esecuzione di O(n²):

+ — — — — — — -+ — — — — — +| Punti dati | Secondi |+ - - - - - - -+ - - - - - +| 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 un aumento di 4 volte del tempo.

Un tempo di esecuzione quadratico limita le prestazioni di RAC++ quando i set di dati diventano veramente massicci, tuttavia, questo tempo di esecuzione rappresenta già un grande miglioramento rispetto al tradizionale tempo di esecuzione di O(n³) o al tempo di esecuzione ottimizzato con heap minimo O(n²log(n)).

Nota: gli sviluppatori di RAC++ stanno lavorando per passare la matrice delle distanze come parametro, il che darebbe a RAC++ un tempo di esecuzione lineare.

Come funziona RAC

Perché RAC++ è così veloce? Possiamo ridurre l’algoritmo sottostante a pochi passaggi:

1. Associa cluster con vicini reciproci più prossimi
2. Unisci le coppie di cluster
3. Aggiorna i vicini

Si noti che l’unica differenza rispetto all’algoritmo di clustering agglomerativo tradizionale è che ci assicuriamo di associare insieme i vicini reciproci più prossimi. Da qui deriva il nome Reciprocal Agglomerative Clustering (RAC). Come vedrete, questa associazione reciproca ci consente di parallelizzare il passaggio più computazionalmente oneroso del clustering agglomerativo.

Associa cluster con vicini reciproci più prossimi

Prima di tutto, iteriamo per trovare cluster con vicini reciproci più prossimi, il che significa che i loro vicini più vicini sono reciprocamente tra loro (ricordate, la distanza può essere direzionale!).

Unisci le coppie

RAC è parallelizzabile perché non importa in quale ordine vengono unite le coppie di vicini reciproci più prossimi, purché il metodo di collegamento sia riducibile.

Un metodo di collegamento è la funzione che determina la distanza tra due cluster, basata sulle distanze tra coppie di punti contenuti in ciascun cluster. Un metodo di collegamento riducibile garantisce che il nuovo cluster unito non sia più vicino a nessun altro cluster dopo l’unione.

Fortunatamente, i quattro metodi di linkage più popolari sono riducibili:

• Linkage singolo – distanza min
• Linkage medio – media delle distanze
• Linkage completo – distanza max
• Linkage di Ward – minimizzazione della varianza

Dato che sappiamo che le coppie reciproche identificate sono il vicino più vicino l’una dell’altra, e sappiamo che le fusioni di linkage riducibili non renderanno mai un cluster appena fuso più vicino a un altro cluster, possiamo fondere in sicurezza tutte le coppie reciproche di vicini più vicini contemporaneamente. Ogni coppia di vicini più vicini può essere inserita in un thread disponibile per essere fusa secondo il metodo di linkage.

Il fatto che possiamo fondere i vicini più vicini reciproci contemporaneamente è fantastico, perché la fusione di cluster è la fase più costosa dal punto di vista computazionale!

Aggiorna i vicini più vicini

Con il linkage riducibile, l’ordine con cui vengono aggiornati i vicini più vicini dopo la fusione non ha importanza. Pertanto, con un po’ di ingegno, possiamo aggiornare i vicini rilevanti in parallelo.

Conclusioni

Con alcuni dataset di test, abbiamo dimostrato che RAC++ produce gli stessi risultati dell’Agglomerative Clustering tradizionale (cioè sklearn) per dataset completamente connessi con un tempo di esecuzione molto migliore. Con una comprensione delle metriche di linkage riducibili e una conoscenza di base della programmazione parallela, possiamo capire la logica che rende RAC++ così veloce.

Per una comprensione (e una prova) più completa dell’algoritmo su cui RAC++ si basa su open-source, dai un’occhiata alla ricerca originale di Google su cui è stato basato.

Il futuro

Porter Hunley ha iniziato a costruire RAC++ per creare tassonomie per gli endpoint dei termini clinici prodotti tramite l’impiego di embedding BERT ottimizzati. Ciascuno di questi embedding medici aveva 768 dimensioni e, tra i vari algoritmi di clustering provati, solo il clustering agglomerativo ha dato buoni risultati.

Tutti gli altri metodi di clustering di larga scala richiedevano la riduzione della dimensionalità per ottenere risultati coerenti. Purtroppo, non esiste un modo infallibile per ridurre la dimensionalità: si perderà sempre informazione.

Dopo aver scoperto la ricerca di Google su RAC, Porter ha deciso di costruire un’implementazione di clustering open-source personalizzata per supportare la sua ricerca sul clustering dei termini clinici. Porter ha guidato lo sviluppo, mentre io ho contribuito allo sviluppo di alcune parti di RAC, in particolare avvolgendo l’implementazione in C++ in Python, ottimizzando il tempo di esecuzione e confezionando il software per la distribuzione.

RAC++ permette molte applicazioni di clustering che sono troppo lente con il clustering agglomerativo tradizionale e alla fine sarà scalabile a milioni di punti dati.

Anche se RAC++ può già essere utilizzato per raggruppare grandi dataset, ci sono miglioramenti da fare… RAC++ è ancora in fase di sviluppo – si prega di contribuire!

Autore dei contributi:

• Porter Hunley, Senior Software Engineer presso Daceflow.ai: github
• Daniel Frees, studente di laurea in Statistica e Scienza dei Dati presso Stanford, Data Scientist presso IBM: github

GitHub – porterehunley/RACplusplus: Un’implementazione ad alte prestazioni del Reciprocal Agglomerative…