不平衡數據分類中的數據重采樣比較研究*

衷宇清，陳文文，李昭樺

（1.廣州供電局通信中心，廣東 廣州 510000；2.中國能源建設集團廣東省電力設計研究院，廣東 廣州 510000）

0 引言

在大數據和人工智能時代，數據挖掘和機器學習已成為必不可少的關鍵技術，從各行各業的海量大數據中學習、挖掘有價值的信息用于決策支撐。數據分類與預測是一種常見的應用形式，如網絡安全領域的異常檢測[1,2]、金融領域的信用卡欺詐識別[3]、智能制造領域的產品瑕疵分析以及醫療領域的病理檢測[4]等。在許多實際應用中會出現某一類別樣本數量遠少于其他類別的情況，如網絡中的異常流量占總體流量的極少數、信用卡欺詐在信用卡交易中屬于罕見行為以及某些特定的病變在正常人群中比例極低等，這種數據現象稱為類別分布不平衡（Class Imbalance）。

不平衡數據分類問題是機器學習領域的一個重要挑戰。許多傳統的分類算法如決策樹[5]、支持向量機（Support Vector Machine，SVM）[6]、k 近鄰（k-Nearest Neighbor，k-NN）[7]等，在類別均衡的數據中能取得較好的分類結果，但在不平衡數據中的分類結果會偏向主導數據集的多數類。而往往在這些應用中，少數類才是重點關注的關鍵對象，如上述提及的網絡異常、信用卡欺詐以及病理檢測等，對少數類的漏識別和誤識別代價極大。因此，不平衡數據分類問題多年來一直是機器學習領域的研究熱點之一[3,8-9]。

解決不平衡數據分類問題的方法大致可以分為兩類。第一類是從算法角度出發，通過調整代價給予少數類更高權重，從而避免分類模型偏向多數類，這類方法稱為代價敏感學習[3]。它主要挑戰是如何在各種實際應用中為少數類確定合適的代價值，因此不具備普遍適用性。第二類從數據角度出發，通過對類別分布不平衡的數據集進行重采樣，使其類別均衡。重采樣可分為過采樣和欠采樣，分別通過增加少數類樣本和減少多數類樣本來降低數據集的不平衡比例。數據重采樣會改變原始數據的分布，但是由于其具有普遍適用性，得到了較多的應用，如學術界提出了SMOTE[10]、Borderline-SMOTE[11]、基于聚類的重采樣算法[12-13]以及集成重采樣算法[14]等一系列的算法。不同算法生成的數據集特性各不相同，對不同類型的分類器的影響也不同。哪一類型重采樣算法更適合于哪一類型分類器，現有文獻中缺乏系統性的理論框架或實驗分析。

針對該問題，本文深入探索不平衡數據分類任務中的數據重采樣算法和分類器模型的匹配適用性。具體地，采用不同類型的9 種數據重采樣算法，對來自不同領域的14 個真實數據集進行訓練集類別均衡化，比較C4.5 決策樹、支持向量機和最近鄰3 種經典分類器在其上取得的分類結果。

1 不平衡數據分類問題

1.1 不平衡數據集

考慮一個二元分類數據集，其中一個類別樣本較為稀缺，稱之為少數類（Minority Class）。因為它往往是期望識別的類別，所以又稱為正類（Positive Class）。數據集中的大多數樣本屬于另外的類別，稱之為多數類（Minority Class）和負類（Negative Class）。例如，在網絡異常檢測應用中，大多數樣本屬于正常流量，異常流量樣本稀缺屬于少數類，是待檢測類別。類別分布的不平衡比例定義為：

在不同領域的數據集中，不平衡比例差別極大。例如，在社交網絡中垃圾消息和正常消息不平衡比例約為1:20[2]，在其他實際應用中可達到1:1 000 甚至更大[8]。

1.2 不平衡數據分類結果評價

對于不平衡數據集，傳統機器學習常用的總體準確率（Overall Accuracy）和錯誤率（Error Rate）等評價指標并不適用。例如，對于不平衡比例為1:1 000 的數據集，分類器將所有樣本判別為多數類即可取得高于99.9%的總體準確率，但該分類結果在實際應用中沒有價值。因此，不平衡數據分類一般采用針對少數類的評價指標。

