大數(shù)據(jù)計(jì)數(shù)原理1+0=1這你都不會(huì)算(七)
今天的干貨，不是一般的干，噎死人那種干。沒下面這些準(zhǔn)備的話直接退出吧，回去度娘啊谷哥啊弄懂是什么東西再回來。
知識(shí)儲(chǔ)備必須有這些：
BitMap知識(shí)。概率論二項(xiàng)分布。泰勒展開。函數(shù)求極限。求期望值。求方差、標(biāo)準(zhǔn)差。log對(duì)數(shù)變換。極大似然估計(jì)。
照例甩一波鏈接。
大數(shù)據(jù)計(jì)數(shù)原理1+0=1這你都不會(huì)算(一)
大數(shù)據(jù)計(jì)數(shù)原理1+0=1這你都不會(huì)算(二)
大數(shù)據(jù)計(jì)數(shù)原理1+0=1這你都不會(huì)算(三)
大數(shù)據(jù)計(jì)數(shù)原理1+0=1這你都不會(huì)算(四)
大數(shù)據(jù)計(jì)數(shù)原理1+0=1這你都不會(huì)算(五)
大數(shù)據(jù)計(jì)數(shù)原理1+0=1這你都不會(huì)算(六)
來了喔。
真的來了喔。
我們先定義幾個(gè)代數(shù)。
整個(gè)BitMap 有m個(gè)坑，還要有u個(gè)坑還沒被占。我們已經(jīng)假設(shè)了值經(jīng)過 Hash 后近似服從獨(dú)立均勻分布。
對(duì)事件進(jìn)行定義：
A = “經(jīng)過n個(gè)元素進(jìn)行Hash后，第j個(gè)桶值為0”
則A出現(xiàn)的概率如上。意思就是坑為1的概率都是1/m，那么坑為0的概率為 (1 - 1/m)，如此重復(fù)n次 ，就得到上面的式子了。
又因?yàn)槊總€(gè)桶都是獨(dú)立的，所以整個(gè)BitMap的期望值為A的概率直接乘以m。
做一個(gè)小小的trick(小把戲)變換，也就是強(qiáng)行把內(nèi)部滿足某個(gè)求極限的式子。喏，這個(gè)。
當(dāng)m和n都趨向于無窮大的時(shí)候，求一下極限，就得到了這個(gè)
這個(gè)是有u個(gè)坑的估計(jì)，而我們想知道的是基數(shù)n，做一下log變換。
根據(jù)極大似然估計(jì)的判定定理。
既然
是可逆的，那么這樣我們就得到了下面這個(gè)估計(jì)了。
好了，剛剛我們已經(jīng)得到期望，現(xiàn)在我們求一下方差和比率t的方差和期望，后面有用，至于怎么求的，自行找一下怎么求。
我們定義一下函數(shù)f。
然后對(duì)
進(jìn)行泰勒展開，得到下面這串玩意。
取前三項(xiàng)。原論文里說，因?yàn)榈诙?xiàng)展開的期望為0，所以保留前三項(xiàng)，求期望得到
代入前面求到的期望值，化簡可以得到。
所以直接除于n，可以得到偏差比率為：
至此，偏差比率的推導(dǎo)就完成啦，能看到這里的都是大神，說實(shí)話。
那標(biāo)準(zhǔn)差又是怎么樣的呢?
還是它，泰勒展開。
這里啟發(fā)性地取前兩項(xiàng)。
一步一步推導(dǎo)下來，再配合前面求的方差，嗯相信你可以的。
所以標(biāo)準(zhǔn)差就是這樣。
至此，原理，偏差率，標(biāo)準(zhǔn)差都推導(dǎo)完畢，但是還有一點(diǎn)點(diǎn)問題。就是，這樣去算有什么條件呢，對(duì)于m的取值?啟發(fā)性地取泰勒展開前三項(xiàng)和前兩項(xiàng)又分別代表什么?這個(gè)大家自己去論文看，我要是開心，我可能也會(huì)說說看。
是不是很干貨?我也知道很干，但是真的要細(xì)細(xì)閱讀，讀完***搭配上原始論文好好看一下，我看了蠻久的說實(shí)話。
好了睡覺了。要是覺得很干就點(diǎn)個(gè)贊吧，讓我知道還有人在看。
【本文為51CTO專欄作者“大蕉”的原創(chuàng)稿件，轉(zhuǎn)載請(qǐng)通過作者微信公眾號(hào)“一名叫大蕉的程序員”獲取授權(quán)】
