問題タブ [record-linkage]

次のような個人データを含むテーブルのソースがいくつかあります。

したがって、ソース1と2のID 1のレコードが同じ人物であると仮定すると、私の問題は、すべてのソースのレコードが同じ人物を表すかどうかを判断する方法です。さらに、すべてのレコードがすべてのソースに存在するわけではないことを確認してください。すべての名前は、主にスペイン語で書かれています。

この場合、データソースが国の公式識別局に対して厳密にチェックされていないことを前提としているため、正確な一致を緩和する必要があります。また、データを収集するプロセスの性質上、タイプミスが一般的であると想定する必要があります。さらに、レコードの量は、すべてのソースで約200万から300万です...

私たちのチームは次のようなことを考えていました。まず、ID NUMBERやNAMESなどの選択したフィールドで完全一致を強制して、問題がどれほど難しいかを確認します。次に、一致基準を緩和し、一致できるレコードの数を数えますが、ここで問題が発生します。ノイズを生成しすぎず、制限しすぎずに一致基準を緩和するにはどうすればよいでしょうか。

これを処理するためにどのツールがより効果的である可能性がありますか？たとえば、このマッチングをサポートするためのデータベースエンジンの特定の拡張機能について知っていますか？この近似一致を処理するためのsoundexのような巧妙なアルゴリズムについて知っていますが、スペイン語のテキスト用です。

どんな助けでもいただければ幸いです！

ありがとう。

私はデータベースにある構造化されたレコードのかなり小さなコーパスを持っています。Webフォーム（テーブルスキーマと同じように構造化されている）を介して送信された単一のレコードに含まれる情報のごく一部を考えると（これをテストレコードと呼びます）、リストをすばやく作成する必要があります。テストレコードと一致する可能性が最も高いレコード、および検索用語がレコードとどの程度一致しているかの信頼性の見積もりを提供します。この検索の主な目的は、コーパス内のレコードと重複するレコードを誰かが入力しようとしているかどうかを検出することです。テストレコードが重複する可能性は十分にあり、テストレコードが重複しない可能性は十分にあります。

レコードの幅は約12000バイトで、レコードの総数は約150,000です。テーブルスキーマには110の列があり、検索の95％が最も一般的に検索される上位5％の列になります。

データは、名前、住所、電話番号、その他の業界固有の番号などです。コーパスとテストレコードの両方で、手作業で入力され、個々のフィールド内で半構造化されています。最初は「列に手作業で重みを付け、その中の単語トークンを一致させる」と赤面するかもしれませんが、それはそれほど簡単ではありません。私もそう思いました。電話番号を取得した場合、それは完全に一致することを示していると思いました。問題は、トークンの頻度が桁違いに変化しないフォームに単一のフィールドがないことです。電話番号は、コーパスに100回、またはコーパスに1回表示される場合があります。他の分野についても同じことが言えます。これにより、フィールドレベルでの重み付けは実用的ではなくなります。きちんとしたマッチングを得るには、よりきめ細かいアプローチが必要です。

私の最初の計画は、ハッシュのハッシュを作成することでした。最上位はフィールド名です。次に、特定のフィールドのコーパスからすべての情報を選択し、そこに含まれるデータをクリーンアップして、サニタイズされたデータをトークン化し、トークンをキーとして、頻度を値として、第2レベルでトークンをハッシュします。

頻度カウントを重みとして使用します。参照コーパス内のトークンの頻度が高いほど、テストレコードで見つかった場合に、そのトークンに付加する重みは少なくなります。

私の最初の質問は、部屋の統計家に向けたものです。頻度を重みとしてどのように使用しますか？n、レコード数f（t）、トークンtがコーパスに出現する頻度、レコードがオリジナルで重複ではない確率o、および確率pの間に正確な数学的関係がありますか？テストレコードは、実際にはテストが与えられたレコードxであり、xには同じフィールドに同じtが含まれていますか？複数のフィールドにわたる複数のトークンの一致の関係はどうですか？

あることを心から疑っていますが、魔法の要素でいっぱいの完全に恣意的なハックよりも、私を近づけるものはありますか？

それを除けば、誰かがこれを行う方法を持っていますか？

トークン頻度ルックアップテーブルなど、データベース内の別のテーブルを維持する必要のない他の提案に特に熱心です。

検索とマッチングの問題があります:

入力

私のデータベースには、何千もの名前があり、その他の一致する特徴もあります。数列の数値データと、この特定の会社を識別するのに役立つ他のテキストの数列です。

見込み顧客には約 500 の会社名があり、それぞれの名前について上記のように追加の特性がまばらに入力されています。

