[ML] Basic Imbalance data

有鑑於不管是有人問, 或者是我自己, 都碰到滿多次 imbalance data

假設你有兩類的 data, 差異相當的大, 可以 class a 佔了 95%, class b 佔了 5%

針對這種很嚴重的 imbalance data 那該怎麼辦勒? 或者甚至是 multi-class 的狀況

其實有相當相當多的方法可以去 approach 他

有一篇 '09年發表在 IEEE Transactions on Knowledge and Data Engineering 的 paper 有做 survey
(話說這是一個相當相當好的期刊, 常常有很多最新的知識發表)

他們 survey了眾多過去處理 imbalance data 的方法, 我個人看完是覺得滿實用的

其中分析了 over-sampling, under-sampling, kernel based, active learning, cost-sensitive 等應用

而我這邊針對 over-sampling, under-sampling 做簡易的翻譯跟解釋

Title: Learning from Imbalanced Data (2009)

pdf: http://www.ele.uri.edu/faculty/he/PDFfiles/ImbalancedLearning.pdf

其實此 paper 作者最近出書了, 但是我還沒有買到這本, 所以只好參考他這篇 paper 來解說


首先我們要處理的問題是 Imbalance data, 所以有分 majority 跟 minority 兩種(多跟少)

整個 training set 簡稱 S, majority 可以簡稱為 S_maj, minority 可以簡稱為 S_min

而 majority 的數量表示為|S_maj| , minority表示為 |S_min|, | | <-- 這可不是絕對值, 這是個數的意思

那其實有很多方法都會隨機取一些 majority or minority 的樣本

所以如果隨機只採取部份 majority 的樣本簡稱為|E_maj|, minority 採取補份則稱為 |E_min|

這邊假設的情況都是兩著差異相當的大, 例如 1:10 甚至是 1:100 之類的情況

Over-Sampling

over-sampling 通常指的是 random over-sampling, over-sampling 意思就是增加 sampling 的數量

而常見的思維就是把少的變多的, 所以也就是隨機的挑選 S_min 並且再加入到 S_min 中

而增加的量通常是 |S_maj| - |S_min|

Under-Sampling

那相反來說, under-sampling 就是減少 sampling 的數量, 所以剛剛是把少的增加

現在就是把多的減少, 也就是隨機的挑選 S_maj 的樣本除去到跟 S_min 一樣大小 (|S_min|)

Drawback

那這兩種很直觀的方法很簡單, 可是也都有明顯的缺點

over-sampling 因為重複著增加原本有的資料, 所以容易造成 over-fitting 的狀況

而 under-sampling 則是有可能除去了一些重要的資訊而導致 under-fit 的情況

---

針對於上述的缺點, 有一篇 paper 就提出了 over-sampling 改進的辦法

Title: Exploratory Undersampling for Class-Imbalance Learning (2006)

pdf: http://cse.seu.edu.cn/people/xyliu/publication/tsmcb09.pdf

EasyEnsemble

方法很簡單, 由於 |S_maj| >> |S_min|, 所以我們就隨機產生多個 E_maj, 且 |E_maj| == |S_min|

很明顯的看出要做啥, 也就是將較大量的 class 拆成多個小量的 training set

並且跟 S_min做 training, 例如 |S_maj|:|S_min| 比例是 10 : 1, 所以我就將 S_maj 切成不同的十份 E_maj

然後建立 10 個 classifier 來 training E_maj & S_min, 最後用 ensemble (vote) 的結果來判定

BalanceCascade

跟上述方法接近, 不過只先建立出一組 E_maj & S_min 而非十組

然後就 training 一個 classiifer, 並且判斷整個 S_maj, 將判斷錯誤的挑出來

用錯誤的 S_maj 組一個新的 E_maj , 並且再跟 S_min training 一個 classifier, 然後再判斷 S_maj

然後不停的用這個流程建立下去, 看是先用完 sample 或者是判斷準確停下來

