改進的增量貝葉斯模型的研究

蘇志同　李　楊

(北方工業大學計算機學院　北京 100144)

?

改進的增量貝葉斯模型的研究

蘇志同李楊

(北方工業大學計算機學院北京 100144)

傳統分類算法的研究主要關注批量學習任務。實際中，帶標注樣本很難一次性獲得。且存儲空間開銷較大的特點，也使批量學習顯現出一定的局限性。因此，需要增量學習來解決該問題。樸素貝葉斯分類器簡單、高效、魯棒性強，且貝葉斯估計理論為其應用于增量任務提供了基礎。但現有的增量貝葉斯模型沒有對適應新類別作出描述。同時，實驗表明類別之間樣本數量的不平衡，會嚴重影響該模型的分類性能。故基于這兩個問題，提出對增量貝葉斯模型的改進，增加參數修正公式，使其可適應新出現的類別，并引入最小風險決策思想減輕數據不平衡造成的影響。取UCI數據集進行仿真測試，結果表明改進后的模型可以漸進提高分類性能，并具有適應新類別的能力。

機器學習樸素貝葉斯增量學習最小化風險

0　引　言

分類問題的研究是監督學習研究的核心任務之一。可以將分類描述為根據已知數據集，建立分類器(決策函數或概率模型)，再利用分類器判斷未知樣本類別的過程。建立分類器過程，稱為學習。而利用分類器判斷的過程，稱為預測。依據樣本獲得過程與模型學習過程的具體特點，學習任務可分為批量學習任務與增量學習任務[1]。Giraud-Carrier指出，增量學習任務具有樣本隨時間獲得，并且學習過程需持續進行的特點。而傳統機器學習算法的研究假設訓練集可以一次性獲得，一旦訓練集被充分處理后，學習就結束了。所獲得的模型僅僅用于對新實例的預測。雖然對批量學習算法稍做修改，所得暫時批量學習算法[2]可應用于增量任務，但是要存儲已學習過的樣本，用重新訓練的方式更新模型，這增加了額外的時空開銷。與此方法相比，Polikar[3]面向監督學習任務，定義增量學習算法應當滿足從新數據中學習新的知識，不需要訪問當前分類器學習過的數據，僅保存當前所獲得的知識，可以適應具有新的類別標記的樣本。基于這種思想，Polikar等人提出了一種針對有監督任務的增量學習算法Learn++，增量地訓練多層感知機(MLP)，并將之運用于分類任務中。對UCI的部分數據集及一些現實數據進行仿真測試，證明算法使得多層感知機的分類性能隨著訓練數據的增加得以提高，且成功適應了新引入的類別。此后，在傳統算法基礎上，前人提出了很多增量算法。從所獲得的模型角度來看，一些算法以較少的時空代價，對多個訓練子集進行增量學習，從而獲得與在全部訓練集進行批量訓練近似的模型，進而達到近似的分類效果。如支持向量機(SVM) 的增量版本[4-6]及增量決策樹ID4[7]。另一類算法則是，可以獲得與批量學習相同的模型，如增量決策樹ID5R[8]。從Polikar等所定義的增量學習所滿足的條件來看，除針對新樣本數據進行增量學習外，還可以學習新的樣本類別，如Jia H等人提出的SVM的類別增量學習算法[10]。

因此，可以認為增量任務分為對數據或樣本的增量學習和對新引入類別的增量學習。樸素貝葉斯模型以其很好的魯棒性與分類精度[11]成為處理分類任務重要模型。而貝葉斯參數估計理論為其能夠在連續學習的過程中，利用樣本信息修正當前模型提供了的理論依據。宮秀軍等人對基于貝葉斯理論的增量學習進行了詳細論證，并給出了完整的增量貝葉斯分類模型[9]。隨后，在諸多場景下都得以應用，如病毒上報分析的應用[12]與中文問句分類[13]等。雖然增量貝葉斯分類模型的提出很好地解決了在類別平衡的數據集上，對樣本的增量學習。但是該模型存在兩點不足。其一，該模型并沒有對新出現的類別增量予以描述。其二，并非從所有領域中收集而來的訓練集都是類別平衡的。在不平衡數據集中，往往一些類別被大量的樣本過度的表達。相反代表另一些類別的樣本數量卻很少。從而導致分類器不能識別少數樣本所代表的類別。故本文在其基礎之上，基于貝葉斯估計方法對增量貝葉斯模型進行擴展，實現對新類別適應。并提出一種代價函數使之結合最小化風險決策，從而克服從不平衡數據集學習分類器的問題。

