利用自然最近鄰的不平衡數(shù)據(jù)過采樣方法

孟東霞，李玉鑑

1.河北金融學(xué)院 金融科技學(xué)院，河北 保定071051

2.桂林電子科技大學(xué) 人工智能學(xué)院，廣西 桂林541004

在不平衡數(shù)據(jù)中，各類別樣本的數(shù)量存在較大差異，樣本數(shù)量較多的類被稱為多數(shù)類，樣本數(shù)量較少的是少數(shù)類。不平衡數(shù)據(jù)集在信用風(fēng)險評估、欺詐檢測、疾病診斷、氣象預(yù)測等應(yīng)用領(lǐng)域中廣泛存在，其中的少數(shù)類樣本是識別的重點，若被誤分類將帶來重大的損失。以信用評估問題為例，信用差的客戶樣本相對較少，傳統(tǒng)分類算法在對其進(jìn)行分類時，側(cè)重于考慮整體分類準(zhǔn)確率，易造成少數(shù)類的誤判，導(dǎo)致少數(shù)類的信用差的客戶被誤分為好客戶的錯誤率較高，若給其撥付貸款，將給企業(yè)造成極大的資金損失。因此，有效提高不平衡數(shù)據(jù)集的分類性能是目前的研究熱點。

目前，針對不平衡數(shù)據(jù)的研究主要有算法層面和數(shù)據(jù)層面兩種思路：算法層面主要通過引入誤分類代價、集成學(xué)習(xí)等手段使分類算法更側(cè)重于少數(shù)類，包括代價敏感學(xué)習(xí)方法、提升算法和集成算法；在數(shù)據(jù)層面上，常用過采樣、欠采樣和混合采樣三種方式改善樣本分布，再對獲得平衡的數(shù)據(jù)集進(jìn)行分類。過采樣通過某些策略增加少數(shù)類樣本的個數(shù)；欠采樣通過剔除部分多數(shù)類樣本，減少多數(shù)類樣本的個數(shù)；混合采樣將過采樣和欠采樣相結(jié)合使各類樣本數(shù)量接近。本文將從數(shù)據(jù)層面通過增加少數(shù)類樣本的數(shù)量對不平衡數(shù)據(jù)進(jìn)行處理。

隨機(jī)復(fù)制少數(shù)類樣本雖然能快速直接地增加樣本數(shù)量，但實際效果不夠理想，易產(chǎn)生過擬合[1]。SMOTE算法（Synthetic Minority Over-sampling Technique）是目前最為典型的過采樣方法，其通過對少數(shù)類樣本和K個近鄰插值合成新樣本，以增加少數(shù)類樣本的數(shù)量[2]。SMOTE算法雖然在一定程度上改善了少數(shù)類樣本的分類性能，但是未考慮到少數(shù)類樣本類內(nèi)不平衡的情況，易引入噪聲點。Borderline-SMOTE（Borderline Synthetic Minority Over-sampling Technology）根據(jù)少數(shù)類樣本點周邊的近鄰分布，將其分為safe（近鄰均為少數(shù)類樣本）、danger（近鄰中包含少數(shù)類和多數(shù)類樣本）和noise（近鄰均為多數(shù)類樣本）三種類型，只選取danger樣本利用SMOTE 算法合成新樣本，通過強化邊界點的影響力來提高分類性能[3]?；诰垲惖倪^采樣方法先對少類樣本進(jìn)行聚類，然后在每個類簇中生成特定數(shù)量的新樣本，避免生成跨越邊界的噪聲點，聚類方法包括Kmeans聚類[4]、層次聚類[5]等策略。帶多數(shù)類權(quán)重的過采樣方法根據(jù)少數(shù)類和多數(shù)類樣本的距離信息，識別出難以學(xué)習(xí)的、加權(quán)信息量較大的少數(shù)類樣本，結(jié)合其所屬的少數(shù)類類簇合成新樣本，有效減少了重疊新樣本的生成[6]。周等人提出的基于樣本分層的雙向過采樣方法基于最高密度點和類內(nèi)距離將少類樣本分為密集層和稀疏層，在兩者之間進(jìn)行雙向過采樣，避免了采樣后類內(nèi)樣本分布不均的問題[7]?？紤]到支持向量對分類超平面的影響，基于支持向量的過采樣方法在利用支持向量機(jī)訓(xùn)練完數(shù)據(jù)集后，使用支持向量生成新的少數(shù)類樣本[8]。針對少數(shù)類樣本可能存在的類內(nèi)不平衡和新生成樣本的重疊問題，本文基于自然最近鄰的定義和分布特征設(shè)計了一種結(jié)合少數(shù)類樣本自然近鄰關(guān)系和內(nèi)部類簇信息進(jìn)行過采樣的不平衡數(shù)據(jù)處理方法。所提方法首先根據(jù)自然最近鄰的定義計算少數(shù)類樣本的自然最近鄰，獲得處于樣本分布密集區(qū)域中的核心點，然后基于自然近鄰關(guān)系對少數(shù)類樣本進(jìn)行聚類，最后利用同類中的核心點和非核心點合成新樣本。

