基于用戶投票的六大排名算法研究

時間：2022-05-29 00:00:01 | 來源：網(wǎng)絡營銷

時間：2022-05-29 00:00:01 來源：網(wǎng)絡營銷

隨著互聯(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是為了防止最新的帖子導致分母過?。ㄖ赃x擇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值越大，曲線越陡峭，排名下降得越快，意味著排行榜的更新速度越快。

億企邦點評：知道了Delicious和Hacker News是算法構(gòu)成，就可以調(diào)整參數(shù)的值，以適用你自己的應用程序。

二、Reddit算法排名

對于Hacker News的排名算法，它的特點是用戶只能投贊成票，但是很多網(wǎng)站還允許用戶投反對票。就是說，除了好評以外，你還可以給某篇文章差評。如下圖的Reddit社區(qū)所示：

Reddit是美國最大的網(wǎng)上社區(qū)，它的每個帖子前面都有向上和向下的箭頭，分別表示“贊成”和“反對”。用戶點擊進行投票，Reddit根據(jù)投票結(jié)果，計算出最新的“熱點文章排行榜”。

那么怎樣才能將贊成票和反對票結(jié)合起來，計算出一段時間內(nèi)最受歡迎的文章呢？如果文章A有100張贊成票、5張反對票，文章B有1000張贊成票、950張反對票，誰應該排在前面呢？這就需要我們來仔細的分析一下Reddit排名算法的工作原理了。

Reddit的程序是開源的，使用Python語言編寫。排名算法的代碼大致如下圖所示：

這段代碼考慮了這樣幾個因素：

（1）、帖子的新舊程度t

t = 發(fā)貼時間 - 2005年12月8日7:50:50

t的單位為秒，用unix時間戳計算。不難看出，一旦帖子發(fā)表，t就是固定值，不會隨時間改變，而且帖子越新，t值越大。至于2005年12月8日，應該是Reddit成立的時間。

（2）、贊成票與反對票的差x

x = 贊成票 - 反對票

（3）、投票方向y

y是一個符號變量，表示對文章的總體看法。如果贊成票居多，y就是+1；如果反對票居多，y就是-1；如果贊成票和反對票相等，y就是0。

（4）、帖子的受肯定（否定）的程度z

z表示贊成票與反對票之間差額的絕對值。如果對某個帖子的評價，越是一邊倒，z就越大。如果贊成票等于反對票，z就等于1。

結(jié)合以上的幾個變量，我們可以得出Reddit的最終得分計算公式如下：

對于這個公式億企邦覺得又可以分成兩個部分來討論：

1、

這個部分表示，贊成票與反對票的差額z越大，得分越高。

需要注意的是，這里用的是以10為底的對數(shù)，意味著z=10可以得到1分，z=100可以得到2分。也就是說，前10個投票人與后90個投票人（乃至再后面900個投票人）的權(quán)重是一樣的，即如果一個帖子特別受到歡迎，那么越到后面投贊成票，對得分越不會產(chǎn)生影響。

當贊成票等于反對票，z=1，因此這個部分等于0，也就是不產(chǎn)生得分。

2、

這個部分表示，t越大，得分越高，即新帖子的得分會高于老帖子。它起到自動將老帖子的排名往下拉的作用。

分母的45000秒，等于12.5個小時，也就是說，后一天的帖子會比前一天的帖子多得2分。結(jié)合前一部分，可以得到結(jié)論，如果前一天的帖子在第二天還想保持原先的排名，在這一天里面，它的z值必須增加100倍（凈贊成票增加100倍）。

y的作用是產(chǎn)生加分或減分。當贊成票超過反對票時，這一部分為正，起到加分作用；當贊成票少于反對票時，這一部分為負，起到減分作用；當兩者相等，這一部分為0。這就保證了得到大量凈贊成票的文章，會排在前列；贊成票與反對票接近或相等的文章，會排在后面；得到凈反對票的文章，會排在最后（因為得分是負值）。

億企邦點評：這種算法的一個問題是，對于那些有爭議的文章（贊成票和反對票非常接近），它們不可能排到前列。假定同一時間有兩個帖子發(fā)表，文章A有1張贊成票（發(fā)帖人投的）、0張反對票，文章B有1000張贊成票、1000張反對票，那么A的排名會高于B，這顯然不合理。

結(jié)論就是，Reddit的排名，基本上由發(fā)帖時間決定，超級受歡迎的文章會排在最前面，一般性受歡迎的文章、有爭議的文章都不會很靠前。這決定了Reddit是一個符合大眾口味的社區(qū)，不是一個很激進、可以展示少數(shù)派想法的地方。

三、Stack Overflow排名算法

對于Reddit的排名算法，它的特點是用戶可以投贊成票，也可以投反對票。也就是說，除了時間因素以外，只要考慮兩個變量就夠了。

但是，還有一些特定用途的網(wǎng)站，必須考慮更多的因素。而程序員問答社區(qū)Stack Overflow，就是這樣一個網(wǎng)站。

你在上面提出各種關(guān)于編程的問題，等待別人回答。訪問者可以對你的問題進行投票（贊成票或反對票），表示這個問題是不是有價值。如下圖所示：

一旦有人回答了你的問題，其他人也可以對這個回答投票（贊成票或反對票）。

排名算法的作用是，找出某段時間內(nèi)的熱點問題，即哪些問題最被關(guān)注、得到了最多的討論。

在Stack Overflow的頁面上，每個問題前面有三個數(shù)字，分別表示問題的得分、回答的數(shù)目和該問題的瀏覽次數(shù)。以這些變量為基礎(chǔ)，就可以設計算法了。

其創(chuàng)始人之一的Jeff Atwood，曾經(jīng)在幾年前，公布過排名得分的計算公式如下：

寫成php代碼，就是下面這樣：

各個算法變量的含義如下：

1、Qviews（問題的瀏覽次數(shù)）

某個問題的瀏覽次數(shù)越多，就代表越受關(guān)注，得分也就越高。這里使用了以10為底的對數(shù)，用意是當訪問量越來越大，它對得分的影響將不斷變小。

2、Qscore（問題得分）和Qanswers（回答的數(shù)量）

首先，Qscore（問題得分）= 贊成票-反對票。如果某個問題越受到好評，排名自然應該越靠前。

Qanswers表示回答的數(shù)量，代表有多少人參與這個問題。這個值越大，得分將成倍放大。這里需要注意的是，如果無人回答，Qanswers就等于0，這時Qscore再高也沒用，意味著再好的問題，也必須有人回答，否則進不了熱點問題排行榜。

3、Ascores（回答得分）

一般來說，“回答”比“問題”更有意義。這一項的得分越高，就代表回答的質(zhì)量越高。

但是億企邦感覺，簡單加總的設計還不夠全面。這里有兩個問題。首先，一個正確的回答勝過一百個無用的回答，但是，簡單加總會導致，1個得分為100的回答與100個得分為1的回答，總得分相同。其次，由于得分會出現(xiàn)負值，因此那些特別差的回答，會拉低正確回答的得分。

4、Qage（距離問題發(fā)表的時間）和Qupdated（距離最后一個回答的時間）

改寫一下，可以看得更清楚：

Qage和Qupdated的單位都是秒。如果一個問題的存在時間越久，或者距離上一次回答的時間越久，Qage和Qupdated的值就相應增大。也就是說，隨著時間流逝，這兩個值都會越變越大，導致分母增大，因此總得分會越來越小。

億企邦點評：Stack Overflow熱點問題的排名，與參與度（Qviews和Qanswers）和質(zhì)量（Qscore和Ascores）成正比，與時間（Qage和Qupdated）成反比。

四、牛頓冷卻定律

牛頓冷卻定律原是用于物理學的，本意是指溫度高于周圍環(huán)境的物體向周圍媒質(zhì)傳遞熱量逐漸冷卻時所遵循的規(guī)律。當物體表面與周圍存在溫度差時，單位時間從單位面積散失的熱量與溫度差成正比，比例系數(shù)稱為熱傳遞系數(shù)。

但伴隨著互聯(lián)網(wǎng)信息的日益增多，這種定律也四、適用于最新文章的展示排名情況。根據(jù)用戶的投票，決定最近一段時間內(nèi)的“熱文排名”。

你可能會覺得，這是一個全新的課題。但是，實際上不是。我們可以把“熱文排名”想象成一個“自然冷卻”的過程：

1、任一時刻，網(wǎng)站中所有的文章，都有一個“當前溫度”，溫度最高的文章就排在第一位。

2、如果一個用戶對某篇文章投了贊成票，該文章的溫度就上升一度。

3、隨著時間流逝，所有文章的溫度都逐漸“冷卻”。

這樣假設的意義，在于我們可以照搬物理學的冷卻定律，使用現(xiàn)成的公式，建立“溫度”與“時間”之間的函數(shù)關(guān)系，輕松構(gòu)建一個“指數(shù)式衰減”（Exponential decay）的過程。

偉大的物理學家牛頓，早在17世紀就提出了溫度冷卻的數(shù)學公式，被后人稱作“牛頓冷卻定律”（Newton's Law of Cooling）。我們不妨就用這個定律構(gòu)建排名算法。

如果用一句話概況“牛頓冷卻定律”的話，那就是：物體的冷卻速度，與其當前溫度與室溫之間的溫差成正比。我們把它寫成數(shù)學公式就是：

解讀公式可知：

- T(t)是溫度（T）的時間（t）函數(shù)。微積分知識告訴我們，溫度變化（冷卻）的速率就是溫度函數(shù)的導數(shù)T'(t)。

- H代表室溫，T(t)-H就是當前溫度與室溫之間的溫差。由于當前溫度高于室溫，所以這是一個正值。

- 常數(shù)α（α>0）表示室溫與降溫速率之間的比例關(guān)系。前面的負號表示降溫。不同的物質(zhì)有不同的α值。

這是一個微分方程，為了計算當前溫度，需要求出T(t)的函數(shù)表達式。

第一步，改寫方程，然后等式兩邊取積分。



第二步，求出這個積分的解（c為常數(shù)項）。



第三步，假定在時刻t0，該物體的溫度是T(t0)，簡寫為T0。代入上面的方程，得到：



第四步，將上一步的C代入第二步的方程。

假定室溫H為0度，即所有物體最終都會“冷寂”，方程就可以簡化為：

上面這個方程，就是我們想要的最終結(jié)果：

本期溫度 = 上一期溫度 x exp(-(冷卻系數(shù)) x 間隔的小時數(shù))

將這個公式用在"排名算法"，就相當于（假定本期沒有增加凈贊成票）

本期得分 = 上一期得分 x exp(-(冷卻系數(shù)) x 間隔的小時數(shù))

其中，“冷卻系數(shù)”是一個你自己決定的值。如果假定一篇新文章的初始分數(shù)是100分，24小時之后“冷卻”為1分，那么可以計算得到“冷卻系數(shù)”約等于0.192。如果你想放慢“熱文排名”的更新率，“冷卻系數(shù)”就取一個較小的值，否則就取一個較大的值。

五、威爾遜區(qū)間排名算法

上述的介紹，我們已經(jīng)討論了如何給出“某個時段”的排名，比如“過去24小時最熱門的文章”。但是，很多的時候我們也需要“所有時段”的排名，比如“最受用戶好評的產(chǎn)品”等等。

這時，時間因素就不需要考慮了。那么我們該如何給出排名呢？

一種常見的錯誤算法是：得分 = 贊成票 - 反對票

假定有兩個項目，項目A是60張贊成票，40張反對票，項目B是550張贊成票，450張反對票。請問，誰應該排在前面？按照上面的公式，B會排在前面，因為它的得分（550 - 450 = 100）高于A（60 - 40 = 20）。但是實際上，B的好評率只有55%（550 / 1000），而A為60%（60 / 100），所以正確的結(jié)果應該是A排在前面。

Urban Dictionary就是這種錯誤算法的實例：

另一種常見的錯誤算法是：得分 = 贊成票 / 總票數(shù)

如果“總票數(shù)”很大，這種算法其實是對的。問題出在如果“總票數(shù)”很少，這時就會出錯。假定A有2張贊成票、0張反對票，B有100張贊成票、1張反對票。這種算法會使得A排在B前面。這顯然錯誤。

Amazon就是這種錯誤算法的實例：

那么，正確的算法是什么呢？

我們先做如下設定：

（1）、每個用戶的投票都是獨立事件。

（2）、用戶只有兩個選擇，要么投贊成票，要么投反對票。

（3）、如果投票總?cè)藬?shù)為n，其中贊成票為k，那么贊成票的比例p就等于k/n。

