資料科學(一) : 處理不平衡資料幾種方法

在經典的分類問題中(classification problem)，當資料集的目標類別(Target Class)資料量差距比例過大(Major Class versus Minor Class)或者在多類別資料中具有類別分布不平均即可稱作為不平衡資料(imbalanced dataset)。我們通常假設資料不平衡是影響模型表現的原因之一，讓我們來看看Data Level Approach有什麼解決方法。

舉一個關於資料不平衡的例子，Van Horn and Perona在一篇文章The Devil is in the Long Tail 中描述到[1]，經過觀察北美鳥類的物種分類照片後發現，自然界的物種大多具有長尾效應(The Long Tail Effect)，也就是少數類別資料數量相當龐大但大部分類別的資料數量很少，正好符合不平衡資料定義，不平衡資料是常見的。如下圖1，自然界物種的長尾效應。

自然界物種長尾效應(注: Y軸非等差) (圖源: The Devil is in the Long Tail)

一、重要前提假設

在開始處理資料不平衡之前，有幾點你需要釐清的觀念

1. 處理資料不平恆是手段而非目的

並不是不平衡的資料一定會導致模型分類不準確。假如機場做新冠肺炎篩檢，100000人真正得病的只有10人，將資料DownSampling到10:10來建立模型真的能獲得一個好的準確度嗎? 亦或者另一個任務你想建立模型辨識人類與麵包，資料比是100000:10，你想模型會把麵包辨識錯誤嗎?

我不當人啦! JOJO!

所以重點並不是要將不平衡資料透過各種方式拉到平衡，只要類別(Class)與類別之間的特徵(Feature)差距過大，模型自然而然就能分類的準確又正確。不巧的是，現實世界中的分類任務特徵是重疊性很高的，如最上述的例子，北美鳥類物種分類，不巧的是每個北美鳥類物種恰好有相似的特徵，都有爪子、羽毛、鳥緣，此時少樣本的物種無法形成群集(Clustering)來讓模型學習。

因此我們的目的應該是，該用什麼方法來讓模型獲得更好的表現，不論你是採用Data Level Approach 在資料層面處理讓模型更好學習小類別抑或是採用更強更好的Model來讓分類更準確。因此，在處理不平衡資料上並沒有絕對答案，最佳的處理方式會跟你的資料集特徵與你想達到的目的習習相關。

2. 資料工程的假設是樣本能夠被線性分類

經典資料工程的假設是分類問題能夠被線性分類的，想像你的資料Feature特徵只有兩個維度，模型要做的事情就是往中間切一條線，並期望這條線能夠達到好的分類效果，如下圖。這類將問題簡化到將樣本視為特徵空間中散布的點點並分類就是稱為線性分類問題，可以用線性代數來求解。然而世上是有很多資料無法用向量空間來表示的，圖片、聲音、文字、影像…這類問題無法被映射到向量空間並進行線性分類的，深度學習模型的成就在於成功將問題用分線性的方式得到很好的結果。

在進行資料工程時的目的是讓模型能夠獲得更好的表現，投射到維度空間即是，樣本散布在高維度的空間中，我們如何透過手段來讓模型有更好的分類結果。也許你可以選擇使用資料工程，採用特徵選取來篩選一些干擾分類的特徵維度; 或是用OverSampling、UnderSampling的方式來讓樣本群集(Clustering)的界線更明確從而使得模型更好的做分類; 抑或是簡單粗暴，使用更強更厲害更符合這個資料集的模型來進行分類。總而言之，沒有標準答案，這篇文章給基於線性分類下幾個值得參考的方法(不討論NN)。

經典二維線性 SVM

二、Data Level Approach

首先探討如何從資料層面讓模型分類的更好。換另一句話來說，資料不平衡導致模型時常將小類別資料當作Noise並忽略他們，如何使得小類別資料相比大類別能形成一個易被分類的群集是Data Level主要探討的目標。Data Level Approach主要分為兩部分OverSampling、UnderSampling，也就是將小類別樣本數量生成變多，或是將大類別樣本數量變少，細節上我們能做些什麼來讓模型有更好的分類呢?

1. Random OverSampling/UnderSampling

當然，最簡單的方法就是隨機複製或刪減樣本，來讓大類別的數量降低、小類別數量增加。但是問題是，隨機複製或刪減真的能夠讓模型變得更好?

2. Condensed Nearest Neighbor (CNN)

CNN(Hart, 1968)[2]是一種採用 Nearest Neighbor 概念的 Undersampling 方式，將每筆資料看成是特徵空間上的一個點。計算KNN將樣本分群成多個群集(Clustering)，將群集內隸屬於不同類別的資料點歸於該群集類別。此方法可以建立在同一個類別的點彼此特徵相似的基礎之上，透過 CNN 方法將離散的點預先歸類進不同群體內，群體與群體之間的界線更加清晰可見，模型更簡單的做分類。

CNN 左右為前後對比 (圖源: KNN Wiki)

3. Edited Nearest Neighbor (ENN)

