基于用戶投票的排名算法之Delicious和Hacker News
互聯(lián)網(wǎng)的出現(xiàn)，意味著"信息大爆炸"。
用戶擔(dān)心的，不再是信息太少，而是信息太多。如何從大量信息之中，快速有效地找出最重要的內(nèi)容，成了互聯(lián)網(wǎng)的一大核心問(wèn)題。
各種各樣的排名算法，是目前過(guò)濾信息的主要手段之一。對(duì)信息進(jìn)行排名，意味著將信息按照重要性依次排列，并且及時(shí)進(jìn)行更新。排列的依據(jù)，可以基于信息本身的特征，也可以基于用戶的投票，即讓用戶決定，什么樣的信息可以排在第一位。
下面，我將整理和分析一些基于用戶投票的排名算法，打算分成四個(gè)部分連載，今天是第一篇。
一、Delicious
最直覺(jué)、最簡(jiǎn)單的算法，莫過(guò)于按照單位時(shí)間內(nèi)用戶的投票數(shù)進(jìn)行排名。得票最多的項(xiàng)目，自然就排在第一位。
舊版的Delicious，有一個(gè)"熱門書簽排行榜"，就是這樣統(tǒng)計(jì)出來(lái)的。
它按照"過(guò)去60分鐘內(nèi)被收藏的次數(shù)"進(jìn)行排名。每過(guò)60分鐘，就統(tǒng)計(jì)一次。
這個(gè)算法的優(yōu)點(diǎn)是比較簡(jiǎn)單、容易部署、內(nèi)容更新相當(dāng)快;缺點(diǎn)是排名變化不夠平滑，前一個(gè)小時(shí)還排在前列的內(nèi)容，往往第二個(gè)小時(shí)就一落千丈。
二、Hacker News
Hacker News是一個(gè)網(wǎng)絡(luò)社區(qū)，可以張貼鏈接，或者討論某個(gè)主題。
每個(gè)帖子前面有一個(gè)向上的三角形，如果你覺(jué)得這個(gè)內(nèi)容很好，就點(diǎn)擊一下，投上一票。根據(jù)得票數(shù)，系統(tǒng)自動(dòng)統(tǒng)計(jì)出熱門文章排行榜。但是，并非得票最多的文章排在第一位，還要考慮時(shí)間因素，新文章應(yīng)該比舊文章更容易得到好的排名。
Hacker News使用Paul Graham開(kāi)發(fā)的Arc語(yǔ)言編寫，源碼可以從arclanguage.org下載。它的排名算法是這樣實(shí)現(xiàn)的：
將上面的代碼還原為數(shù)學(xué)公式：
其中，
P表示帖子的得票數(shù)，減去1是為了忽略發(fā)帖人的投票。
T表示距離發(fā)帖的時(shí)間(單位為小時(shí))，加上2是為了防止最新的帖子導(dǎo)致分母過(guò)小(之所以選擇2，可能是因?yàn)閺脑嘉恼鲁霈F(xiàn)在其他網(wǎng)站，到轉(zhuǎn)貼至Hacker News，平均需要兩個(gè)小時(shí))。
G表示"重力因子"(gravityth power)，即將帖子排名往下拉的力量，默認(rèn)值為1.8，后文會(huì)詳細(xì)討論這個(gè)值。
從這個(gè)公式來(lái)看，決定帖子排名有三個(gè)因素：
第一個(gè)因素是得票數(shù)P。
在其他條件不變的情況下，得票越多，排名越高。
從上圖可以看到，有三個(gè)同時(shí)發(fā)表的帖子，得票分別為200票、60票和30票(減1后為199、59和29)，分別以黃色、紫色和藍(lán)色表示。在任一個(gè)時(shí)間點(diǎn)上，都是黃色曲線在最上方，藍(lán)色曲線在最下方。
如果你不想讓"高票帖子"與"低票帖子"的差距過(guò)大，可以在得票數(shù)上加一個(gè)小于1的指數(shù)，比如(P-1)^0.8。
第二個(gè)因素是距離發(fā)帖的時(shí)間T。
在其他條件不變的情況下，越是新發(fā)表的帖子，排名越高?；蛘哒f(shuō)，一個(gè)帖子的排名，會(huì)隨著時(shí)間不斷下降。
從前一張圖可以看到，經(jīng)過(guò)24小時(shí)之后，所有帖子的得分基本上都小于1，這意味著它們都將跌到排行榜的末尾，保證了排名前列的都將是較新的內(nèi)容。
第三個(gè)因素是重力因子G。
它的數(shù)值大小決定了排名隨時(shí)間下降的速度。
從上圖可以看到，三根曲線的其他參數(shù)都一樣，G的值分別為1.5、1.8和2.0。G值越大，曲線越陡峭，排名下降得越快，意味著排行榜的更新速度越快。
知道了算法的構(gòu)成，就可以調(diào)整參數(shù)的值，以適用你自己的應(yīng)用程序。
[參考文獻(xiàn)]
原文：http://www.ruanyifeng.com/blog/2012/02/ranking_algorithm_hacker_news.html
【編輯推薦】
