//p/ate.html
今天介紹一下樸素貝葉斯分類算法，講一下基本原理，再以文本分類實踐。
一個簡單的例子
樸素貝葉斯算法是一個典型的統(tǒng)計學(xué)習(xí)方法，主要理論基礎(chǔ)就是一個貝葉斯公式，貝葉斯公式的基本定義如下：
這個公式雖然看上去簡單，但它卻能總結(jié)歷史，預(yù)知未來。公式的右邊是總結(jié)歷史，公式的左邊是預(yù)知未來，如果把Y看出類別，X看出特征，P(Yk|X)就是在已知特征X的情況下求Yk類別的概率，而對P(Yk|X)的計算又全部轉(zhuǎn)化到類別Yk的特征分布上來。
舉個例子，大學(xué)的時候，某男生經(jīng)常去圖書室晚自習(xí)，發(fā)現(xiàn)他喜歡的那個女生也常去那個自習(xí)室，心中竊喜，于是每天買點好吃點在那個自習(xí)室蹲點等她來，可是人家女生不一定每天都來，眼看天氣漸漸炎熱，圖書館又不開空調(diào)，如果那個女生沒有去自修室，該男生也就不去，每次男生鼓足勇氣說：“嘿，你明天還來不？”,“啊，不知道，看情況”。
然后該男生每天就把她去自習(xí)室與否以及一些其他情況做一下記錄，用Y表示該女生是否去自習(xí)室，即Y={去，不去}，X是跟去自修室有關(guān)聯(lián)的一系列條件，比如當(dāng)天上了哪門主課，蹲點統(tǒng)計了一段時間后，該男生打算今天不再蹲點，而是先預(yù)測一下她會不會去，現(xiàn)在已經(jīng)知道了今天上了常微分方法這么主課，于是計算P(Y=去|常微分方程)與P(Y=不去|常微分方程)，看哪個概率大，
如果P(Y=去|常微分方程) > P(Y=不去|常微分方程)，那這個男生不管多熱都屁顛屁顛去自習(xí)室了，否則不就去自習(xí)室受罪了。P(Y=去|常微分方程)的計算可以轉(zhuǎn)為計算以前她去的情況下，那天主課是常微分的概率P(常微分方程|Y=去)，注意公式右邊的分母對每個類別（去/不去）都是一樣的，所以計算的時候忽略掉分母，這樣雖然得到的概率值已經(jīng)不再是0~1之間，但是其大小還是能選擇類別。
后來他發(fā)現(xiàn)還有一些其他條件可以挖，比如當(dāng)天星期幾、當(dāng)天的天氣，以及上一次與她在自修室的氣氛，統(tǒng)計了一段時間后，該男子一計算，發(fā)現(xiàn)不好算了，因為總結(jié)歷史的公式：
這里n=3，x(1)表示主課，x(2)表示天氣，x(3)表示星期幾，x(4)表示氣氛，Y仍然是{去，不去}，現(xiàn)在主課有8門，天氣有晴、雨、陰三種、氣氛有A+,A,B+,B，C五種，那么總共需要估計的參數(shù)有8*3*7*5*2=1680個，每天只能收集到一條數(shù)據(jù)，那么等湊齊1680條數(shù)據(jù)大學(xué)都畢業(yè)了，男生打呼不妙，于是做了一個獨(dú)立性假設(shè)，假設(shè)這些影響她去自習(xí)室的原因是獨(dú)立互不相關(guān)的，于是
有了這個獨(dú)立假設(shè)后，需要估計的參數(shù)就變?yōu)椋?8+3+7+5)*2 = 46個了，而且每天收集的一條數(shù)據(jù)短文本分類算法優(yōu)化，可以提供4個參數(shù)，這樣該男生就預(yù)測越來越準(zhǔn)了。
樸素貝葉斯分類器
講了上面的小故事，我們來樸素貝葉斯分類器的表示形式：
當(dāng)特征為為x時，計算所有類別的條件概率，選取條件概率最大的類別作為待分類的類別。由于上公式的分母對每個類別都是一樣的，因此計算時可以不考慮分母，即
樸素貝葉斯的樸素體現(xiàn)在其對各個條件的獨(dú)立性假設(shè)上，加上獨(dú)立假設(shè)后，大大減少了參數(shù)假設(shè)空間。
在文本分類上的應(yīng)用
文本分類的應(yīng)用很多，比如垃圾郵件和垃圾短信的過濾就是一個2分類問題，新聞分類、文本情感分析等都可以看成是文本分類問題，分類問題由兩步組成：訓(xùn)練和預(yù)測，要建立一個分類模型，至少需要有一個訓(xùn)練數(shù)據(jù)集。貝葉斯模型可以很自然地應(yīng)用到文本分類上：現(xiàn)在有一篇文檔d（），判斷它屬于哪個類別ck，只需要計算文檔d屬于哪一個類別的概率最大：
在分類問題中，我們并不是把所有的特征都用上，對一篇文檔d，我們只用其中的部分特征詞項（nd表示d中的總詞條數(shù)目），因為很多詞項對分類是沒有價值的，比如一些停用詞“的,是,在”在每個類別中都會出現(xiàn)，這個詞項還會模糊分類的決策面，關(guān)于特征詞的選取，我的這篇文章有介紹。用特征詞項表示文檔后，計算文檔d的類別轉(zhuǎn)化為：
注意P(Ck|d)只是正比于后面那部分公式，完整的計算還有一個分母，但我們前面討論了，對每個類別而已分母都是一樣的，于是在我們只需要計算分子就能夠進(jìn)行分類了。實際的計算過程中，多個概率值P(tj|ck)的連乘很容易下溢出為0，因此轉(zhuǎn)化為對數(shù)計算，連乘就變成了累加：
我們只需要從訓(xùn)練數(shù)據(jù)集中，計算每一個類別的出現(xiàn)概率P(ck)和每一個類別中各個特征詞項的概率P(tj|ck)，而這些概率值的計算都采用最大似然估計，說到底就是統(tǒng)計每個詞在各個類別中出現(xiàn)的次數(shù)和各個類別的文檔的數(shù)目：
其中，Nck表示訓(xùn)練集中ck類文檔的數(shù)目，N訓(xùn)練集中文檔總數(shù)；Tjk表示詞項tj在類別ck中出現(xiàn)的次數(shù)，V是所有類別的詞項集合。這里對詞的位置作了獨(dú)立性假設(shè)，即兩個詞只要它們出現(xiàn)的次數(shù)一樣，那不管它們在文檔的出現(xiàn)位置，它們大概率值P(tj|ck)都是一樣，這個位置獨(dú)立性假設(shè)與現(xiàn)實很不相符，比如“放馬屁”跟“馬放屁”表述的是不同的內(nèi)容，但實踐發(fā)現(xiàn)，位置獨(dú)立性假設(shè)得到的模型準(zhǔn)確率并不低，因為大多數(shù)文本分類都是靠詞的差異來區(qū)分，而不是詞的位置，如果考慮詞的位置，那么問題將表達(dá)相當(dāng)復(fù)雜，以至于我們無從下手。
然后需要注意的一個問題是ti可能沒有出現(xiàn)在ck類別的訓(xùn)練集，卻出現(xiàn)在ck類別的測試集合中，這樣因為Tik為0，導(dǎo)致連乘概率值都為0，其他特征詞出現(xiàn)得再多，該文檔也不會被分到ck類別，而且在對數(shù)累加的情況下，0值導(dǎo)致計算錯誤，處理這種問題的方法是采樣加1平滑，即認(rèn)為每個詞在各個類別中都至少出現(xiàn)過一次，即
下面這個例子來自于參考文獻(xiàn)1，假設(shè)有如下的訓(xùn)練集合測試集：
現(xiàn)在要計算docID為5的測試文檔是否屬于China類別，首先計算個各類的概率，P(c=China)=3/4,P(c!=China)=1/4，然后計算各個類中詞項的概率：
注意分母（8+6）中8表示China類的詞項出現(xiàn)的總次數(shù)是8，+6表示平滑，6是總詞項的個數(shù)，然后計算測試文檔屬于各個類別的概率：
可以看出該測試文檔應(yīng)該屬于CHina類別。
文本分類實踐
我找了搜狗的搜狐新聞數(shù)據(jù)的歷史簡潔版，總共包括汽車、財經(jīng)、it、健康等9類新聞，一共16289條新聞，搜狗給的數(shù)據(jù)是每一篇新聞用一個txt文件保存，我預(yù)處理了一下，把所有的新聞文檔保存在一個文本文件中，每一行是一篇新聞，同時保留新聞的id，id的首字母表示類標(biāo)，預(yù)處理并分詞后的示例如下：
我用6289條新聞作為訓(xùn)練集，剩余1萬條用于測試，采用互信息進(jìn)行文本特征的提取，總共提取的特征詞是700個左右。
分類的結(jié)果如下：
.8343
總共10000條新聞，分類正確的8343條，正確率0.8343，這里主要是演示貝葉斯的分類過程，只考慮了正確率也沒有考慮其他評價指標(biāo)，也沒有進(jìn)行優(yōu)化。貝葉斯分類的效率高，訓(xùn)練時，只需要掃描一遍訓(xùn)練集，記錄每個詞出現(xiàn)的次數(shù)，以及各類文檔出現(xiàn)的次數(shù)，測試時也只需要掃描一次測試集，從運(yùn)行效率這個角度而言，樸素貝葉斯的效率是最高的，而準(zhǔn)確率也能達(dá)到一個理想的效果。
我的實現(xiàn)代碼如下：
#!=utf-8
sys
math
sys
def ():
'''將原來的文本打亂順序，用于得到訓(xùn)練集和測試集'''
datas = [line.strip() for line in sys.stdin]
.(datas)
for line in datas:
print line
= ['A','B','C','D','E','F','G','H','I']
def (lable):
for i in (len()):
if lable == [i]:
i
raise ('Error lable %s' % (lable))
def ():
[0]*len()
def (N,Nij,Ni_,N_j):
#print N,Nij,Ni_,N_j
Nij * 1.0 / N * math.log(N * (Nij+1)*1.0/(Ni_*N_j))/ math.log(2)
def ():
'''基于統(tǒng)計每個詞在每個類別出現(xiàn)的次數(shù)，以及每類的文檔數(shù)'''
= [0] * len()
#每個類的詞數(shù)目
= .()
for line in sys.stdin:
lable,text = line.strip().split(' ',1)
index = (lable[0])
words = text.split(' ')
for word in words:
[word][index] += 1
[index] += 1
= .()
#互信息值
N = sum()
for k,vs in .items():
for i in (len(vs)):
N11 = vs[i]
N10 = sum(vs) - N11
N01 = [i] - N11
N00 = N - N11 - N10 - N01
mi = (N,N11,N10+N11,N01+N11) + (N,N10,N10+N11,N00+N10)+ (N,N01,N01+N11,N01+N00)+ (N,N00,N00+N10,N00+N01)
[k][i] = mi
= set()
for i in (len()):
keyf = x:x[1][i]
= (.items(),key=keyf,=True)
for j in (100):
.add([j][0])
#打印各個類的文檔數(shù)目
for fword in :
print fword
def ():
'''導(dǎo)入特征詞'''
f = open('.txt')
= eval(f.())
= set()
for line in f:
.add(line.strip())
f.close()
,
def ():
'''訓(xùn)練貝葉斯模型，實際上計算每個類中特征詞的出現(xiàn)次數(shù)'''
, = ()
= .()
= [0]*len()
#每類文檔特征詞出現(xiàn)的次數(shù)
for line in sys.stdin:
lable,text = line.strip().split(' ',1)
index = (lable[0])
words = text.split(' ')
for word in words:
if word in :
[index] += 1
[word][index] += 1
for k,v in .items():
= [(v[i]+1) * 1.0 / ([i]+len()) for i in (len(v))]
#加1平滑
print '%s\t%s' % (k,)
def ():
'''導(dǎo)入貝葉斯模型'''
f = open('model.txt')
= {}
for line in f:
word, = line.strip().('\t',1)
[word] = eval()
f.close()
def ():
'''預(yù)測文檔的類標(biāo)，標(biāo)準(zhǔn)輸入每一行為一個文檔'''
, = ()
= [math.log(count * 1.0 /sum()) for count in ]
= ()
= 0
= 0
for line in sys.stdin:
lable,text = line.strip().split(' ',1)
index = (lable[0])
words = text.split(' ')
= list()
for word in words:
if word in :
for i in (len()):
[i]+=math.log([word][i])
m = max()
= .index(m)
if == index:
+= 1
print lable,[],text
+= 1
print ,, * 1.0 /
if =='':
#()
#()
#()
()
代碼里面，計算特征詞與訓(xùn)練模型、測試是分開的，需要修改main方法，比如計算特征詞：
$cat train.txt | bayes.py > .txt
訓(xùn)練模型：
$cat train.txt | bayes.py > model.txt
預(yù)測模型：
cat test.txt | bayes.py > .out
總結(jié)
本文介紹了樸素貝葉斯分類方法，還以文本分類為例短文本分類算法優(yōu)化，給出了一個具體應(yīng)用的例子，樸素貝葉斯的樸素體現(xiàn)在條件變量之間的獨(dú)立性假設(shè)，應(yīng)用到文本分類上，作了兩個假設(shè)，一是各個特征詞對分類的影響是獨(dú)立的，另一個是詞項在文檔中的順序是無關(guān)緊要的。樸素貝葉斯的獨(dú)立性假設(shè)在實際中并不成立，但在分類效上依然不錯，加上獨(dú)立性假設(shè)后，對與屬于類ck的謀篇文檔d，其p(ck|d)往往會估計過高，即本來預(yù)期p(ck|d)=0.55，而樸素貝葉斯卻計算得到p(ck|d)=0.99，但這并不影響分類結(jié)果，這是樸素貝葉斯分類器在文本分類上效果優(yōu)于預(yù)期的原因。
參考文獻(xiàn):