9

matlabの2つの行列間のユークリッド距離を計算する必要があります。現在、bsxfunを使用して、以下のように距離を計算しています（コードのスニペットを添付しています）：

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

fea_testのサイズは4754x1024、fea_trainは6800x1024です。彼のforループを使用すると、forの実行に約12分かかりますが、これは高すぎると思います。両方の行列間のユークリッド距離をより速く計算する方法はありますか？

不要なforループを削除することで、実行時間を短縮できると言われました。また、pdist2が計算時間を短縮するのに役立つことも知っていますが、バージョン7のmatlabを使用しているため、pdist2関数がありません。アップグレードはオプションではありません。

どんな助けでも。

よろしく、

バヴィア

4

3 に答える 3

12

これは、ユークリッド距離を計算するためのベクトル化された実装です。これは、現在の距離よりもはるかに高速です（私のマシンのPDIST2よりも大幅に高速です）。

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

これは、次の事実に基づいています。||u-v||^2 = ||u||^2 + ||v||^2 - 2*u.v

以下に、2つの方法の大まかな比較を検討してください。

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

R2011bを実行している私のWinXPラップトップでは、時間の10倍の改善を見ることができます。

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

PDIST2とまったく同じ結果が得られるわけではないことに注意してください。結果を比較すると、わずかな違いがわかります（通常epsは浮動小数点の相対精度に近い）。

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

ちなみに、私はこの距離計算のために約10の異なる実装（いくつかは互いに小さなバリエーションです）を収集し、それらを比較しています。他のベクトル化されたソリューションと比較して、単純なループがどれほど高速であるか（JITのおかげで）驚くでしょう...

于 2011-10-14T22:41:08.520 に答える
2

fea_test次のように、6800回とfea_train4754回の行を繰り返すことで、計算を完全にベクトル化できます。

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));

ただし、これにより、サイズ6800x4754x1024（* doubleの場合は8バイト）の中間アレイが作成され、最大250GBのRAMが使用されます。したがって、完全なベクトル化は機能しません。

ただし、事前に割り当て、必要になる前に平方根を計算しないことで、距離の計算時間を短縮できます。

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);
于 2011-10-08T13:02:13.877 に答える
0

このベクトル化されたバージョンを試してください、それはかなり効率的であるはずです。編集：私の答えが@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
于 2012-06-29T16:08:22.293 に答える