,,

[點(diǎn)晴CRM客戶管理系統(tǒng)]垃圾郵件算法：貝葉斯推斷及其互聯(lián)網(wǎng)應(yīng)用

當(dāng)前位置：點(diǎn)晴教程→點(diǎn)晴CRM客戶管理信息系統(tǒng) →『經(jīng)驗(yàn)分享&問(wèn)題答疑』

admin

2012年6月20日 1:8 本文熱度 7545

　　一、什么是貝葉斯推斷

　　貝葉斯推斷（Bayesianinference）是一種統(tǒng)計(jì)學(xué)方法，用來(lái)估計(jì)統(tǒng)計(jì)量的某種性質(zhì)。

　　它是貝葉斯定理（Bayes'theorem）的應(yīng)用。英國(guó)數(shù)學(xué)家托馬斯·貝葉斯（ThomasBayes）在1763年發(fā)表的一篇論文中，首先提出了這個(gè)定理。

　　貝葉斯推斷與其他統(tǒng)計(jì)學(xué)推斷方法截然不同。它建立在主觀判斷的基礎(chǔ)上，也就是說(shuō)，你可以不需要客觀證據(jù)，先估計(jì)一個(gè)值，然后根據(jù)推斷結(jié)果不斷修正。正是因?yàn)樗闹饔^性太強(qiáng)，曾經(jīng)遭到許多統(tǒng)計(jì)學(xué)家的詬病。

　　貝葉斯推斷需要大量的計(jì)算，因此歷史上很長(zhǎng)一段時(shí)間，無(wú)法得到廣泛應(yīng)用。只有等到計(jì)算機(jī)誕生以后，它才獲得真正的重視。人們發(fā)現(xiàn)，許多統(tǒng)計(jì)量是無(wú)法事先進(jìn)行客觀判斷的，而互聯(lián)網(wǎng)時(shí)代出現(xiàn)的大型數(shù)據(jù)集，再加上高速運(yùn)算能力，為驗(yàn)證這些統(tǒng)計(jì)量提供了方便，也為應(yīng)用貝葉斯推斷創(chuàng)造了條件，它的威力正在日益顯現(xiàn)。

　　二、貝葉斯定理

　　要理解貝葉斯推斷，就必須先理解貝葉斯定理。后者實(shí)際上就是計(jì)算"條件概率"的公式。

　　所謂"條件概率"（Conditionalprobability），就是指在事件B發(fā)生的情況下，事件A發(fā)生的概率，用P(A│B)來(lái)表示。

　　根據(jù)文氏圖，可以很清楚地看到在事件B發(fā)生的情況下，事件A發(fā)生的概率就是P(A∩B)除以P(B)。

$P(A|B)=\frac{P(A\cap B)}{P(B)}$

　　因此，

$P(A\cap B)=P(A|B){P(B)}$

　　同理可得，

$P(A\cap B)=P(B|A){P(A)}$

　　所以，

$P(A|B){P(B)}=P(B|A){P(A)}$

　　即

$P(A|B)=\frac{P(B|A){P(A)}}{{P(B)}}$

　　這就是條件概率的計(jì)算公式。

　　三、全概率公式

　　由于后面要用到，所以除了條件概率以外，這里還要推導(dǎo)全概率公式。

　　假定樣本空間S，是兩個(gè)事件A與A'的和。

　　上圖中，紅色部分是事件A，綠色部分是事件A'，它們共同構(gòu)成了樣本空間S。

　　在這種情況下，事件B可以劃分成兩個(gè)部分。

　　即