如果你熟悉統(tǒng)計學，可能已經(jīng)看出來了，這是一種統(tǒng)計分布，叫做“二項分布”（binomial distribution）。這很重要，下面馬上要用到。

我們的思路是，p越大，就代表這個項目的好評比例越高，越應該排在前面。但是，p的可信性，取決于有多少人投票，如果樣本太小，p就不可信。好在我們已經(jīng)知道，p是“二項分布”中某個事件的發(fā)生概率，因此我們可以計算出p的置信區(qū)間。所謂“置信區(qū)間”，就是說，以某個概率而言，p會落在的那個區(qū)間。比如，某個產(chǎn)品的好評率是80%，但是這個值不一定可信。根據(jù)統(tǒng)計學，我們只能說，有95%的把握可以斷定，好評率在75%到85%之間，即置信區(qū)間是[75%, 85%]。

這樣一來，排名算法就比較清晰了：

第一步，計算每個項目的“好評率”（即贊成票的比例）。

第二步，計算每個“好評率”的置信區(qū)間（以95%的概率）。

第三步，根據(jù)置信區(qū)間的下限值，進行排名。這個值越大，排名就越高。

這樣做的原理是，置信區(qū)間的寬窄與樣本的數(shù)量有關(guān)。比如，A有8張贊成票，2張反對票；B有80張贊成票，20張反對票。這兩個項目的贊成票比例都是80%，但是B的置信區(qū)間（假定[75%, 85%]）會比A的置信區(qū)間（假定[70%, 90%]）窄得多，因此B的置信區(qū)間的下限值（75%）會比A（70%）大，所以B應該排在A前面。

