孟東霞，李玉鑑

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

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

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

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

1 自然最近鄰

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

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

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

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

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

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

定義4（自然穩(wěn)定狀態(tài)）當(dāng)所有的樣本點(diǎn)都有逆近鄰或者逆近鄰個數(shù)為0的樣本點(diǎn)不變時，自然近鄰搜索過程到達(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 計(jì)算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 計(jì)算所有樣本的自然最近鄰，NNN( xi)=NN( xi)?RNN( xi)，輸出supk、NNN( xi)和NB( xi)。

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

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

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

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

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

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

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

定義7（直接密度可達(dá)）若樣本點(diǎn)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ù)類樣本的核心點(diǎn)集合C_set ，非核心點(diǎn)集合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，計(jì)算xi的鄰域半徑εi和直接密度可達(dá)的核心點(diǎn)集合DRi。

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

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

步驟3.1 計(jì)算xj的εj。

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

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

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

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

對少數(shù)類樣本完成聚類操作后，根據(jù)各類中的非核心點(diǎn)所占比例確定各個類需合成的樣本個數(shù)，類內(nèi)非核心點(diǎn)越多，需合成的新樣本越多。原因在于非核心點(diǎn)是自然近鄰數(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 計(jì)算類Ci中非核心點(diǎn)的比例ρi，按照比例大小確定類Ci需合成的樣本數(shù)

步驟5 在類Ci中隨機(jī)挑選非核心點(diǎn)x 和核心點(diǎn)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)，由于大量實(shí)驗(yàn)表明supk遠(yuǎn)小于nmin，一般在[1，30]之間，因此，該步驟的時間復(fù)雜度為O( nminlb nmin)。

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

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

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

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

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

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

3 實(shí)驗(yàn)

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

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

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

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

為了進(jìn)一步驗(yà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ù)類。所有樣本點(diǎn)的特征值都被縮放到[0，1]之間。采用五折交叉驗(yàn)證的方法將所有數(shù)據(jù)集分為訓(xùn)練集和測試集，取平均值作為實(shí)驗(yà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í)驗(yàn)所用數(shù)據(jù)集

本文選擇不平衡數(shù)據(jù)分類問題的常用評價指標(biāo)Fvalue、G-mean 和AUC 作為分類結(jié)果。其中，AUC 是ROC 曲線下各部分的面積之和，表示分類器將隨機(jī)測試的正實(shí)例排序高于隨機(jī)測試的負(fù)實(shí)例的概率，數(shù)值越大，分類性能越好。F-value 和G-mean 的計(jì)算過程由混淆矩陣構(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)示。

通過對比實(shí)驗(yàn)結(jié)果可以看出：

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

表4 SVM分類器實(shí)驗(yàn)效果對比

表5 KNN分類器實(shí)驗(yàn)效果對比

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