數(shù)據(jù)挖掘8：樸素貝葉斯分類算法原理與實(shí)踐

1、-. z數(shù)據(jù)挖掘8：樸素貝葉斯分類算法原理與實(shí)踐隔了很久沒(méi)有寫數(shù)據(jù)挖掘系列的文章了，今天介紹一下樸素貝葉斯分類算法，講一下根本原理，再以文本分類實(shí)踐。一個(gè)簡(jiǎn)單的例子樸素貝葉斯算法是一個(gè)典型的統(tǒng)計(jì)學(xué)習(xí)方法，主要理論根底就是一個(gè)貝葉斯公式，貝葉斯公式的根本定義如下：這個(gè)公式雖然看上去簡(jiǎn)單，但它卻能總結(jié)歷史，預(yù)知未來(lái)。公式的右邊是總結(jié)歷史，公式的左邊是預(yù)知未來(lái)，如果把Y看出類別，*看出特征，P(Yk|*)就是在特征*的情況下求Yk類別的概率，而對(duì)P(Yk|*)的計(jì)算又全部轉(zhuǎn)化到類別Yk的特征分布上來(lái)。舉個(gè)例子，大學(xué)的時(shí)候，*男生經(jīng)常去圖書室晚自習(xí)，發(fā)現(xiàn)他喜歡的那個(gè)女生也常去那個(gè)自習(xí)室，心中竊喜，于是

2、每天買點(diǎn)好吃點(diǎn)在那個(gè)自習(xí)室蹲點(diǎn)等她來(lái)，可是人家女生不一定每天都來(lái)，眼看天氣漸漸炎熱，圖書館又不開空調(diào)，如果那個(gè)女生沒(méi)有去自修室，該男生也就不去，每次男生鼓足勇氣說(shuō)：嘿，你明天還來(lái)不？,啊，不知道，看情況。然后該男生每天就把她去自習(xí)室與否以及一些其他情況做一下記錄，用Y表示該女生是否去自習(xí)室，即Y=去，不去，*是跟去自修室有關(guān)聯(lián)的一系列條件，比方當(dāng)天上了哪門主課，蹲點(diǎn)統(tǒng)計(jì)了一段時(shí)間后，該男生打算今天不再蹲點(diǎn)，而是先預(yù)測(cè)一下她會(huì)不會(huì)去，現(xiàn)在已經(jīng)知道了今天上了常微分方法這么主課，于是計(jì)算P(Y=去|常微分方程)與P(Y=不去|常微分方程)，看哪個(gè)概率大，如果P(Y=去|常微分方程) P(Y=不去|常

3、微分方程)，那這個(gè)男生不管多熱都屁顛屁顛去自習(xí)室了，否則不就去自習(xí)室受罪了。P(Y=去|常微分方程)的計(jì)算可以轉(zhuǎn)為計(jì)算以前她去的情況下，那天主課是常微分的概率P(常微分方程|Y=去)，注意公式右邊的分母對(duì)每個(gè)類別去/不去都是一樣的，所以計(jì)算的時(shí)候忽略掉分母，這樣雖然得到的概率值已經(jīng)不再是01之間，但是其大小還是能選擇類別。后來(lái)他發(fā)現(xiàn)還有一些其他條件可以挖，比方當(dāng)天星期幾、當(dāng)天的天氣，以及上一次與她在自修室的氣氛，統(tǒng)計(jì)了一段時(shí)間后，該男子一計(jì)算，發(fā)現(xiàn)不好算了，因?yàn)榭偨Y(jié)歷史的公式：這里n=3，*(1)表示主課，*(2)表示天氣，*(3)表示星期幾，*(4)表示氣氛，Y仍然是去，不去，現(xiàn)在主課有8門

