Reddit排名算法工作原理
這是一篇繼《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找到了它，但我懷疑他們未必是原作者)：
文章提交時間對排名的影響
文章提交時間對排名的影響可以總結為以下幾點：
- 提交時間對排名影響巨大，越新的文章排名會越高
- 文章排名得分不會隨時間的流逝而降低，但新文章會比老文章獲得更高的分。這跟Hacker News的排名算法有很大區別，它的得分會隨時間流逝而降低。
下面是一個圖片，表現的是具有相同支持和反對的票數，但時間不同的文章的排名得分情況：
對數加強
Reddit在‘熱門’排名中使用了對數函數來強化前幾票的份量。基本是這個原理：
- 前10個贊成票的份量和后面100個的份量，以及再后面1000票的份量是相同的，以此類推
下面是效果圖：
如果不使用對數加強，則分數會是這樣：
反對票對排名的影響
Reddit是少數幾個能投反對票的網站之一。就像你從代碼里看到的，一篇文章的的’得分‘定義如下：
- up_votes – down_votes
這就是說，我們可以把它表現為下圖：
這種計算方式會對既有很的贊成票，又有很多反對票的文章（比如很有爭議的文章）帶來重大影響，它們可能會比那些只有很少贊成票的文章獲得更低的分數。這也就說明了為什么小貓小狗之類的帖子(以及其它無爭議的文章)會獲得如此高的評分。
#p#
對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算法，它的數學表達式是這樣的：
在上面的公式中，各個參數的定義如下：
- 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
譯文鏈接：http://www.aqee.net/how-reddit-ranking-algorithms-work/
