貝葉斯算法及其相關(guān)

introduce貝葉斯網(wǎng)絡(luò)BN(BayesianNetworks)源于概率統(tǒng)計(jì)學(xué),作為機(jī)器學(xué)習(xí)的重要方法倍受矚目,在數(shù)據(jù)挖掘中被廣泛研究應(yīng)用。樸素貝葉斯NB(Na!veBayes)分類方法（p.s.其縮寫都是nb，可見此算法確實(shí)很牛逼）具有堅(jiān)實(shí)的理論基礎(chǔ),和其它分類方法相比,表現(xiàn)出了高速度和高效率,被廣泛地應(yīng)用于模式識(shí)別、自然語言處理、機(jī)器人導(dǎo)航、規(guī)劃、機(jī)器學(xué)習(xí)以及利用貝葉斯網(wǎng)絡(luò)技術(shù)構(gòu)建和分析軟件系統(tǒng)。貝葉斯其人貝葉斯ThomasBayes，英國數(shù)學(xué)家.1702年出生于倫敦，做過神甫。1742年成為英國皇家學(xué)會(huì)會(huì)員。1763年4月7日逝世。貝葉斯在數(shù)學(xué)方面主要研究概率論。他首先將歸納推理法用于概率論基礎(chǔ)理論，并創(chuàng)立了貝葉斯統(tǒng)計(jì)理論，對(duì)于統(tǒng)計(jì)決策函數(shù)、統(tǒng)計(jì)推斷、統(tǒng)計(jì)的估算等做出了貢獻(xiàn).1763年發(fā)表了這方面的論著，對(duì)于現(xiàn)代概率論和數(shù)理統(tǒng)計(jì)都有很重要的作用。貝葉斯的另一著作《機(jī)會(huì)的學(xué)說概論》發(fā)表于1758年。貝葉斯所采用的許多術(shù)語被沿用至今。貝葉斯的兩大貢獻(xiàn)概率論中的貝葉斯公式統(tǒng)計(jì)學(xué)中的貝葉斯決策理論貝葉斯公式又稱逆概公式。在全概公式后出現(xiàn)，不是第一也是前三重要的概率公式。設(shè)D1，D2，……，Dn為樣本空間S的一個(gè)劃分，如果以P(Di)表示Di發(fā)生的概率，且P(Di)>0(i=1，2，…，n)。對(duì)于任一事件x，P(x)>0，則有：就形式上而言，該公式可寫作一簡單的形式，p(Di|x)=p(Di,x)/p(x)非常簡潔明了，但是十分犀利如何犀利，下一頁見分曉一個(gè)例子有一個(gè)經(jīng)典的概率問題，在三個(gè)箱子a，b，c里有一個(gè)里面有禮物，甲選擇了a箱子以后，工作人員從剩余的兩個(gè)中打開一個(gè)沒有禮物的箱子c，這時(shí)甲被要求再做一次選擇。他可以選擇：（1）改變以前的想法，選擇箱子b（2）堅(jiān)持以前的想法，選擇第一次選擇的箱子a他到底應(yīng)該做出怎樣的選擇呢？目標(biāo):比較p(a非空|選a，工作人員打開c)和p(b非空|選a，工作人員打開c)貝葉斯決策理論什么是統(tǒng)計(jì)決策？設(shè)x的分布函數(shù)是F(x,c),c是未知參數(shù)，c∈C，C叫做參數(shù)空間。X=(x1,x2,…,xn)是X的樣本。又設(shè)A是某項(xiàng)實(shí)際工作中可能采取的各種行動(dòng)所組成的非空集合，A叫做行動(dòng)空間。L(c,a)是定義在C*A上的非負(fù)函數(shù)，它表示參數(shù)是c時(shí)采取行動(dòng)a（a∈A）引起的損失。稱樣本空間到行動(dòng)空間A的映射g(x1,…xn)為決策函數(shù)，簡稱決策。目的是找一個(gè)決策g，使得L的平均值最小。一個(gè)例子檢查某設(shè)備零件零件可能狀態(tài)：c1(好),c2(壞)可能采取的行動(dòng)：a1(保留),a2(更換),a3(修理).損失函數(shù)為樣本：X取值為0或1.在工作時(shí)用手摸零件，溫度正常時(shí)則記1，發(fā)燙則記0.X的概率函數(shù)為La1a2a3c10105c21216p01c10.30.7c20.60.4貝葉斯決策理論經(jīng)典方法中把參數(shù)c看做是客觀常數(shù)，通過樣本的研究對(duì)c給出估計(jì)值或者判斷c屬于某個(gè)給定的范圍貝葉斯學(xué)派的基本觀點(diǎn)，認(rèn)為在關(guān)于c的任何統(tǒng)計(jì)推斷問題中，除了使用樣本X提供的信息外，還必須對(duì)c提供一個(gè)先驗(yàn)分布，它是進(jìn)行推斷時(shí)不可缺少的要素。說得準(zhǔn)確些，應(yīng)該把c看做隨機(jī)變量，他服從某個(gè)概率分布（叫做先驗(yàn)分布），總體X的分布實(shí)際上是c給定時(shí)x的分布。根據(jù)分布密度f和c的先驗(yàn)分布，可以算出在樣本x下c的條件分布密度，p(c|x)，因?yàn)檫@個(gè)分布是在抽樣后得到的，故成為后驗(yàn)分布貝葉斯方法的關(guān)鍵在于得出后驗(yàn)分布后，他所做的推斷就只基于后驗(yàn)分布，而與樣本無關(guān)了，無論是做最大似然估計(jì)，還是最小二乘估計(jì)。樸素貝葉斯分類算法假設(shè)A1,A2,?,An是數(shù)據(jù)集的n個(gè)屬性,假定有m個(gè)類,C={C1,C2,?,Cm},給定一個(gè)具體的例子X,其屬性值為(x1,x2,?,xn),這里xi就是屬性Ai的取值,該例子屬于某一個(gè)類Ci的后驗(yàn)概率是P(X|Ci),c(X)表示分類所得的類標(biāo)簽。貝葉斯分類器進(jìn)行如下工作:樸素貝葉斯分類假設(shè)類條件獨(dú)立,即屬性之間不存在依賴關(guān)系。這樣有:于是,樸素貝葉斯的分類算法公式為:其中P(Ci)被稱為先驗(yàn)概率,有時(shí)認(rèn)為P(C1)=P(C2)=?=P(Cn),也可以通過公式P(Ci)=si/s計(jì)算,其中si是類Ci中的訓(xùn)練樣本數(shù),而s是訓(xùn)練樣本總數(shù)。概率P(xk|Ci)可以由訓(xùn)練樣本估值,即P(xk|Ci)=sik/si,其中sik是在屬性Ak中具有值xk的類Ci的訓(xùn)練樣本數(shù),而si是Ci中的訓(xùn)練樣本數(shù)。上周論文中的NBC算法貝葉斯過濾算法利用概率函數(shù)構(gòu)建哈希表，當(dāng)其判定函數(shù)超過闕值時(shí)，判定為垃圾郵件。foxmail等都用此算法判定是否為垃圾郵件，當(dāng)然是改進(jìn)后的。一個(gè)例子：垃圾郵件例如：一封含有“法輪功”字樣的垃圾郵件A和一封含有“法律”字樣的非垃圾郵件B根據(jù)郵件A生成hashtable_bad，該哈希表中的記錄為法：1次輪：1次功：1次計(jì)算得在本表中：法出現(xiàn)的概率為0。3輪出現(xiàn)的概率為0。3功出現(xiàn)的概率為0。3根據(jù)郵件B生成hashtable_good，該哈希表中的記錄為：法：1