置信區(qū)間的實質(zhì)，就是進行可信度的修正，彌補樣本量過小的影響。如果樣本多，就說明比較可信，不需要很大的修正，所以置信區(qū)間會比較窄，下限值會比較大；如果樣本少，就說明不一定可信，必須進行較大的修正，所以置信區(qū)間會比較寬，下限值會比較小。

二項分布的置信區(qū)間有多種計算公式，最常見的是"正態(tài)區(qū)間"（Normal approximation interval），教科書里幾乎都是這種方法。但是，它只適用于樣本較多的情況（np > 5 且 n(1 ? p) > 5），對于小樣本，它的準確性很差。

1927年，美國數(shù)學家Edwin Bidwell Wilson提出了一個修正公式，被稱為“威爾遜區(qū)間”，很好地解決了小樣本的準確性問題。

在上面的公式中，表示樣本的“贊成票比例”，n表示樣本的大小，表示對應某個置信水平的z統(tǒng)計量，這是一個常數(shù)，可以通過查表或統(tǒng)計軟件包得到。一般情況下，在95%的置信水平下，z統(tǒng)計量的值為1.96。

威爾遜置信區(qū)間的均值為：

它的下限值為：

可以看到，當n的值足夠大時，這個下限值會趨向。如果n非常小（投票人很少），這個下限值會大大小于。實際上，起到了降低“贊成票比例”的作用，使得該項目的得分變小、排名下降。

