Python - Как создать матрицу парных расстояний Хэмминга

Начинающий с Python здесь. Поэтому у меня возникли проблемы при попытке вычислить результирующую двоичную попарно матрицу Хэммингтона между строками входной матрицы, используя только библиотеку numpy. Я должен избегать петель и использовать векторизацию. Если, например, у меня есть что-то вроде:

   [ 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, но все они в значительной степени дали мне нечто подобное.

Источник

2 ответа

Решение

Попробуйте этот подход, создайте новую ось вдоль axis = 1, а затем сделать трансляцию и считать истины или ненулевое значение с 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) Создайте трехмерный массив, который имеет форму (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) это 2d массив имеет форму (3, 6)

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

3) Это запускает трансляцию, так как их форма не совпадает, и 2-й массив arr сначала транслируется вдоль оси 0 3d-массива arr [:, None,:], а затем у нас есть массив формы (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 по третьей оси подсчитайте, сколько элементов не равны, т. е. истинно, что дает расстояние Хемминга.

Источник

По причинам, которые я не понимаю, это

(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's немного быстрее для очень маленького примера:

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

Обновить

Частично причина в том, что float быстрее других 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
Источник
Другие вопросы по тегам