読者です 読者をやめる 読者になる 読者になる

人工知能であそぶ

人工知能をつくってあそぶ.あと個人的な勉強のメモ.

2つの文字列の類似度を数値化 レーベンシュタイン距離とジャロ・ウィンクラー距離の解説

自然言語処理 人工知能

人工知能のブログと言っておきながら今まで人工知能っぽいことを書いてきませんでしたが,ようやくそれっぽいことを書こうと思う(汗
今回は2つの文字列の類似度を数値化する2つの方法について考える.
これらは自然言語処理の分野でよく用いられる方法である.
私も必要に応じて調べたのだが,ジャロ・ウィンクラー距離を日本語で詳しく解説してくれているところがなかったため,理解したことを日本語でメモしておく.

2つの文字列の類似度を数値化

2つの文字列の類似度を数値化する手段として
レーベンシュタイン距離(Levenshtein Distance)
ジャロ・ウィンクラー距離(Jaro-Winkler Distance)
というものがある.

レーベンシュタイン距離(Levenshtein Distance)

レーベンシュタイン距離(LD:Levenshtein Distance)2つの文字列の類似度を図る方法である.
元の文字列をs,対象の文字列をtとして考える.
すると,レーベンシュタイン距離はsをtに置き換えるのに必要な削除,挿入,置換の回数として定義できる.

ここで,例を挙げて考えてみよう.

sが"テスト"で,tが"テスト"だとしよう.
これらの文字列は元から同じ文字列であるため変換を必要としない.
そのため,レーベンシュタイン距離LDは以下のように書ける.
LD(s,t) = 0

次に,
sが"テスト"で,tが"テント"だとしよう.
sをtに変えるためには,"ス"を"ン"に変える必要がある.
そのため,レーベンシュタイン距離LDは以下のように書ける.
LD(s,t) = 1

これらの例からわかるように,レーベンシュタイン距離が長くなればなるほど,文字列は異なるものになる.
レーベンシュタイン距離はロシアのレーベンシュタインによって1965年に発表されたが,スペルや発音が難しいためedit distance(編集距離)と呼ばれることが多い.

レーベンシュタイン距離は以下のことに使われている.
・スペルチェック
・会話の認識
・DNAの分析
・剽窃の判断

・参考文献
ピッツバーグ大学の講義資料を元にさせていただきました.
Levenshtein Distance

ジャロ・ウィンクラー距離(Jaro-Winkler Distance)

ジャロ・ウィンクラー距離(Jaro-Winkler Distance)は2つ文字列の部分的な一致を測る.
全く類似していない場合は0,完全に一致する場合は1となる.
この距離では文字列の長さと,文字列中の部分的な間違い(人によるスペルのミス)の数から構成される.
そのためタイプミスやスペルミスの判断などに使用される.

まずは,Jaro Distanceの定義から見ていく.
Jaro-Winkler DistanceはJaro Distanceを使って定義されるので後ほど解説する.
Jaro Distance Φ は以下の式で定義される.

{
\begin{eqnarray}
Φ = W_1 \cdot \frac{c}{d} + W_2 \cdot \frac{c}{r} + W_t \cdot \frac{(c-τ)c}{d} \tag{1}
\end{eqnarray}
}

ただし, c=0Φ=0 とする.
ここで,各文字は以下のように定義される.
 W_1:最初の文字列の文字に掛かる重み
 W_2:2番目の文字列中の文字に掛かる重み
 W_t:置き換えに掛かる重み
 d:最初の文字列の長さ
 r:2番目の文字列の長さ
 τ:文字の「置換」の数
 c区間内で一致する文字の数(順番は関係ない)
実際は,W_1,W_2,W_tには\frac{1}{3}がセットされる.

具体的に c は以下のように数える.
2つの文字の場所が

{
\begin{eqnarray}
\frac{max(d,r)}{2} - 1 \tag{2}
\end{eqnarray}
}

よりも離れていない時に一致すればカウントする.

例えば,
文字列1:あいえお
文字列2:あいかきえおう
があるとする.
この時,文字列1は長さ5,文字列2は長さ7なので,距離が \frac{max(5,7)}{2}-1=\frac{7}{2}-1=3.5 以内で一致した時にカウントすることになる.(実際は小数点は切り捨てても変わらないので3文字以内となる.)

1文字目から順に見ていくと,
1文字目:「あ」=「あ」 → カウント:1
2文字目:「い」=「い」 → カウント:2
3文字目:「う」≠「か」 → カウント:2
3文字目:「う」≠「き」 → カウント:2
3文字目:「う」≠「え」 → カウント:2
4文字目:「え」≠「き」 → カウント:2
4文字目:「え」=「え」 → カウント:3
5文字目:「お」≠「え」 → カウント:3
5文字目:「お」=「お」 → カウント:4
となる.
よって, c=4 である.

また,「置換」の数 τ は以下のように数える.
一致した文字を順に抜き出してできた2つの文字列のうち,片方の文字列中の1文字目が,他方の文字列の1文字目と一致しなければ「置換」は起こらない.
一致した文字を順に抜き出してできた2つの文字列のうち,片方の文字列中の2文字目が,他方の文字列の2文字目と一致しなければ...
と進めていき,置換の数を数える.
これを2で割ることにより「置換」の数 τ とする.

例えば,
文字列1:あいうえおさしすせそ
文字列2:あえいおうたちつてと
があるとする.
一致する文字のみを順に抜き出すと
文字列1:あいうえお
文字列2:あえいおう
となる.

1文字目は共に「あ」のため置換は起こらない.
2文字目は「い」と「え」であるため置換が起こる.
3文字目は「う」と「い」であるため置換が起こる.
4文字目は「え」と「お」であるため置換が起こる.
5文字目は「お」と「う」であるため置換が起こる.
よって,「置換」の数は4/2で2となる.
(つまり,2回置換すれば文字列2は文字列1にできる.)

次に,Jaro-Winkler Distanceの定義を見ていく.
Jaro-Winkler DistanceはJaro Distanceを使って定義される.
Jaro-Winkler Distance Φ は以下の式で定義される.

{
\begin{eqnarray}
Φ_n = Φ + i \cdot 0.1 \cdot (1-Φ) \tag{3}
\end{eqnarray}
}

i=1,2,3,4で,先頭から何文字目まで一致しているかを見る.
つまり,共通の接頭辞があるかどうかを見る.
i は最大4である.

例えば,
文字列1:octagon
文字列2:octopus
があるとする.
共通する接頭辞はoctの3文字であるので, i=3 となる.
日本語の場合は超-,真っ-,全-,などの接頭辞があるが4文字の接頭辞は思いつかないのでもしかすると i=1,2 くらいに設定する必要があるのかもしれない.

・参考文献
Winkler, W. E. (1990). "String Comparator Metrics and Enhanced Decision Rules in the Fellegi-Sunter Model of Record Linkage". Proceedings of the Section on Survey Research Methods. American Statistical Association: 354–359.
http://www.amstat.org/sections/srms/Proceedings/papers/1990_056.pdf

(これを食べながら書いた)

クローバー ポップコーン原料豆業務用 1kg

クローバー ポップコーン原料豆業務用 1kg