探索SMOTE算法

2020-02-19     sandag

SMOTE是一種綜合採樣人工合成數據算法，用於解決數據類別不平衡問題(Imbalanced class problem)，以Over-sampling少數類和Under-sampling多數類結合的方式來合成數據。本文將以 Nitesh V. Chawla（2002） 的論文為藍本，闡述SMOTE的核心思想以及實現其樸素算法，在傳統分類器（貝葉斯和決策樹）上進行對比算法性能並且討論其算法改進的途徑。

1. 引言

類別不平衡是一種在分類器模型訓練過程中常見的問題之一，如通過大量胸透圖片來學習判斷一個人是否有癌症，又如在網絡流日誌中學習檢測可能是攻擊行為的數據模式，這一類的任務中都是正常的類多於異常（診斷屬於癌症，屬於攻擊行為）的類，在類別不平衡數據下訓練出來的分類器要非常的小心，即使該分類器擁有很高的精度，因為它很可能會習得大部分的都是正常的，而我們可能需要的是它能夠最大程度的識別異常行為，哪怕精度低於前者。

為了解決這一問題，業內已經有以下5種公認的方法去擴充數據集[1]，以至於類別均勻：

  1. 隨機的增大少數類的樣本數量。
  2. 隨機的增大特定少數類樣本的數量。
  3. 隨機的減少多數類樣本的數量。
  4. 隨機的減少特定多數類樣本的數量。
  5. 修改代價函數，使得少數類出錯的代價更高。

本文要介紹的SMOTE算法就是一種綜合1，3方法的改進方式，它以每個樣本點的k個最近鄰樣本點為依據，隨機的選擇N個鄰近點進行差值乘上一個[0,1]範圍的閾值，從而達到合成數據的目的。這種算法的核心是：特徵空間上鄰近的點其特徵都是相似的。它並不是在數據空間上進行採樣，而是在特徵空間中進行採樣，所以它的準確率會高於傳統的採樣方式。這也是為什麼到目前為止SMOTE以及其派生的算法仍然是較為主流的採樣技術的原因。

如上圖所示，假設數據點A在特徵空間上有4個鄰近點，若N為2，則SMOTE會隨機選擇其中2個鄰近點B,C，分別計算A->B， A->C的距離，如圖中綠線和紅線所示，在綠線或紅線上的所有採樣點都是合理的，如點A1。為了確保數據點儘可能的多樣（不重疊），故乘上一個[0, 1]之間的隨機因子。

本文將會在第2章根據SMOTE的核心以及其偽代碼實現該算法，並應用在測試數據集上；第3章會使用第三方 imbalanced-learn 庫中實現的SMOTE算法進行採樣，以驗證我們實現的算法的準確性，當然這個庫中的算法要優於樸素的SMOTE算法，之後我們會以決策樹和高斯貝葉斯分類器為工具，對測試原始數據、應用我們所實現的SMOTE採樣後產生的數據以及應用第三方庫SMOTE產生的數據三者分別產生的數據集進行性能比較；第4章會討論樸素SMOTE算法更加魯棒和表現更好的優化途徑；第5章是對本文的總結。

2. 算法分析與實現

下圖是在SMOTE論文中提出的偽代碼，由兩個函數 SMOTE(T, N, K) 和 Populate(N, i, nnarray) 組成。

SMOTE 負責接受要採樣的類數據集X，返回一個經過SMOTE採樣後的數據集，大小為 (N/100)*T ，函數有三個參數，分別是 T: 需要處理的數據集X的樣本數量; N: 採樣比例，一般為100, 200, 300等整百數，對應即1倍，2倍，3倍；K: 為採樣的最近鄰數量，論文中默認為5 。 SMOTE 代碼思想非常簡單，掃描每一個樣本點，計算每一個樣本點的K個最近鄰，將每一個最近鄰樣本點的索引記錄在 nnarray 中，之後傳入 Populate(N, i, nnarray) 中即完成一個樣本點的採樣。

