新的基于代價敏感集成學習的非平衡數據集分類方法NIBoost

王莉 陳紅梅 王生武

摘 要：現實生活中存在大量的非平衡數據，大多數傳統的分類算法假定類分布平衡或者樣本的錯分代價相同，因此在對這些非平衡數據進行分類時會出現少數類樣本錯分的問題。針對上述問題，在代價敏感的理論基礎上，提出了一種新的基于代價敏感集成學習的非平衡數據分類算法——NIBoost （New Imbalanced Boost）。首先，在每次迭代過程中利用過采樣算法新增一定數目的少數類樣本來對數據集進行平衡，在該新數據集上訓練分類器;其次，使用該分類器對數據集進行分類，并得到各樣本的預測類標及該分類器的分類錯誤率;最后，根據分類錯誤率和預測的類標計算該分類器的權重系數及各樣本新的權重。實驗采用決策樹、樸素貝葉斯作為弱分類器算法，在UCI數據集上的實驗結果表明，當以決策樹作為基分類器時，與RareBoost算法相比，F-value最高提高了5.91個百分點、G-mean最高提高了7.44個百分點、AUC最高提高了4.38個百分點;故該新算法在處理非平衡數據分類問題上具有一定的優勢。

關鍵詞：非平衡數據集;分類;代價敏感;過采樣;Adaboost算法

中圖分類號： TP181

文獻標志碼：A

文章編號：1001-9081（2019）03-0629-05

Abstract： The problem of misclassification of minority class samples appears frequently when classifying massive amount of imbalanced data in real life with traditional classification algorithms， because most of these algorithms only suit balanced class distribution or samples with same misclassification cost. To overcome this problem， a classification algorithm for imbalanced dataset based on cost sensitive ensemble learning and oversampling — New Imbalanced Boost （NIBoost） was proposed. Firstly， the oversampling algorithm was used to add a certain number of minority samples to balance the dataset in each iteration， and the classifier was trained on the new dataset. Secondly， the classifier was used to classify the dataset to obtain the predicted class label of each sample and the classification error rate of the classifier. Finally， the weight coefficient of the classifier and new weight of each sample were calculated according to the classification error rate and the predicted class labeles. Experimental results on UCI datasets with decision tree and Naive Bayesian used as weak classifier algorithm show that when decision tree was used as the base classifier of NIBoost， compared with RareBoost algorithm， the F-value is increased up to 5.91 percentage points， the G-mean is increased up to 7.44 percentage points， and the AUC is increased up to 4.38 percentage points. The experimental results show that the proposed algorithm has advantages on imbalanced data classification problem.

Key words： imbalanced dataset; classification; cost sensitive; over-sampling; Adaboost algorithm

0 引言