$P(B)=P(B\cap A)+P(B\cap A')$

　　在上一節(jié)的推導(dǎo)當(dāng)中，我們已知

$P(B\cap A)=P(B|A)P(A)$

　　所以，

$P(B)=P(B|A)P(A)+P(B|A')P(A')$

　　這就是全概率公式。它的含義是，如果A和A'構(gòu)成樣本空間的一個(gè)劃分，那么事件B的概率，就等于A和A'的概率分別乘以B的條件概率之和。

　　將這個(gè)公式代入上一節(jié)的條件概率公式，就得到了條件概率的另一種寫(xiě)法：

$P(A|B)=\frac{P(B|A)P(A)}{P(B|A)P(A)+P(B|A')P(A')}$

　　四、貝葉斯推斷的含義

　　對(duì)條件概率公式進(jìn)行變形，可以得到如下形式：

$P(A|B)=P(A)\frac{P(B|A)}{P(B)}$

　　我們把P(A)稱為"先驗(yàn)概率"（Priorprobability），即在B事件發(fā)生之前，我們對(duì)A事件概率的一個(gè)判斷。P(A│B)稱為"后驗(yàn)概率"（Posteriorprobability），即在B事件發(fā)生之后，我們對(duì)A事件概率的重新評(píng)估。P(B│A)/P(B)稱為"可能性函數(shù)"（Likelyhood），這是一個(gè)調(diào)整因子，使得預(yù)估概率更接近真實(shí)概率。

　　所以，條件概率可以理解成下面的式子：

$\mbox{Posterior probability} \propto \mbox{Prior probability} \times \mbox{Likelihood}$

　　這就是貝葉斯推斷的含義。我們先預(yù)估一個(gè)"先驗(yàn)概率"，然后加入實(shí)驗(yàn)結(jié)果，看這個(gè)實(shí)驗(yàn)到底是增強(qiáng)還是削弱了"先驗(yàn)概率"，由此得到更接近事實(shí)的"后驗(yàn)概率"。

　　在這里，如果"可能性函數(shù)"P(B│A)/P(B)>1，意味著"先驗(yàn)概率"被增強(qiáng)，事件A的發(fā)生的可能性變大；如果"可能性函數(shù)"=1，意味著B(niǎo)事件無(wú)助于判斷事件A的可能性；如果"可能性函數(shù)"<1，意味著"先驗(yàn)概率"被削弱，事件A的可能性變小。

　　五、【例子】水果糖問(wèn)題

　　為了加深對(duì)貝葉斯推斷的理解，我們看兩個(gè)例子。

　　第一個(gè)例子。兩個(gè)一模一樣的碗，一號(hào)碗有30顆水果糖和10顆巧克力糖，二號(hào)碗有水果糖和巧克力糖各20顆。現(xiàn)在隨機(jī)選擇一個(gè)碗，從中摸出一顆糖，發(fā)現(xiàn)是水果糖。請(qǐng)問(wèn)這顆水果糖來(lái)自一號(hào)碗的概率有多大？

　　我們假定，H1表示一號(hào)碗，H2表示二號(hào)碗。由于這兩個(gè)碗是一樣的，所以P(H1)=P(H2)，也就是說(shuō)，在取出水果糖之前，這兩個(gè)碗被選中的概率相同。因此，P(H1)=0.5，我們把這個(gè)概率就叫做"先驗(yàn)概率"，即沒(méi)有做實(shí)驗(yàn)之前，來(lái)自一號(hào)碗的概率是0.5。

　　再假定，E表示水果糖，所以問(wèn)題就變成了在已知E的情況下，來(lái)自一號(hào)碗的概率有多大，即求P(H1│E)。我們把這個(gè)概率叫做"后驗(yàn)概率"，即在E事件發(fā)生之后，對(duì)P(H1)的修正。

　　根據(jù)條件概率公式，得到

$P(H_{1}|E)=P(H_{1})\frac{P(E|H_{1})}{P(E)}$

　　已知，P(H1)等于0.5，P(E│H1)為一號(hào)碗中取出水果糖的概率，等于0.75，那么求出P(E)就可以得到答案。根據(jù)全概率公式，

$P(E)=P(E|H_{1})P(H_{1})+P(E|H_{2})P(H_{2})$

　　所以，

$P(E)=0.75\times 0.5+0.5\times 0.5=0.625$

　　將數(shù)字代入原方程，得到

$P(H1|E)=0.5\times \frac{0.75}{0.625}=0.6$

　　這表明，來(lái)自一號(hào)碗的概率是0.6。也就是說(shuō)，取出水果糖之后，H1事件的可能性得到了增強(qiáng)。

　　六、【例子】假陽(yáng)性問(wèn)題

　　第二個(gè)例子是一個(gè)醫(yī)學(xué)的常見(jiàn)問(wèn)題，與現(xiàn)實(shí)生活關(guān)系緊密。

　　已知某種疾病的發(fā)病率是0.001，即1000人中會(huì)有1個(gè)人得病。現(xiàn)有一種試劑可以檢驗(yàn)患者是否得病，它的準(zhǔn)確率是0.99，即在患者確實(shí)得病的情況下，它有99%的可能呈現(xiàn)陽(yáng)性。它的誤報(bào)率是5%，即在患者沒(méi)有得病的情況下，它有5%的可能呈現(xiàn)陽(yáng)性。現(xiàn)有一個(gè)病人的檢驗(yàn)結(jié)果為陽(yáng)性，請(qǐng)問(wèn)他確實(shí)得病的可能性有多大？

　　假定A事件表示得病，那么P(A)為0.001。這就是"先驗(yàn)概率"，即沒(méi)有做試驗(yàn)之前，我們預(yù)計(jì)的發(fā)病率。再假定B事件表示陽(yáng)性，那么要計(jì)算的就是P(A│B)。這就是"后驗(yàn)概率"，即做了試驗(yàn)以后，對(duì)發(fā)病率的估計(jì)。

　　根據(jù)條件概率公式，

$P(A|B)=P(A) \frac{P(B|A)}{P(B)}$

　　用全概率公式改寫(xiě)分母，

$P(A|B)=P(A) \frac{P(B|A)}{P(B|A)P(A)+P(B|\bar{A})P(\bar{A})}$

　　將數(shù)字代入，

$P(A|B)=0.001\times \frac{0.99}{0.99\times 0.001+0.05\times 0.999}\approx 0.019$

　　我們得到了一個(gè)驚人的結(jié)果，P(A│B)約等于0.019。也就是說(shuō)，即使檢驗(yàn)呈現(xiàn)陽(yáng)性，病人得病的概率，也只是從0.1%增加到了2%左右。這就是所謂的"假陽(yáng)性"，即陽(yáng)性結(jié)果完全不足以說(shuō)明病人得病。

　　為什么會(huì)這樣？為什么這種檢驗(yàn)的準(zhǔn)確率高達(dá)99%，但是可信度卻不到2%？答案是與它的誤報(bào)率太高有關(guān)。（【習(xí)題】如果誤報(bào)率從5%降為1%，請(qǐng)問(wèn)病人得病的概率會(huì)變成多少？）

　　有興趣的朋友，還可以算一下"假陰性"問(wèn)題，即檢驗(yàn)結(jié)果為陰性，但是病人確實(shí)得病的概率有多大。然后問(wèn)自己，"假陽(yáng)性"和"假陰性"，哪一個(gè)才是醫(yī)學(xué)檢驗(yàn)的主要風(fēng)險(xiǎn)？

　　上面我們介紹了貝葉斯推斷的原理，下面講如何將它用于垃圾郵件過(guò)濾。

　　七、什么是貝葉斯過(guò)濾器？

　　垃圾郵件是一種令人頭痛的頑癥，困擾著所有的互聯(lián)網(wǎng)用戶。

　　正確識(shí)別垃圾郵件的技術(shù)難度非常大。傳統(tǒng)的垃圾郵件過(guò)濾方法，主要有"關(guān)鍵詞法"和"校驗(yàn)碼法"等。前者的過(guò)濾依據(jù)是特定的詞語(yǔ)；后者則是計(jì)算郵件文本的校驗(yàn)碼，再與已知的垃圾郵件進(jìn)行對(duì)比。它們的識(shí)別效果都不理想，而且很容易規(guī)避。

　　2002年，PaulGraham提出使用"貝葉斯推斷"過(guò)濾垃圾郵件。他說(shuō)，這樣做的效果，好得不可思議。1000封垃圾郵件可以過(guò)濾掉995封，且沒(méi)有一個(gè)誤判。

　　另外，這種過(guò)濾器還具有自我學(xué)習(xí)的功能，會(huì)根據(jù)新收到的郵件，不斷調(diào)整。收到的垃圾郵件越多，它的準(zhǔn)確率就越高。

　　八、建立歷史資料庫(kù)

　　貝葉斯過(guò)濾器是一種統(tǒng)計(jì)學(xué)過(guò)濾器，建立在已有的統(tǒng)計(jì)結(jié)果之上。所以，我們必須預(yù)先提供兩組已經(jīng)識(shí)別好的郵件，一組是正常郵件，另一組是垃圾郵件。

　　我們用這兩組郵件，對(duì)過(guò)濾器進(jìn)行"訓(xùn)練"。這兩組郵件的規(guī)模越大，訓(xùn)練效果就越好。PaulGraham使用的郵件規(guī)模，是正常郵件和垃圾郵件各4000封。

　　"訓(xùn)練"過(guò)程很簡(jiǎn)單。首先，解析所有郵件，提取每一個(gè)詞。然后，計(jì)算每個(gè)詞語(yǔ)在正常郵件和垃圾郵件中的出現(xiàn)頻率。比如，我們假定"sex"這個(gè)詞，在4000封垃圾郵件中，有200封包含這個(gè)詞，那么它的出現(xiàn)頻率就是5%；而在4000封正常郵件中，只有2封包含這個(gè)詞，那么出現(xiàn)頻率就是0.05%。（【注釋】如果某個(gè)詞只出現(xiàn)在垃圾郵件中，PaulGraham就假定，它在正常郵件的出現(xiàn)頻率是1%，反之亦然。隨著郵件數(shù)量的增加，計(jì)算結(jié)果會(huì)自動(dòng)調(diào)整。）

　　有了這個(gè)初步的統(tǒng)計(jì)結(jié)果，過(guò)濾器就可以投入使用了。

　　九、貝葉斯過(guò)濾器的使用過(guò)程

　　現(xiàn)在，我們收到了一封新郵件。在未經(jīng)統(tǒng)計(jì)分析之前，我們假定它是垃圾郵件的概率為50%。（【注釋】有研究表明，用戶收到的電子郵件中，80%是垃圾郵件。但是，這里仍然假定垃圾郵件的"先驗(yàn)概率"為50%。）

　　我們用S表示垃圾郵件（spam），H表示正常郵件（healthy）。因此，P(S)和P(H)的先驗(yàn)概率，都是50%。

$P(S)=P(H)=50%$

　　然后，對(duì)這封郵件進(jìn)行解析，發(fā)現(xiàn)其中包含了sex這個(gè)詞，請(qǐng)問(wèn)這封郵件屬于垃圾郵件的概率有多高？

　　我們用W表示"sex"這個(gè)詞，那么問(wèn)題就變成了如何計(jì)算P(S│W)的值，即在某個(gè)詞語(yǔ)（W）已經(jīng)存在的條件下，垃圾郵件（S）的概率有多大。

　　根據(jù)條件概率公式，馬上可以寫(xiě)出

$P(S|W)=\frac{P(W|S)P(S)}{P(W|S)P(S)+P(W|H)P(H)}$

　　公式中，P(W│S)和P(W│H)的含義是，這個(gè)詞語(yǔ)在垃圾郵件和正常郵件中，分別出現(xiàn)的概率。這兩個(gè)值可以從歷史資料庫(kù)中得到，對(duì)sex這個(gè)詞來(lái)說(shuō)，上文假定它們分別等于5%和0.05%。另外，P(S)和P(H)的值，前面說(shuō)過(guò)都等于50%。所以，馬上可以計(jì)算P(S│W)的值：

$P(S|W)=\frac{5%\times 50%}{5%\times 50%+0.05%\times 50%}=99.0%$

　　因此，這封新郵件是垃圾郵件的概率等于99%。這說(shuō)明，sex這個(gè)詞的推斷能力很強(qiáng)，將50%的"先驗(yàn)概率"一下子提高到了99%的"后驗(yàn)概率"。

　　十、聯(lián)合概率的計(jì)算

　　做完上面一步，請(qǐng)問(wèn)我們能否得出結(jié)論，這封新郵件就是垃圾郵件？

　　回答是不能。因?yàn)橐环忄]件包含很多詞語(yǔ)，一些詞語(yǔ)（比如sex）說(shuō)這是垃圾郵件，另一些說(shuō)這不是。你怎么知道以哪個(gè)詞為準(zhǔn)？

