利用自然最近鄰的不平衡數據過采樣方法

孟東霞，李玉鑑

1.河北金融學院 金融科技學院，河北 保定071051

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

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

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

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

1 自然最近鄰

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

假設有數據集X={ x1,x2,…,xn} 。

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

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

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

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

定義4（自然穩定狀態）當所有的樣本點都有逆近鄰或者逆近鄰個數為0的樣本點不變時，自然近鄰搜索過程到達自然穩定狀態。到達自然穩定狀態時的搜索次數稱為自然特征值，記為supk。

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

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

輸入：數據集X 。

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

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

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

步驟3 r=r+1。

步驟4 當所有xi的RNN( xi)≠?或{xi|RNN( xi)=?} 不再變化時，搜索過程到達自然穩定狀態，supk=r-1，否則轉至步驟2。

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

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

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

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

2.1 少數類基于自然最近鄰的聚類

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

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

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

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

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

算法2 少數類基于自然最近鄰的聚類算法

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

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

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

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

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

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

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

步驟3.1 計算xj的εj。

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

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

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

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

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

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

輸入：不平衡數據集S。

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

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

步驟2 根據算法2 對少數類樣本進行聚類，得到K、CK、C_set、NC_set。

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

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

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

Sgen即為合成的少數類樣本集合。

2.3 算法時間復雜度分析

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

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

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

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

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

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

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

表1 其他方法的時間復雜度

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

3 實驗

3.1 人工數據集

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

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

3.2 UCI數據集

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

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

表2 實驗所用數據集

本文選擇不平衡數據分類問題的常用評價指標Fvalue、G-mean 和AUC 作為分類結果。其中，AUC 是ROC 曲線下各部分的面積之和，表示分類器將隨機測試的正實例排序高于隨機測試的負實例的概率，數值越大，分類性能越好。F-value 和G-mean 的計算過程由混淆矩陣構造得到。混淆矩陣的定義如表3所示。

表3 混淆矩陣

F-value：

G-mean：

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

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

通過對比實驗結果可以看出：

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

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

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

（2）F-value。在SVM的分類結果中，本文方法在所有數據集上都取得了最優值。在KNN 的分類結果中，本文方法在六個數據集中獲得最優值，在數據集Letter、Glass7和Yeast4中的結果略低于最優值。總體來看，本文方法有效提高了少數類樣本的分類準確率。

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

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

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

4 結束語

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