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

Question

在 NumPy 中，命令

numpy.corrcoef(X.T)

在计算矩阵

X

中每对可能的列之间的相关性方面非常高效。我正在寻找一种类似有效的方法来计算二进制矩阵 B 的每个可能列之间的

Hamming

距离。是否有一种 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
import itertools
from scipy import stats, 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

Answer 1

我只是将

pdist

与自定义函数

my_hamming

一起使用，并用

numba

进行装饰。我非常准确地得到了相同的时间使用情况。使用低级语言可能没有太大潜力。我怀疑这是计算复杂性的问题，事实上：

相关系数以二次时间计算（对于较大尺寸，斜率为时间轴上的 2 个十年到尺寸轴上的 1 个十年），而距离计算为三次（斜率 3）。

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

所以总而言之，这些算法没有可比性。 在某种程度上，您也许可以通过并行处理来加速 - 但只能通过恒定因子（最大 #CPU）。