一種改進(jìn)的增量式貝葉斯文本分類(lèi)算法

吳國(guó)文 莊千料

(東華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 上海 201620)

一種改進(jìn)的增量式貝葉斯文本分類(lèi)算法

吳國(guó)文 莊千料

(東華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 上海 201620)

針對(duì)難以獲得大量有標(biāo)簽的訓(xùn)練集問(wèn)題，將增量式貝葉斯學(xué)習(xí)用于小規(guī)模訓(xùn)練集上，并提出了一種新的序列學(xué)習(xí)算法以彌補(bǔ)其學(xué)習(xí)序列中存在的不足：無(wú)法充分利用先驗(yàn)知識(shí)導(dǎo)致噪聲數(shù)據(jù)不斷傳播。在增量學(xué)習(xí)的樣本選擇上，算法引入了配對(duì)樣本檢驗(yàn)和類(lèi)支持度的知識(shí)，分別從橫向和縱向角度充分利用先驗(yàn)知識(shí)來(lái)選取最優(yōu)增量子集優(yōu)化分類(lèi)器，使分類(lèi)器參數(shù)在動(dòng)態(tài)學(xué)習(xí)過(guò)程中得以強(qiáng)化。實(shí)驗(yàn)結(jié)果表明，該算法能有效弱化噪聲數(shù)據(jù)的消極影響，提高分類(lèi)精度，同時(shí)能大幅度減少增量學(xué)習(xí)時(shí)間。

增量學(xué)習(xí) 貝葉斯分類(lèi) 配對(duì)樣本檢驗(yàn) 類(lèi)支持度

0 引 言

文本分類(lèi)的目標(biāo)是在分析文本內(nèi)容的基礎(chǔ)上，根據(jù)預(yù)先定義的規(guī)則集將文本劃分一個(gè)或多個(gè)類(lèi)別，從而提高文本的檢索和使用效率。但是面對(duì)現(xiàn)代爆炸式的信息增長(zhǎng)，已很難把所有的訓(xùn)練數(shù)據(jù)全部一次性讀取到內(nèi)存中，尤其是當(dāng)數(shù)據(jù)是分批獲得時(shí)則更加凸顯了傳統(tǒng)分類(lèi)方法的不足，同時(shí)也很難獲得完備的訓(xùn)練實(shí)例來(lái)訓(xùn)練分類(lèi)器，這都成為文本分類(lèi)的一大研究熱點(diǎn)。針對(duì)這個(gè)難題，宮秀軍等提出將增量學(xué)習(xí)模型用于文本分類(lèi)上[1-2]，根據(jù)0-1分類(lèi)損失度大小，優(yōu)先選擇最小的測(cè)試實(shí)例加入到訓(xùn)練集中，這有效地解決了因訓(xùn)練集不足導(dǎo)致分類(lèi)精度下降問(wèn)題。

本文首先簡(jiǎn)要介紹增量式貝葉斯分類(lèi)模型，分析原有模型存在的不足之處，并提出基于配對(duì)樣本檢驗(yàn)的一種新的序列學(xué)習(xí)算法。該算法首先在增量集中通過(guò)配對(duì)樣本檢驗(yàn)來(lái)獲取最優(yōu)子集，然后根據(jù)分類(lèi)損失度大小選擇樣本更新分類(lèi)器。該算法能有效利用分類(lèi)器的先驗(yàn)信息，在提高分類(lèi)精度的同時(shí)，能大幅度減小增量學(xué)習(xí)時(shí)間。

1 樸素貝葉斯

樸素貝葉斯是一種比較常用的文本分類(lèi)算法[3]，在某些場(chǎng)合其性能甚至還優(yōu)于神經(jīng)網(wǎng)絡(luò)、決策樹(shù)等其他分類(lèi)器。它是以貝葉斯理論為基礎(chǔ)，通過(guò)對(duì)象的先驗(yàn)概率和條件概率求得其后驗(yàn)概率，然后選擇后驗(yàn)概率最大的類(lèi)別作為其所屬的類(lèi)別。

設(shè)一個(gè)文本s={a1,a2,…,an}，其中a1,a2,…,an為文本中互相獨(dú)立的特征詞，可以通過(guò)以下公式來(lái)求得后驗(yàn)概率：

