一種基于密度的SMOTE方法研究

王俊紅，段冰倩

非平衡數據的分類問題廣泛存在于電信詐騙檢測、醫療診斷、網絡入侵監控[1]、生物信息學、文本分類[2]、語言識別[3]、監測石油泄漏衛星圖像[4]等領域中，在這些實際應用中，很多數據的結構并不是理想化、均勻、平衡地分布。在非平衡數據分類過程中，由于正類樣本數量相對稀少，其所要表達的信息受到了限制，從而在分類時很難正確分析出數據的分布以及內部規律，導致少數類的分類精度降低，所以在分類過程中非平衡數據中少數類的數據稀少是導致分類性能下降的直接原因之一[5]。如何能夠在分類之前對數據進行預處理，彌補少數類樣本在分布信息方面不足的問題，以達到將數據平衡化的目的，從而提高分類器的性能，是非平衡數據學習過程中的重點所在。

在目前的研究中，用于解決非平衡數據分類問題的常用策略大致分為兩種，即數據層面的方法和算法層面的方法。算法層面的方法主要包括集成學習方法和代價敏感學習方法[6]；數據層面的方法主要思想是基于重采樣技術也就是對少數類樣本的過采樣和對多數類樣本的欠采樣。

作為數據層面的處理方法，重采樣方法簡單、直觀，倍受研究人員青睞[7-9]，在過采樣研究中，2002年Chawla提出的SMOTE[10](synthetic minority over-sampling technique)算法是其中的一個經典算法，現有很多算法都是在此原型的基礎上提出的。SMOTE算法在少數類樣本與其K個近鄰之間的連線上產生隨機的合成樣本，完成對少數類樣本的過采樣，提高了少數類樣本數量，使分類器更好地對未知少數類樣本進行預測，有效地提高了分類精度。但是，由于SMOTE算法無區分地對所有少數類樣本進行過采樣，在少數類極度稀缺時很容易造成過擬合。為了解決這一問題，文獻[11]提出了基于SMOTE的改進方法(adaptive SMOTE，ASMOTE)方法[11]，該方法根據樣本集內部實際分布特性，自適應地調整合成樣本產生過程中的近鄰選擇策略，避免了原始方法中樣本生成的盲目性，進而一定程度上提高了分類算法的準確率。在文獻[12]提出的Borderline-SMOTE方法中，改變了傳統的思路，認為邊界樣本具有更多的信息，通過查找出的“危險樣本”作為種子來產生新的合成樣本。在此基礎上，Haibo He等[13]對以上算法進行了改進，根據樣本的“危險”程度，也就是少數類樣本在學習中的難易程度，使用加權的方法，構造合成樣本的分布函數，來確定這些樣本合成新樣本的數目。

上述文獻中所涉及的采樣思想大多為基于線性距離，有一定的局限性，易受數據集中樣本分布結構的影響。本文提出了一種新的非平衡數據集處理方法——基于密度的重采樣算法DS-SMOTE，旨在識別任意形狀的簇，并且擴大“危險樣本”的范圍，對簇中的“稀疏樣本”進行重采樣，達到數據集的平衡。在本文實驗中，選擇了C4.5算法作為基準分類算法，C4.5算法是具有代表性的決策樹基準算法，在分類數據不平衡的情況下與同類分類器相比具有良好的分類性能，故選擇C4.5算法作為基準分類算法。

1 基于密度的過采樣方法

基于密度的方法能夠用于識別任意形狀的簇，如“S”形以及橢圓形簇[14]。為了更好地對非平衡數據集的分布進行刻畫，結合SMOTE的思想，本節提出一種基于密度的過采樣方法。

1.1 SMOTE算法

SMOTE[7]是過采樣方法中的經典算法。其主要思想基于k近鄰算法，對每個少數類樣本o，從它的k個最近鄰中隨機選擇一個樣本a，在o～a之間的連線上隨機產生合成樣本，一般地，取k=5[15]。

