Was ist eine gute Heuristik für Tweets?

Question

Jeder weiß, wenn Sie E-Mails einreihen möchten, verwenden Sie Jamie Zawinski's algorithm. Aber es ist ein neues Jahrhundert, und es gibt einen neuen Nachrichtenservice.

Was ist der beste Algorithmus für Threading Status Updates auf Twitter gepostet?

Dinge, die ich würde auf jeden Fall, wie es zu bewältigen:

• der einfache Teil: mit in_reply_to_status_id, in_reply_to_user_id und in_reply_to_screen_name. (Übrigens finden ordnungsgemäße Dokumentation dieser Werte an sich nützlich sein würde! Eine solche Dokumentation offensichtlich nicht zu von here, beispielsweise verbunden ist.)

• gute Heuristik für eine „Antwort“ Beziehung Folgern aus Nachrichten, die einen Benutzer mit der @ Konvention erwähnen, aber sind nicht explizit als Antwort auf eine bestimmte Nachricht. Diese "Erwähnungen" are provided in the "entities" element of statuses now wenn Sie das verlangen. Diese Heuristiken könnten in account (a) die Zeit zwischen zwei Statusupdates aufnehmen, (b) ob es zwei aufeinanderfolgende Antworten zwischen den beiden Benutzern gibt, usw. (Antworten, die aus einem Retweet im alten Stil mit einem zusätzlichen Kommentar bestehen, als mentioned by user85509 below sind nur eine Instanz dieser Art von Antwort.)

• Gespräche, die zwischen mehr als zwei Benutzern stattfinden.

• Arbeiten mit einer Reihe von Tweets gegeben, um den Algorithmus oder alle Tweets auf Twitter.

... aber vielleicht können Sie an mehr denken.

Answer 1

Da es nur eine Antwort gibt und die Bounty-Deadline bald naht, dachte ich, ich sollte eine Grundantwort hinzufügen, damit die Bounty nicht automatisch zu einer Antwort hinzugefügt wird, die nicht viel über die Frage hinausgeht.

Der offensichtliche erste Schritt besteht darin, Ihre ursprünglichen Tweets zu nehmen und alle in_reply_to_status_id Links zu folgen, um viele gerichtete azyklische Graphen zu erstellen. Über diese Beziehungen kann man sich nahezu 100% sicher sein. (Sie sollten den Links auch durch Tweets folgen, die nicht im ursprünglichen Satz enthalten sind, und diese zu den Statusaktualisierungen hinzufügen, die Sie in Betracht ziehen.)

Über diesen einfachen Schritt hinaus muss man sich mit dem " erwähnt ". Anders als beim E-Mail-Threading gibt es nichts hilfreiches wie eine Betreffzeile, auf die man sich anpassen kann - das ist zwangsläufig wird sehr fehleranfällig sein. Der Ansatz, den ich wählen würde, besteht darin, einen Merkmalsvektor für jede mögliche Beziehung zwischen Status-IDs zu erstellen, die durch Erwähnungen in diesem Tweet repräsentiert werden könnten, und dann einen Klassifizierer zu schulen, um die beste Option zu erraten, einschließlich einer "keine Antwort" -Option.

Um das Bit "jede mögliche Beziehung" auszuarbeiten, betrachten Sie zunächst alle Statusaktualisierungen, die einen oder mehrere andere Benutzer enthalten, und enthält keine in_reply_to_status_id. Nehmen sich ein Beispiel für eine dieser tweets ist:

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

... Sie einen Merkmalsvektor für die Beziehung zwischen diesem Update schaffen würden und jeden Update mit einem frühen Zeitpunkt in dem Zeitrahmen von @a, @b, @c, und @stephenfry für die letzte Woche (sagen wir) und eine zwischen diesem Update und einem speziellen "no reply" -Update. Dann müssen Sie einen Merkmalsvektor erstellen - Sie können diese hinzufügen, was auch immer Sie möchten, aber ich würde zumindest vorschlagen Zugabe:

• Die Zeit, die zwischen den beiden Updates verstrichene - vermutlich Antworten sind eher zu sein, kürzliche Updates.
• Der Anteil des Weges durch den Tweet in Bezug auf Wörter, die eine Erwähnung auftritt. z.B. Wenn dies das erste Wort ist, wäre dies eine Punktzahl von 0, und das ist wahrscheinlich eher eine Antwort als Erwähnungen später im Update.
• Die Anzahl der Anhänger des genannten Benutzers - Prominente sind vermutlich eher Spam-Erwähnung.
• Die Länge des längsten gemeinsamen Teilstrings zwischen den Aktualisierungen, der ein direktes Angeben anzeigen könnte.
• Wird vor der Erwähnung "/ cc" oder andere Zeichen angezeigt, die darauf hinweisen, dass dies nicht direkt eine Antwort auf diese Person ist?
• Das following/followed Verhältnis für den Autor des ursprünglichen Updates.
• usw.
• usw.

Je mehr von diesen kann man mit dem besser kommen, da der Klassifikator nur diejenigen, die erweisen sich als nützlich verwenden. Ich würde vorschlagen, einen random forest Klassifikator zu versuchen, der bequem in Weka implementiert wird.

Als nächstes braucht man ein Trainingset. Dies kann zunächst klein sein - gerade genug, um einen Dienst zu erhalten, der die laufenden Unterhaltungen identifiziert. Zu diesem Basisdienst müsste man eine nette Schnittstelle hinzufügen, um nicht übereinstimmende oder falsch verknüpfte Aktualisierungen zu korrigieren, so dass Benutzer sie korrigieren können. Mit diesen Daten kann man ein größeres Trainingset und einen genaueren Klassifikator erstellen.

^{_{..., die von der Ebene des Diskurses auf Twitter typisch sein könnte;)}}

Answer 2

Auf Twitter schreiben Leute oft "RT" vor der Nachricht, auf die sie antworten.