基于二維信息增益加權(quán)的樸素貝葉斯分類算法①

任世超,黃子良

(成都信息工程大學(xué) 通信工程學(xué)院,成都 610225)

引言

隨著互聯(lián)網(wǎng)技術(shù)的快速發(fā)展,海量的文本信息及其多樣化使得文本分類任務(wù)越來越受到研究界的關(guān)注.文本分類在信息檢索方面能夠加速檢索過程,提高檢索性能.同時(shí),文本分類在新聞專線過濾、專利分類和網(wǎng)頁分類方面都發(fā)揮了重要的作用.文本分類中數(shù)據(jù)往往具有的高維、稀疏、多標(biāo)號等特點(diǎn),這些往往是機(jī)器學(xué)習(xí)需要解決的問題.因此文本分類在機(jī)器學(xué)習(xí)方面具有重要的價(jià)值.

目前雖然有許多算法可以實(shí)現(xiàn)文本分類,如SVM,KNN,神經(jīng)網(wǎng)絡(luò)、深度學(xué)習(xí)等,但是在簡潔性和有效性方面樸素貝葉斯算法都要優(yōu)于其他算法[1-3].樸素貝葉斯算法發(fā)源于古典數(shù)學(xué)理論,有著堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ),以及穩(wěn)定的分類效率.在數(shù)據(jù)較少的情況下仍然有效,它是在貝葉斯定理的基礎(chǔ)上提出了一個(gè)屬性條件獨(dú)立性假設(shè),即對于已知類別,假設(shè)所有屬性相互獨(dú)立,對于分類結(jié)果互不影響[4],所以樸素貝葉斯可以有效的用于文本多分類任務(wù).因此我們決定使用樸素貝葉斯算法用來文本分類的研究.由于樸素貝葉斯算法是在條件獨(dú)立性假設(shè)的基礎(chǔ)上提出來的,即所有屬性的權(quán)值都為1,但實(shí)際上每個(gè)屬性對于文檔的分類的重要性是不同的,也就是權(quán)值的取值不同.特征提取是文本分類的關(guān)鍵步驟,由于不同的加權(quán)算法對應(yīng)權(quán)值計(jì)算,直接會(huì)對我們的特征的提取以及最終分類的結(jié)果造成比較大的影響,所以研究者們提出不同的權(quán)值計(jì)算方法來進(jìn)行改進(jìn)加權(quán).如文獻(xiàn)[5]中把特征信息增益加到TF-IDF算法中相應(yīng)改善算法性能后,之后文獻(xiàn)[6]又把信息增益與信息熵結(jié)合,文獻(xiàn)[7]中提出了根據(jù)特征在類間的詞頻和文檔頻率重新計(jì)算反文檔頻率,文獻(xiàn)[8]中把各特征相對于類別的互信息作為權(quán)重.但是這些算法沒有全面考慮影響特征權(quán)重的因素.

本文通過對現(xiàn)有文獻(xiàn)中文本分類算法的研究,提出了基于二維信息增益的加權(quán)算法IGC-IGD (Information Gain of ocument and Category),從類別信息增益和文檔信息增益兩個(gè)方面綜合考慮特征詞對分類效果的影響,并設(shè)計(jì)實(shí)驗(yàn)進(jìn)一步驗(yàn)證了IGC-IGD 算法在各個(gè)評價(jià)指標(biāo)上都要優(yōu)于其他算法.

1 樸素貝葉斯及其改進(jìn)加權(quán)算法

1.1 樸素貝葉斯算法

本文采用了文獻(xiàn)[9]所給出的貝葉斯模型為多項(xiàng)式模式,算法思想是：首先計(jì)算出各個(gè)類別的先驗(yàn)概率,再利用貝葉斯定理計(jì)算出各特征屬于某個(gè)類別的后驗(yàn)概率,通過選出具有最大后驗(yàn)概率(maximum a posteriori,MAP)估計(jì)值的類別即為最終的類別[9].

算法描述：

設(shè)文檔類別為C={C1,C2,···,Cj},j=1,2,3,···,V,則每個(gè)類的先驗(yàn)概率為P(Cj).設(shè)Di為任意一篇文檔,其包含的特征詞為Di={t1,t2,···,tm},把Di歸為哪一類的概率就是后驗(yàn)概率P(Cj|Di).

貝葉斯分類的過程就是求解P(Cj|Di)最大值的過程,顯然對于給定的訓(xùn)練文檔P(Di)是個(gè)常數(shù).所以求解過程可轉(zhuǎn)化成求解：

因?yàn)镈i={t1,t2,···,tm},根據(jù)樸素貝葉斯假設(shè),{t1,t2,···,tm}各特征相互獨(dú)立,所以式(2)可等效成：

