樸素貝葉斯分類器

樸素貝葉斯分類器

學(xué)院：汽車學(xué)院專業(yè)：車輛工程姓名：李振江主要內(nèi)容樸素貝葉斯分類器理論和計(jì)算過程具體實(shí)例一、樸素貝葉斯分類器理論和計(jì)算過程應(yīng)用MAP假設(shè)分類新實(shí)例x的目標(biāo)是在給定描述實(shí)例的屬性值X{x1,x2,x3,…，xm}的情況下，得到最可能的類標(biāo)記c(i)。應(yīng)用公式得到:現(xiàn)在要做的就是基于訓(xùn)練實(shí)例集估計(jì)式中的兩個(gè)概率值。估計(jì)每個(gè)P(c)值很容易，只要計(jì)算每個(gè)類標(biāo)記c出現(xiàn)在訓(xùn)練實(shí)例集中的頻率就可以。然而，估計(jì)每個(gè)P(x1,x2,x3,…,xm∣c)值不太可行，原因在于:①完整估計(jì)P(x1,x2,x3,…,xm∣c)值的時(shí)間復(fù)雜度相當(dāng)于學(xué)習(xí)一個(gè)貝葉斯網(wǎng)絡(luò)，是一個(gè)NP-難問題。②這些P(x1,x2,x3,…,xm∣c)值的數(shù)量等于可能實(shí)例的數(shù)量乘以可能類的數(shù)量。因此，為獲得合理的估計(jì)，實(shí)例空間中每個(gè)實(shí)例必須出現(xiàn)多次，這要求訓(xùn)練實(shí)例集非常大。為此，提出了相互條件獨(dú)立的樸素貝葉斯分類器。一、樸素貝葉斯分類器理論和計(jì)算過程

樸素貝葉斯分類器在貝葉斯分類器中結(jié)構(gòu)最簡(jiǎn)單，它是包含一個(gè)根節(jié)點(diǎn)、多個(gè)葉節(jié)點(diǎn)的樹狀貝葉斯網(wǎng)，其結(jié)構(gòu)如下圖所示。其中葉節(jié)點(diǎn)A1,A2,...,An是屬性變量，描述待分類對(duì)象的屬性;根節(jié)點(diǎn)C是類別變量，描述對(duì)象的類別。一、樸素貝葉斯分類器理論和計(jì)算過程樸素貝葉斯分類器假定：在給定類標(biāo)記時(shí)屬性值之間是相互條件獨(dú)立的。也就是說，在給定實(shí)例的情況下，觀察到的聯(lián)合概率正好是每個(gè)屬性值概率的乘積。具體的數(shù)學(xué)表達(dá)式如下：將其代入上個(gè)式子，可以得到樸素貝葉斯分類器的分類公式：

一、樸素貝葉斯分類器理論和計(jì)算過程貝葉斯算法處理流程一、樸素貝葉斯分類器理論和計(jì)算過程具體的計(jì)算過程：(1)每個(gè)數(shù)據(jù)樣本用一個(gè)n維特征向量X（x1,x2,x3,…,xn）表示，分別描述對(duì)n個(gè)屬性A1,A2,A3,…,AN樣本的N個(gè)度量。(2)假定有m個(gè)類C1，C2，C3，…，C4，給定一個(gè)未知的數(shù)據(jù)樣本X（x1,x2,x3,…,xn）（即沒有類標(biāo)號(hào))，樸素貝葉斯分類將未知的樣本分配給類Ci，當(dāng)且僅當(dāng)根據(jù)貝葉斯定理，最大化即可進(jìn)行分類。其中

最大的類Ci稱為最大后驗(yàn)假定。(3)其中P(X)代表屬性集A1,A2,A3,…,AN取值為x1,x2,x3,…,xn時(shí)的聯(lián)合概率，為一常數(shù)。類的先驗(yàn)概率可以用P（Ci

）=si/s計(jì)算，其中si是類Ci中訓(xùn)練樣本數(shù)，而s是訓(xùn)練樣本總數(shù)。（4）給定具有許多屬性的數(shù)據(jù)集，計(jì)算P(X|Ci)即P(A1=x1，…,An=xn|Ci)的開銷可能非常大。為降低計(jì)算P(X|Ci)的開銷，可以做類條件獨(dú)立的樸素假定。給定樣本的類標(biāo)號(hào)，假定屬性值相互條件獨(dú)立，即在屬性間，不存在依賴關(guān)系。這樣有：一、樸素貝葉斯分類器理論和計(jì)算過程概率P（x1|Ci），P（x1|Ci），…，P（x1|Ci）可以由訓(xùn)練樣本估值，其中：（a）如果Ak是離散屬性，P（xk|Ci）=N（Ak=xk，C=Ci）/N（C=Ci

）。其中N(C=Ci)是樣本集中屬于類Ci的樣本個(gè)數(shù)。N（Ak=xk，C=Ci