　　PaulGraham的做法是，選出這封信中P(S│W)最高的15個(gè)詞，計(jì)算它們的聯(lián)合概率。（【注釋】如果有的詞是第一次出現(xiàn)，無(wú)法計(jì)算P(S│W)，PaulGraham就假定這個(gè)值等于0.4。因?yàn)槔]件用的往往都是某些固定的詞語(yǔ)，所以如果你從來(lái)沒(méi)見(jiàn)過(guò)某個(gè)詞，它多半是一個(gè)正常的詞。）

　　所謂聯(lián)合概率，就是指在多個(gè)事件發(fā)生的情況下，另一個(gè)事件發(fā)生概率有多大。比如，已知W1和W2是兩個(gè)不同的詞語(yǔ)，它們都出現(xiàn)在某封電子郵件之中，那么這封郵件是垃圾郵件的概率，就是聯(lián)合概率。

　　在已知W1和W2的情況下，無(wú)非就是兩種結(jié)果：垃圾郵件（事件E1）或正常郵件（事件E2）。

　　其中，W1、W2和垃圾郵件的概率分別如下：

　　如果假定所有事件都是獨(dú)立事件（【注釋】嚴(yán)格地說(shuō)，這個(gè)假定不成立，但是這里可以忽略），那么就可以計(jì)算P(E1)和P(E2)：

