Octave: calculer la distance entre deux matrices de vecteurs

12

Supposons que j'ai deux matrices Nx2, Mx2 représentant respectivement N, M 2d vecteurs. Existe-t-il un moyen simple et efficace de calculer les distances entre chaque paire de vecteurs (n, m)?

La manière simple mais inefficace est bien sûr:

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

La réponse la plus proche que j'ai trouvée est bsxfun, utilisée comme ceci:

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
la source
J'ai jeté un œil à cela et je ne pouvais pas faire mieux que de vectoriser le calcul. Je pense que ce calcul est un assez bon candidat pour écrire une fonction C / Fortran externe.
Aron Ahmadia
1
Je parie que vous pourriez faire une matrice 2xNxM que vous remplissez avec un produit extérieur, puis équerrez chacune des entrées et additionnez le long de l'axe zéro et de la racine carrée. En Python, cela ressemblerait à: distance_matrix = (n [:,:, nexaxis] * m [:, newaxis ,:]); distance_matrix = distance_matrix ** 2; distance_matrix = sqrt (distance_matrix.sum (axe = 1)); Si vous avez seulement besoin de connaître les n-vecteurs les plus proches, il existe de bien meilleures façons de le faire!
meawoppl
3
@meawoppl (Nouveau sur Octave) J'ai découvert comment utiliser le paquet d' algèbre linéaire dans Octave, qui fournit cartprod, alors maintenant je peux écrire: (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) ..qui tourne beaucoup plus vite!
Kelley van Evert
Que diriez-vous octave.sourceforge.net/statistics/function/pdist.html
Nemo

Réponses:

6

La vectorisation est simple dans ces situations en utilisant une stratégie comme celle-ci:

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

Voici un exemple qui vectorise la boucle for avec une accélération de 15x pour M = 1000 et 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
la source
David, ravi de vous voir sur scicomp! J'ai édité sans vergogne votre fragment de code et je l'ai développé, veuillez revenir si mes modifications vont dans le mauvais sens en clarifiant ce que vous vouliez.
Aron Ahmadia
2

Depuis Octave 3.4.3 et versions ultérieures, l'opérateur - effectue la diffusion automatique (utilise bsxfun en interne). Vous pouvez donc procéder de cette manière.

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

Vous pouvez faire de même en utilisant une matrice 3D, mais je suppose que c'est plus clair. D est une matrice NxM de distances, chaque vecteur dans N contre chaque vecteur dans M.

J'espère que cela t'aides

JuanPi
la source