有没有一种高效的方法来计算二进制矩阵中每一列之间的汉明距离？

Question

在NumPy中，命令numpy.corrcoef(X.T)在计算矩阵X中每对列之间的相关性时非常高效。我正在寻找一种类似高效的方法来计算二进制矩阵B中每对列之间的汉明距离。是否有NumPy方法可以适应这个需求？

我尝试使用SciPy的spatial.distance.pdist(X, metric='hamming')，但它比NumPy的成对相关函数慢100倍。

根据@frank-yellin的评论，我还尝试了spatial.distance.pdist(X, metric='cityblock')，但这只加快了计算速度1.7倍 - 这很好，但如果可能的话，我希望能够加快大约100倍的速度。

import random
import numpy as np
from scipy import spatial
import time

binary_matrix = np.random.randint(0,2,(1000,1500),dtype = 'int32')
start = time.time()
hamming_with_scipy = spatial.distance.pdist(binary_matrix.T, metric = 'hamming')
end = time.time()
print(f'Hamming takes {end-start} seconds with scipy')

start = time.time()
corr_with_numpy = np.corrcoef(binary_matrix.T)
end = time.time()
print(f'Correlation takes {end-start} seconds with numpy')

输出：

Hamming takes 5.301102876663208 seconds with scipy
Correlation takes 0.03205609321594238 seconds with numpy

- Sam

---

由于您的数据已经是0或1，您可以尝试使用'cityblock'而不是'hamming'。结果相同，但乘以元素数量。 - undefined

谢谢！使用“cityblock”而不是“hamming”将时间缩短了1.7倍，但仍然比NumPy对成对相关性的实现慢得多。 - undefined

转到C/C++。在Python中要求时间减少两个数量级是可疑的，即使使用了Numpy。 - undefined

有一点需要说明（并非答案；这并不改变corrcoeff的复杂性显然与pdist不同），即corrcoeff利用了机器的所有核心，而pdist则没有。设置环境变量MKL_NUM_THREADS=1，NUMEXPR_NUM_THREADS=1，OMP_NUM_THREADS=1，以进行有意义的比较。 - undefined

大多数加速距离矩阵超过pdist点的方法都取决于后续的处理过程。如果你打算以后查找距离但现在不需要完整的表格，或者想要查找最近的邻居，KDTree数据结构可能会有所帮助。 - undefined

你面临的问题是CPU缓存。NumPy函数利用BLAS实现的matmul（实际上是gemm）以一种对CPU缓存友好的方式执行“外积和收缩”。SciPy的实现是“向量化”的，但它对缓存是不敏感的，因此受到RAM速度的限制（通常会减慢100倍）。如果你真的_需要_更快的速度，你应该了解一下对缓存友好的算法，或者从一个好的实现开始并进行适应。你可以在这里找到一个实现：https://akkadia.org/drepper/cpumemory.pdf - undefined

Answer 1

我刚刚使用了自定义函数my_hamming，并用numba进行了装饰，然后使用pdist。我得到了相当准确的相同时间使用情况。使用低级语言可能没有太大的潜力。我怀疑这更多是一个计算复杂性的问题，事实上：

相关系数是以二次时间计算的（在较大尺寸上，时间轴上的斜率是尺寸轴上的1个数量级的2倍），而距离计算是以立方时间计算的（斜率为3）。

我认为这适用于大多数距离，因为它们需要迭代遍历列向量的所有元素。

所以总结起来，这些算法是不可比较的。 在某种程度上，你可能能够通过并行处理来加速计算 - 但只能通过一个常数因子（最大CPU数量）来实现。

- Dr. V

---

谢谢你尝试这个！我猜你并不是想表明汉明距离的成对计算在时间复杂度上基本上比相应的相关系数计算“更难”。两者都需要遍历每一列，并且从涉及的公式来看，计算相关性似乎需要更多的步骤。相反，我认为你所展示的问题在于用于计算汉明成对距离的算法（由scipy提供）。如果是这样，这正是我发帖的原因 - 我正在寻找一个更好的算法。 - undefined

嗯，每个组合需要二次时间来计算距离，然后乘以线性复杂度来迭代列以计算单个距离。虽然我对意外保持开放态度，但我担心这是无法减少的。对于相关系数，起初也需要立方操作，但可以表示为矩阵乘法（A*A.T），这样可以更高效地实现。问题（就像你所说的）是：在汉明距离计算中是否可能利用类似的技巧，特别是在矩阵只包含零和一的情况下。 - undefined

你能否包含你用于Numba实现my_hamming()的代码？ - undefined

哦，抱歉，我没有保存代码，而且最近几天一直在旅行。这并不是什么魔法，只是实现了距离函数，并使用njit修饰器进行了装饰。 - undefined