構造性覆蓋算法的SMOTE 過采樣方法*

嚴遠亭，朱原瑋，吳增寶，張以文，張燕平

安徽大學 計算機科學與技術學院，合肥230601

1 引言

在生物醫學數據分析[1-3]、衛星雷達圖像中溢油的檢測[4]、文本分類[5]和欺詐電話的檢測[6]等很多實際的應用領域中，處理的對象往往是不平衡數據集。不平衡數據集[7]是指數據集中某類樣本的數量明顯少于其他類樣本的數量。為了描述方便，一般將數量較多的樣本稱為負類樣本，數量較少的樣本稱為正類樣本。在處理不平衡數據集分類問題上，傳統的機器學習分類算法總會傾向于負類樣本的預測，從而導致正類樣本的識別能力下降。在很多情況下，識別出正類樣本要比識別出負類樣本更為重要，甚至會涉及到分類代價敏感問題[8]。因此，如何有效地提高不平衡數據集中少數類樣本的分類準確率和整體準確率成為機器學習領域的一個研究熱點和難點。

在解決不平衡數據分類問題上，近十年來眾多國內外學者做了大量的研究工作，主要概括為以下兩類：一個是從數據集層面；另一個是從算法層面。其中，從數據集層面[9]是通過一些機制改善不平衡數據，獲到均衡的數據分布，常見的策略包括過采樣技術和欠采樣技術，一種常用的過采樣方法是Chawla等[10]提出的合成少數類過采樣技術（synthetic minority over-sampling technique，SMOTE）。SMOTE 方法的優點在于它能使決策區域更大，但也存在兩方面的缺陷：一是在選擇最近鄰時存在一定的盲目性，即如何確定K值才能使算法達到最優是未知的；二是該算法無法克服不平衡數據集的數據分布問題，即容易產生分布的邊緣化問題。在少數類中，不同樣本在過采樣過程中的作用并不相同，處于少數類邊界的樣本往往比處于少數類中心的樣本作用更大。

為了解決上述SMOTE 方法盲目性和邊緣化的問題，Han等[11]提出基于SMOTE的Borderline-SMOTE算法，算法通過比較少數類樣本近鄰中多數類與少數類樣本的個數，來判斷該樣本是否處于少數類樣本的邊界，然后只對少數類的邊界樣本進行SMOTE過采樣處理。He等[12]提出一種自適應合成采樣（adaptive synthetic sampling，ADASYN）算法，算法以樣本的分布為標準，動態地確定合成樣本的總數量，并自適應地改變不同少數類樣本的權重，為每個樣本合成相應數量的樣本。Calleja 等[13]提出D-SMOTE 算法，利用求最近鄰樣本均值點生成人工合成樣本。陳思等[14]提出在數據處理之前對數據進行聚類融合，判定在多次聚類過程中總是處于同一類簇的樣本為中心樣本，總是變化所屬類簇的樣本為邊界樣本，然后對少數類的邊界樣本進行SMOTE 采樣，對于多數類的中心樣本進行欠采樣。Barua 等[15]提出（majority weighted minority over-sampling technique，MWMOTE）算法，該方法首先識別難以學習的信息類樣本，并根據其與最近的多數類樣本之間的歐氏距離賦予它們權重，然后利用聚類方法從加權信息類樣本中生成合成樣本，這樣所有生成的樣本都位于某個少數類的集群中。陶新民等[16]提出基于代價敏感的支持向量機算法，首先利用邊界人工少數類過采樣技術（Borderline-SMOTE）實現訓練樣本的均衡，然后利用K近鄰構造代價值，同時利用每個樣本的代價函數來消除噪聲樣本對SVM（support vector machine）算法精度的影響。Batista 等[17]提出了SMOTE+Tomek-Link 的方法，首先對原始的數據集進行SMOTE 過采樣，然后將Tomek 鏈作為清除數據的方法，生成具有定義明確的類集群的平衡數據集。

