fra*_*cus 14 algorithm twitter heuristics email-threading
每个人都知道,如果你想要发送电子邮件,你可以使用Jamie Zawinski的算法.但这是一个新世纪,还有一种新的消息传递服务.
Twitter上发布的线程状态更新的最佳算法是什么？
我绝对喜欢它应对的事情:
简单的部分:使用in_reply_to_status_id,
in_reply_to_user_id和in_reply_to_screen_name.(顺便说一句,找到这些值的正确文档本身就很有用!例如,这些文档显然与此处没有关联
.)
用于从提及具有@约定的用户但未明确回复特定消息的消息推断"回复"关系的良好启发式.
如果您要求,这些"提及" 现在在状态的"实体"元素中提供.这些启发式方法可能会考虑(a)两个状态更新之间的时间,(b)两个用户之间是否存在后续回复等.(回复包含带有附加注释的旧式转发,如user85509所述以下
只是这种回复方式的一个例子.)
在两个以上用户之间进行的对话.
使用给出算法的一组推文,或推特上的所有推文.
......但也许你可以想到更多.
由于只有一个答案,并且赏金截止日期即将到来,我认为我应该添加一个基线答案,因此赏金不会自动授予答案,而答案不会超出问题的范围.
显而易见的第一步是采用原始的推文集,并按照所有in_reply_to_status_id链接构建许多有向无环图.这些关系你几乎可以100%肯定.(您应该通过不在原始集中的推文来关注链接,将这些添加到您正在考虑的状态更新集中.)
除了这个简单的步骤,人们必须处理"提及".与电子邮件线程不同,没有什么可以像人们可以匹配的主题行那样有用 - 这不可避免地会出现非常容易出错的情况.我将采用的方法是为状态ID之间的每个可能关系创建一个特征向量,该关系可能由该推文中的提及表示,然后训练分类器以猜测最佳选项,包括"无回复"选项.
要计算"每个可能的关系"位,首先要考虑提及一个或多个其他用户且不包含的每个状态更新in_reply_to_status_id.假设其中一条推文的一个例子是:1
@a @b no it isn't lol RT @c Yes, absolutely. /cc @stephenfry
...您将创建一个特征向量,此更新,并与在的时间表提前每次更新之间的关系@a,@b,@c,和@stephenfry在上周(说)和更新之间的一个特殊的"无应答"更新.然后你必须创建一个特征向量 - 你可以添加到你想要的任何东西,但我至少建议添加:
following / followed原始更新的作者的比率.这些中的越多越好,因为分类器将仅使用那些最有用的分类器.我建议尝试一个随机森林分类器,它可以在Weka中方便地实现.
下一个需要训练集.这可能很小 - 刚好足以获得识别对话正常运行的服务.对于这个基本服务,人们必须添加一个很好的界面来纠正不匹配或错误链接的更新,以便用户可以纠正它们.使用此数据可以构建更大的训练集和更准确的分类器.
1 ...这可能是Twitter上话语层次的典型;)