11

SQL Server 2008にPersonsテーブルがあります。

私の目標は、ほとんど同じ住所を持つ人を見つけることです。

state、town、 、 、 street、 、 、 、 、 、 、house、apartment、postcodeでアドレスを記述しますphone。

一部の州 (米国以外) や人的要因 (住所の間違いなど) での特定の違いにより、住所は同じパターンで入力されません。

よくある住所の間違い

  1. 大文字と小文字の区別
  2. 誰かが「apt.」、別の「アパート」または「ap」と書きました。（住所は英語で書かれていませんが）
  3. スペース、ドット、カンマ
  4. 通りの名前の書き方の違い。ジョーンズ ストリート」または「ドクター ジョーンズ ストリート」または「D. ジョン。st." または "Dr Jones st" など。

主な問題は、データが同じパターンではないため、類似した住所を見つけるのが非常に難しいことです。

この種の問題に対するアルゴリズムはありますか?

前もって感謝します。

アップデート

  1. 前述したように、住所はさまざまな列に分かれています。列を連結する文字列を生成するか、列ごとに手順を実行する必要がありますか? 列を連結するべきではないと思いますが、列を個別に比較する場合、どのように整理すればよいでしょうか? 各列の類似点を見つけたり、それらを結合したり、交差させたりする必要がありますか?
  2. 統計収集または何らかの教育アルゴリズムが必要ですか?
4

15 に答える 15

7

このようにそれに近づくことを提案します：

  1. さまざまなエントリから単語レベルのnグラム（トリグラム/ 4グラムで可能）を作成します

  2. 文字列の比較のためにmanyxmanyの比較を行い、文字列の距離でそれらをクラスター化します。誰かがレーベンシュタインを提案しました。この種のタスクにはより良いものがあり、Jaro-WinklerDistanceとSmith-Watermanの方がうまく機能します。SimMetricsなどのライブラリは、生活をはるかに楽にします

  3. n-gramのクラスターができたら、構成サブグラムを使用して文字列全体を解決できます。つまり、D.Jones St => Davy Jones St. =>DJonesStです。

それほど難しいことではありませんが、これは非常に一般的な問題です。

更新：上記の更新に基づいて、推奨される手順は次のとおりです

  1. 列を単一の文字列に連結し、おそらくdb"view"を作成します。例えば、

    ビューvwAddressをselecttop10000州の町、通り、家、アパート、郵便番号、州+町+通り+家+アパート+郵便番号として作成します。

  2. 別のアプリケーション（JavaまたはC＃/ VB.NETなど）を作成し、JaroWinklerなどのアルゴリズムを使用して、結合されたアドレスの文字列距離を推定し、多×多の比較を作成します。別のテーブルに書き込みますaddress1| アドレスn| 類似性

Simmetricsを使用して、類似性を取得できます。

 JaroWinnkler objJw = new JaroWinkler()
double sim =  objJw.GetSimilarity (address1, addres n);

  1. 「1JonesStreet、Sometown、SomeCountry」などのアドレスが「1Jones Street」、「Jones Street Sometown」などになるようにトリグラムして、トリグラムを比較することもできます。（または4グラム）より高い精度。

  2. 最後に、類似度順に並べ替えて、最も類似したアドレスのクラスターを取得し、適切なしきい値を決定できます。なぜ立ち往生しているのかわからない

于 2010-07-08T09:41:12.223 に答える
5

私は次のことをしようとします：

  • 住所を複数の単語に分割し、同時に句読点を取り除く
  • すべての単語をチェックして、一般的に異なる形で書かれているパターンを探し、それらを一般的な名前に置き換えます (たとえば、apartment、ap.、... を apt に置き換え、Doctor を Dr. に置き換えます)。
  • すべての単語をアルファベット順に並べ替えて 1 つの文字列に戻す
  • あいまい文字列比較アルゴリズムを使用してすべてのアドレスを比較します。たとえば、Levenshtein です。
  • レーベンシュタイン アルゴリズムのパラメーターを微調整します (たとえば、長い文字列でより多くの違いを許容したい場合など)。
  • 最後に、文字列の手動チェックを行います

もちろん、データを「適切な状態」に保つための解決策は、データベースに各特性の明示的なフィールドを用意することです。そうしないと、数か月ごとにこの演習を行うことになります。

于 2010-07-08T08:08:53.567 に答える
2

私は前世紀にこのようなプロジェクトを行いました。基本的に、それは合併後の 2 つの顧客ファイルの統合であり、3 つの異なる情報源からの名前と住所が含まれていました。

まず、多くの投稿者が示唆しているように、すべての一般的な単語、略語、およびスペルミスを一般的な形式「Apt」に変換します。「Apatment」などを「Apt」に。

次に、名前に目を通し、名の最初の文字と名字を特定します。（「Dr. Med. Sir Henry de Baskerville Smythe」を考えると簡単ではありません）しかし、あいまいさがある場合は心配しないでください。運が良ければ、HBASKERVILLE と HSMYTHE を手に入れることができます。ここで、ほとんどのスペルのバリエーションが発生する母音をすべて削除して、HBSKRVLL HSMTH を作成します。