$P(E_{1})=P(S|W_{1})P(S|W_{2})P(S)$ $P(E_{2})=(1-P(S|W_{1}))(1-P(S|W_{2}))(1-P(S))$

　　又由于在W1和W2已經(jīng)發(fā)生的情況下，垃圾郵件的概率等于下面的式子：

$P=\frac{P(E_{1})}{P(E_{1})+P(E_{2})}$

　　即

$P=\frac{P(S|W_{1})P(S|W_{2})P(S)}{P(S|W_{1})P(S|W_{2})P(S)+(1-P(S|W_{1}))(1-P(S|W_{2}))(1-P(S))}$

　　將P(S)等于0.5代入，得到

$P=\frac{P(S|W_{1})P(S|W_{2})}{P(S|W_{1})P(S|W_{2})+(1-P(S|W_{1}))(1-P(S|W_{2}))}$

　　將P(S│W1)記為P1，P(S│W2)記為P2，公式就變成

$P=\frac{P_{1}P_{2}}{P_{1}P_{2}+(1-P_{1})(1-P_{2})}$

　　這就是聯(lián)合概率的計(jì)算公式。如果你不是很理解，點(diǎn)擊這里查看更多的解釋。

　　十一、最終的計(jì)算公式

　　將上面的公式擴(kuò)展到15個(gè)詞的情況，就得到了最終的概率計(jì)算公式：

