王思晨 丁家滿

摘要：不平衡數(shù)據(jù)在各個應(yīng)用領(lǐng)域普遍存在。在處理不平衡數(shù)據(jù)時，破壞原始數(shù)據(jù)的分布特點和丟棄多數(shù)類樣本的潛在信息都會降低分類精度，為此，提出一種不平衡數(shù)據(jù)集成分類方法。從多數(shù)類樣本中依據(jù)計算得到的綜合權(quán)重進行隨機采樣，并與少數(shù)類樣本組成新的訓(xùn)練樣本子集；為了保證基分類器的差異性，將投影得到的不同樣本子集作為各個基分類器的訓(xùn)練樣本，通過多分類器集成學(xué)習(xí)獲得最終分類結(jié)果；在UCI數(shù)據(jù)集下進行實驗。結(jié)果表明，該方法不僅能夠提高少數(shù)類樣本的分類性能，而且能夠有效提高整體分類精度。

關(guān)鍵詞：不平衡數(shù)據(jù)；分類；集成學(xué)習(xí)；綜合權(quán)重

DOIDOI：10.11907/rjdk.173258

中圖分類號：TP301

文獻標識碼：A 文章編號文章編號：1672-7800（2018）008-0076-05

英文摘要Abstract：Imbalanced data is widespread in various application fields.When dealing with imbalanced data，breaking the distribution characteristics of the original data and discarding the latent information in the majority class samples will decrease classification accuracy.Therefore，in this paper，an integrated classification method for imbalance data is proposed.Firstly we randomly extract from the majority samples based on the calculated comprehensive weight，combine the extracted samples with the minority samples into new training samples； then，in order to ensure the difference between the base classifiers，we use the same subset of projections as the training samples of each base classifier，and get the final classification results by ensemble learning of multiple classifiers.Finally，experiments have been done on UCI data sets and the results show that this method can not only improve the classification performance of the minority class samples，but also effectively improve the overall classification accuracy.

英文關(guān)鍵詞Key Words：imbalance data；classification；ensemble learning；comprehensive weight

0 引言

分類是數(shù)據(jù)挖掘、機器學(xué)習(xí)領(lǐng)域研究的重要內(nèi)容，可以有效幫助人們對獲取的數(shù)據(jù)進行預(yù)測分析、對未知的模式樣本進行判斷識別。目前，已有許多經(jīng)典的分類算法，例如人工神經(jīng)網(wǎng)絡(luò)、決策樹、支持向量機（SVM）等，用它們對平衡數(shù)據(jù)進行分類一般都能取得較好的分類效果。但是在實際應(yīng)用中不平衡數(shù)據(jù)普遍存在于各個應(yīng)用領(lǐng)域，例如文本分類[1]、疾病診斷[2]以及網(wǎng)絡(luò)入侵檢測[3]等。然而傳統(tǒng)分類算法為了追求總體分類性能，通常只基于平衡數(shù)據(jù)分布或者忽略樣本中的少數(shù)類樣本，從而導(dǎo)致少數(shù)類樣本分類準確率過低，分類器性能下降[4-7]。因此，研究用于處理不平衡數(shù)據(jù)集的分類方法，有效提高對少數(shù)類的分類準確率與分類器的整體性能顯得尤為重要。

