寻找成对欧几里得距离(距离矩阵)的快速算法 [英] 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 euclidean 的跟进成对平方距离函数.

是否有解决这种计算效率低下的方法.我尝试手动编码成对距离计算，通常需要一整天才能运行(有时 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×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 代码没有得到很好的优化，但它允许更少的内存使用 -ndash;假设您一次不需要整个数组.请注意，您可以使用 pdist(或 pdistc)更有效地执行相同的操作，方法是创建一个循环，在该循环中直接传入 X 的子集，而不是全部.

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 范围内(eps).pdist 可能会也可能不会做一些花哨的事情来避免大​​输入和其他数字问题的溢出，但请注意我的代码不会.

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屋！