現在のプロセス

以前は、このプロセスは手作業でした。データベースを検索し、私に報告されたものと「似た」名前を見つけて、追加の特徴が一致することを確認することで、クライアントから提供された各名前を一致させようとしました。ただし、主な問題は、報告された名前が同じではなく、多くの場合、略語が含まれているか、データベースに保存されている名前の一部のみが含まれている可能性があり、追加の特徴も不完全であるか部分的にしか一致しない可能性があることです.

オートメーション

このプロセスは頻繁に発生するため、自動化したいと考えています。最適なソリューションは、顧客リストから 1 つの会社を入力し、その会社が入力した追加の特性を入力し、データベースで上位 5 つの一致を見つけようとすることです。

私は Lucene や Sphinx を使用したことはありませんが、ドキュメント駆動型のようです。これらのライブラリがこの問題に対して機能するようにこれらの入力をフォーマットする方法はありますか、または代わりに機能する他のソフトウェアツールはありますか?

Fellegi-Sunterのオープンソース実装はありますか？

やや高度な質問があるので、できるだけ具体的にしようと思います。

私は、さまざまなデータ セットを同じエンティティ (通常は会社または金融証券) を参照するヘッダー情報と組み合わせることを含む多くの調査を行っています。このレコードのリンクには、通常、名前が唯一の共通の主要な識別子であるヘッダー情報が含まれますが、いくつかの二次情報 (市と州、操作の日付、相対的なサイズなど) がしばしば利用可能です。これらの一致は通常 1 対多ですが、1 対 1 または多対多の場合もあります。私は通常、手動で、またはクリーンな部分文字列の非常に基本的なテキスト比較を使用して、このマッチングを行ってきました。レーベンシュタイン距離測定のような単純なマッチング アルゴリズムをときどき使用しましたが、それを適用する適切な正式な方法がなかったため、あまり活用できませんでした。

私の推測では、これはかなり一般的な質問であり、この種のことを行うために開発された形式化されたプロセスがいくつかあるに違いありません。与えられたアプローチの理論的妥当性を扱った主題に関する学術論文をいくつか読んだことがありますが、レシピや少なくとも実用的なフレームワークを説明する良い情報源は見つかりませんでした。

私の質問は次のとおりです。

• 本やウェブサイト、出版された記事や研究論文など、多次元ファジーレコードマッチングを実装するための良い情報源を知っている人はいますか?

• 私は、実用的な例と明確に定義されたアプローチを備えたものを好む.

• このアプローチは反復的であり、中間段階で人間が改善をチェックします。

• (編集) リンクされたデータは統計分析に使用されます。そのため、多少のノイズは問題ありませんが、「正しくない一致」が少ないことよりも「正しくない一致」が少ないことを強く好む傾向があります。

• それらが Python にあれば素晴らしいことですが、必須ではありません。

最後にもう 1 つ重要な点として、私は計算効率についてはあまり気にしていません。私はこれを動的に実装していません。通常、数千のレコードを扱っています。

MS SQL Server と互換性のある重複除外ソフトウェアを探しています。私は、世界中の住所がすべての異なる言語で含まれているかなり大規模で乱雑なテーブルを持っています。テーブルは重複を親/子レコードとして処理するように設定されているため、一致を処理する機能が必要です (つまり、重複を削除するだけではありません)。

編集：これが構造です

はMasterIDレコードごとに一意です。

ParentIDMasterID各エントリの親レコードの が含まれており、親レコードはMasterID = ParentID.

CountryCode2 文字の ISO 国コードです (電話コードではありません)。

比較的短いテキスト文字列 (住所、名前などの順序) を持つ大規模なデータベース (潜在的に数百万のレコード) があります。

不正確な重複を削除する戦略を探していますが、あいまい一致が最適な方法のようです。私の問題: 多くの記事と SO の質問は、データベース内のすべてのレコードに対して単一の文字列を照合することを扱っています。データベース全体を一度に重複排除しようとしています。

前者は、線形時間の問題になります (ある値を他の 100 万の値と比較し、毎回何らかの類似度を計算します)。後者は指数時間の問題です (すべてのレコードの値を他のすべてのレコードの値と比較します。100 万レコードの場合、前者のオプションの 1,000,000 回の計算に対して、約 5 x 10^11 回の計算になります)。

私が言及した「ブルートフォース」方法以外のアプローチがあるかどうか疑問に思っています。各レコードの値を比較するための文字列を生成し、類似度がほぼ等しい文字列をグループ化し、これらのグループに対して総当り法を実行することを考えていました。線形時間は達成できませんが、役立つかもしれません。また、これを適切に考えていれば、文字列 A と B の間の潜在的なあいまい一致を見逃す可能性があります。文字列 C (生成されたチェック文字列) との類似性は、互いに非常に類似しているにもかかわらず、非常に異なるためです。

