biblioteca de clústeres a gran escala posiblemente con enlaces de python

Question

He intentado agrupar algunos datos más grandes. que consta de 50000 vectores de medición con una dimensión 7. Estoy tratando de generar de 30 a 300 clústeres para su posterior procesamiento.

He estado tratando los siguientes implementaciones de agrupamiento sin suerte:

• Pycluster.kcluster (da sólo 1-2 racimos no vacías en mi conjunto de datos)
• scipy.cluster.hierarchy.fclusterdata (corre demasiado tiempo)
• scipy.cluster.vq.kmeans (se queda sin memoria)
• sklearn.cluster.hierarchical.Ward (es demasiado largo)

¿Hay alguna otra implementación que pueda perder?

Answer 1

50000 instancias y 7 dimensiones no es realmente grande, y no debería matar a una implementación.

Aunque no tiene enlace de pitón, pruebe ELKI. El conjunto de referencia que utilizan en su página de inicio es 110250 instancias en 8 dimensiones, y ejecutan k-means en él en 60 segundos aparentemente, y el OPTICS mucho más avanzado en 350 segundos.

Evite la agrupación jerárquica. Es realmente solo para pequeños conjuntos de datos. La forma en que se implementa comúnmente en las operaciones de la matriz es O(n^3), que es realmente malo para grandes conjuntos de datos. Así que no estoy sorprendido de que estos dos hayan expirado.

DBSCAN y OPTICS cuando se implementan con soporte de índice son O(n log n). Cuando se implementa ingenuamente, están en O(n^2). K-means es realmente rápido, pero a menudo los resultados no son satisfactorios (porque siempre se divide en el medio). Debería ejecutarse en O(n * k * iter), que generalmente converge en no demasiadas iteraciones (iter<<100). Pero solo funcionará con la distancia euclidiana, y simplemente no funciona bien con algunos datos (alta dimensión, discreto, binario, clústeres con diferentes tamaños, ...)

Answer 2

OpenCV tiene una k-medias aplicación, Kmeans2

esperado tiempo de ejecución es del orden de O(n**4) - para una aproximación de orden de magnitud, ver cuánto tiempo toma a agruparse 1000 puntos, a continuación, que se multiplican por siete millones (50 ** 4 redondeados).

Answer 3

Dado que ya estás intentando scikit-learn : sklearn.cluster.KMeans debe escalar mejor que Ward y admite el ajuste paralelo en máquinas multinúcleo. MiniBatchKMeans es mejor aún, pero no hará reinicios aleatorios para usted.

>>> 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

Mi paquete milk maneja este problema fácilmente:

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 

Me pregunto si usted significó para escribir 500.000 puntos de datos, ya que 50k puntos no es mucho. Si es así, la leche tarda un poco más (~ 700 seg), pero todavía se maneja bien, ya que no asigna ninguna memoria que no sean sus datos y los centroides.