14

メールをスレッド化する場合は、JamieZawinskiのアルゴリズムを使用します。しかし、それは新しい世紀であり、新しいメッセージングサービスがあります。

Twitterに投稿されたステータスの更新をスレッド化するための最良のアルゴリズムは何ですか?

私が絶対に対処したいこと:

  • 簡単な部分:、、およびを使用in_reply_to_status_idin_reply_to_user_idますin_reply_to_screen_name。(ちなみに、これらの値の適切なドキュメントを見つけること自体が役立ちます!このようなドキュメントは、たとえば、ここから明らかにリンクされていません 。)

  • @規則でユーザーに言及しているが、特定のメッセージに明示的に応答していないメッセージから「応答」関係を推測するための優れたヒューリスティック。これらの「メンション」は、 リクエストした場合、ステータスの「エンティティ」要素で提供されるようになりました。これらのヒューリスティックは、(a)2つのステータス更新間の時間、(b)2人のユーザー間に後続の返信があるかどうかなどを考慮に入れる場合があります(user85509が言及した、古いスタイルのリツイートと追加のコメントで構成される返信以下 は、このスタイルの返信のほんの一例です。)

  • 3人以上のユーザー間で行われる会話。

  • アルゴリズムに与えられた一連のツイート、またはTwitterのすべてのツイートを操作します。

...しかし、おそらくあなたはもっと考えることができます。

4

2 に答える 2

6

回答は1つしかなく、報奨金の期限が近づいているので、ベースラインの回答を追加して、質問の内容をはるかに超えて追加されない回答に報奨金が自動的に付与されないようにする必要があると思いました。

明らかな最初のステップは、元のツイートのセットを取得し、すべてのin_reply_to_status_idリンクをたどって多くの有向非巡回グラフを作成することです。これらの関係については、ほぼ100%確信できます。(元のセットに含まれていないツイートでもリンクをたどり、検討しているステータス更新のセットにそれらを追加する必要があります。)

その簡単なステップを超えて、人は「言及」に対処しなければなりません。電子メールのスレッド化とは異なり、件名のように一致するものはありません。これは必然的にエラーが発生しやすくなります。私が採用するアプローチは、そのツイート内の言及によって表される可能性のあるステータスID間のすべての可能な関係の特徴ベクトルを作成し、「応答なし」オプションを含む最適なオプションを推測するように分類子をトレーニングすることです。

「すべての可能な関係」ビットを解決するには、1人以上の他のユーザーに言及し、を含まないすべてのステータス更新を検討することから始めますin_reply_to_status_id。これらのツイートの1つの例が次のとおりであるとします:1

@a @b no it isn't lol  RT @c Yes, absolutely. /cc @stephenfry

...この更新と、、、、のタイムラインのより早い日付のすべての更新と先週(たとえば)の関係、およびその更新と特別な「応答なし」更新の@a間の関係の特徴ベクトルを作成します。 。次に、特徴ベクトルを作成する必要があります。これに好きなように追加できますが、少なくとも次のものを追加することをお勧めします。@b@c@stephenfry

  • 2つの更新の間に経過した時間-おそらく、最近の更新に対する応答である可能性が高くなります。
  • 言及が発生する単語の観点からのツイートの途中の割合。たとえば、これが最初の単語である場合、これはスコア0になり、更新の後半で言及するよりも、おそらく返信を示す可能性が高くなります。
  • 言及されたユーザーのフォロワーの数-有名人はおそらくスパムに言及されている可能性が高いです。
  • 更新間の最長の共通部分文字列の長さ。直接引用符を示している可能性があります。
  • 言及の前に「/cc」またはこれがその人への直接の返信ではないことを示す他の記号が付いていますか?
  • following / followed元の更新の作成者の比率。

分類器は有用であることが判明したもののみを使用するため、これらの1つが多いほど良い結果が得られます。Wekaで便利に実装されているランダムフォレスト分類子を試すことをお勧めします。

次はトレーニングセットが必要です。これは最初は小さい場合があります-稼働中の会話を識別するサービスを取得するのに十分です。この基本的なサービスに、ユーザーがそれらを修正できるように、不一致または誤ってリンクされた更新を修正するための優れたインターフェースを追加する必要があります。このデータを使用して、より大きなトレーニングセットとより正確な分類器を構築できます。

1 ...これはTwitterでの談話のレベルの典型かもしれません;)

于 2011-03-28T08:14:30.753 に答える
0

Twitterでは、返信するメッセージの前に「RT」と書くことがよくあります。

于 2010-08-24T00:26:18.000 に答える