帖子排序算法

本文為學(xué)習(xí)阮一峰《基于用戶投票的排名算法》的學(xué)習(xí)筆記娘侍。

一、Hacker News(只有贊成票)

Hacker News排序數(shù)學(xué)公式

① P 表示帖子的得票數(shù)泳炉,減去 1 是為了忽略發(fā)帖人的投票憾筏。
② T 表示距離發(fā)帖的時(shí)間(單位為小時(shí)),加上 2 是為了防止最新的帖子導(dǎo)致分母過小花鹅。
③ G 表示"重力因子"(gravityth power)氧腰,即將帖子排名往下拉的力量,默認(rèn)值為1.8刨肃。


得分趨勢表

從上圖可以看到古拴,有三個(gè)同時(shí)發(fā)表的帖子,得票分別為 200 票真友、60票和 30 票(減 1 后為 199黄痪、59和 29),分別以黃色盔然、紫色和藍(lán)色表示桅打。在任一個(gè)時(shí)間點(diǎn)上铡羡,都是黃色曲線在最上方尾膊,藍(lán)色曲線在最下方。


調(diào)整重力因子后的得分趨勢表

從上圖可以看到肮蛹,三根曲線的其他參數(shù)都一樣刻帚,G的值分別為1.5潦嘶、1.8和2.0。G值越大崇众,曲線越陡峭掂僵,排名下降得越快,意味著排行榜的更新速度越快顷歌。

二锰蓬、Reddit(贊成票與反對票)

Reddit排序數(shù)學(xué)公式

① 帖子的新舊程度t = 發(fā)貼時(shí)間 - 建站時(shí)間
② 贊成票與反對票的差x = 贊成票 - 反對票

③ 投票方向y

④ 帖子的受肯定程度z

(一)

這表示,贊成票超過反對票的數(shù)量越多眯漩,得分越高芹扭。 前 10 個(gè)投票人與后 90 個(gè)投票人(乃至再后面 900 個(gè)投票人)的權(quán)重是一樣麻顶。
(二)

這個(gè)表示,t越大舱卡,得分越高辅肾。
分母的 45000 秒,等于 12.5 個(gè)小時(shí)轮锥,如果前一天的帖子在第二天還想保持原先的排名矫钓,在這一天里面,它得到的凈贊成票必須增加 100 倍舍杜。y 的作用是用來產(chǎn)生正分和負(fù)分新娜。
(三)對于那些有爭議的文章(贊成票和反對票非常接近),它們不可能排到前列既绩。

三概龄、Stack Overflow(對問題投贊成或反對,對回復(fù)投贊成或反對)

Stack Overflow排序數(shù)學(xué)公式

① Qviews(問題的瀏覽次數(shù))

這里使用了以 10 為底的對數(shù)饲握,用意是當(dāng)訪問量越來越大私杜,它對得分的影響將不斷變小。

② Qscore(問題得分)和 Qanswers(回答的數(shù)量)

Qscore(問題得分)= 贊成票-反對票互拾。如果某個(gè)問題越受到好評,排名自然應(yīng)該越靠前嚎幸。Qanswers 表示回答的數(shù)量颜矿,代表有多少人參與這個(gè)問題。這個(gè)值越大嫉晶,得分將成倍放大骑疆。
③ Ascores(回答得分)

"回答"比"問題"更有意義。這一項(xiàng)的得分越高替废,就代表回答的質(zhì)量越高箍铭。

④ Qage(距離問題發(fā)表的時(shí)間)和 Qupdated(距離最后一個(gè)回答的時(shí)間)

隨著時(shí)間流逝,這兩個(gè)值都會越變越大椎镣,導(dǎo)致分母增大诈火,因此總得分會越來越小。
⑤ Stack Overflow 熱點(diǎn)問題的排名状答,與參與度(Qviews 和 Qanswers)和質(zhì)量(Qscore 和 Ascores)成正比冷守,與時(shí)間(Qage 和 Qupdated)成反比。

四惊科、牛頓冷卻定律

牛頓冷卻定律 數(shù)學(xué)公式

假定室溫H為 0 度拍摇,即所有物體最終都會"冷寂",方程就可以簡化為
簡化后的牛頓冷卻定律

