注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

秋风扫落叶

 
 
 

日志

 
 
 
 

Reddit 排名算法工作原理  

2013-09-08 16:15:09|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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

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

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

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

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

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

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

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

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

对数加强

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

下面是效果图:

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

反对票对排名的影响

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

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

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

对Reddit文章排名算法的总结

Reddit评论排名算法工作原理

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

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

深入分析评论排序代码

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

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

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

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

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

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

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

图表视图

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

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

排序之外的应用

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

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

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

结论

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

祝编程快乐

本文由“外刊IT评论”网(www.aqee.net)荣誉出品

[英文原文:How Reddit ranking algorithms work ]

  评论这张
 
阅读(1737)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017