python を使った名寄せ

名寄せの手段

レーベンシュタイン距離を使います．
『レーベンシュタイン距離』は，別名『編集距離』とも言われ，
1文字の『挿入』・『削除』・『置換』によって、一方の文字列をもう一方の文字列に変形するのに必要な手順の最小回数のことです.

例えば，cat から cut なら，
cat → c t → cut で「a削除, u挿入」の 2 ．
と思いがちですが，置換を使えるのでレーベンシュタイン距離は1．

詳細はWikiを見てください．
今回のチュートリアルでは，いくつかの実験をしながら，最終的に名寄せをしていきます．

実験1.『レーベンシュタイン距離』を使ってみよう

test0

import Levenshtein

target = ['oniku_a', 'oniku_b', 'oniku_c', 'yasai_a', 'yasai_b', 'yasai_c']
cates = ['kome']

for val in target:
    nearL_flag = False
    for cate in cates:
        if Levenshtein.distance(val, cate) < 1:   # 基準とするレーベンシュタイン距離が1未満，つまり少しでも違っていたら，cates に放り込んでいく
            nearL_flag = True
    if not nearL_flag:
        cates.append(val)
cates

output

['kome', 'oniku_a', 'oniku_b', 'oniku_c', 'yasai_a', 'yasai_b', 'yasai_c']

基準とするレーベンシュタイン距離が1以上のものが全てcatesに入っていくプログラムになっています．
これをベースに改造していきます．まず，距離を徐々に上げていき，出力がどうなるか観察します．

実験1. 基準とするレーベンシュタイン距離をあげてみる （曖昧性を許容していく）

test1

import Levenshtein

target = ['oniku_a', 'oniku_b', 'oniku_c', 'yasai_a', 'yasai_b', 'yasai_c']

for i in range(10):
    cates = ['kome']
    for val in target:
        nearL_flag = False
        for cate in cates:
            if Levenshtein.distance(val, cate) < i:
                nearL_flag = True
        if not nearL_flag:
            cates.append(val)
    print(i, cates)

output

0 ['kome', 'oniku_a', 'oniku_b', 'oniku_c', 'yasai_a', 'yasai_b', 'yasai_c']
1 ['kome', 'oniku_a', 'oniku_b', 'oniku_c', 'yasai_a', 'yasai_b', 'yasai_c']
2 ['kome', 'oniku_a', 'yasai_a']
3 ['kome', 'oniku_a', 'yasai_a']
4 ['kome', 'oniku_a', 'yasai_a']
5 ['kome', 'oniku_a', 'yasai_a']
6 ['kome', 'oniku_a', 'yasai_b']
7 ['kome', 'yasai_a']
8 ['kome']
9 ['kome']

この出力結果より，レーベンシュタイン距離を上げていくと，曖昧性を許容していくことが分かります．
例えば, 'oniku_a' と 'oniku_b' を同じ分類とみなすかどうか．
基準となるレーベンシュタイン距離が小さいと，「別物とみなす」
基準となるレーベンシュタイン距離が大きいと，「まぁ，同じとみなそう」，となります．

また，上記出力結果より，catesの初期リストを['kome']ではなく，['kome', 'oniku', 'yasai']としておくといい感じになりそうです．

実験2. 初期値を['kome', 'oniku', 'yasai']に変えて名寄せしてみる

test2

import Levenshtein

target = ['oniku_a', 'oniku_b', 'oniku_c', 'yasai_a', 'yasai_b', 'yasai_c']

for i in range(10):
    cates = ['kome', 'oniku', 'yasai']
    for val in target:
        nearL_flag = False
        for cate in cates:
            if Levenshtein.distance(val, cate) < i:
                nearL_flag = True
        if not nearL_flag:
            cates.append(val)
    print(i, cates)

output

0 ['kome', 'oniku', 'yasai', 'oniku_a', 'oniku_b', 'oniku_c', 'yasai_a', 'yasai_b', 'yasai_c']
1 ['kome', 'oniku', 'yasai', 'oniku_a', 'oniku_b', 'oniku_c', 'yasai_a', 'yasai_b', 'yasai_c']
2 ['kome', 'oniku', 'yasai', 'oniku_a', 'yasai_a']
3 ['kome', 'oniku', 'yasai']
4 ['kome', 'oniku', 'yasai']
5 ['kome', 'oniku', 'yasai']
6 ['kome', 'oniku', 'yasai']
7 ['kome', 'oniku', 'yasai']
8 ['kome', 'oniku', 'yasai']
9 ['kome', 'oniku', 'yasai']

以上より，今回の target に対しては，
cates初期値: ['kome', 'oniku', 'yasai'] とすると，レーベンシュタイン距離 3 未満で名寄せできることが分かりました．

それでは，最後に名寄せのプログラムです．

名寄せプログラム

nayose

import Levenshtein

target = ['oniku_a', 'oniku_b', 'oniku_c', 'yasai_a', 'yasai_b', 'yasai_c']
cates = ['kome', 'oniku', 'yasai']

nayose = []

for val in target:
    minL = 100
    afterNayose = 'dummy'
    for cate in cates:
        tmp_distance = Levenshtein.distance(val, cate)
        if tmp_distance < minL:
            minL = tmp_distance
            afterNayose = cate
    nayose.append(afterNayose)

[(before, after, Levenshtein.distance(before, after)) for before, after in zip(target, nayose)]

output

[('oniku_a', 'oniku', 2),
 ('oniku_b', 'oniku', 2),
 ('oniku_c', 'oniku', 2),
 ('yasai_a', 'yasai', 2),
 ('yasai_b', 'yasai', 2),
 ('yasai_c', 'yasai', 2)]

アウトプットの見方は(before, after, beforeとafterのレーベンシュタイン距離) となります．
確かにレーベンシュタイン距離が3未満で名寄せできていることを確認できます．