Liste des valeurs hors diagonale de la matrice de distance de levenshtein

Question

En utilisant les données suivantes, comment puis-je créer un DataFrame avec la colonne 'id' comme index et une deuxième colonne contenant une liste de valeurs hors diagonale d'une matrice de distance de Levenshtein pour la liste de chaînes de caractères correspondant à chaque id ?

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

L'objectif est de générer un DataFrame qui ressemble à quelque chose du genre

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

J'ai construit quelques éléments bruts qui fonctionnent avec une seule liste mais je n'ai pas été capable d'itérer par 'id' sur plusieurs listes. J'utilise pandas comme 'pd', numpy comme 'np' et distance de Levenshtein comme 'dist'.

Étape 1 : créer une liste de test

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

Étape 2 Créer une fonction qui renvoie la matrice de distance d'édition de 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

Étape 3 Créer une fonction qui renvoie les termes de distance d'édition hors diagonale

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 

Étape 4 Tester la liste d'exemples

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

L'étape suivante consiste à itérer les fonctions sur les valeurs d'identification uniques dans l'ensemble de données. J'ai créé un nouveau cadre de données d'identifiants appariés à une liste de chaînes de caractères avec la commande

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

Mes tentatives pour que les fonctions bouclent sur les termes d'identification ont échoué lamentablement, avez-vous des suggestions ?

Answer 1

Vous pouvez obtenir la distance de Levenshtein avec une pip installer

pip install python-Levenshtein

Vous pouvez alors faire quelque chose comme ceci

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]

Ou

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 a une fonction, scipy.spatial.distance.pdist qui permet de calculer les distances par paire entre des éléments dans un espace à n dimensions. La fonction permet également d'ajouter un metric paramètre.

Nous pouvons alimenter cette fonction avec vos valeurs, ainsi qu'avec une fonction métrique calculée à l'aide de la fonction python-Levenshtein bibliothèque.

Configuration

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

Utilisation de pdist avec une métrique personnalisée :

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]