當前，不平衡數(shù)據(jù)分類問題的解決思路主要包括改變數(shù)據(jù)分布和改進已有分類算法。改變數(shù)據(jù)分布以達到數(shù)據(jù)平衡最常見的策略有隨機過采樣（over-sampling）、隨機欠采樣（under-sampling）[8-9]。隨機過采樣是指對少數(shù)類的樣本進行復(fù)制，使數(shù)據(jù)集的樣本數(shù)達到平衡，隨機欠采樣則以一定策略選取多類樣本中的一個子集達到同樣目的。過采樣中應(yīng)用最廣泛的是 Chawla 等[10]提出來的SMOTE 算法，該算法的本質(zhì)是改進隨機過采樣策略，通過擴充少數(shù)類樣本集使得樣本數(shù)目達到均衡。文獻[11]提出基于RSBoost算法的不平衡數(shù)據(jù)分類方法，該方法采用SMOTE算法對少數(shù)類進行過采樣處理，然后對整個數(shù)據(jù)集進行隨機欠采樣處理，以改善整個數(shù)據(jù)集的不平衡性，提高少數(shù)類的分類準確性。文獻[12]針對采用隨機過采樣處理不平衡數(shù)據(jù)后，可能會導(dǎo)致不平衡數(shù)據(jù)集分布的整體變化以及模糊正負類邊界問題，提出基于 KM-SMOTE 和隨機森林的不平衡數(shù)據(jù)分類方法。文獻[13]提出的RUSBoost算法是在AdaBoost算法迭代過程中采用隨機欠采樣技術(shù)（RUS）從多數(shù)類中隨機選擇樣本，但不分配新的權(quán)重，從而使算法更加關(guān)注少數(shù)類樣本，該算法具有實現(xiàn)簡單、訓(xùn)練時間短等優(yōu)勢，但是在欠采樣中可能會移除潛在的有用多數(shù)類樣本。文獻[14]提出了EusBoost算法，采用欠采樣方法選擇多數(shù)類樣本中具有代表性的樣本，實現(xiàn)樣本數(shù)據(jù)平衡，并引入適應(yīng)度函數(shù)保證基分類器的差異性，最終提高不平衡數(shù)據(jù)的分類精度。文獻[15]提出一種新的不平衡數(shù)據(jù)學(xué)習(xí)算法PCBoost，該算法用數(shù)據(jù)合成方法添加合成的少數(shù)類樣本，以平衡訓(xùn)練樣本。文獻[16]提出一種處理不平衡數(shù)據(jù)的欠采樣方法，用以解決因樣本過于集中導(dǎo)致的過擬合問題。文獻[17]提出一種過采樣算法，將過采樣與欠采樣進行融合，利用過采樣的優(yōu)點增加少數(shù)類樣本數(shù)量，使分類器能夠更好地提高少數(shù)類的分類性能。文獻[18]提出多類類別不平衡學(xué)習(xí)算法EasyEssemble M，該算法采用多數(shù)類樣本多次隨機欠采樣方法，學(xué)習(xí)多個子分類器提高分類效果。雖然以上通過改變數(shù)據(jù)分布達到數(shù)據(jù)平衡的算法能夠在一定程度上解決多類類別不平衡問題，但是存在一定的局限性：簡單機械地采樣將破壞原始數(shù)據(jù)的分布特點，移除過多的多類樣本將會導(dǎo)致信息丟失[19]。

現(xiàn)有不平衡數(shù)據(jù)處理方法的另一種思路是改進已有分類算法。如文獻[20]在AdaBoost算法基礎(chǔ)上使用基于級聯(lián)模型的分類器，以逐步縮小多類別，使數(shù)據(jù)集趨于平衡，通過迭代訓(xùn)練得到一系列分類器并以集成方式對預(yù)測樣本進行分類。文獻[21，22]針對現(xiàn)有AdaBoost系列算法未考慮類的先驗分布問題，改進并提出了不平衡分類問題連續(xù)AdaBoost算法。文獻[23]在SVM分類算法基礎(chǔ)上，針對不平衡數(shù)據(jù)導(dǎo)致SVM的分類超平面偏移問題，提出了一種改進 SVM-KNN 算法。這些改進方法能夠在某種程度上提高分類精度，但泛化性不夠強大，并且算法參數(shù)和閾值的設(shè)定或選取存在一定主觀性，稍有不當將破壞原始數(shù)據(jù)的分布特點且無法充分利用多數(shù)類樣本潛在信息[24]。

綜上所述，雖然以上兩種思路及方法能夠在特定環(huán)境下一定程度上解決數(shù)據(jù)不平衡問題，但是數(shù)據(jù)平衡按比例機械地抽樣將破壞原始數(shù)據(jù)的分布特點，而對多數(shù)類樣本進行簡單抽樣則可能移除潛在有用分類信息，導(dǎo)致分類效率低、分類精度差等問題。