律：1

計(jì)算得在本表中：法出現(xiàn)的概率為0。5

律出現(xiàn)的概率為0。5綜合考慮兩個(gè)哈希表，共有四個(gè)TOKEN串：法輪功律當(dāng)郵件中出現(xiàn)“法”時(shí)，該郵件為垃圾郵件的概率為：

P=0。3/（0。3+0。5）=0。375

出現(xiàn)“輪”時(shí)：

P=0。3/（0。3+0）=1

出現(xiàn)“功“時(shí)：

P=0。3/（0。3+0）=1

出現(xiàn)“律”時(shí)

P=0/（0+0。5）=0；由此可得第三個(gè)哈希表：hashtable_probability其數(shù)據(jù)為：法：0。375

輪：1

功：1

律：0當(dāng)新到一封含有“功律”的郵件時(shí)，我們可得到兩個(gè)TOKEN串，功律查詢哈希表hashtable_probability可得

P（垃圾郵件|功）=1P（垃圾郵件|律）=0

此時(shí)該郵件為垃圾郵件的可能性為：

P=（0*1）/[0*1+（1-0）*（1-1）]=0

由此可推出該郵件為非垃圾郵件優(yōu)點(diǎn)與缺點(diǎn)優(yōu)點(diǎn)：高速度，高效率，占用內(nèi)存少缺點(diǎn)：基于獨(dú)立性假設(shè)，當(dāng)假設(shè)成立時(shí)與其他分類算法相比,樸素貝葉斯分類