Oitava: calcule a distância entre duas matrizes de vetores

12

Suponha que eu tenha duas matrizes Nx2, Mx2 representando N, M2 vetores, respectivamente. Existe uma maneira simples e boa de calcular distâncias entre cada par de vetores (n, m)?

A maneira mais fácil, porém ineficiente, é:

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

A resposta mais próxima que encontrei é a seguinte bsxfun:

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
fonte
Dei uma olhada nisso e não pude fazer muito melhor do que vetorizar a computação. Eu acho que esse cálculo é um bom candidato para escrever uma função C / Fortran externa.
Aron Ahmadia
1
Aposto que você pode criar uma matriz 2xNxM que preenche com um produto externo, depois quadrar cada uma das entradas e somar ao longo do eixo zerótico e da raiz quadrada. Em Python, isso se pareceria com: distance_matrix = (n [:,:, nexaxis] * m [:, newaxis ,:]); Matriz da distância = Matriz da distância ** 2; distance_matrix = sqrt (distance_matrix.sum (eixo = 1)); Se você só precisa conhecer os n vetores mais próximos, existem maneiras muito melhores de fazer isso!
27612 meawoppl
3
@meawoppl (Novo no Octave) Descobri como usar o pacote de álgebra linear no Octave, que fornece cartprod, então agora eu posso escrever: (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) ..o que corre muito mais rápido!
Kelley van Evert
Que tal octave.sourceforge.net/statistics/function/pdist.html
Nemo

Respostas:

6

A vetorização é direta nessas situações, usando uma estratégia como esta:

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

Aqui está um exemplo que vetoriza o loop for com uma aceleração de 15x para M = 1000 e 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
fonte
David, prazer em vê-lo no scicomp! Editei descaradamente o seu fragmento de código e o expandi um pouco, por favor, reverta se minhas edições foram na direção errada para esclarecer o que você pretendia.
Aron Ahmadia 09/04
2

A partir da oitava 3.4.3 e posterior, o operador - faz a transmissão automática (usa bsxfun internamente). Então você pode proceder dessa maneira.

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

Você pode fazer o mesmo usando uma matriz 3d, mas acho que assim é mais claro. D é uma matriz NxM de distâncias, todo vetor em N contra todo vetor em M.

Espero que isto ajude

JuanPi
fonte