基于簇內樣本平均分類錯誤率的混合采樣算法

熊炫睿，陳高升，熊 煉，張 媛，程占偉，付明凱

1(重慶郵電大學 通信與信息工程學院，重慶 400065)

2(重慶工程學院，重慶 400056)

1 引 言

分類學習是機器學習的重要研究方向之一，許多實際應用中存在類別分布不平衡的數據，即數據集中不同類別的樣本數量相差很大的情況，例如入侵檢測、醫療檢測、信用卡欺詐等應用場景，少數類樣本在這些應用場景中也很重要[1，2].機器學習模型在對類別分布不平衡的數據進行分類時，對少數類的召回率會較低.

現有算法層面的方法和數據層面的方法[3]能提高分類模型對類別不平衡數據的分類效果.算法層面的方法包括代價敏感學習方法和集成學習等方法.數據層面的方法有欠采樣方法、過采樣方法與混合采樣方法.欠采樣方法通過減少多數類樣本使數據達到平衡，例如各種基于聚類的欠采樣算法以及隨機欠采樣算法.過采樣方法通過增加少數類樣本使數據達到平衡，例如SMOTE算法.混合采樣方法將過采樣方法與欠采樣方法相結合，通過對少數類樣本采用過采樣方法提高數據量，對多數類樣本采用欠采樣方法降低數據量，將不平衡數據轉化為平衡數據集.

近年來，許多學者對SMOTE算法進行了改進優化.燕昺昊等人通過改進的SMOTE算法增加少數類樣本數量，用得到的平衡數據集訓練一個深度循環神經網絡分類器，對少數類的召回率顯著地得到提高[4].陳虹等人提出一種改進的SMOTE算法—基于最大相異系數密度的SMOTE算法，對少數類樣本采用該算法進行過采樣，然后用得到的平衡數據集訓練梯度提升決策樹分類器，對少數類的召回率顯著地得到提高[5].然而，在處理不平衡的數據分類時僅采用SMOTE過采樣算法，會引入過多的噪聲，從而影響分類器的準確性.

此外，有不少學者對基于聚類的欠采樣算法進行了相關研究.Ng等人提出了一種基于聚類的欠采樣算法—DSUS(Diversified Sensitivity Undersampling)算法，該算法首先對多數類樣本集采用聚類算法，然后根據各個簇的代表點的敏感度大小選擇多數類樣本[6].魏力等人對多數類采用K-means聚類算法，簇中心點根據NearMiss距離進行排序，按序在各個簇內提取若干個與簇中心點相距最近的樣本，從而減少多數類的樣本數量，將不平衡數據轉化為平衡數據集[7].徐麗麗等人采用聚類算法將多數類樣本聚類，從每個簇中根據采樣率選取與簇中心相距最近的若干個樣本，構成平衡樣本集[8].Di等人提出了一種快速搜索與發現密度峰值的自適應聚類算法，對多數類采用該算法進行聚類，然后按照一定比例對每個簇進行欠采樣[9].然而，以上這些基于聚類的欠采樣算法對多數類樣本采用聚類算法后從簇中選取樣本，沒有考慮根據簇內樣本總體信息對簇進行篩選，事實上對于構建分類器而言有些簇價值很低，因此從這些簇內提取的多數類樣本代表性不夠，例如：在支持向量機(Support Vector Machine，SVM)算法中，與分類邊界相距很遠的簇的內部樣本不會是的支持向量，這些簇對構建支持向量機分類器沒有價值.此外，以上這些基于聚類的單純的欠采樣算法會丟棄過多的多數類數據，從而導致過多的多數類信息被丟失.

近年來，許多學者對混合采樣方法進行了相關研究.Han等人提出了GSRA(Gaussian mixture model based combined resampling algorithm)算法[10]，GSRA算法對少數類采用SMOTE方法增加樣本數量，此外，該算法對多數類采用高斯混合聚類算法，從各個簇內中選取部分樣本，從而減少多數類樣本數量.張艷等人對多數類采用一種基于加權重疊距離的k-modes聚類算法，并選取簇中心，以減少多數類樣本數量；同時，對少數類采用SMOTE算法增加樣本數量[11].然而，上述兩種混合采樣方法中對多數類采樣的基于聚類的欠采樣方法，沒有考慮到對于構建分類器而言有些簇價值很低，而從這些簇內提取的多數類樣本代表性也就不夠.

