一種改進的增量式貝葉斯文本分類算法

吳國文 莊千料

(東華大學計算機科學與技術學院 上海 201620)

一種改進的增量式貝葉斯文本分類算法

吳國文 莊千料

(東華大學計算機科學與技術學院 上海 201620)

針對難以獲得大量有標簽的訓練集問題，將增量式貝葉斯學習用于小規模訓練集上，并提出了一種新的序列學習算法以彌補其學習序列中存在的不足：無法充分利用先驗知識導致噪聲數據不斷傳播。在增量學習的樣本選擇上，算法引入了配對樣本檢驗和類支持度的知識，分別從橫向和縱向角度充分利用先驗知識來選取最優增量子集優化分類器，使分類器參數在動態學習過程中得以強化。實驗結果表明，該算法能有效弱化噪聲數據的消極影響，提高分類精度，同時能大幅度減少增量學習時間。

增量學習 貝葉斯分類 配對樣本檢驗 類支持度

0 引 言

文本分類的目標是在分析文本內容的基礎上，根據預先定義的規則集將文本劃分一個或多個類別，從而提高文本的檢索和使用效率。但是面對現代爆炸式的信息增長，已很難把所有的訓練數據全部一次性讀取到內存中，尤其是當數據是分批獲得時則更加凸顯了傳統分類方法的不足，同時也很難獲得完備的訓練實例來訓練分類器，這都成為文本分類的一大研究熱點。針對這個難題，宮秀軍等提出將增量學習模型用于文本分類上[1-2]，根據0-1分類損失度大小，優先選擇最小的測試實例加入到訓練集中，這有效地解決了因訓練集不足導致分類精度下降問題。

本文首先簡要介紹增量式貝葉斯分類模型，分析原有模型存在的不足之處，并提出基于配對樣本檢驗的一種新的序列學習算法。該算法首先在增量集中通過配對樣本檢驗來獲取最優子集，然后根據分類損失度大小選擇樣本更新分類器。該算法能有效利用分類器的先驗信息，在提高分類精度的同時，能大幅度減小增量學習時間。

1 樸素貝葉斯

樸素貝葉斯是一種比較常用的文本分類算法[3]，在某些場合其性能甚至還優于神經網絡、決策樹等其他分類器。它是以貝葉斯理論為基礎，通過對象的先驗概率和條件概率求得其后驗概率，然后選擇后驗概率最大的類別作為其所屬的類別。

設一個文本s={a1,a2,…,an}，其中a1,a2,…,an為文本中互相獨立的特征詞，可以通過以下公式來求得后驗概率：

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

(1)

根據貝葉斯理論，文本所屬的類別為其最大后驗概率所對應的類別，因此只要輸出最大后驗概率所對應的類別即可：

(2)

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

標準的TFIDF算法并沒有充分考慮到訓練集中數據偏移[4-5]的問題。針對這一問題，張玉芳[6]等對標準的TFIDF進行分析研究，并給出了改進的方法。

(3)

(4)

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

2 貝葉斯增量模型

2.1 增量學習模型

貝葉斯分類模型屬于監督學習，它必須要有一個完備的訓練集才能獲得分類效果良好的分類器。但是隨著分類數據量的大幅度增長，同時受到人工分類整理的主觀性影響，訓練集的質量往往參差不齊，特別是當訓練的數據是在分批獲得時，這種缺點更是暴露無遺，因此需要找到一種方法使得訓練集更加完備，從而到達優化的效果。增量學習的思想[7-8]就是在未分類的增量集中，根據一定的順序選擇樣本集進入到訓練集中，動態地修改分類器參數，從而達到優化分類器的目的。

(5)

其中，θ=|C|+|D|為一系數，|C|表示類別數，|D|表示樣本數。

估計條件概率：

(6)

其中，?=1+|Aj|為一系數，|Aj|表示類別cj下所有特征總數。

2.2 增量學習中的序列選擇問題

