數據嗨客 | 第6期：不平衡數據處理

常用的分類演算法一般假設不同類的比例是均衡的，現實生活中經常遇到不平衡的數據集，比如廣告點擊預測（點擊轉化率一般都很小）、商品推薦（推薦的商品被購買的比例很低）、信用卡欺詐檢測等等。

對於不平衡數據集，一般的分類演算法都傾向於將樣本劃分到多數類，體現在模型整體的準確率很高。

但對於極不均衡的分類問題，比如僅有1%的人是壞人，99%的人是好人，最簡單的分類模型就是將所有人都劃分為好人，模型都能得到99%的準確率，顯然這樣的模型並沒有提供任何的信息。

在類別不平衡的情況下，對模型使用F值或者AUC值是更好的選擇。

處理不平衡數據，可以從兩方面考慮：一是改變數據分布，從數據層面使得類別更為平衡；

二是改變分類演算法，在傳統分類演算法的基礎上對不同類別採取不同的加權方式，使得模型更看重少數類。

本部分對數據層面的一些方法做一個介紹，改變數據分布的方法主要是重採樣：

• 欠採樣：減少多數類樣本的數量

• 過採樣：增加少數類樣本的數量

• 綜合採樣：將過採樣和欠採樣結合

一、欠採樣

隨機欠採樣

減少多數類樣本數量最簡單的方法便是隨機剔除多數類樣本，可以事先設置多數類與少數類最終的數量比例ratio，在保留少數類樣本不變的情況下，根據ratio隨機選擇多數類樣本。

• 優點：操作簡單，只依賴於樣本分布，不依賴於任何距離信息，屬於非啟發式方法。

• 缺點：會丟失一部分多數類樣本的信息，無法充分利用已有信息。

Tomek links方法

首先來看一些定義。假設樣本點

首先來看一些定義。

假設樣本點xi和xj屬於不同的類別，d(xi,xj)表示兩個樣本點之間的距離。

稱(xi,xj)為一個Tomek link對，如果不存在第三個樣本點xl使得d(xl,xi)<d(xi,xj)或者d(xl,xj)<d(xi,xj)成立。

容易看出，如果兩個樣本點為Tomek link對，則其中某個樣本為雜訊（偏離正常分布太多）或者兩個樣本都在兩類的邊界上。

下圖是對Tomek link對的直觀解釋（其中加號為少數類，減號為多數類）：A、B、C中的樣本在兩類的邊界上，D、E中的多數類樣本均為雜訊。

Tomek link對一般有兩種用途：

• 欠採樣：將Tomek link對中屬於多數類的樣本剔除。

• 數據清洗：將Tomek link對中的兩個樣本都剔除。

NearMiss方法

NearMiss方法是利用距離遠近剔除多數類樣本的一類方法，實際操作中也是藉助kNN，總結起來有以下幾類：

• NearMiss-1：在多數類樣本中選擇與最近的3個少數類樣本的平均距離最小的樣本。

• NearMiss-2：在多數類樣本中選擇與最遠的3個少數類樣本的平均距離最小的樣本。

• NearMiss-3：對於每個少數類樣本，選擇離它最近的給定數量的多數類樣本。

NearMiss-1和NearMiss-2方法的描述僅有一字之差，但其含義是完全不同的：NearMiss-1考慮的是與最近的3個少數類樣本的平均距離，是局部的；NearMiss-2考慮的是與最遠的3個少數類樣本的平均距離，是全局的。

NearMiss-1方法得到的多數類樣本分布也是「不均衡」的，它傾向於在比較集中的少數類附近找到更多的多數類樣本，而在孤立的（或者說是離群的）少數類附近找到更少的多數類樣本，原因是NearMiss-1方法考慮的局部性質和平均距離。

NearMiss-3方法則會使得每一個少數類樣本附近都有足夠多的多數類樣本，顯然這會使得模型的精確度高、召回率低。

論文中有對這幾種方法的比較，得到的結論是NearMiss-2的效果最好，不過這也是需要綜合考慮數據集和採樣比例的不同造成的影響。

One-Sided Selection

One-Sided Selection利用從上圖得到的啟發式想法，其中五角星表示少數類樣本，圓形表示多數類樣本，四種不同顏色的圓形代表四種不同類型的多數類樣本：

紅色：屬於多數類中的雜訊（noise），它們都各自緊貼著某一個少數類樣本。

藍色：屬於邊界樣本，此類樣本很容易被錯分。

綠色：屬於多餘的（redundant）樣本，因為在訓練模型的時候，此類樣本沒有提供額外的有用信息，其類別信息可以很容易地通過其他樣本信息得到。此類冗餘的樣本會提高分類的代價，使得邊界曲線向右上方移動。

黃色：屬於安全（safe）樣本，對於分類模型有著重要的作用。

