MATLAB版本7中的pdist2等效项

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可以帮助减少计算时间,但由于我使用的是matlab版本7.我没有pdist2函数.升级不是一种选择.

任何帮助.

问候,

巴维亚

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 次和 4754 次的行来完全矢量化计算fea_train，如下所示：

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