基于自然最近鄰的不平衡數(shù)據(jù)欠采樣方法

孟東霞，魏曉光，柳凌燕

（河北金融學(xué)院a.金融科技學(xué)院；b.信息工程與計(jì)算機(jī)學(xué)院，河北 保定 071051）

0 引言

不平衡數(shù)據(jù)是指各類別樣本的數(shù)量有巨大差異的數(shù)據(jù)集，其廣泛存在于金融欺詐檢測(cè)、醫(yī)療診斷、故障預(yù)測(cè)等實(shí)際應(yīng)用中。在將支持向量機(jī)、貝葉斯分類器、神經(jīng)網(wǎng)絡(luò)等傳統(tǒng)的分類模型用于不平衡數(shù)據(jù)的分類時(shí)，分類器傾向于學(xué)習(xí)多數(shù)類樣本的特征而忽略了少數(shù)類，容易將少數(shù)類樣本識(shí)別為多數(shù)類，無法保證少數(shù)類樣本的分類準(zhǔn)確率。而由于少數(shù)類樣本往往具有重要價(jià)值，因此其類別的誤判會(huì)造成嚴(yán)重的損失。以保險(xiǎn)欺詐檢測(cè)為例，欺詐行為的數(shù)量遠(yuǎn)遠(yuǎn)小于正常交易的數(shù)量，如果不能檢測(cè)出欺詐活動(dòng)，那么將會(huì)造成機(jī)構(gòu)資金的損失[1]。因此，如何提高不平衡數(shù)據(jù)中少數(shù)類樣本的分類準(zhǔn)確率具有重要的研究?jī)r(jià)值。

目前，對(duì)于提升不平衡數(shù)據(jù)分類性能的研究主要包括算法改進(jìn)和數(shù)據(jù)處理兩種思路。在算法方面，許多學(xué)者通過代價(jià)敏感學(xué)習(xí)、組合學(xué)習(xí)等策略對(duì)傳統(tǒng)的分類模型進(jìn)行改進(jìn)，使其在訓(xùn)練過程中關(guān)注少數(shù)類樣本的特征，提高少數(shù)類的識(shí)別準(zhǔn)確率。數(shù)據(jù)處理通常采用過采樣、欠采樣和混合采樣三種策略獲得平衡數(shù)據(jù)集，再使用分類模型對(duì)其分類。過采樣方法在少數(shù)類中根據(jù)某些策略合成新樣本，增加樣本數(shù)量，已有研究對(duì)經(jīng)典過采樣算法SMOTE（Synthetic Minority Over-sampling Technique）[2]提出了多種改進(jìn)方法，文獻(xiàn)[3]總結(jié)對(duì)比了85種過采樣方法的算法策略和分類表現(xiàn)。欠采樣方法刪除多數(shù)類中的部分樣本，使其在數(shù)量上與少數(shù)類樣本相等。混合采樣[4,5]綜合應(yīng)用了過采樣和欠采樣方法，使各類樣本的數(shù)量達(dá)到平衡。

隨機(jī)欠采樣在多數(shù)類中隨機(jī)刪除一定數(shù)量的樣本，使剩余樣本的數(shù)量與少數(shù)類相同，雖然操作簡(jiǎn)單，但有可能刪掉較多對(duì)分類有重要價(jià)值的樣本。為盡量保留多數(shù)類中重要樣本的分類信息，學(xué)者們提出了基于聚類的欠采樣、邊界附近的欠采樣等數(shù)據(jù)處理策略?；诰垲惖那凡蓸臃椒ㄕJ(rèn)為多數(shù)類中可能存在類內(nèi)不平衡的問題，在對(duì)多數(shù)類樣本進(jìn)行聚類后，從各類簇中篩選出代表性樣本加入平衡數(shù)據(jù)集，采用的聚類算法和樣本篩選策略是文獻(xiàn)研究的主要內(nèi)容[6—8]。在分類邊界處，不同類樣本的分布位置較為接近甚至重疊，文獻(xiàn)[9,10]指出類重疊對(duì)分類模型的表現(xiàn)有負(fù)面影響，因此，邊界區(qū)域中多數(shù)類樣本的欠采樣對(duì)準(zhǔn)確識(shí)別少數(shù)類樣本有積極作用：編輯最近鄰欠采樣方法[11]計(jì)算多數(shù)類樣本的三個(gè)最近鄰，若最近鄰中有兩個(gè)或以上為少數(shù)類樣本，則樣本容易被誤分為少數(shù)類樣本，需將其移除；由于支持向量分布在決策邊界附近，吳園園和申立勇（2018）[12]將多數(shù)類樣本依據(jù)類重疊度從大到小進(jìn)行欠采樣，保留對(duì)分類起決定性作用的支持向量；文獻(xiàn)[13]保留了多數(shù)類中分布在分類決策面附近可用于構(gòu)造特征邊界的樣本，減少了樣本信息的流失。石洪波等（2019）[14]在多數(shù)類的欠采樣中，基于安全樣本的計(jì)算保留對(duì)確定決策邊界有價(jià)值的樣本和部分安全樣本，丟棄噪聲樣本，結(jié)合SMOTE過采樣處理后的少數(shù)類，實(shí)現(xiàn)了不平衡數(shù)據(jù)集的再平衡。