針對上述問題，本文提出了一種基于簇內樣本平均分類錯誤率的混合采樣算法(SABER).該算法定義了“簇內樣本平均分類錯誤率”V(C)的概念，V(C)包含簇內所有樣本的總體分類信息，該混合采樣算法首先對少數類使用SMOTE方法增加樣本數量，接著選取各類別的部分數據添加至平衡樣本集中，并用該樣本集訓練一個初始的分類器，然后進行多輪迭代，在每一輪迭代中執行：采用K-means聚類算法對多數類樣本集中剩余的還未用于訓練分類器的樣本進行聚類，然后計算出各個簇的V(C)，篩選出V(C)最大的若干個簇，并將這些簇各自的代表點不放回地取出并添加至平衡數據集中，同時不放回地隨機取出若干個少數類樣本添加至平衡樣本集中，使平衡樣本集中的少數類與多數類數據數量基本相同的，然后在平衡樣本集上重新訓練分類器.重復執行以上操作，直到達到迭代次數.最終SABER算法得到一個平衡的數據集以及用該數據集訓練好的分類器.

2 相關理論

2.1 K-menas

K-means算法屬于無監督的聚類算法，K-means算法通過多次迭代將樣本劃分到不同的簇中.最小化平方誤差E：

(1)

Input：樣本集D與聚類簇個數r

Output：r個簇

步驟1.從樣本集D中任選r個樣本作為初始的簇中心；

步驟2.循環步驟3和步驟4直到簇中心不再更新；

步驟3.計算r個簇中心與樣本集D中的每個樣本的距離，將樣本劃分到相距最近的簇內；

步驟4.更新r個簇中心；

2.2 SMOTE

Chawla等人提出了SMOTE算法[12].該算法根據已有的樣本合成人工樣本，從而增加少數類樣本數量.SMOTE算法步驟為：

步驟1.對于每一個少數類樣本Si，找出樣本Si的r個近鄰；

步驟2.根據采樣的倍率，從r個近鄰中隨機選出若干個樣本，假設選擇的近鄰為Sj；

步驟3.對于每一個選出的近鄰Sj，根據式(2)在Si和Sj之間隨機合成一個新的樣本Sn

Sn=Si+w(Sj-Si)

(2)

式中，w為一個介于0和1之間的隨機數.

3 提出的SABER算法

3.1 基于簇內樣本平均分類錯誤率的欠采樣

定義1.(簇的代表點)與簇中心相距最近的該簇的內部樣本稱為簇的代表點.

定義2.(簇內樣本平均分類錯誤率)給定一個分類器h和已知樣本標簽的簇C，簇C內樣本的平均分類錯誤率V(C)定義為：

(3)

式中，xj為簇C內樣本j，yj為樣本j的真實標簽，h(xj)返回分類器h對樣本j的預測類別，I為指示函數，若輸入為真，則返回1，否則返回0.

V(C)包含了簇內所有樣本的分類總體信息，當V(C)較大，表明分類器h缺少這個簇足夠的信息，因此，該簇對提升分類器性能具有較大的價值，而該簇的代表點能夠提供該簇大量的有用信息，分類器可以通過對該簇的代表點的學習，從而提高分類器的性能.反之，當V(C)較小，表明分類器已經學習到該簇足夠的信息了，因此，該簇無法為提升分類器提供較多的有用信息.因此，在采用基于聚類的欠采樣方法減少多數類樣本時，應該優先從簇內樣本平均分類錯誤率V(C)更大的簇內選取簇的代表點，從而在減少多數類數據的同時，能選出更具有代表性的多數類數據.

本文對多數類樣本集使用基于簇內樣本平均分類錯誤率的欠采樣，以降低多數類樣本的同時保留盡量多的對構建分類器有用的信息.其核心思想為：首先選取各類別的部分數據添加至平衡樣本集中，并用該樣本集訓練一個初始的分類器，然后進行多輪迭代，在每一輪迭代中執行：采用K-means聚類算法對多數類樣本集中剩余的還未用于訓練分類器的樣本進行聚類，然后計算出各個簇的V(C)，篩選出V(C)最大的若干個簇，并將這些簇各自的代表點不放回地取出并添加至平衡數據集中，同時不放回地隨機取出若干個少數類樣本添加至平衡樣本集中，使平衡樣本集中的少數類與多數類數據數量基本相同的，然后在平衡樣本集上重新訓練分類器.重復執行上述操作以進行下一輪迭代，直到達到迭代次數.最終SABER算法得到一個平衡的數據集以及用該數據集訓練好的分類器.

3.2 SABER算法

在基于簇內樣本平均分類錯誤率的欠采樣的基礎上，將其與SMOTE過采樣結合，提出了SABER混合采樣算法，該算法由兩部分構成：1)使用SMOTE對少數類樣本過采樣；2)使用K-means對多數類樣本聚類，根據簇內樣本平均分類錯誤率V(C)對多數類樣本進行欠采樣.

SABER算法步驟如下所述，其核心思想：基于簇內樣本平均分類錯誤率的欠采樣，在下面的步驟4中.

輸入：一個包含N類的不平衡的數據集、平衡采樣樣本數m、分類器算法h、迭代次數T、SMOTE的參數近鄰數量k.

