Several posts exist about efficiently calculating pairwise distances in MATLAB. These posts tend to concern quickly calculating euclidean distance between large numbers of points.
关于在MATLAB中有效计算成对距离存在几个帖子。这些帖子倾向于关注快速计算大量点之间的欧氏距离。
I need to create a function which quickly calculates the pairwise differences between smaller numbers of points (typically less than 1000 pairs). Within the grander scheme of the program i am writing, this function will be executed many thousands of times, so even small gains in efficiency are important. The function needs to be flexible in two ways:
我需要创建一个函数来快速计算较小数量的点(通常少于1000对)之间的成对差异。在我正在编写的程序的宏伟方案中,此功能将执行数千次,因此即使效率的微小提升也很重要。该功能需要以两种方式灵活:
- On any given call, the distance metric can be euclidean OR city-block.
- The dimensions of the data are weighted.
在任何给定的呼叫中,距离度量可以是欧几里德或城市街区。
数据的维度是加权的。
As far as i can tell, no solution to this particular problem has been posted. The statstics toolbox offers pdist and pdist2, which accept many different distance functions, but not weighting. I have seen extensions of these functions that allow for weighting, but these extensions do not allow users to select different distance functions.
据我所知,没有解决这个特定问题的解决方案。 statstics工具箱提供了pdist和pdist2,它们可以接受许多不同的距离函数,但不能加权。我已经看到这些功能的扩展允许加权,但这些扩展不允许用户选择不同的距离功能。
Ideally, i would like to avoid using functions from the statistics toolbox (i am not certain the user of the function will have access to those toolboxes).
理想情况下,我想避免使用统计工具箱中的函数(我不确定该函数的用户是否可以访问这些工具箱)。
I have written two functions to accomplish this task. The first uses tricky calls to repmat and permute, and the second simply uses for-loops.
我写了两个函数来完成这个任务。第一个使用棘手的调用来进行repmat和permute,第二个只使用for循环。
function [D] = pairdist1(A, B, wts, distancemetric)
% get some information about the data
numA = size(A,1);
numB = size(B,1);
if strcmp(distancemetric,'cityblock')
r=1;
elseif strcmp(distancemetric,'euclidean')
r=2;
else error('Function only accepts "cityblock" and "euclidean" distance')
end
% format weights for multiplication
wts = repmat(wts,[numA,1,numB]);
% get featural differences between A and B pairs
A = repmat(A,[1 1 numB]);
B = repmat(permute(B,[3,2,1]),[numA,1,1]);
differences = abs(A-B).^r;
% weigh difference values before combining them
differences = differences.*wts;
differences = differences.^(1/r);
% combine features to get distance
D = permute(sum(differences,2),[1,3,2]);
end
AND:
function [D] = pairdist2(A, B, wts, distancemetric)
% get some information about the data
numA = size(A,1);
numB = size(B,1);
if strcmp(distancemetric,'cityblock')
r=1;
elseif strcmp(distancemetric,'euclidean')
r=2;
else error('Function only accepts "cityblock" and "euclidean" distance')
end
% use for-loops to generate differences
D = zeros(numA,numB);
for i=1:numA
for j=1:numB
differences = abs(A(i,:) - B(j,:)).^(1/r);
differences = differences.*wts;
differences = differences.^(1/r);
D(i,j) = sum(differences,2);
end
end
end
Here are the performance tests:
以下是性能测试:
A = rand(10,3);
B = rand(80,3);
wts = [0.1 0.5 0.4];
distancemetric = 'cityblock';
tic
D1 = pairdist1(A,B,wts,distancemetric);
toc
tic
D2 = pairdist2(A,B,wts,distancemetric);
toc
Elapsed time is 0.000238 seconds.
Elapsed time is 0.005350 seconds.
Its clear that the repmat-and-permute version works much more quickly than the double-for-loop version, at least for smaller datasets. But i also know that calls to repmat often slow things down, however. So I am wondering if anyone in the SO community has any advice to offer to improve the efficiency of either function!
很明显,repmat-and-permute版本的工作速度比双循环版本快得多,至少对于较小的数据集而言。但我也知道,调用repmat通常会减慢速度。所以我想知道SO社区中是否有人提出任何建议来提高这两种功能的效率!
EDIT
@Luis Mendo offered a nice cleanup of the repmat-and-permute function using bsxfun. I compared his function with my original on datasets of varying size:
@Luis Mendo使用bsxfun对repmat-and-permute函数进行了很好的清理。我将他的功能与我原来的不同大小的数据集进行了比较:
As the data become larger, the bsxfun version becomes the clear winner!
随着数据变得越来越大,bsxfun版本成为明显的赢家!
EDIT #2
I have finished writing the function and it is available on github [link]. I ended up finding a pretty good vectorized method for computing euclidean distance [link], so i use that method in the euclidean case, and i took @Divakar's advice for city-block. It is still not as fast as pdist2, but its must faster than either of the approaches i laid out earlier in this post, and easily accepts weightings.
我已经完成了函数的编写,它可以在github [link]上找到。我最终找到了一个非常好的矢量化方法来计算欧氏距离[link],所以我在欧几里德案例中使用了这个方法,我把@Divakar的建议用于city-block。它仍然没有pdist2那么快,但它必须比我在本文前面列出的任何一种方法都快,并且很容易接受权重。
2 个解决方案
#1
6
You can replace repmat
by bsxfun
. Doing so avoids explicit repetition, therefore it's more memory-efficient, and probably faster:
你可以用bsxfun替换repmat。这样做可以避免显式重复,因此它的内存效率更高,而且可能更快:
function D = pairdist1(A, B, wts, distancemetric)
if strcmp(distancemetric,'cityblock')
r=1;
elseif strcmp(distancemetric,'euclidean')
r=2;
else
error('Function only accepts "cityblock" and "euclidean" distance')
end
differences = abs(bsxfun(@minus, A, permute(B, [3 2 1]))).^r;
differences = bsxfun(@times, differences, wts).^(1/r);
D = permute(sum(differences,2),[1,3,2]);
end
#2
5
For r = 1 ("cityblock" case)
, you can use bsxfun
to get elementwise subtractions and then use matrix-multiplication
, which must speed up things. The implementation would look something like this -
对于r = 1(“cityblock”情况),您可以使用bsxfun获取元素减法,然后使用矩阵乘法,这必须加快速度。实现看起来像这样 -
%// Calculate absolute elementiwse subtractions
absm = abs(bsxfun(@minus,permute(A,[1 3 2]),permute(B,[3 1 2])));
%// Perform matrix multiplications with the given weights and reshape
D = reshape(reshape(absm,[],size(A,2))*wts(:),size(A,1),[]);
#1
6
You can replace repmat
by bsxfun
. Doing so avoids explicit repetition, therefore it's more memory-efficient, and probably faster:
你可以用bsxfun替换repmat。这样做可以避免显式重复,因此它的内存效率更高,而且可能更快:
function D = pairdist1(A, B, wts, distancemetric)
if strcmp(distancemetric,'cityblock')
r=1;
elseif strcmp(distancemetric,'euclidean')
r=2;
else
error('Function only accepts "cityblock" and "euclidean" distance')
end
differences = abs(bsxfun(@minus, A, permute(B, [3 2 1]))).^r;
differences = bsxfun(@times, differences, wts).^(1/r);
D = permute(sum(differences,2),[1,3,2]);
end
#2
5
For r = 1 ("cityblock" case)
, you can use bsxfun
to get elementwise subtractions and then use matrix-multiplication
, which must speed up things. The implementation would look something like this -
对于r = 1(“cityblock”情况),您可以使用bsxfun获取元素减法,然后使用矩阵乘法,这必须加快速度。实现看起来像这样 -
%// Calculate absolute elementiwse subtractions
absm = abs(bsxfun(@minus,permute(A,[1 3 2]),permute(B,[3 1 2])));
%// Perform matrix multiplications with the given weights and reshape
D = reshape(reshape(absm,[],size(A,2))*wts(:),size(A,1),[]);