7

タグに基づいて多くのフィードをクラスター化しようとしています。典型的な例は、Twitter フィードです。各フィードには、ユーザー定義のタグが関連付けられています。タグを分析することで、フィードをさまざまなグループに分類し、非常に多くのフィードが非常に多くのタグに基づいていることを確認できますか。例は-

  • Feed1 - インドネシアの地震 #earthquake #asia #bad
  • フィード 2 - 私の地域で大規模な地震が発生しました #earthquake #bad
  • Feed3 - 私の両親はシンガポール #アジア #ツアーに行きました
  • Feed4 - XYZ社は多くの人を解雇しています #XYZ #layoff #bear
  • フィード 5 - XYZ が悪化している、レイオフを計画している #XYZ #layoff #bad
  • フィード 6 - XYZ は一時解雇中 #layoff #XYZ #最悪

クラスタリング後

  • #アジア 、 # 地震 - フィード 1 、フィード 2
  • #XYZ , #レイオフ - Feed4 , Feed 5 , Feed6

ここでは、クラスタリングは純粋にタグに基づいています。これを達成するための良いアルゴリズムはありますか

4

2 に答える 2

7

私があなたの質問を正しく理解していれば、タグをまとめてクラスタ化し、フィード内のタグに基づいてこれらのクラスタにフィードを配置したいと考えています。

このために、タグが一緒に表示されるフィードの数に基づいて、タグ間の類似度測定を作成できます。あなたの例では、これは次のようになります

               #earthquake | #asia | #bad | ...
#earthquake        1       |  1/2  |  2/2
#asia             1/2      |   1   |  1/2
#bad              2/3      |  1/3  |   1
...

ここで、値 at (i,j)equals frequency of (i,j)/frequency of (i)。

これで、タグ間の類似性マトリックスが得られ、ニーズに合った実質的に任意のクラスタリング アルゴリズムが可能になりました。タグの数が非常に多くなる可能性があり、アルゴリズムを実行する前にクラスターの数を推定するのは難しいため、非常に高速な Fast Modularity クラスタリングのような階層型クラスタリング アルゴリズムを使用することをお勧めします (詳細はこちらをご覧ください)。ただし、これを分割したいクラスター数の見積もりがある場合は、スペクトル クラスタリングも役立つ可能性があります (詳細については、こちらを参照してください)。

タグをまとめてクラスター化したら、簡単な方法で各フィードをクラスターに割り当てることができます。これは非常に簡単です。たとえば、フィード内の各クラスターからのタグの数をカウントし、一致するタグの最大数を持つクラスターを割り当てます。

クラスタリング戦略に柔軟に対応できる場合は、フィード間の共通タグの数に基づいてフィード間の類似性を作成し、類似性マトリックスにクラスタリング アルゴリズムを適用することで、同様の方法でフィードを一緒にクラスタリングすることもできます。

于 2013-02-14T15:40:37.623 に答える
2

興味深い質問です。私はここで物事を作っていますが、これはうまくいくと思います。

アルゴリズム

フィードごとに、タグの組み合わせ (長さ >= 2) の完全なリストを作成します。おそらく一貫性のために並べ替えられます。例えば：

  • Feed1: (asia-bad)、(asia-earthquake)、(bad-earthquake)、(asia-bad-earthquake)
  • Feed2: (悪い地震)
  • Feed3: (アジアツアー)
  • Feed4: (ベア-レイオフ)、(ベア-XYZ)、(レイオフ-XYZ)、(ベア-レイオフ-XYZ)
  • Feed5: (悪いレイオフ)、(悪い-XYZ)、(レイオフ-XYZ)、(悪いレイオフ-XYZ)
  • Feed6: (一時解雇-最悪)、(一時解雇-XYZ)、(最悪-XYZ)、(一時解雇-最悪-XYZ)

次に、マッピングを逆にします。

  • (アジア悪い): Feed1
  • (アジア地震): Feed1
  • (悪い地震): Feed1、Feed2
  • (アジア悪い地震): Feed1
  • (アジアツアー): Feed3
  • (ベアレイオフ): Feed4
  • ...
  • (レイオフ-XYZ): Feed4、Feed5、Feed6
  • ...

次に、頻度がしきい値よりも高いすべてのエントリを選別できます。この場合、頻度のしきい値を 2 にすると、Feed1 と Feed2 で (bad-earthquake)、Feed4、Feed5 と Feed6 で (layoff-XYZ) になります。

パフォーマンスの問題

これを単純に実装すると、パフォーマンスが非常に低下します。フィードごとのタグ数が指数関数的に増加します (スペース要件は言うまでもありません)。ただし、これを改善するためにヒューリスティックを適用するさまざまな方法があります。例えば：

  1. すべてのフィード (またはランダムに選択された X フィード) をスキャンして、最も人気のある X タグを特定します。これは、フィードごとのタグ数に比例します。次に、各フィードで最も人気のある Y 個のタグのみを検討します。
  2. すべての (またはほとんどの) タグの頻度を決定します。次に、投稿ごとに、その投稿で最も人気のある X 個のタグのみを検討します。これにより、たとえば、ある投稿に 15 個のタグがあり、組み合わせのリストが膨大になり、そのほとんどが発生しないという状況が回避されます。
  3. 各投稿について、長さ <= X の組み合わせのみを考慮してください。たとえば、フィードに 15 個のタグがある場合、膨大な数の組み合わせになる可能性がありますが、それらのほとんどは、特に長いタグの出現が非常に少なくなります。そのため、2 つまたは 3 つのタグの組み合わせのみを検討してください。
  4. X フィードのランダムな選択のみをスキャンします。

お役に立てれば！

于 2013-02-14T15:06:13.850 に答える