面向不平衡數據集分類模型的優化研究

,,

(1.東北林業大學 信息與計算機工程學院,哈爾濱 150040; 2.國家林業局 哈爾濱林業機械研究所,哈爾濱 150086)

0 概述

在這個信息大爆炸的時代,為了從海量數據中挖掘出有效信息[1],許多實際應用的數據集需要進行分類處理,如防火墻過濾、入侵檢測[2]和缺陷預測[3]等。但多數情況下,這些數據集是不平衡的,表現出來的現象是,數據集中各個樣本之間的數量差距懸殊。在機器學習過程中,一般將數據集中關于類別分布的不均衡問題稱為數據集的不均衡問題(Class Imbalance Problem of Data Set,CIPD),體現在樣本的數量差異較大。采用傳統分類方法解決CIPD時,分類結果往往傾向于多數類。對CIPD學習效果進行改善,提高CIPD的分類準確率是當前機器學習算法領域的熱點之一[4-6]。

支持向量機以其效果穩定、精確度高的優點得到了廣泛應用。但是在利用支持向量機(Support Vector Machine,SVM)對不均衡數據集分類時效果都不夠理想,原因是SVM算法學習得到的超平面傾向于少數類樣本,導致分類器性能較差。

過采樣通過生成少類樣本來減少數據的不均衡性。文獻[7]提出SMOTE算法,該算法通過隨機合成而不是復制少類樣本的方式有效解決了過擬合的現象,但是由于沒有對少類樣本進行區域劃分,致使合成的樣本分布區域存在局限性。

針對SMOTE算法的不足,文獻[8]提出了B-SMOTE算法,用SMOTE算法對決策邊界的少數類樣本進行人工合成。文獻[9]提出了對錯分樣本進行循環采樣人工合成新樣本的方法(L-SMOTE)。雖然這些方法有效地提升了SMOTE算法的性能,但是仍然存在一些不足。如B-SMOTE算法在執行過程中,忽略了決策邊界外的少類樣本中的重要信息;L-SMOTE算法在執行過程中,忽視了錯分樣本中的噪聲點,不斷合成新的噪聲樣本,影響了分類精確度。

文獻[10]通過精確選擇參數ε值提高了ε-SVM在均衡與不均衡數據集上的分類精度。文獻[11]引入雙隸屬度的非對稱加權算法對混合核SVM的核函數進行優化,并將其應用到不平衡數據集分類中。以上2種方法有效改善了分類算法對不平衡數據集的分類效果,但是到目前為止,對于混合核ε-SVM的優化方法只涉及到預測方面,而關于混合核ε-SVM對不平衡數據集分類方面的優化方法還沒有提出過。

針對以上不足,本文提出一種從樣本采樣和分類算法兩方面同時優化的分類模型。在樣本采集方面,給出一種面向決策邊界少類樣本循環過采樣的LD-SMOTE算法,并將新生成的樣本集與決策邊界外新生成的少類樣本進行合并。在分類算法方面,將正負懲罰系數引入到混合核ε-SVM中,并將更具有客觀性的熵值法運用到懲罰系數的選擇上。

1 基于決策邊界的L-SMOTE優化方法

1.1 L-SMOTE算法

和傳統的SMOTE算法不同,L-SMOTE算法關注的是影響分類平面的錯分樣本,根據錯分樣本循環合成新樣本,提升這些關鍵樣本的質量,提高分類的精確度。

但是該算法在執行時存在一定的缺陷,如圖1所示,P3、P4和P5是少數類樣本,P1和P2是新生成的樣本,P2是較為合理的合成樣本,但是P1的有效性卻是值得商榷的,因為P1生成的位置正好位于多數類的散列點中間,屬于噪聲點,根據L-SMOTE算法,P1點是錯分樣本點,采取錯分樣本的重采樣,那么生成的新樣本也必然是噪聲點,循環執行將會嚴重影響分類效果。

圖1 合成樣本的有效性

1.2 D-SMOTE算法

因為錯分類樣本主要集中在決策邊界,只對決策邊界的少類樣本進行循環重采樣就會有效避免噪聲點的不斷生成。針對決策邊界少類樣本的人工合成,本文提出一種基于樣本間距的決策邊界過采樣算法(D-SMOTE)。

該算法的具體步驟如下:

