Reddit排名算法工作原理

标签: reddit 排名 算法 | 发表时间:2013-08-26 15:53 | 作者:
出处:http://news.cnblogs.com/

算法

英文原文: How Reddit ranking algorithms work

这是一篇继《 Hacker News 排名算法工作原理》之后的又一篇关于排名算法的文章。这次我将跟大家探讨一下 Reddit 的文章排名算法和评论排名算法的工作原理。Reddit 使用的算法也是很简单,容易理解和实现。这篇文章里我将会对其进行深入分析。

reddit

首先我们关注的是文章排名算法。第二部分将重点介绍评论排名算法,Reddit 的评论排名跟文章排名使用的不是同一种算法(这点跟 Hacker News 不一样),Reddit 的评论排名算法非常有趣,它是由 xkcd 的作者 Randall Munroe 发明的。

深入研究文章排名算法代码

Reddit 的源代码是开源的,你可以下载它的任意代码。它是用 Python 写成的,代码放在 这里。里面的排名算法部分是用 Pyrex 实现的,这是一种开发 Python 的C语言扩展的编程语言。这里用 Pyrex 主要是出于速度的考虑。我用纯 Python 重写了他们的 Pyrex 实现,这样更容易阅读。

Reddit 缺省的排名是’热门‘排名,实现代码如下:

#Rewritten code from /r2/r2/lib/db/_sorts.pyx from datetime import datetime, timedelta
from math import log

epoch = datetime (1970, 1, 1)

def epoch_seconds (date):
    """Returns the number of seconds from the epoch to date."""
    td = date - epoch
    return td.days * 86400 + td.seconds + (float (td.microseconds) / 1000000)

def score (ups, downs):
    return ups - downs

def hot (ups, downs, date):
    """The hot formula. Should match the equivalent function in postgres."""
    s = score (ups, downs)
    order = log (max (abs (s), 1), 10)
    sign = 1 if s > 0 else -1 if s < 0 else 0
    seconds = epoch_seconds (date) - 1134028003 return round (order + sign * seconds / 45000, 7)

这个“热门“排名算法用数学公式表达是下面这个样子(我从 SEOmoz 找到了它,但我怀疑他们未必是原作者):

reddit_cf_algorithm

文章提交时间对排名的影响

文章提交时间对排名的影响可以总结为以下几点:

  • 提交时间对排名影响巨大,越新的文章排名会越高
  • 文章排名得分不会随时间的流逝而降低,但新文章会比老文章获得更高的分。这跟 Hacker News 的排名算法有很大区别,它的得分会随时间流逝而降低。

下面是一个图片,表现的是具有相同支持和反对的票数,但时间不同的文章的排名得分情况:

reddit_score_time

对数加强

Reddit 在‘热门’排名中使用了对数函数来强化前几票的份量。基本是这个原理:

  • 前 10 个赞成票的份量和后面 100 个的份量,以及再后面 1000 票的份量是相同的,以此类推

下面是效果图:

reddit_log_function

如果不使用对数加强,则分数会是这样:

reddit_without_log

反对票对排名的影响

Reddit 是少数几个能投反对票的网站之一。就像你从代码里看到的,一篇文章的的’得分‘定义如下:

  • up_votes – down_votes

这就是说,我们可以把它表现为下图:

reddit_up_down

这种计算方式会对既有很的赞成票,又有很多反对票的文章(比如很有争议的文章)带来重大影响,它们可能会比那些只有很少赞成票的文章获得更低的分数。这也就说明了为什么小猫小狗之类的帖子(以及其它无争议的文章)会获得如此高的评分。 

对 Reddit 文章排名算法的总结

  • 提交时间是一项非常重要的指标,新文章比老文章得分更高
  • 头 10 个赞成票的份量和后 100 个的份量相同。获得 10 个赞成票和获得 50 个赞成票的排名很接近
  • 具有相近赞成票和反对票数的有争议文章会比只获得赞成票的排名低。

Reddit 评论排名算法工作原理

xkcd 网站的 Randall Munroe 是 Reddit 网站上的‘最佳文章’排名算法的发明者。他写了一篇很好的文章来解释它。

