algorithm - 什么是线程推文的一套好的启发式方法？

Question

大家都知道，如果你想发送电子邮件，你可以使用 Jamie Zawinski's algorithm .但这是一个新世纪，还有一个 新的消息服务。

线程状态更新的最佳算法是什么？ 推特？

我绝对希望它能处理的事情:

• 简单的部分:使用 in_reply_to_status_id， in_reply_to_user_id 和 in_reply_to_screen_name。 (顺便说一句，找到这些值的适当文档 本身就会有用!这样的文档不是 显然与来自 here , 例如。)

• 从中推断“回复”关系的良好启发式方法 使用 @ 约定提及用户但不是的消息 明确回复特定消息。这些 “提到” are provided in the "entities" element of statuses now 如果你要求的话。这些启发式可能会考虑 帐户 (a) 两次状态更新之间的时间，(b) 是否 两个用户之间有后续回复，等等。 (回复由旧式转推和 附加评论，如 mentioned by user85509 below 只是这种回复方式的一个例子。)

• 发生在两个以上用户之间的对话。

• 处理给定算法的一组推文，或所有推文 在 Twitter 上发推文。

...但也许您可以想到更多。

Answer 1

由于只有一个答案，而且赏金截止日期快到了，我想我应该添加一个基准答案，这样赏金就不会自动授予那些没有超出问题内容的答案。

显而易见的第一步是采用您的原始推文集并遵循所有 in_reply_to_status_id 链接来构建许多有向无环图。您几乎可以 100% 确定这些关系。 (即使通过不在原始集中的推文，您也应该关注这些链接，将它们添加到您正在考虑的状态更新集中。)

除了这个简单的步骤之外，还必须处理“提及”。与电子邮件线程不同，没有什么比可以匹配的主题行更有用了——这不可避免地会很容易出错。我将采取的方法是为可能由该推文中的提及表示的状态 ID 之间的每个可能关系创建一个特征向量，然后训练分类器来猜测最佳选项，包括“不回复”选项。

要计算出“每种可能的关系”位，首先要考虑提到一个或多个其他用户且不包含 in_reply_to_status_id 的每个状态更新。假设这些推文之一的示例是:¹

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

...您将为此更新与时间轴中较早日期的每个更新之间的关系创建一个特征向量 @a, @b, @c 和 @stephenfry 是上周(比方说)以及那个更新和特殊的“无回复”更新之间的一个。然后你必须创建一个特征向量——你可以添加任何你想要的，但我至少建议添加:

• 两次更新之间耗时 - 大概是对最近更新的回复。
• 在推文中出现提及的单词所占的比例。例如如果这是第一个词，则得分为 0，与更新中稍后提到的相比，这可能更可能表示回复。
• 所提及用户的关注者数量 - 名人可能更有可能被提及为垃圾邮件。
• 更新之间最长公共(public)子串的长度，这可能表示直接引用。
• 是否以“/cc”或其他表示这不是直接回复该人的指示符开头？
• 原始更新作者的关注/关注比率。
• 等等
• 等等

越多越好，因为分类器只会使用那些最终证明有用的分类器。我建议尝试 random forest分类器，在 Weka 中方便地实现.

下一个需要训练集。一开始这可能很小——刚好足以获得识别对话的服务。对于这项基本服务，必须添加一个漂亮的界面来纠正不匹配或错误链接的更新，以便用户可以纠正它们。使用这些数据可以构建更大的训练集和更准确的分类器。

^{1 _{... 这可能是 Twitter 上典型的话语水平；)}}