Calcolare in modo efficiente la distanza euclidea quadrata a coppie in Matlab

Dati due insiemi di punti tridimensionali. Come posso calcolare in modo più efficiente la matrice di distanza euclidea a due a due nel Matlab?

Notazione: il set uno è dato da una (numA,d) -matrice A e l’impostazione due è data da una (numB,d) -matrice B La matrice della distanza risultante deve essere del formato (numA,numB) .

Punti di esempio:

 d = 4; % dimension numA = 100; % number of set 1 points numB = 200; % number of set 2 points A = rand(numA,d); % set 1 given as matrix A B = rand(numB,d); % set 2 given as matrix B 

La risposta solitamente fornita qui è basata su bsxfun (vedere ad es. [1] ). Il mio approccio proposto si basa sulla moltiplicazione della matrice e risulta essere molto più veloce di qualsiasi algoritmo comparabile che ho trovato:

 helpA = zeros(numA,3*d); helpB = zeros(numB,3*d); for idx = 1:d helpA(:,3*idx-2:3*idx) = [ones(numA,1), -2*A(:,idx), A(:,idx).^2 ]; helpB(:,3*idx-2:3*idx) = [B(:,idx).^2 , B(:,idx), ones(numB,1)]; end distMat = helpA * helpB'; 

Nota: per la costante d si può sostituire il for -loop con implementazioni codificate, es

 helpA(:,3*idx-2:3*idx) = [ones(numA,1), -2*A(:,1), A(:,1).^2, ... % d == 2 ones(numA,1), -2*A(:,2), A(:,2).^2 ]; % etc. 

Valutazione:

 %% create some points d = 2; % dimension numA = 20000; numB = 20000; A = rand(numA,d); B = rand(numB,d); %% pairwise distance matrix % proposed method: tic; helpA = zeros(numA,3*d); helpB = zeros(numB,3*d); for idx = 1:d helpA(:,3*idx-2:3*idx) = [ones(numA,1), -2*A(:,idx), A(:,idx).^2 ]; helpB(:,3*idx-2:3*idx) = [B(:,idx).^2 , B(:,idx), ones(numB,1)]; end distMat = helpA * helpB'; toc; % compare to pdist2: tic; pdist2(A,B).^2; toc; % compare to [1]: tic; bsxfun(@plus,dot(A,A,2),dot(B,B,2)')-2*(A*B'); toc; % Another method: added 07/2014 % compare to ndgrid method (cf. Dan's comment) tic; [idxA,idxB] = ndgrid(1:numA,1:numB); distMat = zeros(numA,numB); distMat(:) = sum((A(idxA,:) - B(idxB,:)).^2,2); toc; 

Risultato:

 Elapsed time is 1.796201 seconds. Elapsed time is 5.653246 seconds. Elapsed time is 3.551636 seconds. Elapsed time is 22.461185 seconds. 

Per una valutazione più dettagliata, la dimensione e il numero di punti dati seguono la discussione seguente (@commenti). Risulta che diversi algos dovrebbero essere preferiti in diverse impostazioni. In situazioni non critiche basta usare la versione pdist2 .

Ulteriore sviluppo: si può pensare di sostituire l’euclideo quadrato con qualsiasi altra metrica basata sullo stesso principio:

 help = zeros(numA,numB,d); for idx = 1:d help(:,:,idx) = [ones(numA,1), A(:,idx) ] * ... [B(:,idx)' ; -ones(1,numB)]; end distMat = sum(ANYFUNCTION(help),3); 

Tuttavia, questo richiede molto tempo. Potrebbe essere utile sostituire per il più piccolo d l’ help matrice tridimensionale da matrici bidimensionali. Soprattutto per d = 1 fornisce un metodo per calcolare la differenza di coppia da una semplice moltiplicazione di matrice:

 pairDiffs = [ones(numA,1), A ] * [B'; -ones(1,numB)]; 

Hai altre idee?

Per la distanza Euclidea quadrata si può anche usare la seguente formula

 ||ab||^2 = ||a||^2 + ||b||^2 - 2 

Dove è il prodotto punto tra b

 nA = sum( A.^2, 2 ); %// norm of A's elements nB = sum( B.^2, 2 ); %// norm of B's elements distMat = bsxfun( @plus, nA, nB' ) - 2 * A * B' ; 

Recentemente, mi è stato detto che a partire da R2016b questo metodo per calcolare la distanza Euclidea quadrata è più veloce del metodo accettato.