你应该读一读这篇文章,它以很通俗的语言解释了这个算法。这篇的文章的重点是:

  • ‘热门‘排名算法对评论进行排名不是很有效,它会显得对早期的评论过于偏爱。
  • 在一个评论系统中,我们的目的是找出最佳评论,不论它是什么时间提交的。
  • 1927 年 Edwin B. Wilson 找到了一种很好的算法,被叫做”Wilson score interval”,它可以被用于“信任排序(the confidence sort)”
  • 信任排序把文章的获得的票数当作全体读者的一个抽样统计——就像一次民意测验。
  • 《How Not To Sort By Average Rating》这篇文章对这种信任评级算法做了详细的解释,绝对值得一读!

深入分析评论排序代码

Reddit 里的信任排序算法是在 _sorts.pyx 这个文件里实现的,我用纯 Python 重写了它们的 Pyrex 实现(同时去掉了其中的缓存优化代码):

#Rewritten code from /r2/r2/lib/db/_sorts.pyx from math import sqrt

def _confidence (ups, downs):
    n = ups + downs

    if n == 0:
        return 0

    z = 1.0 #1.0 = 85%, 1.6 = 95% phat = float (ups) / n
    return sqrt (phat+z*z/(2*n)-z*((phat*(1-phat) +z*z/(4*n))/n))/(1+z*z/n)

def confidence (ups, downs):
    if ups + downs == 0:
        return 0
    else:
        return _confidence (ups, downs)

信任排序使用 Wilson score interval 算法,它的数学表达式是这样的:

wilsons_score_interval

在上面的公式中,各个参数的定义如下:

  • p是支持票的百分比
  • n总票数
  • z α/2是正态分布(1-α/2) 分位数

我们对上面的介绍做一些总结:

  • 信任排序是把票数看作一次全体读者的抽样调查
  • 信任排序会给一条评论一个临时评级,认为它有 85% 的可信度
  • 票数越多,可信度越高
  • Wilson’s interval 算法能很好的处理票数很少和低端概率情况

Randall 在 他的文章里对信任排序的工作原理给了一个很好的例子:

如果一条评论只有一个赞成票和 0 个反对票,它有 100% 的支持率,但因为投票数太少,系统将会把它放在排名底部。但如果它有 10 个赞成票,而其只有 1 个反对票,那系统将会把它放到比具有 40 个赞成票和 20 个反对票的评论更高的排名上——可以推断出,当这个评论获得 40 个赞成票时,它极有可能获得的反对票会少于 20。这种算法最好的部分是,如果推断错了,那它会很快的获得更多的数据来证明,因为它已经被排到了顶部。

发表时间对排名的影响:没有!

信任排序一个优点是评论发表时间是不产生影响作用的(这跟‘热门排序’和 Hacker News 的排名算法是不一样的)。评论是通过信任评级,通过数据取样计算,一条评论获得的票数越多,它能获得的评级越接近他的真实的得分。

图表视图

让我们把信任排序做成图表,看一看它是如何影响评论排序的。我们使用 Randall 的例子:

reddit_confidence_sort

可以看到,信任排序并不在意一条评论获得了多少票数,它关注的是它的支持率和数据采样规模!

排序之外的应用

正像 Evan Miller 所说的,Wilson’s score interval 算法可以在非排名应用里使用,他列举了 3 个例子:

  • 检查垃圾信息:看过这条信息的人中有多大比例认为它是垃圾信息?
  • 制作“最优”排名:看过这条信息的人中有多大比例认为它是“最好的….”?
  • 制作“邮件转发”排名:看过条信息这的人中有多大比例点击了‘Email’按钮?

使用这个算法你只需要两个数据:

  • 取样总数
  • 支持数

这个算法是如此有效,但很奇怪很多的网站如今仍然是最原始的评级方法,这包括著名的 亚马逊,它仍然使用“得分 = 支持票 / 总票数”。

结论

我希望这篇文章对你们有些用处,如有任何疑问,请在评论里写出。

祝编程快乐。

本文链接

相关 [reddit 排名 算法] 推荐:

数学之美:Reddit的排名算法