步驟4對各個決策樣本計算在少數類樣本集中的k近鄰,從中任取一個aj,利用aj和ai兩個樣本,結合SMOTE算法合成新的樣本。公式如下:

anew=ai+random(0,1)×|ai-aj|

(1)

在對決策邊界的少類樣本進行人工合成時,本文用D-SMOTE算法取代傳統的B-SMOTE算法,因為B-SMOTE算法在處理少數類樣本極少的樣本集時,往往會造成合成的新樣本分布不均、過于集中的現象,而D-SMOTE通過比對數類和多數類樣本的間距來確定決策邊界樣本,有效地控制了決策樣本的分布范圍,樣本分布更均勻,提升了決策邊界樣本集的質量。

1.3 LD-SMOTE算法

將本文提出的D-SMOTE算法與L-SMOTE算法相結合,得到LD-SMOTE算法。該算法的具體操作步驟如下:

步驟1用D-SMOTE算法選出少數類樣本的決策樣本集合,記為Pd。

步驟2用標準SMOTE算法對少數類樣本進行人工合成,合成后的新樣本集合記作Pl。

步驟3用標準SMOTE算法對Pd中的樣本進行人工合成,生成新的樣本集合,記為Pe。

步驟4令Pd=Pe,Pld=Pd+Pl,重復步驟3,直到Pld=nN。

Pld就是LD-SMOTE算法執行后最終得到的少數類樣本集,與B-SMOTE算法合成的樣本集不同,該樣本集包含了非決策邊界的少數類樣本的重要信息,而且通過循環合成讓決策邊界的少數類樣本能夠反復學習,從而提高了最終合成的少數類樣本集的質量。

該算法的偽碼如下:

輸入樣本集T,少數類樣本集P,多數類樣本集N,少數類樣本數量nP,多數類樣本數量nN

輸出最終生成的少數類樣本集:Pld

1. Pd= D-SMOTE(P)

2. Pl= SMOTE(P)

3. Pe= SMOTE(Pd)

4. Pd=Pe,Pld= Pd+ Pl

5. While Pld!= nN

6. Pe= SMOTE(Pd)

7. Pd=Pe,Pld= Pd+ Pl

8. Endwhile

2 基于熵值法的混合核ε-SVM優化方法

2.1 ε-SVM

SVM分為線性可分、非線性可分以及需要核函數映射3種情況。設訓練樣本T={(xi,yi)}(i=1,2,…,l),xi為SVM的輸入特征,yi為類別標簽,l為訓練樣本個數?；诙诸惸繕撕撕瘮礢VM實現非線性劃分的分類算法,其模型的原始問題可表示為:

s.t.yi((w·φ(xi))+b)≥1-ξi,i=1,2,…,

ξi≥0,i=1,2,…,l

(2)

其中,w是一個被確定的權重向量,C和ζi分別為懲罰系數和松弛變量。

L(y,f(x,a))=L(|y-f(x,a)|ε)

(3)

f(xi)=ω·φ(xi)+b

(4)

其中,ω為回歸系數,φ(xi)為輸入空間到特征空間的映射函數,b為閾值。

2.2 混合核函數

混合核函數是指通過組合的方式將單個核函數合并成新的核函數,同時考慮局部核函數和全局核函數的特性,將兩者的優勢充分發揮,彌補兩者在應用上的不足。由于Polynomial核函數有著良好的全局性質,而RBF核函數則是局部性強,本文將這2種核函數組合起來,得到學習能力和推廣性都很強的混合核函數,其構造形式如下:

kPoly=[(x×xi)+1]q

(5)

kRBF=exp(-‖x-xi‖2/σ2)

(6)

k(x,x′)=λkPoly(x,x′)+(1-λ)kRBF(x,x′)

(7)

(8)

式(5)和式(6)分別表示Polynomial核函數和RBF核函數。式(7)表示構造的混合核函數,其中的λ表示的是單個核函數在混合核函數中占有的比重,0<λ<1。式(8)表示的是Mercer核函數約束條件。將k(x,x′)帶入到式(8)中,符合Mercer核函數約束條件[14-15]。文獻[14]已對k(x,x′)的線性組合進行驗證,滿足Mercer條件,這里不作具體論證。

