新型SEO思維就是從一個全新的層次上提升seo優化的水平,達到網絡信息最佳化的展示效果!
我叫mt4国服第一盗贼 > SEO優化 > SEO研究院 > 基于用戶投票的六大排名算法研究

我叫mt4803:基于用戶投票的六大排名算法研究

時間:2013-12-28   文章來源:馬海祥博客   訪問次數:

我叫mt4国服第一盗贼 www.nijqb.icu 隨著互聯網的發展,網站的數量也在隨著成倍的增加著,就中國的互聯網來說,根據中國互聯網信息中心的數據顯示,目前中國的網站數量每半年都會以接近10%的數量增長。這些大量的網站涌現,也就意味著我們已進入了“信息大爆炸”的時代。

而如今用戶擔心的已不再是信息太少,而是信息太多。如何從大量信息之中,快速有效地找出最重要的內容,成了互聯網的一大核心問題。所以各種各樣的排名算法,已成為目前過濾信息的主要手段之一,尤其是搜索引擎的排名。在對信息進行排名的同時,也就意味著將信息按照重要性依次排列,并且及時進行更新。排列的依據,可以基于信息本身的特征,也可以基于用戶的投票,即讓用戶決定,什么樣的信息可以排在第一位。

基于用戶投票的六大排名算法研究-馬海祥博客

下面,我將借助馬海祥博客的平臺整理和分析一些基于用戶投票的排名算法,跟大家共同分享一下:

一、Delicious和Hacker News排名算法

1、Delicious排名算法

Delicious是提供了一種簡單共享網頁的方法,它為無數互聯網用戶提供共享及分類他們喜歡的網頁書簽。

對于最初的信息排名來說,最直覺、最簡單的算法,莫過于按照單位時間內用戶的投票數進行排名。得票最多的項目,自然就排在第一位。

舊版的Delicious,有一個“熱門書簽排行榜”,就是這樣統計出來的,如下圖所示:

基于用戶投票的六大排名算法研究-馬海祥博客

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

Delicious算法的優點是:比較簡單、容易部署、內容更新相當快;

Delicious算法的缺點是:一方面,排名變化不夠平滑,前一個小時還排名靠前的內容,往往第二個小時就一落千丈,另一方面,缺乏自動淘汰舊項目的機制,某些熱門內容可能會長期占據排行榜前列。

2、Hacker News排名算法

Hacker News是一個網絡社區,可以張貼鏈接,或者討論某個主題,如下圖所示:

基于用戶投票的六大排名算法研究-馬海祥博客

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

Hacker News使用Paul Graham開發的Arc語言編寫。它的排名算法的實現的方法如下圖所示:

基于用戶投票的六大排名算法研究-馬海祥博客

將上面的代碼還原為數學公式就是:

基于用戶投票的六大排名算法研究-馬海祥博客

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

T表示距離發帖的時間(單位為小時),加上2是為了防止最新的帖子導致分母過?。ㄖ匝≡?,可能是因為從原始文章出現在其他網站,到轉貼至Hacker News,平均需要兩個小時)。

G表示"重力因子"(gravityth power),即將帖子排名往下拉的力量,默認值為1.8,后文會詳細討論這個值。

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

第一個因素是得票數P

在其他條件不變的情況下,得票越多,排名越高,如下圖所示:

基于用戶投票的六大排名算法研究-馬海祥博客

從上圖可以看到,有三個同時發表的帖子,得票分別為200票、60票和30票(減1后為199、59和29),分別以黃色、紫色和藍色表示。在任一個時間點上,都是黃色曲線在最上方,藍色曲線在最下方。

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

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

在其他條件不變的情況下,越是新發表的帖子,排名越高?;蛘咚?,一個帖子的排名,會隨著時間不斷下降。

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

第三個因素是重力因子G

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

基于用戶投票的六大排名算法研究-馬海祥博客

從上圖可以看到,三根曲線的其他參數都一樣,G的值分別為1.5、1.8和2.0。G值越大,曲線越陡峭,排名下降得越快,意味著排行榜的更新速度越快。

馬海祥博客點評:知道了Delicious和Hacker News是算法構成,就可以調整參數的值,以適用你自己的應用程序。

二、Reddit算法排名

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

基于用戶投票的六大排名算法研究-馬海祥博客

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

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

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

基于用戶投票的六大排名算法研究-馬海祥博客

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

(1)、帖子的新舊程度t

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

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

(2)、贊成票與反對票的差x

x = 贊成票 - 反對票

(3)、投票方向y

基于用戶投票的六大排名算法研究-馬海祥博客

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

(4)、帖子的受肯定(否定)的程度z

基于用戶投票的六大排名算法研究-馬海祥博客

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

結合以上的幾個變量,我們可以得出Reddit的最終得分計算公式如下:

基于用戶投票的六大排名算法研究-馬海祥博客

對于這個公式馬海祥覺得又可以分成兩個部分來討論:

1、基于用戶投票的六大排名算法研究-馬海祥博客

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

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

當贊成票等于反對票,z=1,因此這個部分等于0,也就是不產生得分。

2、基于用戶投票的六大排名算法研究-馬海祥博客

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

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

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

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

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

三、Stack Overflow排名算法

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

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

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

基于用戶投票的六大排名算法研究-馬海祥博客

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

基于用戶投票的六大排名算法研究-馬海祥博客