將各類別的樣本劃分開，共有N個樣本集S1～SN，下標為類編號.輸入的平衡采樣數m與輸出的平衡數據集Q中的各個類別的樣本數近似相等，建議將平衡采樣數m設置為輸入的不平衡數據集中各個類別的樣本數的中位數；本文中的多數類是指樣本數量大于m的類，少數類是指樣本數量小于m的類，非多數類包括少數類和樣本數量等于m的類；多數類欠采樣后的樣本數量等于m，少數類過采樣后的樣本數量約等于m.分類器算法h采用最終將要使用的分類器算法，原因是：公式(3)說明V(C)與分類器h的分類結果相關，而SABER算法根據V(C)對多數類進行欠采樣，因此SABER算法是針對分類器h進行的采樣.

步驟1.對每個少數類樣本集使用SMOTE進行過采樣，根據式(4)設置少數類i的過采樣倍率?i，

?i=(?m/|Si|-1」)×100%

(4)

使少數類樣本數盡量接近平衡采樣數m；

步驟2.分別對每個類的樣本集使用K-means聚類算法，每個類劃分為z個簇，

z=「m/T?

(5)

從每個簇中不放回地提取出簇的代表點，共提取N×z個樣本，將其作為初始的平衡樣本集Q；

步驟3.使用初始的平衡樣本集Q訓練一個初始的分類器h；

針對每一次迭代，t=1，2，…，T-1，重復步驟4)-步驟 6)；

步驟4.對多數類樣本使用基于簇內樣本平均分類錯誤率的欠采樣.分別對每個多數類剩余的還未用于訓練分類器的樣本數據集使用K-means進行聚類，各類生成m個簇.對每一個多數類執行如下操作：根據式(3)計算分類器h對該類的每個簇的V(C)，根據V(C)由大到小的順序對該類的m個簇進行排序，篩選出前z個簇，并不放回地提取出這些簇各自的代表點添加至平衡樣本集Q中，并從該類的樣本集中去掉已被提取的樣本；

步驟5.從每個非多數類剩余的樣本數據集中不放回地隨機提取z個樣本，并添加至平衡樣本集Q中；

步驟6.此時平衡樣本集Q中各類別的樣本數量基本相同，用平衡樣本集Q重新訓練分類器h；重新執行步驟4-步驟6，以進入下一輪迭代，t=t+1，直到t=T-1.

輸出：平衡樣本集Q、已經用Q訓練過的分類器h.

每次迭代中，從每個類中提取z個樣本添加至平衡樣本集Q中，在最后幾次迭代中，z的值可能會變小，具體地設置見表1，以保證最終對各類重采樣的數量達到預期的數量，即最終平衡樣本集Q中多數類樣本數量要等于m，少數類樣本集數量為上述步驟1中以某一倍率使用SMOTE進行過采樣的數量.將創建初始的平衡樣本集的一次迭代包含在內，經過共T次迭代，得到一個各類樣本數量接近的平衡樣本集Q，同時得到一個使用Q訓練好的分類器h.

表1 SABER算法流程

表1為SABER算法的流程，該算法的核心思想：基于簇內樣本平均分類錯誤率的欠采樣，在Step 4中.

4 實驗與分析

本節中，我們評估了本文提出的SABER算法，所有實驗均在Windows10操作系統上進行，并且使用python 3.7.3版本.

4.1 評價方法

本文將G-mean和召回率作為評價指標[13]，通過混淆矩陣可以計算得出這兩個指標.表2為混淆矩陣，其中Nij表示類別為Ci的樣本被識別為類別Cj的個數，參數k表示類別的總數.

表2 混淆矩陣

類別Ci的召回率Ri為實際為類別Ci的所有樣本中被正確預測為類別Ci的樣本的比例，其定義為：

(6)

G-mean與各類別的召回率相關，體現了分類器的總體性能，其定義為：

(7)

4.2 實驗數據與預處理

4.2.1 實驗數據

在網絡攻擊中，各種攻擊發生的頻率各不相同，甚至相差很大，因此網絡入侵檢測是一種典型的類別不平衡的領域.KDD Cup99數據集來源于美國國防高級研究計劃局公開的TCPdump數據，是網絡入侵檢測領域的公開的常用的數據集.該數據集提供了名為KDD Cup99_10%的數據集，該數據集如表3所示，本實驗將使用該數據集驗證SABER算法的有效性.

表3 KDD Cup99_10%數據集

KDD Cup99_10%包含5種類別：Normal和4種攻擊：Dos、Probe、U2R和R2L，每個樣本具有41個特征，表3為數據集的最大不平衡度和樣本數量，最大不平衡度定義為數據數量最多的類與數據數量最少的類的數據數量比值，體現了數據集的不平衡程度，KDD Cup99_10%數據集中的樣本數量最少的類是U2R，樣本數量最多的類是Dos，從表3中可知，該數據集的最大不平衡度很大.該數據集中的類Dos和Normal的數量遠大于類U2R、Probe和R2L的樣本數量，因此，將R2L和U2R視為少數類，將U2R 、Probe和R2L視為非多數類，將Normal和Dos視為多數類.