P(cj|s)= P(cj|a1,a2,…,an)=

(1)

根據(jù)貝葉斯理論，文本所屬的類(lèi)別為其最大后驗(yàn)概率所對(duì)應(yīng)的類(lèi)別，因此只要輸出最大后驗(yàn)概率所對(duì)應(yīng)的類(lèi)別即可：

(2)

其中，Cs為文本s所屬的類(lèi)別，P(ai|cj)表示在類(lèi)別cj中第i個(gè)特征詞出現(xiàn)的概率，一般采用TFIDF算法來(lái)計(jì)算。

標(biāo)準(zhǔn)的TFIDF算法并沒(méi)有充分考慮到訓(xùn)練集中數(shù)據(jù)偏移[4-5]的問(wèn)題。針對(duì)這一問(wèn)題，張玉芳[6]等對(duì)標(biāo)準(zhǔn)的TFIDF進(jìn)行分析研究，并給出了改進(jìn)的方法。

(3)

(4)

其中，IDF考慮到了數(shù)據(jù)在類(lèi)間、類(lèi)內(nèi)的分布差異，式(4)中t表示w特征詞在類(lèi)c中出現(xiàn)的文檔數(shù)，h表示除類(lèi)c外，其他類(lèi)中包含w特征詞的文檔數(shù)。

2 貝葉斯增量模型

2.1 增量學(xué)習(xí)模型

貝葉斯分類(lèi)模型屬于監(jiān)督學(xué)習(xí)，它必須要有一個(gè)完備的訓(xùn)練集才能獲得分類(lèi)效果良好的分類(lèi)器。但是隨著分類(lèi)數(shù)據(jù)量的大幅度增長(zhǎng)，同時(shí)受到人工分類(lèi)整理的主觀性影響，訓(xùn)練集的質(zhì)量往往參差不齊，特別是當(dāng)訓(xùn)練的數(shù)據(jù)是在分批獲得時(shí)，這種缺點(diǎn)更是暴露無(wú)遺，因此需要找到一種方法使得訓(xùn)練集更加完備，從而到達(dá)優(yōu)化的效果。增量學(xué)習(xí)的思想[7-8]就是在未分類(lèi)的增量集中，根據(jù)一定的順序選擇樣本集進(jìn)入到訓(xùn)練集中，動(dòng)態(tài)地修改分類(lèi)器參數(shù)，從而達(dá)到優(yōu)化分類(lèi)器的目的。

(5)

其中，θ=|C|+|D|為一系數(shù)，|C|表示類(lèi)別數(shù)，|D|表示樣本數(shù)。

估計(jì)條件概率：

(6)

其中，?=1+|Aj|為一系數(shù)，|Aj|表示類(lèi)別cj下所有特征總數(shù)。

2.2 增量學(xué)習(xí)中的序列選擇問(wèn)題

序列選擇問(wèn)題是影響增量學(xué)習(xí)結(jié)果好壞的重要因素，即何時(shí)選擇哪個(gè)樣本加入訓(xùn)練集對(duì)結(jié)果會(huì)造成直接的影響。因?yàn)橄闰?yàn)信息的不完備性，會(huì)造成未分類(lèi)實(shí)例預(yù)測(cè)結(jié)果的不確定性，若過(guò)早地加入預(yù)測(cè)錯(cuò)誤的實(shí)例，對(duì)分類(lèi)器性能會(huì)起到抑制作用，甚至這些噪聲數(shù)據(jù)會(huì)一直傳播下去，使得分類(lèi)效果越來(lái)越差。

宮秀軍等針對(duì)這個(gè)問(wèn)題所采取的方法是：衡量測(cè)試實(shí)例加入到訓(xùn)練集后對(duì)分類(lèi)器影響好壞的標(biāo)準(zhǔn)是：在0-1分類(lèi)損失假設(shè)前提下，優(yōu)先選擇分類(lèi)損失度最小的測(cè)試實(shí)例加入訓(xùn)練集。該算法考慮了測(cè)試實(shí)例的特性，但存在以下兩個(gè)問(wèn)題：