1　增量貝葉斯模型

表1　類別分布律

此分布中存在m-1個參數，記為ξ=(ξ1,ξ2,…,ξm-1)。將訓練集中的樣本視為n次獨立實驗的觀測結果，則其似然函數可表示為式(1):

(1)

其中：ui為樣本集中類別yj出現的次數，且∑ui=n。

貝葉斯參數估計方法需要將所估計的參數看作隨機變量，假設已經掌握了關于ξ的先驗k0，所以假設在事先得知ξ的先驗分布為p(ξ|k0)。通過獲得的樣本x1,x2,…,xn計算后驗分布p(ξ|k0,x1,x2,…,xn)，最終用后驗分布下ξ的期望值作為估計結果。當只有一個已知樣本x1時，計算后驗分布如下:

(2)

當獲得兩個樣本x1,x2時，計算后驗分布如下：

(3)

此時，ξ的先驗分布變為p(ξ|K0,x1)，即先驗知識由k0變為了(K0,x1)。以此類推可得Ki+1=Ki+xi。當樣本是連續獲得時，可將當前計算的后驗結果作為新樣本獲得后再次進行估計的先驗來使用，即增量地修正估計結果。

特別地，后驗分布與先驗分布共軛時效果最佳。根據此問題的似然結構應取dirichlet分布作為參數ξ的先驗分布。式(4)給出了其概率密度與數學期望，其中(α1,α2,…,αm)稱作超參數且α=∑αi。

=dirichlet(α1,α2,…,αm)

(4)

p(ξ|K0,x1,x2,…,xn)

=dirichlet(α1+u1,α2+u2,…,αm+um)

0≤ξ1+ξ2+…+ξm-1<1

(5)

(6)

(7)

增量貝葉斯模型的提出，從參數估計的角度，給出了增量修正模型參數方法。更重要的是，貝葉斯估計理論使得分類器僅僅通過累加操作就能應用于增量學習任務中，實現了隨樣本的獲得而動態修正模型參數，并最終獲得與樸素貝葉斯在完整數據集進行批量學習相同的模型，從而克服了批量學習要求樣本一次性獲得的問題。

2　類別的增量學習

前人提出的增量貝葉斯模型屬于數據增量的范疇，用于不能一次性獲得全部訓練數據的場景。通過不斷學習新產生的樣本修正當前模型，從而改善預測性能。所以在式(7)中看到，對新引入類別，該如何處理，并沒有給出描述。對于新出現類別進行增量學習，使得分類模型隨著這種樣本的不斷出現而逐漸學習這個類別的知識，最終實現對此類別的識別，在一些實際問題中是重要的。因為在學習過程中數據是隨時間產生的，很難保證每次產生的增量集都包含所有類別的樣本。在復雜系統中，重新訓練模型的代價有時是難以接受的。如文獻[16]所描述的生物圖像數據庫的建立，全部物種圖像不能一次性獲得的，起初的分類器并不能正確識別新的物種圖像。因此，系統應當增量的學習新類別圖像的知識，而非對系統進行重新訓練。故本文基于貝葉斯估計方法，對于學習帶有新類別標示的樣本時，參數估計與模型修正公式進行論證。并給出了修正方法的數學表達。

(8)

與此同時，應當對模型中的其他p(Y=yi),i≠m+1參數進行修正，如式(9)：

(9)

(10)

(11)

至此，給出完整類別增量修正參數的數學表達如式(12)，對帶有新類別的樣本，學習的過程就是向原有模型添加新參數，并對其進行估計，再將其他相關參數進行修正的過程。

(12)

3　樣本選擇與類別間的不平衡性

文獻[9]中認為增量學習過程中，對于增量集中的標記數據應當逐漸全部學習，隨后用半監督學習方式追加一定數量的無標記數據進行訓練，以提高分類效果。并使用精度作為衡量分類效果的標準。這種方式存在三個問題，其一，實驗表明并非所有標記樣本都是值得學習的，應采取相應的策略對待學習樣本進行甄選。其二，其假設所使用的訓練集中各類別被近似相同數量的樣本所代表，而在一些情況中，數據集中的類別分布是非常不平衡的[17]。最后，在數據不平衡的情況下僅僅用精度來衡量分類性能是片面的。因此，本文引入最小化風險決策的思想克服此問題，并分別從精度與召回率兩個角度進行分析評價。

(13)

(14)

