pdist2等价于MATLAB 7版

Question

我需要在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函数。不能升级

任何帮助。

问候,

Bhavya

Answer 1

这是计算欧几里得距离的矢量化实现，它比你拥有的要快得多(甚至比我机器上的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

---

考虑下面两种方法之间的粗略比较:

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

Answer 2

您可以通过重复fea_test 6800次，fea_train 4754次来完全矢量化计算，如下所示:

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

Answer 3

试试这个矢量化的版本，它应该是相当有效的。编辑:刚刚注意到我的答案和@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