在實(shí)際應(yīng)用中，數(shù)據(jù)集內(nèi)部樣本的分布密度有高和低的區(qū)別，密集區(qū)域聚集了大量的樣本，區(qū)域內(nèi)樣本包含的特征信息較稀疏區(qū)域中的樣本具有更高的價(jià)值和分類可靠性，在欠采樣時(shí)應(yīng)盡可能地選擇保留。為了選擇局部密集區(qū)域中的代表性樣本構(gòu)造平衡數(shù)據(jù)集，減少欠采樣造成的分類信息損失，本文提出了一種利用自然最近鄰的分布情況對(duì)多數(shù)類進(jìn)行欠采樣的數(shù)據(jù)處理方法。該方法先在數(shù)據(jù)集中計(jì)算多數(shù)類樣本的自然最近鄰，根據(jù)自然最近鄰的分布情況移除多數(shù)類中的噪聲樣本和局部密度較小的樣本；再計(jì)算剩余樣本之間的相似度，依據(jù)相似度大小選擇構(gòu)造平衡數(shù)據(jù)集的多數(shù)類樣本，丟棄冗余樣本和相對(duì)密度較小的樣本。

1 自然最近鄰

自然最近鄰是近年來提出的一種最近鄰概念，樣本的自然最近鄰個(gè)數(shù)由各自的分布特征自適應(yīng)生成，個(gè)數(shù)多少與樣本分布的疏密程度有關(guān)。局部分布稀疏的樣本所擁有的自然最近鄰少于密集樣本，而離群樣本和噪聲樣本的自然最近鄰個(gè)數(shù)相對(duì)更少甚至為0。考慮到自然最近鄰反映出的樣本分布疏密情況，有研究將其應(yīng)用到聚類、離群點(diǎn)檢測(cè)等領(lǐng)域。

假設(shè)有數(shù)據(jù)集X={x1,x2,…,xn}，樣本xi的自然最近鄰如定義1所示。

定義1（自然最近鄰）：NNN(xi)表示樣本xi的自然最近鄰集合：

其中，NNk(xi)表示樣本xi的k近鄰集合，RNNk(xi)表示樣本xi的k逆近鄰集合。

由定義1得出，自然最近鄰是一種對(duì)稱的鄰居關(guān)系，即樣本xi和xj互為彼此的k近鄰。與k近鄰的計(jì)算相比，自然最近鄰在搜索前無須指定任何參數(shù)，當(dāng)所有的樣本都有逆近鄰或逆近鄰個(gè)數(shù)為0的樣本保持不變時(shí)，自然最近鄰的搜索到達(dá)自然穩(wěn)定狀態(tài)，此時(shí)，搜索次數(shù)k被稱為自然特征值，記為λ。

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

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

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

輸出：自然特征值λ、樣本xi的自然最近鄰集合NNN(xi)和數(shù)量NB(xi)，1≤i≤|X|。

（1）初始化搜索次數(shù)k=1，NB(xi)=0，近鄰集合NN(xi)=?，逆近鄰集合RNN(xi)=?。

（2）計(jì)算xi的k近鄰，更新NB(xi)、NN(xi)、RNN(xi)。

