一種基于樣本學習復雜度的不平衡數據過采樣方法?

許 皓 孫廷凱

（南京理工大學計算機科學與工程學院 南京 210094）

1 引言

不平衡數據是指某個類別的樣本數遠大于其它類別，通常稱樣本少的類別為少數類（正類），樣本數多的類為多數類（負類）［1］。不平衡數據廣泛存在于我們的日常生活中，例如，醫學診斷［15］，文本分類［16］等。如何識別我們感興趣的少數類是一個具有挑戰性的問題。在設計分類器時，我們必須要考慮到數據的不平衡問題，否則，以最大化分類準確率為目標的機器學習算法會傾向于將測試樣本預測為多數類，而忽視少數類的識別率［1］。例如，在臨床醫學診斷時，普通的機器學習算法傾向于將所有人（包括多數類即健康人和少數類即待確診的患者）都歸類為健康人，這固然得到很高的總體識別率，但對于識別患者卻毫無意義。

重采樣技術是一種有效用于不平衡數據的方法，它通過增加少數類樣本（即過采樣）或減少多數類樣本（即欠采樣），來緩解訓練集中類之間的不平衡。欠采樣可能會刪除某些對分類重要的樣本，從而丟失一些有用的信息。而過采樣會導致過擬合問題，并可能帶來噪聲樣本。文獻［6～8］通過實驗，驗證了重采樣可以提高不平衡數據的分類性能。比如，He 等提出了ADASYN 算法［5］，這是一種基于樣本學習復雜度的合成過采樣方法。根據該方法的思想，每個少數類樣本稱為主樣本；而將K 近鄰中的多數類樣本數稱為主樣本的學習復雜度。ADASYN算法根據學習復雜度的大小，為少數類主樣本賦予選擇權重，使分類器關注那些學習困難的樣本，提升了分類性能。但該方法也存在離散值的復雜度問題，不能充分地表現主樣本在學習復雜度方面的差異。

在本文中，我們設計了一種新的基于樣本學習復雜度的過采樣方法LDSMOTE，用于不平衡數據的分類。與ADASYN 方法不同的是LDSMOTE 方法的樣本復雜度計算綜合利用了主樣本在少數類空間和多數類空間的局部分布，它是一個連續的值，更能表現少數類主樣本的學習復雜度。

2 相關工作

針對不平衡數據的分類問題，研究人員提出了許多有效的方法，主要分為數據層的方法和算法層的方法［1］。前者通過調整數據的分布，來緩解訓練集中類的不平衡程度。后者通過設計新的分類器，強調學習過程中的少數類，來提高少數類的識別率。算法層的方法包括代價敏感學習、單類分類、集成學習以及基于核的分類等［1］。在本文中，我們主要研究數據層的方法。

數據層的方法一般使用重采樣方法調整數據分布以緩解不平衡問題。隨機過采樣ROS 隨機復制若干個少數類樣本，強調了原始樣本，易產生過擬合問題。隨機欠采樣RUS 隨機刪除若干個多數類樣本，可能丟棄某些對分類有用的樣本，降低分類的性能。由Chawla 等提出的SMOTE 算法［3］是一種合成少數類過采樣方法，它隨機選擇一個少數類樣本作為一個主樣本，從它的K近鄰少數類樣本中隨機選擇一個，將兩者的凸組合作為合成樣本。它不是簡單地復制少數類，減輕了過擬合的影響。但是，該方法對噪聲樣本敏感，當主樣本是一個噪聲樣本時，新合成的樣本有可能也是一個噪聲樣本?；谶@個事實，Han 等提出了一種利用邊界位置信息的SMOTE 改進算法，稱為Borderline-SMOTE［4］，它將少數類樣本分為三類：安全樣本、邊界樣本和噪聲樣本，并在邊界樣本上使用SMOTE 算法合成新樣本。Borderline-SMOTE 算法合成的樣本位于決策邊界附近，對決策邊界的產生具有顯著的意義，并且減輕了SMOTE 算法中傳播噪聲的影響。對于少數類存在多個子類的情況，DBSMOTE 方法［9］利用聚類算法DBSCAN 對少數類進行聚類，得到多個子類，接著在每個子類上使用SMOTE 算法合成新樣本。文獻［10］使用基于密度的OPTICS聚類算法計算每個少數類的核心距離和可達距離，將核心距離與核心距離內的多數類樣本數的加權和作為主樣本的選擇權重，使用SMOTE 自適應地合成樣本。