取UCI數據集中Car Evaluation對增量貝葉斯模型進行驗證，數據集由4種類別的1728個實例構成，每個實例有6個特征屬性與1個類別屬性。從完整數據集中，取其中3種類別的1663個實例用來測試。隨機取出663個實例作為測試集，記為T。剩余數據共有1000個實例涵蓋3種類別，將其記為D。再將D分為5份，記為S1…S5。每個子集隨機分配200個實例 ，使用增量學習方式進行訓練。同時，使用樸素貝葉斯在D上做批量訓練。在測試集T上對比二者精度，實驗結果如表2所示。

表2　精度測試結果

從結果中看出，模型精度并沒有隨著學習樣本數量的增多而提高的。相反地，模型精度呈現下降趨勢，直至獲得與樸素貝葉斯在全集D上批量學習相同的模型為止。單純通過學習更多的帶標注樣本的訓練方式，在一些情況下，會對提高模型精度起反作用。如果待學習的樣本不能改善分類器性能，那么對這些樣本的學習就會既費時又無用。

同時，由于訓練集中樣本數量具有典型的不平衡性特點，造成少數樣本代表的類別呈現不可接受的低識別率。表3列出了Car Evaluation實驗集的類別數量比例與上述增量方法在完成全部增量學后對每個類別的召回情況。從中很直觀地反映出樣本數量傾斜所導致的good類別完全不識別，極大地削弱了分類器的決策價值。

表3　測試結果

對于有標注樣本的學習，文獻[15]中認為被當前分類器錯分的樣本往往帶有更多有價值的信息，應對優先選擇錯分樣本進行學習。而對于訓練集的不平衡性問題，從決策風險的角度來看，傳統貝葉斯分類器基于最大化后驗概率進行決策，其本質等價于在0-1損失下最小化風險。這種決策假設所有的錯誤決策的風險都是相同的。考慮到數據集樣本數量的不平衡性，0-1損失顯然是不合理的。故本文提出錯分代價函數如式(15)。其中count(yi)表示當前訓練集中類別為yi的樣本個數，0<α<1作為一種對決策錯誤的懲罰參數。當α<0.5時，可體現出將訓練集中數量少的類別被預測為數量多的類別，其代價更高。從而使得決策對數量少的類別更加關注。

(15)

進而依據貝葉斯決策理論，此時的風險計算變為了如式(16)所示。而決策也有最大化后驗概率變為了最小化風險。故決策函數也相應調整為式(17)所示:

R(yi|x)=∑p(yj|x)·cost(yj,yi)

(16)

(17)

至此，本文提出一種改進的增量學習算法。在進行增量學習之前，首先，根據當前各類別樣本的數量分布，計算代價矩陣，使用當前模型對增量集進行分類，獲得所有被錯分的樣本形成集合。為了在訓練階段盡量平衡各類別的樣本數量，采取優先學習少數樣本代表的類信息，故將錯分集合中樣本按其類別在訓練集中存在的數量進行升序排序。取出升序后的第一個樣本進行學習，更新貝葉斯模型。隨后，更新代價矩陣。再將已學樣本從增量集中刪除。重復此過程，直至增量集為空或沒有新的錯誤樣本產生。算法描述如下:

增量學習算法模型建立過程:輸入:初始訓練集D,錯分代價參數α輸出:初始貝葉斯模型與代價矩陣利用D建立貝葉斯模型M,并獲得每個類別樣本的數量存于向量ynum[]中;

通過式(15)和ynum計算代價矩陣C;增量學習過程:輸入:增量集S,錯分代價參數α輸出:更新后的分類模型定義錯分集合wset;do初始化錯分集合wset為空;fori=1:|S|用當前模型M對(xp,yp)進行預測;將錯分樣本xp保存于錯誤集wset中;Endfor;將wset中的樣本按它們類別在訓練集中存在的數量進行升序排序;if|wset|>0 從wset中取出第一個錯分樣本(xp,yp); ifyp?Y通過式(12)更新M,并更新ynum;再利用ynum更新代價矩陣C; 從S中刪除xp; Else通過式(7)更新M,并更新ynum;再利用ynum更新代價矩陣C; 從S中刪除xp;Elsebreak;Endif;While(|S|>0);

4　代價函數中參數取值分析

由于本文提出的決策風險函數中含有一個懲罰參數，故現取UCI中的兩個不平衡程度不同的數據集驗證本文算法，從而給出數據集不平衡程度與參數取值關系的分析。所選用的數據集信息如表4列出。從中可見，car數據集屬于嚴重不平，而Spect heart的不平衡程度較輕。