上述方法從不同的側重點對不平衡數據進行了處理，但這些方法在篩選少數類關鍵樣本方面仍存在一定的不足。為了解決此問題，本文提出一種基于構造性覆蓋算法[18]的不平衡數據分類算法（constructive covering algorithm-based minority oversampling technique，CMOTE）。該算法提供了兩種不同的策略（覆蓋內樣本個數和覆蓋密度）對少數類中關鍵樣本進行選擇。首先，利用構造性覆蓋算法找出少數類樣本的所有覆蓋；然后，選擇覆蓋中樣本數或樣本密度不大于給定閾值的樣本作為過采樣過程的輸入；最后，對所選樣本使用SMOTE 生成新的少數類樣本，并將其與原始數據集結合作為訓練集構造分類器。

2 SMOTE 算法

SMOTE 是一種基于隨機過采樣算法的改進過采樣方法[19]，應用十分廣泛。SMOTE 的基本思想是利用K近鄰[20-21]和線性插值[22]，在相距較近的兩個少數類樣本間按照一定的規則人工地插入新的樣本，以達到使少數類樣本數目增加，數據集趨于平衡的目的。算法具體過程描述如下：

（1）對于少數類中每一個樣本x，以歐氏距離為標準計算它到其他每一個少數類樣本的距離，得到其K近鄰。

（2）根據樣本不平衡程度設置一個采樣倍率N，對每一個少數類樣本x，從其K近鄰中隨機選擇若干個樣本，假設其中一個選中的近鄰為xn。

（3）對于每一個隨機選擇的近鄰xn，按照式（1）構建新的樣本Xnew：

（4）把人工合成的新樣本與原始數據集組成一個新的數據集，然后利用分類器對其進行分類。

為了更直觀地表述，圖1（a）表示少數類樣本x利用K近鄰找出最近的同類樣本點，圖1（b）中Xnew表示利用最近鄰和線性插值的方法生成少數類樣本點。

Fig.1 SMOTE schematic chart圖1 SMOTE 示意圖

3 構造性覆蓋算法的少數類過采樣技術

3.1 構造性覆蓋算法

構造性覆蓋算法（constructive covering algorithm，CCA）可以看作一個三層的神經網絡分類器，包括輸入層、隱藏層和輸出層。

輸入層共有n個神經元，每個神經元對應樣本的一維特征屬性，假定X={(xi,li)|i=1,2,…,t,li=1,2,…,m}為給定的數據集，t和m分別表示樣本數目和類別數目，即。

隱藏層共有s個神經元，初始時為0 個，每一個球形覆蓋對應一個神經元，每個神經元的權值為覆蓋的中心點，閾值為覆蓋的半徑。對所有的樣本進行覆蓋，求得的一組覆蓋表示為表示第i類樣本的第j個覆蓋。隱藏層共有s=∑ni個覆蓋，其中ni代表第i類的覆蓋個數，i=1,2,…,m。

輸出層共有m個神經元，第i個神經元的輸入為類別相同的一組覆蓋，輸出為該類別。例如當輸出Ot=(o1=0,o2=0,…,oi=1,…,om=0)，oi=1 表示第i個樣本的輸出。

CCA 根據樣本之間的距離構造一個覆蓋，首先找到不同類別的最近樣本，然后找到相同類別的最遠樣本。值得注意的是，求最大距離等于求最小內積，在構造覆蓋時用內積來描述CCA。CCA 算法描述如下[23-24]：

（1）根據式（2）將全部樣本投影到n+1 維的球面空間。

（2）隨機選擇一個樣本xi作為覆蓋中心點，根據內積計算公式分別計算最大內積d1(k)和最小內積d2(k)。

（3）計算覆蓋半徑：

（4）根據xi和θ構造一個覆蓋，即一個隱藏神經元。

（5）從訓練集中刪除覆蓋內的樣本，回到步驟（2），直到所有的樣本都被覆蓋。