SMOTE過采樣方法通過對數據集中每一個少數類樣本隨機地選取k個最近鄰，并在該少數類樣本與其選取的最近鄰之間的連線上隨機產生合成樣本。在步驟1)中，通過獲取的過采樣比例以及少數類樣本的數量，產生新樣本數量；在步驟2)～5)中，循環遍歷每一個少數類樣本，獲取其k近鄰，并將其k近鄰的索引保存于數組nnarry中，作為合成新樣本的參數獲取新樣本，這里選取最近鄰個數k=5，例如：已知過采樣比例為300%，那么需要從每個少數類樣本的5個最近鄰中隨機選取3個樣本，作為合成新樣本的素材；其中Populate方法詳細介紹了合成樣本的產生過程。在步驟3)中，根據少數類樣本的屬性數以及新樣本的數量進行遍歷，步驟5)用于求得樣本間的歐式距離；在步驟8)中，根據公式，得到少數類樣本與其近鄰之間的合成樣本。新生成的樣本使得分類器能夠從學習過程中產生更大更抽象的決策邊界，有效地使少數類的決策邊界變得更加明顯，從而獲得更好的分類效果。

SMOTE算法

SMOTE(T, N, K)

輸入 少數類樣本數量T；過采樣百分比N%；樣本近鄰個數k；

輸出 (N/100)*T個少數類合成樣本。

1) N=(int)(N/100)；

2) for i=1:T

3) 計算第i個樣本的k個最近鄰, 其k近鄰的索引保存于nnarry中；

4) Populate(N, i, nnarry)；

5) endfor

Populate(N, i, nnarry)方法

1) While N～=0

2) 選擇1～k之間的隨機整數, 記為nn。隨機選擇第i個樣本的k近鄰中的一個近鄰。

3) for attr=1:numattrs

4) (numattrs為樣本的屬性個數)

5) dif = sample[nnarry[nn][attr]] – sample[i][attr]；

6) (sample[][]為原始少數類樣本集合)

7) gap=rand()；

8) synthetic[newinder][attr] = sample[i][attr] +gap*dif；

9) (newinder為合成樣本總量, 初始值為0)

10) endfor

11) newindex++；

12) N=N+1；

13) endwhile

1.2 Borderline-SMOTE算法

Borderline-SMOTE算法在SMOTE算法的基礎上進行了改進[12]。不同于SMOTE算法，Borderline-SMOTE算法避免了在過采樣過程中樣本選擇的隨機性，選擇類邊界樣本，作為種子樣本合成新樣本。在樣本空間中，如某一樣本周圍的鄰居樣本較多，則這個樣本較為稠密，就決策樹分類算法而言，產生的葉子節點——規則較多，容易產生過擬合問題，所以不宜在這個樣本與其近鄰之間添加新的樣本。Borderline-SMOTE算法嘗試著在訓練過程中盡量地去學習邊界特征，認為邊界樣本在分類中比遠離邊界的樣本更容易被錯分，一個類的邊界樣本攜帶了更多的信息，對分類器分類性能的好壞起到了決定性的作用。因此，在Borderline-SMOTE算法中，加入了識別邊界樣本的過程：若一個少數類樣本的m近鄰中，半數以上為多數類樣本，則認為這個樣本為容易被錯分的危險樣本；否則為安全樣本。在危險樣本與其k近鄰之間合成新樣本，完成對邊界少數類樣本的過采樣，以此加強少數類的決策邊界，以獲得好的分類結果。

1.3 基于密度的過采樣算法

設某類的樣本集合為S={si, i=1, 2, ···, n}，其中si為維數為m的樣本向量，樣本的維數代表其屬性的個數。一個類的對象o的密度是指靠近對象o的對象數量。

定義1 參數ε(ε＞0)為對象o的鄰域區域的半徑，即o的鄰域半徑。則一個對象o的ε-鄰域是指以o為圓心、以ε為半徑的空間，定義為

式中：D(si, o)為對象o以外的樣本si到對象o的距離，采用歐式距離方法計算[16]；θ為點o與si連線與水平軸之間的夾角。