（3）k=k+1。

（4）當(dāng)所有xi的RNN(xi)≠?或集合{xi|RNN(xi)=?}保持不變時(shí)，搜索過程到達(dá)自然穩(wěn)定狀態(tài)，λ=k-1，跳轉(zhuǎn)到步驟（5），否則跳轉(zhuǎn)到步驟（2）。

（5）計(jì)算所有樣本的自然最近鄰，NNN(xi)=NN(xi)，返回λ、NNN(xi)和NB(xi)。

通過算法1可以得到所有樣本的自然最近鄰和數(shù)量，自然最近鄰數(shù)量大于或等于λ的樣本處于局部分布較為密集的區(qū)域，其余樣本的局部密度較小。在不平衡數(shù)據(jù)集中，根據(jù)多數(shù)類樣本的自然最近鄰數(shù)量可以推測(cè)樣本是否處于密集區(qū)域，如果多數(shù)類樣本的自然最近鄰集合中存在少數(shù)類樣本，那么可以判定多數(shù)類樣本距離少數(shù)類較近，甚至有可能為噪聲樣本。本文在確定了所有多數(shù)類樣本的自然最近鄰集合后，根據(jù)自然最近鄰的分布情況移除噪聲樣本和部分分布較為稀疏的樣本，選擇局部密度較大的代表性樣本構(gòu)造平衡數(shù)據(jù)集。

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

本文利用多數(shù)類樣本的自然最近鄰所反映出的樣本局部分布情況，提出了一種基于自然最近鄰選擇樣本構(gòu)造平衡數(shù)據(jù)集的欠采樣方法（Undersampling Method based on Natural Nearest Neighbor,USNNN）。欠采樣方法USNNN的實(shí)現(xiàn)包括四個(gè)步驟：

（1）利用算法1計(jì)算多數(shù)類樣本在不平衡數(shù)據(jù)集中的自然最近鄰。

（2）根據(jù)自然最近鄰的數(shù)量和分布，將多數(shù)類樣本分為四種類型，不同種類的樣本采取不同的處理方法。

第一類：噪聲樣本。如果樣本的自然最近鄰個(gè)數(shù)大于0且所有的自然最近鄰均屬于少數(shù)類，那么可將此類樣本判定為噪聲點(diǎn)，為了減少其對(duì)分類模型性能的影響，在欠采樣時(shí)將其移除。

第二類：離群樣本。如果樣本的自然最近鄰個(gè)數(shù)為0，那么可判斷此樣本為多數(shù)類中的離群點(diǎn)，對(duì)分類的影響較小，在欠采樣時(shí)將其移除。

第三類：稀疏樣本。如果樣本的自然最近鄰均屬于多數(shù)類且數(shù)量小于λ/2，那么根據(jù)自然最近鄰的概念，此類樣本位于較為稀疏的區(qū)域，樣本特征對(duì)分類的影響較小，在欠采樣時(shí)將其移除。

第四類：由不屬于前三類的樣本構(gòu)成。其中，自然最近鄰個(gè)數(shù)大于或等于λ/2且近鄰均屬于多數(shù)類的樣本，處于局部密度相對(duì)較大的區(qū)域，且自然最近鄰的個(gè)數(shù)越多，該樣本的局部分布越密集，如果樣本的自然最近鄰具有相同的特點(diǎn)，那么樣本與其自然最近鄰可能分布在多數(shù)類內(nèi)部某個(gè)子類簇的中心區(qū)域或距離中心較近，樣本的保留能體現(xiàn)原始數(shù)據(jù)的主要分布結(jié)構(gòu)信息。該類中其他樣本的自然最近鄰?fù)瑫r(shí)分布在少數(shù)類和多數(shù)類兩個(gè)類別中，可推測(cè)此樣本距離少數(shù)類較近，樣本特征對(duì)訓(xùn)練分類模型有重要價(jià)值，在欠采樣過程中可選擇部分樣本保留。由于此類樣本的數(shù)量較多，且存在分布位置較為接近的冗余樣本，因此USNNN算法將在后續(xù)步驟中對(duì)其做欠采樣處理。

（3）在第四類樣本中，計(jì)算任意兩個(gè)樣本之間的相似度，構(gòu)造相似度矩陣。

