? 姓名：崔升? ? 學(xué)號(hào)：14020120005

? 轉(zhuǎn)載自：http://www.cnblogs.com/en-heng/p/5173704.html

【嵌牛導(dǎo)讀】：

?樸素貝葉斯（Na?ve Bayes）屬于監(jiān)督學(xué)習(xí)的生成模型，實(shí)現(xiàn)簡單，沒有迭代，學(xué)習(xí)效率高，在大? 樣? 本量下會(huì)有較好的表現(xiàn)。但因?yàn)榧僭O(shè)太強(qiáng)——假設(shè)特征條件獨(dú)立，在輸入向量的特征條件有關(guān)聯(lián)的場? ?景下并不適用。

【嵌牛鼻子】：經(jīng)典大數(shù)據(jù)算法之Na?ve Bayes算法的簡單介紹

【嵌牛提問】：Na?ve Bayes是一種怎么的算法，其數(shù)學(xué)原理又是如何？

【嵌牛正文】：

1. 樸素貝葉斯算法

樸素貝葉斯分類器的主要思路：通過聯(lián)合概率P(x,y)=P(x|y)P(y)P(x,y)=P(x|y)P(y)建模，運(yùn)用貝葉斯定理求解后驗(yàn)概率P(y|x)P(y|x)；將后驗(yàn)概率最大者對應(yīng)的的類別作為預(yù)測類別。

分類方法

首先，我們定義訓(xùn)練集T={(x1,y1),(x2,y2),?,(xN,yN)}T={(x1,y1),(x2,y2),?,(xN,yN)}，其類別yi∈{c1,c2,?,cK}yi∈{c1,c2,?,cK}，則訓(xùn)練集中樣本點(diǎn)數(shù)為NN，類別數(shù)為KK。輸入待預(yù)測數(shù)據(jù)xx，則預(yù)測類別

argmaxckp(y=ck|x)(1)(1)arg?maxck?p(y=ck|x)

由貝葉斯定理可知：

p(y=ck|x)=p(x|y=ck)p(y=ck)p(x)p(y=ck|x)=p(x|y=ck)p(y=ck)p(x)

對于類別ckck而言，p(x)p(x)是恒等的，因此式子(1)(1)等價(jià)于

argmaxckp(x|y=ck)p(y=ck)(2)(2)arg?maxck?p(x|y=ck)p(y=ck)

從上面式子可以看出：樸素貝葉斯將分類問題轉(zhuǎn)化成了求條件概率與先驗(yàn)概率的最大乘積問題。先驗(yàn)概率p(y=ck)p(y=ck)可通過計(jì)算類別的頻率得到，但如何計(jì)算條件概率p(x|y=ck)p(x|y=ck)呢？

樸素貝葉斯對條件概率做了條件獨(dú)立性的假設(shè)，即特征條件相互獨(dú)立。設(shè)輸入xx為n維特征向量(x(1),x(2),?,x(j),?,x(n))(x(1),x(2),?,x(j),?,x(n))，第jj維特征x(j)x(j)的取值有SjSj個(gè)。由概率論的知識(shí)可知：

p(x|y=ck)=∏jp(x(j)|y=ck)p(x|y=ck)=∏jp(x(j)|y=ck)

式子(2)(2)等價(jià)于

argmaxckp(y=ck)∏jp(x(j)|y=ck)(3)(3)arg?maxck?p(y=ck)∏jp(x(j)|y=ck)

為什么要選擇后驗(yàn)概率最大的類別作為預(yù)測類別呢？因?yàn)楹篁?yàn)概率最大化，可以使得期望風(fēng)險(xiǎn)最小化，具體證明參看[1]。

極大似然估計(jì)

在樸素貝葉斯學(xué)習(xí)中，需要估計(jì)先驗(yàn)概率與條件概率，一般時(shí)采用極大似然估計(jì)。先驗(yàn)概率的極大似然估計(jì)：

p^(y=ck)=∑iI(yi=ck)Np^(y=ck)=∑iI(yi=ck)N

其中，II是指示函數(shù)，滿足括號(hào)內(nèi)條件時(shí)為1否則為0；可以看作為計(jì)數(shù)。

設(shè)第jj維特征的取值空間為{aj1,aj2,?,ajSj}{aj1,aj2,?,ajSj}，且輸入變量的第jj維x(j)=ajlx(j)=ajl，則條件概率的極大似然估計(jì)：

