string-matching - 製品名のあいまい一致

Question

さまざまなソースからの製品名（カメラ、ラップトップ、テレビなど）をデータベース内の正規名に自動的に一致させる必要があります。

たとえば、「Canon PowerShot a20IS」、「NEW powershot A20 IS from Canon」、「Digital Camera Canon PS A20IS」 は、すべて「CanonPowerShotA20IS」と一致する必要があります。私はいくつかのヒューリスティックを追加してレーベンシュタイン距離で作業しました（明白な一般的な単語を削除し、番号の変更により高いコストを割り当てるなど）。これはある程度機能しますが、残念ながら十分ではありません。

主な問題は、関連するキーワードを1文字だけ変更しても大きな違いが生じる可能性があることですが、関連するキーワードを特定するのは簡単ではありません。たとえば、次の3つの製品名を考えてみましょう
。LenovoT400
Lenovo R400
New Lenovo T-400、Core 2 Duo
最初の2つは、どの規格でもばかばかしいほど似た文字列です（この場合、soundexはTとRを区別するのに役立つかもしれませんが、名前は400Tと400Rも同様です）、1番目と3番目はストリングとして互いにかなり離れていますが、同じ製品です。

明らかに、マッチングアルゴリズムを100％正確にすることはできません。私の目標は、名前の約80％を高い信頼性で自動的にマッチングすることです。

任意のアイデアや参考文献は大歓迎です

score 6 · Accepted Answer

これは、 LenovoなどのキーワードとNewなどのチャフを区別することに要約されると思います。

名前のデータベースを分析して、キーワードを特定します。ワードクラウドの生成に使用されるものと同様のコードを使用できます。

次に、リストを手作業で編集して、明らかに面倒なものを削除します。たとえば、New は実際には一般的ですが、キーではありません。

次に、類似点を識別するのに役立つキーワードのリストが表示されます。「未加工」の名前をそのキーワードに関連付け、2 つ以上の未加工の名前を比較して類似性 (文字通り、共有キーワードのパーセンテージ) を調べるときに、それらのキーワードを使用します。

決して完璧な解決策ではありませんが、期待しているとは思いませんか?

score 5 · Accepted Answer

ここで重要なことは、適切な距離メトリックがあるということです。それは実際にはあなたの問題ではありません。あなたの問題は分類にあります。

例を挙げましょう。Foo X1 に 20 個、Foo Y1 に 20 個のエントリがあるとします。2 つのグループであると安全に想定できます。一方、バー X1 に 39 エントリ、バー Y1 に 1 つのエントリがある場合は、それらを 1 つのグループとして扱う必要があります。

さて、距離 X1 <-> Y1 は両方の例で同じですが、なぜ分類に違いがあるのでしょうか? これは、Bar Y1 が外れ値であるのに対し、Foo Y1 はそうではないためです。

おもしろいのは、これらのグループを事前に決定するために実際に多くの作業を行う必要がないことです。再帰的な分類を行うだけです。グループごとのノードから始めて、最も近い 2 つのノードにスーパーノードを追加します。スーパーノードに、最良の仮定、そのサブツリーのサイズ、およびそのバリエーションを保存します。多くの文字列が同一であるため、すぐに同一のエントリを持つ大きなサブツリーが得られます。再帰は、ツリーのルートに含まれるスーパーノードで終了します。

次に、このツリーに対して正規名をマップします。それぞれがサブツリー全体に一致することがすぐにわかります。次に、これらの木の間の距離を使用して、そのエントリの距離カットオフを選択します。データベースに Foo X1 と Foo Y1 の両方の製品がある場合は、それを反映するためにカットオフ距離を小さくする必要があります。

score 3 · Accepted Answer

edgの答えは正しい方向にあると思います.キーワードと綿毛を区別する必要があります.

コンテキストが重要です。あなたの例を挙げると、T400 の 2 つのインスタンスを見ると、Core 2 Duo は綿毛ですが、CPU OEM パッケージを見るとそうではありません。

製品名の正規形のどの部分がより重要であり、製品を識別するために何らかの形で表示する必要があるかをデータベースでマークできる場合は、そうする必要があります。ある種のセマンティックマークアップを使用することでしょうか？人間がデータベースをマークアップする余裕はありますか?

「T-400」、「T400」、「T 400」などの等価クラスを定義することができます。おそらく、「数字は、それらの数字に付けられた文字よりも強く結合する」という一連のルールです。

メーカーや型番などでケース分けしてみるのもいいかもしれません。タームスポッティングのテクニックを見て、それを達成することをお勧めします: http://www.worldcat.org/isbn/9780262100854