1 自然最近鄰

自然最近鄰是近年來提出的最近鄰概念，其在離群點檢測[9-10]、數(shù)據(jù)聚類[11-12]和協(xié)同過濾[13]等領(lǐng)域中的應(yīng)用具有良好的表現(xiàn)，其考慮到了樣本分布疏密程度對近鄰個數(shù)和對稱關(guān)系的影響，即密集區(qū)中的樣本點擁有較多的自然近鄰，稀疏區(qū)的樣本點近鄰較少，離群樣本點和噪聲點的近鄰相對很少甚至為0。自然近鄰的搜索無需人工指定參數(shù)，根據(jù)每個點的分布特征自適應(yīng)生成，當(dāng)所有樣本點都有逆近鄰或逆近鄰個數(shù)為0 的所有樣本不變時結(jié)束，達(dá)到自然穩(wěn)定狀態(tài)[14]。

假設(shè)有數(shù)據(jù)集X={ x1,x2,…,xn} 。

定義1（最近鄰）NNr( xi)表示樣本點xi的r 最近鄰，r 由自然最近鄰搜索算法自動產(chǎn)生。

定義2（逆近鄰） RNNr( xi)表示樣本點xi的r 逆最近鄰：

定義3（自然最近鄰） NNN( xi)表示樣本點xi的自然最近鄰：

由定義3 得出，自然最近鄰是一種對稱的鄰居關(guān)系，即樣本點xi和xj互為彼此的r 近鄰。

定義4（自然穩(wěn)定狀態(tài)）當(dāng)所有的樣本點都有逆近鄰或者逆近鄰個數(shù)為0的樣本點不變時，自然近鄰搜索過程到達(dá)自然穩(wěn)定狀態(tài)。到達(dá)自然穩(wěn)定狀態(tài)時的搜索次數(shù)稱為自然特征值，記為supk。

算法1描述了自然最近鄰搜索算法的具體步驟。

算法1 自然最近鄰搜索算法

輸入：數(shù)據(jù)集X 。

輸出：supk,NNN( xi)，自然近鄰數(shù)NB( xi)。

步驟1 初始化搜索次數(shù)r=1,NB( xi)=0,NN( xi)=?,逆近鄰RNN( xi)=?。

步驟2 計算xi的r 近鄰，更新NB( xi)、NN( xi)、RNN( xi)。

步驟3 r=r+1。

步驟4 當(dāng)所有xi的RNN( xi)≠?或{xi|RNN( xi)=?} 不再變化時，搜索過程到達(dá)自然穩(wěn)定狀態(tài)，supk=r-1，否則轉(zhuǎn)至步驟2。

步驟5 計算所有樣本的自然最近鄰，NNN( xi)=NN( xi)?RNN( xi)，輸出supk、NNN( xi)和NB( xi)。

通過算法1 可以看出自然特征值supk是所有樣本的自然鄰居數(shù)量的平均值，自然鄰居數(shù)大于等于supk的樣本點位于樣本分布密集區(qū)，其余樣本點的分布較為稀疏。

2 基于自然最近鄰的過采樣方法

針對少數(shù)類樣本類內(nèi)不平衡、新生成樣本存在噪聲和重疊的問題，本文設(shè)計了一種結(jié)合少數(shù)類樣本的自然近鄰關(guān)系和所屬內(nèi)部類簇進(jìn)行過采樣的不平衡數(shù)據(jù)處理方法。所提方法首先根據(jù)自然最近鄰的定義計算少數(shù)類樣本的自然最近鄰，獲得處于樣本分布密集區(qū)域中的核心點，然后基于自然近鄰關(guān)系對少數(shù)類樣本進(jìn)行聚類，最后利用同類中的核心點和非核心點合成新樣本。

2.1 少數(shù)類基于自然最近鄰的聚類

