Вычислить расстояние Хэмминга между двумя наборами данных

Мне нужно рассчитать расстояние Хэмминга между:

  1. Мой эталонный набор данных формы N0 (строки) x M0 (столбцы) - Ref.csv
  2. Мой тестовый набор данных формы N1 (строки) x M1 (столбцы) - Tes.csv

Результирующая матрица должна иметь форму N0 x N1, которая содержит расстояние Хэмминга между всеми ссылочными строками и всеми строками теста (как столбец в новом наборе данных).

Выполнение этого с помощью цикла может быть неэффективным.

Некоторые ресурсы, которые я использовал

from scipy.spatial.distance import hamming

В идеале я бы хотел рассчитать расстояние Хэмминга, как показано ниже, что в вычислительном отношении менее затратно. В приведенном ниже цикле вычисляется евклидово расстояние.

def compute_distances_no_loops(Train, X):
    dists = -2 * np.dot(X, Train.T) + np.sum(Train**2,    axis=1) + np.sum(X**2, axis=1)[:, np.newaxis]
    return dists

Вот наборы данных csv в Dropbox, которые вы можете использовать: HammingDistance


python numpy scipy dataframe hamming-distance
person siddhartha pachhai    schedule 29.08.2020    source источник

Ответы (1)


arrow_upward
0
arrow_downward

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

Хотя концепция расстояния Левенштейна была разработана для сравнения строк, оказалось, что ее можно применить и к последовательностям чисел.

Я использовал следующую функцию для вычисления расстояния Левенштейна:

def levDist(s1, s2):
    if len(s1) < len(s2): return levDist(s2, s1)
    if len(s2) == 0: return len(s1)
    prev_row = range(len(s2) + 1)
    for i, c1 in enumerate(s1):
        curr_row = [i + 1]
        for j, c2 in enumerate(s2):
            curr_row.append(min(prev_row[j + 1] + 1, curr_row[j] + 1,
                prev_row[j] + (c1 != c2)))
        prev_row = curr_row
    return prev_row[-1]

Чтобы проверить свой код, я сократил Tes.csv и Res.csv до первых 10 и 4 строк соответственно и прочитал их:

tes = np.loadtxt('Tes.csv', delimiter=',', encoding='utf-8')
ref = np.loadtxt('Ref.csv', delimiter=',', encoding='utf-8')

Фактические вычисления выглядят следующим образом:

result = np.zeros([tes.shape[0], ref.shape[0]], dtype=int)
iTes = 0
for tesRow in tes:
    iRef = 0
    for refRow in ref:
        result[iTes, iRef] = levDist(tesRow.tolist(), refRow.tolist())
        iRef += 1
    iTes += 1

Для ваших (сжатых) входных файлов я получил следующий результат:

[[ 0 39 38 39]
 [39  4  6  3]
 [39  3  5  0]
 [39  6  8  3]
 [39  3  7  4]
 [39  0  6  3]
 [39  1  5  2]
 [39  3  5  4]
 [39  5  6  4]
 [39  3  3  2]]
person Valdi_Bo    schedule 30.08.2020
comment
Спасибо за подробное объяснение, но я только что проверил предоставленные мной наборы данных, в обоих по 38 столбцов. - person siddhartha pachhai; 30.08.2020
comment
Даже если обе последовательности имеют одинаковый размер, вы все равно можете использовать мое решение. Или замените вызов моей функции любой другой функцией, вычисляющей расстояние Хэмминга. - person Valdi_Bo; 30.08.2020