其中,P(Cj)表 示Cj類出現(xiàn)的概率,P(ti|Cj)出現(xiàn)ti屬于Cj類的概率.

1.2 基于TF-IDF 加權(quán)樸素貝葉斯算法

由于樸素貝葉斯算法沒有考慮到不同特征對分類效果造成的影響,通常采用TFIDF 算法[10]對特征進(jìn)行特征加權(quán).加權(quán)樸素貝葉斯模型：

由于每次計(jì)算的概率可能會(huì)比較小,為了避免出現(xiàn)下溢的情況,通常采用對決策規(guī)則取對數(shù)的形式：

TF-IDF 算法的思想：特征單詞雖然在整個(gè)文本集中出現(xiàn)的頻率比較低,但是在某特定文本中出現(xiàn)的頻數(shù)越大,則對于該文本的分類作用越大,反之,特征單詞在大多數(shù)文檔中出現(xiàn)的頻數(shù)越大,對于文本的分類作用越小[6,11].TF-IDF 算法將詞頻和反文檔頻率結(jié)合作為特征的權(quán)重,歸一化計(jì)算方法：

其中,TF(ti)為特征ti在訓(xùn)練集中出現(xiàn)的頻數(shù),IDF(ti)是反文檔頻率,N表示訓(xùn)練集的總文檔數(shù),n(ti)表示出現(xiàn)特征ti的文檔數(shù).

1.3 基于TF-IDF＊IGC 加權(quán)改進(jìn)算法

雖然TF-IDF 算法一定程度上能提高分類的精確度,但效果并不是很明顯.因?yàn)樵撍惴ㄖ豢紤]了特征詞在訓(xùn)練集中的總體分布情況,而忽視了特征詞在類別中的分布情況對其權(quán)重造成的影響.針對這個(gè)問題,文獻(xiàn)[5]的工作主要是把信息論中信息增益應(yīng)用到文本集合的類別層次上.提出了一種改進(jìn)的權(quán)重公式TFIDF*IGC,首先計(jì)算出各個(gè)類別的信息熵,然后計(jì)算各特征詞在每個(gè)類別中的條件信息熵,利用兩者的差值計(jì)算出單詞在各個(gè)類別中的信息增益,把該信息增益反映在權(quán)重中,計(jì)算公式：

其中,C為文檔的類別集合,為類別Cj在訓(xùn)練集中的概率,為每個(gè)特征詞t在類別Cj中出現(xiàn)的概率,表示類別總數(shù).

利用TF-IDF*IGC 算法能夠?qū)⑻卣髟陬悇e中的信息反應(yīng)出來,并同時(shí)能夠?qū)γ總€(gè)特征權(quán)重做一定的修正.當(dāng)特征詞t在某個(gè)類別中分布很多,而在其他類別中分布很少時(shí),利用信息增益計(jì)算公式就能得到很高的信息增益值,這樣就能很好的反應(yīng)出特征詞的分布對分類的影響,反之就能得到較小的信息增益值[5],所以在一定程度提高了算法的精確度.

2 基于IGC-IGD 特征加權(quán)樸素貝葉斯算法

由于1.3 節(jié)給出的TF-IDF*IGC 算法只考慮了特征詞在類列間的分布情況并沒有考慮到特征詞在每個(gè)類別文檔中的出現(xiàn)情況,因此會(huì)對對權(quán)重造成的影響.以進(jìn)一步提高算法精度為目標(biāo),針對TF-IDF*IGC 算法的缺陷,本節(jié)定義一個(gè)新的權(quán)重計(jì)算函數(shù)：IGC-IGD 函數(shù).由于信息增益是描述某個(gè)屬性對分類效果提升作用的指標(biāo),信息增益越大,意味著特征屬性對文檔分類提升越大[4].二維信息增益的定義即為同時(shí)從特征詞關(guān)于文檔的信息增益和特征詞關(guān)于類別的信息增益這兩個(gè)維度進(jìn)行考慮,有效的結(jié)合了特征在兩個(gè)方面的性能來刻畫特征類別和特征文檔對分類作用的提升程度,這里定義了新的方法求特征類別概率：

其中,t f(Dt,Cj)表示各特征詞在類Cj中的頻數(shù),所以P(t,Cj)就表示類Cj中出現(xiàn)的特征詞在訓(xùn)練集該特征詞總數(shù)中出現(xiàn)的概率.式中的L是為了抑制概率為0 的情況所加入的平滑因子,本文中取L=0.01,V表示類別數(shù).同樣的方法得到各類別中特征詞出現(xiàn)的文檔數(shù)在訓(xùn)練集中對應(yīng)特征詞所出現(xiàn)的總文檔數(shù)中出現(xiàn)的概率：

