Reddit排名算法工作原理_最新动态

您所在的位置：程序员俱乐部 > 新闻资讯 > 最新动态 > Reddit排名算法工作原理

Reddit排名算法工作原理

2013/8/27 1:57:24 程序员俱乐部我要评论(0)

摘要：英文原文：HowRedditrankingalgorithmswork这是一篇继《HackerNews排名算法工作原理》之后的又一篇关于排名算法的文章。这次我将跟大家探讨一下Reddit的文章排名算法和评论排名算法的工作原理。Reddit使用的算法也是很简单，容易理解和实现。这篇文章里我将会对其进行深入分析。首先我们关注的是文章排名算法。第二部分将重点介绍评论排名算法，Reddit的评论排名跟文章排名使用的不是同一种算法(这点跟HackerNews不一样)，Reddit的评论排名算法非常有趣
标签：工作排名算法

　　英文原文：How Reddit ranking algorithms work

　　这是一篇继《Hacker News 排名算法工作原理》之后的又一篇关于排名算法的文章。这次我将跟大家探讨一下 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 网站上的‘最佳文章’排名算法的发明者。他写了一篇很好的文章来解释它。

reddit’s new comment sorting system

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

‘热门‘排名算法对评论进行排名不是很有效，它会显得对早期的评论过于偏爱。
在一个评论系统中，我们的目的是找出最佳评论，不论它是什么时间提交的。
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