二元分類混淆矩陣（Confusion Matrix）如表1 所示，真正例（True Positive）表示正類樣本被正確識別為正類，假正例（False Positive）表示負類樣本被錯誤識別為正類。對應的，假負例（False Negative）表示負類樣本被錯誤識別為正類，真負例（True Negative）表示負類樣本被正確識別為負類。

表1 混淆矩陣

在混淆矩陣的基礎上，可以計算少數類的精確率（Precision）、召回率（Recall）和F值（F Measure）等指標。

精確率又稱查準率，表示被分類模型識別為正類的樣本中真正例所占的比例，計算方法為：

召回率又稱查全率，表示測試集中所有正類樣本中被正確識別正類的樣本的比例，計算方法為：

F值是精確率和召回率的加權調和平均，本文采用最常用的F1值，計算方法為：

1.3 機器學習算法

C4.5 算法[5]是一種流行的決策樹分類算法，基于信息量增益率（Gain Ratio）最大化的分割原則，采用分治法分割訓練集從而構建決策樹。在構建過程中，C4.5 算法采用剪枝方法處理由訓練數據中的噪聲和離群點等異常導致的分枝，從而避免過擬合問題。C4.5 決策樹分類模型的節點對應訓練集中的樣本子集，其中內部節點代表對一個屬性取值的測試，分支代表測試的兩種不同結果，而葉節點代表一個類別。給定一個待測試樣本，從根節點出發對樣本的屬性值進行一系列測試，直至到達某個葉節點。因為在生成樹過程中的分割原則會考慮到所有類別，所以一般認為決策樹算法對不平衡數據集的適應能力較強，但是不平衡比例較高的數據集仍然會對算法的分類效果產生影響。

支持向量機[6]是一種線性分類模型，將訓練樣本視為n維特征空間中的點，算法尋找一個以最大間隔分開兩類樣本的n-1 維超平面，即其到兩邊最近樣本點的距離最大化。該超平面稱為最大間隔超平面，兩類中最靠近該超平面的樣本點稱為支持向量。對于線性不可分數據，可通過核函數進行非線性特征變換，將數據映射到更高維的特征空間，然后在該空間中尋找最大間隔超平面實現數據分類。在不平衡數據集中訓練SVM 分類器，經典算法尋找的最優超平面會傾向于少數類，使得分類結果偏向多數類。

k近鄰（k-NN）算法[7]是非參數機器學習算法的另一個代表。k-NN 算法沒有復雜的訓練過程，只需保存訓練樣本的特征向量和類別標簽。給定一個待測試樣本，從訓練集中找出距離其最近的k個樣本，將在它們之間占最多數的類別標簽賦予測試樣本。本文使用歐氏距離計算樣本間距離，并在實驗中將k值設為1，即采用最近鄰分類器。k-NN 分類器的泛化誤差不超過貝葉斯分類器的兩倍，具有良好的特性。但是，在不平衡數據集中，該算法將受到極大影響，即出現頻率較多的多數類樣本有較大可能出現在測試樣本的k鄰域，從而主導測試樣本的預測結果。

2 數據重采樣算法

2.1 數據過采樣算法

數據過采樣算法通過增加少數類的樣本來調整數據集類別分布。增加的基本方法包括重復采樣少數類樣本或增加人工合成樣本。

隨機過采樣（Random Oversampling）算法通過隨機從少數類現有樣本中重復抽取數據，增加樣本數量，降低類別不平衡比例。它簡單復制樣本的策略，容易導致模型過擬合問題。

SMOTE（Synthetic Minority Oversampling Technique）[10]是經典的基于人工合成樣本的過采樣算法。算法思路：對每個少數類樣本使用k-NN算法在數據集中搜索距其最近的另外k個樣本（可能屬于少數類或多數類），從中隨機選擇一個樣本進行隨機線性插值構造一個新的少數類樣本，根據采樣倍率重復n次，即可生成一個原有樣本數量n倍的少數類樣本集。該算法的缺陷是可能使得類別邊界變得模糊。于是，研究人員提出了很多改進方法[15-16]，其中Borderline-SMOTE[11]算法的思路是先搜索出特征空間的類別邊界，然后在邊界區域生成少數類樣本。具體地，對于每個少數類樣本，先考察距離其最近的m 個樣本，若其中有半數以上屬于多數類，則認為該樣本是少數類邊界樣本。最后，該算法使用SMOTE 算法從少數類邊界樣本中構造合成樣本。

