Reddit 排名算法工作原理

9顶
0踩

2013-08-27 14:08 by 副主编 WnouM 评论(1) 有9094人浏览

Reddit 排名算法

Reddit是个社交新闻站点，其口号是“提前于新闻发生，来自互联网的声音”。用户（也叫redditors）能够浏览并且可以提交互联网上内容的链接或发布自己的原创帖子。其他的用户可对发布的链接进行高分或低分的投票，得分突出的链接会被放到首页。另外，用户可对发布的链接进行评论以及回复其他评论者。

本文将跟大家探讨一下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找到了它，但我怀疑他们未必是原作者）：

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

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

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

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

对数加强

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

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

下面是效果图：

如果不使用对数加强，则分数会是这样：

反对票对排名的影响

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

up_votes – down_votes

这就是说，我们可以把它表现为下图：

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

对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算法，它的数学表达式是这样的：

在上面的公式中，各个参数的定义如下：

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

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

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

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

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

发表时间对排名的影响：没有！

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

图表视图

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

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

排序之外的应用

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

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

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

取样总数
支持数

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

英文原文：How Reddit ranking algorithms work / 译：外刊IT评论

查看图片附件

来自: 外刊IT评论

分享到：

9
顶

0
踩

评论共 1 条请登录后发表评论

1 楼 dohkoos 2014-04-04 22:54

xkcd网站的Randall Munroe是Reddit网站上的‘最佳文章’排名算法的发明者。

明显不是发明者啊，只是推荐了该算法而已。

发表评论

您还没有登录,请您登录后再发表评论

相关推荐

零基础数据分析的我用了半年时间利用信用卡交易数据建模协助警方破获电信诈骗集团

五年前，我离开了国企工厂的安乐窝，借一个偶然的机会进入了天津唯一的第三方支付公司中汇支付。这是我职业生涯中跨度最大的转变之一。说实话这个跨度挺大的，以后我每次的换工作行业、领域跨度都很大。@[TOC]

新人怎么入门游戏建模？从哪一个软件开始学习？

入门游戏建模，从零基础变成有基础：包括美术基础，软件基础（3Dmax，ZBrush，PS）主要包括：3Dmax基础、UV拆分和摆放、贴图绘制基础。（1）底模软件（3dmax或Maya）你可以从基础的3D建模软件学起了，它可以是3D...

学习游戏3D建模电脑推荐，入门级应该怎么学才能做出好看的模型？

一学3D建模电脑配置需要高配还是低配？这个必须是高配，低配你电脑卡的就直接就跑不动了，你平时用的那种一般的电脑，顶多算个小...这绝对是全B站最用心（没有之一）的建模电脑配置讲解！_哔哩哔哩_bilibilihttps:

游戏3D建模要美术基础吗？

关于3D建模软件有哪些，这个问题，我在下面会详细的讲解，一堆，会看的你眼疼，这个问题不着急，淡定。首先我需要讲的是跳出软件这个层面来理解软件，放大我们的格局来学习软件，只有理解了更大的层面，才能更好的去...

数据中台和ERP是啥关系？不都是信息系统吗？ by彭文华

这是彭文华的第142篇原创最近感觉选题进入平台期了，急需各位同学骚扰聊天，好激发我的灵感。啥问题都行，我不挑的，啥事都能聊。还好，昨天朋友老赵就问我一个问题，然后我给他说了半个小时，要不我...

我用python写了一套股票万金油，回报小雪下面给我吃

回复“pythonpdf“，立刻领取100本全品类Python电子书2020年春。H江畔的L地段，是众多跨国银行的Z区及Y洲总部所在地，Z国最具影响力的金融中心之一。受全球疫情影响，今年...

4米乘以12米CAD图_这篇文章解决了我多年CAD制图比例问题！

设计院来了个年轻人——如果跟着我每一步都做完之后，你还不懂CAD制图比例，那你就过来掐死我吧——谨以此文送给刚刚毕业的学生朋友们！——我多么希望我刚毕业的时候能够看到这么一篇攻略！！！恨不能把这个给十年...

小白学习3D游戏建模从什么软件开始？人物角色建模怎么做？

一建模软件多如牛毛，要么不学，要么就学主流，非主流一边凉快去吧。关于3D建模软件有很多，都了解，都学没什么意义，最后只会犯选择困难症，把在社会上应用最普遍的，最主流的学会，就能很好的在3D建模这个行业混...

3D游戏建模需要学会哪些软件？想入行游戏建模的你都学习了吗？

一、次世代的制作流程： 1、根据二维原画设定制作中模； 2、导进ZB进行高模雕刻； 3、拓补低模（即在游戏中的模型）； 4、展分UV； 5、烘焙（将高模细节烘焙到低模上面）； 6、绘制贴图； 7、引擎中调整。 ...

3D人物建模需要哪些软件？资深大牛全方位从入门到实战解析

maya游戏模型制作是指：maya游戏模型制作师根据原画师提供的原画稿件，制作出游戏中的环境、机械、道具、人物、动物、怪物等模型，分为maya游戏角色模型制作和maya游戏场景模型制作。 Autodesk Maya用于不少的动画...

我用python写了一套股票万金油，回报小雪下面给我吃！

2020年春。 H江畔的L地段，是众多跨国银行的Z区及Y洲总部所在地，Z国最具影响力的金融中心之...其中一扇不起眼的窗户，19寸电脑显示屏上，红绿的代码焦急的闪烁着。屏幕前，是一位妙龄少女，居家的粉红暖靴，玉腿颀长

