3

私は、多数の単語セットを比較することを含む問題を解決しようとしています。各セットには、一連の単語 (合計約 600 +、非常に高い次元!) からの多数の順序付けられた単語が含まれており、類似性があり、それらをクラスター化して明確なグループ分け。ソリューションは、可能な限り監視されていない必要があります。

データは次のようになります

[りんご、バナナ、オレンジ…]
[りんご、バナナ、ぶどう…]
[ゼリー、アニス、オレンジ…]
[いちご、バナナ、オレンジ…]
...etc

各セットの単語の順序が重要です ([Apple, Banana, Orange] は [Apple, Orange, Banana] とは異なります)

私がこれまでに使用してきたアプローチは、Python スクリプトで計算されるメトリックとしてレーベンシュタイン距離 (距離のしきい値によって制限される) を使用し、各単語を一意の識別子として、距離から類似度マトリックスを生成し、そのマトリックスをグループ化のための KNIME の k-Mediods。

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

  • レーベンシュタインは、この問題に使用する最も適切な距離計量ですか?
  • 平均/medoid プロトタイプ クラスタリングは、グループ化を行うための最良の方法ですか?
  • クラスタリングで「k」の選択を検証することについては、まだあまり考えていません。クラスタリングの SSE 曲線を評価することは、これを行うための最良の方法でしょうか?
  • 私の方法論に欠陥はありますか？
  • 将来のソリューションの拡張として、トレーニング データが与えられた場合、クラスター割り当てに確率を割り当てる方法について考えている人はいますか? たとえば、セット 1 がクラスター 1 に含まれる確率は 80% です。

私の質問があまりにもばかげているように見えたり、答えが痛々しいほど明白に見えたりしないことを願っています.私はデータマイニングに比較的慣れていません.

ありがとう！

4

2 に答える 2

3

はい、レーベンシュタインはこれを行うのに非常に適した方法です。しかし、シーケンスのサイズが大きく異なる場合は、これらの距離をシーケンスの長さの合計で割って正規化する方がよい場合があります。そうしないと、「平均距離」(対応する長さ k の部分文字列間の平均距離の意味は、いくつかの小さな k) に対して一定です。

例: ペア([Apple, Banana], [Carrot, Banana])は、2 番目の項目ごとに両方で一致するため、同じ「平均」距離を持つと言えます([Apple, Banana, Widget, Xylophone], [Carrot, Banana, Yam, Xylophone])が、後者のペアの生のレーベンシュタイン距離は 2 倍になります。

また、レーベンシュタインは「ブロック移動」を特別に考慮していないことに注意してください。文字列を取得し、その部分文字列の 1 つを十分に遠くに移動すると、結果のペア (元の文字列と変更された文字列) は同じレーベンシュタイン スコアになります。部分文字列が移動された位置で、2 番目の文字列が完全に異なる要素を持っているかのように。これを考慮に入れたい場合は、代わりに圧縮ベースの距離を使用することを検討してください。（順序に関係なく距離を計算するのに役立つと言っていますが、もちろん、無秩序な類似性よりも順序付けられた類似性を優先します。）

于 2010-12-02T07:05:06.920 に答える
0

タスクに最適なものを評価する手段として使用できるさまざまなメトリックをサポートするプラットフォームについては、sourceforge の SimMetrics を確認してください。

商業的に有効なバージョンについては、K-Now.co.uk の K-Similarity をチェックしてください。

于 2010-12-01T23:19:51.650 に答える