Эквивалент pdist2 в MATLAB версии 7 - PullRequest
Новая
       69

Эквивалент pdist2 в MATLAB версии 7

9 голосов
/ 08 октября 2011

Мне нужно вычислить евклидово расстояние между 2 матрицами в Matlab.В настоящее время я использую 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 вызывает выполнениепримерно 12 минут, которые я считаю слишком высокими.Есть ли способ быстрее вычислить евклидово расстояние между обеими матрицами?

Мне сказали, что, удалив ненужные циклы, я могу сократить время выполнения.Я также знаю, что pdist2 может помочь сократить время вычислений, но так как я использую версию 7. Matlab, у меня нет функции pdist2.Обновление не вариант.

Любая помощь.

С уважением,

Бхавья

Ответы [ 3 ]

12 голосов
/ 15 октября 2011

Вот векторизованная реализация для вычисления евклидова расстояния, которая намного быстрее, чем у вас (даже значительно быстрее, чем 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

На моем ноутбуке WinXP с R2011b мы можем наблюдать улучшение в 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) по сравнению с другими векторизованными решениями ...

2 голосов
/ 08 октября 2011

Вы можете полностью векторизовать вычисление, повторяя строки 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 байт для двойных чисел), которые будут занимать ~ 250 ГБ ОЗУ. Таким образом, полная векторизация не будет работать.

Однако вы можете сократить время расчета расстояния путем предварительного распределения и не вычисляя квадратный корень до того, как это необходимо: 

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);
0 голосов
/ 29 июня 2012

Попробуйте эту векторизованную версию, она должна быть довольно эффективной. Редактировать: только что заметил, что мой ответ похож на @ Amro's. 

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
...