Populate 則負責根據 nnarray 中的索引去隨機生成 N 個與觀測樣本 i 相似的樣本。該函數會計算隨機鄰近點 nn 與觀測樣本 i 點的每一個特徵之間的差距 dif ，將其差距乘上一個[0, 1]隨機因子 gap ，再將 dif*gap 的值加上觀測點 i 即完成了一個特徵的合成。

在Python中實現如下：

註：為了保證本文中所有代碼的可復現性，設置的 random_state 均為 666

def NaiveSMOTE(X, N=100, K=5):    """    {X}: minority class samples;    {N}: Amount of SMOTE; default 100;    {K} Number of nearest; default 5;    """    # {T}: Number of minority class samples;     T = X.shape[0]    if N < 100:        T = (N/100) * T        N = 100    N = (int)(N/100)        numattrs = X.shape[1]    samples = X[:T]    neigh = NearestNeighbors(n_neighbors=K)    neigh.fit(samples)    Synthetic = np.zeros((T*N, numattrs))    newindex = 0        def Populate(N, i, nns, newindex):        """        Function to generate the synthetic samples.        """        for n in range(N):            nn = np.random.randint(0, K)            for attr in range(numattrs):                dif = samples[nns[nn], attr] - samples[i, attr]                gap = np.random.random()                Synthetic[newindex, attr] = samples[i, attr] + gap*dif            newindex += 1        return newindex        for i in range(T):        nns = neigh.kneighbors([samples[i]], K, return_distance=False)        newindex = Populate(N, i, nns[0], newindex)    return Synthetic

這裡沒有採用矩陣運算，而是完完全全的按照論文中的方式復現（所以稱為NaiveSMOTE），其中最近鄰的計算我們使用 scikit-learn 提供的 NearestNeighbors 類完成。

接下來我們使用 scikit-learn 中的 make_classification 來生成測試分類數據集，模擬不平衡類數據，當然有興趣的讀者也可以去尋找論文中所使用的數據集。

from sklearn.datasets import make_classificationX, y = make_classification(n_samples=500,                           n_features=9,                           n_redundant=3,                           weights=(0.1, 0.9),                           n_clusters_per_class=2,                           random_state=666)   # 為了可復現性print(X.shape, y.shape)       # ((500, 9), (500,))# 查看y的各類樣本數 print(view_y(y))              # class 0: 50  class 1: 450

原數據集的分布如下圖所示，其中紅色圓圈為正類即少數類，藍色×為負類即多數類。

將我們實現的 NaiveSMOTE 應用在此測試數據上：

X_over_sampling = NaiveSMOTE(X[y==0], N=800)print(X_over_sampling.shape)         # (400, 9) 新增了400個樣本# 將合成數據與原數據集合併new_X = np.r_[X, X_over_sampling]new_y = np.r_[y, np.zeros((X_over_sampling.shape[0]))]print(new_X.shape, new_y.shape)      # ((900, 9), (900,))print(view_y(new_y))                 # class 0: 450 class 1: 450

接下來我們將原數據集與經過 NaiveSMOTE 合成後的數據集進行比對：

可以很清晰的看見原來的類增大至一個滿意的水平，並且生成的類之間距離都相距不遠。

3. 算法性能比對

本章我們將引入第三方庫 imbalanced-learn 中提供的 SMOTE 類與依據論文實現的 NaiveSMOTE 進行比較。兩者都是基於同一個論文的思想去實現的，只是第三方庫中實現的 SMOTE 更為魯棒，並且能夠綜合考慮所有的類，是一種完全意義上的 Combination of Over-sampling minority class and Under-sampling majority class 技術。因此我們引入它只為了驗證我們所復現的方法的準確性。

from imblearn.over_sampling import SMOTEsm = SMOTE(random_state=666)X_res, y_res = sm.fit_resample(X, y)     # 即完成了合成print(X_res.shape, y_res.shape)          # ((900, 9), (900,))

下圖對比 imblearn 的 SMOTE 與我們復現的 NaiveSMOTE 生成的數據集：