One-Sided Selection演算法的目的是剔除多數類樣本中雜訊（紅色）、邊界樣本（藍色）和多餘樣本（綠色），其演算法流程如下(S為原始訓練樣本集合)：

初始化集合CC，CC應該包括所有的少數類樣本和隨機選擇的一個多數類樣本。

集合C訓練一個1-NN分類器（即kNN中選擇近鄰數為1），並用這個分類器對S中的樣本進行分類，將錯分的多數類樣本併入集合C。

對集合C使用Tomek links方法剔除多數類樣本，得到最終的訓練樣本集合T。

One-Sided Selection演算法中使用Tomek links剔除多數類樣本中的雜訊和邊界樣本，未被1-NN分類器錯分的樣本則被視為多餘樣本，最終得到一個類別分布更為平衡的樣本集合。

二、過採樣

隨機過採樣

與欠採樣對應，增加少數類樣本數量最簡單的方法便是隨機複製少數類樣本，可以事先設置多數類與少數類最終的數量比例ratio，在保留多數類樣本不變的情況下，根據ratio隨機複製少數類樣本。

在使用的過程中為了保證所有的少數類樣本信息都會被包含，可以先完全複製一份全量的少數類樣本，再隨機複製少數類樣本使得數量比例滿足給定的ratio。

• 優點：操作簡單，只依賴於樣本分布，不依賴於任何距離信息，屬於非啟發式方法。

• 缺點：重複樣本過多，容易造成分類器的過擬合。

SMOTE

SMOTE全稱為Synthetic Minority Over-sampling Technique，主要思想來源於手寫字識別：對於手寫字的圖片而言，旋轉、扭曲等操作是不會改變原始類別的（要排除翻轉和180度大規模旋轉這類的操作，因為會使得「9」和「6」的類別發生變化），因而可以產生更多的樣本。

SMOTE的主要思想也是通過在一些位置相近的少數類樣本中生成新樣本達到平衡類別的目的，由於不是簡單地複製少數類樣本，因此可以在一定程度上避免分類器的過度擬合。具體如下圖：

其演算法流程如下：

1. 設置向上採樣的倍率為N，即對每個少數類樣本都需要產生對應的N個少數類新樣本。

2. 對少數類中的每一個樣本x，搜索得到其k（通常取5）個少數類最近鄰樣本，並從中隨機選擇N個樣本，記為y1,y2,…,yN（可能有重複值）。

3. 構造新的少數類樣本rj=x+rand(0,1)?(yj?x)，其中rand(0,1)表示區間(0,1)內的隨機數。

Borderline SMOTE

原始的SMOTE演算法對所有的少數類樣本都是一視同仁的，但實際建模過程中發現那些處於邊界位置的樣本更容易被錯分，因此利用邊界位置的樣本信息產生新樣本可以給模型帶來更大的提升。Borderline SMOTE便是將原始SMOTE演算法和邊界信息結合的演算法。它有兩個版本：Borderline SMOTE-1和Borderline SMOTE-2。

Borderline SMOTE-1演算法流程：

1. 記整個訓練集合為T，少數類樣本集合為P，多數類樣本集合為N。對P中的每一個樣本xi，在整個訓練集合T中搜索得到其最近的m個樣本，記其中少數類樣本數量為mi。

3. 對DANGER中的每一個樣本點，採用普通的SMOTE演算法生成新的少數類樣本。

Borderline SMOTE-2和Borderline SMOTE-1是很類似的，區別是在得到DANGER集合之後，對於DANGER中的每一個樣本點xi：

1. Borderline SMOTE-1：從少數類樣本集合P中得到k個最近鄰樣本，再隨機選擇樣本點和xi作隨機的線性插值產生新的少數類樣本。（和普通SMOTE演算法流程相同）

2. Borderline SMOTE-2：從少數類樣本集合P和多數類樣本集合N中分別得到k個最近鄰樣本Pk和Nk。設定一個比例α，在Pk中選出α比例的樣本點和xi作隨機的線性插值產生新的少數類樣本，方法同Borderline SMOTE-1；在Nk中選出1?α比例的樣本點和xi作隨機的線性插值產生新的少數類樣本，此處的隨機數範圍選擇的是(0,0.5)，即使得產生的新的樣本點更靠近少數類樣本。

下圖可以幫助我們直觀理解Borderline SMOTE的基本想法。考慮最近的m=5個樣本：

• 對於A而言，最近的5個樣本均屬於多數類樣本，認為A為雜訊點，在其附近產生少數類樣本會使得雜訊的影響更大

• 對於C而言，最近的5個樣本中有3個屬於少數類樣本，2個屬於多數類樣本，此類樣本是不容易被錯分的，認為C為安全點