非平衡數據集的分類是指在各類樣本數目不相等的情況下的分類問題[1]。在實際應用中非平衡數據集分布廣泛，比如醫療診斷、金融詐騙、網絡入侵檢測、電信用戶檢測、石油勘探等[2-6]。傳統的分類算法大部分都以提高分類器總體分類精度為目標，然而當傳統的分類算法應用在非平衡數據集上時很容易造成少數類的錯分。國內外學者通過不斷的研究，從算法層面和數據層面提出了許多改進優化的算法。數據層面主要是通過采樣技術對數據集進行重構，以降低非平衡度進而提高分類準確率。常見的采樣方法有兩種：過采樣和欠采樣。欠采樣是通過減少多數類樣本個數使數據集分布相對平衡。過采樣是通過增加少數類樣本個數使數據集分布相對平衡。Chawla等[7]于2002年提出合成少數類過采樣技術（Synthetic Minority Oversampling TEchnique， SMOTE）算法，其基本思想是在對樣本集中所有的少數類樣本，分別求出與其距離較近的少數類樣本，然后在它們之間通過線性插值的方式來生成新的少數類樣本，以降低數據集的非平衡度。算法層面主要有集成學習、代價敏感和單類別學習等算法。集成學習法是通過對多個基分類器進行集成從而獲得更強的泛化性能。Qian等[8]提出將采樣方法與集成學習理論相結合，其中運用的采樣方法有欠采樣和SMOTE算法。Douzas等[9]提出一種基于k-means聚類和SMOTE的簡單、有效的過采樣方法，該方法設法僅在安全區域進行過采樣來避免產生噪聲。Galar等[10]提出在集成學習中通過對基分類器進行選擇，以提高其分類效率。Zhang等[11]提出通過將少數類與多數類多次組合，得到不同的訓練樣本集，然后再運用集成學習思想進行分類，其結果提高了少數類的分類精度。Kim等[12]提出GMBoost（Geometric Mean based Boosting）算法將弱分類器的評價標準由錯誤率改為多數類樣本錯誤率與少數類樣本錯誤率的幾何均值，然后與采樣算法相結合，以解決非平衡分類問題。李雄飛等[13]提出的PCBoost（Perturbation Correction Boosting）算法，該算法每次迭代開始時通過增加少數類樣本的個數，平衡訓練數據集，在子分類器形成后，刪除分類錯誤的合成樣本，然后通過多個基分類器的組合來解決非平衡的問題，其方法具有很好的泛化能力。He等[14]提出了一種新穎的集成模型，該模型拓展了BalanceCascade方法，且用隨機森林（Random Forest， RF）和XGBoost（eXtreme Gradient Boosting）兩種樹型分類器作為基分類器，具有很高的性能和穩健性。代價敏感學習（Cost Sensitive Learning，SCL）[15]用于處理非平衡分類的基本思路是在非平衡分類中正確識別出少數類樣本的價值比正確識別出多數類樣本的價值要高，因此在分類中應賦予不同的損失代價。Fan等[16]提出的AdaCost算法是一種基于代價敏感的Boosting方法，該算法給予分錯的少數類樣本與多數類樣本不同的代價因子，實驗證明當以精度和召回率衡量分類結果時，AdaCost的性能優于其他版本的Boosting算法。Sun等[17]根據樣本權重更新方式的不同，提出三種不同的代價敏感Boosting算法。Joshi等[18]提出的RareBoost算法按照每次迭代之后的TP/FP（True Positive/False Positive）與TN/FN（True Negative/False Negative）的比值分別為預測為正類的樣本和預測為負類的樣本進行權值更新。代價敏感學習也可以與傳統的分類算法相結合，進而使傳統分類算法具有代價敏感性[19-24]。

本文提出一種將代價敏感集成學習算法與過采樣技術相結合的非平衡數據分類算法——NIBoost（New Imbalanced Boost）算法。其基本思想是首先采用GMBoost算法中多數類樣本錯誤率與少數類樣本錯誤率的幾何均值作為分類器的評價標準。然后在每次迭代中融入NKSMOTE（New Kernel Synthetic Minority Over-Sampling TEchnique）算法，即通過增加少數類樣本平衡數據集;然后在該數據集上訓練分類器，隨后根據TP/FP與TN/FN的比值分別為預測為正類的樣本和預測為負類的樣本進行權值更新，使得分類器在訓練中更加關注被分錯的樣本。

1 相關基礎知識

本章對相關的基礎知識及對本文所提出的NIBoost算法中迭代過程需要用到的過采樣算法（NKSMOTE）的基本原理進行介紹。

1.1 AdaBoost算法簡介

AdaBoost基本思想是首先為數據集中的每個樣本賦予一個初始權值，然后在該數據集上訓練基分類器，最后根據基分類器的分類結果對樣本權值進行更新，使得錯分樣本在后續訓練時可以得到更多的關注。最后組合分類器的判決結果是所有弱分類器判決結果的加權和。AdaBoost算法流程如下。

1.2 代價敏感集成算法

非平衡數據集的分類問題中，少數類往往是分類的重點，即正確識別出少數類比識別出多數類樣本具有更大的價值。代價敏感學習就是基于該思想設計，給錯分的少數類樣本賦予較高的錯分代價。