定義2 對象o的ε-鄰域的密度是指對象o在ε-鄰域內的對象數量。

定義3 一個樣本數量為m的類在鄰域半徑為ε時，類中樣本的密度閾值Min Pts為類中樣本i的ε-鄰域密度Mi的均值。

為了確定對象o是否為稀疏點，即對象o的ε-鄰域是否稀疏，本文中使用參數Min Pts，作為稠密區域的密度閾值。如果一個對象o的ε-鄰域密度M≥Min Pts，則o為一個稠密對象，如果一個對象o的ε-鄰域密度M＜Min Pts，則o為一個稀疏對象。一個類中的稀疏對象構成此類的種子樣本集合(seeds)。

根據SMOTE算法思想，DS-SMOTE算法根據式（3）在種子樣本與其近鄰之間合成新樣本：

式中：o為目標對象，D(seedi, o)為種子樣本seedi與其近鄰樣本o之間的歐氏距離，r為隨機數，且r∈(0, 1)。

DS-SMOTE算法的核心思想為：在SMOTE算法的基礎上，在少數類中抽取種子樣本集合后對其進行過采樣。在算法中，我們對少數類中稀疏對象進行樣本采集得到一個種子樣本集合，產生種子集合的過程主要包括：計算少數類中樣本的鄰域半徑、計算該類的密度閾值、產生稀疏對象集合作為種子樣本集。DS-SMOTE算法產生的合成樣本分布于稀疏對象及其近鄰之間，最終得到與多數類樣本數量相等的少數類樣本集合。

DS-SMOTE算法

輸入 訓練集T, 原始樣本集合中多數類S1={x1, x2, ···, xmaj}、少數類集合S2= {y1, y2, ···, ymin}、鄰域半徑ε、密度閾值Min Pts。

1) 對于少數類集合S2, 在整個訓練集T中對S2中的每一個樣本yi計算其近鄰。若其近鄰類別都為多數類, 則認為yi為噪聲, 且不會出現在下一步計算中；

2) 選擇少數類集合S3, 執行ε= getE(S3)得到少數類鄰域半徑ε；

3) 求得鄰域半徑為ε時, 每個少數類樣本的密度；

4) for j = 1, |min|

5) 令 yi的 ε-鄰域密度=1；

6) for j = 1, |min|

7) 計算其他少數類樣本與樣本yi的歐式距離D；

8) if D＜=ε

9) yi的 ε-鄰域密度+1；

10) endfor

11) endfor

12) endfor

13) 根據式(2), 求得密度閾值Min Pts；

14) for j = 1, |min|

15) if yi的ε-鄰域密度≤密度閾值

16) yi為稀疏對象, 將yi加入種子樣本集合；

17) endfor

18) endfor

19) 產生種子集合seed；

20) 產生隨機數r；

21) 根據式(3)合成新樣本, 得到樣本集合new；

22) train = train∪new；

DS-SMOTE算法中，需要輸入非平衡數據集合T，以及參數鄰域半徑ε、密度閾值Min Pts。首先在步驟1)中，排除少數類中的噪聲產生新的少數類集合，S3；在步驟2)中，算法選取了少數類樣本集合S3進行操作，根據密度的概念：對象o的ε-鄰域密度是指對象o在ε-鄰域內的對象數量，遍歷每個少數類樣本求得其ε-鄰域的密度，并在步驟3)～12)中取少數類樣本密度的均值作為判斷少數類集合中樣本是否稠密的密度閾值。

如何排除人工的方法，為少數類設置恰當的鄰域半徑是基于密度的分類算法中的一個亟待解決的問題。本文選擇非平衡類分類中一般性的評估標準：F-value以及G-mean值進行評估，經實驗分析，選擇類內樣本間平均距離作為鄰域半徑。表1與表2分別隨機選取5個數據集進行實驗分析，選取了鄰近樣本間平均距離ε′值的一系列大于零的點，如 ε′*0.3、ε′*0.5、ε′*0.7 以及 ε′*1.3、ε′*1.5、ε′*1.7進行測試。經過測試，在圖1與圖2中可看出，結果呈現出一定的規律性：ε值的變化對不同的數據集的影響不盡相同，在ε值等于ε′或鄰近取值時F-value以及G-mean值水平較高，隨著取值向ε′的兩側遠離，F-value以及G-mean值或保持平穩，或有所下降。說明選取類內樣本間平均距離作為鄰域半徑具有一定的普適性，并且對分類器的分類性能有一定的保證。由于其脫離了人工選擇的鄰域半徑設置方法，所以這種鄰域半徑的設置方法也提高了DS-SMOTE方法的可操作性。