序列選擇問題是影響增量學習結果好壞的重要因素，即何時選擇哪個樣本加入訓練集對結果會造成直接的影響。因為先驗信息的不完備性，會造成未分類實例預測結果的不確定性，若過早地加入預測錯誤的實例，對分類器性能會起到抑制作用，甚至這些噪聲數據會一直傳播下去，使得分類效果越來越差。

宮秀軍等針對這個問題所采取的方法是：衡量測試實例加入到訓練集后對分類器影響好壞的標準是：在0-1分類損失假設前提下，優先選擇分類損失度最小的測試實例加入訓練集。該算法考慮了測試實例的特性，但存在以下兩個問題：

首先，沒有充分利用先驗知識。在計算0-1分類損失時沒有充分利用先驗知識，這有可能導致將噪聲數據提前加入到訓練集中，給分類器帶來消極影響。

其次，每次都只是選擇分類損失度最小的實例加入到訓練集中，導致算法運行效率不高。若測試實例的規模增大，其運行時間會成幾何倍數增加。

3 改進的增量學習算法

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

3.1 算法思想

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

3.2 算法描述

輸入：訓練數據集D={s1,s2,…,sn}，測試數據集T={t1,t2,…,tn}

輸出：分類器C

Step1 在訓練集D上，獲得分類器C；

Step2 若T為空，則算法結束；

Step3 設置閾值λ，對測試集T中的每個實例ti進行如下計算：

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

Step4 在Step3中會優先選出一部分增量子集T1，若沒有，則算法結束；

Step5 對增量子集T1中的每個實例ti進行如下計算：

(1) 計算每個實例ti的配對樣本檢驗值P值；

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

Step6 在Step5中會再次優先選出一部分增量子集T2，若沒有，則算法結束；

Step7 計算增量子集T2中的每個實例ti的改進后的分類損失度，按照分類損失度由小到大的順序加入到訓練集中，并更新分類器。轉到Step2繼續此過程。

3.3 算法分析

該算法通過測試實例加入訓練集前后是否對訓練集產生顯著性差異來選取最優增量子集，并采用改進后的分類損失度計算方式來判斷增量子集中的實例進入訓練集中的先后次序，在判斷方式和計算方式上都充分利用先驗知識。

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

4 實驗結果及分析

4.1 實驗數據

實驗是在Intel(R)Core(TM)2DuoCPUE8400 @ 3.00GHzCPU、2.00GB內存、300GB硬盤和Ubuntu14.04操作系統下進行的，使用Python2.7開發環境。

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

表1 數據集分布情況

4.2 實驗結果

實驗中，對數據集進行A、B、C和D四種測試分類，A表示樸素貝葉斯，B表示采用改進的分類損失度的增量式貝葉斯，C表示采用類支持度的增量式貝葉斯，D表示本文分類算法。

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

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

圖1 各算法的ROC曲線

表2 各算法的準確率%

圖2和圖3是通過改變增量集大小的對比圖，從圖中可以看出，當增大增量集時，即獲取到更多的數據集并進入訓練集時，分類器的效果會更好。

圖2 增量集比例0.5

圖3 增量集比例1.0

從表3運行時間來看，算法在保證分類器精度的前提下，大大提高了運行效率。

表3 運行時間

5 結 語

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

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

[1] 宮秀軍,劉少輝,史忠植.一種增量貝葉斯分類模型[J].計算機學報,2002,25(6):645-650.

[2] 李曉毅,徐兆棣.一種增量式貝葉斯分類的算法[J].沈陽農業大學學報,2011,42(3):349-353.

[3] 王小林,鎮麗華,楊思春,等.基于增量式貝葉斯模型的中文問句分類研究[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] 張玉芳,彭時名,呂佳.基于文本分類TFIDF方法的改進與應用[J].計算機工程,2006,32(19):76-78.

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

[8] 許明英,尉永清,趙靜.一種結合反饋信息的貝葉斯分類增量學習方法[J].計算機應用,2011,31(9):2530-2533.

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

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

[11] 中文信息技術專業委員會.中文微博情感分析評測[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。國家自然科學基金項目(61472075)。吳國文，副教授，主研領域：機器學習，社會網絡。莊千料，碩士生。

TP3

A

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