樣本xi和xj的相似度sim(xi,xj)可由公式（1）計(jì)算得到：

其中，inter(xi,xj)表示樣本xi和xj共同擁有的自然最近鄰的個(gè)數(shù)，其值越大，表示樣本xi和xj在空間分布上越接近，相似程度越高，若兩者不存在共同自然最近鄰，則相似度為0；dist(xi,xj)是xi和xj之間的歐幾里德距離，距離越近，相似度sim(xi,xj)的值越大，反之則越小。因此，由公式（1）定義樣本間的相似性是合理的。

相似度矩陣的行數(shù)和列數(shù)與第四類樣本的數(shù)量相同。

（4）根據(jù)相似度選擇樣本構(gòu)造平衡數(shù)據(jù)集。挑選相似度矩陣中相似度最高的兩個(gè)樣本，將其中自然最近鄰較多的樣本保留，刪除另外一個(gè)樣本，并在相似度矩陣中刪除兩個(gè)樣本對(duì)應(yīng)的行和列，重復(fù)此步驟直到保留的樣本個(gè)數(shù)與少數(shù)類樣本的數(shù)量一致或相似度矩陣為空矩陣。當(dāng)矩陣為空矩陣時(shí)，保留的多數(shù)類樣本個(gè)數(shù)小于少數(shù)類，從第四類樣本中隨機(jī)選擇部分樣本加入平衡數(shù)據(jù)集。

算法2描述了USNNN的實(shí)現(xiàn)步驟。

算法2（基于自然最近鄰的欠采樣方法）

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

輸出：平衡數(shù)據(jù)集Sbal。

（1）將數(shù)據(jù)集S中的多數(shù)類樣本和少數(shù)類樣本分別劃分到集合Smaj和Smin中，得到兩類樣本的個(gè)數(shù)Nmaj和Nmin。

（2）利用算法1計(jì)算Smaj中的所有樣本在S中的自然最近鄰，得到自然特征值λ、樣本xi的自然最近鄰集合NNN(xi)和自然最近鄰的數(shù)量NB(xi)，i=1,2,…,Nmaj。

（3）根據(jù)NNN(xi)和NB(xi)，將噪聲點(diǎn)、離群點(diǎn)和稀疏樣本從Smaj中刪除。

①定義噪聲樣本的集合S1、離群樣本的集合S2和稀疏樣本的集合S3，初始值均為?。

②如果NB(xi)>0且NNN(xi)中的所有自然最近鄰樣本均屬于Smin，那么樣本xi為噪聲點(diǎn)，將xi加入集合S1，執(zhí)行操作Smaj=Smaj-S1和Nmaj=Nmaj-|S1|，將S1中的樣本從Smaj中刪除。若Nmaj≤Nmin，則將集合Smaj和Smin構(gòu)造平衡數(shù)據(jù)集Sbal并輸出，算法2結(jié)束，否則執(zhí)行步驟③。

③如果NB(xi)=0，那么樣本xi為離群點(diǎn)，將xi加入集合S2，執(zhí)行操作Smaj=Smaj-S2和Nmaj=Nmaj-|S2|，將S2中的樣本從Smaj中刪除。若Nmaj≤Nmin，則將集合Smaj和Smin構(gòu)造平衡數(shù)據(jù)集Sbal并輸出，算法2結(jié)束，否則執(zhí)行步驟④。

④如果NB(xi)<λ/2且NNN(xi)中的任意自然最近鄰樣本均屬于Smaj，那么樣本xi為多數(shù)類中的稀疏樣本，將xi加入集合S3，執(zhí)行操作Smaj=Smaj-S3和Nmaj=Nmaj-|S3|，將S3中的樣本從Smaj中刪除。若Nmaj≤Nmin，則將集合Smaj和Smin構(gòu)造平衡數(shù)據(jù)集Sbal并輸出，算法2結(jié)束，否則執(zhí)行步驟（4）。

（4）對(duì)Smaj中剩余的第四類樣本計(jì)算相似度，構(gòu)造相似度矩陣M。M的行數(shù)和列數(shù)均等于Nmaj，第i行第j列位置上的元素值是樣本xi和xj的相似度（1≤i,j≤Nmaj），可通過公式計(jì)算得到，inter(xi,xj)是xi和xj共有的自然最近鄰的個(gè)數(shù)，dist(xi,xj)是兩者之間的歐幾里德距離。