能看出 NaiveeSMOTE 合成的數據更加傾向於中部，而第三方的 SMOTE 能夠綜合考慮全局情況下方區域生成的數據要比 NaiveSMOTE 的多。

接下來我們使用 DecisionTree 和 GaussianNaive 來驗證3個數據集（原數據集、NaiveSMOTE合成的數據集和第三方SMOTE合成的數據集）的ROC曲線，具體代碼見附錄中的 Notebook 文件

原數據的ROC曲線

NaiveSMOTE生成的數據的ROC曲線

第三方SMOTE生成的數據的ROC曲線

可以看出 NaiveSMOTE 與 imblearn 的 SMOTE 生成的數據的 AUC 面積均大於原始數據的面積。 imblearn 的 SMOTE 生成的數據在 GaussianNaiveBayes 分類器上的表現要好於 NaiveSMOTE 所生成的數據訓練出來的分類器。

4. 算法改進

這部分我們從 NaiveSMOTE 的三個方面進行優化討論：

  1. 處理速度。 NaiveSMOTE 中有許多處都可以改成使用矩陣運算的方式，這樣會提高數據處理的速度。並且 Populate 函數也顯得非常冗餘，可以用矩陣運算將其改寫。
  2. 全局合理性。 全局合理性包括兩個方面：合成數據比率的合理性和合成數據在全局的合理性。合成數據比率的合理性：在 NaiveSMOTE 中可以知道樣本的數量有 N 合成比率來控制，只能合成其整數倍，本文中使用的數據集恰好是 1:9 ，只要合成原始數據的8倍即可是兩類都到達一個相對數量同等的水平，但是在現實數據集中大部分都不具備成倍的數量關係，因此可以考慮更換一個更好的生成比率，使得每個類均能處於相對數量近似的水平，避免出現合成後的原少數類變多數類的情況。合成數據在全局的合理性：回想在 NaiveSMOTE 與 imblearn SMOTE 各自合成的數據對比中可以發現， NaiveSMOTE 更加容易使得合成的數據聚集在某一樣本點附近，而 imblearn SMOTE 所合成的數據更為稀疏且分布均勻，更加接近原始數據的機率分布。其原因在於 NaiveSMOTE 在進行合成時只考慮原始的數據樣本，沒不考慮合成後的數據樣本會如何影響全局數據。可以考慮在每次合成數據後將其加入數據集，在處理過程中將合成數據也加入考慮範圍。
  3. 魯棒性。 不難發現 NaiveSMOTE 僅能夠處理數值型的數據並且其距離計算公式很有可能產生誤解。在現實中有許多非數值型的數據，如 性別 , 職業 等等。當然可以將其全部重新編碼成可以應用數值處理的數據，如將性別進行 OneHot 編碼，但是此時的距離計算公式就會出現誤解，可以考慮更換為歐氏距離、曼哈頓距離或者馬氏距離等。

Note：在對性別進行 OneHot 編碼時情況如下:

男性: 0 1女性: 1 0

如果按照 NaiveSMOTE 原始的距離計算公式，很有可能會將其理解為男性和女性的差距為1，因此產生誤解。

5. 結論

本文對三種數據進行對比，經過 NaiveSMOTE 和 imblearn SMOTE 合成後的數據在傳統分類器上的表現均好於原始數據(即不做任何修改)，且 imblearn SMOTE 在魯棒性上要高於 NaiveSMOTE 。討論 NaiveSMOTE 的不足與其可能的優化方向。建議在實際應用中優先考慮魯棒性更高的 imlearn SMOTE 而不是自己造輪子， imblearn SMOTE 的實現更加符合主流標準。但不能因此就忽略了 NaiveSMOTE 的意義，任何的優化有必要要基於原有的基礎。理解 NaiveSMOTE 才能去更好的使用和優化它。

文章來源: https://twgreatdaily.com/zh-tw/qNAcXHAB3uTiws8KlYVZ.html