寻找成对欧氏距离的快速算法(距离矩阵)

Question

我知道matlab有一个内置的pdist函数,可以计算成对距离.但是,我的矩阵非常大,60000乘300和matlab内存不足.

这个问题是对Matlab欧几里德成对平方距离函数的跟进.

这种计算效率低下是否存在任何解决方法？我尝试手动编码成对距离计算,通常需要一整天才能运行(有时需要6到7个小时).

任何帮助是极大的赞赏!

Answer 1

好吧,我无法抗拒玩耍.我创建了一个名为Matlab的mex C文件pdistc,它实现了单精度和双精度的成对欧几里德距离.在我使用Matlab R2012b和R2015a的机器上,对于大输入(例如,60,000乘300),它比pdist(和底层pdistmex辅助函数)快20-25%.

正如已经指出的那样,这个问题从根本上受到记忆的限制,你要求的很多.我的mex C代码使用了超出输出所需内存的最小内存.在比较其内存使用情况时pdist,看起来两者实际上是相同的.换句话说,pdist没有使用大量的额外内存.您的内存问题可能出现在调用之前用完的内存中pdist(您可以使用它clear来删除任何大型数组吗？)或仅仅是因为您试图在小型硬件上解决一个大的计算问题.

因此,我的pdistc功能可能无法为您整体节省内存,但您可以使用我内置的其他功能.您可以计算整个成对距离向量的块.像这样的东西:

m = 6e3;
n = 3e2;
X = rand(m,n);
sz = m*(m-1)/2;

for i = 1:m:sz-m
    D = pdistc(X', i, i+m); % mex C function, X is transposed relative to pdist
    ...                     % Process chunk of pairwise distances
end

这个速度相当慢(10次左右)并且我的C代码的这部分没有很好地优化,但它将允许更少的内存使用 - 假设您不需要一次完整的数组.请注意,通过创建一个循环传递直接子集而不是所有子集的循环,您可以更有效地使用pdist(或pdistc)执行相同的操作X.

如果您有64位Intel Mac,则不需要编译,因为我已经包含了.mexmaci64二进制文件,但是您需要弄清楚如何为您的机器编译代码.我无法帮助你.您可能无法编译它,或者您可能需要通过自己编辑代码来解决兼容性问题.也有可能存在错误,代码将崩溃Matlab.另外,请注意,相对于pdist机器epsilon(eps)范围内两者之间的差异,输出可能略有不同.pdist可能会或可能不会做一些花哨的事情来避免大​​输入和其他数字问题的溢出,但要注意我的代码没有.

另外,我创建了一个简单的纯Matlab实现.它比mex代码慢得多,但仍然比天真的实现或代码中的代码更快pdist.

所有文件都可以在这里找到.ZIP存档包含所有文件.它是BSD许可的.随意优化(我在C代码中尝试了BLAS调用和OpenMP无济于事 - 也许一些指针魔法或GPU/OpenCL可以进一步加快速度).我希望它对你或其他人有所帮助.

Answer 2

在我的系统上,以下是最快的(甚至比pdistc@horchler 的C代码更快):

function [ mD ] = CalcDistMtx ( mX )    
  vSsqX = sum(mX .^ 2);
  mD = sqrt(bsxfun(@plus, vSsqX.', vSsqX) - (2 * (mX.' * mX)));       
end

我想你需要一个非常好的C代码才能击败它.

自MATLAB R2016b以来更新MATLAB支持隐式广播而不使用bsxfun().

因此代码可以写成:

function [ mD ] = CalcDistMtx ( mX )    
  vSsqX = sum(mX .^ 2, 1);
  mD = sqrt(vSsqX.'+ vSsqX - (2 * (mX.' * mX)));       
end

在我的计算距离矩阵项目中给出了推广.

PS
使用MATLAB pdist进行比较:squareform(pdist(mX.'))相当于CalcDistMtx(mX).
即输入应该被转置.

Answer 3

计算机并不是无限大，也不是无限快。人们认为他们拥有大量内存、快速 CPU，因此他们只会制造越来越大的问题，然后最终想知道为什么他们的问题运行缓慢。事实是，这并不是计算效率低下。这只是一个超载的CPU。

正如 Oli 在评论中指出的那样，即使假设您只计算距离矩阵的上半部分或下半部分，也需要计算类似 2e9 的值。（6e4^2/2 大约为 2e9。）这将需要大约 16 GB 的 RAM 来存储，假设在内存中只创建了该数组的一份副本。如果你的代码很马虎，你可能很容易将其增加一倍或三倍。一旦进入虚拟内存，事情就会变得慢得多。

想要一个大问题跑得快是不够的。为了真正帮助您，我们需要知道有多少 RAM 可用。这是虚拟内存问题吗？您是否在可以处理所有所需 RAM 的 CPU 上使用 64 位 MATLAB？