針對上述問題，本文提出一種不平衡數(shù)據(jù)集成分類方法（Integrated Classification Method for Imbalanced Data，簡稱ICMID），首先多數(shù)類樣本中依照多數(shù)類樣本的權(quán)重以及少數(shù)類樣本得到的綜合權(quán)重進行不放回隨機抽取，并與少數(shù)類樣本組成訓(xùn)練樣本集；再隨機選取若干項特征構(gòu)造特征子集，將特征子集對訓(xùn)練樣本子集進行投影，得到的對應(yīng)特征子集樣本作為算法訓(xùn)練基分類器的訓(xùn)練樣本，經(jīng)過多次迭代產(chǎn)生多個弱分類器，通過弱分類器權(quán)重投票得出最終輸出結(jié)果。因此，在保證基分類器差異性的前提下，提高了少數(shù)類的分類準確率，還挖掘了多數(shù)類樣本中的潛在有用信息。

1 問題描述與建模

2 不平衡數(shù)據(jù)集成分類方法

為了保持原始數(shù)據(jù)的分布特點，更好地利用潛在有用的分類信息，保證集成學(xué)習(xí)中各分類器之間的差異性，本文提出基于綜合權(quán)重的不平衡數(shù)據(jù)集成分類方法。主要包括3個階段：①去除多數(shù)類中的噪聲樣本；②通過綜合樣本權(quán)重抽取多數(shù)類樣本生成合成樣本集；③訓(xùn)練不同的基分類器進行集成分類。具體流程如圖1。

2.1 不平衡數(shù)據(jù)處理

為了保持原有樣本的分布特點，同時又能更好地利用多數(shù)類樣本中潛在有用的信息，在不平衡數(shù)據(jù)處理階段，首先循環(huán)隨機選取n個特征子集，然后按照少數(shù)類樣本的數(shù)量和多數(shù)類樣本中每個類別樣本數(shù)量占比計算綜合權(quán)重，并依據(jù)綜合權(quán)重抽取每一類別的樣本數(shù)量，再將少數(shù)類樣本與抽取的樣本組合，使少數(shù)類樣本在訓(xùn)練樣本中所占比例升高，重復(fù)抽取M次，最后獲得處理過的訓(xùn)練樣本子集和特征子集。具體過程見算法1。

為了增強分類器之間的差異性以及提高分類準確率，做法如下：第一，根據(jù)特征子集Fi對訓(xùn)練樣本子集D′j進行投影，得到相對應(yīng)特征子集的樣本Yij，將該樣本作為訓(xùn)練基分類器的樣本；第二，初始化樣本權(quán)重；第三，通過T次迭代訓(xùn)練得到多個弱分類器，在每次迭代中計算每個基分類器的錯誤率，判斷分類錯誤率是否超過給定閾值，當超過給定閾值時，說明該部分樣本分類困難，則退出迭代過程進行下一輪，當錯誤率小于給定閾值時，依據(jù)錯誤率更新權(quán)重；第四，依據(jù)所有基分類器錯誤率以及分類正確的樣本個數(shù)綜合計算投票權(quán)重，得出最終輸出結(jié)果。具體過程見算法2。

3 實驗與結(jié)果

3.1 實驗數(shù)據(jù)

為評價本文方法對不平衡數(shù)據(jù)集分類問題的有效性，選擇6個少數(shù)類和多數(shù)類樣本比例不平衡的數(shù)據(jù)集進行實驗，數(shù)據(jù)集來源于 UCI 機器學(xué)習(xí)數(shù)據(jù)庫，見表1。其中數(shù)據(jù)集樣本數(shù)用#Ex表示，#F代表特征數(shù)，#Minority代表少數(shù)類樣本數(shù)，#R代表少數(shù)類樣本占數(shù)據(jù)集的比重。采用決策樹C4.5算法以及AdaBoost.M1算法進行對照，Adaboost.M1迭代時用 C4.5 作為基分類器，迭代 20次，此外還對數(shù)據(jù)采用十交叉驗證。其中，C4.5決策樹算法直接對不平衡數(shù)據(jù)集進行分類，基分類器算法使用C4.5算法，利用weka平臺中J48分類器實現(xiàn)。

3.2 評估指標

采用查全率、查準率和F-measure作為評價分類器性能的指標，其在機器學(xué)習(xí)、數(shù)據(jù)挖掘等領(lǐng)域應(yīng)用廣泛，能被廣大學(xué)者接受。傳統(tǒng)的二分類評價指標基于混淆矩陣，在不平衡數(shù)據(jù)集中正類和反類分別代表少數(shù)類和多數(shù)類。TP和 TN分別表示正確分類的正類和反類樣本個數(shù)；FP表示誤分為正類的樣本個數(shù)；FN表示誤分為負類的樣本個數(shù)，見表2。