4、，天氣有晴、雨、陰三種、氣氛有A+,A,B+,B，C五種，則總共需要估計(jì)的參數(shù)有8*3*7*5*2=1680個(gè)，每天只能收集到一條數(shù)據(jù)，則等湊齊1680條數(shù)據(jù)大學(xué)都畢業(yè)了，男生打呼不妙，于是做了一個(gè)獨(dú)立性假設(shè)，假設(shè)這些影響她去自習(xí)室的原因是獨(dú)立互不相關(guān)的，于是有了這個(gè)獨(dú)立假設(shè)后，需要估計(jì)的參數(shù)就變?yōu)椋?8+3+7+5)*2 = 46個(gè)了，而且每天收集的一條數(shù)據(jù)，可以提供4個(gè)參數(shù)，這樣該男生就預(yù)測(cè)越來(lái)越準(zhǔn)了。樸素貝葉斯分類器講了上面的小故事，我們來(lái)樸素貝葉斯分類器的表示形式：當(dāng)特征為為*時(shí)，計(jì)算所有類別的條件概率，選取條件概率最大的類別作為待分類的類別。由于上公式的分母對(duì)每個(gè)類別都是一樣的，因此

5、計(jì)算時(shí)可以不考慮分母，即樸素貝葉斯的樸素表達(dá)在其對(duì)各個(gè)條件的獨(dú)立性假設(shè)上，加上獨(dú)立假設(shè)后，大大減少了參數(shù)假設(shè)空間。在文本分類上的應(yīng)用文本分類的應(yīng)用很多，比方垃圾和垃圾短信的過(guò)濾就是一個(gè)2分類問(wèn)題，新聞分類、文本情感分析等都可以看成是文本分類問(wèn)題，分類問(wèn)題由兩步組成：訓(xùn)練和預(yù)測(cè)，要建立一個(gè)分類模型，至少需要有一個(gè)訓(xùn)練數(shù)據(jù)集。貝葉斯模型可以很自然地應(yīng)用到文本分類上：現(xiàn)在有一篇文檔dDocument，判斷它屬于哪個(gè)類別ck，只需要計(jì)算文檔d屬于哪一個(gè)類別的概率最大：在分類問(wèn)題中，我們并不是把所有的特征都用上，對(duì)一篇文檔d，我們只用其中的局部特征詞項(xiàng)nd表示d中的總詞條數(shù)目，因?yàn)楹芏嘣~項(xiàng)對(duì)分類是沒(méi)有價(jià)

6、值的，比方一些停用詞的,是,在在每個(gè)類別中都會(huì)出現(xiàn)，這個(gè)詞項(xiàng)還會(huì)模糊分類的決策面，關(guān)于特征詞的選取，我的這篇文章有介紹。用特征詞項(xiàng)表示文檔后，計(jì)算文檔d的類別轉(zhuǎn)化為：注意P(Ck|d)只是正比于后面那局部公式，完整的計(jì)算還有一個(gè)分母，但我們前面討論了，對(duì)每個(gè)類別而已分母都是一樣的，于是在我們只需要計(jì)算分子就能夠進(jìn)展分類了。實(shí)際的計(jì)算過(guò)程中，多個(gè)概率值P(tj|ck)的連乘很容易下溢出為0，因此轉(zhuǎn)化為對(duì)數(shù)計(jì)算，連乘就變成了累加：我們只需要從訓(xùn)練數(shù)據(jù)集中，計(jì)算每一個(gè)類別的出現(xiàn)概率P(ck)和每一個(gè)類別中各個(gè)特征詞項(xiàng)的概率P(tj|ck)，而這些概率值的計(jì)算都采用最大似然估計(jì)，說(shuō)到底就是統(tǒng)計(jì)每個(gè)詞在