首先，沒(méi)有充分利用先驗(yàn)知識(shí)。在計(jì)算0-1分類(lèi)損失時(shí)沒(méi)有充分利用先驗(yàn)知識(shí)，這有可能導(dǎo)致將噪聲數(shù)據(jù)提前加入到訓(xùn)練集中，給分類(lèi)器帶來(lái)消極影響。

其次，每次都只是選擇分類(lèi)損失度最小的實(shí)例加入到訓(xùn)練集中，導(dǎo)致算法運(yùn)行效率不高。若測(cè)試實(shí)例的規(guī)模增大，其運(yùn)行時(shí)間會(huì)成幾何倍數(shù)增加。

3 改進(jìn)的增量學(xué)習(xí)算法

針對(duì)原模型中的不足之處，姜卯生[9]等對(duì)分類(lèi)損失度的計(jì)算公式進(jìn)行相應(yīng)的改進(jìn)，在損失度計(jì)算中加入先驗(yàn)知識(shí)因子，充分利用了先驗(yàn)知識(shí)對(duì)分類(lèi)器進(jìn)行優(yōu)化，取得了不錯(cuò)的分類(lèi)效果，但分類(lèi)損失度計(jì)算復(fù)雜，仍然存在著增量學(xué)習(xí)時(shí)間代價(jià)問(wèn)題；丁厲華[10]等人引入了類(lèi)支持度的概念，優(yōu)先選擇測(cè)試實(shí)例的最優(yōu)子集，大幅度縮短了增量學(xué)習(xí)時(shí)間，但對(duì)噪聲數(shù)據(jù)的抑制作用仍有改進(jìn)的地方。通過(guò)以上分析，本文提出了基于配對(duì)樣本檢驗(yàn)的新序列學(xué)習(xí)算法。

3.1 算法思想

當(dāng)從測(cè)試集T中選擇某個(gè)實(shí)例si做增量學(xué)習(xí)時(shí)，應(yīng)選擇包含信息最完善、最有助于提高分類(lèi)器精度的實(shí)例，同時(shí)保證在當(dāng)前分類(lèi)器下對(duì)實(shí)例si的預(yù)測(cè)結(jié)果是可信的。通過(guò)構(gòu)造一個(gè)置信空間，若實(shí)例si進(jìn)入訓(xùn)練集，修改分類(lèi)器參數(shù)后，對(duì)原有訓(xùn)練集的預(yù)測(cè)效果與修改前沒(méi)有顯著性差異，那么就認(rèn)為該實(shí)例si是可以加入到訓(xùn)練集中。同時(shí)在本算法中加入淘汰機(jī)制，未標(biāo)注的數(shù)據(jù)集總是能夠很容易獲得，因此在當(dāng)前分類(lèi)器下確實(shí)沒(méi)有符合要求的實(shí)例時(shí)，可以將剩余的實(shí)例舍去或是和下一批數(shù)據(jù)集一起構(gòu)成新的數(shù)據(jù)集。

3.2 算法描述

輸入：訓(xùn)練數(shù)據(jù)集D={s1,s2,…,sn}，測(cè)試數(shù)據(jù)集T={t1,t2,…,tn}

輸出：分類(lèi)器C

Step1 在訓(xùn)練集D上，獲得分類(lèi)器C；

Step2 若T為空，則算法結(jié)束；

Step3 設(shè)置閾值λ，對(duì)測(cè)試集T中的每個(gè)實(shí)例ti進(jìn)行如下計(jì)算：

(2) 若λi>λ，則保留實(shí)例ti；

Step4 在Step3中會(huì)優(yōu)先選出一部分增量子集T1，若沒(méi)有，則算法結(jié)束；

Step5 對(duì)增量子集T1中的每個(gè)實(shí)例ti進(jìn)行如下計(jì)算：

(1) 計(jì)算每個(gè)實(shí)例ti的配對(duì)樣本檢驗(yàn)值P值；

(2) 若無(wú)顯著性差異，則保留實(shí)例ti；

Step6 在Step5中會(huì)再次優(yōu)先選出一部分增量子集T2，若沒(méi)有，則算法結(jié)束；