- - 标点符
上一篇文章介绍了 Hacker News 的排名规则. 这次要介绍的是另外一个社会化新闻类网站 Reddit. Reddit对文章和评论使用了不同的排名算法,这边文章要介绍的是前者,后面的关于评论的排名在后面的文章作再作介绍. Reddit与Hacker News有很大的不同点就是,Hacker News文章标题前面只有一个向上的小箭头,即只能投赞成票,而Reddit的每个文章标题前会有两个箭头,即一个向上,一个像下.

Reddit排名算法工作原理

- - 博客园_新闻
英文原文: How Reddit ranking algorithms work. 这是一篇继《 Hacker News 排名算法工作原理》之后的又一篇关于排名算法的文章. 这次我将跟大家探讨一下 Reddit 的文章排名算法和评论排名算法的工作原理. Reddit 使用的算法也是很简单,容易理解和实现.

基于用户投票的排名算法(二):Reddit

- - 阮一峰的网络日志
(不好意思,这个系列中断了近两周,我会尽快在这几天,把后面几篇写完. 上一次,我介绍了 Hacker News的排名算法. 它的特点是用户只能投赞成票,但是很多网站还允许用户投反对票. 就是说,除了好评以外,你还可以给某篇文章差评. Reddit是美国最大的网上社区,它的每个帖子前面都有向上和向下的箭头,分别表示"赞成"和"反对".

重写Reddit

- - 博客园_新闻
英文原文: Rewriting Reddit. 2012 年注:本文首发于 2005 年. 发布之后,Django 上线了一个 RemovingTheMagic 项目,提出了我的一些质疑(尽管我本人发现它仍然不可用), web.py 促进了 FriendFeed 的. tornado.web 和 Google 的.

Android Market排名算法及规则(转)

- boho - 数据挖掘与数据分析
原文来自:http://www.mobile20.com.cn/android-market-ranking-rules/. 众所周知,做搜索出身的Google,旗下的Market的排名肯定是依据一个形同( A×a% + B×b% + C×c%)的公式计算出来的数值,进行排名的. 可根据其排名规则,对自己的产品设计和研发以及推广进行指导.

Android Market排名算法及规则

- PH囧ENIX - Mobile 2.0-我们专注移动互联网
  众所周知,做搜索出身的Google,旗下的Market的排名肯定是依据一个形同( A×a% + B×b% + C×c%)的公式计算出来的数值,进行排名的. 开发者可根据其排名规则,对自己的产品设计和研发以及推广进行指导.   指标A、B、C到底是什么. 这些问题的答案,应该是每个App开发者和运营者都渴望了解的.

Hacker News的热门排名算法

- - 互联网实践
Hacker News 是一家关于计算机黑客和创业公司的社会化新闻网站,由 Paul Graham 的创业孵化器 Y Combinator 创建. 与其它社会化新闻网站不同的是 Hacker News 没有踩或反对一条提交新闻的选项(不过评论还是可以被有足够 Karma 的用户投反对票,或是投支持票);只可以赞或是完全不投票.

Google新闻排名算法透视

- - 博客园_新闻
自 2002 年推出以来,Google News 已成为 Web 上最大的新闻内容聚合器. 在去年 9 月《大西洋月刊》的一篇文章中,Google News 的主管曾说该网站收集的新闻来源超过 5 万个,每周的独立访客超过 10 亿. 该网站完全由计算机生成,每天都会收集和展示从全球数千个新闻来源的头条新闻.

Hacker News 排名算法工作原理

- - python.cn(jobs, news)
这篇文章我要向大家介绍 Hacker News网站的文章排名算法工作原理,以及如何在自己的应用里使用这种算法. 这个算法非常的简单,但却在突出热门文章和遴选新文章上表现的异常优秀. 深入 news.arc 程序代码. Hacker News是用Arc语言开发的,这是一种Lisp方言,由Y Combinator投资公司创始人 Paul Graham创造.

Reddit审查“未成年少女”

- 微笑!?~ - Solidot
Reddit以“危险到社区结构完整性”为名正式关闭了一个子群组“r/jailbait”. jailbait是美国英语俚语,指未到法定年龄的年轻少女,但身体发育已经成熟,会被误以为是成年人. 关闭jailbait引发了言论自由的争论,但有人指出,Reddit是私人经营的网站,它有权阻止一些它不想要的言论.