1.3 SMOTE算法簡介

SMOTE基本思想是通過人工合成新的少數類樣本來改變樣本分布。其基本原理是在相距較近的少數類樣本之間進行線性插值，從而生成新的少數類樣本。下面對SMOTE關鍵步驟進行簡單的介紹。

1.4 核距離

將樣本通過非線性映射函數映射到核空間，在核空間中度量的樣本之間的距離稱為核距離。NKSMOTE算法中涉及核距離的計算，對于核空間中任意兩個樣本點φ（x）和φ（y），其核距離計算如下：

目前常用的核函數有高斯核函數、多項式核函數、S型核函數等。

1.5 NKSMOTE算法簡介

1）對任意少數類樣本x在核空間上尋找距其最近的K個樣本。根據其K個樣本近鄰中少數類樣本的個數與多數類樣本的個數的比例，將少數類樣本x分為安全樣本，危險樣本，噪聲樣本。若少數類樣本的個數多于多數類樣本的個數，則少數類樣本x為安全樣本;若少數類樣本的個數少于多數類樣本的個數，且存在少數類樣本，則少數類樣本x為危險樣本;若全是多數類樣本則該少數類樣本x為噪聲樣本。

2）若少數類x不是噪聲樣本，則從其K近鄰中隨機選擇兩個樣本，在三個樣本之間按照一定的合成規則合成N個新樣本，其中N值是向上采樣倍率。若選中的兩個樣本y1，y2均是多數類樣本，則利用式（12）和（13）得到新的少數類樣本。

3）若少數類樣本x是噪聲樣本，對其進行過采樣時有給數據集引入噪聲的風險，但是噪聲樣本又有其積極作用，為了使風險降到最低，設定其向上采樣倍率N為1。在其余少數類樣本中隨機選擇一個少數類樣本y，在x與y之間進行隨機線性插值，其中增量因子是一個在（0.5，1）區間上服從均勻分布的隨機數，使新的少數類樣本更靠近樣本y。

2 NIBoost算法基本原理

本文所提出的NIBoost算法是一種結合了代價敏感和過采樣技術的Boosting算法。它能在每次迭代的過程中逐漸地增加少數類樣本的數目來平衡數據集和調整錯分樣本的權重，使得最終訓練出來的強分類器對非平衡數據集有很高的分類性能。

2.1 NIBoost原理介紹

2.2 NIBoost的時間復雜度分析

由于所提出的算法需要用到NKSMOTE算法來平衡訓練數據集，故NIBoost算法的時間復雜度要高于一般的Boost算法。若各變量符號如之前的算法流程所示，數據集的大小為n，算法的迭代次數為T，則在數據的預處理階段，需要為各個樣本初始化權重，時間復雜度為O（n）;然后調用NKSMOTE算法來生成新的少數類，當計算少數類與其他樣本的距離時，時間復雜度為O（f·ni·（m+n）），再將距離排序，其時間復雜度為O（n log（n）），其中： f是樣本的特征個數，ni表示在第i次迭代過程中少數類樣本的個數，m為之前迭代過程中新增的少數類樣本個數總和。最后更新樣本權重的時間復雜度也為O（n+m）。因為少數類樣本的數量ni遠小于樣本個數n，新增的少數類樣本個數m也不會超過n，算法共要迭代T次，故NIBoost的整體時間復雜度可簡化為O（2·T·f·n2）。

3 實驗設計與結果分析

為了驗證本文所提算法的有效性，在實際的非平衡數據集上用NIBoost算法對其分類。對實驗結果的分析證明，NIBoost算法在處理非平衡數據集時具有一定的優勢。

3.1 數據集

實驗所用數據集來自UCI數據庫，表1列出了這些非平衡數據集的基本信息，包括數據集名稱、樣本數、屬性數、少數類數以及非平衡度（Imbalanced Rate， IR）。

3.2 評價標準