Step7 計(jì)算增量子集T2中的每個(gè)實(shí)例ti的改進(jìn)后的分類(lèi)損失度，按照分類(lèi)損失度由小到大的順序加入到訓(xùn)練集中，并更新分類(lèi)器。轉(zhuǎn)到Step2繼續(xù)此過(guò)程。

3.3 算法分析

該算法通過(guò)測(cè)試實(shí)例加入訓(xùn)練集前后是否對(duì)訓(xùn)練集產(chǎn)生顯著性差異來(lái)選取最優(yōu)增量子集，并采用改進(jìn)后的分類(lèi)損失度計(jì)算方式來(lái)判斷增量子集中的實(shí)例進(jìn)入訓(xùn)練集中的先后次序，在判斷方式和計(jì)算方式上都充分利用先驗(yàn)知識(shí)。

相對(duì)于每次只選擇一個(gè)實(shí)例(以下簡(jiǎn)稱(chēng)“算法A”)進(jìn)入訓(xùn)練集而言，本算法犧牲部分空間來(lái)?yè)Q取運(yùn)行效率的提升。首先，算法中只是引入了存儲(chǔ)經(jīng)過(guò)類(lèi)支持度選擇后的增量子集T1、經(jīng)過(guò)配對(duì)樣本檢驗(yàn)后的增量子集T2的空間，而這一部分空間一般只占據(jù)原始數(shù)據(jù)集中很小的一部分。其次，分類(lèi)損失度的計(jì)算本身就比較耗時(shí)，雖然算法的最后也是按照分類(lèi)損失度的大小來(lái)評(píng)估實(shí)例進(jìn)入訓(xùn)練集的先后順序，但是經(jīng)過(guò)類(lèi)支持度和配對(duì)樣本檢驗(yàn)后，參與分類(lèi)損失度計(jì)算的數(shù)據(jù)集大幅度減小，使得算法總體運(yùn)行效率得以提升。經(jīng)過(guò)分析，本算法的時(shí)間復(fù)雜度為O((1+m1+m2)×n)，比算法A的時(shí)間復(fù)雜度O(n2)要小很多(m1、m2要遠(yuǎn)小于n，m1為增量子集T1的大小，m2為增量子集T2的大小)。

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

4.1 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)是在Intel(R)Core(TM)2DuoCPUE8400 @ 3.00GHzCPU、2.00GB內(nèi)存、300GB硬盤(pán)和Ubuntu14.04操作系統(tǒng)下進(jìn)行的，使用Python2.7開(kāi)發(fā)環(huán)境。

實(shí)驗(yàn)數(shù)據(jù)來(lái)源于第二屆自然語(yǔ)言處理與中文計(jì)算會(huì)議(NLP&CC2013)[11]，該數(shù)據(jù)集共包含2 172條帶有情緒的語(yǔ)句(已將不帶有情緒的語(yǔ)句過(guò)濾)，共分為7大類(lèi)，包括憤怒(Anger)、厭惡(Disgust)、恐懼(Fear)、高興(Happiness)、喜好(Like)、悲傷(Sadness)、驚訝(Surprise)，每類(lèi)的數(shù)據(jù)分布情況如表1所示。從表中可以看出Fear和Surprise兩類(lèi)的數(shù)量明顯偏少，使得數(shù)據(jù)集呈現(xiàn)出不平衡。為了解決數(shù)據(jù)集中數(shù)據(jù)偏移問(wèn)題，在文本向量化時(shí)采用了文獻(xiàn)[6]所提供的方法：根據(jù)式(3)和式(4)計(jì)算每個(gè)特征詞的TFIDF值。

表1 數(shù)據(jù)集分布情況

4.2 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)中，對(duì)數(shù)據(jù)集進(jìn)行A、B、C和D四種測(cè)試分類(lèi)，A表示樸素貝葉斯，B表示采用改進(jìn)的分類(lèi)損失度的增量式貝葉斯，C表示采用類(lèi)支持度的增量式貝葉斯，D表示本文分類(lèi)算法。

