列出来自编辑距离矩阵的非对角线值

Question

使用以下数据，我如何创建一个 DataFrame，其中列 'id' 作为索引，第二列包含来自 Levenshtein 距离矩阵的非对角线值列表，用于对应的字符串列表每个 id?

d = {'id':[1,1,1,2,2],'string':['roundys','roundys','ppg','brewers','cubs']}
df = pd.DataFrame(data=d)

目标是生成一个类似于

的DataFrame

df_diag = pd.DataFrame({'id':[1,2],'diag_val':['0.0,7.0,7.0','6.0']})

我构建了一些粗略的片段，它们可以处理单个列表，但无法通过 'id' 遍历多个列表。我使用 pandas 作为 'pd'，numpy 作为 'np'，与 Levenshtein 的距离作为 'dist'

步骤 1 创建测试列表

aTest = ['roundys','roundys','ppg']

步骤 2 创建 Returns 从 aTest 编辑距离矩阵的函数

def editDistance(list_o_strings):
    matrix = np.zeros(shape = (len(list_o_strings),len(list_o_strings)))

    for i in range(len(list_o_strings)):
        for j in range(i, len(list_o_strings)):
            matrix[i][j] = dist(list_o_strings[i],list_o_strings[j])
    for i in range(0, len(list_o_strings)):
        for j in range(0,len(list_o_strings)):
            if i == j:
                matrix[i][j] = 0
            elif i > j:
                matrix[i][j] = matrix[j][i]
    return matrix

步骤 3 创建 Returns 非对角线编辑距离项

的函数

def selectElements(matrix):
    ws = []
    for i in range(0, matrix.shape[0]):
        for j in range(0, matrix.shape[1]):
            if i <> j and i>j:
                ws.append(matrix[i,j])
    return ws

第 4 步测试示例列表

testDistance = editDistance(aTest)
testOffDiag = selectElements(testDistance)

我的下一步是在数据集中的唯一 id 值上迭代函数。我创建了一个新的 id 数据框，该数据框与

的字符串列表配对

df1 = df.groupby('id').agg(lambda x: ','.join(x))

我尝试让函数循环遍历 id 项的尝试惨遭失败，有什么建议吗？

Answer 1

您可以通过 pip 安装获得 Levenshtein 距离

pip install python-Levenshtein

那么你可以这样做

from Levenshtein import distance
from itertools import combinations

def lm(a):
  return [distance(*b) for b in combinations(a, 2)]

df.groupby('id').string.apply(lm).reset_index(name='diag_val')

   id   diag_val
0   1  [0, 7, 7]
1   2        [6]

或者

def lm(a):
  return ','.join([str(distance(*b)) for b in combinations(a, 2)])

df.groupby('id').string.apply(lm).reset_index(name='diag_val')

   id diag_val
0   1    0,7,7
1   2        6

Answer 2

Scipy 有一个函数 scipy.spatial.distance.pdist，它允许您计算 n 维 space 中元素之间的成对距离。该函数还允许自定义 metric 参数。

我们可以为该函数提供您的值，以及使用 python-Levenshtein 库计算的度量函数。

设置

from Levenshtein import distance
from scipy.spatial.distance import pdist

将 pdist 与自定义指标结合使用：

def lm(x):
    return pdist(x.values.reshape(-1, 1), lambda x,y: distance(x[0],y[0]))

res = pd.DataFrame(
    [(i, lm(g)) for i, g in df.groupby('id').string],
    columns=['id', 'diag_val']
)

   id         diag_val
0   1  [0.0, 7.0, 7.0]
1   2            [6.0]

列出来自编辑距离矩阵的非对角线值

List off-diagonal values from levenshtein distance matrix

python

levenshtein-distance

pandas