1

名前に基づいて、いくつかのホテルを同じカテゴリにグループ化する必要があります。グループ化にレーベンシュタインを使用していますが、どれだけ試しても、本来あるべきカテゴリから外れたり、別のカテゴリになっているホテルがあります。

例: これらのホテルはすべて同じカテゴリに属している必要があります。

=============================

ベストウェスタン ベルシー リヴ ゴーシュ

ベストウェスタン コリーゼ

ベストウェスタン デュック ド ブルゴーニュ

ベストウェスタン フォークストーン オペラ

ベストウェスタン フランス ヨーロッパ

ベストウェスタン ホテル シドニー オペラ

ベストウェスタン パリ ルーヴル オペラ

ベストウェスタン ホテル ドゥ ヌーヴィル

=============================

すべてのホテル名（1000行など）のリストがあります。また、それらをグループ化する方法もあります。レーベンシュタインを最適化して、私の状況により柔軟にする方法はありますか?

$inserted = false;
foreach($hotelList as $key => $value){
    if (levenshtein($key, $hotelName, 2, 5, 1) <= abs(strlen($key) - strlen($hotelName))){
        array_push($hotelList[$key], trim($line));
        $inserted = true;
    }
}
// if no match was found add another entry
if (!$inserted){
    $hotelList[$hotelName] = array(
            trim($line)
        );
}
4

3 に答える 3

2

思いを込めて入っていきます。まず、このようなデータのグループ化または「クラスタリング」は非常に大きなトピックです。具体的には触れませんが、おそらく物事を理想的な方向に向けることができます。

比較された文字列の長さでレーベンシュタインを正規化することで素晴らしいことを行いました-多くの場合、文字列の長さが類似性を過剰に決定するという問題を回避するため、これはまさに正しいことです。

しかし、アルゴリズムは問題を解決しませんでした。まず、単語を比較します。「Bent Eastern French Hotels」は「Best Western French Hotels」とは明らかに大きく異なりますが、「Best Western Paris Bed and Breakfasts」よりもスコアが高くなります。ここで理解しておくべきことは、トークンは文字ではなく単語であるべきだということです。

私は@sauryの答えが好きですが、最初の仮定についてはよくわかりません。代わりに、「 bag of words 」と呼ばれることが多い、素晴らしく簡単なものから始めましょう。次に、最も使用頻度の低い単語に最も多くの情報が含まれているという直感に基づいて、キー フレーズを識別できるハッシュトリックを実装します。

ホテルのブランド名が先頭に近いという考えに同意する場合は、文字列の先頭に近いかどうかを常に歪めることができます. つまり、あなたのグループは、「最高」/「西洋」と同じくらい「フランス」になる可能性があります (ただし、「ホテル」ではありません-なぜですか?)。

結果をより正確にしたいですか？

ここからは、いくつかの本格的なアルゴリズムにステップアップする必要があります。多くのスタック オーバーフローのトピックをサーフィンして楽しんでください。私の直感では、多くのホテル名はまったくブランド化されていないので、それらについても別のカテゴリが必要になるでしょう。また、私の本能は、ホテル名で繰り返される単語の数が比較的少なくなるということでもあります。一部の単語は、ホテル名のメンバーとして頻繁に使用されます。これらの事実は、上記の問題になります。この場合、k-means と呼ばれる非常に人気のある (SO で決まり文句である場合) 手法があります。これは、選択したnキーフレーズをnクラスターの次元、次にクラスターの中心点の大部分のコンポーネントを分類タグとして取得します。(たとえば、"France" のヒットは n 次元空間全体にかなり均等に分散されるため、"France" は削除されます)。

これはおそらく小さな問題のように思えるかもしれませんが、データが構造化されていない場合、物事を適切に行うための近道はないことを強調したいと思います。

于 2013-07-04T10:38:11.233 に答える
0

一般的なhttp://en.wikipedia.org/wiki/K-means_clusteringとhttp://en.wikipedia.org/wiki/Cluster_analysisについて読むことをお勧めします。

于 2013-07-04T10:52:32.890 に答える
0

同じグループの一部として扱われる単語間のデルタとして、どのレーベンシュタイン距離値を取りますか? 最初のいくつかの単語に基づいてホテルをグループ化する傾向があり、それにはまったく異なるアプローチが必要になるようです (辞書の並べ替えを行う、現在の文字列を次の文字列と比較するなど)。ただし、ユースケースで依然としてレーベンシュタイン距離を計算する必要がある場合は、文字列の長さに基づいて文字列を並べ替えてから、各文字列を同様の長さの他の文字列と比較することをお勧めします (「類似」と見なすものに独自のヒューリスティックを適用します)あなたが言うように isSimilar = Math.abs(str1.length - str2.length) < SOME_LOWEST_DELTA_VALUE またはそのようなもの)

于 2013-07-04T09:56:31.950 に答える