通常評(píng)價(jià)文本分類(lèi)好壞常用的指標(biāo)包括準(zhǔn)確率(Precision)、召回率(Recall)、微平均(F1)以及ROC曲線(xiàn)。ROC曲線(xiàn) (receiveroperatingcharacteristiccurve)，又稱(chēng)為感受性曲線(xiàn)(sensitivitycurve)，曲線(xiàn)上各點(diǎn)反映著相同的感受性，它們都是對(duì)同一信號(hào)刺激的反應(yīng)，只不過(guò)是在幾種不同的判定標(biāo)準(zhǔn)下所得的結(jié)果而已。曲線(xiàn)往往以真陽(yáng)性率(靈敏度)為縱坐標(biāo)，以假陽(yáng)性率(1-特異度)為橫坐標(biāo)而繪制。與此同時(shí)，ROC曲線(xiàn)有個(gè)很好的特性：當(dāng)測(cè)試集中正負(fù)樣本的分布發(fā)生變化時(shí)，ROC曲線(xiàn)能夠保持不變。這一特性尤其是在數(shù)據(jù)集中的類(lèi)數(shù)據(jù)不平衡時(shí)顯得尤為重要，它能夠從一個(gè)宏觀的角度整體上把握分類(lèi)器的優(yōu)劣。鑒于ROC曲線(xiàn)這一特性和本次實(shí)驗(yàn)中Fear、Surprise兩類(lèi)數(shù)量明顯偏少所出現(xiàn)的數(shù)據(jù)集不平衡現(xiàn)象， 將采用ROC曲線(xiàn)來(lái)作為此次實(shí)驗(yàn)評(píng)價(jià)的標(biāo)準(zhǔn)，通常曲線(xiàn)下方的面積越大，分類(lèi)器分類(lèi)的效果就越好。

從圖1可以看出：本文采用的算法(D)對(duì)比采用類(lèi)支持度的算法(C)、改進(jìn)的分類(lèi)損失度算法(B)，總體上分類(lèi)的效果有所提升，因本算法在選取最優(yōu)增量子集時(shí)充分利用了先驗(yàn)知識(shí)，通過(guò)配對(duì)樣本檢驗(yàn)嚴(yán)格篩選能進(jìn)入訓(xùn)練集的測(cè)試實(shí)例，同時(shí)加入淘汰機(jī)制，把不必須的實(shí)例舍去或是和下一批數(shù)據(jù)集一起重新構(gòu)建新的數(shù)據(jù)集。同時(shí)從表2可以看出：本算法(D)相對(duì)于算法(B)而言準(zhǔn)確率提升了2.95%，相對(duì)于算法(C)而言提升了1.79%。

圖1 各算法的ROC曲線(xiàn)

表2 各算法的準(zhǔn)確率%

圖2和圖3是通過(guò)改變?cè)隽考笮〉膶?duì)比圖，從圖中可以看出，當(dāng)增大增量集時(shí)，即獲取到更多的數(shù)據(jù)集并進(jìn)入訓(xùn)練集時(shí)，分類(lèi)器的效果會(huì)更好。

圖2 增量集比例0.5

圖3 增量集比例1.0

從表3運(yùn)行時(shí)間來(lái)看，算法在保證分類(lèi)器精度的前提下，大大提高了運(yùn)行效率。

表3 運(yùn)行時(shí)間

5 結(jié) 語(yǔ)

本文將增量學(xué)習(xí)用于貝葉斯模型，并采用配對(duì)樣本檢驗(yàn)和類(lèi)支持度相結(jié)合的方法選擇最優(yōu)增量子集，優(yōu)先將具有完備信息，能提高精度的實(shí)例加入訓(xùn)練集中，將不符合要求的實(shí)例剔除或留到下次和其他數(shù)據(jù)集使用，在保證分類(lèi)器精度的前提下，大大縮短了算法運(yùn)行時(shí)間。

但從實(shí)驗(yàn)結(jié)果看到，雖然效果有所提升，但是ROC曲線(xiàn)并不是很完美，離左上角還存在一定的差距，這可能跟數(shù)據(jù)集中Fear(49例)和Surprise(113例)兩類(lèi)數(shù)量偏低有關(guān)。這也從側(cè)面反映出數(shù)據(jù)集完備性的重要性：數(shù)據(jù)集不平衡會(huì)使得分類(lèi)器對(duì)該類(lèi)得不到充分學(xué)習(xí)，在識(shí)別過(guò)程中，也往往容易將該類(lèi)誤判為其他類(lèi)。所以本算法在如何平衡數(shù)據(jù)集方面還有待提高，這也是下一步的研究?jī)?nèi)容，相信這個(gè)問(wèn)題的解決會(huì)使得分類(lèi)器整體上再有所提高。