（5）根據(jù)相似度的值挑選樣本構(gòu)造平衡數(shù)據(jù)集。

①定義集合S'maj表示平衡后的多數(shù)類樣本集合，初始值為?。

②選擇矩陣M中最大的相似度值Mi,j，比較Mi,j對(duì)應(yīng)的樣本xi和xj的自然最近鄰數(shù)NB(xi)和NB(xj)，將自然最近鄰數(shù)量較多的樣本加入集合Sm'aj，并且在集合Smaj中移除xi和xj。將矩陣M的第i行和第j列刪除，得到新的矩陣。重復(fù)執(zhí)行此步驟直到或M為空矩陣。

③步驟②結(jié)束后，如果M為空矩陣且，那么在集合Smaj中隨機(jī)挑選個(gè)樣本加入Sm'aj，使，否則跳轉(zhuǎn)到步驟④。

下頁圖1展示了應(yīng)用USNNN方法對(duì)二維不平衡數(shù)據(jù)集欠采樣的過程。圖1（a）中的數(shù)據(jù)集包括200個(gè)樣本，其中，少數(shù)類樣本有50個(gè)，多數(shù)類樣本有150個(gè)，在圖1（a）中分別用“?”和“×”表示。多數(shù)類中包括多個(gè)子類簇，樣本具有分布不平衡的特點(diǎn)，邊界處和類內(nèi)均包含密集區(qū)域和稀疏區(qū)域。使用算法2中的步驟（2）計(jì)算了所有多數(shù)類樣本的自然最近鄰后，通過步驟（3）確定多數(shù)類中的噪聲樣本、離群樣本和稀疏樣本，并在圖1（b）和圖1（c）中進(jìn)行標(biāo)記。在圖1（b）中，噪聲樣本和離群樣本分別用“▲”和“▼”表示。噪聲樣本的自然最近鄰均屬于少數(shù)類，位置處于少數(shù)類樣本較多的區(qū)域。噪聲樣本的存在會(huì)對(duì)分類模型的訓(xùn)練產(chǎn)生干擾，在欠采樣時(shí)應(yīng)刪掉。離群樣本距離多數(shù)類樣本較遠(yuǎn)，其特征對(duì)分類模型的影響較小，可以刪除。圖1（c）中的“?”是由自然最近鄰確定的稀疏樣本，其所在區(qū)域的密度較小，樣本特征的價(jià)值小于密集區(qū)域的樣本，在欠采樣過程中可移除。對(duì)圖1（c）中的剩余樣本使用算法2中的步驟（4）計(jì)算相似度矩陣后，使用步驟（5）挑選代表性樣本構(gòu)造平衡數(shù)據(jù)集，欠采樣后的平衡數(shù)據(jù)集如圖1（d）所示。與原始數(shù)據(jù)集相比，在多數(shù)類的各個(gè)類簇中，類內(nèi)密度較大的代表性樣本被保留，冗余樣本和對(duì)訓(xùn)練分類模型價(jià)值較小的樣本被移除。

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

為了驗(yàn)證USNNN欠采樣方法的分類效果，本文利用Random UnderSampling（RUS）、Cluster Centroids（CC）、TomekLinks（TL）、Edited Nearest Neighbors（ENN）和USNNN對(duì)來自KEEL[15]的12組數(shù)據(jù)集進(jìn)行欠采樣處理。表1列出了數(shù)據(jù)集的基本信息，IR是多數(shù)類樣本數(shù)量和少數(shù)類樣本數(shù)量的比值，表示不平衡率。在多類別數(shù)據(jù)集中，指定一個(gè)類別為少數(shù)類，其余類合并為多數(shù)類。在實(shí)驗(yàn)前，將所有樣本的特征值歸一化到[0,1]區(qū)間內(nèi)。實(shí)驗(yàn)采用五折交叉驗(yàn)證的方法，各組訓(xùn)練集和測(cè)試集的IR與原數(shù)據(jù)集保持一致，各指標(biāo)的實(shí)驗(yàn)結(jié)果取五組實(shí)驗(yàn)的平均值。USNNN方法使用Python實(shí)現(xiàn)，其余欠采樣方法使用Python庫imbalance-learn package中的代碼，分類模型為支持向量機(jī)，核函數(shù)采用高斯核，使用Python庫scikit-learn中的SVC代碼實(shí)現(xiàn)。