表1 不同鄰域半徑取值下的G-mean值Table 1 The G-mean under different neighborhood radius

表2 不同鄰域半徑取值下的F-value值Table 2 The F-value under different neighborhood radius

圖1 不同鄰域半徑取值下的G-mean值Fig. 1 The G-mean under different neighborhood radius

圖2 不同鄰域半徑取值下的F-value值Fig. 2 The F-value under different neighborhood radius

在步驟14)～18)中，使用循環遍歷的方式判斷少數類樣本的稀疏性，并將稀疏樣本加入種子集合，作為在步驟21)中合成新樣本的素材。在步驟21)中引用了直觀、易操作的SMOTE算法的思想產生合成樣本，一定程度上避免了隨機過采樣方法容易造成的分類器過擬合問題，最終在稀疏對象及其近鄰之間合成新樣本，達到少數類與多數類樣本在數量上的一致。

2 實驗與結果分析

2.1 評價標準

一個分類器算法在二分類問題中的性能往往使用混淆矩陣來評估，分別將兩類分為正類（positive）、負類(negative)，如表3所示[17]。混淆矩陣的列用來表示類的預測結果，混淆矩陣的行用來表示類的實際類別[18]。其中，TN (true negative)表示負類樣本中被劃分正確的樣本數，即真負類；TP(true positive)表示正類樣本中被劃分正確的樣本數，即真正類；FN(false negative)表示負類樣本中被劃分錯誤的樣本數，也就是負類中的樣本被劃分為正類的樣本數，即假負類；FP(flase positive)表示正類樣本中被劃分錯誤的樣本數，也就是正類中的樣本被劃分為負類的樣本數，即假正類[19]。

表3 二分類問題中的含混矩陣Table 3 The confusion matrix of 2-class problem

準確率(Precision)和召回率(Recall)是分類性能的兩個最基本的指標[20]。準確率(Precision)也稱為查準率，召回率(Recall)也稱為查全率，即正類（少數類）的分類準確率。定義為

F-value是準確率和召回率的調和平均，實驗中令β值為1，即F1度量。定義如下：（式中β為調整準確率(Precision)和召回率(Recall)所占比重的參數，一般地令 β=1）。

在非平衡類分類問題中，G-mean值用來衡量分類器對于兩類樣本分類的平均性能[21]，是對算法性能的總體評價。

本文選用 Recall(TPR)、TNR、Precision、F-value、G-mean等值作為實驗過程中算法性能指標的度量。

2.2 實驗數據

為了測試文中實現的采樣方法與同類方法對非平衡數據的分類效果，文中采用了11個UCI數據集進行實驗和分析，如表4所示。非平衡數據中的非平衡度為正類與負類樣本數量之比，實驗中所選取的數據集分別具有不同的非平衡程度，正類的比例從0.097～0.629不等。這些數據集中的數據大多為數值型的兩類樣本數據，其中，statimage數據集中的樣本有7個類別，為了構造極其不平衡的樣本集合，人為將第4類樣本作為少數類樣本，其余樣本合為一類作為多數類樣本，從而得到一組非平衡度為0.097的兩類數據樣本；thyroid數據集中具備3類樣本，通過將類別為2和3的樣本合為一類，從而獲得了一組非平衡度為0.194的兩類數據樣本。表4同時給出了各數據集的屬性個數、總樣本數量、正類樣本數量、負類樣本數量以及正負類樣本數量的比值——非平衡度。