ENN(Wilson, 1972)[3]同樣屬於Undersampling，將每筆資料特徵映射到多維空間上做處理後計算出Tomek link並將大類別資料刪除。Tomek Link的意思為，抽取小樣本，假如距離該小樣本最近的樣本為其他類別樣本，則這兩個樣本之間為Tomek Link。我們假設了Tomek Link的出現其Link兩端必定有一方為Noise，因此將其刪除一方面減少大量資料類別的數量，平衡小類別的分類比例，另一方面讓類別的界線變得清晰，將兩個群體之間分開，從而使得模型更好的訓練，如下圖所示。

Tomek Link (圖源: Kaggle Resampling strategies for imbalanced datasets)

4. Synthetic Minority Oversampling Technique (SMOTE)

SMOTE(Chawla et al., 2002)[4]是最知名Oversampling方法之一。隨機選中某個小類別樣本與該樣本附近K個同類別樣本(如下圖K=3)，隨機選擇K個樣本中的其中一個並讓他與選中樣本之間產生一個新的同類別樣本。SMOTE給與小類別一個更大、更廣大的樣本覆蓋範圍，並給予模型一個更飽滿的decision regoins。原文中提到，這就是為什麼SMOTE在Naive Bayes有著更好的表現。

SMOTE Algorithm

5. Borderline SMOTE

Borderline SMOTE(Han, Wang and Mao, 2005)[5]是基於SMOTE所做出的改進方案，SMOTE隨機抽取小類別的樣本來進行生成並未考慮到抽取的樣本是否為離群樣本(NOISE)，假如SMOTE抽取到NOISE會導致新生成樣本成為新的NOISE (生成的樣本位於大樣本)，反而使得模型更難以分類。Borderline SMOTE的做法中，將抽取的樣本分成三大類 1) Safe 樣本：周圍一半以上為同樣的少數樣本。 2)Danger 樣本：周圍一半以上為其他類別樣本。 3)Noise 樣本：周圍均為其他類別樣本。Borderline SMOTE只會在Danger樣本附近生成新的樣本，而不會在Safe即Noise樣本周圍生成新樣本，以此來平衡資料與增加界線的明確度。

Borderline-SMOTE: A New Over-Sampling Method in Imbalanced Data Sets Learning

6. Adaptive Synthetic Sampling Approach (ADASYN)

ADASYN(He et al., 2008)[6]針對生成數量做出改良。ADASYN提出，當一個樣本周圍有許多與他相似的少數類別樣本時，應該生成更多的樣本來讓整體變成一個明確的類別群體(Clustering)。計算方式如下，假如我們目標是生成100筆Data，針對我們要生成的少數類別樣本全數抽樣並計算他們周圍所包含同樣類別的樣本數 (r1)。將每一個樣本的r1值正規化後，根據這個r1正規化值與目標生成筆數(100)相乘，來得到應在該抽取樣本周圍生成多少筆資料。此方法可以讓小類別快速形成群集，缺點是群體內所有樣本r1值很高，因此在群集內生成出過多樣本而導致生成出來的樣本之間十分相似。

ADASYN資料生成

7. Feature Selection

剛拿到資料的時候可能有千千萬萬個Feature在手中，有些Feature可能幫助不了模型分類，反而會干擾模型分類能力，篩選幾個用於分類的Feature對模型可能有幫助。Feature Selection計算每一個Feature與Target之間的相互資訊(Mutual information)，簡單的來說，算出兩個事件彼此之間的關聯性。你可以為每一個Feature排出與Target關聯性排名，並選擇高相關性的Feature來訓練看看，要注意的是:

• 只計算了單個Feature與Target的關係，有可能某個Feature自己本身跟Target幾乎無關，但是與其他Feature相結合後與Target分類任務重大相關。
• 實際上Feature到底有沒有用是根據你的模型來決定的，高MI不代表能高度決定模型分類過程。

MI Score Rank (圖源: Kaggle Mutual Information)

Reference

1. Van Horn, G. and Perona, P. (2017) ‘The Devil is in the Tails: Fine-grained Classification in the Wild’, arXiv:1709.01450 [cs] [Preprint]. Available at: http://arxiv.org/abs/1709.01450 (Accessed: 6 March 2022)
2. Hart, P. (1968) ‘The condensed nearest neighbor rule (corresp.)’, IEEE transactions on information theory, 14(3), pp. 515–516.
3. Wilson, D.L. (1972) ‘Asymptotic properties of nearest neighbor rules using edited data’, IEEE Transactions on Systems, Man, and Cybernetics, (3), pp. 408–421.
4. Chawla, N.V. et al. (2002) ‘SMOTE: Synthetic Minority Over-sampling Technique’, Journal of Artificial Intelligence Research, 16, pp. 321–357. doi:10.1613/jair.953.
5. Han, H., Wang, W.-Y. and Mao, B.-H. (2005) ‘Borderline-SMOTE: A New Over-Sampling Method in Imbalanced Data Sets Learning’, in Huang, D.-S., Zhang, X.-P., and Huang, G.-B. (eds) Advances in Intelligent Computing. Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 878–887. doi:10.1007/11538059_91.
6. He, H. et al. (2008) ‘ADASYN: Adaptive synthetic sampling approach for imbalanced learning’, in 2008 IEEE international joint conference on neural networks (IEEE world congress on computational intelligence). IEEE, pp. 1322–1328.