從以上描述很容易看出，如果學習了一個樣本，它將立即從訓練集中移除，CCA 算法避免了迭代計算。此外，CCA 算法從一個空的隱藏層開始，并根據后續數據的位置擴展現有的隱藏神經元，該學習過程避免了盲目選擇神經網絡的結構。覆蓋的形成十分適合在不平衡數據中為SMOTE 算法尋找候選樣本。

3.2 CMOTE 算法

在少數類中識別哪些關鍵樣本進行過采樣，與數據集的不平衡度、樣本整體分布情況、少數類內部樣本分布情況、樣本個數、樣本屬性個數以及樣本屬性的類型都有一定的關系。這是一個復雜的優化問題，確定數學模型比較困難。從構造性覆蓋算法的構建過程來看，其能夠從一定程度上挖掘樣本空間領域的信息，因此本文基于CCA 這樣的特點，提出利用CCA 來進行關鍵樣本的選擇。

根據上述提到的CCA 與SMOTE 算法，本文提出基于以上兩種算法的不平衡數據分類算法（CMOTE算法），識別不平衡數據集中容易被誤分的少數類樣本。

首先，該算法利用構造性覆蓋算法對不平衡數據求覆蓋，每一個覆蓋包括覆蓋類別、覆蓋內樣本數、覆蓋半徑和覆蓋中心點樣本。對于少數類樣本形成的覆蓋，如果覆蓋包含較多個樣本，則該覆蓋中的樣本易于分類，對于提高識別少數類樣本模型的能力貢獻不大。

其次，本文提出了兩種策略來確定選擇哪些少數類樣本來生成新樣本。（1）若覆蓋內的樣本數量小于特定閾值P，則覆蓋內的樣本視為關鍵樣本；（2）若覆蓋內的樣本密度小于特定閾值D，則覆蓋內的樣本視為關鍵樣本。

按照CCA的構建過程，本文定義如下的覆蓋密度：

其中，m表示的是第i個少數類樣本的覆蓋中樣本的個數，r是覆蓋的半徑，其值由式（3）～式（5）求得。

算法1基于構造性覆蓋算法的少數類過采樣技術

輸入：訓練集T={(x1,l1),(x2,l2),…,(xn,ln)}，閾值P，閾值D，采樣倍率N。

輸出：合成的少數類樣本集合。

最后，使用SMOTE 算法對上述關鍵樣本合成新的少數類樣本。CMOTE 算法的具體過程描述如算法1 所示。

為了直觀地描述CMOTE 算法，以二維數據為例，算法的大致過程如圖2 所示。圖2（a）中少數類樣本B是利用構造性覆蓋算法篩選出容易被誤分的樣本點。圖2（b）中的少數類樣本B利用SMOTE 算法按照特定的比率N合成新的樣本，新樣本與原數據集組合成新的數據集，新數據集使用WEKA 平臺[25]中的C4.5 決策樹分類算法進行分類。

4 實驗與分析

4.1 評價標準

Fig.2 CMOTE schematic chart圖2 CMOTE 示意圖

在不平衡數據分類中，少數類樣本更容易被錯誤分類，少數類樣本的錯誤分類對分類器整體分類性能[26]的影響很小。例如，當少數類樣本數目所占不到1%時，即使所有的少數類樣本被錯誤劃分成多數類樣本，整體的分類準確率也可以達到99%，但少數類的分類準確率為0。在實際應用中，識別少數類樣本的正確率尤其重要[27]。研究表明，當存在類的不平衡問題時，最常用的性能度量“精度”已經不能準確地度量分類器的性能，因為它不能分別反映出正類和負類的真實分類性能。

一些研究者在研究不平衡數據集分類指標時沒有使用整體的分類性能，ROC 曲線下面積（AUC，縮寫為RA）和準確率、召回率、F-measure、G-mean 等指標更適合評價對少數類的分類性能。因此，本文以準確率、召回率、F-measure、G-mean 和AUC為主要評價指標。召回率用于評價不平衡數據集中少數樣本的正確率。F-measure 用來評價不平衡數據集中少類樣本的分類性能，G-mean 用來評價整體分類性能[4]。

