Algoritmos rápidos para encontrar la distancia euclidiana por pares (matriz de distancia)

Sé que Matlab tiene una función pdist integrada que calculará las distancias por pares. Sin embargo, mi matriz es tan grande que su 60000 por 300 y matlab se queda sin memoria.

Esta pregunta es un seguimiento de la función de distancia cuadrada euclidiana por pares de Matlab .

¿Hay alguna solución para esta ineficiencia computacional? Intenté codificar manualmente los cálculos de distancia por pares y, por lo general, toma un día completo para ejecutarse (a veces de 6 a 7 horas).

¡Cualquier ayuda es muy apreciada!

Bueno, no pude resistirme a jugar. pdistc archivo C de Matlab mex llamado pdistc que implementa distancia Euclidiana por pares para precisión simple y doble. En mi máquina con Matlab R2012b y R2015a es 20-25% más rápido que pdist (y la función de ayuda pdistmex subyacente) para entradas grandes (por ejemplo, 60,000 por 300).

Como se ha señalado, este problema está fundamentalmente limitado por la memoria y usted está pidiendo mucho. Mi código C mex utiliza una memoria mínima más allá de la necesaria para la salida. Al comparar su uso de memoria con el de pdist , parece que los dos son prácticamente iguales. En otras palabras, pdist no está usando mucha memoria extra. Es probable que tu problema de memoria se haya agotado en la memoria antes de llamar a pdist (¿puedes usar clear para eliminar matrices grandes?) O simplemente porque estás tratando de resolver un gran problema de cómputo en hardware pequeño.

Por lo tanto, pdistc probable que mi función pdistc no pueda guardar la memoria en general, pero es posible que pueda utilizar otra función que incorporé. Puede calcular fragmentos de su vector de distancia por pares global. Algo como esto:

 m = 6e3; n = 3e2; X = rand(m,n); sz = m*(m-1)/2; for i = 1:m:sz-m D = pdistc(X', i, i+m); % mex C function, X is transposed relative to pdist ... % Process chunk of pairwise distances end 

Esto es considerablemente más lento (10 veces más o menos) y esta parte de mi código C no está bien optimizada, pero permitirá un uso mucho menor de la memoria, suponiendo que no necesita toda la matriz al mismo tiempo. Tenga en cuenta que puede hacer lo mismo mucho más eficientemente con pdist (o pdistc ) creando un bucle donde pasa directamente en subconjuntos de X , en lugar de hacerlo todo.

Si tiene una Intel Mac de 64 bits, no necesitará comstackr ya que he incluido el binario .mexmaci64 , pero de lo contrario deberá averiguar cómo comstackr el código para su máquina. No puedo ayudarte con eso. Es posible que no pueda comstackr o que haya problemas de compatibilidad que necesitará resolver editando el código usted mismo. También es posible que haya errores y el código bloqueará Matlab. Además, tenga en cuenta que puede obtener salidas ligeramente diferentes en relación con pdist con diferencias entre los dos en el rango de epsilon de la máquina ( eps ). pdist puede o no hacer cosas sofisticadas para evitar desbordamientos de grandes entradas y otros problemas numéricos, pero tenga en cuenta que mi código no lo hace.

Además, creé una implementación pura y simple de Matlab . Es masivamente más lento que el código mex, pero aún más rápido que una implementación ingenua o el código que se encuentra en pdist .

Todos los archivos se pueden encontrar aquí . El archivo ZIP incluye todos los archivos. Tiene licencia BSD. Siéntase libre de optimizar (Probé las llamadas BLAS y OpenMP en el código C en vano, tal vez algún puntero mágico o GPU / OpenCL podría acelerarlo aún más). Espero que pueda ser útil para usted u otra persona.

En mi sistema, el siguiente es el más rápido (incluso más rápido que el código de pdistc de @horchler):

 function [ mD ] = CalcDistMtx ( mX ) vSsqX = sum(mX .^ 2); mD = sqrt(bsxfun(@plus, vSsqX.', vSsqX) - (2 * (mX.' * mX))); end 

Necesitarás un código C muy ajustado para superar esto, creo.

Actualizar
Como MATLAB R2016b MATLAB admite transmisiones implícitas sin el uso de bsxfun() .

Por lo tanto, el código se puede escribir:

 function [ mD ] = CalcDistMtx ( mX ) vSsqX = sum(mX .^ 2, 1); mD = sqrt(vSsqX.'+ vSsqX - (2 * (mX.' * mX))); end 

Se da una generalización en mi proyecto Calculate Distance Matrix .

PD
Usando el pdist de MATLAB para la comparación: squareform(pdist(mX.')) Es equivalente a CalcDistMtx(mX) .
Es decir, la entrada debe transponerse.

Las computadoras no son infinitamente grandes, o infinitamente rápidas. La gente piensa que tienen mucha memoria, una CPU rápida, por lo que solo crean problemas cada vez mayores y, finalmente, se preguntan por qué su problema se desarrolla lentamente. El hecho es que esto NO es una ineficiencia computacional. Es SOLO una CPU sobrecargada.

Como señala Oli en un comentario, hay algo así como 2e9 valores para calcular, incluso suponiendo que solo calcule la mitad superior o inferior de la matriz de distancia. (6e4 ^ 2/2 es aproximadamente 2e9.) Esto requerirá aproximadamente 16 gigabytes de RAM para almacenar, suponiendo que solo se crea en la memoria UNA copia del arreglo. Si su código es descuidado, puede duplicarlo o triplicarlo fácilmente. Tan pronto como entras en la memoria virtual, las cosas se vuelven mucho más lentas.

Querer un gran problema para correr rápido no es suficiente. Para ayudarlo realmente, necesitamos saber cuánta RAM hay disponible. ¿Es esto un problema de memoria virtual? ¿Estás usando MATLAB de 64 bits en una CPU que puede manejar toda la RAM necesaria?

    Intereting Posts