基于欠采樣和代價敏感的不平衡數據分類算法

王俊紅，閆家榮

（1.山西大學計算機與信息技術學院，太原 030006；2.計算智能與中文信息處理教育部重點實驗室（山西大學），太原 030006）

0 引言

分類是數據挖掘領域中一個重要的分支，普通的分類模型通常假設數據集中各類別的樣本數量差距很小且對于每個類別的誤分代價相等，而使用不平衡數據集訓練傳統的分類器會導致模型對于少數類的預測精度很低，因此不平衡數據學習一直是機器學習領域的研究熱點［1］。數據的類別不平衡主要指數據集中某類樣本數量與其他類別樣本數量有很大差距，而擁有較多樣本數據量的類被稱為多數類，擁有較少樣本數據量的類則被稱為少數類。在互聯網應用方面存在著大量不平衡數據分類問題，如醫療檢測［2］、欺詐識別［3］、入侵檢測［4］、工業故障檢測［5］等。

對于目前不平衡數據分類問題，通常的解決方法主要分為數據預處理層面和分類算法層面［6］。數據預處理層面的方法主要思想是通過重采樣技術使數據集中各個類別樣本數量達到相對的平衡，主要有對多數類的欠采樣［7-8］，對少數類的過采樣［9-10］，以及結合兩種采樣方法的混合采樣［11］。而在算法層面，相關研究人員通過改進算法以增加分類器對少數類的重視程度，比較有代表性的算法是代價敏感［12］、單類學習［13-14］和集成學習［15］等。本文重點關注基于集成學習的不平衡數據分類算法的研究進展。

集成學習主要思想是將學習得到的多個子分類模型通過一定方式組合，從而得到一個泛化能力更好的強分類器。其中Bagging和Boosting是機器學習中應用最廣泛的集成學習技術，Boosting 雖然不是為處理不平衡數據設計的，但卻可以有效提高分類器對于不平衡數據的分類性能。Freund等［16］提出的自適應增強（Adaptive Boosting，AdaBoost）算法是最常用的Boosting 算法。目前基于集成學習方法的不平衡數據分類算法中主要分為將數據重采樣技術與集成算法結合和將代價敏感思想與集成算法相結合。將數據預處理與集成方法結合主要是在訓練基分類器之前對數據樣本使用重采樣技術。Chawla等［17］提出了一種將過采樣技術與集成學習結合的算法SOMTEBoost（Synthetic Minority Over-sampling TEchnique Boosting），該算法基于AdaBoost.M2［18］算法，通過每次迭代中使用合成少數類過采樣技術（Synthetic Minority Over-sampling TEchnique，SMOTE）對少數類過采樣，從而獲得較為平衡的數據。算法通過將SMOTE 算法和AdaBoost算法的結合，有效改善了分類器的性能，其結果優于單獨使用SMOTE 和AdaBoost算法。但SMOTEBoost 算法在訓練過程中由于過采樣生成了更多的數據，當樣本容量很大時，時間復雜度會增加。因此Seiffert 等［19］在2010 年提出了RUSBoost（Random Under-Sampling Boosting）算法，它與SOMTEBoost 算法相似，該算法在迭代中使用了隨機欠采樣技術，使用更少的數據集訓練弱分類器，在提升不平衡數據集分類性能的同時降低了訓練的時間復雜度，在處理樣本容量較大的分類問題中更具優勢。Rayhan 等［20］提出了CUSBoost（Cluster-based Under-Sampling with Boosting）算法，該算法首先使用K均值聚類（K-Means Clustering，KMC）算法對多數類進行聚類，然后在每次迭代中對每個聚類子簇中的數據隨機下采樣，得到平衡的數據集。該算法雖然在下采樣之后可以獲得更具代表性的多數類樣本，但對多數類進行聚類時，會消耗大量的時間。Feng 等［21］通過將間隔理論與集成技術結合，提出了基于間隔理論的不平衡數據分類算法，算法在采樣時使用信息量更大的低間隔樣本，從而獲得更高的預測精度。陳圣靈等［22］通過將SMOTE算法和集成學習思想相結合，提出了一種基于更新樣本權重的不平衡數據學習算法，算法通過重采樣從而間接地更新樣本權重，有效提高算法模型少數類識別能力。將代價敏感與集成方法結合最具代表性的方法是Fan 等［23］提出的代價敏感集成（Cost-sensitive AdaBoosting，AdaCost）算法，算法主要通過修改樣本錯分代價，使得AdaBoost 采用不同的策略更新不同錯分代價的樣本權重。