これらの文字列は、「H. Baskerville」、「Sir Henry Baskerville Smith」、そして残念ながら「Harold Smith」からも取得できますが、ここではファジー マッチングについて説明しています。

通り、アパート、郵便番号のフィールドで同様の演習を実行します。ただし、元のデータは捨てないでください。

最初に、元の文字列のそれぞれを比較し、正確に一致する文字列ごとに 50 点を与えます。次に、「正規化された」文字列を調べて、正確に一致する文字列ごとに 20 ポイントを与えます。次に、すべての文字列を調べて、共通する 4 文字以上の部分文字列ごとに 5 ポイントを与えます。比較された各ペアについて、特定の一致と見なすことができるスコアが 150 を超えるもの、一致していないと見なすことができるスコアが 50 未満のもの、および一致する可能性がある中間のものがあります。

これを改善するには、「姓が 'smith' の場合は 20 ポイントを引く」などのさまざまなルールを追加して、さらに微調整する必要があります。結果の一致に満足するまで、実際に実行と微調整を続ける必要がありますが、結果を見ると、どのスコアが「一致」と見なされ、どの誤検出を取り除く必要があるかがかなりよくわかります。の。

于 2010-07-08T10:36:13.277 に答える
2

郵便番号フィールドがあります!!!

では、あなたの国の郵便番号表を購入して、それを使って通り/町/地域/州の情報をクリーンアップしてみませんか?

于 2010-07-08T09:47:07.440 に答える
2

ここで私が目にする主な問題は、平等を正確に定義することです。たとえ誰かがジョンと書いたとしても。そしてもう一人のジョン。- それらが同じかどうかは決して言えません。(Jon-Jonethan、Joneson、Jonedoe 何でも;)

私は、まさにこの問題に対処しなければならない会社で働いています。申し訳ありませんが、この種のナビゲーション システムの住所リストのチェックは、ほとんどの場合「手作業」で行われています。略語は文脈に依存する場合があり、これを困難にする他の要因があります。文字列などの置き換えはPythonで行われますが、そのような略語の意味を教えてくれます。場合によっては、スクリプトでのみ実行できます。("St." -> "Saint" と "Street" のどちらでもかまいません。どうやって決めるか? 不可能...これは人間の仕事です。)

もう 1 つの大きな問題は、あなたが言ったように、「DJones という通りがあるのか​​、それとも人がいるのですか? それともその両方ですか? ここにあるのはどちらですか? この DJones は Dr Jones と同じですか、それとも Don Jones と同じですか? 判断するのは不可能です!

ここでの別の回答で示されているように、リストを使用していくつかの作業を行うことができますが、十分な「誤検知」などが得られます。

于 2010-07-08T09:18:11.280 に答える
1

コメントで言及する重要なことの1つは、これをインタラクティブに行うことです。

これにより、ユーザー入力を解析すると同時に、略語の推測を検証し、多くの間違いを修正することができます（たとえば、電話番号の入力が一部の連絡先管理システムで機能する方法-システムは国を解析して修正するために最善を尽くしますコード、市外局番、および番号ですが、最終的にはユーザーに推測が表示され、入力を修正する機会があります）

あなたがそれを本当にうまくやりたいのなら、郵便番号、町、通り、略語とそれらのバリエーションのデータベース/辞書を保持することはデータ検証と前処理を改善することができます。

したがって、少なくとも完全に修飾されたアドレスがあります。すべての入力に対してこれを行うことができれば、すべてのデータが分類され、一致は特定のフィールドでは厳密になり、他のフィールドではそれほど厳密ではなくなり、割り当てた重みに従って一致スコアが計算されます。

入力を一貫して前処理した後、n-gramは同様のアドレスを見つけることができるはずです。

于 2010-07-08T13:07:11.097 に答える
1

データの量は、どのアプローチが最適かを左右する可能性があると思います。さまざまなアーティストのコンピレーション アルバムから音楽をインデックス化するときに
、同様の問題が発生しました。アーティストが最初に来ることもあれば、曲名が最初に来ることもあり、さまざまな区切りスタイルが使用されていました。

私がしたことは、同じ値を持つ他のエントリの出現回数を数えて、それが曲名であるかアーティストであるかを知識に基づいて推測することでした.

おそらく、soundexまたは同様のアルゴリズムを使用して、類似のものを見つけることができます。

編集: (おそらく、アーティスト名は曲名よりも頻繁に繰り返される可能性が高いと仮定したことを明確にする必要があります。)

于 2010-07-08T09:16:57.423 に答える
1

素晴らしい記事を見つけました。

dll をSQL ユーザー定義関数として追加すると、 SimMetricsライブラリを使用して文字列比較アルゴリズムを使用できます。

確認してください

http://anastasiosyal.com/archive/2009/01/11/18.aspx

于 2010-07-14T07:28:11.900 に答える
1

これについて SQL Server Integration Services を見たことがありますか? あいまい検索コンポーネントを使用すると、「ほぼ一致」を見つけることができます: http://msdn.microsoft.com/en-us/library/ms137786.aspx