將混合核函數植入到傳統的ε-SVM,構造成混合核ε-SVM,分類算法具有了更強大的學習能力和泛化能力。

2.3 混合核ε-SVM的優化

通過LD-SMOTE算法生成新樣本能夠使樣本數據集變得均衡,但是擴充樣本集合時,并不能改變原有樣本分布的外圍輪廓特征,這就意味著對分類問題中分類邊界的影響比較小,所以利用混合核ε-SVM訓練樣本時超平面依然會偏向少數類,分類效果依然會受到影響。受文獻[16]的啟發,在樣本訓練過程中,將正負懲罰系數C+和C-引入到混合核ε-SVM中,并在正負懲罰系數的選擇上運用了熵值法進行優化。

1)正負懲罰系數

二分類平面圖如圖2所示。圓和星分別表示多數類樣本和少數類本,虛線表示的是使用一個懲罰系數時的分割效果。在這種情況下,如果對2類樣本賦予不同的懲罰系數C+和C-,靈活地調節誤差代價,最終就會得到理想的分類效果,圖中的實線表示調整正負懲罰系數后的分割效果。

圖2 二分類平面圖

通過以上分析,結合式(2)～式(4)、式(7),最終推導出改進的混合核ε-SVM的約束化問題:

i=1,2,…,l

(9)

其中,ζi和ζi*為松弛因子,C+和C-表示少類樣本(正類)和多類樣本(負類)的懲罰系數。

在懲罰系數C+和C-的選擇上,傳統方法都沒有考慮到樣本內各個屬性的相對變化程度,使得懲罰系數在選擇上過分依賴個人經驗,具有很強的主觀性。

2)熵值法確定正負懲罰系數

本文將信息熵的思想用于到懲罰系數的選擇上,提出熵值法[17]確定懲罰系數的方法。根據多數類和少數類樣本的離散程度確定不同的懲罰系數,避開主觀人為因素的干擾,即一種客觀的賦值方法,選出的懲罰系數更具有價值,其具體實現方法如下:

(10)

同理,負類樣本S-包含m個子類,負類樣本S-的熵值為:

(11)

計算正類樣本S+和負類樣本S-的差異性系數,將式(10)、式(11)代入得:

(12)

(13)

其中,d+、d-分別表示正類和負類的差異性系數。令C+=C,得:

(14)

通過以上優化方法,使得分類算法在對不平衡數據集分類時的性能進一步提高。在參數的選擇上,本文利用文獻[18]提出的AMPSO算法進行參數尋優。將優化后的混合核ε-SVM算法和LD-SMOTE算法相結合,最終得出本文的分類模型,如圖3所示。

圖3 本文的分類模型

本文的分類模型偽碼如下:

輸入訓練樣本集中的多數類樣本D1,訓練樣本集中的少數類樣本D2,測試數據集D3

輸出D3數據集的分類結果

1.計算LD-SMOTE決策邊界樣本語料庫

2.計算SMOTE非決策邊界樣本語料庫

3.DNEW = LD-SMOTE + SMOTE

4. 使用式(11)～式(16)訓練模型ε-SVM參數

5.result =[]

6.for i in range(0,len(D3))

7. result_D3 =ε-SVM(D3[i])

8. result.append(result_D3)

9.end for

10.return result

3 實驗設置與結果分析

3.1 數據來源

為了驗證本文提出的分類模型的分類效果,采用UCI數據集[19]中的6個不平衡數據集作為測試性能的數據,各個數據集的信息如表1所示,其中的比例表示的是少數類與多數類的比值。

表1 不平衡數據集

3.2 分析指標

在對不平衡數據集進行分類時,常用的分析指標有3種,分別是查準率(Precision)p、敏感度(Sensitivity)s和綜合考慮F-measure指標f,具體公式如下:

(15)

(16)

(17)

其中,FP表示將負類樣本錯分成正類的數目,FN是指將正類樣本錯分成負類的數目,TP表示正類樣本被正確分類的個數。

3.3 實驗結果分析

將數據的70%作為樣本的訓練集,30%作為樣本的測試集。利用word2vec對樣本進行詞向量的訓練,生成向量空間。實驗中所有的數據集都采用了5折交叉驗證,以便于驗證分類模型的性能。

1)近鄰值參數k值的確定

