不平衡數(shù)據(jù)分類算法介紹與比較

在數(shù)據(jù)挖掘中，經(jīng)常會存在不平衡數(shù)據(jù)的分類問題，比如在異常監(jiān)控預(yù)測中，由于異常就大多數(shù)情況下都不會出現(xiàn)，因此想要達(dá)到良好的識別效果普通的分類算法還遠(yuǎn)遠(yuǎn)不夠，這里介紹幾種處理不平衡數(shù)據(jù)的常用方法及對比。

符號表示

記多數(shù)類的樣本集合為L，少數(shù)類的樣本集合為S。

用r=|S|/|L|表示少數(shù)類與多數(shù)類的比例

基準(zhǔn)

我們先用一個邏輯斯諦回歸作為該實驗的基準(zhǔn)：

Weighted loss function

一個處理非平衡數(shù)據(jù)常用的方法就是設(shè)置損失函數(shù)的權(quán)重，使得少數(shù)類判別錯誤的損失大于多數(shù)類判別錯誤的損失。在python的scikit-learn中我們可以使用class_weight參數(shù)來設(shè)置權(quán)重。

欠采樣方法(undersampling)

Random undersampling of majority class

一個最簡單的方法就是從多數(shù)類中隨機(jī)抽取樣本從而減少多數(shù)類樣本的數(shù)量，使數(shù)據(jù)達(dá)到平衡。

Edited Nearest Neighbor (ENN)

我們將那些L類的樣本，如果他的大部分k近鄰樣本都跟他自己本身的類別不一樣，我們就將他刪除。

Repeated Edited Nearest Neighbor

這個方法就是不斷的重復(fù)上述的刪除過程，直到無法再刪除為止。

Tomek Link Removal

如果有兩個不同類別的樣本，它們的最近鄰都是對方，也就是A的最近鄰是B，B的最近鄰是A，那么A,B就是Tomek link。我們要做的就是講所有Tomek link都刪除掉。那么一個刪除Tomek link的方法就是，將組成Tomek link的兩個樣本，如果有一個屬于多數(shù)類樣本，就將該多數(shù)類樣本刪除掉。

過采樣方法(Oversampling)

我們可以通過欠抽樣來減少多數(shù)類樣本的數(shù)量從而達(dá)到平衡的目的，同樣我們也可以通過，過抽樣來增加少數(shù)類樣本的數(shù)量，從而達(dá)到平衡的目的。

Random oversampling of minority class

一個最簡單的方法，就是通過有放回的抽樣，不斷的從少數(shù)類的抽取樣本，不過要注意的是這個方法很容易會導(dǎo)致過擬合。我們通過調(diào)整抽樣的數(shù)量可以控制使得r=0.5

Synthetic Minority Oversampling Technique(SMOTE)

這是一個更為復(fù)雜的過抽樣方法，他的方法步驟如下：

For each point p in S:
1. Compute its k nearest neighbors in S.
2. Randomly choose r ≤ k of the neighbors (with replacement).
3. Choose a random point along the lines joining p and
each of the r selected neighbors.
4. Add these synthetic points to the dataset with class
S.
For each point p in S：
1. 計算點(diǎn)p在S中的k個最近鄰
2. 有放回地隨機(jī)抽取R≤k個鄰居
3. 對這R個點(diǎn)，每一個點(diǎn)與點(diǎn)p可以組成一條直線，然后在這條直線上隨機(jī)取一個點(diǎn)，就產(chǎn)生了一個新的樣本，一共可以這樣做從而產(chǎn)生R個新的點(diǎn)。
4.  將這些新的點(diǎn)加入S中

Borderline-SMOTE1

這里介紹兩種方法來提升SMOTE的方法。

For each point p in S:
    1. Compute its m nearest neighbors in T. Call this set Mp and let m'= |Mp ∩ L|.
    2. If m'= m, p is a noisy example. Ignore p and continue to the next point.
    3. If 0 ≤ m'≤m/2, p is safe. Ignore p and continue to the next point.
    4. If m/2 ≤ m'≤ m, add p to the set DANGER.
For each point d in DANGER, apply the SMOTE algorithm to generate synthetic examples.
For each point p in S:
    1. 計算點(diǎn)p在訓(xùn)練集T上的m個最近鄰。我們稱這個集合為Mp然后設(shè) m'= |Mp ∩ L| (表示點(diǎn)p的最近鄰中屬于L的數(shù)量).
    2. If m'= m, p 是一個噪聲,不做任何操作.
    3. If 0 ≤m'≤m/2, 則說明p很安全，不做任何操作.
    4. If m/2 ≤ m'≤ m, 那么點(diǎn)p就很危險了，我們需要在這個點(diǎn)附近生成一些新的少數(shù)類點(diǎn)，所以我們把它加入到DANGER中.
最后，對于每個在DANGER中的點(diǎn)d，使用SMOTE算法生成新的樣本.

我們應(yīng)用Borderline-SMOTE1的參數(shù)設(shè)置為k=5,為了使得r=0.5

Borderline-SMOTE2

這個與Borderline-SMOTE1很像，只有最后一步不一樣。
在DANGER集中的點(diǎn)不僅從S集中求最近鄰并生成新的少數(shù)類點(diǎn)，而且在L集中求最近鄰，并生成新的少數(shù)類點(diǎn)，這會使得少數(shù)類的點(diǎn)更加接近其真實值。

FORpinDANGER:1.在S和L中分別得到k個最近鄰樣本Sk和Lk。2.在Sk中選出α比例的樣本點(diǎn)和p作隨機(jī)的線性插值產(chǎn)生新的少數(shù)類樣本3.在Lk中選出1?α比例的樣本點(diǎn)和p作隨機(jī)的線性插值產(chǎn)生新的少數(shù)類樣本。

為了達(dá)到r=0.5 實驗取k=5

組合方法(Combination)

SMOTE + Tomek Link Removal

SMOTE + ENN

集成方法(Ensemble)

EasyEnsemble

一個最簡單的集成方法就是不斷從多數(shù)類中抽取樣本，使得每個模型的多數(shù)類樣本數(shù)量和少數(shù)類樣本數(shù)量都相同，最后將這些模型集成起來。
算法偽代碼如下：

1. For i = 1, ..., N:
    (a) 隨機(jī)從 L中抽取樣本Li使得|Li| = |S|.
    (b) 使用Li和S數(shù)據(jù)集，訓(xùn)練AdaBoost分類器Fi。



2. 將上述分類器聯(lián)合起來

BalanceCascad

這個方法跟EasyEnsemble有點(diǎn)像，但不同的是，每次訓(xùn)練adaboost后都會扔掉已被正確分類的樣本，經(jīng)過不斷地扔掉樣本后，數(shù)據(jù)就會逐漸平衡。

該圖來自：劉胥影, 吳建鑫, 周志華. 一種基于級聯(lián)模型的類別不平衡數(shù)據(jù)分類方法[J]. 南京大學(xué)學(xué)報:自然科學(xué)版, 2006, 42(2):148-155