文字列類似性メトリック–距離の編集
1. 序章
このチュートリアルでは、文字列の類似性を定量化する方法について学習します。 ほとんどの場合、アプリケーションで使用できるさまざまな文字列距離タイプについて説明します。 さまざまなメトリックの概要を説明し、各メソッドのプロパティと計算の複雑さについて説明します。 最後に、特定のデータセットの手法の選択に関する推奨事項を考え出します。
2. 問題のコンテキストとメトリックのカテゴリ
レコードリンケージやスペル修正から音声認識や遺伝子シーケンシングに至るまでの複数のアプリケーションは、文字列の類似性の尺度を決定するためにいくつかの定量的メトリックに依存しています。 文字列の類似性の計算は、これらの問題のいずれにも役立ちますが、一般に計算コストが高く、考えられるすべてのデータ障害の多様であいまいな性質のため、理想的な結果を自動的に生成しません。
これを考えると、利用可能な技術のセット全体から使用する最適なメトリックを選択したい場合があります。 以下は、4つのカテゴリにグループ化された最も一般的な文字列類似距離メトリックのチャートです。
この記事では、文字列の直接文字比較に焦点を当てた最初のカテゴリについて説明します。 このファミリのすべてのメトリックは、文字列に対して実行された編集操作の数から導出されるため、一般に編集距離と呼ばれます。
3. ハミング距離
ハミング距離は、比較された文字列の対応する記号が異なる位置の数です。 これは、ある文字列を別の文字列に変換するために必要な置換の最小数に相当します。
KAROLINとKERSTINの2つの弦を取りましょう。 位置1、3、および4（ゼロベース）の文字が異なり、残りはすべて同等であることがわかります。
これは、この場合、ハミング距離が3であることを意味します。
すべての文字列距離メトリックの中で最も簡単なハミング距離は、同じ長さの文字列にのみ適用されます。 計算は簡単で、線形の時間計算量があります。
4. レーベンシュタイン距離
ハミング距離と同様に、レーベンシュタイン距離は、ある文字列を別の文字列に変換するために必要な編集操作の最小数です。 ハミング距離とは異なり、一連の編集操作には挿入と削除も含まれているため、さまざまな長さの文字列を比較できます。
2つの文字列がある場合、それらの間のレーベンシュタイン距離は、1つの文字列を別の文字列に変更するために必要な1文字の編集（挿入、削除、または置換）の最小数です。
たとえば、GRATEとGIRAFFEの間のレーベンシュタイン距離は3です。
2つの弦のサイズが同じである場合、ハミング距離はレーベンシュタイン距離の上限になります。 たとえば、TALKとALSOのハミング距離は、場所ごとに文字が異なるため4です。 ただし、レーベンシュタイン距離は3つだけです。
レーベンシュタイン距離はメートル法の要件に準拠しており、最も重要なのは対称であり、三角不等式を満たすことです。
レーベンシュタイン距離の計算はコストがかかる可能性があり、最悪の場合の完全な計算には時間と空間の複雑さがあります。 償却の複雑さを改善するために多くの最適化手法が存在しますが、一般的なアプローチは、事前に選択されたしきい値を超える完全なレーベンシュタイン距離の計算を回避することです。
正規化されたメトリックを使用する場合は、次の式を使用して、レーベンシュタイン距離を類似度に変換できます。
5. ダメラウ・レーベンシュタイン距離
人間のスペルミスのエラーのほとんどは、挿入、削除、置換、および転置の4つのタイプのエラーに分類されることが観察されています。 この経験的観察に動機付けられて、ダメラウ・レーベンシュタイン距離は、2つの隣接する文字の転置を使用して、レーベンシュタイン距離で許可される編集操作のセットを拡張します。
たとえば、GIFTとFITの間のレーベンシュタイン距離は3です。
この例では、IFをFIに変換するために2つのステップが必要です。 ただし、隣接する2つの文字間の転置を許可する場合、変換を行うために使用できるステップは1つだけです。 したがって、GIFTとFITの間のダメラウレーベンシュタイン距離は2です。
元のレーベンシュタイン距離計算アルゴリズムに転置を組み込むことは、比較的困難な場合があります。 転置を担当するエントリを使用してレーベンシュタイン距離の計算に使用される動的計画法のアプローチを簡単に変更すると、ダメラウ・レーベンシュタイン距離ではなく、期待される結果とは異なるだけでなく、三角不等式のプロパティも保持しない「最適な文字列整列距離」が予期せず計算されます。 。
ダメラウ・レーベンシュタイン距離を計算するための効率的なアルゴリズムは、同じ時間計算量を提供します–。
6. ジャロ距離
文字列との間のJaroの類似性は、次の式を使用して定義されます。
どこ：
一致する文字の数です。 からの2つの文字が同じであり、文字が離れていない場合は、一致していると見なします。
一致する（ただしシーケンス順序が異なる）文字の半分の数です。
Jaroの類似性の値の範囲は0から1までです。 2つの文字列がまったく同じである場合、および。 したがって、それらのJaroの類似性は、2番目の条件に基づいて1になります。 一方、2つの文字列が完全に異なる場合は、。 それらのJaroの類似性は、最初の条件に基づいて0になります。
ジャロ距離は、ジャロ類似性の反転です。 したがって、ジャロ距離の値が大きいほど、2つの弦の差が大きくなります。
たとえば、CARTELと TRACE、「A」、「R」、および「E」のみが一致する文字であることがわかります。
一致する距離のしきい値はです。 文字「C」は両方の文字列に表示されますが、3文字離れています。 したがって、「C」を一致する文字とは見なしません。 同様に、文字「T」も一致する文字ではありません。 全体として、一致する文字の総数はです。
一致するシーケンスはAREとRAEです。 一致する（ただしシーケンス順序が異なる）文字の数は2です。これは、を意味します。 したがって、2つの文字列のJaro類似性の値はです。 すると、ジャロ距離はです。
時間計算量は2次式ですが、ジャロ距離を計算するアルゴリズムの空間計算量はです。
7. ジャロ・ウィンクラー距離
Winklerは、経験的観察に基づいたアイデアを適用することにより、Jaroアルゴリズムを改善しました。これにより、スペルミスのある人の名前の先頭で発生するエラーが少なくなることがわかりました。
したがって、ウィンクラーアルゴリズムは、同等の初期文字のJaro類似度を増加させます。
どこ：
は、両方の文字列の先頭にある共通プレフィックスの長さで、最大4までです。
はスケーリング係数です。 スケーリング係数は0.25を超えてはなりません。 そうしないと、考慮されるプレフィックスの最大長が4であるため、類似度が1より大きくなる可能性があります。 オリジナルのウィンクラーの作品は値0.1を使用しました。
ジャロ距離と同様に、ジャロウィンクラー距離をとして定義できます。
たとえば、2つの文字列TREATとTRACEを比較すると、一致するシーケンスはTRAです。
したがって、これら2つの文字列間のJaroの類似性はです。 2つの文字列の共通のプレフィックスはTRで、長さは2です。 スケーリング係数として0.1を使用すると、ジャロ・ウィンクラー類似度はになります。 すると、ジャロ・ウィンクラー距離はです。
ジャロ・ウィンクラー距離は三角不等式に従わないため、距離空間を構築するのに適した距離ではありません。
Winklerは、2つ以上の単語を含む文字列を比較するというトピックも検討しましたが、順序が異なる可能性があります。 この目的のために、彼はバリアント SortedWinklerおよびPermutedWinklerを導入しました。 前者のアルゴリズムは、類似性を計算する前に文字列をアルファベット順にソートしますが、後者は、考えられるすべての順列の類似性を計算し、最大値を返します。
8. 評価と推奨事項
利用可能なアルゴリズムのすべての多様性を考えると、関連するデータセットの一致品質を評価することが重要になります。一致の最終結果は、選択した類似度のしきい値に基づいて一致/不一致として分類する必要があります。しきい値を超える類似度値は一致として分類され、以下の類似度値を持つペアは不一致として分類されます。
具体的な推定を提供するための一般的な方法は、ラベル付きのトレーニングデータを使用することです。
一致するすべてのペアについて、真の陽性（一致として分類される既知の一致する文字列ペア）、真の陰性（不一致として分類される既知の不一致のペア）、偽陽性-一致として分類される不一致のペア、および偽の数を定義します。ネガティブ–不一致として分類された既知の一致ペア。
これらの値を使用して、PrecisionおよびRecallを推定します。
精度は、見つかったすべての一致間の実際の対応の割合を反映します。精度の値が高いソリューションは、多くの誤検知を返さないことを意味します。
リコールは実際の対応のシェアを指定します。特定のソリューションのリコールの値が高いということは、多くのフォールスネガティブを返さないことを意味します。
最後に、全体的な効率を見積もるために、F-measureを使用できます。 Fメジャーは、適合率と再現率の調和平均です：
品質のマッチングに加えて、パフォーマンスは大規模なデータセットを処理するために重要です。
速度が重要な場合は、文字列の長さが線形である時間計算量の手法を使用することが不可欠です。 手元の名前データにニックネーム、エイリアス、および同様のバリエーションが多く含まれていることがわかっている場合は、照合を実行する前に、辞書ベースの名前の標準化を適用する必要があります。
一般に、短い文字列にはレーベンシュタイン距離などのより良い品質を提供し、長い文字列にはトークンベース（qグラムやバッグ距離など）を提供する重いアルゴリズムを使用することをお勧めします。
文字列の類似性に加えて、構文的な性質上、異なる文またはドキュメント全体で意味的な類似性を見つけるという関連する問題に対処する必要がある場合があります。 パス長、情報コンテンツ、辞書などに基づくさまざまなセマンティックメトリックがあります。 それらに加えて、潜在意味解析、ポイントワイズ相互情報量など、いくつかの統計的アプローチが構築されています。
NCD – 正規化された圧縮距離など、上記のカテゴリ以外にも、あまり一般的ではない指標がいくつかあります。これらは、アプリケーションで使用できます。
9. 結論
このチュートリアルでは、文字列の類似性を評価するための複数のアルゴリズムとメトリックについて説明しました。
この問題に対処するために複数の異なるアプローチを使用する可能性があることがわかりました。それぞれのアプローチには、実装と実行の両方の点で独自の複雑さがあります。
最後に、これらのメトリックを評価して、アプリケーションに最適なものを見つける方法を確認しました。