k值的選擇對于本文提出的LD-SMOTE算法至關重要,將k值范圍設置在2～10之間進行討論。實驗數據采用UCI不平衡數據集中30%的測試數據,對6個數據集分別進行測試,將不同k值下的F-measure值作為評價指標,F-measure取6個數據集的平均值。用本文提出的改進混合核ε-SVM作為分類算法,圖4表示的是在本文分類算法下,不同k值取得F-measure值的折線圖。當k值到6時,F-measure達到最高值,因此在接下來的實驗中,將LD-SMOTE算法的k值設定為6。

圖4 不同k值下的實驗結果

2)3種分類算法的實驗結果對比

實驗采用abalone作為測試數據集,該數據集是一個極度不均衡的數據集。該實驗用本文提出的LD-SMOTE算法進行樣本過采樣處理,然后用改進的混合核ε-SVM算法、改進的單核ε-SVM算法(采用RBF核函數,運用熵值法確定正負懲罰系數)和傳統的ε-SVM算法(采用RBF核函數)進行學習和最終的預測,利用文獻[18]提出的AMPSO算法對3種分類算法進行參數優化,下面的實驗均用該方法進行參數優化。實驗采用查準率、敏感度和F-measure值作為評估標準。利用AMPSO算法尋找出最優參數組合如表2所示,實驗結果如圖5所示。

表2 參數尋優結果

圖5 3種分類算法的實驗結果

如圖5所示,本文提出的改進混合核ε-SVM的3個評估指標比其他2種分類算法明顯提高。因為采用了熵值法確定正負懲罰系數,所以在處理極度不均衡數據集時,2種改進算法的分類精度要比傳統ε-SVM算法有所提高。而混合核比單核分類精確度高是因為混合核函數具有更強的泛化能力和魯棒性。

3)傳統SMOTE算法和LD-SMOTE算法的分類結果對比

實驗采用6個不平衡數據集作為測試數據集,分類算法均采用標準SVM,F-measure值作為評估標準,實驗結果如圖6所示。

圖6 2種采樣算法的實驗結果

實驗結果表明,LD-SMOTE+SVM的分類精確度比SMOTE+SVM算法有明顯提升。但是當樣本集極度不均衡時(abalone數據集),只對訓練樣本進行重采樣處理,不對分類算法進行改進,分類精確度明顯偏低。

4)3種分類方法實驗結果對比

為了更好地驗證本文提出的分類模型的性能,在相同實驗條件下,與標準的SVM[20]和SD-ISMOTE+SVM[21]進行實驗比較。實驗選用F-measure指作為評價標準。實驗結果如表3和圖7所示。

表3 3種分類方法的F-measure值對比 %

圖7 3種分類方法的實驗結果

表3顯示了3個算法對6個數據集進行分類預測的實驗結果。實驗結果表明,本文提出的分類模型比SD-ISMOTE+SVM和標準SVM在F-measure值上取得了明顯提升。F-measure值比標準SVM平均高出18.1%,比SD-ISMOTE+SVM平均高出4.35%,說明本文提出的分類模型在對不平衡數據集進行分類時具有明顯優勢。

在圖7中,標準SVM算法的折線始終在圖像的最下方,尤其是在car和abalone兩個數據點上,其F-measure值達到了最低。產生的原因是,標準SVM算法沒有對訓練樣本做任何處理,尤其是當數據集的正負類樣本數量差距懸殊,分類平面嚴重向另一側傾斜時,如果直接采用SVM算法對測試樣本進行分類,分類的精確度會大大降低。而本文的分類模型和SD-ISMOTE+SVM都針對不平衡的訓練樣本集進行過采樣處理,都獲得了較好的分類效果。但是本文的分類模型的分類精確度更高一些,原因在于在分類算法的改進上,將正負懲罰系數、熵值法和多核學習引入到支持向量機中,進一步提高了分類模型的分類性能。

4 結束語