本期溫度 = 上一期溫度 x exp (-(冷卻系數(shù)) x 間隔的小時(shí)數(shù))
將這個(gè)公式用在"排名算法"馆截,就相當(dāng)于(假定本期沒有增加凈贊成票)
本期得分 = 上一期得分 x exp (-(冷卻系數(shù)) x 間隔的小時(shí)數(shù))
如果假定一篇新文章的初始分?jǐn)?shù)是 100 分充活,24小時(shí)之后"冷卻"為 1 分蜂莉,那么可以計(jì)算得到"冷卻系數(shù)"約等于0.192。如果你想放慢"熱文排名"的更新率混卵,"冷卻系數(shù)"就取一個(gè)較小的值映穗,否則就取一個(gè)較大的值。

五淮菠、威爾遜區(qū)間(不考慮時(shí)間因素)

① 錯(cuò)誤一
得分 = 贊成票 - 反對票
假定有兩個(gè)項(xiàng)目男公,項(xiàng)目A是 60 張贊成票,40張反對票合陵,項(xiàng)目B是 550 張贊成票枢赔,450張反對票。請問拥知,誰應(yīng)該排在前面踏拜?按照上面的公式,B會排在前面低剔,因?yàn)樗牡梅郑?50 - 450 = 100)高于A(60 - 40 = 20)速梗。但是實(shí)際上,B的好評率只有 55%(550 / 1000)襟齿,而A為 60%(60 / 100)姻锁,所以正確的結(jié)果應(yīng)該是A排在前面。
② 錯(cuò)誤二
得分 = 贊成票 / 總票數(shù)
 如果"總票數(shù)"很大猜欺,這種算法其實(shí)是對的位隶。問題出在如果"總票數(shù)"很少,這時(shí)就會出錯(cuò)开皿。假定A有 2 張贊成票涧黄、0張反對票,B有 100 張贊成票赋荆、1張反對票笋妥。這種算法會使得A排在B前面。這顯然錯(cuò)誤窄潭。

那么春宣,正確的算法是什么呢?
我們先做如下設(shè)定:

(1)每個(gè)用戶的投票都是獨(dú)立事件嫉你。
(2)用戶只有兩個(gè)選擇信认,要么投贊成票,要么投反對票均抽。
(3)如果投票總?cè)藬?shù)為n嫁赏,其中贊成票為k,那么贊成票的比例p就等于k/n油挥。

如果你熟悉統(tǒng)計(jì)學(xué)潦蝇,可能已經(jīng)看出來了款熬,p服從一種統(tǒng)計(jì)分布,叫做"兩項(xiàng)分布"攘乒。
p越大贤牛,就代表這個(gè)項(xiàng)目的好評比例越高,越應(yīng)該排在前面则酝。但是殉簸,p的可信性,取決于有多少人投票沽讹,如果樣本太小般卑,p就不可信。
p服從"兩項(xiàng)分布"爽雄,因此我們可以計(jì)算出p的置信區(qū)間蝠检。所謂"置信區(qū)間",就是說挚瘟,以某個(gè)概率而言叹谁,p會落在的那個(gè)區(qū)間。比如乘盖,某個(gè)產(chǎn)品的好評率是 80%焰檩,但是這個(gè)值不一定可信。根據(jù)統(tǒng)計(jì)學(xué)订框,我們只能說析苫,有 95% 的把握可以斷定,好評率在 75% 到 85% 之間布蔗,即置信區(qū)間是[75%藤违, 85%]浪腐。
排名算法:

第一步纵揍,計(jì)算每個(gè)項(xiàng)目的"好評率"(即贊成票的比例)。
第二步议街,計(jì)算每個(gè)"好評率"的置信區(qū)間(以 95% 的概率)泽谨。
第三步,根據(jù)置信區(qū)間的下限值特漩,進(jìn)行排名吧雹。這個(gè)值越大,排名就越高涂身。

這樣做的原理是雄卷,置信區(qū)間的寬窄與樣本的數(shù)量有關(guān)。比如蛤售,A有 8 張贊成票丁鹉,2張反對票妒潭;B有 80 張贊成票,20張反對票揣钦。這兩個(gè)項(xiàng)目的贊成票比例都是 80%雳灾,但是B的置信區(qū)間(假定[75%, 85%])會比A(假定[70%冯凹, 90%])窄得多谎亩,因此B的置信區(qū)間的下限值(75%)會比A(70%)大,所以B應(yīng)該排在A前面宇姚。
下限值計(jì)算公式:


