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

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

律：1

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

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

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

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

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

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

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

出現(xiàn)“律”時

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

輪：1

功：1

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

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

此時該郵件為垃圾郵件的可能性為：

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

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