除了單一數據層面的重采樣技術，大量方法結合使用了采樣和集成學習，如文獻［11］中的SMOTEBoost，在AdaBoost 的每一次迭代中，通過SMOTE 合成少數類樣本來改變每個樣本的分布，使得分類器更加關注少數類，從而提高它的識別率。文獻［12］中作者將隨機欠采樣與集成方法相結 合，提出了EasyEnsemble 和BalanceCascade 方法，解決欠采樣丟失數據信息的問題。前者獨立地使用T 次欠采樣得到T 個平衡訓練集，學習得到T個AdaBoost分類器，而對一個待測試樣本進行類別預測時，將這T 個AdaBoost分類器的預測值進行集成，得到它的類別；后者順序使用欠采樣得到平衡訓練集，每次從原始數據集中刪除被正確分類的多數類樣本。

在本文中，我們設計了一種新的基于樣本學習復雜度的過采樣方法LDSMOTE，它選擇出最重要并且難以學習的少數類樣本，根據樣本學習復雜度為它賦予選擇權重，然后使用SMOTE 算法合成少數類，加入到訓練集中，達到平衡正負樣本的目的。

3 本文方法

不同于ADASYN 算法，在LDSMOTE 中，樣本的學習復雜度包含兩個方面，近鄰少數類的平均距離和近鄰多數類的個數。對于每個少數類主樣本xi，它與K 個近鄰少數類的平均距離kMinDisti表示了該樣本在少數類樣本空間中的稀疏程度。它的值越大，意味著少數類樣本之間距離很大，即它在少數類樣本空間中分布很稀疏，遠離了少數類的中心區域，這類樣本難以學習，對它應賦予一個更大的權重；反之，該樣本在少數類樣本空間中密集，這類樣本容易學習，應該賦予一個更小的權重。另一方面，在以它的第K 個少數類近鄰樣本距離為半徑的鄰域內，多數類樣本數nMaji表示了它的局部多數類密度。隨著多數類樣本數的增多，它位于多數類與少數類的邊界區域或位于多數類的中心區域的可能性越大，它的學習越困難，權重應該越大。同時，對這兩項值做歸一化操作，分別得到K近鄰少數類平均距離的歸一化值和局部多數類樣本數的歸一化值，即：

它的值越大，表示越難學習。α 是一個加權系數，表示少數類平均距離對樣本學習復雜度貢獻的比例。當α 取值為0 時，它與ADASYN 算法相似，都是將它的近鄰多數類樣本數作為它的學習復雜度，不同點在于：在ADASYN 算法中，K 近鄰包含了多數類和少數類，計算的是其中多數類的樣本數，只能?。?，K］之間的整數值，所以學習復雜度至多存在K+1 個不同值，它是一系列離散值，這不能充分地表達樣本之間的差異性。而在本方法中，少數類的權值可能有大于K+1種不同的取值情況，并且在α 不為0 時，也包括了近鄰少數類平均距離，所以學習復雜度是一個連續值，它更能夠表現少數類樣本在學習復雜度方面的多樣性。

從以上算法流程中，我們可以看出：少數類樣本被選擇作為主樣本的次數與它在少數類樣本空間的分布和在多數類樣本空間的分布都有關，分別對應于它的局部少數類平均距離和局部多數類樣本數，實際上，這也對應了它的學習復雜度。圖1給出了iris數據（使用第一維和第二維特征，以類別setosa為少數類，其他兩類為多數類，o表示少數類，x 表示多數類）中少數類樣本的學習復雜度的等高線，可以看出，在邊界位置的樣本復雜度比中心區域高，所以，在iris 數據集上，本文方法會合成更多對分類器有決策意義的邊界樣本。

圖1 iris數據少數類樣本的學習復雜度的等高線

4 實驗結果與分析

4.1 數據集

