scikit-learn DBSCAN utilizzo della memoria

Question

AGGIORNATO: Alla fine, la soluzione che ho scelto di utilizzare per raggruppare il mio grande set di dati è stata suggerita da Anony-Mousse di seguito. Cioè, usando l'impiantazione DBSCAN di ELKI per fare il mio clustering piuttosto che scikit-learn. Può essere eseguito dalla riga di comando e con indicizzazione corretta, esegue questa attività entro poche ore. Usa la GUI e piccoli set di dati campione per elaborare le opzioni che desideri utilizzare e poi andare in città. Vale la pena esaminare. Chiunque, continua a leggere per una descrizione del mio problema originale e qualche discussione interessante.

Ho un set di dati con ~ 2,5 milioni di campioni, ciascuno con 35 funzioni (valori in virgola mobile) che sto cercando di raggruppare. Ho cercato di farlo con l'implementazione di DBSCAN di scikit-learn, utilizzando la metrica di distanza di Manhattan e un valore di epsilon stimato da alcuni piccoli campioni casuali tratti dai dati. Fin qui tutto bene. (Qui è il frammento di, per riferimento)

db = DBSCAN(eps=40, min_samples=10, metric='cityblock').fit(mydata) 

Il mio problema in questo momento è che ho facilmente a corto di memoria. (Attualmente sto lavorando su una macchina con 16 GB di RAM)

La mia domanda è, è DBSCAN che calcola la matrice della distanza in coppia al volo mentre corre, e questo è ciò che mi sta assorbendo la memoria? (2,5 milioni^2) * 8 byte è ovviamente stupidamente grande, lo capisco. Non dovrei usare il metodo fit()? E più in generale, c'è un modo per aggirare questo problema, o sto generalmente abbaiando dall'albero sbagliato qui?

Ci scusiamo se la risposta si rivela evidente. Ci sono rimasto perplesso per alcuni giorni. Grazie!

Addendum: Anche se qualcuno potrebbe spiegare la differenza tra fit(X) e fit_predict(X) a me più esplicitamente Vorrei anche apprezzato che - temo solo che non riesce quasi mai esso.

Addendum n. 2: Per essere sicuri, ho appena provato questo su una macchina con ~ 550 GB di RAM e si è ancora fatto esplodere, quindi mi sento come se DBSCAN stia tentando di creare una matrice a distanza di coppia o qualcosa che indosso chiaramente lo voglio fare Immagino che ora la grande domanda sia come fermare quel comportamento, o trovare altri metodi che potrebbero soddisfare di più le mie esigenze. Grazie per aver portato con me qui.

Addendum # 3 (!): Ho dimenticato di allegare il traceback, eccolo,

Traceback (most recent call last): 
    File "tDBSCAN.py", line 34, in <module> 
    db = DBSCAN(eps=float(sys.argv[2]), min_samples=10, metric='cityblock').fit(mydata) 
    File "/home/jtownsend/.local/lib/python2.6/site-packages/sklearn/base.py", line 329, in fit_predict 
    self.fit(X) 
    File "/home/jtownsend/.local/lib/python2.6/site-packages/sklearn/cluster/dbscan_.py", line 186, in fit 
    **self.get_params()) 
    File "/home/jtownsend/.local/lib/python2.6/site-packages/sklearn/cluster/dbscan_.py", line 69, in dbscan 
    D = pairwise_distances(X, metric=metric) 
    File "/home/jtownsend/.local/lib/python2.6/site-packages/sklearn/metrics/pairwise.py", line 651, in pairwise_distances 
    return func(X, Y, **kwds) 
    File "/home/jtownsend/.local/lib/python2.6/site-packages/sklearn/metrics/pairwise.py", line 237, in manhattan_distances 
    D = np.abs(X[:, np.newaxis, :] - Y[np.newaxis, :, :]) 
MemoryError 

Answer 1

Il problema apparentemente è un'implementazione DBSCAN di bassa qualità in scikit.

DBSCAN non richiede una matrice di distanza. L'algoritmo è stato progettato utilizzando un database in grado di accelerare una funzione regionQuery e restituire i vicini all'interno del raggio della query in modo efficiente (un indice spaziale dovrebbe supportare tali query in O(log n)).

L'implementazione in scikit tuttavia, a quanto pare, calcola tutta la matrice di distanza O(n^2), che ha un costo sia in termini di memoria che di runtime.

Così vedo due scelte:

1. Si consiglia di provare l'attuazione DBSCAN in ELKI invece, che quando viene utilizzato con una R * indice -tree solito è sostanzialmente più veloce di un'implementazione ingenuo.

2. Altrimenti, è possibile reimplementare DBSCAN, in quanto l'implementazione in scikit non sembra essere troppo buona. Non aver paura di questo: DBSCAN è davvero semplice da implementare. La parte più difficile di una buona implementazione di DBSCAN è in realtà la funzione regionQuery. Se riesci a ottenere rapidamente questa query, DBSCAN sarà veloce. E puoi effettivamente riutilizzare questa funzione anche per altri algoritmi.

Aggiornamento: ormai, sklearn non calcola una distanza matrice e può, ad esempio, utilizzare un indice kd-tree. Tuttavia, a causa della "vettorizzazione", precomputerà ancora i vicini di ogni punto, quindi l'utilizzo della memoria di sklearn per epsilon di grandi dimensioni è O (n²), mentre per la mia comprensione la versione di ELKI userà solo la memoria O (n). Quindi, se esaurisci la memoria, scegli un epsilon più piccolo e/o prova con ELKI.

Answer 2

L'algoritmo DBSCAN realmente fa calcolare la matrice di distanza, quindi nessuna possibilità qui. Per questi molti dati, consiglierei l'uso di MiniBatchKMeans. Non è possibile utilizzare la metrica di Manhattan in quel momento, ma è possibile eseguire la propria implementazione. Forse prova prima l'implementazione standard con la metrica euclidea.

Non conosco molti algoritmi di clustering che non eseguono le distanze a coppie.

Utilizzo del nuovo centro interno cheat-sheet in basso: buona fortuna.

Answer 3

È possibile eseguire questa operazione utilizzando DBSCAN di scikit-learn con la metrica di haversine e l'algoritmo della sfera. Non è necessario precompilare una matrice di distanze.

Questo esempio clusters over a million GPS latitude-longitude points con DBSCAN/haversine ed evita problemi di utilizzo della memoria:

df = pd.read_csv('gps.csv') 
coords = df.as_matrix(columns=['lat', 'lon']) 
db = DBSCAN(eps=eps, min_samples=ms, algorithm='ball_tree', metric='haversine').fit(np.radians(coords)) 

Si noti che questo utilizza specificamente scikit-learn v0.15, come alcune versioni precedenti/successivi sembrano richiedere una distanza completa matrice da calcolare, che fa esplodere la tua RAM in modo veloce. Ma se si utilizza Anaconda, è possibile impostare rapidamente questo con:

conda install scikit-learn=0.15 

Oppure, creare un ambiente virtuale pulito per questo compito il clustering:

conda create -n clusterenv python=3.4 scikit-learn=0.15 matplotlib pandas jupyter 
activate clusterenv