Argmax без ограничения дубликатов numpy - нечеткое сопоставление строк

У меня есть два списка строк, один называется l1, другой l2. Мне интересно найти для каждой строки в l1 наиболее подходящую строку в l2 (но не наоборот, т.е. меня интересуют только строки в l1). Я знаю, что идеальных пар не бывает. Я использую показатель Джаро-Винклера для вычисления сходства каждой строки с помощью модуля медузы.

Для этого я создаю матрицу всех оценок Яро-Винклера, а затем нахожу максимальные значения для каждой точки в матрице. Однако проблема в том, что иногда строка из l2 может лучше всего соответствовать более чем одной строке из l1, и я хочу предотвратить это.

Есть ли способ оптимизировать метод argmax, чтобы максимальная позиция индекса могла появляться в результирующей матрице только один раз?

Для примера ниже приведены списки буксировки и последующий код:

l1 = ['skinnycorebrokenblack184567', 'promtex2365h6', 'lovelinen940770', 'promtex2365h1', 'lovetrs844705', 
      'lovetrs844704', 'bennttrs49655', 'stella55900', 'kaxsprassel55250', 'smurfbs185573', 'kaxsprassel55880', 
      'victoriacort182062', 'juliatreggings916531', 'juliatreggings916530', 'milo63624505', 'promtex2365s2', 
      'promtex2365s1', 'promtex2365s6', 'promtex2365s4', 'stantwill160810', 'topazchini51081', 'topazchini51087',
      'juliatreggings187109', 'hansentrs50924', '2454s1ladiesjeanscolure', 'promtex2365h2']
l2 = ['stannewtwill160810', 'stellatrs55900', 'jennyhigh352300', 'victoriacort180565', 
      'mistylowribsatins818820202031', 'lovelinen940771', 'kaxsprasseltrs55250', 'milo63626624', 'lovetrs844702',
      'sarabootcuts842887019398270', 'sarabootcuts84288701939', 'victoriacords81805848817', 
      'ladiesjeanscolouredxxl2454s340999', 'julliatregging1871168817', 'logandrawstringpants92686705656', 
      '72480', 'victoriacords85203408817', 'julliatregging9673907817', 'lilypoplin9418412031', 'stellatrs56023',
      'tysontrs50626', 'bolttrousers51370', 'bellamystripe184539', 'tenrhino63602214', 'kidsthermotrousers2365h1',
      'bennytrouser53648', 'bluerinse070201072', 'topazchino51077', 'slimclassicblack674220203128999', 
      'milo63603812', 'milo63603813', 'milo63603814', 'slimclassicblack6742202031', 'lilypoplin9418402031', 
      'julliatregging9673917817', 'smurfjr185606', 'sarabootcuts81884571939', 'julliatregging9165318817']

#create the matrix
mat = np.matrix([[jf.jaro_distance(str(st1), str(st2)) 
              if jf.jaro_distance(str(st1), str(st2)) > 0.85 else 0 
              for st2 in l2] for st1 in l1])

#get max values
mat_max = (mat.argmax(1))

#create match dictionary
match_dict = {}
for x in xrange(len(mat_max)):
    if int(mat_max[x]):
        match_dict[styles[x]] = s2[int(mat_max[x])]

Обратите внимание, что в приведенном выше примере 'topazchino51077' из l2 дважды сопоставляется со строками из l1. Это именно то, что я надеюсь предотвратить. Строка из l2 должна быть сопоставлена ​​с лучшим совпадением.


numpy python-2.7 string matrix fuzzy-comparison
person Woody Pride    schedule 03.08.2014    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Вы можете смоделировать свою проблему в терминах классической проблемы стабильного брака. В вашей проблеме предпочтения парного сопоставления задаются jaro_distance двух строк; и мы хотим сопоставить каждую строку в l1 с ближайшей строкой в ​​l2 если только эта строка уже не связана с другой строкой из l1 с большим сходством.

Ядро алгоритма представлено здесь. И это возможная реализация:

xs = np.array([[jf.jaro_distance(x, y) for y in l2] for x in l1])
order = np.argsort(xs, axis=1)

FREE = -1 # special value to indicate no match yet
match = FREE * np.ones(len(l1), dtype=np.int_)
jnext = len(l2) * np.ones(len(l1), dtype=np.int_)

# reverse match: if string in l2 is matched to a string in  l1
rev_match = FREE * np.ones(len(l2), dtype=np.int_)

while(np.any(match == FREE)): # while there is an un-matched string
    i = np.where(match == FREE)[0][0] # take the first un-matched index
    jnext[i] -= 1
    j = order[i, jnext[i]] # next l2 string that l1[i] will be matched against
    if rev_match[j] == FREE:  # l2[j] is free, pair i & j together
        rev_match[j], match[i] = i, j
        print('{:30} --> {}'.format(l1[i], l2[j]))
    else: # l2[j] is already paired
        l = rev_match[j] # current l1 string that l2[j] is paired with
        if xs[l, j] < xs[i, j]:  # l2[j] is more similar to l1[i] than l1[l]
            match[l] = FREE      # unpair l & j, and pair i & j
            rev_match[j], match[i] = i, j
            print('{:30} -/- {}'.format(l1[l], l2[j]))
            print('{:30} --> {}'.format(l1[i], l2[j]))

Чтобы увидеть окончательное совпадение:

for i, w in enumerate(l1):
    print('{:30} {}'.format(w, l2[match[i]]))

Как видите, в этом решении 'topazchino51077' только сочетается с 'topazchini51087', потому что эти два более похожи:

>>> jf.jaro_distance('topazchini51087', 'topazchino51077')
0.9111
>>> jf.jaro_distance('topazchini51081', 'topazchino51077')
0.8667
person behzad.nouri    schedule 03.08.2014
comment
Это круто. Мне нужно будет немного обработать то, что происходит, и добавить условие, согласно которому не должно быть совпадений, если оценка меньше 0,85, чтобы предотвратить ложные совпадения. - person Woody Pride; 03.08.2014
comment
На самом деле я могу просто добавить это в последний цикл через l1: if xs[l1.index(w), l2.index(l2[match[i]])] > 0.85: работает! - person Woody Pride; 03.08.2014