Octava: calcula la distancia entre dos matrices de vectores

12

Supongamos que tengo dos matrices Nx2, Mx2 que representan N, M 2d vectores respectivamente. ¿Hay una manera simple y buena de calcular distancias entre cada par de vectores (n, m)?

La manera fácil pero ineficiente es, por supuesto:

d = zeros(N, M);
for i = 1:N,
  for j = 1:M,
    d(i,j) = norm(n(i,:) - m(j,:));
  endfor;
endfor;

La respuesta más cercana que he encontrado es bsxfun, usada así:

bsxfun(inline("x-y"),[1,2,3,4],[3;4;5;6])

ans =
  -2 -1  0  1
  -3 -2 -1  0
  -4 -3 -2 -1
  -5 -4 -3 -2
performance octave vectorization Kelley van Evert
fuente
Eché un vistazo a esto y no pude hacer mucho mejor que vectorizar el cálculo. Creo que este cálculo es un buen candidato para escribir una función externa de C / Fortran.
Aron Ahmadia
1
Apuesto a que podrías hacer una matriz de 2xNxM que llenes con un producto externo, luego cuadrar cada una de las entradas y sumar a lo largo del eje cero y la raíz cuadrada. En Python esto se vería así: distance_matrix = (n [:,:, nexaxis] * m [:, newaxis ,:]); distance_matrix = distance_matrix ** 2; distance_matrix = sqrt (distance_matrix.sum (axis = 1)); Si solo necesita conocer los n-vectores más cercanos, ¡hay formas mucho mejores de hacerlo!
meawoppl
3
@meawoppl (Nuevo en Octave) Descubrí cómo usar el paquete de álgebra lineal en Octave, que proporciona cartprod, así que ahora puedo escribir: (1) x = cartprod(n(:,1), m(:,1)); (2) y = cartprod(n(:,2), m(:,2)); (3) d = sqrt((x(:,1)-x(:,2)).^2+(y(:,1)-y(:,2)).^2) ... ¡que funciona mucho más rápido!
Kelley van Evert
¿Qué tal octave.sourceforge.net/statistics/function/pdist.html
Nemo

Respuestas:

6

Vectorizar es sencillo en estas situaciones utilizando una estrategia como esta:

eN = ones(N,1);
eM = ones(M,1);
d  = sqrt(eM*n.^2' - 2*m*n' + m.^2*eN');

Aquí hay un ejemplo que vectoriza el ciclo for con una aceleración de 15x para M = 1000 y N = 2000.

n = rand(N,2);
m = rand(M,2);
eN = ones(N,2);
eM = ones(2,M);

tic;
d_vect  = sqrt(eN*m.^2' - 2*n*m' + n.^2*eM);
vect_time = toc;

tic;
for i=1:N
  for j=1:M
     d_for(i,j) = norm(n(i,:)-m(j,:));
  end
end
for_time = toc; 

assert(norm(d_vect-d_for) < 1e-10*norm(d_for))
David Bindel
fuente
David, me alegro de verte en scicomp! Edité descaradamente su fragmento de código y lo expandí un poco, reviértalo si mis ediciones fueron en la dirección incorrecta al aclarar lo que pretendía.
Aron Ahmadia
2

Desde Octave 3.4.3 y posterior, el operador realiza transmisiones automáticas (usa bsxfun internamente). Entonces puedes proceder de esta manera.

Dx = N(:,1) - M(:,1)';
Dy = N(:,2) - M(:,2)';
D = sqrt (Dx.^2 + Dy.^2);

Puedes hacer lo mismo usando una matriz 3D, pero supongo que esto es más claro. D es una matriz de distancias NxM, cada vector en N contra cada vector en M.

Espero que esto ayude

JuanPi
fuente