equivalente a pdist2 in MATLAB versione 7

Ho bisogno di calcolare la distanza euclidea tra 2 matrici in MATLAB. Attualmente sto usando bsxfun e calcolando la distanza come di seguito (sto allegando uno snippet del codice):

for i=1:4754 test_data=fea_test(i,:); d=sqrt(sum(bsxfun(@minus, test_data, fea_train).^2, 2)); end 

La dimensione di fea_test è 4754×1024 e fea_train è 6800×1024, l’uso del suo ciclo for sta causando l’esecuzione del for per circa 12 minuti, che penso sia troppo alto. C’è un modo per calcolare la distanza euclidea tra entrambe le matrici più velocemente?

Mi è stato detto che rimuovendo i loop non necessari posso ridurre i tempi di esecuzione. So anche che pdist2 può aiutare a ridurre il tempo per il calcolo, ma dal momento che sto usando la versione 7. di matlab non ho la funzione pdist2. L’aggiornamento non è un’opzione.

Qualsiasi aiuto.

Saluti,

Bhavya

È ansible rendere completamente vettoriale il calcolo ripetendo le righe di fea_test 6800 volte e di fea_train volte, in questo modo:

 rA = size(fea_test,1); rB = size(fea_train,1); [I,J]=ndgrid(1:rA,1:rB); d = zeros(rA,rB); d(:) = sqrt(sum(fea_test(J(:),:)-fea_train(I(:),:)).^2,2)); 

Tuttavia, ciò porterebbe a matrici intermedie di dimensioni 6800x4754x1024 (* 8 byte per i doppi), che occuperanno circa 250 GB di RAM. Pertanto, la completa vettorizzazione non funzionerà.

Tuttavia, è ansible ridurre il tempo del calcolo della distanza per preallocazione e non calcolare la radice quadrata prima che sia necessario:

 rA = size(fea_test,1); rB = size(fea_train,1); d = zeros(rA,rB); for i = 1:rA test_data=fea_test(i,:); d(i,:)=sum( (test_data(ones(nB,1),:) - fea_train).^2, 2))'; end d = sqrt(d); 

Ecco l’implementazione vettoriale per calcolare la distanza euclidea che è molto più veloce di quella che hai (anche significativamente più veloce di PDIST2 sulla mia macchina):

 D = sqrt( bsxfun(@plus,sum(A.^2,2),sum(B.^2,2)') - 2*(A*B') ); 

Si basa sul fatto che: ||uv||^2 = ||u||^2 + ||v||^2 - 2*uv


Considera di seguito un confronto approssimativo tra i due metodi:

 A = rand(4754,1024); B = rand(6800,1024); tic D = pdist2(A,B,'euclidean'); toc tic DD = sqrt( bsxfun(@plus,sum(A.^2,2),sum(B.^2,2)') - 2*(A*B') ); toc 

Sul mio laptop WinXP con R2011b, possiamo vedere un miglioramento di 10 volte nel tempo:

 Elapsed time is 70.939146 seconds. %# PDIST2 Elapsed time is 7.879438 seconds. %# vectorized solution 

È necessario essere consapevoli del fatto che non fornisce esattamente gli stessi risultati di PDIST2 con la massima precisione. Confrontando i risultati, si noteranno piccole differenze (in genere vicino a eps l’accuratezza relativa in virgola mobile):

 >> max( abs(D(:)-DD(:)) ) ans = 1.0658e-013 

In una nota a margine, ho raccolto circa 10 diverse implementazioni (alcune sono solo piccole variazioni l’una dell’altra) per questo calcolo a distanza e le ho confrontate. Sareste sorpresi di quanto possano essere veloci i loop semplici (grazie al JIT), rispetto ad altre soluzioni vettorializzate …

Prova questa versione vettoriale, dovrebbe essere abbastanza efficiente. Modifica: ho appena notato che la mia risposta è simile a quella di @ Amro.

 function K = calculateEuclideanDist(P,Q) % Vectorized method to compute pairwise Euclidean distance % Returns K(i,j) = sqrt((P(i,:) - Q(j,:))'*(P(i,:) - Q(j,:))) [nP, d] = size(P); [nQ, d] = size(Q); pmag = sum(P .* P, 2); qmag = sum(Q .* Q, 2); K = sqrt(ones(nP,1)*qmag' + pmag*ones(1,nQ) - 2*P*Q'); end