依據(jù)算法1 對少數(shù)類樣本完成自然最近鄰的搜索過程后，參考文獻(xiàn)[15]基于自然近鄰關(guān)系對少數(shù)類樣本進(jìn)行密度聚類，過程主要包括三個步驟：首先根據(jù)所有少數(shù)類樣本的自然近鄰關(guān)系確定核心點；計算核心點的自身鄰域半徑，確定與其密度直達(dá)的核心點，依據(jù)密度聚類的過程對核心點聚類，將互相處于自身鄰域半徑值范圍內(nèi)的兩個核心點歸為同一類；依據(jù)非核心點和核心點的近鄰關(guān)系，將非核心點劃歸到現(xiàn)有分類中。

定義5（核心點）對于xi∈X ，若滿足NB(xi) ≥則稱xi為核心點。核心點的自然近鄰數(shù)NB( xi)不小于自然特征值supk，且大于其所有自然近鄰的自然近鄰數(shù)的平均值，位于樣本分布的密集區(qū)域中。

定義6（鄰域半徑） xi的鄰域半徑εi是xi到所有自然近鄰的最大距離，即

定義7（直接密度可達(dá)）若樣本點xi與xj之間的距離D( xi,xj)滿足D( xi,xj)≤εi和D( xi,xj)≤εj，則稱xi與xj直接密度可達(dá)。

密度相連、密度可達(dá)的定義與密度聚類算法中的定義相同。

算法2 少數(shù)類基于自然最近鄰的聚類算法

輸入：少數(shù)類樣本的supk，NNN( xi)和NB( xi)。

輸出：少數(shù)類樣本的核心點集合C_set ，非核心點集合NC_set，聚類個數(shù)K 和各類簇的樣本集合CK。

步驟1 根據(jù)定義5，由supk、NNN( xi)和NB( xi)確定C_set 和NC_set。

步驟2 對xi聚類，xi∈Cset。

步驟2.1 根據(jù)定義6 和7，計算xi的鄰域半徑εi和直接密度可達(dá)的核心點集合DRi。

步驟2.2 利用εi和DRi，參照密度聚類的流程，將所有密度相連的核心點歸入同一個類簇，得到CK和K。

步驟3 將xj劃分到K 類中，xj∈NCset。

步驟3.1 計算xj的εj。

步驟3.2 得到與xj互為自然近鄰且彼此互在對方鄰域半徑內(nèi)的所有核心點。

步驟3.3 確定距離xj最近的核心點xi，將xj加入xi所在的類簇中；若不存在這樣的核心點，則將xj標(biāo)記為噪聲點。

新樣本由屬于同一類簇中的核心點和非核心點生成，噪聲點不參與樣本點的合成，可避免引入新的噪聲點。

2.2 基于自然最近鄰的過采樣方法

對少數(shù)類樣本完成聚類操作后，根據(jù)各類中的非核心點所占比例確定各個類需合成的樣本個數(shù)，類內(nèi)非核心點越多，需合成的新樣本越多。原因在于非核心點是自然近鄰數(shù)小于自然特征值的樣本，其周圍的樣本分布較為稀疏，在其內(nèi)部更多地合成新樣本，可避免新樣本過多地集中于分布密集的區(qū)域中，減少了合成樣本的重疊。算法3 描述了基于自然最近鄰進(jìn)行過采樣的具體步驟，流程圖如圖1所示。

算法3 基于自然最近鄰的過采樣方法

輸入：不平衡數(shù)據(jù)集S。

輸出：過采樣生成的少數(shù)類樣本集合Sgen。

步驟1 使用算法1 對少數(shù)類樣本進(jìn)行自然最近鄰的搜索，得到supk、NNN( xi)和NB( xi)。

步驟2 根據(jù)算法2 對少數(shù)類樣本進(jìn)行聚類，得到K、CK、C_set、NC_set。

步驟3 新合成的樣本數(shù)N=多數(shù)類樣本數(shù)-少數(shù)類樣本數(shù)。

步驟4 計算類Ci中非核心點的比例ρi，按照比例大小確定類Ci需合成的樣本數(shù)

步驟5 在類Ci中隨機(jī)挑選非核心點x 和核心點y合成新樣本，i=1,2,…,K 。 z=x+a×( y-x )，a 是[0，1]之間的隨機(jī)數(shù)，將z 加入集合Sgen。重復(fù)進(jìn)行此步驟直到各類獲得所需樣本數(shù)。

Sgen即為合成的少數(shù)類樣本集合。

