本文為學(xué)習(xí)阮一峰《基于用戶投票的排名算法》的學(xué)習(xí)筆記娘侍。
一、Hacker News(只有贊成票)
① 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)色曲線在最下方。
從上圖可以看到肮蛹,三根曲線的其他參數(shù)都一樣刻帚,G的值分別為1.5潦嘶、1.8和2.0。G值越大崇众,曲線越陡峭掂僵,排名下降得越快,意味著排行榜的更新速度越快顷歌。
二锰蓬、Reddit(贊成票與反對票)
① 帖子的新舊程度t = 發(fā)貼時(shí)間 - 建站時(shí)間
② 贊成票與反對票的差x = 贊成票 - 反對票
④ 帖子的受肯定程度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ù)投贊成或反對)
① Qviews(問題的瀏覽次數(shù))
這里使用了以 10 為底的對數(shù)饲握,用意是當(dāng)訪問量越來越大私杜,它對得分的影響將不斷變小。
Qscore(問題得分)= 贊成票-反對票互拾。如果某個(gè)問題越受到好評,排名自然應(yīng)該越靠前嚎幸。Qanswers 表示回答的數(shù)量颜矿,代表有多少人參與這個(gè)問題。這個(gè)值越大嫉晶,得分將成倍放大骑疆。
③ Ascores(回答得分)
"回答"比"問題"更有意義。這一項(xiàng)的得分越高替废,就代表回答的質(zhì)量越高箍铭。
隨著時(shí)間流逝,這兩個(gè)值都會越變越大椎镣,導(dǎo)致分母增大诈火,因此總得分會越來越小。
⑤ Stack Overflow 熱點(diǎn)問題的排名状答,與參與度(Qviews 和 Qanswers)和質(zhì)量(Qscore 和 Ascores)成正比冷守,與時(shí)間(Qage 和 Qupdated)成反比。
四惊科、牛頓冷卻定律
假定室溫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ì)算公式:
六兵罢、貝葉斯平均
解決:排行榜前列總是那些票數(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/