Reddit排名算法工作原理
這是一篇繼《Hacker News 排名算法工作原理》之后的又一篇關于排名算法的文章。這次我將跟大家探討一下Reddit的文章排名算法和評論排名算法的工作原理。Reddit使用的算法也是很簡單，容易理解和實現(xiàn)。這篇文章里我將會對其進行深入分析。
首先我們關注的是文章排名算法。第二部分將重點介紹評論排名算法，Reddit的評論排名跟文章排名使用的不是同一種算法(這點跟Hacker News不一樣)，Reddit的評論排名算法非常有趣，它是由xkcd的作者Randall Munroe發(fā)明的。
深入研究文章排名算法代碼
Reddit的源代碼是開源的，你可以下載它的任意代碼。它是用Python寫成的，代碼放在這里。里面的排名算法部分是用Pyrex實現(xiàn)的，這是一種開發(fā)Python的C語言擴展的編程語言。這里用Pyrex主要是出于速度的考慮。我用純Python重寫了他們的Pyrex實現(xiàn)，這樣更容易閱讀。
Reddit缺省的排名是’熱門‘排名，實現(xiàn)代碼如下：
- #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)
這個“熱門“排名算法用數(shù)學公式表達是下面這個樣子(我從SEOmoz找到了它，但我懷疑他們未必是原作者)：
文章提交時間對排名的影響
文章提交時間對排名的影響可以總結(jié)為以下幾點：
- 提交時間對排名影響巨大，越新的文章排名會越高
- 文章排名得分不會隨時間的流逝而降低，但新文章會比老文章獲得更高的分。這跟Hacker News的排名算法有很大區(qū)別，它的得分會隨時間流逝而降低。
下面是一個圖片，表現(xiàn)的是具有相同支持和反對的票數(shù)，但時間不同的文章的排名得分情況：
對數(shù)加強
Reddit在‘熱門’排名中使用了對數(shù)函數(shù)來強化前幾票的份量。基本是這個原理：
- 前10個贊成票的份量和后面100個的份量，以及再后面1000票的份量是相同的，以此類推
下面是效果圖：
如果不使用對數(shù)加強，則分數(shù)會是這樣：
反對票對排名的影響
Reddit是少數(shù)幾個能投反對票的網(wǎng)站之一。就像你從代碼里看到的，一篇文章的的’得分‘定義如下：
- up_votes – down_votes
這就是說，我們可以把它表現(xiàn)為下圖：
這種計算方式會對既有很的贊成票，又有很多反對票的文章（比如很有爭議的文章）帶來重大影響，它們可能會比那些只有很少贊成票的文章獲得更低的分數(shù)。這也就說明了為什么小貓小狗之類的帖子(以及其它無爭議的文章)會獲得如此高的評分。
#p#
對Reddit文章排名算法的總結(jié)
- 提交時間是一項非常重要的指標，新文章比老文章得分更高
- 頭10個贊成票的份量和后100個的份量相同。獲得10個贊成票和獲得50個贊成票的排名很接近
- 具有相近贊成票和反對票數(shù)的有爭議文章會比只獲得贊成票的排名低。
Reddit評論排名算法工作原理
xkcd網(wǎng)站的Randall Munroe是Reddit網(wǎng)站上的‘最佳文章’排名算法的發(fā)明者。他寫了一篇很好的文章來解釋它。
你應該讀一讀這篇文章，它以很通俗的語言解釋了這個算法。這篇的文章的重點是：
- ‘熱門‘排名算法對評論進行排名不是很有效，它會顯得對早期的評論過于偏愛。
- 在一個評論系統(tǒng)中，我們的目的是找出最佳評論，不論它是什么時間提交的。
- 1927年Edwin B. Wilson找到了一種很好的算法，被叫做”Wilson score interval”，它可以被用于“信任排序(the confidence sort)”
- 信任排序把文章的獲得的票數(shù)當作全體讀者的一個抽樣統(tǒng)計——就像一次民意測驗。
- 《How Not To Sort By Average Rating》這篇文章對這種信任評級算法做了詳細的解釋，絕對值得一讀！
深入分析評論排序代碼
Reddit里的信任排序算法是在_sorts.pyx這個文件里實現(xiàn)的，我用純Python重寫了它們的Pyrex實現(xiàn)(同時去掉了其中的緩存優(yōu)化代碼)：
- #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算法，它的數(shù)學表達式是這樣的：
在上面的公式中，各個參數(shù)的定義如下：
- p是支持票的百分比
- n總票數(shù)
- zα/2是正態(tài)分布(1-α/2)分位數(shù)
我們對上面的介紹做一些總結(jié)：
- 信任排序是把票數(shù)看作一次全體讀者的抽樣調(diào)查
- 信任排序會給一條評論一個臨時評級，認為它有85%的可信度
- 票數(shù)越多，可信度越高
- Wilson’s interval算法能很好的處理票數(shù)很少和低端概率情況
Randall在他的文章里對信任排序的工作原理給了一個很好的例子：
如果一條評論只有一個贊成票和0個反對票，它有100%的支持率，但因為投票數(shù)太少，系統(tǒng)將會把它放在排名底部。但如果它有10個贊成票，而其只有1個反對票，那系統(tǒng)將會把它放到比具有40個贊成票和20個反對票的評論更高的排名上——可以推斷出，當這個評論獲得40個贊成票時，它極有可能獲得的反對票會少于20。這種算法最好的部分是，如果推斷錯了，那它會很快的獲得更多的數(shù)據(jù)來證明，因為它已經(jīng)被排到了頂部。
發(fā)表時間對排名的影響：沒有！
信任排序一個優(yōu)點是評論發(fā)表時間是不產(chǎn)生影響作用的(這跟‘熱門排序’和Hacker News的排名算法是不一樣的)。評論是通過信任評級，通過數(shù)據(jù)取樣計算，一條評論獲得的票數(shù)越多，它能獲得的評級越接近他的真實的得分。
圖表視圖
讓我們把信任排序做成圖表，看一看它是如何影響評論排序的。我們使用Randall的例子：
可以看到，信任排序并不在意一條評論獲得了多少票數(shù)，它關注的是它的支持率和數(shù)據(jù)采樣規(guī)模！
排序之外的應用
正像Evan Miller所說的，Wilson’s score interval算法可以在非排名應用里使用，他列舉了3個例子：
- 檢查垃圾信息：看過這條信息的人中有多大比例認為它是垃圾信息？
- 制作“最優(yōu)”排名：看過這條信息的人中有多大比例認為它是“最好的….”？
- 制作“郵件轉(zhuǎn)發(fā)”排名：看過條信息這的人中有多大比例點擊了‘Email’按鈕？
使用這個算法你只需要兩個數(shù)據(jù)：
- 取樣總數(shù)
- 支持數(shù)
這個算法是如此有效，但很奇怪很多的網(wǎng)站如今仍然是最原始的評級方法，這包括著名的亞馬遜，它仍然使用“得分 = 支持票 / 總票數(shù)”。
英文原文：How Reddit ranking algorithms work
譯文鏈接：http://www.aqee.net/how-reddit-ranking-algorithms-work/