六、貝葉斯平均

或許會有人質(zhì)疑說：“威爾遜區(qū)間”雖然它解決了投票人數(shù)過少、導致結(jié)果不可信的問題。比如：如果只有2個人投票，“威爾遜區(qū)間”的下限值會將贊成票的比例大幅拉低。這樣做固然保證了排名的可信性，但也帶來了另一個問題：排行榜前列總是那些票數(shù)最多的項目，新項目或者冷門的項目，很難有出頭機會，排名可能會長期靠后。

我們暫時以IMDB為例，它是目前世界上比較大的電影數(shù)據(jù)庫，觀眾可以對每部電影投票，最低為1分，最高為10分。

系統(tǒng)根據(jù)投票結(jié)果，計算出每部電影的平均得分。然后，再根據(jù)平均得分，排出最受歡迎的前250名的電影。

這里就有一個問題：熱門電影與冷門電影的平均得分，是否真的可比？舉例來說，一部好萊塢大片有10000個觀眾投票，一部小成本的文藝片只有100個觀眾投票。這兩者的投票結(jié)果，怎么比較？如果使用“威爾遜區(qū)間”，后者的得分將被大幅拉低，這樣處理是否公平，能不能反映它們真正的質(zhì)量？

一個合理的思路是，如果要比較兩部電影的好壞，至少應該請同樣多的觀眾觀看和評分。既然文藝片的觀眾人數(shù)偏少，那么應該設法為它增加一些觀眾。

