7

レベンスタイン距離アルゴリズムに問題があります。

レーベンスタイン距離アルゴリズムを使用して、製品名を製品名のリストと比較し、最も近いものを見つけています。ただし、少し微調整する必要があります。dotnetperls.comの例を使用しています。

私自身のデータベースから 2000 個の製品名のリスト A があるとします。私はこれらすべての製品を自分で販売しています。

それから突然、サプライヤーの 1 人から、製品名と各製品の新しい価格が記載されたリスト B を受け取りました。これは年に 1 回以上発生する可能性があるため、手動で作業を行うソフトウェアを開発したいと考えています。

問題は、このサプライヤーは一貫性があまり得意ではないということです。そのため、彼は時々名前に小さな変更を加えます。つまり、単純な文字列比較を行うことができません。

距離アルゴリズムを実装しましたが、私のニーズにはあまり合いません。- まだ！

サプライヤーリストを調べているときに、という製品に出くわしました

アメリカン クルー アンチ フケ シャンプー 250 ml

この製品は、私自身の製品とのマッチングに成功しました

アメリカン クルー アンチ フケ 250 ml。

10の距離で。

問題

という商品も見つけました。

アメリカン クルー 3-In-1 シャンプー 450 ml。

誤って一致したもの

アメリカン クルー デイリー シャンプー 450ml

私の代わりに

アメリカン クルー 3 イン 1 450 ml。

そして、その理由がわかります！しかし、ここからアルゴリズムをどのように変更すればよいかわかりません。

何か案は？

ところで、私はアルゴリズムがあまり得意ではありませんが、何らかの重み付けがここで役立つと信じています。

編集：

計算時間は実際には問題ではありません。完了するのに 10 時間かかったとしても、手動で行うよりもはるかに優れています :P

4

4 に答える 4

3

1 つのアプローチは、複数の方法を使用して検索し、それぞれに重みを適用することです。Item少なくとも文字列Nameプロパティを持つクラスがあると仮定しました。

double levWeight = 1.0;   // adjust these weights as you see fit
double matchWeight = 1.0;

// add whatever to here you'd like
var splitOn = new[] { ' ', '!', '"', '#', '$', '%', '&', '\'', '(', ')', '-' };
Func<string, string[]> split = 
    s => s.Split(splitOn, StringSplitOptions.RemoveEmptyEntries);

var matches =
    from xx in mine
    let xp = split(xx.Name)
    select new {
        Item = xx,
        Matches =
           (from yy in theirs
            let yp = split(yy.Name)

            /* found how many name components match */
            let mm = xp.Intersect(yp, StringComparer.OrdinalIgnoreCase).Count()

            /* find the Levenshtein distance of the two names */
            let ld = LevDist(xx, yy)

            /* weight our two criteria */
            let ww = (matchWeight * mm) + (levWeight / ld)

            /* should match on at least ONE name component */
            where mm > 0
            orderby ww descending
            select yy)
    };

あなたが持っているデータのコーパスに対して実行すると、次の出力が表示されます。

  • アメリカン クルー アンチ フケ シャンプー 250 ml
    1. アメリカン クルー アンチ フケ 250 ml
    2. アメリカン クルー デイリー シャンプー 450 ml
    3. アメリカン クルー 3 イン 1 450 ml
  • アメリカン クルー 3 イン 1 シャンプー 450 ml
    1. アメリカン クルー 3 イン 1 450 ml
    2. アメリカン クルー デイリー シャンプー 450 ml
    3. アメリカン クルー アンチ フケ 250 ml

より多くの基準がある場合は、単純にそれらをクエリに追加し (他のlet句とインラインで)、その結果に重みを適用します。

他の可能なアプリケーションは、「同じ順序でコンポーネントに名前を付ける」です。

let or = xp.Zip(yp, (a,b) => String.Compare(a, b, true))
           .TakeWhile(c => c == 0)
           .Count()
于 2012-11-01T14:59:40.397 に答える
1

レーベンシュタインを、-、スペース、ドットを含まない 2 番目のパスと、正確に類似した単語をカウントする 3 番目のパス、および製品名の最初の異なる単語に基づく 4 番目のパスと組み合わせることができますか?

神経回路網を見てもらえますか？トレーニング データベースの作成には長い時間がかかりますが、それも答え (または答えの一部) になる可能性があります。

于 2012-11-01T14:11:03.080 に答える
1

データに関する外部の知識の一部を挿入する必要があります。たとえば、あなたが示した場合、「シャンプー」という言葉は製品についての情報を提供するものではありません (つまり、2 つの製品が類似しているかどうかに関する有用な情報を追加するものではありません)。データから「シャンプー」という単語を削除していれば、この方法は機能していたはずです。

したがって、できることの 1 つは、非常に頻繁に使用される (多くの単語に現れる) 単語をコンピューターで検索し、データから削除することです。次に、アルゴリズムを実行します。

2 番目の小さな調整は、文字「-」に関する知識を使用することです。この文字は、空白文字 ' ' に似ていると見なすことができます。したがって、アルゴリズムを実行する前に、「-」を「 」に置き換えてください。

この方法では、アルゴリズムを変更する必要はありませんが、問題に関する知識を引き続き使用できます (アルゴリズムの変更を避けたいと考えていることは理解しています)。

最後に、レーベンシュタイン距離を使用しない、または単語全体を比較するなど、より抜本的な変更を検討することをお勧めします。データセットは表示されませんが、現在使用している形式のレーベンスタイン距離は、文字数が少ない場合 (タイプミスなど) に最適です。

于 2012-11-01T15:10:22.637 に答える
0

アルゴリズムは一致ではなく、距離を示します。したがって、問題のシナリオでは、2 つの異なる文から得られる距離を比較する必要があります。距離が最も短い方が優れていますが、それでも特定の一致はありません。最良の解決策は、アルゴリズムに基づいて一致すると思われるさまざまな製品名をユーザーに提示することだと思います。その後、ユーザーは最終的な選択を行うことができます。しかし、たまにミスマッチを気にしないのであれば、正しい道を歩んでいます。まだ一致していると見なす距離の数値を選択するだけですが、これにより多くの誤検知が発生します.

于 2012-11-01T14:19:29.407 に答える