2.3 算法時間復(fù)雜度分析

假設(shè)在不平衡數(shù)據(jù)集中，少數(shù)類樣本個數(shù)為nmin，多數(shù)類樣本個數(shù)為nmax。本文方法的時間復(fù)雜度由以下主要步驟決定：

圖1 基于自然最近鄰過采樣方法的流程圖

（1）搜索所有少數(shù)類樣本的自然最近鄰：①創(chuàng)建可用于存儲數(shù)據(jù)的KD 樹，時間復(fù)雜度為O( nminlb nmin)；②每一輪搜索自然最近鄰，時間復(fù)雜度為O( nminlb nmin)，共進(jìn)行supk輪，時間復(fù)雜度為O( supk×nminlb nmin)，由于大量實驗表明supk遠(yuǎn)小于nmin，一般在[1，30]之間，因此，該步驟的時間復(fù)雜度為O( nminlb nmin)。

（2）對少數(shù)類樣本進(jìn)行聚類：①依據(jù)定義5，將樣本分為核心點和非核心點，時間復(fù)雜度為O( nmin×supk)，由于supk遠(yuǎn)小于nmin，可記為O( nmin)；②使用密度聚類對核心點聚類，假設(shè)核心點數(shù)量為nmin_c，使用KD樹加快索引，時間復(fù)雜度為O( nmin_clb nmin_c)；③將非核心點劃分到K 類中，假設(shè)非核心點數(shù)量為nmin_nc，通過之前保存的自然近鄰信息，時間復(fù)雜度為O( nmin_nc)。該步驟的時間復(fù)雜度為O( nmin+nmin_clb nmin_c)。

（3）在各類簇中合成新樣本：①計算各類簇的新生成樣本數(shù)，時間復(fù)雜度為O( K )；②在各類簇中生成新樣本，時間復(fù)雜度為O( N )，N=nmax-nmin，為新生成樣本數(shù)。該步驟時間復(fù)雜度為O( N )。

將上述步驟的時間復(fù)雜度相加并化簡，得到本文方法的時間復(fù)雜度為O( nminlb nmin+nmax)。

實驗部分用到的SMOTE、Borderline-SMOTE 和SVM過采樣方法的時間復(fù)雜度如表1所示。

表1 其他方法的時間復(fù)雜度

通過對比可以看出本文方法的時間復(fù)雜度與SMOTE 和Borderline-SMOTE 基本接近，優(yōu)于SVM 過采樣方法，證明了本文方法的有效性。

3 實驗

3.1 人工數(shù)據(jù)集

為了驗證本文所提方法的有效性，構(gòu)造人工數(shù)據(jù)集比較不同過采樣方法新生成樣本的分布情況。假設(shè)所構(gòu)造的數(shù)據(jù)樣本點為( xi,yi)，其中xi是二維特征，其在兩個維度上均服從均勻分布，yi是類標(biāo)簽。在圖2 中，多數(shù)類由實心點表示，少數(shù)類是X 形，新生成的少數(shù)類樣本由方塊形表示，其數(shù)量是多數(shù)類樣本和少數(shù)類樣本的差值。在算法實現(xiàn)上，SMOTE 和Borderline-SMOTE方法使用的是Python庫imbalance-learn package中的程序，所提方法使用python語言編寫完成。

圖2 給出了不同過采樣方法合成新樣本的分布圖。圖2（a）中是數(shù)據(jù)的原始分布情況，多數(shù)類中包含少量的少數(shù)類樣本噪聲點；圖2（b）和（c）分別是采用SMOTE 和Borderline-SMOTE 方法合成的樣本分布情況；圖2（d）展示了本文方法所合成的新樣本分布情況。通過對比可以看出，本文方法引入了較少的噪聲點，生成的新樣本較為均勻地分布在少數(shù)類的兩個類簇中，重疊樣本較少。

3.2 UCI數(shù)據(jù)集

為了進(jìn)一步驗證本文方法的有效性，利用SMOTE、Borderline-SMOTE、SVM過采樣方法和本文方法對9組UCI數(shù)據(jù)集進(jìn)行少數(shù)類樣本的過采樣處理，再使用支持向量機(jī)和KNN對采樣后的數(shù)據(jù)進(jìn)行分類。數(shù)據(jù)集信息如表2所示，不平衡率是少數(shù)類樣本數(shù)量和多數(shù)類樣本數(shù)量的比值。對于多類數(shù)據(jù)集，將其中一類設(shè)置為少數(shù)類，其余類合并為多數(shù)類。所有樣本點的特征值都被縮放到[0，1]之間。采用五折交叉驗證的方法將所有數(shù)據(jù)集分為訓(xùn)練集和測試集，取平均值作為實驗結(jié)果。本文所提方法使用Python 語言編寫，SMOTE、Borderline-SMOTE和SVM過采樣方法使用的是Python庫imbalancelearn package 中的代碼。支持向量機(jī)、KNN 都使用Python庫scikit-learn中的代碼，SVM的核函數(shù)采用高斯核，KNN的近鄰數(shù)量設(shè)置為5。

