樸素貝葉斯分類(lèi)器

樸素貝葉斯分類(lèi)器

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

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

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

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

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

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

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

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