? 姓名：崔升? ? 學(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)簡(jiǎn)單，沒(méi)有迭代前鹅，學(xué)習(xí)效率高焙糟，在大? 樣? 本量下會(huì)有較好的表現(xiàn)。但因?yàn)榧僭O(shè)太強(qiáng)——假設(shè)特征條件獨(dú)立，在輸入向量的特征條件有關(guān)聯(lián)的場(chǎng)? ?景下并不適用。

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

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

【嵌牛正文】：

1. 樸素貝葉斯算法

樸素貝葉斯分類器的主要思路：通過(guò)聯(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)概率最大者對(duì)應(yīng)的的類別作為預(yù)測(cè)類別拐邪。

分類方法

首先，我們定義訓(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ù)測(cè)數(shù)據(jù)xx东臀，則預(yù)測(cè)類別

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)

對(duì)于類別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)

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

樸素貝葉斯對(duì)條件概率做了條件獨(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ù)測(cè)類別呢？因?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í)被稱為L(zhǎng)aplace平滑（Laplace smoothing）。下面提到的拼寫(xiě)檢查則用到了Laplace平滑——初始時(shí)將所有單詞的計(jì)數(shù)置為1凰棉。

2. 拼寫(xiě)檢查

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

樸素貝葉斯分類

設(shè)用戶輸入的單詞為ww胆筒，要返回的拼寫(xiě)正確單詞為cc，拼寫(xiě)檢查要找出最大可能的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)的辦法可以在文本庫(kù)中統(tǒng)計(jì)單詞cc的頻率矫渔。p(w|c)p(w|c)表示大多數(shù)用戶在輸入cc時(shí)拼寫(xiě)錯(cuò)誤輸入成了ww的概率彤蔽，可以看作時(shí)錯(cuò)誤模型。這需要對(duì)大量的錯(cuò)誤輸入進(jìn)行統(tǒng)計(jì)蚌斩，才能對(duì)p(w|c)p(w|c)估計(jì)得較為準(zhǔn)確铆惑。Norvig對(duì)此做了簡(jiǎn)易化的處理：

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

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

若與ww編輯距離為2的拼寫(xiě)正確單詞也未找到，則返回ww（即分類失斔貉帧）受裹。

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

存在問(wèn)題

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

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

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

3. 參考資料

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

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