大疆RoboMaster技术总监：我是如何成为一名机器人工程师的

作者 | 大疆创新RoboMaster技术总监YY硕▌前言很多朋友私信问我对机器人和人工智能感兴趣，该怎么展开学习。最近稍微有点空，我写写我的看法。两年前，我在知乎回答如...

Flexsim项目：××便利贴供应链建模与仿真设计

本课程设计旨在通过学习FlexSim仿真软件，应用理论知识解决生产物流问题。以××便利贴的部件入库和组装出库为案例，通过模拟发现问题，减少浪费，提高运营效率。流程涵盖材料处理、染色、组装、质检等环节，使用...

大疆技术总监：如何用六年成为一个全能的机器人工程师（转载）

（机器人学的核心问题是做好和物理世界的交互。现在主流的机器人学分支里，处理与物理世界的交互的学科分为三类：传感器和处理算法；多刚体系统动力学控制；机器人自主移动。）

FLAC3D隧道台阶法施工模拟：命令操作与支护结构一体化构建

内容概要：本文详细介绍了利用FLAC3D进行隧道台阶法施工模拟的方法和技术细节。首先解释了隧道台阶法施工的基本流程，重点在于开挖命令的应用，如'zone cmodel assign'和'zone remove'用于改变区域本构模型并执行开挖操作。接着阐述了支护结构的设置方法，包括超前加固体、初衬、二衬、锚杆和锁脚锚杆的具体配置方式。此外，还讲解了如何通过'mesh'命令直接在FLAC3D中生成符合实际工程需求的网格模型。最后展示了模拟后的围岩体位移云图和应力云图，验证了计算结果的有效性，强调了这些数据对优化施工方案的重要性。适合人群：从事岩土工程、隧道工程及相关领域的工程师和技术人员。使用场景及目标：适用于需要进行隧道施工模拟的专业人士，旨在提升他们对FLAC3D的理解和应用能力，确保隧道施工的安全性和高效性。其他说明：文中提供的实例和命令操作均基于真实项目经验，有助于读者更好地理解和掌握FLAC3D的实际应用技巧。

纤维骨料细观尺度混凝土模型：基于多有限元软件的网格划分与应用

内容概要：本文介绍了纤维骨料细观尺度混凝土模型的设计与应用，重点在于如何通过控制骨料尺寸和体积率，在不同有限元软件（如Abaqus、Ansys、Ls-Dyna、Flac3d）中进行有效的四面体网格划分和六面体网格投影。文中提供了生成随机骨料位置和直径的Python代码片段，并详细解释了网格划分过程中需要注意的技术细节，如碰撞检测、网格转换公式以及材料属性设置。此外，还讨论了模型验证的方法及其在实际工程项目中的应用价值。适合人群：从事土木工程、材料科学领域的研究人员和技术人员，尤其是那些需要利用有限元方法进行混凝土结构分析的专业人士。使用场景及目标：①帮助工程师更好地理解和预测纤维混凝土的行为特性；②为实际工程项目提供理论支持和技术指导，从而优化纤维混凝土的应用；③提高仿真精度，减少实验成本和时间。其他说明：文中提到的一些具体操作步骤和技术细节对于初学者来说可能具有一定挑战性，建议读者在实践中逐步掌握相关技能并积累经验。同时，正确设置物理量单位非常重要，错误的单位可能导致计算结果严重偏离预期。

嵌入式八股文面试题库资料知识宝典-c++个人笔记总结.zip

工业自动化领域西门子S7-1200 PLC模块、板卡及多协议通讯详解

内容概要：本文详细介绍了西门子S7-1200 PLC在工业自动化领域的应用，重点讲解了其模块、板卡和通讯方式。首先概述了PLC模块和板卡作为基本单元的作用，接着深入探讨了支持的多种通讯协议，包括Modbus-RTU、S7通讯、Modbus-TCP和TCP/IP等。每种协议都配有具体的代码分析和调试方法。最后，介绍了博途V16编程软件的使用体验，强调了其对S7-1200 PLC编程的支持。适合人群：从事工业自动化领域的工程师和技术人员，尤其是对西门子S7-1200 PLC有初步了解或希望深入了解的人群。使用场景及目标：适用于需要掌握PLC模块化设计、不同通讯协议的应用场景，旨在帮助读者理解PLC的工作原理，提高编程和调试能力，从而更好地应用于实际项目中。其他说明：文中提供的实例和代码分析有助于读者快速上手，同时推荐使用博途V16及以上版本的编程软件进行实践操作。

Comsol仿真无模型等离子体空气反应框架：多气体反应及关键参数求解

内容概要：本文介绍了Comsol仿真软件在等离子体空气反应领域的应用，重点探讨了其无模型反应框架的功能。该框架能模拟超过40种气体（如氧气、氮气、氦气）的详细反应过程，提供碰撞截面数据、迁移率扩散系数、速率系数和汤森系数的查询与求解功能，并通过bosig+模块实现自定义反应路径的选择。此外，文中强调了代码分析与实践应用的重要性，以及这些功能如何提升等离子体反应研究的效率和准确性。适合人群：从事等离子体物理、化学反应动力学及相关领域研究的专业人士和技术人员。使用场景及目标：适用于需要精确模拟复杂等离子体环境中气体反应的研究项目，旨在提高对等离子体反应机制的理解，优化实验设计，预测反应行为。其他说明：Comsol仿真软件凭借其强大的计算能力，在等离子体研究中扮演着重要角色。随着技术的发展，该框架有望进一步推动相关领域的创新和发展。

9顶0踩