レーベンシュタイン距離と三角不等式について混乱しています。ウィキペディアや他の記事では、レーベンシュタイン距離は三角形の不等式に従うと書かれています。
三角不等式はx+y>z_ たとえば、、および。ここで何が欠けていますか？x+yzkitten-> sitting=3kitten->sittin=2sittin->sitting=1
編集
三角形の不等式は、ユークリッド空間ではなく、メートル空間にあります。計量空間では、三角形の不等式はd(x,z)<= d(x,y)+d(y,z)
多くのタスクで、正規化されたレーベンシュタイン距離またはその逆の類似性が使用されていることに言及したいと思います。同様に、長さ 4 と 10 の単語間の距離 2 は、50% と 80% の類似性を意味します。正規化されたレーベンシュタイン距離は、多くの場合、三角形の不等式を満たしません。したがって、数学的な観点からのメトリックではありません。
ただし、レーベンシュタイン距離を正しく正規化することで三角形の不等式を実現できます。
一般的なレーベンシュタイン距離 (GLD) は、正規化されたレーベンシュタイン距離です。GLD は、[0, 1] で評価されるメトリックです。長さ |X| の有限のアルファベットを超える 2 つの文字列 X と Y が与えられます。と|Y|。正規化の式は次のとおりです。
GLD(X,Y) = 2*d(X,Y) / (|X|,|Y| + d(X,Y))
ここで、d(X,Y) はレーベンシュタイン距離です。
この正規化は、記事 [1] の結果として三角不等式を満たします。
作成した Nuget パッケージでも使用しました - 三角形の不等式 (1 - d(X,Y)/max(|X|,|Y|)) に違反する BlueSimilarity[2] 一般的な正規化。
あなたの例
X = 「子猫」、Y = 「座っている」、Z = 「座っている」
GLD(X,Z) <= GLD(X,Y)+ GLD(Y,Z)
2* d(X,Y) / (|X|,|Y| + d(X,Y)) + 2* d(Y,Z) / (|Y|+|Z| + d(Y,Z) ) >= 2*d(X,Z) / (|X|,|Z| + d(X,Z))
2 3 /(6+7+3) + 1 - 2 1/(6+7+1) >= 2*2/(6+6+2)
0.375 + 0.143 >= 0.286
参考文献:
[1] Li Yujian、Liu Bo; 正規化されたレーベンシュタイン距離メトリック。パターン分析とマシン インテリジェンスに関する IEEE トランザクション、2007 年
[2] Rozinek、Ondrej。BlueSimilarity; https://www.nuget.org/packages/BlueSimilarity/