一種不平衡數據集成分類方法

王思晨 丁家滿

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

關鍵詞：不平衡數據；分類；集成學習；綜合權重

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.

英文關鍵詞Key Words：imbalance data；classification；ensemble learning；comprehensive weight

0 引言

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

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

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

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

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

1 問題描述與建模

2 不平衡數據集成分類方法

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

2.1 不平衡數據處理

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

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

3 實驗與結果

3.1 實驗數據

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

3.2 評估指標

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

3.3 實驗結果分析

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

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

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

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

5 結語

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

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

參考文獻：

[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] 鄒權，郭茂祖，劉揚，等.類別不平衡的分類方法及在生物信息學中的應用[J].計算機研究與發展，2010，47（8）：1407-1414.

[3] 陸悠，李偉，羅軍舟，等.一種基于選擇性協同學習的網絡用戶異常行為檢測方法[J].計算機學報，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] 陶新民，郝思媛，張冬雪，等.不均衡數據分類算法的綜述[J].重慶郵電大學學報：自然科學版，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] 林智勇，郝志峰，楊曉偉.不平衡數據分類的研究現狀[J].計算機應用研究，2008，25（2）：332-336.

[9] 錢洪波，賀廣南.非平衡類數據分類概述[J].計算機工程與科學，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算法的不平衡數據分類方法[J].計算機科學，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，FERNNDEZ 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] 李雄飛，李軍，董元方，等.一種新的不平衡數據學習算法PCBoost[J].計算機學報，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] 李倩倩，劉胥影.多類類別不平衡學習算法：EasyEnsemble.M [J].模式識別與人工智能，2014（2）：187-192.

[19] 胡小生，溫菊屏，鐘勇.動態平衡采樣的不平衡數據集成分類方法[J].智能系統學報，2016，11（2）：257-263.

[20] 劉胥影，吳建鑫，周志華.一種基于級聯模型的類別不平衡數據分類方法[J].南京大學學報：自然科學版，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].計算機學報，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] 馬彪，周瑜，賀建軍.面向大規模類不平衡數據的變分高斯過程分類算法[J].大連理工大學學報，2016，56（3）：279-284.

（責任編輯：何 麗）