本文構建一種面向不平衡數據集的分類模型。在樣本集過采樣優化方面,針對L-SMOTE算法對錯分樣本進行循環采樣時不斷生成噪聲點的問題,通過對決策邊界樣本進行循環過采樣的方法生成新的樣本集,并將第一次過采樣時生成的決策邊界范圍外的少類樣本添加到新生成的樣本集中,提升了樣本的重要度。在算法優化方面,針對傳統的ε-SVM算法在對不平衡數據集分類時超平面偏移的問題,把正負懲罰系數引入到支持向量機模型中,并且采用了更具有客觀性的熵值法選取懲罰系數。同時構造了混合核ε-SVM,加強了支持向量機的泛化能力和學習能力,分類精確度明顯提高。下一步將改進粒子群算法,選出最優參數,并減少算法運行消耗的時間。

[1] GARCA S,LUENGO J,HERRERA F.Data preprocessing in data mining[M].Berlin,Germany:Springer,2016.

[2] 沈夏炯,王 龍,韓道軍.人工蜂群優化的BP神經網絡在入侵檢測中的應用[J].計算機工程,2016,42(2):190-194.

[3] YU Qiao,JIANG Shujuan,ZHANG Yanmei.The performance stability of defect prediction models with class imbalance:an empirical study[J].IEICE Transactions on Information & Systems,2017,100(2):265-272.

[4] ZHANG Chunkai,WANG Guoquan,ZHOU Ying,et al.A new approach for imbalanced data classification based on minimize loss learning[C]//Proceedings of the 2nd International Conference on Data Science in Cyberspace.Washington D.C.,USA:IEEE Press,2017:82-87.

[5] NAPIERALA K,STEFANOWSKI J.Types of minority class examples and their influence on learning classifiers from imbalanced Data[J].Journal of Intelligent Information Systems,2016,46(3):563-597.

[6] HERRERA F.Cost-sensitive linguistic fuzzy rule based classification systems under the MapReduce framework for imbalanced Big Data[J].Fuzzy Sets & Systems,2015,258(3):5-38.

[7] CHAWLA N V,BOWYER K W,HALL L O,et al.SMOTE:synthetic minority over-sampling technique[J].Journal of Artificial Intelligence Research,2002,16(1):321-357.

[8] HAN Hui,WANG Wenyuan,MAO Binghuan.Borderline-SMOTE:a new over-sampling method in imbalanced data sets learning[C]//Proceedings of International Conference on intelligent Computing.Berlin,Germany:Springer,2005:878-887.

[9] 衣柏衡,朱建軍,李 杰.基于改進SMOTE的小額貸款公司客戶信用風險非均衡SVM分類[J].中國管理科學,2016,24(3):24-30.

[10] 楊俊燕,張優云,朱永生.ε不敏感損失函數支持向量機分類性能研究[J].西安交通大學學報,2007,41(11):1315-1320.

[11] 趙淑娟.基于非對稱加權和核方法的不平衡數據集[D].南京:南京郵電大學,2013.

[12] ALZATE C,SUYKENS J.Kernel component analysis using an epsilon-insensitive robust loss function[J].IEEE Transactions on Neural Networks,2008,19(9):1583-1598.

[13] WATANABE K.Vector quantization based on ε-insensitive mixture models[J].Neurocomputing,2015,165(3):32-37.

[14] 唐 奇,王紅瑞,許新宜,等.基于混合核函數SVM水文時序模型及其應用[J].系統工程理論與實踐,2014,34(2):521-529.

[15] 顏根廷,馬廣富,肖余之.一種混合核函數支持向量機算法[J].哈爾濱工業大學學報,2007,39(11):1704-1706.

[16] 劉東啟,陳志堅,徐 銀,等.面向不平衡數據分類的復合SVM算法研究[EB/OL].[2017-11-06].http://kns.cnki.net/kcms/detail/51.1196.TP.20170401.1738.050.html.

[17] 朱喜安,魏國棟.熵值法中無量綱化方法優良標準的探討[J].統計與決策,2015(2):12-15.

[18] FRANK A,ASUNCION A.UCI machine learning repository[EB/OL].[2017-11-06].http://archive.ics.uci.edu/ml.

[19] 劉文貞,陳紅巖,李孝祿,等.基于自適應變異粒子群算法的混合核ε-SVM在混合氣體定量分析中的應用[J].傳感技術學報,2016,29(9):1464-1470.

[20] 常甜甜.支持向量機學習算法若干問題的研究[D].西安:西安電子科技大學,2010.

[21] 古 平,楊 煬.面向不均衡數據集中少數類細分的過采樣算法[J].計算機工程,2017,43(2):241-247.