在MATLAB中有效计算加权距离

Question

几个 帖子 存在约高效计算MATLAB成对距离.这些帖子往往涉及快速计算大量点之间的欧氏距离.

我需要创建一个函数来快速计算较小数量的点(通常少于1000对)之间的成对差异.在我正在编写的程序的宏伟方案中,此功能将执行数千次,因此即使效率的微小提高也很重要.该功能需要以两种方式灵活:

1. 在任何给定的呼叫中,距离度量可以是欧几里德或城市街区.
2. 数据的维度是加权的.

据我所知,这个特定问题没有解决方案.statstics工具箱提供了pdist和pdist2,它们接受许多不同的距离函数,但不能加权.我已经看到这些功能的扩展允许加权,但这些扩展不允许用户选择不同的距离功能.

理想情况下,我想避免使用统计工具箱中的函数(我不确定该函数的用户是否可以访问这些工具箱).

我写了两个函数来完成这个任务.第一个使用棘手的调用来进行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

和:

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

以下是性能测试:

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.

很明显,repmat-and-permute版本的工作速度比双循环版本快得多,至少对于较小的数据集而言.但我也知道,调用repmat通常会减慢速度.所以我想知道SO社区中是否有人提出任何建议来提高这两种功能的效率!

编辑

@Luis Mendo使用bsxfun对repmat-and- permute函数进行了很好的清理.我将他的功能与我原来的不同大小的数据集进行了比较:

随着数据变得越来越大,bsxfun版本成为明显的赢家!

编辑#2

我已经完成了函数的编写,它可以在github [ link ]上找到.我最终找到了一个非常好的矢量化方法来计算欧氏距离[ link ],所以我在欧几里德案例中使用了这个方法,我把@Divakar的建议用于city-block.它仍然没有pdist2那么快,但它必须比我在本文前面列出的任何一种方法都快,并且很容易接受权重.

Answer 1

您可以替换repmat的bsxfun.这样做可以避免明确的重复,因此它的内存效率更高,而且可能更快:

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

Answer 2

因为r = 1 ("cityblock" case),您可以使用bsxfun元素减法然后使用matrix-multiplication,这必须加快速度.实现看起来像这样 -

%// 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),[]);