ほとんどがルール駆動型の柔軟なフレームワークですべてを設計し、ニーズに基づいてルールを変更したり、悪いパターン (アルゴリズムを壊すもの) が出現したりすることも良い考えです。このようにして、実際のデータに基づいてシステムのパフォーマンスを向上させることができます。

score 2 · Accepted Answer

あなたはこれのためにトライグラム検索を利用することができるかもしれません。インデックスを実装するアルゴリズムを見たことがないことを認めなければなりませんが、それが製薬アプリケーションで機能しているのを見たことがあります。この問題に同じ種類のロジックを適用できる場合があります。

score 1 · Accepted Answer

レコード連携の問題です。dedupe python ライブラリは完全な実装を提供しますが、python を使用しない場合でも、ドキュメントにはこの問題へのアプローチ方法の概要が記載されています。

簡単に言うと、標準的なパラダイムでは、このタスクは 3 つの段階に分けられます

フィールドを比較します。この場合は名前だけです。これには、1 つ以上のコンパレータを使用できます。たとえば、レーベンシュタイン距離のような編集距離や、一般的な単語の数を比較するコサイン距離のようなものです。
距離スコアの配列を、レコードのペアが本当にほぼ同じである確率に変換します
それらのペアごとの確率スコアを、すべて同じものを参照している可能性が高いレコードのグループにクラスター化します。

score 0 · Accepted Answer

モデル番号の文字と数字の組み合わせを無視するロジックを作成することをお勧めします（モデル番号は常に非常に類似しているため）。

score 0 · Accepted Answer

この種の問題の経験はありませんが、非常に単純な実装は、検索語をトークン化し、トークンのいずれかを含む一致を検索することだと思います。

たとえば、「Canon PowerShot A20 IS」は次のようにトークン化されます。

キヤノン
パワーショット
A20
は

これは、結果に表示したい他の各項目と一致します。もちろん、この戦略では、多くの誤った一致も生成される可能性があります。

また、「カメラ」「キャノン」「デジカメ」など、商品ごとに「キーワード」を付けて、キーワードが一致する商品を検索する方法もあります。さらに、Maker、Brand などの他の属性を保存した場合は、これらのそれぞれで検索できます。

score 0 · Accepted Answer

スペルチェックアルゴリズムが思い浮かびます。

適切な実装例は見つかりませんでしたが、基本的なスペルチェックアルゴリズムを変更して、満足のいく結果が得られると信じています。つまり、単語を文字ではなく単位として扱います。

私の記憶に残った断片：

すべての一般的な単語 (a、an、the、new) を取り除きます。「一般的」とは文脈によって異なります。
各単語の最初の文字とその長さを取得し、それを単語キーにします。
疑わしい単語が出てくると、同じまたは類似の単語キーを持つ単語を探します。

問題を直接解決することはできないかもしれませんが、アイデアを探していたということですね。

:-)

score 0 · Accepted Answer

それはまさに私が暇なときに取り組んでいる問題です。私が思いついたのは、キーワードに基づいて検索範囲を絞り込むことです。

この場合、いくつかの階層を持つことができます:

タイプ --> 会社 --> モデル

タイプとして「デジタルカメラ」と一致するように

会社の「Canon」では、検索する範囲がはるかに狭くなります。

製品ラインなどを導入することで、これをさらに掘り下げることができます。しかし、要点は、これはおそらく繰り返し行う必要があるということです。

score 0 · Accepted Answer

製品の照合にはDatadecision サービスを使用できます。

統計アルゴリズムを使用して、製品データを自動的に一致させることができます。この操作は、信頼度のしきい値スコアを定義した後に実行されます。

自動的に一致させることができないすべてのデータは、専用のユーザーインターフェイスを介して手動で確認する必要があります。

オンラインサービスでは、ルックアップテーブルを使用して類義語と手動照合履歴を保存します。これにより、次に新しいデータをインポートする際のデータマッチングの自動化を改善できます。

score 0 · Accepted Answer

私は過去にまったく同じことをしました。私が行ったことは、NLP メソッドを使用することです。各単語に重みを割り当てる TF-IDF Vectorizer。たとえば、あなたの場合：

Canon PowerShot a20IS

Canon --> weight = 0.05 (あまり区別のつかない単語)
PowerShot --> 重み = 0.37 (区別可能)
a20IS --> 重み = 0.96 (非常に特徴的)

これにより、どの単語を気にし、どの単語を気にしないかをモデルに伝えます。TF-IDFのおかげでかなりいい試合ができました。ただし、これに注意してください: a20IS は a20 IS として認識されません。そのような場合をフィルタリングするために、ある種の正規表現を使用することを検討してください。

その後、コサイン類似度などの数値計算を使用できます。

string-matching - 製品名のあいまい一致

11 に答える 11

Related

Reference