何か案は？

PS私は、時間の複雑さに対して間違った用語を使用した可能性があることを認識しています-それは私が基本的に理解している概念ですが、その場でアルゴリズムを適切なカテゴリにドロップできるほど十分ではありません. 用語を間違って使用した場合は、修正を歓迎しますが、少なくとも私の主張を理解していただければ幸いです.

編集

一部のコメンターは、レコード間のあいまい一致を考慮して、どのレコードを削除するかを選択するための私の戦略は何であるかを尋ねました (つまり、「foo」、「boo」、および「coo」が与えられた場合、重複としてマークされ、削除されます)。ここで自動削除を探しているわけではないことに注意してください。アイデアは、人間によるレビューと評価の目的で、6,000 万以上のレコード データベースで潜在的な重複にフラグを立てることです。おおまかに予測可能/一貫した量である限り、誤検知があっても問題ありません。重複がどの程度蔓延しているかを把握する必要があるだけです。しかし、ファジー マッチング パススルーの実行に 1 か月かかる場合、そもそもこれはオプションではありません。

ここで私が間違っていることを誰かに教えてもらえますか？おもちゃのデータセットでRパッケージのRecordLinkageの比較機能をテストしようとしています

レコード1と3は明らかに一致していますが、is_matchは3つのペアすべてでNAです。

私の部門は、データマイニング/企業ダッシュボードで使用するために、企業内のさまざまなソースからのデータの収集と表示を処理します。

私たちが抱える大きな課題の1つは、さまざまな部門間で場所の名前を相互参照することです。私たちはかなり大規模な組織であり、さまざまな関心を持つ部門が1つの場所について独自のレポートを作成します。一般に、場所の名前がこれらの部門全体のレポートで持つ正確な名前には、多くの不一致があります。たとえば、場所は次のように呼ばれる場合があります。

• 素晴らしいレストラン
• 素晴らしいレストラン
• 素晴らしいF＆B
• 場所がいくつかの改修を経るとき...素晴らしいカフェ '
• またはProfitCenter12345ABC

だから私の質問は、私たち自身のデータベースとコードでこれらの名前を調整する際にどのようなベストプラクティスが存在するのかということです。今のところ、私の部門には、共通の階層標準（最適なソリューション）の下で組織を統合する機能がないと仮定しましょう。現在のところ、私たちの慣習は、場所名の増え続ける参照テーブルを維持することです。これらの参照テーブルは、その後、独自の命名基準に参照されます。これにより、データとの履歴の一貫性を維持できます。

場所を相互参照するときに、ある種の「あいまい検索」を実装することは実行可能/推奨されますか？たとえば、「the」などの単語のインスタンスを無視したり、「cafe」と「restaurant」を同等に扱ったりするもの（事前に定義されたロジックに基づく）。

私は確かに、私たちが遭遇するランダムな命名規則のすべてをアルゴリズムで説明できるとは思いませんが、それらの一部/ほとんどを説明できるのに十分ですか？

以下のことを行うJava製品を提案してください（私はオープンソースを好むでしょう）：

1. データ重複排除
2. 重複排除スコアリング
3. 重複排除ルールとスコアリング ルールをカスタマイズできます。

例を見てください：

1. 「INPUT_DB」という名前の入力ステージング データベースがあります。
2. 「INPUT_PERSONS」という名前のテーブルがあります

3. このテーブルにはいくつかのフィールドがあります。

   ID (無意味な代理主キー)
   FIRST_NAME
   LAST_NAME
   SECOND_NAME
   BIRTH_DATE
   PASSPORT_SERIES (PASSPORT_SERIES + PASSPORT_NUM は市民の一意の識別子)
   PASSPORT_NUM

INPUT_PERSONS のすべてのレコードを調べて、重複と一致を見つける必要があります。いくつかのルールを作成する必要があります。

1. PASSPORT_SERIES+PASSPORT_NUM が何らかのレコードに等しい場合、これら 2 つのレコードが重複していることを意味します。このような状況のスコアは 100 点満点中 100 点です
2. FIRST_NAME と LAST_NAME が等しいが、PASSPORT_SERIES+PASSPORT_NUM に 1 つの異なる文字がある場合 (たとえば、ミスプリント)、これらのレコードは重複している可能性があり、それらのスコアは 100 点中 90 点です。
3. 等々....

すぐに使えるソリューションを見つけて、それをベースとして使用することは可能ですか?