為兼顧類別間不平衡性和類別內不平衡性，基于聚類的過采樣算法（Cluster-based oversampling）[12]先對原始數據集中的多數類和少數類分別進行聚類，然后在每個類別的聚類簇中進行過采樣實現類別均衡化。集成（Ensemble）過采樣[14]算法基于集成學習的思路，對數據集進行多次采樣并訓練分類器，最后通過多數表決得到最終分類結果。本文集成過采樣算法實現采用隨機過采樣、基于聚類的過采樣和基于信息分解的過采樣[2]作為基本算法。

2.2 數據欠采樣算法

隨機欠采樣（Random Undersampling）算法通過隨機從多數類樣本中抽取一個子集作為代表，降低類別不平衡比例，代價是可能丟失多數類的重要信息。基于聚類的欠采樣算法（Cluster-based Undersampling）[13]對原始數據集中的多數類進行聚類，將得到的每個聚類簇都和少數類樣本結合成為一個新的訓練集并訓練分類器，然后從中選擇最優分類器。

基于Wilson 編輯法的欠采樣算法[17]使用k-NN分類器對訓練集進行分類，然后去除分類錯誤的多數類樣本。單邊選擇法（One-sided selection）[18]使用多數類的隨機子集與少數類合成初始訓練集，然后用最近鄰分類器分類原始數據集，將分類錯誤的多數類樣本加入訓練集，從而去除多數類冗余樣本，再用Tomek links 方法（即數據集中距離最近的兩個樣本分別屬于少數類和多數類）去除多數類中的類別邊界及噪聲樣本。

圖1 各數據集的精確率結果

3 實驗設計與結果分析

3.1 數據集

表2 列出了本文使用的數據集，其中包含了屬于生物醫療、軟件工程以及網站統計等不同專業領域的14 個公開數據集，均可在PROMISE 軟件工程庫[19]、UCI 機器學習庫[20]等公開數據庫中獲取。表2 中數據集按不平衡比例排序，可見在現實世界的真實數據集中類別分布不平衡現象普遍存在。其中，只有diabetic 和pima 兩個數據集相對平衡，有8 個數據集的不平衡比率在1:2～1:10，而onehr、pc5、mc1 和pc2 這4 個數據集的不平衡比例則高于1:30。此外，各數據集的大小也相差懸殊，樣本數量在253～17 186 不等。

表2 實驗數據集信息

3.2 實驗設計

對于每個數據集，隨機選擇原始數據的60%構成訓練樣本集，并將另外40%用作測試樣本集。本文探討的數據重采樣方法僅應用于訓練樣本集，用以訓練不同的分類模型。測試數據集未作其他處理，保持了與原始數據集相近的不平衡度，因此分類結果可以反映真實情況。

對于數據重采樣的采樣率參數，欠采樣方法使用多數類的20%、50%、70%和90%等參數，過采樣方法使用少數類的200%、500%、700%和900%等參數。此外，對于兩類采樣方法比較了均衡采樣率，即進行欠采樣或過采樣直至兩類數據樣本數量一致，后文分析中取各算法最優參數的結果。最后，原始的不平衡數據集也用于訓練分類模型，提供對比基線。

如圖2 所示，實驗中的C4.5、SVM 和k-NN 等分類算法采用了WEKA[21]提供的實現版本，且均使用了默認參數，未做特殊優化。

3.3 結果與分析

圖1 和圖2 給出了3 種分類器在各數據集中取得的精確率和召回率結果，其中各灰度條代表不同數據重采樣方法處理過的訓練集。由直接從原始不平衡數據學習（imbalanced）結果可見，數據集不平衡度越高，3 種分類器的精確率和召回率受影響越大，整體呈現下降趨勢。此外，數據集大小對分類結果也有一定影響，如bmg、qvc 和pc5 數據集雖然不平衡比例較前列數據集更高，但是由于數據量較大、少數類樣本數較充足，仍能取得更好的結果。總體而言，類別分布不平衡和少數類樣本稀缺對分類結果造成了極大影響。

圖2 各數據集的召回率結果

