天天看點

基于使用者投票的排名算法(一):Delicious和Hacker News

網際網路的出現,意味着"資訊大爆炸"。

使用者擔心的,不再是資訊太少,而是資訊太多。如何從大量資訊之中,快速有效地找出最重要的内容,成了網際網路的一大核心問題。

基于使用者投票的排名算法(一):Delicious和Hacker News

各種各樣的排名算法,是目前過濾資訊的主要手段之一。對資訊進行排名,意味着将資訊按照重要性依次排列,并且及時進行更新。排列的依據,可以基于資訊本身的特征,也可以基于使用者的投票,即讓使用者決定,什麼樣的資訊可以排在第一位。

下面,我将整理和分析一些基于使用者投票的排名算法,打算分成六個部分連載,今天是第一篇。

一、delicious

最直覺、最簡單的算法,莫過于按照機關時間内使用者的投票數進行排名。得票最多的項目,自然就排在第一位。

基于使用者投票的排名算法(一):Delicious和Hacker News

它按照"過去60分鐘内被收藏的次數"進行排名。每過60分鐘,就統計一次。

這個算法的優點是比較簡單、容易部署、内容更新相當快;缺點是,一方面,排名變化不夠平滑,前一個小時還排名靠前的内容,往往第二個小時就一落千丈,另一方面,缺乏自動淘汰舊項目的機制,某些熱門内容可能會長期占據排行榜前列。

二、hacker news

基于使用者投票的排名算法(一):Delicious和Hacker News

每個文章前面有一個向上的三角形,如果你覺得這個内容很好,就點選一下,投上一票。根據得票數,系統自動統計出熱門文章排行榜。但是,并非得票最多的文章排在第一位,還要考慮時間因素,新文章應該比舊文章更容易得到好的排名。

基于使用者投票的排名算法(一):Delicious和Hacker News

将上面的代碼還原為數學公式:

基于使用者投票的排名算法(一):Delicious和Hacker News

其中,

  p表示文章的得票數,減去1是為了忽略發帖人的投票。

  t表示距離發帖的時間(機關為小時),加上2是為了防止最新的文章導緻分母過小(之是以選擇2,可能是因為從原始文章出現在其他網站,到轉貼至hacker news,平均需要兩個小時)。

  g表示"重力因子"(gravityth power),即将文章排名往下拉的力量,預設值為1.8,後文會詳細讨論這個值。

從這個公式來看,決定文章排名有三個因素:

第一個因素是得票數p。

在其他條件不變的情況下,得票越多,排名越高。

基于使用者投票的排名算法(一):Delicious和Hacker News

如果你不想讓"高票文章"與"低票文章"的差距過大,可以在得票數上加一個小于1的指數,比如(p-1)^0.8。

第二個因素是距離發帖的時間t。

在其他條件不變的情況下,越是新發表的文章,排名越高。或者說,一個文章的排名,會随着時間不斷下降。

從前一張圖可以看到,經過24小時之後,所有文章的得分基本上都小于1,這意味着它們都将跌到排行榜的末尾,保證了排名前列的都将是較新的内容。

第三個因素是重力因子g。

它的數值大小決定了排名随時間下降的速度。

基于使用者投票的排名算法(一):Delicious和Hacker News

知道了算法的構成,就可以調整參數的值,以适用你自己的應用程式。

[參考文獻]

(完)

繼續閱讀