機器學習算法的性能通常由一個混淆矩陣來評估，如表1 所示（針對一個2 類問題）。通常把少數類樣本的標簽視為正，多數類樣本的標簽視為負。表的第一列為真正的類標簽，第一行為預測的類標簽。TP和TN分別表示正確分類的正類和負類樣本個數，FN和FP分別表示錯誤分類的正類和負類樣本個數。

Table 1 Confusion matrix of binary classification tasks表1 二分類任務的混淆矩陣

由上述的混淆矩陣可以得到以下公式。

少數類樣本的召回率為：

少數類樣本的準確率為：

在上述指標的基礎上，定義F-measure（簡稱F1）：

其中，β表示Recall與Precision的相關重要性，本文中取值為1，從定義可以看出，Recall和Precision可用來評估少數類的分類性能，只有Recall和Precision都比較大時，才能獲得較大的F-measure 值，因此Fmeasure常用來評估分類器對于少數類的分類準確率。

Kubat等[28]提出G-mean 作為評價指標：

其中，TPrate用來評估少數類的分類性能，TNrate用來評估多數類的分類性能。從定義可以看出，只有TPrate和TNrate都比較大時，才能獲得較大的G-mean 值，因此G-mean 常用來評估數據集整體的分類準確率。

4.2 實驗數據集

本文使用文獻[29]中的前11 個不平衡數據集，這些數據集在http://www.keel.es/dataset.php 上公開可用，連同從UCI 數據庫下載的數據集Satimage 來驗證本文方法的性能。特別地，對于數據集Satimage，類4的樣本被認為是少數類，其余類的樣本被認為是多數類。對于每個數據集，數據集的詳細信息包括名稱（Dataset）及其縮寫（Abb）、樣本數量（#Ex.）、屬性個數（#Atts.）、少數類和多數類樣本所占總樣本的百分比{mr,MR}以及數據集的不平衡率（imbalanced ratio，IR），都在表2 中列出。

Table 2 Basic information of datasets表2 數據集基本信息

4.3 算法參數的確定

為了篩選出容易被錯誤分類的樣本，需要確定CMOTE 中的兩個參數，即P值和D值。確定P值是因為覆蓋內的樣本中，樣本數量較少的樣本很有可能是噪聲樣本或重疊樣本；D值則是用來衡量樣本的聚集程度，對于D值較小的覆蓋，這些樣本更有可能是噪聲或重疊樣本。

表3 和表4 中顯示了不同參數P和D對應的性能指標，最好的實驗結果以粗體顯示。表3 表明了參數P與CMOTE1 性能之間的關系。從實驗結果可以看出，當P=1 時，5 種評價指標，Precision、F-measure、G-mean、Recall和AUC（縮寫為P1、F1、G1、R1 和AU）在更多的數據集上可以獲得最優值，分別為：P1，8 個數據集；F1，11 個數據集；G1，8 個數據集；R1，10 個數據集；AU，7 個數據集。表4 給出了參數D與CMOTE2 性能之間的關系，當D≤0.1 時，5 種指標可以在大多數數據集上得到最優值，數據集數目分別為9、11、8、9、10。D≤0.1 的情況下，Recall在Y04 數據集上沒有得到最大值，但與最優性能之間只有0.4%的差距，可以忽略。因此，本文將P的值設為1，D的值設為0.1。

確定上述兩個參數后，可篩選出少數類中更容易被誤分的樣本，對這些關鍵樣本用SMOTE 方法進行過采樣。表5 給出了每個數據集在SMOTE 算法中特定的采樣比率N，其中第2 列和第4 列表示兩個不同閾值P和D下對應的采樣比率，即以每個關鍵樣本為種子需要擴充的少數類樣本個數。

4.4 實驗結果與分析