本文采用召回率（Recall）、F-value和G-mean評(píng)估不同欠采樣方法對(duì)不平衡數(shù)據(jù)集分類效果的影響。Recall、F-value和G-mean的計(jì)算過程由表2所示的混淆矩陣得到。表2中，正類代表少數(shù)類，負(fù)類代表多數(shù)類。

表2 混淆矩陣

召回率表示分類正確的少數(shù)類樣本個(gè)數(shù)占所有少數(shù)類樣本的比例，召回率越高，表示被正確分類的少數(shù)類樣本越多。

G-mean同時(shí)衡量了分類器對(duì)多數(shù)類和少數(shù)類的識(shí)別能力，可用于衡量整體分類效果。

表3匯總了使用SVM對(duì)不同欠采樣方法進(jìn)行處理后的平衡數(shù)據(jù)集進(jìn)行分類得到的F-value、G-mean和Recall的值，各項(xiàng)指標(biāo)的最佳結(jié)果使用下劃線表示。將五種欠采樣方法在同一數(shù)據(jù)集、同一指標(biāo)上的結(jié)果按照降序排列，結(jié)果最高的名次為1，依次遞增，下頁表4列出了五種方法在所有數(shù)據(jù)集中的平均排名。

表3 SVM對(duì)不同欠采樣方法構(gòu)造的平衡數(shù)據(jù)集的分類結(jié)果

表4 不同欠采樣方法在同一指標(biāo)上的平均排名

對(duì)比表3中不同欠采樣方法在指標(biāo)F-value上得到的計(jì)算結(jié)果，本文方法USNNN在4個(gè)數(shù)據(jù)集上取得了最高的F-value值，在數(shù)據(jù)集C1、G2、Hd、Y6上的排名為第2，在數(shù)據(jù)集K1和E3上取得的名次為第3，在數(shù)據(jù)集E1和Cd上的排名較TL方法靠前。結(jié)合表4中顯示的USNNN在指標(biāo)F-value上獲得了最高排名，可以發(fā)現(xiàn)USNNN方法對(duì)不平衡數(shù)據(jù)集中的少數(shù)類樣本具有較高的識(shí)別準(zhǔn)確率。對(duì)比G-mean的結(jié)果，USNNN在7個(gè)數(shù)據(jù)集上得到了最高的G-mean值，在數(shù)據(jù)集Pa、K1上獲得的名次為第2，在數(shù)據(jù)集E3、Cd和G2上的排名為第3，在所有數(shù)據(jù)集上的平均排名為第1，說明USNNN對(duì)不平衡數(shù)據(jù)集的整體分類性能較好。USNNN在10個(gè)數(shù)據(jù)集上得到了最佳的Recall值，在數(shù)據(jù)集Pa和G2上的排名分別為第2和第3，平均排名為第1，說明USNNN對(duì)少數(shù)類樣本的召回率普遍優(yōu)于對(duì)比算法，能使分類器更加關(guān)注少數(shù)類樣本。以上結(jié)果證明USNNN提高了對(duì)少數(shù)類樣本的識(shí)別能力，是有效的欠采樣方法。

4 結(jié)束語

本文提出了一種基于多數(shù)類樣本的自然最近鄰進(jìn)行欠采樣的不平衡數(shù)據(jù)處理方法。該方法先計(jì)算多數(shù)類樣本在數(shù)據(jù)集中的自然最近鄰，依據(jù)自然最近鄰的分布情況移除噪聲樣本和稀疏樣本；再根據(jù)剩余樣本間的相似度，移除冗余樣本，選擇密集區(qū)域中的代表性樣本構(gòu)造平衡數(shù)據(jù)集。實(shí)驗(yàn)結(jié)果顯示，本文方法提高了少數(shù)類樣本的分類準(zhǔn)確率，驗(yàn)證了本文方法的有效性。