下限值

在上面的公式中匈庭,

表示樣本的"贊成票比例",
表示樣本的大小空凸,
表示對應(yīng)某個(gè)置信水平的z統(tǒng)計(jì)量嚎花,這是一個(gè)常數(shù),可以通過查表或統(tǒng)計(jì)軟件包得到呀洲。一般情況下紊选,在 95% 的置信水平下,z統(tǒng)計(jì)量的值為1.96道逗。

六兵罢、貝葉斯平均

解決:排行榜前列總是那些票數(shù)最多的項(xiàng)目,新項(xiàng)目或者冷門的項(xiàng)目滓窍,很難有出頭機(jī)會卖词,排名可能會長期靠后。
舉例來說吏夯,一部好萊塢大片有 10000 個(gè)觀眾投票此蜈,一部小成本的文藝片只有 100 個(gè)觀眾投票。這兩者的投票結(jié)果噪生,怎么比較裆赵?如果使用"威爾遜區(qū)間",后者的得分將被大幅拉低跺嗽,這樣處理是否公平战授,能不能反映它們真正的質(zhì)量?


解決公式

WR桨嫁, 加權(quán)得分(weighted rating)植兰。
R,該電影的用戶投票的平均得分(Rating)璃吧。
v楣导,該電影的投票人數(shù)(votes)。
m畜挨,排名前 250 名的電影的最低投票數(shù)(現(xiàn)在為 3000)筒繁。
C彬坏, 所有電影的平均得分(現(xiàn)在為6.9)。
假設(shè)所有電影都至少有 3000 張選票膝晾,那么就都具備了進(jìn)入前 250 名的評選條件栓始;然后假設(shè)這 3000 張選票的評分是所有電影的平均得分(即假設(shè)這部電影具有平均水準(zhǔn));最后血当,用現(xiàn)有的觀眾投票進(jìn)行修正幻赚,長期來看,v/(v+m)這部分的權(quán)重將越來越大臊旭,得分將慢慢接近真實(shí)情況落恼。
把這個(gè)公式寫成更一般的形式:


一般形式

C,投票人數(shù)擴(kuò)展的規(guī)模离熏,是一個(gè)自行設(shè)定的常數(shù)佳谦,與整個(gè)網(wǎng)站的總體用戶人數(shù)有關(guān),可以等于每個(gè)項(xiàng)目的平均投票數(shù)滋戳。
n钻蔑,該項(xiàng)目的現(xiàn)有投票人數(shù)。
x奸鸯,該項(xiàng)目的每張選票的值咪笑。

m,總體平均分娄涩,即整個(gè)網(wǎng)站所有選票的算術(shù)平均值窗怒。

"貝葉斯平均"也有缺點(diǎn),主要問題是它假設(shè)用戶的投票是正態(tài)分布蓄拣。比如扬虚,電影A有 10 個(gè)觀眾評分,5個(gè)為五星球恤,5個(gè)為一星辜昵;電影B也有 10 個(gè)觀眾評分,都給了三星碎捺。這兩部電影的平均得分(無論是算術(shù)平均路鹰,還是貝葉斯平均)都是三星贷洲,但是電影A可能比電影B更值得看收厨。
  解決這個(gè)問題的思路是,假定每個(gè)用戶的投票都是獨(dú)立事件优构,每次投票只有n個(gè)選項(xiàng)可以選擇诵叁,那么這就服從"多項(xiàng)分布",就可以結(jié)合貝葉斯定理钦椭,計(jì)算該分布的期望值拧额。