7、各個(gè)類別中出現(xiàn)的次數(shù)和各個(gè)類別的文檔的數(shù)目：其中，Nck表示訓(xùn)練集中ck類文檔的數(shù)目，N訓(xùn)練集中文檔總數(shù)；Tjk表示詞項(xiàng)tj在類別ck中出現(xiàn)的次數(shù)，V是所有類別的詞項(xiàng)集合。這里對(duì)詞的位置作了獨(dú)立性假設(shè)，即兩個(gè)詞只要它們出現(xiàn)的次數(shù)一樣，那不管它們?cè)谖臋n的出現(xiàn)位置，它們大概率值P(tj|ck)都是一樣，這個(gè)位置獨(dú)立性假設(shè)與現(xiàn)實(shí)很不相符，比方放馬屁跟馬放屁表述的是不同的容，但實(shí)踐發(fā)現(xiàn)，位置獨(dú)立性假設(shè)得到的模型準(zhǔn)確率并不低，因?yàn)榇蠖鄶?shù)文本分類都是靠詞的差異來(lái)區(qū)分，而不是詞的位置，如果考慮詞的位置，則問(wèn)題將表達(dá)相當(dāng)復(fù)雜，以至于我們無(wú)從下手。然后需要注意的一個(gè)問(wèn)題是ti可能沒(méi)有出現(xiàn)在ck類別的訓(xùn)練集，卻出

8、現(xiàn)在ck類別的測(cè)試集合中，這樣因?yàn)門ik為0，導(dǎo)致連乘概率值都為0，其他特征詞出現(xiàn)得再多，該文檔也不會(huì)被分到ck類別，而且在對(duì)數(shù)累加的情況下，0值導(dǎo)致計(jì)算錯(cuò)誤，處理這種問(wèn)題的方法是采樣加1平滑，即認(rèn)為每個(gè)詞在各個(gè)類別中都至少出現(xiàn)過(guò)一次，即下面這個(gè)例子來(lái)自于參考文獻(xiàn)1，假設(shè)有如下的訓(xùn)練集合測(cè)試集：現(xiàn)在要計(jì)算docID為5的測(cè)試文檔是否屬于China類別，首先計(jì)算個(gè)各類的概率，P(c=China)=3/4,P(c!=China)=1/4，然后計(jì)算各個(gè)類中詞項(xiàng)的概率：注意分母8+6中8表示China類的詞項(xiàng)出現(xiàn)的總次數(shù)是8，+6表示平滑，6是總詞項(xiàng)的個(gè)數(shù)，然后計(jì)算測(cè)試文檔屬于各個(gè)類別的概率：可以看出

9、該測(cè)試文檔應(yīng)該屬于CHina類別。文本分類實(shí)踐我找了搜狗的搜狐新聞數(shù)據(jù)的歷史簡(jiǎn)潔版，總共包括汽車、財(cái)經(jīng)、it、*等9類新聞，一共16289條新聞，搜狗給的數(shù)據(jù)是每一篇新聞?dòng)靡粋€(gè)t*t文件保存，我預(yù)處理了一下，把所有的新聞文檔保存在一個(gè)文本文件中，每一行是一篇新聞，同時(shí)保存新聞的id，id的首字母表示類標(biāo)，預(yù)處理并分詞后的例如如下：我用6289條新聞作為訓(xùn)練集，剩余1萬(wàn)條用于測(cè)試，采用互信息進(jìn)展文本特征的提取，總共提取的特征詞是700個(gè)左右。分類的結(jié)果如下8343總共10000條新聞，分類正確的8343條，正確率0.8343，這里主要是演示貝葉斯的分類過(guò)程，只考慮了正確

10、率也沒(méi)有考慮其他評(píng)價(jià)指標(biāo)，也沒(méi)有進(jìn)展優(yōu)化。貝葉斯分類的效率高，訓(xùn)練時(shí)，只需要掃描一遍訓(xùn)練集，記錄每個(gè)詞出現(xiàn)的次數(shù)，以及各類文檔出現(xiàn)的次數(shù)，測(cè)試時(shí)也只需要掃描一次測(cè)試集，從運(yùn)行效率這個(gè)角度而言，樸素貝葉斯的效率是最高的，而準(zhǔn)確率也能到達(dá)一個(gè)理想的效果。我的實(shí)現(xiàn)代碼如下：1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878