表4 實驗所用UCI數據集Table 4 The UCI datasets for experiments

2.3 實驗結果與分析

為了驗證DS-SMOTE算法處理非平衡數據集的有效性，C4.5算法是具有代表性的決策樹基準算法，在分類數據不平衡的情況下與同類分類器相比具有良好的分類性能，實驗中采用了C4.5算法作為分類算法，并與SMOTE算法、Borderline-SMOTE算法進行了對比。本文采用了十折交叉驗證方法進行實驗測試，測試結果均為10次實驗均值，并針對Recall(TPR)、TNR、Precision、F-value、G-mean等指標進行分析。

為了對比算法的優勢，圖3～7分別繪制了4種算法策略在11個數據集上的測試結果趨勢曲線。其中，橫坐標為4種算法策略，縱坐標取值在0～1之間，表中加粗的數據為一系列數據中的最大值。通過以下圖表可以看出，使用DS-SMOTE方法進行過采樣，少數類的分類性能有所上升。

圖3 少數類準確率變化曲線圖Fig. 3 The variation curve for TPR of min

圖4 多數類準確率變化曲線圖Fig. 4 The variation curve for TNR of major

圖5 準確率變化曲線圖Fig. 5 The variation curve of precision

在表5中，大部分數據集在DS-SMOTE算法處理后分類的TNR值大于使用SMOTE算法與Borderline-SMOTE算法，對于少數類樣本絕對稀少、非平衡程度較大的數據集statimage 、thyroid和parkinsons分類效果較差，表明在處理少數類絕對稀少的非平衡類分類問題中，DS-SMOTE算法仍有待改進；表6中多數類樣本的分類精度保持較高，可見DS-SMOTE算法在保證多數類分類準確率的前提下對少數類的分類準確率有一定程度的改善；在表7和8中可以觀察到，DS-SMOTE沒有消除在兩類的極端不平衡時對Precision、F-value值的影響；G-mean值作為非平衡數據整體分類性能的評價指標，往往能夠指示一個方法在非平衡數據集的分類性能好壞，表9顯示出DS-SMOTE算法在大部分的數據集上的G-mean值有顯著的優勢，說明本文提出的算法在這些數據集上有較好的總體分類性能。

圖6 F-value變化曲線圖Fig. 6 The variation curve of F-value

圖7 G-mean變化曲線圖Fig. 7 The variation curve of G-mean

表5 少數類準確率Table 5 The TPR of min

表6 多數類準確率Table 6 The TNR of Major

表7 準確率Table 7 Precision

表8 F-valueTable 8 F-value

表9 G-meanTable 9 G-mean

實驗結果表明本文提出的算法在少數類信息不足的情況下，分類效果有一定程度的改進，能夠在不降低多數類分類精度的同時，保證分類器對少數類的識別，并具有良好的適應性。

3 結束語

基于數據采樣的方法是解決非平衡數據分類問題的一個重要途徑，本文在SMOTE算法的基礎上，結合密度的概念，提出了基于密度的過采樣方法，以提高非平衡數據分類的準確率。實驗結果表明，本文的方法在處理非平衡數據分類問題上具有良好的效果。另外，在本文中使用類內樣本間平均距離作為鄰域半徑，通過實驗證明，這種取值方法避免了人工取值的難題，具有普適性和可操作性，也使得分類器的分類性能得到了一定的保證。但是，如何通過自適應方法產生類的鄰域半徑，是本文進一步的研究方向。

[1]CHARTE F, RIVERA A J, JESUS M J D, et al. Addressing imbalance in multilabel classification: Measures and random resampling algorithms[J]. Neurocomputing, 2015, 163:3–16.

[2]RADIVOJAC P, CHAWLA N V, DUNKER A K, et al.Classification and knowledge discovery in protein databases[J]. Journal of biomedical informatics, 2004, 37(4):224–239.

[3]LIU Y, CHAWLA N V, HARPER M P, et al. A study in machine learning from imbalanced data for sentence bound-ary detection in speech[J]. Computer speech and language,2006, 20(4): 468–494.