3.3 實驗結(jié)果分析

在不平衡數(shù)據(jù)集中，多數(shù)類樣本個數(shù)遠遠多于少數(shù)類，傳統(tǒng)分類算法預(yù)測會傾向于多數(shù)類，如把所有樣本分為多數(shù)類，依然會獲得很高的分類精度，但是卻不能識別一個少數(shù)類。因此在處理不平衡數(shù)據(jù)時，提高少數(shù)類樣本在訓(xùn)練樣本中所占比重，能夠有效提高少數(shù)類樣本的分類性能。從表3及圖2可以看出，不平衡數(shù)據(jù)經(jīng)過處理后，每個數(shù)據(jù)集訓(xùn)練樣本中少數(shù)類樣本的比例明顯提高。

從表4和表5可以看出，AdaBoos.M1算法在Segment、Vehicle數(shù)據(jù)集上的查準率偏低，而C4.5算法在Segment、Sick數(shù)據(jù)集上有較高的查準率和查全率。同AdaBoost.M1和C4.5算法相比較，本文算法在Balance-scale 、Satimage以及Yeast 數(shù)據(jù)集上的查準率具有顯著優(yōu)勢。在這幾個數(shù)據(jù)集上，本文算法顯著優(yōu)于AdaBoost.M1算法，在Segment 、Sick數(shù)據(jù)集上與C4.5算法水平相當。

表6是幾種不同方法在不平衡數(shù)據(jù)分類性能中評估指標F-measure的分類結(jié)果比較。只有當查全率和查準率都較大時，F(xiàn)-measure才會相應(yīng)地較大。因此，F(xiàn)-measure可以合理地評價分類器對于少數(shù)類的分類性能。本文提出采用基于綜合權(quán)重采樣和集成學(xué)習(xí)相結(jié)合的方法處理不平衡數(shù)據(jù)的分類問題，相較于其它兩種方法，分類性能得到大幅度提升。比如在數(shù)據(jù)集Satimage、Sick以及Yeast中比其它兩種算法提高了10%以上。

文獻[15]提出處理不平衡數(shù)據(jù)的PCBoost算法在每次迭代初始，利用數(shù)據(jù)合成方法添加合成的少數(shù)類樣本達到平衡。其在數(shù)據(jù)集Satimage、Segment以及Vehicle中，與本文算法在F-measure方面的比較見圖3。從圖3可以看出，本文算法在數(shù)據(jù)集Satimage中明顯高于PCBoost算法，但是在數(shù)據(jù)集Vehicle明顯低于PCBoost算法，而在數(shù)據(jù)集Segment中兩種方法水平相當。對于每一個數(shù)據(jù)集，PCBoost算法在實驗中選取不同的迭代次數(shù)以獲得最佳預(yù)測性能的分類器，使其在某些數(shù)據(jù)集上比本文算法取得更為明顯的效果。

5 結(jié)語

為了保持原始數(shù)據(jù)的分布特點，更好地利用潛在有用的分類信息，保證集成學(xué)習(xí)中各分類器之間的差異性，本文采用基于綜合權(quán)重采樣與集成學(xué)習(xí)相結(jié)合的方法處理不平衡數(shù)據(jù)分類問題。通過UCI數(shù)據(jù)集實驗，以查全率、查準率和F-measure為度量對算法進行評價，與決策樹算法、AdaBoost.M1算法以及PCBoost算法進行比較，實驗結(jié)果表明本文方法不僅能夠提高少數(shù)類樣本的分類性能，而且能夠有效提高整體分類精度。

在不平衡數(shù)據(jù)處理階段，本文隨機選擇特征構(gòu)成特征子集，并沒有考慮到每個特征對類的貢獻程度以及特征與特征之間對類的貢獻程度；另外還未考慮分類效率問題。因此，將來需考慮對特征的選擇以及提高分類效率，以進一步提高該方法的泛化性能。

參考文獻：

[1] KIM H，HOWLAND P，PARK H.Dimension reduction in text classification with support vector machine[J].Journal of Machine Learning Research，2005，6（1）：37-53.

[2] 鄒權(quán)，郭茂祖，劉揚，等.類別不平衡的分類方法及在生物信息學(xué)中的應(yīng)用[J].計算機研究與發(fā)展，2010，47（8）：1407-1414.

