文字列間の類似性を測るための『標準化』編集距離の計算方法について

『標準化されたレーベンシュタイン距離(normalized Levenshtein distance)では、「アイス」と「ノート」は1とかけ離れており、「ミルクチョコレート」と「チョコレート」は0.33と近いという、実感に近い答えが出てくる。』

by stranger

編集距離のまとめはたくさんありますが、標準化について実装を記述しているものが見つからなかったのでまとめました。
個人的には、文字列間の類似性からクラスタリングを行ったりする際に、この標準化が非常に重要になると思うので、まとめておきます。

たとえば、

• 自社商品やサービスに関するTwitter上のトピックを、ツイートの文字列の類似性を使ってグルーピングしたい
• 大量にやってくるスパムメールの件名やファイル名をもとに、スパムキャンペーンをグルーピングしたい。

とかやる際に重要になるかも！？

本ページの構成は、だいたいこんな感じです。

1. 予備知識を軽くまとめた
2. 通常のレーベンシュタイン距離をPythonでやってみる
3. 「標準化」するとは？
4. 「標準化」したレーベンシュタイン距離の実装と結果

1. 予備知識を軽くまとめた

文字列と文字列の類似性を把握する手段として、編集距離の概念があります。ここでは細かく説明しませんが、導入として簡単にまとめます。

• 編集距離とは

  • 文字列の類似度を測る(1) レーベンシュタイン距離
  • 編集（挿入・削除・置換の3種類）が1回行われるごとに、距離が1つ増えるような距離の計算方法。文字列間の距離を測ります。
    
    

• レーベンシュタイン距離(Levenshtein distance)とは

  • 編集距離の中でも最小編集距離の考え方に基づいて計算される方法。
  • 編集距離とほぼ同義で利用されている気がする。
    
    

• 最小編集距離とは

  • 最低限の編集回数で済むような編集の組み合わせを基準にして計算。
    
    

編集操作のあれこれ

• 挿入（編集 1/3）
  • 例：「タコ」 -> 「タコス」
  • 「ス」という文字が挿入操作されており、距離は+1。
    
    
• 削除（編集 2/3）
  • 例：「バカンス」 -> 「バカ」
  • 「ンス」という文字が削除操作されており、距離は+2。
    
    
• 置換（編集 3/3）
  • 例：「ヘンタイ」 -> 「ヘイタイ」
  • 「ン」が「イ」に置換操作されており、距離は+1。
    
    

2. 通常のレーベンシュタイン距離をPythonでやってみる

最初に利用するパッケージpython-Levenshteinをpip installします。私の環境python2.7で、python-Levenshtein-0.12.0を利用します。

pip install python-Levenshtein

では実際に実行してみます。

例1

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import Levenshtein

string1 = 'きみのなは'
string2 = 'きみのはな'
print Levenshtein.distance(string1, string2)  # 2

• 「きみのなは」と「きみのはな」のレーベンシュタイン距離を測定すると、距離=2という結果になります。
• これは、「な」と「は」が入替わっているので、以下のどちらかの操作で「きみのなは」 <-> 「きみのはな」の変換が可能になります。いずれも2回の操作なので距離は2です。
  • 置換操作 × 2回
  • 挿入操作 × 1回 + 削除操作 × 1回

例2

次に、4つの文字列を登場させ、2ペアの距離を比較します。

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import Levenshtein

string1 = 'たのうえです'
string2 = 'いしおです'
print Levenshtein.distance(string1, string2)  # -> 6

string3 = '僕の名前はいしおです。よろしくおねがいします'
string4 = '僕の名前はいしおです。よろしくおねがいするのさ'

print Levenshtein.distance(string3, string4)  # -> 6

• 「たのうえです」<->「いしおです」の距離は6
• 「僕の名前はいしおです。よろしくおねがいします」と「僕の名前はいしおです。よろしくおねがいするのさ」の距離は6になります。

レーベンシュタイン距離で考えた場合、これらのペアの類似性は同じくらいと認識されます。

3. 「標準化」するとは？

でも待ってください。私たち人間の思考で考えた場合、「僕の名前はいしおです。よろしくおねがいします」と「僕の名前はいしおです。よろしくおねがいするのさ」の方が似てると感じます。

なぜこのような結果になるかというと、文字列の長さを考慮していないからです。
だって、感覚的な話になりますが、10,000文字の文章の中の3文字の転記ミスと、10文字の中の3文字の誤りって重要度というか深刻度は当然変わってきます。

標準化の方法

編集距離における標準化の方法は、文字列Aと文字列Bの距離を比較するとき、長い方の文字列の長さで編集距離を割る。
標準化された編集距離は、0から1までの間の距離を持ちます。

4. 「標準化」したレーベンシュタイン距離の実装と結果

例3

さきほどの例2の文字列について、標準化した結果を比較します。

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import Levenshtein

string1 = 'たのうえです'
string2 = 'いしおです'
print Levenshtein.distance(string1, string2)/(max(len(string1), len(string2)) * 1.00)  # -> 0.333333333333

string3 = '僕の名前はいしおです。よろしくおねがいします'
string4 = '僕の名前はいしおです。よろしくおねがいするのさ'

print Levenshtein.distance(string3, string4)/(max(len(string3), len(string4)) * 1.00)  # ->0.0869565217391

• string1 <-> string2 の距離　：0.333333333333
• string3 <-> string4 の距離　：0.0869565217391

この結果を見ると、後者のstring3 <-> string4間の距離の方が0.0869と、だいぶ短くなる結果になりました。

めでたしめでたし。

もし、ためになりましたらQiitaフォローをお願いします。

Twitterのフォローもお待ちしております。
@ishio