為了驗證本文方法的有效性，我們從KEEL 不平衡數據庫［13］中選取了一部分的基準數據集，以下的表1 列出了它們的基本信息，包括特征維度、數據集大小、少數類與多數類的樣本數以及不平衡比例（多數類：少數類）。

表1 不平衡數據集的基本信息

4.2 評價指標

在不平衡數據的分類問題中，以分類準確率作為指標評價模型的性能是不正確的，本文選用Recall、G-mean和AUC作為模型的評價指標［2］。

4.3 實驗設計

本文中所有實驗都采用5 重交叉驗證的方式，即將數據集劃分為5 等份，每次選擇其中的4 份作為訓練集，剩余1份作為測試集，5次實驗結果取平均值作為評價指標。按照以上方式，將數據集打亂后重復進行10 次實驗，得到評價指標的均值和方差，作為最終的實驗結果。我們對訓練集分別使用原始數據ORI、隨機上采樣ROS、SMOTE、BSMOTE（Borderline-SMOTE）、ADASYN 和LDSMOTE 方法進行處理，使用支持向量機LIBSVM［14］作為分類器，得到分類結果。其中，使用網格搜索策略選擇SVM中參數c 和 σ 的值；LDSMOTE 的K 取值都為5，與SMOTE、BSMOTE 和ADASYN 算法中的K 值相同，α 取值為0.9。

4.4 結果與分析

表2、表3 和表4 分別記錄了在19 個不平衡數據集上，使用不同重采樣方法得出的Recall、G-mean 和AUC 的數值，在每個評價指標中，第一項表示10 次實驗結果的均值，第二項表示方差。為了便于觀察和比較，我們用粗體標識出每個數據集上的最優結果。

表2 Recall性能對比

表3 G-mean性能對比

表4 AUC性能對比

從表2 中可以看出，在多數數據集上，使用采樣方法平衡樣本的分類算法在召回率上都要優于原始的分類算法。實際上，過采樣方法通過增加少數類樣本調整訓練集的數據分布，強調了少數類對學習過程中的貢獻度，從而擴張了少數類的決策空間，使得正類樣本被正確預測的樣本數增多，正類樣本被錯誤預測的樣本數減少，所以召回率Recall值比原始的分類結果要好。另一方面，LDSMOTE算法在11個數據集上取得了最優的Recall值，表明了它對少數類的識別率較大。

表3 表示了在19 個數據集上不同重采樣方法的G-mean 性能指標。G-mean 的值等于正類準確率與負類準確率的幾何平均數，反映了學習算法的綜合性能，它的值越大，分類的性能越好。從表3中我們可以看出，在大部分的數據集上，LDSMOTE的G-mean 大于其它方法，表明了它的綜合能力較強，在保持多數類高識別率的情況下，能夠較大提升少數類的識別率。

從表4 中，我們可以看出LDSMOTE 在超過半數的數據集上取得了最優的AUC值。與SMOTE相比，LDSMOTE 在除了glass6、shuttle0vs4、vehicle2和yeast5 以外的數據集上取得的AUC 值都大于SMOTE；與ADASYN 相比，除了glass6、haberman、segment0、vehicle2 和yeast5 數據 集，LDSMOTE 的AUC 值都大于ADASYN。在vehicle2 數據集上，LDSMOTE 的AUC 結果是過采樣方法中較差的，我們認為這可能與噪聲樣本有關。若存在一個少數類噪聲樣本，它的K 近鄰少數類平均距離很大，并且近鄰中多數類特別多，LDSMOTE 會將它的權重設置非常大，在它的鄰域使用SMOTE 合成的噪聲樣本就越多，所以LDSMOTE 在該數據集上的AUC值較低。

5 結語

本文設計了一種新的基于樣本學習復雜度的過采樣方法LDSMOTE，用于不平衡數據的分類。根據局部少數類平均距離和局部多數類樣本數，該方法選擇出最重要并且難以學習的少數類樣本，對它賦予大的選擇權重，在它鄰域范圍內合成更多的樣本。使用支持向量機，對KEEL 不平衡數據庫中的19 個數據集進行分類實驗，結果表明，在超過半數 的 數 據 集 上 ，LDSMOTE 的Recall、G-mean 和AUC 性 能 優 于SMOTE、Borderline-SMOTE 以 及ADASYN算法。