在傳統分類學習方法中，一般采用分類精度作為評價指標，然而對于非平衡數據集而言，用分類精度來評價分類器的性能是不合理的。在機器學習領域中對于非平衡數據分類的常用評價標準有ROC（Receiver Operating Characteristic）曲線、AUC（Area Under Curve）以及基于混淆矩陣的F-value，G-mean。在非平衡數據學習中，少數類對應為正類，多數類對應為負類，表2給出了二分類問題的混淆矩陣。

根據混淆矩陣可以得到以下評價指標。

如果同時關注兩個類的性能，可以使用G-mean評價算法在兩個類上的性能：

3.3 實驗結果及分析

實驗用Java實現SMOTE、RareBoost、PCBoost、NIBoost算法，采用決策樹（J48）、樸素貝葉斯（Naive Bayesian， NB）算法為基分類器算法。實驗采用五折交叉驗證。表3展示了上述4個算法在5個數據集上的F-value值、G-mean值、AUC值的比較結果。

通過對表3的觀察可以發現，當以J48作為基分類算法，用F-value作為評價度量時，在所有數據集上，NIBoost均比PCBoost、RareBoost效果好，比PCBoost最高提高了2.3個百分點，比RareBoost最高提高了5.91個百分點;除了在數據集ecoli3上略遜于SMOTE外，在其他數據集上NIBoost均比SMOTE算法效果好，最高提高了2個百分點。當用G-mean作為評價度量時，在所有數據集上，NIBoost均比RareBoost、SMOTE效果好，比RareBoost最高提高了7.44個百分點;除了在數據集ecoli1上略遜于PCBoost外，在其他數據集上NIBoost也都比PCBoost效果好。當用AUC作為評價度量時，在所有數據集上，NIBoost均比SMOTE、RareBoost效果好，比SMOTE最高提高了1.54個百分點，比RareBoost最高提高了4.38個百分點;除了在數據集ecoli3、yeast3上略遜于PCBoost外，在其他數據集上NIBoost均比PCBoost效果好。

當以NB作為基分類算法，用F-value作為評價度量時，除了在數據集ecoli1上略遜于SMOTE外，在其他數據集上NIBoost均比SMOTE算法效果好，最高提高了3.9個百分點;除了在數據集ecoli1上NIBoost略遜于PCBoost外，在其他數據集上NIBoost均比PCBoost效果好，最高提高了5.22個百分點;在所有數據集上，NIBoost均比RareBoost效果要好，最高提高了9.6個百分點。當用G-mean作為評價度量時，在所有數據集上，NIBoost均比SMOTE、RareBoost效果好，比SMOTE最高提高了2.3個百分點，比RareBoost最高提高了20.3個百分點;除了在數據集ecoli1上NIBoost略遜于PCBoost外，在其他數據集上NIBoost均比PCBoost效果好。當用AUC作為評價度量時，除了在數據集ecoli1、yeast3上略遜于SMOTE外，在其他數據集上NIBoost均比SMOTE算法效果好，最高提高了1.74個百分點;除了在數據集ecoli1上略遜于PCBoost外，在其他數據集上NIBoost均比PCBoost效果好，最高提高了4.1個百分點;在所有數據集上，NIBoost均比RareBoost算法效果好，最高提高了16.14個百分點。

所以總的來說，NIBoost算法在處理非平衡數據時具有一定的優勢。

4 結語

針對非平衡數據集的分類問題，本文從算法層面入手，結合RareBoost算法和GMBoost算法的思想，給出一種將代價敏感思想與過采樣技術相結合的非平衡數據分類算法——NIBoost算法。該算法是在每次迭代中融入過采樣算法（NKSMOTE），即通過增加少數類樣本逐步平衡數據集;然后在該數據集上訓練分類器。隨后根據樣本的原始類標與分類結果分別進行權值調整。實驗結果表明NIBoost算法具有更好的分類性能。進一步的研究工作是將欠采樣和集成學習的思想融合起來以解決非平衡數據分類困難的問題。

參考文獻 （References）

