查找成对欧几里得距离(距离矩阵)的快速算法

2024-03-12

我知道 matlab 有一个内置的 pdist 函数可以计算成对距离。然而,我的矩阵太大了,以至于它的 60000 x 300 和 matlab 内存不足。

这个问题是后续问题Matlab 欧氏成对平方距离函数 https://stackoverflow.com/questions/17756265/matlab-euclidean-pairwise-square-distance-function/17756481?noredirect=1#comment25925503_17756481.

对于这种计算效率低下的情况,有什么解决方法吗?我尝试手动编码成对距离计算,通常需要一整天的时间才能运行(有时需要 6 到 7 小时)。

任何帮助是极大的赞赏!


嗯,我实在忍不住要玩一玩。我创建了一个Matlab.mex C 文件 http://www.mathworks.com/help/matlab/programming-interfaces-for-c-c-fortran-com.html called pdistc http://biorobots.cwru.edu/personnel/adh/stackoverflow/01/pdistc.c它实现了单精度和双精度的成对欧几里得距离。在我使用 Matlab R2012b 和 R2015a 的机器上,速度比pdist http://www.mathworks.com/help/stats/pdist.html(以及底层的pdistmex辅助函数)用于大型输入(例如 60,000×300)。

正如已经指出的,这个问题从根本上来说是受内存限制的,而且你需要很多内存。我的 mex C 代码使用的内存超出了输出所需的内存。将其内存使用情况与pdist,看起来两者几乎是一样的。换句话说,pdist没有使用大量额外内存。你的内存问题很可能是在调用前内存用完pdist(你能用clear删除任何大型数组?)或者只是因为您试图在小型硬件上解决大型计算问题。

So, my 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 (or pdistc)通过创建一个循环,在其中传递以下子集X直接,而不是全部。

