algorithm - 重複データを検出する方法は？

Question

単純な連絡先データベースがありますが、ユーザーが重複データを入力する際に問題が発生します。簡単なデータ比較を実装しましたが、残念ながら、入力されている重複データは完全に同じではありません。たとえば、名前のつづりが間違っているか、同じ人の1人が「BillSmith」を入力し、別の人が「WilliamSmith」を入力します。

それで、エントリが別のエントリにどれほど類似しているかのパーセンテージを与えることができるある種のアルゴリズムはありますか？

score 7 · Accepted Answer

あるエントリが別のエントリとどの程度類似しているかをパーセンテージで表示できるアルゴリズムはあるのでしょうか?

Soundex や編集距離などのアルゴリズム (以前の投稿で提案されているように) は、いくつかの問題を解決できます。ただし、データのクリーニングを真剣に考えている場合、これでは不十分です。他の人が言っているように、「ビル」は「ウィリアム」のようには聞こえません。

私が見つけた最善の解決策は、縮小アルゴリズムとテーブルを使用して名前をルート名に縮小することです。

通常の Address テーブルに、名前のルートバージョンを追加します。たとえば、Person (Firstname、RootFirstName、Surname、Rootsurname....) などです。

次に、マッピングテーブルを作成します。FirstNameMappings (主キー名、ルート名)

次の方法でマッピングテーブルにデータを入力します。

これにより、「UNDEFINED」の RootName とともに、person テーブルにあるすべてのファーストネームが追加されます。

ここで、悲しいことに、すべての一意の名前を調べて、それらを RootName にマップする必要があります。たとえば、"Bill"、"Bill"、"Will" はすべて "William" に変換する必要があります。これには非常に時間がかかりますが、データの品質が本当に重要な場合は、これが最善の方法の 1 つだと思います。

次に、新しく作成したマッピングテーブルを使用して、Person テーブルの「Rootfirstname」フィールドを更新します。姓と住所について繰り返します。これが完了すると、スペルミスに苦しむことなく重複を検出できるはずです。

score 5 · Accepted Answer

名前をレーベンシュタイン距離と比較できます。名前が同じ場合、距離は0です。それ以外の場合は、1つの文字列を別の文字列に変換するために必要な操作の最小数によって与えられます。

score 4 · Accepted Answer

この問題はよく理解されていると思いますが、最初に読んだときに私に起こることは次のとおりです。

フィールドを個別に比較する
一致するものを数えます（一致の定義が緩い可能性があり、フィールドの重み付けが異なる可能性があります）
人間の介入のために、あるしきい値を超えるすべてのケースに存在する

既存のデータベースを使用して、しきい値を最初に適切に推測し、経験を積み重ねるにつれて修正します。

少なくとも最初は、誤検知に対してかなり強いバイアスを好むかもしれません。

score 3 · Accepted Answer

私はあなたのためのアルゴリズムを持っていませんが、私の最初の行動は、新しい連絡先の入力に関連するプロセスを調べることです。おそらく、ユーザーは探している連絡先を見つける簡単な方法を持っていません。Stack Overflowの新しい質問フォームと同様に、新しい連絡先画面にすでに存在する連絡先を提案できます。

score 3 · Accepted Answer

SSIS にアクセスできる場合は、あいまいグループ化とあいまい参照変換を確認してください。

http://www.sqlteam.com/article/using-fuzzy-lookup-transformations-in-sql-server-integration-services

http://msdn.microsoft.com/en-us/library/ms137786.aspx

score 3 · Accepted Answer

文字列フィールドを含む大規模なデータベースがある場合、 simhashアルゴリズムを使用すると、多数の重複を非常に迅速に見つけることができます。

score 2 · Accepted Answer

これは関連している場合と関連していない場合がありますが、Soundex検索で小さなスペルミスが検出される場合があります。たとえば、これにより、Britney Spears、Britanny Spares、およびBritnySpearsを重複と見なすことができます。

ただし、ニックネームの縮小は重複と見なすのが難しく、賢明かどうかは疑問です。BillSmithとWilliamSmithという名前の人が複数いるはずですが、Charles-> Chuck、Robert->Bobなどでそれを繰り返す必要があります。

また、たとえばイスラム教徒のユーザーを検討している場合、問題はより困難になります（たとえば、Mohammed / Mohammadという名前のイスラム教徒が多すぎます）。

score 1 · Accepted Answer

名前とニックネームの問題でうまくいくかどうかはわかりませんが、この種の分野で最も一般的なアルゴリズムは、編集距離/レーベンシュタイン距離アルゴリズムです。これは基本的に、あるアイテムを別のアイテムに変えるために必要なキャラクターの変更、追加、削除の数です。

名前については、純粋にアルゴリズム的なアプローチで良い結果が得られるかどうかはわかりません。本当に必要なのは大量のデータです。たとえば、Google のスペル候補が通常のデスクトップアプリケーションの候補よりどれだけ優れているかを考えてみましょう。これは、Google が何十億もの Web クエリを処理し、どのクエリが相互につながるか、「何を意味するか」のリンクが実際にクリックされるかなどを調べることができるためです。

名前の一致の問題を専門とする会社がいくつかあります (主に国家安全保障および詐欺アプリケーション用)。私が覚えているのは、Search Software America がこれらの人たちに買収されたようですhttp://www.informatica.com/products_services/identity_resolution/Pages/index.aspxですが、これらの種類のソリューションはどれも遠く離れていると思います連絡先アプリケーションには高価です。

score 1 · Accepted Answer

FullContact.com には、これを解決できる API があります。こちらのドキュメントを参照してください: http://www.fullcontact.com/developer/docs/?category=name。

Name Normalization (Bill into William)、Name Deducer (生テキスト用)、および Name Similarity (2 つの名前の比較) 用の API があります。

現時点ではすべての API が無料です。始めるには良い方法かもしれません。

score 0 · Accepted Answer

0

また、確率的マッチングを調べることもできます。

于 2008-09-20T15:43:50.553 に答える

algorithm - 重複データを検出する方法は？

11 に答える 11

Related

Reference