サンプルサイズが大きいときに文字列の類似度スコアを計算する効率的な方法は？
https://stackoverflow.com/questions/1609742
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
10,000個の電子メールアドレスのリストがあり、最も近い「隣人」のいくつかを見つけたいとしましょう。このリストの-は、リスト内の他のメールアドレスに疑わしいほど近いメールアドレスとして定義されています。
2つの文字列間のレーベンシュタイン距離の計算方法を知っています（ありがとうこの質問）ある文字列を別の文字列に変換するために必要な操作のスコア。
「別のメールアドレスに疑わしいほど近い」と定義するとしましょう。レーベンシュタインスコアがN未満の2つの文字列として。
すべての可能な文字列をリスト内の他のすべての可能な文字列と比較する以外に、スコアがこのしきい値より低い文字列のペアを見つけるより効率的な方法はありますか？つまり、このタイプの問題は O（n ^ 2）よりも早く解決できますか？
この問題に対して、レーベンシュタインのスコアはアルゴリズムの選択肢として不適切ですか？
解決
はい- BK-Tree 。距離nのすべての文字列を生成することを含む代替ソリューションは、1のレーベンシュタイン距離ではより速くなる可能性がありますが、より長い距離では作業量が急激に制御不能になります。
他のヒント
Levenshteinで O（kl）で実行できます。 k は最大距離、lは最大文字列です。
基本的に基本的なレーベンシュタインの計算方法を知っている場合、メインの対角線から k よりも離れているすべての結果は k よりも大きくなければならないことが簡単にわかります。したがって、幅 2k + 1 のメイン対角線を計算すれば十分です。
10000個の電子メールアドレスがある場合、より高速なアルゴリズムは必要ありません。コンピューターは O（N ^ 2）で十分に高速に計算できます。
レーベンシュタインはこの種の問題に非常に適しています。
また、比較する前に、soundexを使用してメールを変換することも検討できます。おそらく、より良い結果が得られます。
この問題はクラスタリングと呼ばれ、より大きな重複排除問題の一部です（クラスターのどのメンバーが「正しい」メンバーであるかを判断できます） ）、 merge-purge とも呼ばれます。
このトピックに関するいくつかの研究論文を一度読んだことがあり（名前は以下です）、基本的に、著者は文字列のソートされたリストでサイズ制限付きのスライディングウィンドウを使用しました。それらは比較するだけです（距離を編集アルゴリズムを使用）N * N文字列 inside ウィンドウ。これにより、計算の複雑さが軽減されます。 2つの文字列が似ている場合、それらはクラスターに結合されました（レコードを別のクラスターテーブルに挿入します）。
リストの最初のパスの後に、 2番目のパスが続きます。ここでは、文字列がソートされる前に反転されました。このように、異なる頭を持つ文字列は、同じウィンドウの一部として評価されるのに十分に接近する別の機会がありました。この2回目のパスで、ウィンドウ内の文字列が2つ（またはそれ以上）の文字列に十分近く見え、それらの文字列がすでに（最初のパスで見つかった）独自のクラスターの一部である場合、2つのクラスターはマージされます（クラスターテーブルを更新することにより）、現在の文字列が新しくマージされたクラスターに追加されます。このクラスタリング手法は、 union-find アルゴリズムとして知られています。
その後、ウィンドウを上位X個の実質的にユニークなプロトタイプのリストに置き換えることにより、アルゴリズムを改善しました。各新しい文字列は、上位Xの各プロトタイプと比較されます。文字列がプロトタイプの1つに十分近いように見える場合、プロトタイプのクラスターに追加されます。プロトタイプがどれも十分に似ていない場合、文字列は新しいプロトタイプになり、一番上のXリストから最も古いプロトタイプを押し出します。 （プロトタイプのクラスター内のどの文字列をクラスター全体を表す新しいプロトタイプとして使用するかを決定するために採用されたヒューリスティックロジックがありました）。繰り返しますが、文字列がいくつかのプロトタイプに似ている場合、すべてのクラスターがマージされます。
私はかつてこのアルゴリズムを名前/住所レコードの重複排除用に実装しました。リストのサイズは約1,000万〜5,000万レコードで、非常に高速に動作しました（重複も発見されました）。
このような問題の場合、最も難しいのはもちろん、類似性しきい値の適切な値を見つけることです。アイデアは、非常に多くの false positive を生成せずにすべての重複をキャプチャすることです。異なる特性を持つデータには、異なるしきい値が必要になる傾向があります。編集距離アルゴリズムの選択も重要です。一部のアルゴリズムはOCRエラーに優れ、他のアルゴリズムはタイプミスに優れ、さらに他のアルゴリズムは音声エラー（電話で名前を取得する場合など）に優れています。
クラスタリングアルゴリズムを実装したら、一意のサンプルのリストを取得し、各サンプルを人工的に変更して、すべてのバリエーションが保持されているという事実を維持しながら、クラスタリングアルゴリズムをテストするのが良い方法です同じ親から来ます。このリストはシャッフルされ、アルゴリズムに送られます。元のクラスタリングと重複排除アルゴリズムによって生成されたクラスタリングを比較すると、効率スコアが得られます。
書誌：
Hernandez M. 1995、大規模データベースのマージ/パージの問題。
Monge A. 1997、ほぼ重複したデータベースレコードを検出するための効率的なドメイン非依存アルゴリズム。
O（n ^ 2）よりも良い結果が得られるとは思いませんが、アプリケーションを使用可能にするのに十分な高速化となる可能性のある小さな最適化を行うことができます。
- 最初に@の後の部分ですべてのメールアドレスをソートし、同じアドレスのみを比較できます
- 2つの住所間の距離の計算がnより大きくなったら、計算を停止できます
編集：実際には、O（n ^ 2）よりも良い結果が得られます。以下のNick Johnsonsの回答をご覧ください。
10,000件のメールアドレスはあまり聞こえません。より大きなスペースでの類似検索には、シングリングと min-hashing 。このアルゴリズムは実装が少し複雑ですが、大きなスペースでははるかに効率的です。
問題を元に戻すという条件の下で、よりうまくやることが可能です。
ここで、あなたの10.000アドレスはかなり「修正」されていると思います。そうでなければ、更新メカニズムを追加する必要があります。
アイデアは、レーベンシュタイン距離を使用することですが、Pythonでは「リバース」モードです：
class Addresses:
def __init__(self,addresses):
self.rep = dict()
self.rep[0] = self.generate_base(addresses)
# simple dictionary which associate an address to itself
self.rep[1] = self.generate_level(1)
self.rep[2] = self.generate_level(2)
# Until N
generate_level メソッドは、以前のセットから既に存在するバリエーションを差し引いた、以前のセットから可能なバリエーションをすべて生成します。キーに関連付けられた値として「オリジン」を保持します。
次に、さまざまなセットで単語を検索する必要があります。
def getAddress(self, address):
list = self.rep.keys()
list.sort()
for index in list:
if address in self.rep[index]:
return (index, self.rep[index][address]) # Tuple (distance, origin)
return None
そうすると、さまざまなセットを1回計算します（時間がかかりますが、それをシリアル化して永久に保持できます）。
そして、ルックアップはO（n ^ 2）よりもはるかに効率的ですが、生成されるセットのサイズに依存するため、正確に指定することは少し難しいです。
3つの文字列があるとします：
1-＆quot; abc＆quot; 2-「bcd」 3-＆quot; cde＆quot;
1＆amp;間のL距離2は2です（「a」を減算し、「d」を追加します）。 Lと2の間の距離3は2です（「b」を減算し、「e」を追加します）。
あなたの質問は、1＆amp;の間のL距離を推測できるかどうかです。上記の2つの比較を使用して3。答えはノーです。
1＆amp;間のL距離3は3（すべての文字を置換）です。最初の2つの計算のスコアのため、これを推測する方法はありません。スコアは、削除、挿入、または置換操作が実行されたかどうかを明らかにしません。
だから、レーベンシュタインは大規模なリストには適していません。
実際に電子メールアドレスを比較している場合、これを行うための1つの明白な方法は、レベンシュタインアルゴリズムとドメインマッピングを組み合わせることです。同じドメインを使用して何かに複数回サインアップしたときのことを考えることができますが、メールアドレスのユーザー名の部分は異なります。