$P=\frac{P_{1}P_{2}\cdot \cdot \cdot P_{15}}{P_{1}P_{2}\cdot \cdot \cdot P_{15}+(1-P_{1})(1-P_{2})\cdot \cdot \cdot (1-P_{15})}$

　　一封郵件是不是垃圾郵件，就用這個(gè)式子進(jìn)行計(jì)算。這時(shí)我們還需要一個(gè)用于比較的門檻值。PaulGraham的門檻值是0.9，概率大于0.9，表示15個(gè)詞聯(lián)合認(rèn)定，這封郵件有90%以上的可能屬于垃圾郵件；概率小于0.9，就表示是正常郵件。

　　有了這個(gè)公式以后，一封正常的信件即使出現(xiàn)sex這個(gè)詞，也不會(huì)被認(rèn)定為垃圾郵件了。

該文章在 2012/6/20 1:19:06 編輯過(guò)

關(guān)鍵字查詢

垃圾

應(yīng)用

郵件

相關(guān)文章

正在查詢...

點(diǎn)晴ERP是一款針對(duì)中小制造業(yè)的專業(yè)生產(chǎn)管理軟件系統(tǒng),系統(tǒng)成熟度和易用性得到了國(guó)內(nèi)大量中小企業(yè)的青睞。

點(diǎn)晴PMS碼頭管理系統(tǒng)主要針對(duì)港口碼頭集裝箱與散貨日常運(yùn)作、調(diào)度、堆場(chǎng)、車隊(duì)、財(cái)務(wù)費(fèi)用、相關(guān)報(bào)表等業(yè)務(wù)管理，結(jié)合碼頭的業(yè)務(wù)特點(diǎn)，圍繞調(diào)度、堆場(chǎng)作業(yè)而開(kāi)發(fā)的。集技術(shù)的先進(jìn)性、管理的有效性于一體，是物流碼頭及其他港口類企業(yè)的高效ERP管理信息系統(tǒng)。

點(diǎn)晴WMS倉(cāng)儲(chǔ)管理系統(tǒng)提供了貨物產(chǎn)品管理,銷售管理,采購(gòu)管理,倉(cāng)儲(chǔ)管理,倉(cāng)庫(kù)管理,保質(zhì)期管理,貨位管理,庫(kù)位管理,生產(chǎn)管理,WMS管理系統(tǒng),標(biāo)簽打印,條形碼,二維碼管理,批號(hào)管理軟件。

點(diǎn)晴免費(fèi)OA是一款軟件和通用服務(wù)都免費(fèi)，不限功能、不限時(shí)間、不限用戶的免費(fèi)OA協(xié)同辦公管理系統(tǒng)。

公交车上荫蒂添的好舒服的电影-公用玩物(np双xing总受)-公用小荡货芊芊-公与妇仑乱hd-攻把受做哭边走边肉楼梯play-古装一级淫片a免费播放口

[點(diǎn)晴CRM客戶管理系統(tǒng)]垃圾郵件算法：貝葉斯推斷及其互聯(lián)網(wǎng)應(yīng)用