二つの文字列の類似度

　雑な備忘録なので、サーベイの前準備程度にお使いください。
　二つの文字列の類似度を測る方法についてまとめる。なお、値が高いほど類似度が高いものには青色、値が高いほど類似度が低いものには赤色で色付けた。
　なお、意味レベルまで考慮して単文あるいは複文同士の類似性を測る技術を一般関係認識や含意関係認識といいます。そこについては書いていませんが、乾健太郎先生の資料が大変参考になりそうです。大規模言語資源時代の意味談話処理
また、原田実先生が開発された意味解析システムSAGEも日本語文の類似性を測る技術です。

文字について、
Shift-JISはダメ文字(2nd octetが5c=backslash)を含んでいるため文字化けの危険がある。
EUC-JPの全角は2 octets文字なので一文字目がAB、二文字目がCDの場合、
正規表現でBCを置換すると文字化けの危険がある。また、マルチバイト文字対応の正規表現に投げるために半角を全角に直すなどの前処理が必要。
これらの問題がUTF-8にはない。その代り、Shift-JISやEUC-JPをUTF-8に変換すると、日本語の全角文字が2から3 octetsに増えるため、日本語文書は約1.5倍の容量になる。

半角文字「1」と全角文字「１」のようにまったく同じ概念を指す文字は一般的には前処理でどちらかに揃えておいた方が後の処理が楽になる。
Unicode 正規化のNFKCフォームで変換するとこのような字種による表記ゆれの問題は回避できる。ただし、句点「。」や読点「、」がピリオド「.」やカンマ「,」に変換されるので注意が必要。

編集距離
- Levenshtein 距離
- Damerau-Levenshtein 距離
Jaro 距離
Jaro-Winkler 距離
Hamming 距離
Sørensen 類似度
Czekanowski 類似度
Bray–Curtis 非類似度
Spearman's 順位相関係数
Kendall tau 順位相関係数
Kendall W 一致係数
ROUGE
- ROUGE-N
  - ROUGE-1
  - ROUGE-2
  - ROUGE-3
  - ROUGE-4
  - ROUGE-5
  - ROUGE-6
  - ROUGE-7
  - ROUGE-8
  - ROUGE-9
- ROUGE-L
- ROUGE-W
  - ROUGE-W1.2
- ROUGE-S
  - ROUGE-S*
  - ROUGE-S4
  - ROUGE-S9
- ROUGE-SU
  - ROUGE-SU*
  - ROUGE-SU4
  - ROUGE-SU9
Cohen’s Kappa
Scott's Pi
Fleiss' Kappa

係り受け関係による類似度

木編集距離

拡張

辞書の利用
検索エンジンの利用

スコアリング後の類似度

Euclidean 距離
normalized Euclidean 距離
Mahalanobis 距離
Manhattan 距離
Chebyshev 距離
Minkowsky 距離
Jaccard 距離
Tanimoto 距離
内積
Dice's 係数
Jaccard 係数(Tanimoto 類似度)
Tversky 係数
Simpson's 係数
Jaccard-Simpson 係数
Lin 98 類似度
Cosine 類似度
共分散
Pearson 相関係数
偏差パターン類似度

スコアの周辺化後の類似度

Pointwise 相互情報量
相互情報量
Kullback–Leibler divergence
Cross Entropy
Perplexity
Bhattacharyya 係数
Bhattacharyya 距離
Hellinger 距離

今回載せていない類似度

Kulczyński 類似度
Renkonen 類似度
Sokal-Sneath 非類似度
McConnaughey 類似度
Kullback–Leibler diveregenceとHellinger 距離以外のf-divergence
BLEU4
など

内容

表層文字列の一致度

編集距離

１つの文字列を別の文字列に変形するのに必要な手順の最小回数。編集操作の違いで名前が変わる。

- Levenshtein 距離

操作は文字の挿入（insertion）、削除（deletion）、置換（substitution）。両文字列の長さの和で割れば区間[0,1)になるが、距離空間ではなくなる。

- Damerau-Levenshtein 距離

Levenshtein 距離とほぼ同じ。ただし、操作に交換（transposition）が加わる。

Jaro 距離

Jaro 距離djは文字列s1、s2において次の３つの類似度の平均。

