Python的 - 如何生成成对海明距离矩阵(Python - How to generate th

2019-09-27 02:38发布

与Python初学者在这里。 所以,我在遇到麻烦尝试计算输入矩阵的只使用numpy的库行之间产生的二进制成对hammington距离矩阵。 我应该避免环路和使用矢量化。 例如如果我有这样的:

   [ 1,  0,  0,  1,  1,  0]
   [ 1,  0,  0,  0,  0,  0]
   [ 1,  1,  1,  1,  0,  0]

矩阵应该是这样的:

   [ 0,  2,  3]
   [ 2,  0,  3]
   [ 3,  3,  0]

即,如果原始矩阵是A和汉明距离矩阵是B. B [0,1] =汉明距离(A [0]和A [1])。 在这种情况下,答案是2,因为他们只有两个不同的元素。

因此,对于我的代码是这样的

def compute_HammingDistance(X):

     hammingDistanceMatrix = np.zeros(shape = (len(X), len(X)))
     hammingDistanceMatrix = np.count_nonzero ((X[:,:,None] != X[:,:,None].T))
     return hammingDistanceMatrix

然而这似乎只是返回一个标量值,而不是预期的矩阵。 我知道我可能做错事与阵列/矢量广播,但我无法弄清楚如何解决它。 我已经使用np.sum代替np.count_nonzero尝试,但他们都非常给了我类似的东西。

Answer 1:

试试这个办法,建立沿新轴axis = 1 ,然后做广播和计数trues或非零sum

(arr[:, None, :] != arr).sum(2)

# array([[0, 2, 3],
#        [2, 0, 3],
#        [3, 3, 0]])

def compute_HammingDistance(X):
    return (X[:, None, :] != X).sum(2)

说明

1)创建,其具有的形状的3D阵列(3,1,6)

arr[:, None, :]
#array([[[1, 0, 0, 1, 1, 0]],
#       [[1, 0, 0, 0, 0, 0]],
#       [[1, 1, 1, 1, 0, 0]]])

2)这是一个二维数组已形状(3,6)

arr   
#array([[1, 0, 0, 1, 1, 0],
#       [1, 0, 0, 0, 0, 0],
#       [1, 1, 1, 1, 0, 0]])

3)这触发广播,因为它们的形状不匹配,并且2D阵列ARR首先沿着3D阵列ARR的0轴广播[:,无,:],然后我们有形状(1数组,6)是广播的针对(3,6)。 这两个步骤广播一起使原始数组的笛卡尔比较。

arr[:, None, :] != arr 
#array([[[False, False, False, False, False, False],
#        [False, False, False,  True,  True, False],
#        [False,  True,  True, False,  True, False]],
#       [[False, False, False,  True,  True, False],
#        [False, False, False, False, False, False],
#        [False,  True,  True,  True, False, False]],
#       [[False,  True,  True, False,  True, False],
#        [False,  True,  True,  True, False, False],
#        [False, False, False, False, False, False]]], dtype=bool)

4) sum沿所述第三轴线计数有多少个元素是不相等的,即,trues其给出的汉明距离。



Answer 2:

至于原因,我不明白这一点

(2 * np.inner(a-0.5, 0.5-a) + a.shape[1] / 2)

似乎远快于@ Psidom是为更大的阵列:

a = np.random.randint(0,2,(100,1000))
timeit(lambda: (a[:, None, :] != a).sum(2), number=100)
# 2.297890231013298
timeit(lambda: (2 * np.inner(a-0.5, 0.5-a) + a.shape[1] / 2), number=100)
# 0.10616962902713567

Psidom的是非常小的例子更快一点:

a
# array([[1, 0, 0, 1, 1, 0],
#        [1, 0, 0, 0, 0, 0],
#        [1, 1, 1, 1, 0, 0]])

timeit(lambda: (a[:, None, :] != a).sum(2), number=100)
# 0.0004370050155557692
timeit(lambda: (2 * np.inner(a-0.5, 0.5-a) + a.shape[1] / 2), number=100)
# 0.00068191799800843

更新

部分原因似乎是彩车比其他dtypes快:

timeit(lambda: (0.5 * np.inner(2*a-1, 1-2*a) + a.shape[1] / 2), number=100)
# 0.7315902590053156
timeit(lambda: (0.5 * np.inner(2.0*a-1, 1-2.0*a) + a.shape[1] / 2), number=100)
# 0.12021801102673635


文章来源: Python - How to generate the Pairwise Hamming Distance Matrix