[3] 陸悠，李偉，羅軍舟，等.一種基于選擇性協(xié)同學(xué)習(xí)的網(wǎng)絡(luò)用戶異常行為檢測方法[J].計算機學(xué)報，2014，37（1）：28-40.

[4] CHAWLA N V，JAPKOWICA N，KOTCZ A.Editorial：special issue on learning from imbalanced data sets[J].ACM SIGKDD Explorations Newslettter，2004，6（1）：1-6.

[5] HE H B，EDWARDO A G.Learning from imbalanced data[J].IEEE Transactions on Knowledge and Data Engineering，2009，21（9）：1263-1284.

[6] 陶新民，郝思媛，張冬雪，等.不均衡數(shù)據(jù)分類算法的綜述[J].重慶郵電大學(xué)學(xué)報：自然科學(xué)版，2013，25（1）：102-110.

[7] CEDER A，HASSOLD S，DANO R.Approaching even-load and even-head way transit timetables using different bus sizes[J].Public Transport，2013，5（3）：193-217.

[8] 林智勇，郝志峰，楊曉偉.不平衡數(shù)據(jù)分類的研究現(xiàn)狀[J].計算機應(yīng)用研究，2008，25（2）：332-336.

[9] 錢洪波，賀廣南.非平衡類數(shù)據(jù)分類概述[J].計算機工程與科學(xué)，2010，32（5）：85-88.

[10] 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.

[11] 李克文，楊磊，劉文英，等.基于RSBoost算法的不平衡數(shù)據(jù)分類方法[J].計算機科學(xué)，2015，42（9）：249-252.

[12] CHEN B，SU Y D，HUANG S.Classification of imbalance data based on KM-SMOTE algorithm and random forest[J].Computer Technology And Development，2015，9（25）：17-21.

[13] SEIFFERTC，KHOSHOFTAARTM，VAN H，et al.RUBoost：a hybrida approach total levitating classing balance[J].IEEE Tran on Systems，Man and Cybernetics，PartA：Systems and Humans，2010，40（1）：185-197.

[14] GALAR M，F(xiàn)ERNNDEZ A，BARRENCHEA E，et al.EUSBoost：enchancing ensembles for highly imbalanced data-sets by evolutionary under sampling[J].Pattern Recognition，2013，46（12）：3460-3471.

[15] 李雄飛，李軍，董元方，等.一種新的不平衡數(shù)據(jù)學(xué)習(xí)算法PCBoost[J].計算機學(xué)報，2012，35（2）：2202-2209.

[16] LIN S Y，LI C H，JIANG Y，et al.Under-sampling method research in class-imbalanced data[J].Journal of Computer Research and Development，2011，48（2）：47-53.

[17] HAN H，WANG W Y，MAO B H.Over-sampling algorithm based on AdaBoost in unbalanced data set[J].Computer Engineering，2007，10（33）：207-209.

[18] 李倩倩，劉胥影.多類類別不平衡學(xué)習(xí)算法：EasyEnsemble.M [J].模式識別與人工智能，2014（2）：187-192.

[19] 胡小生，溫菊屏，鐘勇.動態(tài)平衡采樣的不平衡數(shù)據(jù)集成分類方法[J].智能系統(tǒng)學(xué)報，2016，11（2）：257-263.

[20] 劉胥影，吳建鑫，周志華.一種基于級聯(lián)模型的類別不平衡數(shù)據(jù)分類方法[J].南京大學(xué)學(xué)報：自然科學(xué)版，2006，42（2）：148-155.

[21] FU Z L.Real AdaBoost algorithm for multiclass and imbalanced classification problems[J].Journal of Computer Research and Development，2011，48（12）：2326-2333.

[22] 凌曉峰，SHENG V S.代價敏感分類器的比較研究[J].計算機學(xué)報，2007，30（8）：1203-1212.

[23] WANG C X，ZHANG T，MA C.Improved SVM-KNN algorithm for imbalanced datasets classification[J].Computer Engineering and Applications，2016，52（4）：51-55.

[24] 馬彪，周瑜，賀建軍.面向大規(guī)模類不平衡數(shù)據(jù)的變分高斯過程分類算法[J].大連理工大學(xué)學(xué)報，2016，56（3）：279-284.

（責(zé)任編輯：何 麗）