[1] WEISS G M， ZADROZNY B， SAAR M. Guest editorial： special issue on utility-based data mining [J]. Data Mining and Knowledge Discovery， 2008， 17（2）： 129-135.

[2] del CASTILLO M D， SERRANO J I. A multistrategy approach for digital text categorization from imbalanced documents [J]. Association for Computing Machinery Special Interest Group on Knowledge Discovery and Data Mining ExplorationsACM SIGKDD Explorations Newsletter， 2004， 6（1）： 70-79.

[3] WEI W， LI J， CAO L. Effective detection of sophisticated online banking fraud on extremely imbalanced data [J]. World Wide Web， 2013， 16（4）： 449-475.

[4] 江頡，王卓芳，GONG R S，等.不平衡數據分類方法及其在入侵檢測中的應用研究[J].計算機科學，2013，40（4）：131-135.（JIANG J， WANG Z F， GONG R S， et al. Imbalanced data classification method and its application research for intrusion detection [J]. Computer Science， 2013， 40（4）： 131-135.）

[5] KUBAT M， HOLTE RC， MATWIN S. Machine learning for the detection of oil spills in satellite radar images [J]. Machine Learning， 1998， 30（2）： 195-215.

[6] SCHAEFER G， NAKASHIMA T. Strategies for addressing class imbalance in ensemble classification of thermography breast cancer features [C]// Proceedings of the 2015 IEEE Congress on Evolutionary Computation. Piscataway， NJ： IEEE， 2015： 2362-2367.

[7] CHAWLA N V， BOWYER K W， HALL L O. SMOTE： synthetic minority over-sampling technique [J]. Journal of Artificial Intelligence Research， 2002， 16（1）： 321-357.

[8] QIAN Y， LIANG Y， LI M. A resampling ensemble algorithm for classification of imbalance problems [J]. Neurocomputing， 2014， 143： 57-67.

[9] DOUZAS G， BACAO F， LAST F. Improving imbalanced learning through a heuristic oversampling method based on k-means and SMOTE [J]. Information Sciences， 2018， 465： 1-20.

[10] GALAR M， FERNANDEZ A， BARRENECHEA E. Ordering-based pruning for improving the performance of ensembles of classifiers in the framework of imbalanced datasets [J]. Information Sciences， 2016， 354： 178-196.

[11] ZHANG Y， ZHANG D， MI G. Using ensemble methods to deal with imbalanced data in predicting protein-protein interactions [J]. Computational Biology and Chemistry， 2012， 36（2）： 36-41.

[12] KIM M J， KANG D K， KIM H B. Geometric mean based boosting algorithm with over-sampling to resolve data imbalance problem for bankruptcy prediction [J]. Expert Systems with Applications， 2015， 42（3）： 1074-1082.

[13] 李雄飛，李軍，董元方，等. 一種新的不平衡數據學習算法PCBoost [J]. 計算機學報， 2012， 35（2）： 202-209.（LI X F， LI J， DONG Y F， et al. A new learning algorithm for imbalanced data PCBoost[J]. Chinese Journal of Computers， 2012， 35（2）： 202-209.）

[14] HE H， ZHANG W， ZHANG S. A novel ensemble method for credit scoring： adaption of different imbalance ratios [J]. Expert Systems with Applications， 2018， 98： 105-117.

[15] 付忠良.多標簽代價敏感分類集成學習算法[J]. 自動化學報， 2014， 40（6）： 1075-1085.（FU Z L. Cost-sensitive ensemble learning algorithm for multi-label classification problems [J]. Acta Automatica Sinica， 2014， 40（6）： 1075-1085.）

[16] FAN W， STOLFO S J， ZHANG J， et al. AdaCost： misclassification cost-sensitive boosting [C]// ICML 99： Proceedings of the 16th International Conference on Machine Learning. San Francisco， CA： Morgan Kaufmann Publishers， 1999： 97-105.

[17] SUN Y， KAMEL M S， WONG A K C. Cost-sensitive boosting for classification of imbalanced data [J]. Pattern Recognition， 2007， 40（12）： 3358-3378.