4.2.2 實驗數據預處理

1)符號型特征數值化

將數據集中的符號型特征轉化為數值型特征，如service，protocol和flag等.

2)Z-score標準化

為了加快算法的收斂速度以及消除不同的特征的不同的量綱對分類結果的影響，需要對數據采取Z-score標準化預處理，計算公式為：

(8)

式中，x為原始輸入數據，γ為歸一化后的輸出數據，μ和為原始數據集各維的均值，σ為原始數據集各維的標準差.

4.3 實驗參數設置

SABER算法的平衡采樣數m應該設置在訓練集中的最大類樣本數和最小類樣本數之間，Probe類的訓練樣本數為這5類訓練樣本數的中位數，因此，將平衡采樣數m設置為Probe類的訓練樣本數.分類器算法h應采用最終將要使用的分類器算法，在實驗中，我們將常用的BP神經網絡和決策樹作為最終將要使用的分類器算法.完整的參數設置如表4所示.

表4 SABER算法的參數設置

4.4 對比算法

與該采樣算法進行對比的其它采樣算法有：

DS-SMOTE[14]：該算法是一種過采樣算法，對SMOTE進行了改進，少數類中鄰域密度小于閾值的樣本被視為稀疏對象，在稀疏對象與其近鄰樣本之間合成新的樣本.

DSUS[6]：該算法是一種基于聚類的欠采樣算法，采用聚類算法將多數類樣本集劃分為若干個簇，根據各個簇的敏感度大小選擇多數類樣本.

GSRA[10]：該算法是一種結合欠采樣與過采樣的混合采樣算法.首先，該算法對多數類采用基于聚類的欠采樣方法—高斯混合聚類方法，將多數類劃分為多個簇，然后從每個簇內提取出部分樣本，從而減少多數類樣本的數量；該算法對少數類采用SMOTE方法，以增加少數類樣本數量.

4.5 實驗結果與分析

因為在許多相關研究中將BP神經網絡和決策樹作為分類器算法，所以本實驗選擇將BP神經網絡和決策樹作為分類器算法，DS-SMOTE、DSUS和GSRA采樣算法得到的數據集分別用來訓練這兩種分類器.

由表5可知，本文提出的SABER算法和過采算法DS-SMOTE、欠采樣算法DSUS以及混合采樣算法GSRA相比，SABER算法上的G-mean值最高，可知SABER算法的總體分類性能是最好的.由表6可知，SABER算法和其它采樣算法相比，SABER算法上的少數類Probe、U2R和R2L的召回率是最高的，同時有較高的多數類召回率.究其原因，SABER算法作為一種混合采樣算法，與單純的過采樣DS-SMOTE算法相比，SABER算法生成的少數類新樣本更少，因此模型學習到的噪聲更少；與單純的欠采樣DSUS算法相比，SABER算法丟棄的多數類樣本更少，機器學習模型能夠學習到更多的多數類樣本信息.SABER混合采樣算法與GSRA混合采樣算法對少數類都采用SMOTE方法，以增加少數類的樣本數量，這兩種混合算法之間的區別在于采用不同的欠采樣方法減少多數類樣本數量.GSRA混合采樣算法對多數類采用基于聚類的欠采樣方法，從所有簇內提取若干個樣本，沒有考慮到有些簇對提升分類器性能而言價值很低，從這些簇中提取的多數類樣本代表性也就不夠.而SABER混合采樣算法在對多數類進行聚類后，根據簇內樣本平均分類錯誤率V(C)篩選出對提升分類器性能更有價值的簇，并選取這些簇各自的代表點.因此，與GSRA算法相比，SABER算法能夠選取更具有代表性的多數類樣本，分類器能從這些樣本中學習到更多的有效的多數類信息，因此其分類性能更好.

表5 SABER算法和其它采樣算法上的G-mean值比較

表6 SABER算法和其它采樣算法上的各類的召回率比較

5 結 語

針對類別不平衡的問題，本文提出了一種基于簇內樣本平均分類錯誤率的混合采樣算法—SABER算法，該算法對多數類樣本進行聚類后，根據簇內樣本平均分類錯誤率篩選出對提升分類器性能更有價值的簇，并選取這些簇各自的代表點，從而選出具有代表性的多數類樣本；SABER算法采用SMOTE算法增加少數類樣本的數量；最終得到一個平衡的數據集.實驗結果表明，在對類別不平衡的數據進行分類的場景中，與其它采樣算法相比，SABER混合采樣算法具有更好的整體分類性能以及更好的少數類樣本分類性能.