Libreria di clustering su larga scala possibilmente con collegamenti Python

Question

Ho cercato di raggruppare un insieme di dati più grande. composto da 50000 vettori di misura con dimensione 7. Sto provando a generare da 30 a 300 cluster per ulteriori elaborazioni.

Ho provato le seguenti implementazioni di clustering senza fortuna:

• Pycluster.kcluster (dà solo 1-2 grappoli non vuote sul mio set di dati)
• scipy.cluster.hierarchy.fclusterdata (corre troppo lungo)
• scipy.cluster.vq.kmeans (esaurisce la memoria)
• sklearn.cluster.hierarchical.Ward (corre troppo a lungo)

Esistono altre implementazioni che potrei perdere?

Answer 1

50000 istanze e 7 dimensioni non sono molto grandi e non dovrebbero uccidere un'implementazione.

Anche se non ha il collegamento Python, dare una prova a ELKI. Il set di benchmark che usano nella loro homepage è 110250 istanze in 8 dimensioni, e eseguono k-means su di esso in 60 secondi apparentemente, e l'OTTICA molto più avanzata in 350 secondi.

Evitare il clustering gerarchico. È davvero solo per piccoli set di dati. Il modo in cui viene comunemente implementato nelle operazioni con le matrici è O(n^3), ovvero in realtà non valido per i set di dati di grandi dimensioni. Quindi non sono sorpreso che questi due siano scaduti per te.

DBSCAN e OPTICS se implementati con supporto dell'indice sono O(n log n). Se implementati in modo ingenuo, si trovano in O(n^2). K-means è veramente veloce, ma spesso i risultati non sono soddisfacenti (perché si divide sempre nel mezzo). Dovrebbe essere eseguito in O(n * k * iter) che di solito converge in non troppe iterazioni (iter<<100). Ma funzionerà solo con distanza euclidea, e semplicemente non funziona bene con alcuni dati (ad alta dimensione, discreti, binari, cluster con dimensioni diverse, ...)

Answer 2

OpenCV ha un k-means attuazione, Kmeans2

previsto tempo di esecuzione è dell'ordine di O(n**4) - per un'approssimazione ordine di grandezza, vedere il tempo necessario a raggrupparsi 1000 punti, quindi moltiplicare per sette milioni (50 ** 4 arrotondati per eccesso).

Answer 3

Dal momento che stai già provando scikit-imparare : sklearn.cluster.KMeans dovrebbe scalare meglio di Ward e supporta l'adattamento parallelo su macchine multicore. MiniBatchKMeans è ancora meglio, ma non farà riavvii casuali per te.

>>> from sklearn.cluster import MiniBatchKMeans 
>>> X = np.random.randn(50000, 7) 
>>> %timeit MiniBatchKMeans(30).fit(X) 
1 loops, best of 3: 114 ms per loop 

Answer 4

Il mio pacchetto milk gestisce questo problema facilmente:

import milk 
import numpy as np 
data = np.random.rand(50000,7) 
%timeit milk.kmeans(data, 300) 
1 loops, best of 3: 14.3 s per loop 

Mi chiedo se si intende scrivere 500.000 punti dati, perché 50k punti non è più di tanto. Se è così, il latte impiega un po 'più di tempo (~ 700 sec), ma continua a gestirlo bene in quanto non assegna memoria diversa dai tuoi dati e dai centroidi.