排名算法的作用是,找出某段時間內的熱點問題,即哪些問題最被關注、得到了最多的討論。

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

基于用戶投票的六大排名算法研究-馬海祥博客

其創始人之一的Jeff Atwood,曾經在幾年前,公布過排名得分的計算公式如下:

基于用戶投票的六大排名算法研究-馬海祥博客

寫成php代碼,就是下面這樣:

基于用戶投票的六大排名算法研究-馬海祥博客

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

1、Qviews(問題的瀏覽次數)

基于用戶投票的六大排名算法研究-馬海祥博客

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

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

基于用戶投票的六大排名算法研究-馬海祥博客

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

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

3、Ascores(回答得分)

基于用戶投票的六大排名算法研究-馬海祥博客

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

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

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

基于用戶投票的六大排名算法研究-馬海祥博客

改寫一下,可以看得更清楚:

基于用戶投票的六大排名算法研究-馬海祥博客

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

馬海祥博客點評:Stack Overflow熱點問題的排名,與參與度(Qviews和Qanswers)和質量(Qscore和Ascores)成正比,與時間(Qage和Qupdated)成反比。

四、牛頓冷卻定律

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

但伴隨著互聯網信息的日益增多,這種定律也四、適用于最新文章的展示排名情況。根據用戶的投票,決定最近一段時間內的“熱文排名”。

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

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

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

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

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

基于用戶投票的六大排名算法研究-馬海祥博客

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

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

基于用戶投票的六大排名算法研究-馬海祥博客

解讀公式可知:

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

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

- 常數α(α>0)表示室溫與降溫速率之間的比例關系。前面的負號表示降溫。不同的物質有不同的α值。

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

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

基于用戶投票的六大排名算法研究-馬海祥博客

基于用戶投票的六大排名算法研究-馬海祥博客

第二步,求出這個積分的解(c為常數項)。

基于用戶投票的六大排名算法研究-馬海祥博客

基于用戶投票的六大排名算法研究-馬海祥博客

基于用戶投票的六大排名算法研究-馬海祥博客

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

基于用戶投票的六大排名算法研究-馬海祥博客

基于用戶投票的六大排名算法研究-馬海祥博客

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

基于用戶投票的六大排名算法研究-馬海祥博客

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

基于用戶投票的六大排名算法研究-馬海祥博客

上面這個方程,就是我們想要的最終結果:

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

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

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

基于用戶投票的六大排名算法研究-馬海祥博客

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

五、威爾遜區間排名算法

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

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

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

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

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

基于用戶投票的六大排名算法研究-馬海祥博客

另一種常見的錯誤算法是:得分 = 贊成票 / 總票數

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

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

基于用戶投票的六大排名算法研究-馬海祥博客

那么,正確的算法是什么呢?

我們先做如下設定:

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

(2)、用戶只有兩個選擇,要么投贊成票,要么投反對票。

(3)、如果投票總人數為n,其中贊成票為k,那么贊成票的比例p就等于k/n。

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

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

這樣一來,排名算法就比較清晰了:

第一步,計算每個項目的“好評率”(即贊成票的比例)。

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

第三步,根據置信區間的下限值,進行排名。這個值越大,排名就越高。

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

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

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

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

基于用戶投票的六大排名算法研究-馬海祥博客

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

威爾遜置信區間的均值為:

基于用戶投票的六大排名算法研究-馬海祥博客

它的下限值為:

基于用戶投票的六大排名算法研究-馬海祥博客

可以看到,當n的值足夠大時,這個下限值會趨向。如果n非常?。ㄍ鍍比撕萇伲?,這個下限值會大大小于。實際上,起到了降低“贊成票比例”的作用,使得該項目的得分變小、排名下降。

六、貝葉斯平均

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

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

系統根據投票結果,計算出每部電影的平均得分。然后,再根據平均得分,排出最受歡迎的前250名的電影。

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

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

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

基于用戶投票的六大排名算法研究-馬海祥博客

- WR, 加權得分(weighted rating)。

- R,該電影的用戶投票的平均得分(Rating)。

- v,該電影的投票人數(votes)。

- m,排名前250名的電影的最低投票數(現在為3000)。

- C, 所有電影的平均得分(現在為6.9)。

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

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

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

基于用戶投票的六大排名算法研究-馬海祥博客

- C,投票人數擴展的規模,是一個自行設定的常數,與整個網站的總體用戶人數有關,可以等于每個項目的平均投票數。

- n,該項目的現有投票人數。

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

- m,總體平均分,即整個網站所有選票的算術平均值。

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

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

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

馬海祥博客點評:其實“貝葉斯平均”也是有缺點的,主要問題是它假設用戶的投票是正態分布。比如,電影A有10個觀眾評分,5個為五星,5個為一星;電影B也有10個觀眾評分,都給了三星。這兩部電影的平均得分(無論是算術平均,還是貝葉斯平均)都是三星,但是實際上電影A可能比電影B更值得看。

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

本文為我叫mt4国服第一盗贼原創文章,如想轉載,請注明原文網址摘自于//www.nijqb.icu/seoyjy/366.html,注明出處;否則,禁止轉載;謝謝配合!

相關熱詞搜索: 排名算法 用戶投票 排名算法研究 用戶投票算法

上一篇:網站運營的八大SEO策略
下一篇:盤點2013年百度搜索引擎的重大變更

今日話題更多>

SEO研究院 更多 >>