表4　數據集信息

為使得決策更傾向于少數兩樣本的類別，參數的取值應為α∈[0,0.5]，在此區間上進行取值。按照上文的做法，將兩個數據集，都分為6份，5份用于訓練，1份用于測試。分析不同參數取值對各類別召回率的影響，揭示二者之間的關系。圖1與圖2給出了兩個數據集各類別召回率隨參數取值的變化趨勢。

圖1參數與類別召回率的關系

圖2參數與類別召回率的關系

現從兩個角度對上述趨勢進行分析。由于數據集的不平衡，決策應更加關注少數類別。所以，原則上參數取值應越小越好。如圖1與圖2所示，參數取值越接近0，對少數類別的召回率越接近1。但同時，一旦參數取值超過一定界限，便會對原本的多數類別的識別造成影響。圖中同樣反應出，當少數類別的召回接近1時，多數類別的識別呈下降趨勢。原因是當決策對少數類別的傾向到一定極端程度時，少數類別的樣本達到了完全識別，而錯分集中不再包含少數的類別。在依照算法，依然錯分樣本進行學習，不斷增加多數類別樣本的學習數量。更加加劇了決策向少數類別的傾斜。所以，最理想的參數取值應為兩圖中，各類別召回曲線的交點處。其次，圖示所反映的另一種關系則是訓練集的不平衡程度與參數的取值。理想的參數取值應可以反映訓練的不平衡的程度。正如car集的程度相對于Spect heart集更嚴重，故其參數取值也應比Spect heart集的參數取值更小。

5　實驗結果及分析

為驗證模型與算法的有效性，取UCI機器學習數據集中的部分數據分別進行數據增量與類別增量的驗證。并將樸素貝葉斯(NB)與本文算法進行對比。表5列出了數據集信息。

表5　數據集信息

進一步對上述數據進行簡單處理，先將上述每個實驗數據集都隨機分為兩個部分，即訓練集與測試集。再將每個訓練集平均分為5份為增量學習做好準備，各個子集的實例隨機分配。表6描述了每個實驗集的劃分情況。

表6　實驗準備

首先，驗證在6個數據集上驗證數據增量學習。為了得到更為客觀的實驗結果，按照上述數據集劃分比例，在每個實驗數據集上，做5次增量學習直至將完整訓練全部學習。同時，每個實驗集，做5折交叉驗證，交替對換訓練集與測試集中的數據，取5次驗證的結果的均值作為結果的估計，再與樸素貝葉斯在每個完整訓練集上的5折交叉驗證結果的均值做比對。表7則給出了精度結果的對比。

表7　精度對比

表8則列出了本文方法與樸素貝葉斯，在4個不平衡數據集上，各類別召回情況的對比。

表8　召回對比

從上述實驗結果不難發現，在增量學習過程中，選擇適當的樣本進行學習可以逐漸提高分類器精度。同時，由于風險決策的引入使得決策更加的均衡，從而克服了不平衡訓練的帶來的影響。

再次取涵蓋4個類別的完整car數據集，進行類別增量學習的驗證。仍然將此數據集劃分為兩個部分，即訓練集與測試集。其中，訓練集實例個數為1000，而測試集實例個數為728，涵蓋全部4給類別。同樣將訓練集劃分為5個增量子集，將其記為S1,…,S5，而測試集記為T。S1至S2僅僅包含unacc與acc兩個類別的實例。S3至S4包含unacc、acc與good三個類別的實例。S5則包含全部4個類別的訓練實例。表9給出了5次增量訓練，在每一次學習后，測試精度的變化。

表9　類別適應

表9中的結果反映出在增量集S1至S2階段，分類器維持在較低精度。由于此時的訓練集并不包含good與vgood這兩種類別。所以，分類器不能識別測試集中的兩種類別，再加之對一部分已知類別的誤判，使得錯誤率較高。 隨后，在增量集S3與S5被引入后，分類器的性能均有一次較明顯的改善，則是由于引入了代表新類別的訓練實例，使得分類器可以逐漸識別類別good與vgood。最終實現了測試集中全部4個類別的適應。

6　結　語

本文基于貝葉斯估計理對增量貝葉斯模型進行擴展，使其可適應新出現的類別，并引入最小化風險決策克服了不平衡數據集上少數類別召回率低的問題。利用UCI數據集進行測試，證明了改進后的增量模型可以漸進提高分類性能，并具有適應新類別的能力。但本文給出的代價函數仍存在一定的局限性。特別是參數的確定問題，將是我們后續研究的重點。

