aaaaaa精品视频在线观看,亚洲www在线观看,四虎成人免费

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

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

admin

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

　　一、什么是貝葉斯推斷

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

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

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

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

　　二、貝葉斯定理

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

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

　　根據(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)}}$

　　這就是條件概率的計算公式。

　　三、全概率公式

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

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

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

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

　　即

$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)成樣本空間的一個劃分，那么事件B的概率，就等于A和A'的概率分別乘以B的條件概率之和。

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

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

　　四、貝葉斯推斷的含義

　　對條件概率公式進行變形，可以得到如下形式：

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

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

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

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

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

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

　　五、【例子】水果糖問題

　　為了加深對貝葉斯推斷的理解，我們看兩個例子。

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

　　我們假定，H1表示一號碗，H2表示二號碗。由于這兩個碗是一樣的，所以P(H1)=P(H2)，也就是說，在取出水果糖之前，這兩個碗被選中的概率相同。因此，P(H1)=0.5，我們把這個概率就叫做"先驗概率"，即沒有做實驗之前，來自一號碗的概率是0.5。

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

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

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

　　已知，P(H1)等于0.5，P(E│H1)為一號碗中取出水果糖的概率，等于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$

　　這表明，來自一號碗的概率是0.6。也就是說，取出水果糖之后，H1事件的可能性得到了增強。

　　六、【例子】假陽性問題

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

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

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

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

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

　　用全概率公式改寫分母，

$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$

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

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

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

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

　　七、什么是貝葉斯過濾器？

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

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

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

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

　　八、建立歷史資料庫

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

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

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

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

　　九、貝葉斯過濾器的使用過程

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

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

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

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

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

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

$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)的含義是，這個詞語在垃圾郵件和正常郵件中，分別出現(xiàn)的概率。這兩個值可以從歷史資料庫中得到，對sex這個詞來說，上文假定它們分別等于5%和0.05%。另外，P(S)和P(H)的值，前面說過都等于50%。所以，馬上可以計算P(S│W)的值：

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

　　因此，這封新郵件是垃圾郵件的概率等于99%。這說明，sex這個詞的推斷能力很強，將50%的"先驗概率"一下子提高到了99%的"后驗概率"。

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

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

　　回答是不能。因為一封郵件包含很多詞語，一些詞語（比如sex）說這是垃圾郵件，另一些說這不是。你怎么知道以哪個詞為準(zhǔn)？

　　PaulGraham的做法是，選出這封信中P(S│W)最高的15個詞，計算它們的聯(lián)合概率。（【注釋】如果有的詞是第一次出現(xiàn)，無法計算P(S│W)，PaulGraham就假定這個值等于0.4。因為垃圾郵件用的往往都是某些固定的詞語，所以如果你從來沒見過某個詞，它多半是一個正常的詞。）

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

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