在排名頁面的底部，IMDB給出了它的計算方法。

- WR， 加權(quán)得分（weighted rating）。

- R，該電影的用戶投票的平均得分（Rating）。

- v，該電影的投票人數(shù)（votes）。

- m，排名前250名的電影的最低投票數(shù)（現(xiàn)在為3000）。

- C， 所有電影的平均得分（現(xiàn)在為6.9）。

仔細研究這個公式，你會發(fā)現(xiàn)，IMDB為每部電影增加了3000張選票，并且這些選票的評分都為6.9。這樣做的原因是，假設所有電影都至少有3000張選票，那么就都具備了進入前250名的評選條件；然后假設這3000張選票的評分是所有電影的平均得分（即假設這部電影具有平均水準）；最后，用現(xiàn)有的觀眾投票進行修正，長期來看，v/(v+m)這部分的權(quán)重將越來越大，得分將慢慢接近真實情況。

這樣做拉近了不同電影之間投票人數(shù)的差異，使得投票人數(shù)較少的電影也有可能排名前列。

把這個公式寫成更一般的形式：

- C，投票人數(shù)擴展的規(guī)模，是一個自行設定的常數(shù)，與整個網(wǎng)站的總體用戶人數(shù)有關(guān)，可以等于每個項目的平均投票數(shù)。

- n，該項目的現(xiàn)有投票人數(shù)。

- x，該項目的每張選票的值。

- m，總體平均分，即整個網(wǎng)站所有選票的算術(shù)平均值。

這種算法被稱為“貝葉斯平均”（Bayesian average）。因為某種程度上，它借鑒了“貝葉斯推斷”（Bayesian inference）的思想：既然不知道投票結(jié)果，那就先估計一個值，然后不斷用新的信息修正，使得它越來越接近正確的值。

在這個公式中，m（總體平均分）是“先驗概率”，每一次新的投票都是一個調(diào)整因子，使總體平均分不斷向該項目的真實投票結(jié)果靠近。投票人數(shù)越多，該項目的“貝葉斯平均”就越接近算術(shù)平均，對排名的影響就越小。

因此，這種方法可以給一些投票人數(shù)較少的項目，以相對公平的排名。

億企邦點評：其實“貝葉斯平均”也是有缺點的，主要問題是它假設用戶的投票是正態(tài)分布。比如，電影A有10個觀眾評分，5個為五星，5個為一星；電影B也有10個觀眾評分，都給了三星。這兩部電影的平均得分（無論是算術(shù)平均，還是貝葉斯平均）都是三星，但是實際上電影A可能比電影B更值得看。

對于這個問題的解決思路，億企邦認為可以假定每個用戶的投票都是獨立事件，每次投票只有n個選項可以選擇，那么這就服從“多項分布”（Multinomial distribution），就可以結(jié)合貝葉斯定理，估計該分布的期望值。由于這涉及復雜的統(tǒng)計學知識，本文就不深入解答了，感興趣的朋友可以多多關(guān)注億企邦，我會逐步的跟大家解答這些問題的。