[1] Giraud Carrier C.A note on the utility of incremental learning [J].AI Communications,2000,13(4): 215-223.

[2] Maloof M A,Michalski R S.Selecting examples for partial memory learning [J].Machine Learning,2000,41(1): 27-52.

[3] Polikar R,Upda L,Upda S S,et al.Learn++: An incremental learning algorithm for supervised neural networks[J].Systems,Man,and Cybernetics,Part C: Applications and Reviews,IEEE Transactions on,2001,31(4): 497-508.

[4] Xiao R,Wang J,Zhang F.An approach to incremental SVM learning algorithm[C]//Tools with Artificial Intelligence,2000.ICTAI 2000.Proceedings.12th IEEE International Conference on.IEEE,2000: 268-273.

[5] Wenhua Z,Jian M.A novel incremental SVM learning algorithm[C]//Computer Supported Cooperative Work in Design,2004.The 8th International Conference on.IEEE,2004,1: 658-662.

[6] Wang W J.A redundant incremental learning algorithm for SVM[C]//Machine Learning and Cybernetics,2008 International Conference on.IEEE,2008,2: 734-738.

[7] Schlimmer J C,Fisher D.A case study of incremental concept induction[C]//AAAI.1986: 496-501.

[8] Utgoff P E.Incremental induction of decision trees[J].Machine learning,1989,4(2): 161-186.

[9] Gong X J,Liu S H,Shi Z Z.An incremental Bayes classification model[J].Chinese Journal of Computers,2002,25(6): 645-650.

[10] Jia H,Murphey Y L,Gutchess D,et al.Identifying knowledge domain and incremental new class learning in SVM[C]//Neural Networks,2005.IJCNN’05.2005 IEEE International Joint Conference on.IEEE,2005,5: 2742-2747.

[11] Domingos P,Pazzani M.On the optimality of the simple Bayesian classifier under zero-one loss[J].Machine learning,1997,29(2-3): 103-130.

[12] Chen L,Zhen N,Guo Y H,et al.Applying Naive Bayesian Incremental Learning In Virus Reporting and analyzing[J].Computer Applications and Software,2010,27(1): 92-95.

[13] Di S,Li H,He P.Incremental Bayesian classification for Chinese question sentences based on fuzzy feedback[C]//Future Computer and Communication (ICFCC),2010 2nd International Conference on.IEEE,2010,1: V1-401-V1-404.

[14] Jeffreys S H.Theory of Probability[M].3d Ed.Clarendon Press,1967.

[16] Ditzler G,Rosen G,Polikar R.Incremental learning of new classes from unbalanced data[C]//Neural Networks (IJCNN),The 2013 International Joint Conference on.IEEE,2013: 1-8.

[17] García-Pedrajas N,Pérez-Rodríguez J,de Haro-García A.OligoIS: scalable instance selection for class-imbalanced data sets[J].Cybernetics,IEEE Transactions on,2013,43(1): 332-346.

ON IMPROVED INCREMENTAL BAYESIAN CLASSIFICATION MODEL

Su ZhitongLi Yang

(CollegeofComputer,NorthChinaUniversityofTechnology,Beijing100144,China)

The research of traditional classification algorithm focuses on the batch learning tasks.Actually,it is not easy to obtain labelled samples once for all.In addition,there is certain limitation in batch learning tasks because the cost of storage space is rather high.Therefore,incremental learning can be referred to as a solution.Naive Bayesian classification is simple,efficient and highly robust,besides,the theory of Bayesian estimation lays the foundation for its application in incremental tasks.However no existing incremental Bayesian model has described the adaptation to new classes.Moreover,the experiment shows that the imbalance in numbers of different samples between classes will have a great impact on the classification performance of the model.Therefore,based on the above two problems,we present to improve the incremental Bayesian model and to increase of formulas of parameters modification so as to enable the model to adapt to new classes.Also the idea of risk decision minimisation is introduced to reduce the impact of data imbalance.Simulation is carried out on UCI dataset,result indicates that the improved incremental model can improve the classification performance gradually and has the adaptability to new classes.

Machine learningNaive BayesIncremental learningRisk minimisation

2015-03-16。國家自然科學基金項目(61105045);中央支持地方專項(PXM2014_014212_000097);北方工業大學科研人才提升計劃項目(CCXZ201303)。蘇志同，教授，主研領域：數據挖掘、數字媒體技術。李楊，碩士生。

TP181

A

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