其中,tf(Dt,Cj)表示在類Cj中t含有特征詞的文檔數(shù),L=0.01 為平滑因子,V表示類別數(shù).

傳統(tǒng)的求特征文檔信息增益的方法僅僅考慮了特征與文檔的關(guān)系[11],而忽略了文檔與文檔類別的關(guān)系,所以這里定義新的求特征文檔信息增益的公式把特征與文檔的關(guān)系同時(shí)把文檔與文檔類別的關(guān)系結(jié)合在一起,由此可以得到新的特征類別信息增益和特征文檔信息增益：

其中,IGC表示特征類別信息增益,刻畫特征與類別的關(guān)系;IGD表示特征文檔信息增益,刻畫特征與文檔的關(guān)系;P(Dt,Cj)和P(t,Cj)分別表示上文提出的求特征類別概率和特征文檔概率.這樣得到的兩組信息增益能夠準(zhǔn)確的反應(yīng)出每個(gè)特征詞對每個(gè)類別的影響力以及每個(gè)特征詞對每類文檔的影響力.同時(shí)把特征詞類別信息增益和文檔信息增益結(jié)合起來,并采用歸一化方法進(jìn)行處理,得到權(quán)重表示為：

其中,IGC(ti)、IGD(ti)分別表示數(shù)據(jù)集的某一個(gè)特征的類別信息增益和文檔信息增.式(14)首先計(jì)算IGC(ti)×IGD(ti)的值獲得原始數(shù)據(jù),然后再進(jìn)行歸一化.歸一化的目的是為了使數(shù)據(jù)等比例的變化,這樣不會(huì)影響整體的權(quán)重調(diào)整.這也就是二維信息增益的具體定義.

下面舉例說明新權(quán)重的合理性,假設(shè)訓(xùn)練集包含3 個(gè)類別,每個(gè)類別中有3 篇文檔,特征詞集合為{t1,t2,t3}分布情況如表1所示.

表1 特征詞分布

由表1知t1在三個(gè)文本中都出現(xiàn)過,t1只是在類別1 中出現(xiàn)過,說明t1能夠準(zhǔn)確的代表類別1 的信息,應(yīng)當(dāng)給予較大的權(quán)重,t3在三個(gè)類別中都出現(xiàn)相同的次數(shù),說明不具有分類能力,應(yīng)當(dāng)給予較小的權(quán)重,大部分出現(xiàn)在類別3 中,t2所以分類能力要比t1好,但是比t2要差,所以權(quán)重值應(yīng)當(dāng)介于t1和t2之間,使用以上三個(gè)算法得到的權(quán)重結(jié)果如表2所示.

由表2中的結(jié)果可以看出,TF-IDF 算法因?yàn)獒槍Φ氖钦麄€(gè)訓(xùn)練集中的特征,所以詞頻越大的特征被分配的權(quán)重越大,導(dǎo)致結(jié)果與實(shí)際情況有點(diǎn)截然相反.TF-IDF*IGC 算法不僅考慮了在整個(gè)訓(xùn)練集中的情況,還考慮了特征詞與類別間的關(guān)系,所以權(quán)重分配比較更合理一些,但因?yàn)槿匀慌c反文檔頻率相結(jié)合導(dǎo)致t1與t3的權(quán)重相差很小,這種時(shí)候可能會(huì)影響到分類效果,相比之下IGC-IGD 算法不僅讓沒有分類能力的特征詞t2權(quán)重消零,而且讓t1與t3的權(quán)重拉開了差距,這樣能讓各個(gè)特征起到?jīng)Q定分類作用的效果.

3 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

3.1 實(shí)驗(yàn)數(shù)據(jù)及其預(yù)處理

實(shí)驗(yàn)數(shù)據(jù)采用國際通用的20_NewsGroup 數(shù)據(jù)集

進(jìn)行驗(yàn)證.該數(shù)據(jù)集為英文數(shù)據(jù)集,從qwone.com/～jason/20Newsgroups 官網(wǎng)下載,一共包含20 個(gè)類,從中選出6 個(gè)類：alt.atheismcomp.graphics,misc.forsale,rec.autos,sci.crypt,talk.politics.guns,從每個(gè)類別中各抽出100 篇文檔,一共600 篇文檔,采用交叉驗(yàn)證法[12],隨機(jī)選出60%(360 篇)作為訓(xùn)練集,40%(240 篇)作為測試集.