而這可以看得出來, 他每次建立的方式都是根據上一次不會判斷正確的結果來選 sample

---

而針對 under-sampling, 有一篇 '03 年的 ICML workshop paper 所提出的方法

Title: KNN Approach to Unbalanced Data Distributions: A Case Study Involving Information Extraction

pdf: http://cse.seu.edu.cn/people/xyliu/publication/tsmcb09.pdf

NearMiss 1, NearMiss 2, NearMiss 3

針對 under-sampling 的改進方式, 有這三種, 相當單純, 下面判斷依據都是靠 K-NN 結果

NearMiss 1
找尋 S_maj 中誰離 S_min 最近, 就砍掉他 (離幾個平均下來最低的砍掉, 幾個則是看 K 的設定)

NearMiss 2
類似 1, 但是變成是找 S_min 最遠的 sample, 而 S_maj 誰跟這個 sample 離最近, 就砍誰

NearMiss 3
這比較抽象, 給定一個 majority 的數量 α, 如果一個 minority 週邊的 majority 樣本超過 α, 就砍

意思就是, 每個 minority 週邊只會有 α 個 majoirty 樣本, 至於決定砍誰留誰當然也是看 K-NN

---

Synthetic Sampling with Data Generation

顧名思義, data 的增加不靠複製 sample 來增加, 而是靠推測可能有哪些 sample 也是樣本來加入

有一篇 2002年發表在 Journal of Artificial Intelligence Research 的 paper 就是講述這種方法的作法

Title: SMOTE: Synthetic Minority Over-sampling Technique

JAIR pdf: http://www.csee.usf.edu/~hall/papers/smote.pdf

這篇其實概念也相當簡單, 也是利用 K-NN 來產生新的 sample

首先假設是 6-NN, 所以我先隨便挑一個 S_min 的點 x_i, 根據 6-NN, 也就是找出離他最近的 6 個點

這邊我們只挑出 S_min的點(忽略S_maj), 然後隨機挑一個 6-NN 的點, 假設為 x'_i

然後在 x_i 跟 x'_i 兩點之間的線上, 隨機挑一個點, 當作新的 sample 加入到 S_min 之中

用數學表達就像是

δ 就是那個隨機的意思, 事實上就是 乘上 [0, 1] 之間的小數

就用這樣的方式去增加 S_min 的 sample 數量

這邊放上 paper 中的簡圖

左圖星星就是 S_min 的分佈, 然後這邊採取的是 6-NN, 然後隨機挑到 x' 圖上是用 x -hat 表示

右圖就是在 x_i 跟 x'_i 中間隨機挑一個點來當作新的 input sample

那當然缺點其實也是有, 首先過度的 generalization 跟 S_maj 的 border 之間會有些許負面影響

所以理所當然也有人加強了此演算法

Borderline-SMOTE

這是一篇在 2005 年 ICIC 發表的 paper

Title: Borderline-SMOTE: A New Over-Sampling Method inImbalanced Data Sets Learning

pdf: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.308.9315&rep=rep1&type=pdf

首先用 K-NN 先找出 S_min 的週邊是 S_maj 的 sample

然後代入下列公式

稍微解釋一下這個公式

S_i:m-NN 也就是前敘所說的從 S_min 用 K - NN 找出鄰近的點, 這邊 K = m, 所以用 m-NN 表示

然後跟 S_maj 交集就表示找出那些鄰近點是 S_maj 的意思

然後計算這些點的數量, 可以做出下列假設

如果今天這些點跟 m 一樣多, 也就是這個 minority 的點周遭全都是 S_maj 的點,

那這點很有可能其實只是干擾或者錯誤的 sample (NOISE)

如果今天這些點等於 m/2 到 m 之間, 也就是有大於等於一半是 S_maj 的點

那就表示很有可能在 border 之間, 或者已經到了 S_maj 的範圍, 會有點危險 (Danger)

如果今天少於 m/2, 那就表示其實這點的範圍還在 minority 的分佈之內, 算是安全(SAFE)