圖2 不同過采樣方法在人工數(shù)據(jù)集上的合成樣本分布圖

表2 實驗所用數(shù)據(jù)集

本文選擇不平衡數(shù)據(jù)分類問題的常用評價指標(biāo)Fvalue、G-mean 和AUC 作為分類結(jié)果。其中，AUC 是ROC 曲線下各部分的面積之和，表示分類器將隨機(jī)測試的正實例排序高于隨機(jī)測試的負(fù)實例的概率，數(shù)值越大，分類性能越好。F-value 和G-mean 的計算過程由混淆矩陣構(gòu)造得到?；煜仃嚨亩x如表3所示。

表3 混淆矩陣

F-value：

G-mean：

G-mean 同時考慮了多數(shù)類和少數(shù)類的分類準(zhǔn)確率，可用于衡量整體分類效果。

表4和表5給出了不同過采樣方法處理后分別使用SVM、KNN 分類后得到的F-value、G-mean 和AUC 值，取得最優(yōu)的數(shù)據(jù)使用黑色粗體標(biāo)示。對每個評價指標(biāo)，將四種不平衡處理方法在同一個分類器中得到的數(shù)值按照最優(yōu)到最差排序，最優(yōu)的序號為1，依次遞增，在表格的最后一行給出四種方法在所有數(shù)據(jù)集中的平均排名，最佳排名使用黑色粗體標(biāo)示。

通過對比實驗結(jié)果可以看出：

（1）平均值排名。相較于SMOTE、Borderline-SMOTE和SVM 過采樣方法，在本文方法處理得到的平衡數(shù)據(jù)集上，SVM、KNN 分類器都獲得了較好的分類性能，指標(biāo)F-value、G-mean 和AUC 的平均值排名都是最佳，證明所提方法對處理不平衡數(shù)據(jù)具有明顯的優(yōu)勢。

表4 SVM分類器實驗效果對比

表5 KNN分類器實驗效果對比

（2）F-value。在SVM的分類結(jié)果中，本文方法在所有數(shù)據(jù)集上都取得了最優(yōu)值。在KNN 的分類結(jié)果中，本文方法在六個數(shù)據(jù)集中獲得最優(yōu)值，在數(shù)據(jù)集Letter、Glass7和Yeast4中的結(jié)果略低于最優(yōu)值?？傮w來看，本文方法有效提高了少數(shù)類樣本的分類準(zhǔn)確率。

（3）G-mean 和AUC 值。在分類器SVM 和KNN 的分類結(jié)果中，本文方法在大多數(shù)數(shù)據(jù)集中都取得了最優(yōu)值，證明所提方法改善了不平衡數(shù)據(jù)的整體分類性能。

（4）在數(shù)據(jù)集Glass3、Ecoli3、Vehicle1和Herbman上，本文方法同時取得了最優(yōu)的F-value、G-mean和AUC值。

（5）原因在于本文方法考慮到了少數(shù)類樣本中存在的類內(nèi)不平衡問題，而其他方法未考慮到樣本內(nèi)部分布情況。

4 結(jié)束語

本文提出了一種基于自然最近鄰過采樣的數(shù)據(jù)處理方法。該方法首先計算所有少數(shù)類樣本的自然最近鄰，獲得位于樣本分布密集區(qū)域中的核心點，然后基于自然近鄰關(guān)系對少數(shù)類樣本進(jìn)行密度聚類，最后選擇同一類簇中的核心點和分布于稀疏區(qū)中的非核心點生成新樣本。在人工數(shù)據(jù)集和UCI 數(shù)據(jù)集上開展的對比實驗證明所提方法減少了噪聲點和重疊樣本的引入，有效提高了不平衡數(shù)據(jù)的分類性能。為了使新生成的樣本更能體現(xiàn)少數(shù)類樣本的分布特征，改進(jìn)代表點的選擇和合成策略將是進(jìn)一步的研究方向。