如果您有 64 位 Intel Mac,则无需编译,因为我已经包含了.mexmaci64二进制文件,但否则您需要弄清楚如何为您的机器编译代码。我无法帮助你。您可能无法编译它,或者存在兼容性问题,您需要自己编辑代码来解决。也有可能存在错误并且代码会导致 Matlab 崩溃。另请注意,您可能会得到与以下内容略有不同的输出:pdist两者之间的差异在于机器 epsilon 的范围(eps http://www.mathworks.com/help/matlab/ref/eps.html). pdist可能会或可能不会做一些花哨的事情来避免大​​输入和其他数字问题的溢出,但请注意我的代码没有。

另外,我创建了一个简单的纯Matlab实现 http://biorobots.cwru.edu/personnel/adh/stackoverflow/01/pdistq.m。它比 mex 代码慢得多,但仍然比简单的实现或中找到的代码快pdist.

所有文件可以在这里找到 http://biorobots.cwru.edu/personnel/adh/stackoverflow/01/。 ZIP 存档包含所有文件。它是 BSD 许可的。请随意优化(我在 C 代码中尝试了 BLAS 调用和 OpenMP,但没有成功——也许一些指针魔法或 GPU/OpenCL 可以进一步加快速度)。我希望它对您或其他人有帮助。

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

查找成对欧几里得距离(距离矩阵)的快速算法 的相关文章

  • 增加 .fig 文件中的散点标记大小

    我有一个图形文件 scatter fig 该图有许多使用 scatter 的散点绘图仪 现在我只有这个无花果文件 我需要增加所有散点的标记大小 手动尝试过 但非常困难 有没有办法我可以做类似的事情 H 图形句柄 s 点 h 设置 s 标记大
  • 将输出从符号数学 (sym) 转换为浮点型

    我的问题类似于这个问题 https stackoverflow com questions 11114101 how to convert mupad symbol i sqrt 1 to i in matlab 11114959 1111
  • 在 R 中不循环地对连续的列表元素对应用函数

    我试图找到一种有效的 即避免使用循环 方法来应用一个函数 该函数迭代地将列表的当前和前一个 或下一个 元素作为参数 并返回结果列表 其长度必然是短 1 个元素 作为一个具体的例子 我有一个在某些图中定义路径的顶点列表 vlist lt c
  • 如何使用Matlab提高PSD的分辨率

    我有音频信号 我用 Matlab 读取该信号 并使用 pwelch 获取其 PSD 这是我正在使用的代码 x Fs audioread audioFile wav x x 1 mono xPSD f pwelch x hamming 512
  • 如何在 R 或 MATLAB 中为散点图创建阴影误差条“框”

    我想在 R 或 MATLAB 中创建一个简单的散点图 涉及两个变量 x 和 y 它们有与之相关的错误 epsilon x 和 epsilon y 然而 我不是添加误差线 而是希望在每个 x y 对周围创建一个 阴影框 其中框的高度范围从 y
  • matlab矩阵中求子矩阵的通用方法

    我正在寻找一种 好 方法来在更大的矩阵 任意维数 中找到矩阵 模式 Example total rand 3 4 5 sub total 2 3 1 3 3 4 现在我希望这样的事情发生 loc matrixFind total sub 在
  • 如何避免循环

    大家好 我是 R 新手 我有两个面板数据文件 其中包含 id date 和 ret 列 文件 A 的数据比文件 B 多得多 但我主要处理文件 B 数据 id 和 date 的组合是唯一标识符 有没有一种优雅的方式来查找 B 中的每个 id
  • 傅里叶变换定理 matlab

    我目前正在尝试理解二维傅里叶位移定理 根据我到目前为止所了解到的情况 图像空间中的平移会导致相位差异 但不会导致频率空间中的幅度差异 我试图用一个小例子来演示这一点 但它只适用于行的移位 而不适用于列的移位 这是一个小演示 我只在这里显示幅
  • 通过傅里叶空间填充进行插值

    我最近尝试在 matlab 上实现一个在傅立叶域中使用零填充的插值方法的简单示例 但我无法正常工作 我总是有一个小的频移 在傅里叶空间中几乎不可见 但它在时空上产生了巨大的误差 由于傅里叶空间中的零填充似乎是一种常见 且快速 的插值方法 因
  • 为什么matlab的mldivide比dgels好这么多?

    Solve Ax b 真正的双 A是超定的 Mx2 其中 M gt gt 2 b是MX1 我运行了大量的数据mldivide 并且结果非常好 我用 MKL 写了一个 mex 例程LAPACKE dgels但它远没有那么好 结果有大量噪音 并
  • 在 Matlab 中显示有理数

    我有两个整数 m n 它们一起形成 m n 形式的有理数 现在我只想以这种理性的形式在 Matlab 中显示它们 我可以通过这样做来做到这一点 char sym m n 所以 如果 例如m 1 n 2 Matlab将显示1 2 然而 如果m
  • 为什么 MATLAB 本机函数 cov(协方差矩阵计算)使用与我预期不同的除数?

    给定一个 M 维和 N 个样本的数据矩阵数据 例如 data randn N M 我可以计算协方差矩阵 data mu data ones N 1 mean data cov matrix data mu data mu N 如果我使用原生
  • 为什么 MATLAB 在打印大量 (.png) 图形时速度会变慢?

    我正在将大量数字打印为 png 文件 每个图都是数据矩阵中的一列图 我获取 png 文件并将它们串在一起形成动画 我的问题是 前几百张图像打印得很快 但创建每个新图形的时间却迅速增加 从前几百个 png 文件的约 0 2 秒到第 800 个
  • 非模态 questdlg.m 提示

    我的代码绘制了一个图 然后提示用户是否想使用不同的参数绘制另一个图 问题是 当 questdlg m 打开时 用户无法查看绘图的详细信息 这是代码 while strcmp Cont Yes 1 Some code modifying da
  • 线性代数如何在算法中使用?

    我的几个同行都提到 学习算法时 线性代数 非常重要 我研究了各种算法并学习了一些线性代数课程 但我没有看到其中的联系 那么线性代数如何应用在算法中呢 例如 图的连接矩阵可以带来哪些有趣的事情 三个具体例子 线性代数是现代 3D 图形的基础
  • 从 imread 返回的 ndims

    我正在从文件夹中选取图像 尺寸为128 128 为此 我使用以下代码行 FileName PathName uigetfile jpg Select the Cover Image file fullfile PathName FileNa
  • 垂直子图的单一颜色条

    我想让下面的 MATLAB 图有一个沿着两个子图延伸的颜色条 像这样的事情 使用图形编辑器手动完成 Note 这与提出的问题不同here https stackoverflow com questions 39950229 matlab t
  • MATLAB 可执行文件太慢

    我使用以下命令将 MATLAB 程序转换为基于控制台的应用程序deploytool在 MATLAB 中 MATLAB m文件执行大约需要 2 秒 但在我将其转换为可执行文件并调用 exe 执行需要45秒 太长了 我想将 MATLAB 程序与
  • 从筛查乳腺 X 光检查数字数据库 (DDSM) 获取数据

    我正在尝试以可读格式获取 DDSM 数据集 有谁有 DDSM heathusf 程序的工作版本 可以在 Linux 或 Windows 上正常运行吗 我知道 DDSM 的 jpeg 程序有一个适用于 linux 的工作版本 位于http w
  • 数学 - 映射数字

    如何将 a 和 b 之间的数字线性映射到 c 和 d 之间 也就是说 我希望 2 到 6 之间的数字映射到 10 到 20 之间的数字 但我需要广义的情况 我的脑子炸了 如果您的数字 X 位于 A 和 B 之间 并且您希望 Y 位于 C 和

随机推荐