更多詳細(xì)的解釋請到原文地址查看:
https://kb.cnblogs.com/page/135656/

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末碑诉,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子侥锦,更是在濱河造成了極大的恐慌进栽,老刑警劉巖,帶你破解...
    沈念sama閱讀 206,126評論 6 481
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件恭垦,死亡現(xiàn)場離奇詭異快毛,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)番挺,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 88,254評論 2 382
  • 文/潘曉璐 我一進(jìn)店門唠帝,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人玄柏,你說我怎么就攤上這事襟衰。” “怎么了粪摘?”我有些...
    開封第一講書人閱讀 152,445評論 0 341
  • 文/不壞的土叔 我叫張陵瀑晒,是天一觀的道長。 經(jīng)常有香客問我徘意,道長瑰妄,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 55,185評論 1 278
  • 正文 為了忘掉前任映砖,我火速辦了婚禮间坐,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘邑退。我一直安慰自己竹宋,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 64,178評論 5 371
  • 文/花漫 我一把揭開白布地技。 她就那樣靜靜地躺著蜈七,像睡著了一般。 火紅的嫁衣襯著肌膚如雪莫矗。 梳的紋絲不亂的頭發(fā)上飒硅,一...
    開封第一講書人閱讀 48,970評論 1 284
  • 那天,我揣著相機(jī)與錄音作谚,去河邊找鬼三娩。 笑死,一個(gè)胖子當(dāng)著我的面吹牛妹懒,可吹牛的內(nèi)容都是我干的雀监。 我是一名探鬼主播,決...
    沈念sama閱讀 38,276評論 3 399
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼会前!你這毒婦竟也來了好乐?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 36,927評論 0 259
  • 序言:老撾萬榮一對情侶失蹤瓦宜,失蹤者是張志新(化名)和其女友劉穎蔚万,沒想到半個(gè)月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體临庇,經(jīng)...
    沈念sama閱讀 43,400評論 1 300
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡笛坦,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 35,883評論 2 323
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了苔巨。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片版扩。...
    茶點(diǎn)故事閱讀 37,997評論 1 333
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖侄泽,靈堂內(nèi)的尸體忽然破棺而出礁芦,到底是詐尸還是另有隱情,我是刑警寧澤悼尾,帶...
    沈念sama閱讀 33,646評論 4 322
  • 正文 年R本政府宣布柿扣,位于F島的核電站,受9級特大地震影響闺魏,放射性物質(zhì)發(fā)生泄漏未状。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 39,213評論 3 307
  • 文/蒙蒙 一析桥、第九天 我趴在偏房一處隱蔽的房頂上張望司草。 院中可真熱鬧,春花似錦泡仗、人聲如沸埋虹。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,204評論 0 19
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽搔课。三九已至,卻和暖如春截亦,著一層夾襖步出監(jiān)牢的瞬間爬泥,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 31,423評論 1 260
  • 我被黑心中介騙來泰國打工崩瓤, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留袍啡,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 45,423評論 2 352
  • 正文 我出身青樓谷遂,卻偏偏與公主長得像葬馋,于是被迫代替她去往敵國和親卖鲤。 傳聞我的和親對象是個(gè)殘疾皇子肾扰,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 42,722評論 2 345

推薦閱讀更多精彩內(nèi)容

  • 迄今為止畴嘶,這個(gè)系列都在討論,如何給出"某個(gè)時(shí)段"的排名集晚,比如"過去24小時(shí)最熱門的文章 但是窗悯,很多場合需要的是"所...
    每有睡意便欣然忘食閱讀 3,629評論 0 0
  • 川流不息霓虹燈閃爍,窗外的夜依舊繁華如晝偷拔。 我關(guān)了燈蒋院,蜷縮在無盡黑暗。 我沒有拉上窗簾莲绰。窗子很大欺旧,窗外的顏色好多好...
    萬妍閱讀 234評論 1 1
  • 文/沈墨涼 “媽辞友,我想去整容”。 我媽聽了我這話震肮,嚇得不行称龙。 “閨女兒,雖然我和你爸給你的基因不好戳晌,沒有讓你長的傾...
    沈墨涼閱讀 835評論 6 5
  • 如果你現(xiàn)在有一下午的空余時(shí)間,你會拿來做些什么呢豪嚎? 讀書鸿捧、游玩還是睡覺、打游戲呢疙渣? 今天我想和你分享的是一段木作時(shí)...
    綠草浮生閱讀 830評論 0 0
  • 任正非新華社面對面:燒不死的鳥是鳳凰匙奴,把自己變得更加真實(shí),沙灘上房子遲早會坍塌妄荔。 扎根基礎(chǔ)研究:沙灘上的房子遲早會...
    聞方培訓(xùn)師閱讀 925評論 0 0