基于此，本文從數據預處理層面出發，并將代價敏感思想引入AdaBoost 算法的權重更新公式，提出一種基于欠采樣和代價敏感的不平衡數據分類算法——USCBoost（UnderSamples and Cost-sensitive Boosting），算法旨在對多數類樣本進行欠采樣，并將代價矩陣引入到權重更新公式中，使得錯分少數類的樣本權重增加更快。使用UCI庫中的數據集對本文算法進行實驗分析，結果表明USCBoost 算法與其他對比算法相比，在F1-measure值和G-mean值上有了顯著提高，該算法處理不平衡數據分類具有一定可行性。

1 相關工作

1.1 AdaBoost算法

AdaBoost作為Boosting技術的代表算法，近年來被相關學者廣泛研究和使用。該算法主要通過更新樣本權值，使基分類器在每次迭代中更加注重分錯的樣本，對這一部分樣本進行著重訓練，最后將每次迭代訓練的基分類器加權組合。假如數據集樣本數量為N，算法在第一輪迭代時賦予所有訓練樣本相同的權重1/N；然后學習基分類器。對于訓練集中的樣本數據，假如樣本被此次學習的基分類器分類錯誤，這個樣本權值將會增加；反之，被基分類器分類正確的樣本權值會被降低。因此在下次迭代訓練的基分類器會更加著重學習上次被分錯的數據。最后將每次迭代訓練的基分類器根據權值線性相加。

AdaBoost算法執行步驟如下。

算法1 AdaBoost算法。

輸入：訓練數據集S={(x1，y1)，(x2，y2)，…，(xi，yi)|i=1，2，…，N，yi∈{1，-1}}，T為迭代次數，g為基分類器；

1.2 決策樹生成算法

決策樹（Decision Tree）有著可解釋性強、運行速度快等優點，集成學習中經常使用具有較小深度的決策樹作為基本分類器。本文中構建的集成模型使用CART（Classification And Regression Tree）算法生成基本分類器。

CART 是一種常見的決策樹生成算法，該算法采用Gini系數作為評價最優劃分特征的指標。假如樣本集合Gini值越小，數據集中樣本屬于同一類別的概率越高。

對于樣本集合D，Gini系數計算公式如下：

其中：K為樣本集合D中類別數量，Ck為第k類的樣本數量。

特征A上樣本集合D的基尼系數計算公式如下：

其中：D1和D2為使用特征值A上的某一特征值將數據集劃分后形成的兩個子集。

2 基于欠采樣和代價敏感的不平衡數據分類算法

從AdaBoost 算法的相關研究可知，由于多數類在不平衡數據集中占有著很大的比例，使得傳統AdaBoost 算法在迭代過程中更加著重訓練占比更大的多數類數據，而忽略了不平衡數據集中的少數類數據，導致最終算法模型的分類決策面會偏向少數類。而在集成算法每次迭代中，被分類正確的多數類樣本權值會降低，對于下次弱分類器的性能影響變小，因此可以對于這部分權值低的多數類樣本欠采樣；但是由于欠采樣之后的多數類樣本中仍然存在大量權重高的多數類樣本，為了使少數類樣本在訓練中進一步得到重視，將代價敏感的思想引入樣本權重更新公式，賦予少數類更高的樣本權重，使得分錯的少數類樣本權重增加更快。

本文算法在每次迭代訓練弱分類器之前根據采樣率選取權重較大的多數類樣本并和所有少數類樣本組成臨時訓練集；在樣本權重調整階段，本文采用了AdaCost 算法中樣本權重更新的策略，將代價調整函數β引入到權重更新公式中。β函數的計算公式如下：

其中：β+為模型預測正確時的β函數，β-為模型預測錯誤時的β函數，c為樣本的錯分代價。

綜上所述，本文首先通過欠采樣刪除了大量對分類器貢獻不大的多數類樣本，降低了訓練基分類器的時間復雜度，繼而在樣本更新時通過引入代價調整函數使得誤分代價高的樣本在每次迭代中權重增加更快，使得下次迭代時基分類器更加注重錯分的少數類樣本。

本文集成算法步驟如下。

算法2 USCBoost算法。

輸入：訓練數據集：S={(x1，y1)，(x2，y2)，…，(xi，yi)|i=1，2，…，N，yi∈{1，-1}}，T為迭代次數，g為基分類器；

3 實驗結果與分析

3.1 評價標準

在數據不平衡的分類任務中，通常使用準確率、召回率、F1-measure值等當作模型的性能度量指標。二分類問題混淆矩陣如表1 所示。其中：TP（True Positive）為正例樣本分類正確時的情況；FP（False Positive）為反例樣本被分類錯誤的情況；FN（False Negative）為正例樣本被分類錯誤的情況；TN（True Negative）為反例樣本分類正確的情況。