）是樣本集中屬于類型Ci且屬性Ak取值為xk的樣本個(gè)數(shù)。（b）若Ak是連續(xù)值屬性，常用的處理方法有兩種：一種是對(duì)其離散化，然后按著離散值處理；另一種就是假定這一屬性服從某一分布，常假定服從正態(tài)分布。(5〕對(duì)末知樣本X分類的時(shí)候，對(duì)每個(gè)類Ci.計(jì)算P(X|Ci)P(Ci)。樣本X被指派到類Ci當(dāng)且僅當(dāng)P(X|Ci)P(Ci)>P(X|Ci)P(Ci)，1≤j≤m，j≠i。換言之，X被指派到其P(X|Ci)P(Ci)最大的類Ci。二、具體實(shí)例根據(jù)顧客的基本情況來判斷其是否會(huì)買電腦。給定下表所示的14個(gè)訓(xùn)練實(shí)例，其中每一個(gè)顧客用屬性age,income,student和creditrating來描述，類屬性為buycomputer

現(xiàn)有一測(cè)試實(shí)例x:<age<=30,income=medium,student=yes,creditrating=fair>，問這一顧客是否會(huì)買電腦。顯然，我們的任務(wù)就是要預(yù)測(cè)此新實(shí)例的類屬性Buycomputer的取值(yes或no)。為此，我們構(gòu)建如上圖所示的樸素貝葉斯網(wǎng)絡(luò)分類器。圖中的類結(jié)點(diǎn)C表示類屬性Buycomputer，其他4個(gè)結(jié)點(diǎn)A1，A2，A3，A4分別代表4個(gè)屬性age,income,student和creditrating，類結(jié)C是所有屬性結(jié)點(diǎn)的父親結(jié)點(diǎn)，屬性結(jié)點(diǎn)和屬性結(jié)點(diǎn)之間沒有任何的依賴關(guān)系。二、具體實(shí)例根據(jù)公式有為計(jì)算C(x)，需要從14個(gè)訓(xùn)練實(shí)例中估計(jì)出概率:P(yes),P(<=30|yes),P(medium|yes),P(yes|yes),P(fair|yes),P(no),P(<=30|no),P(medium|no),P(yes|no),P(fair|no)。具體的計(jì)算過程如下：二、具體實(shí)例使用以上概率，我們可以得到P(yes)P(<=30|yes)P(medium|yes)P(yes|yes)P(fair|yes)=0.028P(no)P(<=30|no)P(medium|no)P(yes|no)P(fair|no)=0.007可見，樸素貝葉斯分類器將此實(shí)例分類為yes。將上述概率歸一化，可得到樸素貝葉斯分類器分類此實(shí)例為yes的概率是0.028/(0.028+0.007)=0.8?？偨Y(jié)樸素貝葉斯算法的優(yōu)點(diǎn)：a.算法邏輯簡(jiǎn)單，易于實(shí)現(xiàn)；b.分類過程中空開銷小；c.算法穩(wěn)定，對(duì)于不同的數(shù)據(jù)特點(diǎn)其分類性能差別不大，健壯性比較好。那么“樸素貝葉斯分類法的效率如何呢？”該分類法與決策樹和神經(jīng)網(wǎng)絡(luò)分類法的各種比較試驗(yàn)表明，在某些領(lǐng)域，樸素貝葉斯分類法足以與它們媲美。理論上講，與其他所有分類算法相比，樸素貝葉斯分類算法最有最小的錯(cuò)誤率。然而，實(shí)踐中并非總是如此，這是因?yàn)閷?duì)其使用的假定（如類條件獨(dú)立性）的不正確性，以及缺乏可用的概率數(shù)據(jù)造成的。貝葉斯分類法還可以用來為不直接使用貝葉斯定理的其它分類法提供理論判定。例如，在某些假定下，可以證明：與樸素貝葉斯分類法一樣，許多神經(jīng)網(wǎng)絡(luò)和曲線擬合算法輸出的最大的后驗(yàn)假定。實(shí)際使用中，我們有可能遇見兩個(gè)問題：（1）樸素貝葉斯分類項(xiàng)的特征屬性都是離散值，如果是連續(xù)值該怎么進(jìn)行特征屬性劃分？如果P（aj|yi）=0怎么辦？（2）如果特征屬性之間是有關(guān)聯(lián)的，而不是相互獨(dú)立的該怎么解決？擴(kuò)展針對(duì)第一個(gè)問題：特征屬性是連續(xù)值的時(shí)候，通常假定其值是服從高斯分布的，即：而P(ak|yi)=g(ak,ηyi

,σyi)。所以只要計(jì)算出訓(xùn)練樣本中在各個(gè)類別中該特征項(xiàng)劃分的各個(gè)均值和標(biāo)準(zhǔn)差，代入公式即可得到其估計(jì)值。對(duì)于P(ak|yi)=0的情況可以引入拉普拉斯校準(zhǔn)，對(duì)每類別下所有劃分的計(jì)數(shù)加一，這樣如果訓(xùn)練樣本集數(shù)量充分大時(shí)，并不會(huì)對(duì)結(jié)果產(chǎn)生影響，并且解決了上述頻率為0的情況擴(kuò)展針對(duì)第二個(gè)問題：樸素貝葉斯算法是在假定各個(gè)特征屬性相互獨(dú)立的情況下提出來的，這在現(xiàn)實(shí)生活中是很難實(shí)現(xiàn)的，所以針對(duì)這個(gè)問題人們做了大量的工作來解決這一缺點(diǎn)。（1）如果特征屬性之間是有聯(lián)系的，并且是一個(gè)有向無環(huán)圖，可以采用另一個(gè)相關(guān)的貝葉斯分類算法—