p^(x(j)=ajl|y=ck)=∑iI(x(j)i=ajl,y=ck)I(yi=ck)p^(x(j)=ajl|y=ck)=∑iI(xi(j)=ajl,y=ck)I(yi=ck)

貝葉斯估計(jì)

在估計(jì)先驗(yàn)概率與條件概率時(shí)，有可能出現(xiàn)為0的情況，則計(jì)算得到的后驗(yàn)概率亦為0，從而影響分類的效果。因此，需要在估計(jì)時(shí)做平滑，這種方法被稱為貝葉斯估計(jì)（Bayesian estimation）。先驗(yàn)概率的貝葉斯估計(jì)：

p^(y=ck)=∑iI(yi=ck)+λN+kλp^(y=ck)=∑iI(yi=ck)+λN+kλ

后驗(yàn)概率的貝葉斯估計(jì)：

p^(x(j)=ajl|y=ck)=∑iI(x(j)i=ajl,y=ck)+λI(yi=ck)+Sjλp^(x(j)=ajl|y=ck)=∑iI(xi(j)=ajl,y=ck)+λI(yi=ck)+Sjλ

常取λ=1λ=1，這時(shí)被稱為Laplace平滑（Laplace smoothing）。下面提到的拼寫檢查則用到了Laplace平滑——初始時(shí)將所有單詞的計(jì)數(shù)置為1。

2. 拼寫檢查

當(dāng)用戶在輸入拼寫錯(cuò)誤單詞時(shí)，如何返回他想輸入的拼寫正確單詞。比如，用戶輸入單詞thew，用戶有到底是想輸入the，還是想輸入thaw？這種拼寫檢查的問題等同于分類問題：在許多可能拼寫正確單詞中，到底哪一個(gè)時(shí)最有可能的呢？大神Peter Norvig [2]采用樸素貝葉斯解決這個(gè)拼寫問題。

樸素貝葉斯分類

設(shè)用戶輸入的單詞為ww，要返回的拼寫正確單詞為cc，拼寫檢查要找出最大可能的cc，即

argmaxcp(c|w)arg?maxc?p(c|w)

p(c|w)p(c|w)可以理解為在已發(fā)生ww的情況下發(fā)生cc的概率。根據(jù)貝葉斯定理：

p(c|w)=p(w|c)p(c)p(w)p(c|w)=p(w|c)p(c)p(w)

貝葉斯分類器可表示為：

argmaxcp(w|c)p(c)arg?maxc?p(w|c)p(c)

如何估計(jì)p(w|c)p(w|c)與p(c)p(c)呢？估計(jì)p(c)p(c)的辦法可以在文本庫中統(tǒng)計(jì)單詞cc的頻率。p(w|c)p(w|c)表示大多數(shù)用戶在輸入cc時(shí)拼寫錯(cuò)誤輸入成了ww的概率，可以看作時(shí)錯(cuò)誤模型。這需要對大量的錯(cuò)誤輸入進(jìn)行統(tǒng)計(jì)，才能對p(w|c)p(w|c)估計(jì)得較為準(zhǔn)確。Norvig對此做了簡易化的處理：

統(tǒng)計(jì)所有與ww編輯距離為1的拼寫正確單詞，選出在文本庫中頻率最高者；

若未找到與ww編輯距離為1的拼寫正確單詞，則統(tǒng)計(jì)所有與ww編輯距離為2的拼寫正確單詞，選出在文本庫中頻率最高者

若與ww編輯距離為2的拼寫正確單詞也未找到，則返回ww（即分類失?。?/p>

所謂編輯距離為1，指單詞可以通過增加、刪除、修改（一個(gè)字母）或交換（相鄰兩個(gè)字母）變成另外的單詞。上述處理辦法默認(rèn)了：編輯距離為1的拼寫正確單詞永遠(yuǎn)比編輯距離為2的更有可能。

存在問題

Norvig所介紹的拼寫檢查是非常簡單的一種，他在博文[2]中指出不足。此外，還有一些需要優(yōu)化的地方：

上下文關(guān)聯(lián)，比如輸入thew，在不同的上下文中可能返回的拼寫正確單詞不同；

輸入媒介，比如用戶用鍵盤輸入與用手機(jī)的九宮格輸入，其拼寫錯(cuò)誤的方式時(shí)不一樣的。

3. 參考資料

[1] 李航，《統(tǒng)計(jì)學(xué)習(xí)方法》.

[2] Peter Norvig,How to Write a Spelling Corrector.