從結果中還可看到，不同數據重采樣方法對3種分類器的影響各不相同。對于C4.5 分類器，隨機過采樣（Random Cversampling，ROS）、隨機欠采樣（Random Undersampling，RUS）、SMOTE（Synthetic Minority Cversampling Technique，SM）和集成過采樣（Ensemble Oversampling，ENOS），在大部分數據集中均可以有效提高精確率和召回率。對于SVM 分類器，基于聚類的過采樣（Cluster-based Oversampling，CBOS）、欠采樣（Cluster-based Undersampling，CBUS）、ROS 和ENOS，對精確率提高較為明顯，但是對召回率并沒有明顯改善，在一些數據集中反而有負面影響。對于k-NN 分類器，ROS、RUS 和ENOS 對精確率和召回率均有顯著提升。例如，在不平衡比例較高的pc3、pc4、mw1、pc1、onehr、mc1 以及pc2 等數據集中，直接使用不平衡數據作為訓練集的精確率均在30%以下，而經過上述幾個算法重采樣后，精確率可提升至60%～80%。

圖3 給出了3 種分類器在各數據集的F 值結果，反映了精確率和召回率的加權調和平均。對于C4.5分類器，ROS、RUS、SMOTE 和ENOS 在所有數據集中均能夠有效提高不平衡數據分類的F值。對于SVM 分類器，在diabetic、pima、ilpd 等不平衡比例不高的數據集中，數據重采樣對分類結果影響不大，在其他數據集中ROS 和ENOS 對分類結果的提升較為明顯。對于k-NN 分類器，除了etoys 數據集以外，ROS、RUS 和ENOS 均能夠大幅提高分類F值結果。

圖4～圖6 使用箱線圖更直觀地展示了各個數據重采樣算法對3 種分類器精確率、召回率和F值的提升效果，即基于重采樣數據訓練得到的分類器精確率與原始不平衡數據中訓練得到的指標差值在14 個數據集中錄得的統計值。

從圖4 可見，對于C4.5 分類器，ROS、RUS、SM 和ENOS 算法在各數據集中均顯著提高了精確率，平均提升幅度在20%～38%；相比之下，CBOS 和CBUS 沒有明顯改善，而Borderline-SMOTE（BSM）、One-side Selection（OSS） 和Wilsons Editing（WE）等算法降低了其精確率。對于SVM分類器，CBUS、ROS 和ENOS 在幾乎所有數據集中都提高了精確率，平均幅度在13%～24%。CBOS 在大部分數據集中能夠提高精確率，但是在少數幾個數據集中得到了反效果，總體平均提升幅度為5%。OSS、RUS、SM 和WE 對SVM 精確率幾乎沒有影響，而BSM 會降低其精確率。對于k-NN分類器，ROS、RUS 和ENOS 在各數據集中平均提高精確率約34%，而BSM、CBOS、CBUS、OSS、SM 和WE 算法對精確率沒有明顯的提升。

圖3 各數據集的F 值結果

圖4 各分類器精度提升結果

圖5 結果顯示，對C4.5 分類器，除了CBOS 以外，其他重采樣算法均能不同程度提高召回率，平均幅度在2%～29%不等。SVM 分類器的情況有所不同，結果顯示只有RUS 能夠小幅提高SVM 的召回率，平均約為5%，其他重采樣算法均為不同程度的降低或持平。對于k-NN 分類器，各個重采樣算法幾乎在所有數據集中都提高了召回率，平均幅度在1%～37%不等。

圖5 各分類器召回率提升結果

圖6 給出的F值結果結合了前文討論的精確率和召回率情況，可見ROS、RUS、SM 和ENOS 適用于C4.5 分類器，CBOS、CBUS、ROS 和ENOS 適用于SVM分類器、而ROS、RUS和ENOS適用于k-NN分類器。此外，值得注意的是，數據重采樣對SVM分類器的影響是在降低了召回率的基礎上提高了一定的精確率，在召回率作為關鍵指標的應用中應當避免使用。

圖6 各分類器F 值提升結果

從上述結果中可以得出結論：不同數據重采樣方法產生的訓練集數據分布特性各不相同，對不同類型的分類算法和模型會產生不同的效果，實際應用中應該根據數據特性和分類算法綜合考慮選擇。

4 結語

數據重采樣方法是解決在現實世界中普遍存在的不平衡數據分類問題的常用方法。本文系統地比較了過采樣、欠采樣等不同類型的9 種數據重采樣方法，在來自不同領域的不平衡數據集中研究對C4.5 決策樹、SVM、k-NN 這3 種經典分類器分類效果的影響。實驗結果表明，不同重采樣算法生成的數據集對不同的分類器產生不同的效用。最后，從精確率、召回率和F值等評價指標的角度，給出了適用于3 種分類器的重采樣算法。