新しい入力の場合は、.Net コードからパッケージを呼び出して、チェックする値の行をパラメーターのセットとして渡すことができます。ただし、これがユーザーの操作に十分な速さであるためには、おそらくトークン インデックスを永続化する必要があります。

ここにアドレス マッチングの例があります: http://msdn.microsoft.com/en-us/magazine/cc163731.aspx

于 2010-07-13T12:51:30.077 に答える
1

応答時間は重要ではなく、重複をマージするのではなく、データベース内の既存のアドレスを見つけることが問題であると想定しています。また、データベースには大量のアドレス (たとえば 300 万件) が含まれており、手動またはAmazon の Mechanical Turkによって経済的にクリーンアップできる数ではないと想定しています。

事前計算 - 情報量の多いアドレス フラグメントを識別します。

  1. 各データベース フィールドで使用されている一意の単語をすべて特定し、その出現回数を数えます。
  2. 非常に一般的な単語や略語を削除します。(Street、st.、appt、apt など)

入力住所を提示すると、

  1. 最もユニークな単語を特定し、それらの単語を含む既存の住所を検索 (Street LIKE '%Jones%') します。
  2. 事前に計算された統計を使用して、結果セットに含まれるアドレスの数を見積もります
  3. 推定結果セットが大きすぎる場合は、2 番目にユニークな単語を選択し、検索で組み合わせます (Street LIKE '%Jones%' AND Town LIKE '%Anytown%')。
  4. 推定結果セットが小さすぎる場合は、2 番目にユニークな単語を選択し、検索で組み合わせます (Street LIKE '%Aardvark%' OR Town LIKE '%Anytown')。
  5. 実際の結果セットが大きすぎる/小さすぎる場合は、前と同じように用語を追加してクエリを繰り返します。

アイデアは、最も最適な一致を見つけるのではなく、適切な数の選択肢を提供するために検索できる、アドレス内の情報量の多いフラグメントを十分に見つけることです。スペルミスに対する許容度を高めるには、単語の代わりにトライグラム、テトラグラム、またはサウンデックス コードを使用できます。

明らかに、実際の州/町/通りのリストがある場合、データベースと検索アドレスの両方でデータのクリーンアップが行われる可能性があります。(アルメニアの郵便サービスがそのようなリストを公開していないことに非常に驚いていますが、一部の郵便サービスがこの情報に過剰な料金を課していることは知っています。)

実際問題として、私が使用しているほとんどのシステムは、可能であれば電話番号で人々のアカウントを検索しようとします。明らかに、それが実際的な解決策であるかどうかは、データの性質とその正確さに依存します。

(水平思考のアプローチも検討してください。あなたのデータベースをクリーンアップしてくれる通信販売メーリング リスト ブローカー会社を見つけることができますか?彼らは、アドレスの使用に対して喜んでお金を払ってくれるかもしれません.)

于 2010-07-13T21:24:21.950 に答える
0

別のアイデアは、学習を使用することです。たとえば、それぞれの略語とその文中の位置について、その略語が何を意味するかを学習できます。

3 Jane Dr. -> Dr (in 3rd position (or last)) means Drive
Dr. Jones St -> Dr (in 1st position) means Doctor

たとえば、決定木を使用して、ユーザーにシステムをトレーニングさせることができます。おそらく、それぞれの使用例はほとんどないでしょう。D.Jones のような 1 文字の略語を、David Jones や Dr. Jones の可能性があると分類することはありません。しかし、最初のレベルの翻訳の後、町の通りのインデックスを調べて、D. を通りの名前に展開できるかどうかを確認できます。

ここでも、各アドレスを格納する前に決定木を実行します。

これを行う商用製品がいくつかあるはずだと感じています。

于 2010-07-08T09:48:16.607 に答える
0

可能性としては、すべてのバリアントを単語の「適切な」バージョンにマップする辞書テーブルをデータベースに作成することです。

*Value* | *Meaning*
Apt.    | Apartment
Ap.     | Apartment
St.     | Street

次に、比較する前に各単語を辞書に通します。

編集：これだけでは実用的ではありません（コメントを参照）。

于 2010-07-08T09:12:10.333 に答える
0

1 つの方法は、住所フィールドにレーベンシュタイン距離アルゴリズムを適用することです。これにより、文字列の類似性を比較できます。

編集 あなたが扱っている住所の違いの種類を見た後、これは結局役に立たないかもしれません.

于 2010-07-08T09:58:00.380 に答える
0

すべての住所を Google マップなどの Web サービスに投げて (ただし、これが適切かどうかはわかりません)、同じ GPS 座標が表示されるかどうかを確認できます。

于 2010-07-08T09:05:11.427 に答える
0

そのようなバリエーションの可能性は無数にあり、たとえそのようなアルゴリズムが存在したとしても、それは絶対に確実ではありません。結局のところ、名詞のスペル チェッカーを使用することはできません。できることは、以前に入力したフィールド値のドロップダウン リストを提供して、特定の名前が既に存在する場合にいずれかを選択できるようにすることです。アパートなどの値ごとに個別のフィールドを用意することをお勧めします。

于 2010-07-08T07:18:27.087 に答える