實(shí)驗(yàn)數(shù)據(jù)預(yù)處理：去除掉標(biāo)點(diǎn)符號,停用詞,數(shù)字以及一些特殊符號,為了降低空間復(fù)雜度和分類計(jì)算的時(shí)間,把詞頻特作為選擇單詞的標(biāo)準(zhǔn),對每次選取500 特征進(jìn)行實(shí)驗(yàn),重復(fù)實(shí)驗(yàn)十次求平均值來驗(yàn)證算法的準(zhǔn)確性.

3.2 實(shí)驗(yàn)結(jié)果分析

本實(shí)驗(yàn)中使用上文介紹的三個(gè)加權(quán)算法與樸素貝葉斯算法結(jié)合進(jìn)行實(shí)驗(yàn).采用查準(zhǔn)率(P)[12,13],召回率(R)[14,15],F1 值(F1)和宏F1 值(Macro_F1)四個(gè)指標(biāo)[16-20]算公式如下：

TP表示正確的標(biāo)記為正,FP錯(cuò)誤的標(biāo)記為正,FN錯(cuò)誤的標(biāo)記為負(fù),TN正確的標(biāo)記為負(fù)[4],如表3所示.

表3 參數(shù)含義

實(shí)驗(yàn)結(jié)果如表4所示.

表4 算法測試結(jié)果比較

由表4可以看出,當(dāng)使用基于二維信息增益IGCIGD 加權(quán)的樸素貝葉斯文本分類算法時(shí),查準(zhǔn)率,召回率和F1 值這三個(gè)指標(biāo)總體上都有明顯的提高.具體的,IGDCNB 算法對所有類別的查準(zhǔn)率都要高于其他兩種算法,除了comp.graphics,misc.forsale 兩個(gè)類別的召回率略低于TF-IDF*IGC 特征加權(quán)的樸素貝葉斯文本分類算法,對于F1 值,IGDCNB 算法也都要領(lǐng)先于其他兩種算法,個(gè)別類別比如sci.crypt 和talk.politics.guns,雖然傳統(tǒng)的基于TF-IDF 特征加權(quán)的樸素貝葉斯文本分類算法具有較高的查準(zhǔn)率,但其召回率卻遠(yuǎn)遠(yuǎn)低于IGDCNB 算法,這也不是研究者希望出現(xiàn)的.總體上看,與TF-IDF*IGC 加權(quán)算法相比,三個(gè)指標(biāo)都能提高3%到4%;與TF-IDF 加權(quán)算法相比三個(gè)指標(biāo)都能提高4%到6%,這充分證明了IGC-IGD 加算法的有效性.查準(zhǔn)率對應(yīng)實(shí)際被分類的比例,召回率對應(yīng)應(yīng)該被分類的比例.由于查準(zhǔn)率較高時(shí)召回率不一定能夠很高,所以本文最后采用比較三種算法的宏F1 值的方法來驗(yàn)證IGC-IGD 加權(quán)的樸素貝葉斯文本分類算法的有效性.本文通過選擇不同的特征數(shù)來驗(yàn)證算法的準(zhǔn)確性,實(shí)驗(yàn)結(jié)果如圖1所示.

圖1 3 種算法宏F1 值比較

F1 值對應(yīng)查準(zhǔn)率P和召回率R的調(diào)和均值.宏F1 值是所有類別對應(yīng)的F1 值得平均,能夠反應(yīng)各加權(quán)算法整體性能(查準(zhǔn)率、召回率、F1 值)的指標(biāo).由圖1可以看出,當(dāng)特征數(shù)量從500 增加到1000 時(shí),IGC-IGD 加權(quán)的樸素貝葉斯分類算法的宏F1 值要高于其他兩個(gè)算法,根據(jù)3.2 宏F1 值的計(jì)算公式計(jì)算可以得到該算法相比傳統(tǒng)的加權(quán)算法宏F1 值提升將近6%左右,而且該算法本身不會(huì)因?yàn)樘卣鲾?shù)量的變化出現(xiàn)較大的波動(dòng),說明在給定一定量有價(jià)值的特征時(shí),二維信息增益IGC-IGD 加權(quán)的樸素貝葉斯分類算法能夠有效的對文本進(jìn)行分類.

4 結(jié)束語

本文通過有機(jī)的結(jié)合特征類別信息增益(IGC)和特征文檔信息增益(IGD),提出了二維信息增益加權(quán)的樸素貝葉斯分類算法,充分利用了文本中特征的二維信息,克服了傳統(tǒng)樸素貝葉斯算法分類性能上的缺陷,通過實(shí)驗(yàn)進(jìn)一步驗(yàn)證了該算法的有效性.為了進(jìn)一步提升樸素貝葉斯文本分類算法的性能,以得到更為精確迅速的分類方法.下一步的工作將會(huì)從樸素貝葉斯算法中的條件概率計(jì)算方法這個(gè)方面進(jìn)行改進(jìn).