1. s1とs2に一致する文字数mとすると、 $\frac{m}{|s_1|}$
2. $\frac{m}{|s_2|}$
3. s1とs2の不一致部分で、それぞれで交換するとs1とs2が一致する文字数の合計を２で割った値tとする。例えば、MARTHAとMARHTAの場合はH/TとT/Hの二文字を２で割って、t=1。このとき、 $\frac{m-t}{m}$

従って、
$d_j=\frac{\frac{m}{|s_1|}+\frac{m}{|s_2|}+\frac{m-t}{m}}{3}$

Jaro-Winkler 距離

JW距離dwは
$d_w=d_j+lp(1-d_j)$
ここで、lはs1とs2で一致する接頭辞（先頭文字からの連続する文字列）の文字数（最大４）
pはlに対するスケール因数（0.25以下の定数）。デフォルトでp=0.1。

Hamming 距離

等しい文字数を持つ２つの文字列の中で、対応する位置にある異なった文字の数。

Sørensen 類似度

AとBをサンプルA, Bのそれぞれの種類の数、CをAとBに共通する種類の数とすると、
$QS=\frac{2C}{A+B}$
文字列を構成する要素：形態素、n-gramなどでA, B, Cを求める。
この数式の形はシソーラスを使った類似度やDice's 係数、Czekanowski 類似度、また1-QSの形でHellinger 距離やBray Curtis 非類似度に見られる。

Czekanowski 類似度

Sørensen 類似度とほぼ同じ。Sørensen 類似度が種類に注目しているのに対して、Czekanowski 類似度は量に注目している。

Bray–Curtis 非類似度

$1-QS$

　また、２つのベクトルが同じ項目で構成されているが項目の順位が異なる場合、次の類似度が求まる。

Spearman's 順位相関係数

XとYの対応する順位の差Dについて、
$\rho =1-\frac{6\sum D^2}{T^3-T}$
ただし、同順位がある場合は、X、Yにおける同順位の個数をそれぞれnx、ny、それらの順位をti[1,nx]、tj[1,ny]とし、
$\rho =\frac{T_x+T_y-\sum D^2}{2\sqrt{T_x T_y}}$
$T_x=\frac{N^3-N-\sum (t_i^3-t_i)}{12}$
$T_y=\frac{N^3-N-\sum (t_j^3-t_j)}{12}$

Kendall tau 順位相関係数

Pを２つの項目の順位の組を考えたとき大小関係が一致する組の数とすると、
$\tau =\frac{4P}{T(T-1)}-1$

Kendall W 一致係数

後で書く

ROUGE

テキスト要約の自動評価

Cohen’s Kappa

後で書く

Scott's Pi

後で書く

Fleiss' Kappa

後で書く

係り受け関係による類似度

木編集距離

１つの木を別の木に変形するのに必要な手順の最小回数。

拡張

辞書の利用

　シソーラスを利用する方法。ただし、辞書に載っていない語は当然扱えない。
シソーラスには分類シソーラスと上位下位シソーラスの２種類存在し、類似度の求め方はそれぞれ異なる。
分類シソーラスは、２つの語に共通する上位語の深さによって類似度が求まる。
上位下位シソーラスは、２つの語に共通する上位語の根からの深さの最大をdcとし、２つの語のシソーラス中における根からの深さをそれぞれdi, djとすると、
$\frac{2d_c}{d_i+d_j}$
この類似度計算は、シソーラスのように、各ノード間の距離が等距離になるよう意図して設計されているデンドログラムにのみ有効である。
日本語で利用可能な物として、次の辞書がある。（利用の際はライセンスに注意。）

分類語彙表と角川類語新辞典は分類シソーラスである。それ以外は上位下位シソーラスである。また、角川類語新辞典より分類語彙表の方が多くの語を含んでいる。

検索エンジンの利用

　検索エンジンに投げて、得られたスニペットから語の頻度情報を基に確率検索モデル（TF-IDF法やOkapi BM25など）を使って類似度を測る方法。語としては、形態素あるいはn-gramを利用する。その際、ストップワードとして形態素は助詞、助動詞を、n-gramは頻度上位桁を取り除く
。
APIが開放されている検索エンジン

- Google Web Search API
- Yahoo! Search API（2013年3月31日をもって停止。どうもGoogleがAPIとしての提供を拒否したらしい。合理化すると権限が奪われて後で困るひとつの例。）
- TSUBAKI API（返ってこない・ときどき返す・サーバ停止中のいずれか）
- bing API 無料で叩ける回数がGoogleより多い。
- DuckDuckGo（日本語検索が対応しているとは言え、レスポンスの質がいまいち）

