时间戳

首页 > 解决方案 > 计算两个数据集之间的汉明距离

python - 计算两个数据集之间的汉明距离

问题描述

我需要计算以下之间的汉明距离：

  1. 我的形状 N0(rows) x M0(cols) 的参考数据集 -Ref.csv
  2. 我的形状 N1(rows) x M1(cols) 的测试数据集 -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

以下是您可以使用的 Dropbox 上的 csv 数据集：HammingDistance

标签： pythonnumpydataframescipyhamming-distance

解决方案

让我们从一个通知开始：汉明距离是在相等长度的序列之间计算的。由于您的两个数组都有不同的列数，我们必须应用更通用的方法，即Levenshtein距离，同时考虑插入和删除。

虽然 Levenshtein 距离的概念是用来比较字符串的，但事实证明它也可以应用于 数字序列。

我使用以下函数来计算 Levenshtein 距离：

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]]

推荐阅读