查找成对的欧式距离(距离矩阵)的快速算法 [英] Fast Algorithms for Finding Pairwise Euclidean Distance (Distance Matrix)

问题描述

我知道matlab有一个内置的pdist函数，可以计算成对的距离.但是，我的矩阵是如此之大，以至于其60000 x 300和matlab的内存不足.

I know matlab has a built in pdist function that will calculate pairwise distances. However, my matrix is so large that its 60000 by 300 and matlab runs out of memory.

此问题是对 Matlab欧几里得的跟进成对平方距离函数.

是否存在针对这种计算效率低下的解决方法.我尝试手动编码成对距离计算，通常需要一整天的时间(有时需要6到7个小时).

Is there any workaround for this computational inefficiency. I tried manually coding the pairwise distance calculations and it usually takes a full day to run (sometimes 6 to 7 hours).

任何帮助将不胜感激！

推荐答案

好吧，我无法抗拒.我创建了一个Matlab mex C文件称为 pdistc ，它实现了单双精度的成对欧几里德距离精确.在使用Matlab R2012b和R2015a的计算机上，它比 pdist (以及底层的pdistmex辅助函数)用于大输入(例如60,000 x 300).

Well, I couldn't resist playing around. I created a Matlab mex C file called pdistc that implements pairwise Euclidean distance for single and double precision. On my machine using Matlab R2012b and R2015a it's 20–25% faster than pdist(and the underlying pdistmex helper function) for large inputs (e.g., 60,000-by-300).

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

As has been pointed out, this problem is fundamentally bounded by memory and you're asking for a lot of it. My mex C code uses minimal memory beyond that needed for the output. In comparing its memory usage to that of pdist, it looks like the two are virtually the same. In other words, pdist is not using lots of extra memory. Your memory problem is likely in the memory used up before calling pdist (can you use clear to remove any large arrays?) or simply because you're trying to solve a big computational problem on tiny hardware.

因此，我的pdistc函数可能无法整体节省您的内存，但是您可能可以使用我内置的另一个功能.您可以计算整体成对距离向量的大块.像这样:

So, my pdistc function likely won't be able to save you memory overall, but you may be able to use another feature I built in. You can calculate chunks of your overall pairwise distance vector. Something like this:

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代码的这一部分没有得到很好的优化，但这将减少内存使用量–假设您一次不需要整个数组.请注意，通过创建一个循环，您直接传递X的子集而不是全部传递X的子集，可以使pdist(或pdistc)更有效地完成相同的事情.

This is considerably slower (10 times or so) and this part of my C code is not optimized well, but it will allow much less memory use – assuming that you don't need the entire array at one time. Note that you could do the same thing much more efficiently with pdist (or pdistc) by creating a loop where you passed in subsets of X directly, rather than all of it.

如果您具有64位Intel Mac，则不需要编译，因为我包含了.mexmaci64二进制文件，但是否则，您将需要弄清楚如何为您的计算机编译代码.我不能帮你.您可能无法对其进行编译，或者可能需要通过自己编辑代码来解决兼容性问题.也可能有错误，并且代码会使Matlab崩溃.另外，请注意，相对于pdist，您得到的输出可能会略有不同，两者在机器epsilon范围内会有所不同(

If you have a 64-bit Intel Mac, you won't need to compile as I've included the .mexmaci64 binary, but otherwise you'll need to figure out how to compile the code for your machine. I can't help you with that. It's possible that you may not be able to get it to compile or that there will be compatibility issues that you'll need to solve by editing the code yourself. It's also possible that there are bugs and the code will crash Matlab. Also, note that you may get slightly different outputs relative to pdist with differences between the two in the range of machine epsilon (eps). pdist may or may not do fancy things to avoid overflows for large inputs and other numeric issues, but be aware that my code does not.

此外，我还创建了一个简单的纯Matlab实现.它比mex代码慢得多，但比朴素的实现或pdist中的代码快.

Additionally, I created a simple pure Matlab implementation. It is massively slower than the mex code, but still faster than a naïve implementation or the code found in pdist.

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

All of the files can be found here. The ZIP archive includes all of the files. It's BSD licensed. Feel free to optimize (I tried BLAS calls and OpenMP in the C code to no avail – maybe some pointer magic or GPU/OpenCL could further speed it up). I hope that it can be helpful to you or someone else.

这篇关于查找成对的欧式距离(距离矩阵)的快速算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！