Create distance matrix for all string pairs with pandas

user_5905425 0
Viewed 244

I have a list that I would like to turn into a distance matrix

from pylev3 import Levenshtein
from itertools import combinations

mylist = ['foo', 'bar', 'baz', 'foo', 'foo']

The following produces all possible pairs from the list, needed to compute the matrix

list(combinations(mylist,2))

[('foo', 'bar'),
 ('foo', 'baz'),
 ('foo', 'foo'),
 ('foo', 'foo'),
 ('bar', 'baz'),
 ('bar', 'foo'),
 ('bar', 'foo'),
 ('baz', 'foo'),
 ('baz', 'foo'),
 ('foo', 'foo')]

Then taking the distance for each pair can be done with the following:

def ld(a):
  return [Levenshtein.classic(*b) for b in combinations(a, 2)]


ld(mylist)
[3, 3, 0, 0, 1, 3, 3, 3, 3, 0]

However, I am stuck on creating a matrix-like data frame in pandas - is there an eloquent solution to this in pandas?

       foo    bar   baz  foo   foo
1 foo   0     3     3    0     0
2 bar   3     0     1    3     3
3 baz   3     1     0    3     3
4 foo   0     3     3    0     0
5 foo   0     3     3    0     0
pandas distance matrix python string
2 Answers

Let's try modify the function a bit so that we eliminate the calculation on duplicated entries:

from itertools import combinations, product

def ld(a):
    u = set(a)
    return {b:Levenshtein.classic(*b) for b in product(u,u)}

dist = ld(mylist)

(pd.Series(list(dist.values()), pd.MultiIndex.from_tuples(dist.keys()))
   .unstack()
   .reindex(mylist)
   .reindex(mylist,axis=1)
)

Output:

     foo  bar  baz  foo  foo
foo    0    3    3    0    0
bar    3    0    1    3    3
baz    3    1    0    3    3
foo    0    3    3    0    0
foo    0    3    3    0    0
user_42384080

To compute the Levenshtein distance, I used Levenshtein module (pip install python-Levenshtein required), used in pair with fuzzywuzzy.

import Levenshtein as lv

Then, as we use Numpy functions, mylist must be converted to a Numpy array:

lst = np.array(mylist)

And to compute the whole result, run:

result = pd.DataFrame(np.vectorize(lv.distance)(lst[:, np.newaxis], lst[np.newaxis, :]),
    index=lst, columns=lst)

Details:

  • np.vectorize(lv.distance) is a vectorized version of lv.distance function.
  • (lst[:, np.newaxis], lst[np.newaxis, :]) is a numpythonic idiom - a list of arguments "each with each" from lst array, for consecutive calls of the above function.
  • Due to Numpy vectorization, the whole computation runs quickly, what can be seen especially on big arrays.
  • pd.DataFrame(...) converts the above result (a Numpy array) to a DataFrame, with proper index and column names.
  • If you want, use your original function instead of lv.distance.

The result is:

     foo  bar  baz  foo  foo
foo    0    3    3    0    0
bar    3    0    1    3    3
baz    3    1    0    3    3
foo    0    3    3    0    0
foo    0    3    3    0    0
user_73884770
Related