本實驗采用C4.5 決策樹[30]作為分類算法，該部分主要展示了本文提出的CMOTE算法與對比算法的實驗結果，并對算法的分類性能進行了分析。對于每一個算法，進行10次10折交叉驗證，取平均值作為平均性能。為了簡便起見，本節中列出了3 個重要指標F-measure、G-mean 以及AUC的對比結果。表6、表7給出了7 種算法在F-measure、G-mean 評價指標上的結果，最后一行給出了每種算法在12 個數據集上的平均值，最佳結果以粗體顯示。為了方便，將算法SMOTE、Borderline-SMOTE、SMOTE+TomekLin、ADASYN、MWMOTE、CMOTE1 和CMOTE2 分 別縮寫為SMO、B-SM、SM-T、ADAS、MWM、CSM1 和CSM2。

Table 3 Results of metrics corresponding to different P values表3 不同P 值對應的性能指標結果

Table 4 Results of metrics corresponding to different D values表4 不同D 值對應的性能指標結果

Table 5 Sampling rate corresponding to different P and D表5 兩個不同閾值P/D 對應的采樣率

Table 6 Experimental results on F-measure表6 指標F-measure上的實驗結果

Table 7 Experimental results on G-mean表7 指標G-mean 上的實驗結果

從表6、表7 可以看出，本文所提到的過采樣技術在F-measure、G-mean 指標上對大部分數據集都得到了有效的提高。例如，在F-measure 上，本文方法在12 個數據集中的9 個有最高的F-measure 值。與ADAS 算法相比，CSM1 和CSM2 在某些數據集上甚至有超過10 個百分點的提升。而對于G-mean，本文方法在12 個數據集中的7 個數據集上取得了最優值，與ADAS 算法相比，CSM1 和CSM2 的G-mean 分別提高了4.29 個百分點和4.50 個百分點。

AUC被認為能夠更好地衡量對少數類樣本的分類性能。圖3 給出了7 種算法在AUC上的結果，最后一組為AUC在12 個數據集上的平均值。從圖3 中可以看出與ADAS 算法相比，CSM1 和CSM2 的AUC上分別有明顯的提高。相對于性能較好的SM-T 算法，本文算法在大部分數據集（12 個數據集中的10 個）上的AUC都取得更優值。另外從平均的角度來看，本文提出的兩種過采樣技術的策略在F-measure 和Gmean 這兩種指標上都得到了明顯的改進。

Fig.3 Experiment result on AUC圖3 指標AUC 上的實驗結果

本文還對算法的性能進行了統計比較。圖4 和圖5 給出了CSM1 和CSM2 與其余5 種算法在每個指標上Welch t 檢驗的p值的實驗結果圖，細節如圖4和圖5 中子圖所示。總體上，對比算法的Recall、Fmeasure、G-mean 和AUC與CSM1 和CSM2 都有顯著差異。至于Precision，算法性能僅在幾種對比算法上與CSM1 和CSM2 有顯著差異（5 種算法中有2 種）。從實驗結果來看，CSM2 方法略優于CSM1 方法，CSM1有14個較好的結果，CSM2有18個較好的結果。說明了本文所提出的CMOTE 算法可以在大多數數據集上表現出最佳性能。

5 結論

Fig.4 Experiment result of Welch p between CSM1 and 5 algorithms圖4 CSM1 和5 種算法的Welch p 實驗結果

Fig.5 Experiment result of Welch p between CSM2 and 5 algorithms圖5 CSM2 和5 種算法的Welch p 實驗結果

作為一種典型的過采樣技術，SMOTE 及基于SMOTE 改進的方法受到了越來越多的關注。本文針對SMOTE 方法所存在的缺陷，引入了構造性覆蓋算法CCA 來選擇用于SMOTE 過采樣的關鍵少數類樣本。CCA 作為一種監督學習模型，能夠有效地檢測出對分類邊界影響較大的關鍵樣本。在12 個數據集上的實驗結果表明，在給定合適的參數下，CMOTE 算法的性能在不平衡數據分類方面于其他對比算法有了很大的提高。