[1] 宮秀軍,劉少輝,史忠植.一種增量貝葉斯分類(lèi)模型[J].計(jì)算機(jī)學(xué)報(bào),2002,25(6):645-650.

[2] 李曉毅,徐兆棣.一種增量式貝葉斯分類(lèi)的算法[J].沈陽(yáng)農(nóng)業(yè)大學(xué)學(xué)報(bào),2011,42(3):349-353.

[3] 王小林,鎮(zhèn)麗華,楊思春,等.基于增量式貝葉斯模型的中文問(wèn)句分類(lèi)研究[J].計(jì)算機(jī)工程,2014,40(9):238-242.

[4] Elzimaity D,Kearns A M,Dawson S J,et al.On the Classification of Imbalanced Datasets[J].International Journal of Computer Applications,2012,44(8):1-7.

[5] Satyam Maheshwari,Jitendra Agarwal,Sanjeev Sharma.A New Approach for Classification of Highly Imbalanced Datasets Using Evolutionary Algorithms[J].International Journal of Scientific & Engineering Research,2011,2(7):1-5.

[6] 張玉芳,彭時(shí)名,呂佳.基于文本分類(lèi)TFIDF方法的改進(jìn)與應(yīng)用[J].計(jì)算機(jī)工程,2006,32(19):76-78.

[7] 王祖輝,姜維.引入數(shù)據(jù)平滑的增量式貝葉斯垃圾郵件過(guò)濾方法[J].計(jì)算機(jī)工程與應(yīng)用,2012,48(16):21-25.

[8] 許明英,尉永清,趙靜.一種結(jié)合反饋信息的貝葉斯分類(lèi)增量學(xué)習(xí)方法[J].計(jì)算機(jī)應(yīng)用,2011,31(9):2530-2533.

[9] 姜卯生,王浩,姚宏亮.樸素貝葉斯分類(lèi)器增量學(xué)習(xí)序列算法研究[J].計(jì)算機(jī)工程與應(yīng)用,2004,40(14):57-59.

[10] 丁厲華,張小剛.一種基于類(lèi)支持度的增量貝葉斯學(xué)習(xí)算法[J].計(jì)算機(jī)工程,2008,34(22):218-219.

[11] 中文信息技術(shù)專(zhuān)業(yè)委員會(huì).中文微博情感分析評(píng)測(cè)[OL].http://tcci.ccf.org.cn/conference/2013/pages/page04_eva.html.

AN IMPROVED INCREMENTAL BAYESIAN TEXT CLASSIFICATION ALGORITHM

Wu Guowen Zhuang Qianliao

(CollegeofComputerScienceandTechnology,DonghuaUniversity,Shanghai201620,China)

Aiming at the difficulty of obtaining a large number of labeled training sets, incremental Bayesian learning is applied to the small training sets. And a new sequence learning algorithm is proposed to make up the shortcomings of its learning sequence: unable to make full use of a priori knowledge leading to continuous dissemination of noise data. In the sample selection of incremental learning, the algorithm introduces the knowledge of paired sample test and class support and makes full use of prior knowledge to select the optimal increment subset optimization classifier from the horizontal and vertical angles, and makes the classifier parameters can be strengthened during the dynamic learning process. Experimental results show that the algorithm can effectively reduce the negative influence of noise data, improve the classification accuracy, and can greatly reduce the incremental learning time.

Incremental learning Bayesian classification Paired sample test Class support

TFIDF=tf×idf

2016-05-26。國(guó)家自然科學(xué)基金項(xiàng)目(61472075)。吳國(guó)文，副教授，主研領(lǐng)域：機(jī)器學(xué)習(xí)，社會(huì)網(wǎng)絡(luò)。莊千料，碩士生。

TP3

A

10.3969/j.issn.1000-386x.2017.06.041