• 對於B而言，最近的5個樣本中有2個屬於少數類樣本，3個屬於多數類樣本，此類樣本容易被錯分，認為B處於少數類的邊界上，加入危險集

• 最終只會對B這類的樣本點做SMOTE操作

三、綜合採樣

目前為止我們使用的重採樣方法幾乎都是只針對某一類樣本：對多數類樣本欠採樣，對少數類樣本過採樣。也有人提出將欠採樣和過採樣綜合的方法，解決樣本類別分布不平衡和過擬合問題，本部分介紹其中的兩個例子：SMOTE+Tomek links和SMOTE+ENN。

SMOTE+Tomek links

SMOTE+Tomek links方法的演算法流程非常簡單：

1. 利用SMOTE方法生成新的少數類樣本，得到擴充後的數據集T

2. 剔除T中的Tomek links對。

普通SMOTE方法生成的少數類樣本是通過線性差值得到的，在平衡類別分布的同時也擴張了少數類的樣本空間，產生的問題是可能原本屬於多數類樣本的空間被少數類「入侵」（invade），容易造成模型的過擬合。

Tomek links對尋找的是那種雜訊點或者邊界點，可以很好地解決「入侵」的問題。

下圖紅色加號為SMOTE產生的少數類樣本，可以看到，紅色樣本「入侵」到原本屬於多數類樣本的空間，這種雜訊數據問題可以通過Tomek links很好地解決。

由於第一步SMOTE方法已經很好地平衡了類別分布，因此在使用Tomek links對的時候考慮剔除所有的Tomek links對（而不是只剔除Tomek links對中的多數類）。

SMOTE+ENN

SMOTE+ENN方法和SMOTE+Tomek links方法的想法和過程都是很類似的：

1. 利用SMOTE方法生成新的少數類樣本，得到擴充後的數據集T。

2. 對T中的每一個樣本使用kNN（一般k取3）方法預測，若預測結果和實際類別標籤不符，則剔除該樣本。

四、Informed Understanding

SMOTE演算法是為了解決隨機過採樣容易發生的模型過擬合問題，對應的也有一些方法解決隨機欠採樣造成的數據信息丟失問題。本部分的Informed Undersampling是對欠採樣的補充，因為其中有一些集成（ensemble）的想法，因此單獨介紹。

EasyEnsemble

EasyEnsemble的想法非常簡單，假設少數類樣本集合為P，多數類樣本集合為N，樣本量分別為|P|和|N|，其演算法流程如下：

隨機欠採樣會導致信息缺失，EasyEnsemble的想法則是多次隨機欠採樣，儘可能全面地涵蓋所有信息，演算法特點則是利用boosting減小偏差（AdaBoost）、bagging減小方差（集成分類器）。實際應用的時候也可以嘗試選用不同的分類器來提高分類的效果。

BalanceCascade

EasyEnsemble演算法訓練的子過程是獨立的，BalanceCascade則一種級聯演算法，這種級聯的思想在圖像識別中用途非常廣。論文中詳細描述了BalanceCascade的演算法流程：

BalanceCascade演算法得到的是一個級聯分類器，將若干個強分類器由簡單到複雜排列，只有和少數類樣本特徵比較接近的才有可能輸入到後面的分類器，比如邊界點，因此能更充分地利用多數類樣本的信息，一定程度上解決隨機欠採樣的信息丟失問題。

參考文獻

1. https://github.com/fmfn/UnbalancedDataset

2. Mani, I., & Zhang, I. (2003, January). kNN approach to unbalanced data distributions: a case study involving information extraction. In Proceedings of workshop on learning from imbalanced datasets.

3. Kubat, M., & Matwin, S. (1997, July). Addressing the curse of imbalanced training sets: one-sided selection. In ICML (Vol. 97, pp. 179-186).

4. Chawla, N. V., Bowyer, K. W., Hall, L. O., & Kegelmeyer, W. P. (2002). SMOTE: synthetic minority over-sampling technique. Journal of artificial intelligence research, 321-357.

5. Han, H., Wang, W. Y., & Mao, B. H. (2005). Borderline-SMOTE: a new over-sampling method in imbalanced data sets learning. In Advances in intelligent computing (pp. 878-887). Springer Berlin Heidelberg.

6. Batista, G. E., Bazzan, A. L., & Monard, M. C. (2003, December). Balancing Training Data for Automated Annotation of Keywords: a Case Study. In WOB (pp. 10-18).

7. Batista, G. E., Prati, R. C., & Monard, M. C. (2004). A study of the behavior of several methods for balancing machine learning training data. ACM Sigkdd Explorations Newsletter, 6(1), 20-29.

8. Liu, X. Y., Wu, J., & Zhou, Z. H. (2009). Exploratory undersampling for class-imbalance learning. Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on, 39(2), 539-550.

推薦閱讀：