表1 混淆矩陣Tab.1 Confusion matrix

1）準確率（Accuracy）表示分對的樣本數除以所有的樣本數，計算公式如式（4）：

2）查準率（Precision）表示被分為正例的示例中實際為正例的比例，計算公式如式（5）：

3）召回率（Recall）為分類正確的正例樣本與所有正例樣本的比值，用來度量算法識別正例樣本的能力。計算公式如式（6）：

4）特異度為分類正確的反例樣本與所有反例樣本的比值，用來度量算法識別反例樣本的能力。計算公式如式（7）：

5）F1-measure表示Precision和Recall加權調和平均值，計算公式如式（8）：

6）G-mean值表示召回率和特異度的幾何平均值，如式（9）：

本實驗中采用準確率、F1-measure值、G-mean值作為衡量算法性能的評價指標。

3.2 數據集描述

為了衡量本文提出的USCBoost 算法的性能，使用UCI 中標準數據庫10 組數據集訓練分類器并對實驗結果進行分析。實驗數據集的不平衡度（Imbalance Ratio，IR）從1.8 到24。其中有的數據中為多分類數據集，本實驗將這些數據集中的某些類別合并成二分類數據集。例如在Ecoli數據集中，樣本分為8 類，Ecoli_5 表示將數據集中類別為5 的樣本作為少數類，并將剩余其他類別的樣本合成多數類。實驗數據集信息如表2。

表2 實驗數據集描述Tab.2 Experimental datasets description

3.3 實驗設計與結果分析

本實驗中所有算法采用五折交叉驗證方法，實驗中對比算法為AdaBoost 算法、AdaCost 算法和RUSBoost 算法。其中RUSBoost 算法采用C4.5 生成基分類器，其余集成算法采用CART 生成基分類器，所有決策樹的深度為5，算法的基分類器數都為10。

實驗分析了4 種算法的準確率、F1-measure值、G-mean值。表3 列舉了本文算法和其他3 種對比算法在各數據集下的評價指標值，其中加粗的數值為最高的評價指標值。

從實驗對比結果可以看出，相比傳統的AdaBoost算法，本文提出的算法在大部分數據集上準確率提高并不明顯，而且在有的數據集上會降低。說明算法在提高少數類分類準確率的同時可能會降低多數類的準確率。

F1-measure值和G-mean值更能夠衡量不平衡數據分類算法的性能。由表3 可以看出USCBoost 算法與其他算法相比，在大部分數據集上都具有明顯的優勢，在vowel_3 和anneal_1_2數據集上本文算法的F1-measure值略小于AdaBoost算法，這是因為樣本的減少可能會導致精度的損失；但在Letter_2數據集中，本文算法的F1-measure值與AdaBoost 算法差距較大，這是由于在高度不平衡的數據中，少數類樣本只占到總樣本數的很少一部分，當對多數類樣本欠采樣到少數類樣本的數量時，可能會刪除掉很多潛在的有價值的多數類樣本，此時可以通過適當地提高多數類的采樣率或對少數類進行過采樣操作，保留有價值的樣本。

表3 不同分類算法在不平衡數據集上的分類準確率、F1-measure值、G-mean值對比Tab.3 Classification accuracy，F1-measure and G-mean comparison of different classification algorithms on unbalanced datasets

但本文算法在和使用隨機欠采樣的RUSBoost 算法比較，在letter_2 數據集上F1-measure值有顯著的提高，這是因為本文算法在每次迭代中欠采樣后得到的是權重高的樣本，而這些樣本對于基分類器的影響更大。

為了更直觀地對比4 種算法，圖1、2 展示了對比算法和USCBoost 算法在10個數據集上的實驗結果，可以看出本文算法處理不平衡數據具有一定優勢。

圖1 4種算法的F1-measure值對比Fig.1 F1-measure comparison of four algorithms

圖2 4種算法的G-mean值對比Fig.2 G-mean comparison of four algorithms

4 結語

本文通過對不平衡數據分類在傳統AdaBoost算法中存在的問題進行研究：在集成算法的每次迭代學習中根據樣本權重對多數類欠采樣，挑選出貢獻大的樣本訓練基分類器；在權重調整階段，通過調整樣本誤分代價，使得誤分代價高的樣本權重將會增加更快，從而使少數類樣本在下次訓練中被重視。算法在保證模型不平衡分類性能的同時，降低了訓練分類模型的時間復雜度。然而，本文算法繼承了AdaBoost 對噪聲敏感的缺點，如何在訓練過程中保證預測精度的同時降低噪聲數據對模型的影響，將是未來重點研究方向。