[4]KUBAT M, HOLTE R C, MATWIN S. Machine learning for the detection of oil spills in satellite radar images[J]. Machine learning, 1998, 30(2): 195–215.

[5]QIAN H, HE G. A survey of class-imbalanced data classification[J]. Computer engineering and science, 2010, 5: 025.

[6]翟云, 王樹鵬, 馬楠,等. 基于單邊選擇鏈和樣本分布密度融合機制的非平衡數據挖掘方法[J]. 電子學報, 2014,42(7): 1311–1319.ZHAI Yun, WANG Shupeng, MA Nan, et al. A data mining method for imbalanced datasets based on one-side link and distribution density of instances[J]. Chinise journal of electronics, 2014, 42(7): 1311–1319.

[7]CHARTE F, RIVERA A J, JESUS M J D, et al. Addressing imbalance in multilabel classification: Measures and random resampling algorithms[J]. Neurocomputing, 2015, 163:3–16.

[8]GONG C, GU L. A novel smote-based classification approach to online data imbalance problem[J]. Mathematical problems in engineering, 2016, 35: 1–14.

[9]BIAN J, PENG X G, WANG Y, et al. An efficient costsensitive feature selection using chaos genetic algorithm for class imbalance problem[J]. Mathematical problems in engineering, 2016, 6: 1–9.

[10]CHAWLA N V, BOWYER K W, HALL L O, et al.SMOTE: synthetic minority over-sampling technique[J].Journal of artificial intelligence research, 2002, 16(1):321–357.

[11]楊智明, 喬立巖, 彭喜元. 基于改進SMOTE的不平衡數據挖掘方法研究[J]. 電子學報, 2007, 35(B12): 22–26.YANG Zhimin, QIAO Liyan, PENG Xiyuan. Research on datamining method for imbalanced dataset based on improved SMOTE[J]. Chinese journal of electronics, 2007,35(B12): 22–26.

[12]HAN H, WANG W Y, MAO B H. Borderline-SMOTE: a new over-sampling method in imbalanced data sets learning[C]//International Conference on Intelligent Computing.Springer Berlin Heidelberg, 2005, 3644(5): 878-887.

[13]HE H, BAI Y, GARCIA E A, et al. ADASYN: Adaptive synthetic sampling approach for imbalanced learning[C]//IEEE International Joint Conference on Neural Networks.IEEE Xplore, 2008: 1322-1328.

[14]GRZYMALA-BUSSE J W, STEFANOWSKI J, WILK S.A comparison of two approaches to data mining from imbalanced data[J]. Journal of intelligent manufacturing,2005, 16(6): 565–573.

[15]EZ J, KRAWCZYK B, NIAK M. Analyzing the oversampling of different classes and types of examples in multi-class imbalanced datasets[J]. Pattern recognition,2016, 57(C): 164–178.

[16]NANNI L, FANTOZZI C, LAZZARINI N. Coupling different methods for overcoming the class imbalance problem[J]. Neurocomputing, 2015, 158(C): 48–61.

[17]NAGANJANEYULU S, KUPPA M R. A novel framework for class imbalance learning using intelligent undersampling[J]. Progress in artificial intelligence, 2013, 2(1):73–84.

[18]ZHANG X, SONG Q, WANG G, et al. A dissimilaritybased imbalance data classification algorithm[J]. Applied intelligence, 2015, 42(3): 544–565.

[19]JIANG K, LU J, XIA K. A novel algorithm for imbalance data classification based on genetic algorithm improved SMOTE[J]. Arabian journal for science and engineering,2016, 41(8): 3255–3266.

[20]XU Y, YANG Z, ZHANG Y, et al. A maximum margin and minimum volume hyper-spheres machine with pinball loss for imbalanced data classification[J]. Knowledgebased systems, 2016, 95: 75–85.

[21]ANWAR N, JONES G, GANESH S. Measurement of data complexity for classification problems with unbalanced data[J]. Statistical analysis and data mining the asa data science journal, 2014, 7(3): 194–211.