5

2 つの名前と 1 つの住所の「レコード」(基本的には CSV 文字列) があります。互いに類似しているレコードを見つける必要があります。基本的に、名前と住所の部分はすべて、人間が解釈したかのように「似ている」ように見えます。

この優れたブログ投稿 ( http://knol.google.com/k/simple-simhashing# ) のアイデアを使用して、単純な SimHash を作成しました。2 つ以上の文字列に対する SimHash の結果が同じである場合、このサブセットのすべてのレコードを、セットのすべてのレコードを他のすべてのレコードと比較する O(n^2) であるきめの細かいマッチング プログラムに渡します。

SimHash 部分には、データグラムのサイズ (基本的には文字列に対するサイズ n のスライディング ウィンドウ) と、SimHash の計算に使用する必要がある (ランダムな) ハッシュの数を決定するために使用する反復回数を定義できるパラメーターがあります。 . これまでのところ、データグラム サイズは 4 で、4 つのハッシュを使用して SimHash を計算しています。いろいろな組み合わせを試しましたが、今のところこれが一番いいです。

私が直面している問題は、このメソッドが私が持っているデータ セットの重複の約 80% を見つけることです。上記の非常に遅い O(n^2) 完全一致に対してデータセット全体を検証したため、これを知っています。O(n^2) マッチャは 10^4 未満のデータ セットには問題ありませんが、サイズ 10^8 のセットを実行する必要があるため、すぐに実行できなくなります。

SimHash の精度を高めて、より多くの「類似」レコードに同じ SimHash 番号がタグ付けされるようにする方法について、アイデア、提案、または考えはありますか?

編集: SimHashing の前に、すべての ![0-9A-Z] 文字を大文字にして削除します。一致させるべきものの例 (スペルミスは意図的なものです):

  • JOHN SMITH、123 ANY STREET SOMETOWN ZIP
  • ジョニー・スミス、123 ANY STRET
  • SOMETOWN ZIP ROBERT PARKER, 442 ANY STREET サムタウン ZIP

ここで、1 と 2 は似ていますが、3 は似ていません。出力は次のようになります: 1 + 2

4

3 に答える 3

3

派手に sim ハッシュを変更しようとする前に、ドメイン固有の知識を問題に適用してみましたか?

アルゴリズムのミスペアのリストはありますか? 彼らに共通点はありますか？

大文字の使用を削除する、ニックネームをフルネームに変換する、ミドルネームを削除する、N、E、S、W および北、南、東、西を展開する、st を通りに展開するなどのことを試しましたか?

于 2011-11-30T15:02:44.770 に答える
0

（以下をコメントに入れたいのですが、まだ担当者がいません。）

最終的に何をしようとしているのですか？すべての重複を検索しますか? 重複をどのように定義していますか? 大文字と小文字の区別は重要ですか? 似た文言？

私はあなたがこれについてどのように行っているかについて少し混乱しています-同様のレコードを見つけてセットを作成しますが、後で O(n^2) が完全に等しいと仮定していることを確認します。正確な同等性をチェックしている場合、同様のレコードを見つけるという目的が無効になるようです (時間を節約するために O(n^2) のフィルターとして使用している場合を除きます。

いくつかのランダムな考え：各レコードを最も一般的な形式に変換しようとする一種のサニタイザーを介して各レコードを実行します（気にする場合/これが重要です）。

正確な等価性に関心があり、メモリが制限されていないが速度を求めている場合は、レコードごとに Java オブジェクトを作成するだけで済みます。各レコードに対して .equals() を定義します (これをいつでもカスタマイズして、正確に等しくしないようにすることができます)。次に、このオブジェクトの hashCode() を定義する必要があります。次に、各レコードを HashSet に貼り付けることができます。

結果の HashSet には重複がありません (.equals() / .hashCode() 実装で定義されているように)。

または、重複を見つけたい場合は、HashSet に追加する前に、最初にレコードが含まれているかどうかを確認し、含まれている場合は、重複を見つけたことになります。

この実装は非常に高速ですが、データセット全体をメモリに保存するため、大量のメモリを使用する可能性があります。これに代わる方法は、各レコードのハッシュを作成し、それを HashSet に格納して、各レコードのハッシュが等しいかどうかを確認することです。

レコードごとにハッシュを行うことの欠点は、適切な分散を備えた適切なハッシュ生成を開発するという課題です。もちろん、ハッシュでは、衝突による誤検出を心配する必要があります。しかし、ハッシュ アルゴリズムがしっかりしていれば、競合が発生する可能性は非常に低いため、心配する必要はありません。

実行できるハッシュについてのいくつかの考えは、すべてのフィールドの連結の MD5 と同じくらい単純なものです。チェックサムを実行できます。または、各フィールドの hashCode の合計を取ることもできます。私は数学の天才ではないので、どちらが最適な分散動作を持ち、結果として衝突の可能性が最も低くなるかはわかりません。このルートに進むことにした場合は、調査する価値があるかもしれません。

于 2011-11-30T15:30:51.367 に答える