形態素解析器（辞書のライセンスにも注意！！cf. ICOT条項）

- MeCab
- ChaSen
- CaboCha（日本語構文解析もできる）
- Juman
- KyTea
- Yahoo!日本語形態素解析API 毎週辞書を更新しているため辞書の即時性が優れている（特に名詞）。

辞書

- IPA
- UniDic できるだけ細かい単位で分解する。例：横浜国立大学⇒横浜、国立、大学
- NAIST
- JUMAN 代表表記＋KNP（JUMAN辞書の出力を入力とする日本語構文解析器）

スコアリング後の類似度

　まず２つの文字列を何かしらの方法で同じT次元のベクトルxとyとしてスコア付ける。スコアリングの方法としては、例えば形態素解析して形態素の頻度情報を使う、あるいは、形態素レベルのn-gramの頻度を使う方法などがある。それにより次のような類似度が求まる。ただし、i[1,T]とする。

Euclidean 距離

$\sqrt{\sum (x_i-y_i)^2}$

normalized Euclidean 距離

共分散行列が対角近似された場合の多変量ガウス分布の指数部に似てる。
$\sqrt{\sum (\frac{x_i-y_i}{\sigma_i})^2}$

Mahalanobis 距離

多変量ガウス分布の指数部に似てる。
$\sqrt{(x-y)^T\Sigma^{-1}(x-y)}$

Manhattan 距離

$\sum |x_i-y_i|$

Chebyshev 距離

$\max (|x_1-y_1|,|x_2-y_2|,\cdots,|x_T-y_T|)$

Minkowsky 距離

$(\sum |x_i-y_i|^q)^{\frac{1}{q}}$

Jaccard 距離

Jaccard 係数J(X,Y)とすると、
$1-J(X,Y)$

Tanimoto 距離

$-log_2 J(X,Y)$

内積

$|X\cap Y|=\sum x_i\cdot y_i$

Dice's 係数

$\frac{2|X\cap Y|}{|X|+|Y|}=\frac{2\sum x_i\cdot y_i}{\sum x_i^2+\sum y_i^2}$

Jaccard 係数（Tanimoto 類似度）

$\frac{|X\cap Y|}{|X\cup Y|}=\frac{\sum x_i\cdot y_i}{\sum x_i^2+\sum y_i^2-\sum x_i\cdot y_i}$

Tversky 係数

Dice's 係数とJaccard 係数（Tanimoto 類似度）の一般化。
$\frac{|X\cap Y|}{|X\cap Y|+\alpha |X-Y|+\beta |Y-X|}=\frac{\sum x_i\cdot y_i}{\sum x_i\cdot y_i+\alpha (\sum x_i^2-\sum x_i\cdot y_i)+\beta (\sum y_i^2-\sum x_i\cdot y_i)}$
ただし、 $\alpha, \beta\ge 0$ 。
$\alpha =\beta =1$ のとき、Jaccard 係数（Tanimoto 類似度）。
$\alpha =\beta =0.5$ のとき、Dice's 係数。

Simpson's 係数

$\frac{|X\cap Y|}{\min(|X|,|Y|)}=\frac{\sum x_i\cdot y_i}{\min(\sum x_i^2,\sum y_i^2)}$

Jaccard-Simpson 係数

$\frac{Jaccard+Simpson}{2}=\frac{|X\cap Y|}{2}\cdot (\frac{1}{|X\cup Y|}+\frac{1}{\min(|X|,|Y|)})=\frac{\sum x_i\cdot y_i}{2}\cdot (\frac{1}{\sum x_i^2+\sum y_i^2-\sum x_i\cdot y_i}+\frac{1}{\min(\sum x_i^2,\sum y_i^2)})$

Lin 98 類似度

$\frac{2\sum_{X\cap Y} (x_i+y_i)}{\sum x_i+\sum y_i}$
xiもyiも0でない場合分子に(xi+yi)が足されるって解釈であってるなら、ディラックのデルタ関数を使って表現するとこんな感じ。
$\frac{2\sum \frac{x_i+y_i}{1+\delta (x_i+ y_i)}}{\sum x_i+\sum y_i}$