11、88990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128#!encoding=utf-8importrandomimportsysimportmathimportcollectionsimportsysdefshuffle():將原來(lái)的文本打亂順序，用于得到訓(xùn)練集和測(cè)試集datas =line.strip() forline insys.stdinrandom.shuffle(datas)forline indatas:printl

12、ine lables =A,B,C,D,E,F,G,H,Ideflable2id(lable):fori in*range(len(lables):iflable =lablesi:returniraiseE*ception(Error lable %s%(lable)defdocdict():return0*len(lables)defmutalInfo(N,Nij,Ni_,N_j):#print N,Nij,Ni_,N_jreturnNij *1.0/N *math.log(N *(Nij+1)*1.0/(Ni_*N_j)/math.log(2)defcountForMI():基于統(tǒng)計(jì)每個(gè)

13、詞在每個(gè)類別出現(xiàn)的次數(shù)，以及每類的文檔數(shù)docCount =0 *len(lables)#每個(gè)類的詞數(shù)目wordCount =collections.defaultdict(docdict) forline insys.stdin:lable,te*t =line.strip().split( ,1)inde* =lable2id(lable0) words =te*t.split( )forword inwords:wordCountwordinde* +=1docCountinde* +=1miDict =collections.defaultdict(docdict)#互信息值N =su

14、m(docCount)fork,vs inwordCount.items():fori in*range(len(vs):N11 =vsiN10 =sum(vs) -N11N01 =docCounti -N11N00 =N -N11 -N10 -N01mi =mutalInfo(N,N11,N10+N11,N01+N11) +mutalInfo(N,N10,N10+N11,N00+N10)+mutalInfo(N,N01,N01+N11,N01+N00)+mutalInfo(N,N00,N00+N10,N00+N01)miDictki =mifWords =set()fori in*range

15、(len(docCount):keyf =lambda*:*1isortedDict =sorted(miDict.items(),key=keyf,reverse=True)forj in*range(100):fWords.add(sortedDictj0)printdocCount#打印各個(gè)類的文檔數(shù)目forfword infWords:printfworddefloadFeatureWord():導(dǎo)入特征詞f =open(feature.t*t)docCounts =eval(f.readline()features =set()forline inf:features.add(lin

16、e.strip()f.close()returndocCounts,featuresdeftrainBayes():訓(xùn)練貝葉斯模型，實(shí)際上計(jì)算每個(gè)類中特征詞的出現(xiàn)次數(shù)docCounts,features =loadFeatureWord()wordCount =collections.defaultdict(docdict) tCount =0*len(docCounts)#每類文檔特征詞出現(xiàn)的次數(shù)forline insys.stdin:lable,te*t =line.strip().split( ,1)inde* =lable2id(lable0) words =te*t.split( )

17、forword inwords:ifword infeatures:tCountinde* +=1wordCountwordinde* +=1fork,v inwordCount.items():scores =(vi+1) *1.0/(tCounti+len(wordCount) fori in*range(len(v)#加1平滑print%st%s%(k,scores)defloadModel():導(dǎo)入貝葉斯模型f =open(model.t*t)scores =forline inf:word,counts =line.strip().rsplit(t,1) scoresword =ev

18、al(counts)f.close()returnscoresdefpredict():預(yù)測(cè)文檔的類標(biāo)，標(biāo)準(zhǔn)輸入每一行為一個(gè)文檔docCounts,features =loadFeatureWord() docscores =math.log(count *1.0/sum(docCounts) forcount indocCountsscores =loadModel()rCount =0docCount =0forline insys.stdin:lable,te*t =line.strip().split( ,1)inde* =lable2id(lable0) words =te*t.split( )preValues =list(docscores)forword inwords:ifword infeatures: fori in*range(len(preValues):preValuesi+=math.log(scoreswordi)m =ma*(preValues)pInde* =preValues.inde*(m)