python - algoritmo - Uso de la memoria DBSCAN de scikit-learn
dbscan python (5)
ACTUALIZADO: al final, la solución que opté por usar para agrupar mi gran conjunto de datos fue una sugerida por Anony-Mousse a continuación. Es decir, usar la implementación DBSCAN de ELKI para hacer mi agrupación en lugar de scikit-learn. Se puede ejecutar desde la línea de comandos y con la indexación adecuada, realiza esta tarea en unas pocas horas. Use la GUI y los pequeños conjuntos de datos de muestra para elaborar las opciones que desea usar y luego ir a la ciudad. Vale la pena mirar De todos modos, sigue leyendo para obtener una descripción de mi problema original y algunas discusiones interesantes.
Tengo un conjunto de datos con ~ 2.5 millones de muestras, cada una con 35 características (valores de punto flotante) que estoy tratando de agrupar. He estado tratando de hacer esto con la implementación de scikit-learn de DBSCAN, utilizando la métrica de distancia de Manhattan y un valor de épsilon estimado a partir de algunas pequeñas muestras aleatorias extraídas de los datos. Hasta ahora tan bueno. (Aquí está el fragmento, para referencia)
db = DBSCAN(eps=40, min_samples=10, metric=''cityblock'').fit(mydata)
Mi problema en este momento es que fácilmente me quedo sin memoria. (Actualmente estoy trabajando en una máquina con 16 GB de RAM)
Mi pregunta es, ¿DBSCAN está calculando la matriz de distancia por pares sobre la marcha a medida que se ejecuta, y eso es lo que está engullendo mi memoria? (2.5 millones de ^ 2) * 8 bytes es obviamente estúpidamente grande, lo entendería. ¿No debería usar el método fit() ? Y, de manera más general, ¿hay alguna forma de solucionar este problema, o estoy generalmente ladrando el árbol equivocado aquí?
Disculpas si la respuesta termina siendo obvia. He estado desconcertado sobre esto por unos días. ¡Gracias!
Anexo: Además, si alguien pudiera explicarme la diferencia entre fit(X) y fit_predict(X) de forma más explícita, también lo apreciaría, me temo que no lo entiendo.
Anexo # 2: Para estar seguro, simplemente probé esto en una máquina con ~ 550 GB de RAM y todavía explotó, así que creo que DBSCAN probablemente está tratando de hacer una matriz de distancia por pares o algo que claramente no quiero. que hacer. Supongo que ahora la gran pregunta es cómo detener ese comportamiento o encontrar otros métodos que puedan satisfacer mis necesidades. Gracias por estar conmigo aquí.
Anexo # 3 (!): Olvidé adjuntar el rastreo, aquí está,
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
El algoritmo DBSCAN en realidad calcula la matriz de distancia, así que no hay posibilidad aquí. Por esta cantidad de datos, recomendaría usar MiniBatchKMeans. No puede usar la métrica de Manhattan allí fuera de la caja, pero podría hacer su propia implementación. Tal vez intente la implementación estándar con la métrica euclidiana primero.
No conozco muchos algoritmos de agrupamiento en clúster que no realizan distancias en pares.
Usando el centro inferior de la cheat-sheet recién incrustado: aunque suerte.
El problema aparentemente es una implementación DBSCAN de baja calidad en scikit .
DBSCAN no necesita una matriz de distancia. El algoritmo se diseñó utilizando una base de datos que puede acelerar una función regionQuery y devolver a los vecinos dentro del radio de la consulta de manera eficiente (un índice espacial debe admitir dichas consultas en O(log n) ).
La implementación en scikit , sin embargo, aparentemente, calcula la matriz de distancia completa O(n^2) , que tiene un costo tanto en memoria como en tiempo de ejecución.
Así que veo dos opciones:
Es posible que desee probar la implementación DBSCAN en ELKI , que cuando se usa con un índice R * -tree generalmente es mucho más rápido que una implementación ingenua.
De lo contrario, es posible que desee volver a implementar DBSCAN , ya que la implementación en
scikitaparentemente no es demasiado buena. No te preocupes por eso: DBSCAN es muy sencillo de implementar. La parte más complicada de una buena implementación de DBSCAN es en realidad la funciónregionQuery. Si puede obtener esta consulta rápidamente, DBSCAN será rápido. Y también puedes reutilizar esta función para otros algoritmos.
Actualización: por ahora, sklearn ya no calcula una matriz de distancia y puede, por ejemplo, usar un índice de kd-tree. Sin embargo, debido a la "vectorización" todavía precomputará a los vecinos de cada punto, por lo que el uso de la memoria de sklearn para epsilon grande es O (n²), mientras que para mi entender, la versión en ELKI solo usará la memoria O (n). Por lo tanto, si se queda sin memoria, elija un épsilon más pequeño y / o pruebe ELKI .
Enfrenté el mismo problema cuando estaba usando la versión antigua en sklearn 0.19.1 porque la complejidad era O (N ^ 2).
Pero ahora el problema se resolvió en la nueva versión 0.20.2 y ya no hay errores de memoria, y la complejidad se convierte en O (nd) donde d es el número promedio de vecinos. No es la complejidad del ídolo, pero es mucho mejor que las versiones anteriores.
Consulte las notas en esta versión para evitar un uso https://scikit-learn.org/stable/modules/generated/sklearn.cluster.DBSCAN.html memoria: https://scikit-learn.org/stable/modules/generated/sklearn.cluster.DBSCAN.html
Este problema con sklearn se discute aquí:
Hay dos opciones presentadas allí;
Una es usar OPTICS (que requiere sklearn v21 +), que es un algoritmo alternativo pero estrechamente relacionado con DBSCAN:
https://scikit-learn.org/dev/modules/generated/sklearn.cluster.OPTICS.html
Los otros son precomputar la matriz de adyacencia, o usar ponderaciones de la muestra. Algunos detalles más sobre estas opciones se pueden encontrar en Notas aquí:
https://scikit-learn.org/stable/modules/generated/sklearn.cluster.DBSCAN.html
Puede hacer esto utilizando el DBSCAN de scikit-learn con la métrica de haversine y el algoritmo de bola-árbol. No es necesario calcular previamente una matriz de distancia.
Este ejemplo agrupa más de un millón de puntos de latitud-longitud GPS con DBSCAN / haversine y evita problemas de uso de 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))
Tenga en cuenta que esto utiliza específicamente scikit-learn v0.15, ya que algunas versiones anteriores / posteriores parecen requerir una matriz de distancia completa para calcularse, lo que hace que su RAM se infle rápidamente. Pero si usa Anaconda, puede configurarlo rápidamente con:
conda install scikit-learn=0.15
O bien, cree un entorno virtual limpio para esta tarea de agrupación en clúster:
conda create -n clusterenv python=3.4 scikit-learn=0.15 matplotlib pandas jupyter
activate clusterenv