有這些依據之後, 就開始回到原本的 SMOTE 演算法去產生樣本

但是, 只要是 NOISE 狀況的, 就不產生, 反而是 Danger 的才產生新的樣本出來

也就是說 Border-SMOTE 就只針對 sample 的邊界部份產生新的樣本

(SAFE 的產生意義就不大了, 一般 ML 演算法的假設大多會涵蓋點的附近, 多了容易 over-fit)

ADASYN

這是一篇在 2008 年, 在 NN 發表的 paper

Title: ADASYN: Adaptive Synthetic Sampling Approach for ImbalancedLearning

pdf: http://sci2s.ugr.es/keel/pdf/algorithm/congreso/2008-He-ieee.pdf

首先, 大家都打算增加 S_min 的 sample

但是之前 SMOTE 都是針對一個既有的 sample 只增加一個新的 sample

這次不一樣了, 這次打算一次增加多個點, 那流程如下

首先先訂出一個既有的 sample 要多產生幾個新 sample

公式如下

β 在 [0, 1] 之間

但是這樣還不夠, 有的點適合增加多一點, 有的點不適合增加太多

所以利用之前的概念, borderline 與否的情況, 來決定產生點的多寡

其判斷的依據公式如下

Δ_i 意思其實就是上述 Borderline-SMOTE 的S_i:m-NN, 也就是鄰近的點但是屬於 S_maj

K 就是 K-NN 的 K, 因為 Γ 是一個 distribution, 所以 Z 只是要做 normalization 的參數而已

最後將這個應該要增加多寡的比例乘上一開始設定的值

推出這個點應該適合產生幾個新增加的 sample

最後的結論就是, 我要用 x_i 要產生 g_i 個 sample, 且是用 SMOTE 的找 sample 方式產生新 sample

---

Data Cleaning

Title: Two Modifications of CNN

pdf: 我找不到開放式連結

只有 IEEE Explore 連結: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=4309452

剛講了半天的增加的方法, 那再來一點減少的方法吧

有一個方法如下, 首先建立 pair (x_i, x_j )

定義:

且如果沒有發生

則這我們稱呼為 Tomek links

那這代表甚麼呢? 這代表這兩個點, 要嘛有人是 NOISE, 不然就是貼近 Border

所以可以清理掉

但這並不是直接對著 raw training data 直接使用

流程比較常見的是 1: 先做 SMOTE 2: 移除Tomek link point

---

最後一個我們來提提 Cluster-Based

Cluster-Based Sampling Method (CBO)

Title: Class imbalances versus small disjuncts

pdf: 我找不到開放式連結, 只有 ACM 連結 http://dl.acm.org/citation.cfm?id=1007737

這次故事有趣了, 我們終於不用 K-NN 來幫忙了, 這次換個咖, 叫做 K-Means

不過用這個方法有個前提, 每個類別要可以是 clustered

假設我現在整個 dataset 有 5 個類別, 有很多的 sample class 也有很少的 sample class

假設 3 大, 2 小, 3 大裡面有一個比任何類別都大, 假設最大的數量為 N

首先先做 K-means, 也就是先從各個類別挑出 K 個 samples

然後根據各個類別挑出來的 K 個 samples, 算出各個類別的中心點 (mean)

然後開始把沒挑過得 sample 加進來, 一次加一個, 然後調整一次中心點

那開始會有些 class training sample 開始不夠, 就開始做 over-sampling

如果是 3 大的其中非最大的另外那 2 大, 做 over-sampling 做到跟最大的一樣多就好

而那 2 小, 就做 over-sampling 做到 (3 * N / 2) 的數量就好

那其實我查了一下原篇 paper, 並沒有很詳細的說明 over-sampling 的方式

但是我看 Learning from Imbalanced Data 這篇的圖

個人推測, over-sampling 的方式應該是用SMOTE over-sampling 才有可能長成他那樣的範例圖
(有誤的話, 歡迎指正!!)