編集距離を用いた固有名詞の名寄せ

編集距離（レーベンシュタイン距離）を用いて、名寄せ作業をおこなった。

レーベンシュタイン距離については過去記事参照。 knknkn.hatenablog.com

今回の目的は前述のように、データソースAとBで、同じ固有名詞を示していても表記ゆれがあったため名寄せをおこなうこと。 企業名表記ゆれが性質として似ているので例として、「固有名詞」を企業名とする。

前処理

基本的には標準化レーベンシュタイン距離で処理をするが、カタカナとひらがな、半角と全角は別文字として認識されたり、他にも諸々問題があるので先に前処理をおこなう。

表記ゆれ概要

リストをざっと見ると、ざっくり以下の4種類の揺れがあった。

• 1.「株式会社」の有無による表記ゆれ

  • サントリー株式会社
  • サントリー

• 2.中黒(・)の有無表記ゆれ

  • コカ・コーラ
  • コカコーラ

• 3.英語表記かカタカナ表記か

  • Apple
  • アップル

• 4.全角表記か半角表記か、大文字か小文字か

  • Apple
  • apple
  • ＡＰＰＬＥ

• 5.詳細企業名か、大本企業名かによる部分一致

  • キリン
  • キリンビバレッジ
  • リクルート
  • リクルートライフスタイル

いらない文字の除去

1,2,5は「ある文字列がいらない」共通している。
5はいらない文字列に様々なバリエーションがあって一括処理は難しいが、1,2は共通している。
そのため、「・(中黒)」「株式会社」を除去する。

英語カタカナ表記の統一

英単語に対するカタカナ表記変換のAPIか辞書ないかな、と思いましたが見つからず。。。
会社名のような固有名詞の場合、Mecabuの辞書をWikipediaとかにしているとふりがながある場合もありそう。
英単語以外のものにも適応すると変なことになりそうなので、英単語のみ企業名を抽出→ふりがな変換→カタカナ変換　をおこなうとある程度はカバーできるかも。

半角小文字表記への統一

表記を半角かつ全て小文字に統一

標準化レーベンシュタイン距離

前処理した単語をそれぞれ、データソースAからのものをhoge、Bからのものをfugaというリストに入れて各リスト内単語のレーベンシュタイン距離を全て計算する。
このとき、距離が閾値(0.6)以下のものを紐付ける。

距離の閾値

今回とりあえず0.6にした。 理由として、0.5だと文字数が少ない場合いらない紐づけが起きそうだったから。例えば、

• 東芝
• 東洋

は2文字で1編集が起きているため、距離は0.5になる。

レーベンシュタイン距離求める部分のみ実装

import pandas as pd
import numpy as np
import Levenshtein

# データソースhogeとfugaから企業名リストを読み込む
hoge_company_list = pd.read_csv('hoge_company_list.tsv',sep='\t')
fuga_company_list = pd.read_csv('fuga_company_list.tsv',sep='\t')

# 前処理は一旦省略

# 類似度計算としてLevenshteinを正規化して使う(0.6以下かつ最大を採択)
hoge_company_names = []
fuga_company_names = []
distances = []

# hogeに対するfugaの全企業名に対する距離計算
for hoge_company in hoge_company_list:
    for fuga_company in fuga_company_list:
        distance = Levenshtein.distance(hoge_company, fuga_company)/(max(len(hoge_company), len(fuga_company)) * 1.00) #正規化
        hoge_company_names.append(hoge_company)
        fuga_company_names.append(fuga_company)
        distances.append(distance)
    
hoge_fuga_company_distance = pd.DataFrame({'hoge_company' : hoge_company_names, 'fuga_company' : fuga_company_names, 'distance' : distances})

# 距離0.6以下で1,2,3位のみ使用
hoge_fuga_company_distance = hoge_fuga_company_distance[hoge_fuga_company_distance['distance'] <= 0.6]
hoge_fuga_company_distance['rank'] = hoge_fuga_company_distance.groupby('hoge_company_distance')['distance'].rank(ascending=True,method='min')
hoge_fuga_company_distance = hoge_fuga_company_distance[hoge_fuga_company_distance['rank'] < 4].loc[:,['hoge_company','fuga_company']]

# 完全一致の名前は、完全一致のみにする
hoge_fuga_company_distance_match = hoge_fuga_company_distance[hoge_fuga_company_distance['hoge_company'] == hoge_fuga_company_distance['fuga_company']]
thoge_fuga_company_distance_not_match = hoge_fuga_company_distance[~hoge_fuga_company_distance['hoge_company'].isin(hoge_fuga_company_distance_match['hoge_company'])]

hoge_fuga_company_distance = pd.concat([hoge_fuga_company_distance_match, hoge_fuga_company_distance_not_match])

結果

ある程度は紐付けれたが、やはり一部は別のものとくっついている。

さらに、5.は一致していない部分の文字数が多い場合は距離が遠くなる。

• リクルート
• リクルートホールディングス

=> 13文字で編集距離は8なので、8/13

上記例から見るに、 また、編集距離の定義を今回の場合に意味がありそうなもののみにして自分なりの編集距離を実装して計算するとよい？ 例えば、文字数が多い方の末尾の隣合う文字を削除すると完全一致する場合は距離を近くする処理をするといいかもしれない。 例）「リクルート」と「リクルートホールディングス」だと「リクルート」が共通して、 末尾の隣合う文字 の「ホールディングス」を削除すると距離は0/5。

おまけ

LINEが類似文字検索ライブラリを作成し、API提供しているようです。
今回の目的は、固有名詞のみを比較なので固有名詞外も含んでいるこのAPIは適用範囲が広く、微妙に違いそうだったので未使用。

engineering.linecorp.com