Agrupación ~ 100,000 cadenas cortas en Python

Quiero agrupar ~ 100,000 cadenas cortas por algo así como distancia de q-gramo o simple "distancia de bolsa" o tal vez distancia de Levenshtein en Python. Estaba planeando completar una matriz de distancia (100.000 elegir 2 comparaciones) y luego hacer una agrupación jerárquica con pyCluster. Pero me estoy encontrando con algunos problemas de memoria incluso antes de despegar. Por ejemplo, la matriz de distancia es demasiado grande para numpy.Agrupación ~ 100,000 cadenas cortas en Python

aa = numpy.zeros((100000, 100000)) 
ValueError: array is too big.

¿Esto parece una medida razonable de hacer? ¿O estoy condenado a problemas de memoria en esta tarea? Gracias por tu ayuda.

Fuente

2010-11-22 135498

10 mil millones es un número grande. – nmichaels

Estoy pensando en un enfoque para este problema divertido, pero extraño algo de información. Detalla un poco más qué es exactamente lo que estás tratando de lograr, así como por qué y las posibles suposiciones/limitaciones. Aquí hay 2 preguntas particulares. 1) ¿Puedes tener cadenas replicadas en tu análisis? 2) ¿Realmente necesitas todas las distancias de 2 por 2 o decir que solo una proporción de las distancias más pequeñas para una cadena dada sería suficiente? Aclamaciones. – Morlock

100,000 * 100,000 * 32bits = 40 GBytes, que serían mucho de RAM, así que sí, necesita encontrar otra forma. (E incluso si pudiera ajustar estos datos en la memoria, el cálculo tomaría demasiado tiempo).

Un atajo común y fácil consiste en agrupar un pequeño subconjunto aleatorio de los datos, y después de encontrar los conglomerados de este subconjunto, simplemente coloque el resto de los puntos en los grupos donde se ajusten mejor.

Fuente

2010-11-22 02:35:31 tom10

¿Su máquina no tiene 4096 GB de memoria? –

Gracias por los cálculos. Sí, el enfoque actual parece imposible. – 135498

Disculpe, solo detalle aquí, dos años después: dado que la matriz de distancia es simétrica, sería de 20 GB. –

10 mil millones de elementos es una gran cantidad. No sé por q-grams, pero si esa matriz es escasa, podrías usar un elemento dict 200,000-ish.

Fuente

2010-11-22 02:38:28 nmichaels

He leído sobre matrices dispersas.Incierto si los datos son escasos, como dices ... Tendría que hacer más pruebas. Tampoco está claro (para mí) si pyCluster puede manejar matrices dispersas. Gracias por su consejo. – 135498

¿Qué quieres hacer con los datos? Esa es una pregunta bastante importante, creo. –

En principio, dicha matriz no sería escasa. Un problema de crear una matriz tan dispersa es cómo determinar si algún elemento de la matriz se va a evaluar o no. – cyborg

¿Necesita la matriz? Supongo que quieres usar una matriz para velocidad?

Tengo un algoritmo de clúster k-means (en lugar de un algoritmo de clúster jerárquico) y esto calcula las distancias de nodo según sea necesario. Sin embargo, probablemente solo sea viable para las mediciones de distancia rápida. Y tiene más datos que yo, pero está limitado por limitaciones de memoria.

Fuente

2010-11-23 18:20:46 winwaed

Sí, algo así parece ser la solución. Gracias. – 135498

Hay un método en Machine Learning llamada de inclusión que pueden, en principio, la búsqueda de una solución para este problema usando O (n + m) de memoria en lugar de O (n * m) (n = 10^5 elementos, m = 10^5 características). Desafortunadamente, no sé de un código fuente disponible que se implemente en O (m + n). Ver:

Incrustación euclidiana de datos de coincidencia. Amir Globerson, Gal Chechik, Fernando Pereira y Naftali Tishby. Journal of Machine Learning Research, JMLR, 8 (octubre), 2007. pdf/ Matlab code
Podría haber otras soluciones. Creo que debe hacer esta pregunta en un foro de personas de Machine Learning, por ejemplo, https://stats.stackexchange.com/, o incluso más específico para el procesamiento del lenguaje: http://metaoptimize.com/qa/.

Fuente

2011-10-09 18:18:34 cyborg

Agrupación ~ 100,000 cadenas cortas en Python

Respuesta

Cuestiones relacionadas