基于用戶投票的六大排名算法研究
分享
評論
贊0
隨著互聯(lián)網(wǎng)的發(fā)展，網(wǎng)站的數(shù)量也在隨著成倍的增加著，就中國的互聯(lián)網(wǎng)來說，根據(jù)中國互聯(lián)網(wǎng)信息中心的數(shù)據(jù)顯示，目前中國的網(wǎng)站數(shù)量每半年都會以接近10%的數(shù)量增長。這些大量的網(wǎng)站涌現(xiàn)，也就意味著我們已進入了 信息大爆炸 的時代。
而如今用戶擔心的已不再是信息太少，而是信息太多。如何從大量信息之中，快速有效地找出最重要的內(nèi)容，成了互聯(lián)網(wǎng)的一大核心問題。所以各種各樣的排名算法，已成為目前過濾信息的主要手段之一，尤其是搜索引擎的排名。在對信息進行排名的同時，也就意味著將信息按照重要性依次排列，并且及時進行更新。排列的依據(jù)，可以基于信息本身的特征，也可以基于用戶的投票，即讓用戶決定，什么樣的信息可以排在第一位。
下面，我將借助博客的平臺整理和分析一些基于用戶投票的排名算法，跟大家共同分享一下：
一、Delicious和Hacker News排名算法
1、Delicious排名算法
Delicious是提供了一種簡單共享網(wǎng)頁的方法，它為無數(shù)互聯(lián)網(wǎng)用戶提供共享及分類他們喜歡的網(wǎng)頁書簽。
對于最初的信息排名來說，最直覺、最簡單的算法，莫過于按照單位時間內(nèi)用戶的投票數(shù)進行排名。得票最多的項目，自然就排在第一位。
舊版的Delicious，有一個 熱門書簽排行榜 ，就是這樣統(tǒng)計出來的，如下圖所示：
它按照 過去60分鐘內(nèi)被收藏的次數(shù) 進行排名。每過60分鐘，就統(tǒng)計一次。
Delicious算法的優(yōu)點是：比較簡單、容易部署、內(nèi)容更新相當快；
Delicious算法的缺點是：一方面，排名變化不夠平滑，前一個小時還排名靠前的內(nèi)容，往往第二個小時就一落千丈，另一方面，缺乏自動淘汰舊項目的機制，某些熱門內(nèi)容可能會長期占據(jù)排行榜前列。
2、Hacker News排名算法
Hacker News是一個網(wǎng)絡社區(qū)，可以張貼鏈接，或者討論某個主題，如下圖所示：
每個帖子前面有一個向上的三角形，如果你覺得這個內(nèi)容很好，就點擊一下，投上一票。根據(jù)得票數(shù)，系統(tǒng)自動統(tǒng)計出熱門文章排行榜。但是，并非得票最多的文章排在第一位，還要考慮時間因素，新文章應該比舊文章更容易得到好的排名。
Hacker News使用Paul Graham開發(fā)的Arc語言編寫。它的排名算法的實現(xiàn)的方法如下圖所示：
將上面的代碼還原為數(shù)學公式就是：
P表示帖子的得票數(shù)，減去1是為了忽略發(fā)帖人的投票。
T表示距離發(fā)帖的時間（單位為小時），加上2是為了防止最新的帖子導致分母過小（之所以選擇2，可能是因為從原始文章出現(xiàn)在其他網(wǎng)站，到轉(zhuǎn)貼至Hacker News，平均需要兩個小時）。
G表示 重力因子 （gravityth power），即將帖子排名往下拉的力量，默認值為1.8，后文會詳細討論這個值。
從這個公式來看，決定帖子排名有三個因素：
第一個因素是得票數(shù)P
在其他條件不變的情況下，得票越多，排名越高，如下圖所示：
從上圖可以看到，有三個同時發(fā)表的帖子，得票分別為200票、60票和30票（減1后為199、59和29），分別以黃色、紫色和藍色表示。在任一個時間點上，都是黃色曲線在最上方，藍色曲線在最下方。
如果你不想讓 高票帖子 與 低票帖子 的差距過大，可以在得票數(shù)上加一個小于1的指數(shù)，比如(P-1)^0.8。
第二個因素是距離發(fā)帖的時間T
在其他條件不變的情況下，越是新發(fā)表的帖子，排名越高。或者說，一個帖子的排名，會隨著時間不斷下降。
從前一張圖可以看到，經(jīng)過24小時之后，所有帖子的得分基本上都小于1，這意味著它們都將跌到排行榜的末尾，保證了排名前列的都將是較新的內(nèi)容。
第三個因素是重力因子G
它的數(shù)值大小決定了排名隨時間下降的速度。
從上圖可以看到，三根曲線的其他參數(shù)都一樣，G的值分別為1.5、1.8和2.0。G值越大，曲線越陡峭，排名下降得越快，意味著排行榜的更新速度越快。
猜你喜歡
評論(0人參與，0條評論)
發(fā)布評論
最新評論