鄰域感知的不平衡數據集過采樣方法

嚴遠亭，戴 濤，張以文，趙 姝，張燕平

(安徽大學 計算機科學與技術學院，合肥 230601)

1 引 言

分類是機器學習的一個重要研究分支[1].經典的分類器大多針對不同類別樣本數量相近的情況下進行分類[2].但并非所有的數據集都保持類間和類內平衡.在一個數據集中，當一個類別的樣本數量遠遠多于(或少于)其它類別時，此數據集稱為不平衡數據集[3].在不平衡數據集中，少數類樣本是重要的研究樣本.實際應用中，很多數據集都存在不平衡現象.例如：文本分類[4,5]、欺詐識別[6]、石油勘探[7]、醫療診斷[8-11].這些數據集中的少數類樣本往往更具有研究價值.但是，在不平衡的數據中，由于被研究的類別在整個數據集中所占比例較低，少數類樣本在分類過程中更容易出現分類錯誤，且將少數類的樣本誤分為多數類的代價要往往高于將多數類樣本誤分為少數類的代價.例如，將正常人誤診為癌癥患者，通常只需二次復查便可排除，而將癌癥患者誤診為正常人，會使患者錯過最佳治療時機.

當前對不平衡數據學習的研究大致可以分為算法層面和數據集層面的兩類方法.基于算法層面的典型方法有代價敏感學習[12-15]和核方法[16-19]等，此類方法將不同的數據賦予不同的研究權重，進而對樣本進行分類；數據集層面將不平衡數據集通過算法轉換成平衡數據集，從而進行分類.基于數據集層面的方法又可分為過采樣和欠采樣方法.過采樣方法是合成新的少數類樣本，從而使少數類樣本數量與多數類樣本數量一致.而欠采樣方法是選擇部分具有代表性的多數類樣本，從而與少數類樣本合并形成平衡數據集.

過采樣方法是當前主流的不平衡數據集處理方法，例如，隨機過采樣方法[3]，該方法是通過隨機選擇一定數量的少數類樣本，使少數類樣本和多數類樣本達到平衡.但是，這種方法容易導致模型過擬合.為克服上述缺點，Nitesh V.Chawla等人在2002年提出SMOTE(Synthetic Minority Over-sampling Technique)方法[20].該方法對少數類樣本計算其k近鄰，隨機選擇其中一個近鄰樣本，通過線性插值生成新樣本，以此使少數類和多數類樣本在數量上達到平衡.然而，由于SOMTE并未考慮所選的近鄰樣本的空間分布特征，從而增加了樣本間發生重疊的概率.

2005年，Hui Han等提出Borderline-SMOTE方法[21]，He等人在2008年提出ADASYN(Adaptive Synthetic Sampling Technique)方法[22].兩種方法一定程度上克服了SMOTE方法的不足.Borderline-SMOTE方法針對邊界域的少數類樣本進行過采樣.先計算所選的少數類樣本的m近鄰，若m個近鄰中一半以上是多數類樣本，則將該樣本放入合成新樣本所需的中心樣本的DANGER集中.從DANGER集中選擇一個樣本以及該樣本的k個少數類近鄰樣本中的某些樣本，計算偏差，通過SMOTE的線性插值方法合成新的少數類樣本.ADASYN根據少數類樣本的分布自適應生成新少數類樣本.難學習的樣本會生成更多的新樣本.ADASYN不僅能降低原不平衡數據的不平衡度，而且可以自適應的改變決策邊界，將重點放在那些難學習的樣本上.但是，由于該算法中生成樣本數量受密度分布的影響，當k個近鄰樣本中全為多數類樣本時，密度分布的系數值最大，此時該樣本將與k個近鄰生成多個新少數類樣本，但實際上該樣本可能為噪聲樣本.

Sukarna Barua等人在2014年提出一種基于少數類樣本的權重過采樣合成新的少數類樣本的方法[23].MWMOTE(Majority Weighted Minority Oversampling Technique)從原少數類樣本中基于k近鄰確定重要和難學習的少數類樣本，并給這些少數類樣本賦予選擇權重，最終根據選擇權重從重要和難學習的少數類樣本中合成新的少數類樣本.該方法可以有效地劃分出決策邊界，并在決策邊界附近確定難學習樣本，從而生成新少數類樣本.但是，此方法處理過程比較復雜，需要確定的參數比較多，同時，該方法有可能忽略有研究價值但不處于決策邊界的少數類樣本.

SMOTETomek方法由Batista等人于2003年提出[26].SMOTETomek屬于過采樣與欠采樣的聯合方法，該方法結合SMOTE和Tomek links[27]，先對少數類樣本進行過采樣，使數據樣本達到平衡.然后結合Tomek links技術，清除多數類和少數類相互糾纏的樣本(即噪聲樣本和邊界樣本).類似的方法還有SMOTEENN[28]，相對于SMOTETomek方法，SMOTEENN會對數據進行深度清洗，清除更多的多數類與少數類糾纏的樣本.除此之外，還有很多過采樣方法，如：V-SYNTH[29]、OUPS[30]、CCR[31]等.

當前的過采樣方法大多以如何挖掘邊界樣本，并基于邊界樣本信息進行后續的過采樣為主要研究目標.但是，考慮不平衡數據集樣本分布十分復雜，很難準確的進行邊界樣本的挖掘.因此，如何有效地利用樣本分布信息實現高效的過采樣，仍然是不平衡數據學習的重要挑戰.本文受構造性神經網絡的啟發[32]，從樣本空間分布的角度出發，提出一種基于少數類樣本局部鄰域信息的SMOTE過采樣方法.該方法通過學習樣本鄰域信息并利用鄰域信息約束過采樣過程中樣本的合成，將樣本約束在少數類的鄰域內.同時為了盡可能地挖掘樣本的有效鄰域并探測噪聲樣本.本文采用了集成策略來克服隨機初始化所造成的鄰域挖掘過程的不確定性，提高鄰域挖掘范圍和噪聲樣本的識別能力.

本文的后續結構分為4個部分.第2部分介紹并分析SMOTE；第3部分詳細介紹本文所提的算法；第4部分給出了本文的實驗結果及實驗分析；第5部分總結本文并對下一步工作進行了展望.

2 相關工作

2.1 SMOTE

SMOTE是最經典的過采樣方法之一，該方法有效地解決隨機過采樣產生的過擬合問題.SMOTE利用線性插值并結合k近鄰算法，合成新的少數類樣本，從而使得數據達到平衡.該方法隨機選擇少數類樣本，該樣本與其k近鄰中的一個樣本進行線性插值，得到新樣本.算法步驟如下：

1)確定所需合成的少數類樣本數量M；

2)利用歐氏距離計算少數類樣本xq的k個同類近鄰，其中k取5；

3)從k個近鄰樣本中隨機選擇一個樣本xj，與xq合成新的少數類樣本 ：

(1)

其中q∈{1,2,…,u},j∈{1,2,…,k},α∈[0,1]；

4)如果合成的樣本數量達到要求，則算法結束，否則，跳轉至步驟2.

如圖1所示，假設SMOTE從少數類樣本中隨機選取樣本A，A定義為種子樣本，利用KNN找到A的5個近鄰樣本，選擇其中的一個近鄰樣本B，那么樣本x1就是利用公式(1)得到的一個合成樣本.

圖1 SMOTE合成樣本示意圖Fig.1 Sketch map of SMOTE

2.2 SMOTE算法分析

由于SMOTE利用線性插值合成新的少數類樣本，該過程具有隨機性.從公式(1)可知，合成樣本的位置與種子樣本之間的位置關系以及線性插值中的隨機變量密切相關.

如圖2 (a)，當種子樣本A與其最近鄰樣本B處于同一區域的時候，此時進行樣本的合成并不會帶來噪聲，只可能產生少數類樣本的重疊現象；另一方面，如圖2 (b)所示，假設SMOTE算法中k近鄰取值為5，當以C為種子樣本時，樣本B為其近鄰樣本之一，以樣本C和B進行樣本合成時，由于

圖2 SMOTE合成樣本過程的分析示意圖Fig.2 Analysis of the synthetic process of SMOTE

這兩個樣本不處于同一區域，此時合成的樣本x2可能會落入多數類區域內，從而引入了新的噪聲樣本.同時，有可能產生樣本重疊現象(如樣本x3)，從而影響后續分類模型性能.

3 本文方法

SMOTE的隨機性可能增加新噪聲樣本和重疊樣本.為了提升不平衡數據過采樣的有效性，本文考慮利用樣本的鄰域信息，將過采樣過程中的合成樣本約束在少數類樣本鄰域內，從而避免引入額外的噪聲和異類重疊樣本.

構造性神經網絡[33]與傳統神經網絡的不同之處在于，它能夠構造性的完成網絡模型的自動確定，而不需要預先對網絡結構參數進行設定.文獻[34]給出了M-P神經元結點的幾何意義，即：利用三層神經網絡來構造分類器等同于尋找能夠劃分不同類型的輸入向量的鄰域集合.構造性神經網絡中以超球體作為樣本的鄰域，每一個超球體都是一個局部模式的學習函數.

借鑒上述構造性神經網絡中局部模式的學習方法，本文提出一種針對少數類樣本鄰域的學習方法.如圖3所示，假設圖中圓形區域表示學習的少數類樣本鄰域.通過挖掘少數類樣本的局部鄰域信息，假設鄰域中心為A、B、C、D、E.如圖3所示，假設種子樣本為C，對C與其近鄰樣本B使用線性插值并控制合成樣本的位置，使其落入少數類局部鄰域內，如樣本x4落在以C為中心的鄰域內.此外，合成的樣本也可落入以B或D為中心的鄰域中，如樣本x5和x6.本文方法控制樣本合成的位置，使得新樣本既不會與多數類樣本發生重疊，也不會成為噪聲樣本，即不會產生圖中樣本x7的情況.

圖3 鄰域信息與SMOTE結合示意圖Fig.3 Combing SMOTE and neighborhood information

3.1 鄰域信息挖掘

如何有效地挖掘少數類樣本的鄰域，以便更好地約束樣本的過采樣過程十分重要.本文受構造性神經網絡的啟發，提出樣本鄰域挖掘方法.

假設訓練集為D，記少數類樣本集為Dm，多數類樣本集為Dn.

首先，從Dm中隨機選擇樣本xi，作為鄰域中心.利用歐式距離計算離xi最近的異類樣本的距離，記為d1.

(2)

其中m∈{1,2,…,p}.

以d1為約束，計算以xi為中心，d1為半徑的鄰域范圍內同類樣本與xi的最遠距離，記為d2.

(3)

其中m∈{1,2,…,p}.

通過上述過程，本文能夠得到一個以xi為鄰域中心，θi為半徑的少數類樣本鄰域，本文采取折中[32，35]的辦法得到其半徑：

θi=(d1(i)+d2(i))/2

(4)

通過標記落在鄰域中的樣本，能夠得到一個少數類樣本鄰域.重復上述學習過程，直到數據集中的所有樣本均被標記為止，此時學習任務結束,獲得少數類樣本鄰域集合{N1,N2,…,Nn}.

3.2 鄰域融合

由于鄰域信息的挖掘過程帶有隨機性，所以不同的初始化對應的鄰域信息挖掘會有所差異，如圖4(a)-圖4(c)所示，其中圓形區域表示的是對應的鄰域.以圖4 (a)和圖4 (b)為例，在圖4 (a)中，一次鄰域信息挖掘后，得到以A、C、D、E、F為鄰域中心的樣本鄰域.此時，以A為中心的鄰域包含樣本G，以C為中心的鄰域包含樣本H，以D為中心的鄰域包含樣本I，以F為中心的鄰域包含樣本B，以E為中心的鄰域為單樣本鄰域.圖4 (b)給出的是另一次鄰域信息挖掘后得到的以B、D、E、G、H為鄰域中心的樣本鄰域.此時，樣本F被劃分到以G為中心的樣本鄰域里，樣本B形成單樣本鄰域.所以，不同的中心樣本選擇產生的樣本鄰域存在一定的差異.本文中，為避免隨機初始化造成的不確定性，本文利用集成策略，以盡可能地學習少數類樣本的鄰域范圍.

圖4 鄰域感知過程示意圖.(a),(b),(c)分別表示第1,2,3次鄰域信息挖掘結果,(d)表示三次挖掘的鄰域信息融合結果Fig.4 Sketch map of the proposed neighborhood-aware process.Sub figures(a),(b)and(c)represent the first,second and third times of neighborhood mining results respectively,and(d)denote the combining result of the three results

本文對樣本進行多次鄰域信息挖掘，每一次形成的鄰域都不盡相同.其中一次信息挖掘所形成的少數類樣本鄰域如公式(5)所示.

(5)

定義少數類樣本所在局部鄰域為PLN(Positive Local Neighborhood)，如公式(6)所示.

PLN=∪Nl

(6)

樣本鄰域的中心X=∪Xl，半徑Θ=∪Θl.該鄰域是合成新少數類樣本的安全域.在合成新樣本時，嚴格控制新樣本的空間位置，使得新合成的樣本僅落入PLN中，從而有效避免噪聲樣本的產生.

3.3 噪聲樣本檢測

SMOTE的隨機性增加了產生新噪聲樣本和樣本間發生重疊的可能性.本文提出的方法控制合成的新少數類樣本落入PLN中，有效地避免了新噪聲樣本的產生.但是，當種子樣本中有噪聲樣本時，上述控制合成樣本的過程無法有效識別噪聲樣本，從而使得新合成的樣本落入到噪聲樣本的鄰域.為此，本文提出如下的策略檢測噪聲樣本，對樣本xi，假設鄰域信息挖掘次數為W，那么，若W次鄰域挖掘過程都滿足公式(7)，則定義該樣本為噪聲樣本.

(7)

由公式(7)可知，對于任意一個少數類樣本xi，如果在W次的鄰域信息學習過程中，該樣本所處的鄰域中都僅包含該樣本，那么該樣本所處的鄰域則被視為噪聲域，該噪聲域會被排除在局部鄰域的形成過程之外.從而避免噪聲樣本附近合成新的少數類樣本.如公式(8)所示.

x={xi|(xi∈PLN)∧(xi?NOISE)}

(8)

其中x為合成的樣本集.

如圖5所示，假設E為噪聲樣本，選擇E與其近鄰樣本B合成新樣本x8，該樣本落在以B為中心的鄰域內，并不會落入E的附近.該方法可以有效地避免新噪聲樣本的引入.

圖5 噪聲域的處理示意圖Fig.5 Schematic of noise domain processing

本文的方法通過融合多次鄰域信息的挖掘過程，得到最終的少數類樣本鄰域，在此過程中判斷出高概率的噪聲樣本，利用鄰域信息約束后續的樣本合成過程，最終得到平衡數據.算法的具體步驟如下：

算法1.鄰域感知的過采樣技術(NA-SMOTE)

輸入：訓練集D，訓練次數W;

輸出：平衡數據集.

步驟：

1.數據預處理，得到少數類訓練集Dm，少數類樣本數Nm，多數類訓 練集Dn，多數類樣本數Nn；

2.FORl← 0 toW:

3.FORANYxi∈D:

4. 計算鄰域半徑θi/*公式(2)～公式(4)*/;

5.Ni=(xi,θi);

6.ENDFOR

8.ENDFOR

9.PLN=∪Nl,X=∪Xl,Θ=∪Θl;

10.WHILEDm′∪Dm

11.FORRANDOMxq∈Dm:

12. 計算xq的k近鄰樣本，存入distk中;

13.FORRANDOMxj∈distk:

17.ELSE:

18.j- = 1;

19.ENDIF

20.ENDFOR

21.ENDFOR

22.ENDWHILE

23.D′←Dm′∪Dm∪Dn;

24. 輸出平衡數據集.

3.4 算法復雜度分析

假設用ND表示總樣本數，Nn和Nm分別表示多數類和少數類樣本數量，f表示特征數量.NA-SMOTE的算法復雜度分析可以分為兩步：

1)分析少數類鄰域的復雜度：本文算法在一次迭代中進行多次鄰域信息挖掘，因此，所獲取的任意兩個少數類鄰域的復雜度有所不同.在最佳的情況下，所有少數類樣本都包含在一個少數類鄰域中，此時需要計算ND-1個距離，每次計算的復雜度為O(f)，因此，總復雜度等于O((ND-1)f).最壞的情況下，每一個少數類鄰域僅包含一個少數類樣本，此時有Nm個少數類鄰域.在這種情況下，少數類鄰域的復雜度包含Nm次信息挖掘.對于第一個少數類鄰域，其復雜度等于O((ND-1)f)，類似的，對于第i個少數類鄰域，其復雜度等于O((ND-i)f)，對于最后一個少數類鄰域，其復雜度等于O((ND-Nm)f).它們構成一個等差數列，因此一次鄰域信息挖掘的復雜度為O((2ND-Nm-1)fNm/2)，若局部鄰域信息挖掘重復W次.其復雜度為WO((2ND-Nm-1)fNm/2)， 故挖掘PLN的漸進復雜度為WO(NDNmf).

2)分析基于PLN的過采樣復雜度：為使數據集平衡，需要合成Nn-Nm個少數類樣本.經典的SMOTE 過采樣方法通過選擇種子樣本并進行線性插值，使不平衡數據集達到平衡.本文仍然采用這一思路，以少數類鄰域信息為約束，控制合成

1https://sci2s.ugr.es/keel/imbalanced.php

2https://archive.ics.uci.edu/ml/index.php

4 實驗及分析

本小節介紹了實驗所使用的數據集、用以評估實驗結果的評價指標以及所使用的分類器；并分析了集成次數與性能的關系、噪聲數據探測的結果以及對比實驗的結果.實驗環境為AMD銳龍2700X(8核16線程、主頻3.7GHz)、24GB DDR4 RAM，編程語言為Python(Pycharm1.4).

4.1 數據集

本文的實驗中數據集來自KEEL1和UCI2，其中KEEL數據集樣本容量從108到2935不等，不平衡率在1.8到100.2之間.表1給出了KEEL數據集的具體信息.UCI數據集樣本容量4873到45211不等，不平衡率在7.5到113.1之間.表2給出了UCI數據集的具體信息.部分數據集根據選擇作為少數類的標簽屬性的不同可以作為不同數據集使用，它們樣本容量相同，少數類樣本數量和不平衡率不同.其中，Abbr、Ins、Fea、Min、Maj、IR分別表示數據集簡寫名稱、樣本容量、樣本特征數、少數類樣本、多數類樣本以及不平衡率.

表1 KEEL數據集詳細信息Table 1 KEEL dataset details

表2 UCI數據集詳細信息Table 2 UCI dataset details

4.2 評價指標

本文以處理二分類問題為主要研究對象，將少數類視為正例，多數類視為負例.在實驗中根據真實類別和分類器預測類別，可以組合成真正例TP(true positive)、假正例FP(false positive)、真負例TN(true negative)、假負例FN(false negative)4種類型.其混淆矩陣如表3所示.

表3 混淆矩陣Table 3 Confusion matrix

基于混淆矩陣可以得到Accuracy、Precision、Recall、F_measure、G_mean、AUC等常用的性能評價指標.

Accuracy作為最常見的評價指標之一，通常來說，正確率越高，分類器性能越好.但是有時候準確率高并不能代表一個算法好.在不平衡數據中，需要研究的樣本數量在整個數據集中往往只占很小的比例，在這種樣本數量不平衡的情況下，Accuracy指標有很大的缺陷，會錯誤評估誤分類的代價[36，37].Precision在不平衡數據的研究中可能會出現分母為零的情況，因為分類過程中，可能出現將所有的少數類樣本誤分為多數類樣本的情況[37，38].因此，通常采用Recall、F_measure、G_mean、AUC作為不平衡數據分類效果的評價指標.

(9)

(10)

(11)

(12)

其中tprate=tp/(tp+fn)，fprate=fp/(fp+tn).

4.3 分類器

當前對不平衡數據的研究中，常用的分類器有SVM、Neural network、Na?ve Bayes等等，根據文獻[36]的統計，SVM是使用頻率最高的分類器，本文也選擇SVM作為基分類器.

4.4 集成次數性能的關系

本節對鄰域信息挖掘次數與最終的分類性能的關系進行了研究.為簡便起見，本文列出了其中4個典型數據集(glass9、wineqr、yeast11、krk1)上的實驗結果.分別對每組實驗重復10次并取其均值.

圖6給出了鄰域信息挖掘次數與算法最終性能之間的關系，其中的鄰域信息挖掘次數分別為1、2、5、10、15、20.以圖6(a)的Recall指標為例，Recall在W=5時明顯升高，隨著W的進一步增加，Recall值雖然仍然能夠有一些增長，但是提升并不明顯，整體上算法性能趨于穩定.考慮到W=20的時候，鄰域信息挖掘所耗費的時間大約為W=5時的4倍，但是性能的提升卻很小.可以在另外3個數據集上也發現類似的現象.同時，注意到在數據集wineqr上，鄰域挖掘次數為10的時候算法性能提升較明顯，隨著次數的增加，性能逐步穩定.綜合考慮分類性能與算法計算復雜度，簡便起見，本文選擇10為最終的鄰域信息挖掘次數.

圖6 算法性能與集成次數的關系示意圖Fig.6 Influence of independent ensemble number on algorithm performanc

4.5 噪聲數據探測

表4給出了本文算法在KEEL數據集上的實驗過程中探測出可能是噪聲樣本的個數.其中Numori表示原始數據中探測的噪聲樣本數量，Numfol表示訓練集中的噪聲數量.從表4中可以看出，訓練集中的噪聲數量大部分多于原始數據集，當本文對樣本進行劃分訓練集和測試集時會稀疏原數據集的少數類樣本，使原始數據中處于多數類附近的多個少數類樣本稀疏至單個樣本，從而增加了該樣本被誤判為噪聲樣本的概率.

表4 KEEL數據集對應的少數類噪聲樣本數量Table 4 Number of noise samples corresponding to KEEL datasets

從表5中可以看出，訓練集中噪聲的產生與劃分數據集的選擇有關，使得原始數據集中的正常少數類樣本被誤分為噪聲樣本.同時，在5折交叉中也出現了某一次或多次訓練集中噪聲樣本數量為0的情況，說明在某次劃分數據集時，并未使原數據集中的正常少數類樣本孤立.為了避免這種由交叉驗證過程中產生的樣本分布的變化，本文方法并不刪除測試集上探測出的可能的噪聲樣本，而是在過采樣時避免在此類可能的噪聲樣本形成的鄰域附近合成少數類樣本，從而達到避免引入新的噪聲樣本的可能.

表5 五折交叉訓練中噪聲樣本數量Table 5 Number of noise samples corresponding to training sets in 5-fold cross-validation

4.6 對比實驗

本文選擇5個過采樣方法Random Over Sampling[3]、SMOTE[20]、BorderlineSMOTE[21]、ADASYN[22]和MWMOTE[23]，以及兩種混合采樣方法SMOTETomek[26]、SMOTEENN[28]、CCR[31].在對比實驗中，分別用縮寫ROS、SMO、B-SMO、ADAS、MWMO、SMO-T、SMO-E、CCR代替上述8個算法，用NA-SMO代替本文的NA-SMOTE.實驗中，利用SMOTE合成樣本時，其最近鄰個數均采用SMOTE算法中的默認值，即k=5.

DatasetROSSMOB-SMOADASMWMOSMO-TSMO-ECCRNA-SMOglass10.7079±0.01090.7167±0.00850.6957±0.01680.7025±0.01230.7176±0.00610.7088±0.00930.7138±0.01230.6981±0.00000.7172±0.0059wiscon0.9716±0.00140.9730±0.00170.9740±0.00070.9751±0.00090.9732±0.00190.9723±0.00140.9749±0.00180.9718±0.00000.9731±0.0006glass20.7990±0.00800.7971±0.00730.8042±0.00140.7998±0.00200.7990±0.00770.7989±0.00440.7867±0.00430.8065±0.00000.7908±0.0017yeast10.7183±0.00390.7196±0.00280.7396±0.00410.7443±0.00260.7249±0.00230.7190±0.00270.7461±0.00290.7252±0.00000.7231±0.0023nthyd10.9788±0.00420.9801±0.00510.9862±0.0044.9793±0.00750.9785±0.00580.9786±0.00110.9746±0.00660.9737±0.00000.9767±0.0015nthyd20.9829±0.00840.9868±0.00690.9804±0.00160.9783±0.00140.9798±0.00500.9871±0.00580.9831±0.00620.9664±0.00000.9908±0.0061segmt00.9931±0.00040.9921±0.00000.9866±0.00020.9867±0.00010.9933±0.00010.9919±0.00050.9921±0.00040.9926±0.00000.9918±0.0000glass30.8800±0.00800.8837±0.00180.8812±0.00110.8798±0.00200.8842±0.00220.8833±0.00100.8809±0.00670.8826±0.00000.8826±0.0000ecoli10.8929±0.00500.8849±0.01030.9049±0.00740.8886±0.00470.8883±0.01230.8863±0.01290.8870±0.00570.8982±0.00000.8895±0.0018ecoli20.8893±0.00070.8947±0.00110.8657±0.00000.8884±0.00270.8895±0.00900.8942±0.00120.8893±0.00900.8891±0.00000.8909±0.0014ecoli30.8950±0.01130.8766±0.01660.8347±0.00150.8130±0.00940.8222±0.01830.8829±0.01060.8738±0.01920.9237±0.00000.9202±0.0060ecoli40.8853±0.00000.8855±0.00080.8612±0.00000.8811±0.00200.8880±0.00210.8855±0.00060.8873±0.00280.8853±0.00000.8863±0.0010yeast20.6831±0.01500.6823±0.00720.6831±0.01470.6661±0.01280.6744±0.01240.6794±0.00930.7042±0.01100.6830±0.00000.7183±0.0102yeast30.7239±0.00990.7310±0.01260.6785±0.00930.6674±0.00750.7080±0.00860.7290±0.01170.6981±0.00430.7269±0.00000.7535±0.0024yeast40.8938±0.00200.8927±0.00470.8542±0.00530.8618±0.00430.8947±0.00350.8956±0.00350.8982±0.00340.9095±0.00000.9047±0.0020ecoli50.8834±0.00090.8825±0.00800.8684±0.00000.8790±0.00850.8874±0.00280.8828±0.00890.8734±0.01150.8849±0.00000.8780±0.0006ecoli60.8852±0.01730.8664±0.01140.8353±0.00100.8152±0.01320.8231±0.01700.8710±0.01390.8705±0.01640.9436±0.00000.9106±0.0111ecoli70.8769±0.00080.8858±0.00200.8636±0.00000.8741±0.00120.8867±0.00590.8856±0.00110.8773±0.00260.8765±0.00000.8794±0.0014ecoli80.8615±0.00920.8687±0.00600.8693±0.00100.8413±0.00210.8629±0.00860.8709±0.00420.8576±0.00780.8518±0.00000.8639±0.0041 yeast50.7609±0.01420.7561±0.00790.7401±0.00880.7536±0.01270.7523±0.00770.7515±0.01010.7601±0.01270.7727±0.00000.7524±0.0063vowel00.9423±0.00030.9435±0.00040.8992±0.00000.9489±0.00030.9426±0.00040.9434±0.00030.9418±0.00070.9359±0.00000.9467±0.0022ecoli90.8263±0.00520.8425±0.01620.8431±0.00070.8306±0.01630.8370±0.00240.8406±0.01480.8393±0.01550.8567±0.00000.8808±0.0116glass50.7218±0.02430.6928±0.01780.6895±0.01840.7090±0.01040.6409±0.01930.7204±0.02070.7007±0.02990.6645±0.00000.6941±0.0034glass60.9050±0.06000.8454±0.09830.7250±0.00000.9250±0.00000.7250±0.00000.8854±0.08020.9250±0.00000.9250±0.00000.9608±0.0327glass70.7205±0.00630.7197±0.03420.6911±0.01310.7397±0.02220.6588±0.02510.7327±0.02710.7121±0.03200.7206±0.00000.7136±0.0090glass80.7327±0.01440.7229±0.02260.5831±0.00410.7387±0.02280.5946±0.00990.7222±0.02250.7262±0.02710.7253±0.00000.7216±0.0027ecoli100.8677±0.00480.8797±0.00630.8612±0.00050.8613±0.00190.8830±0.00280.8807±0.00250.8709±0.00470.8657±0.00000.8760±0.0011ecoli110.8945±0.00220.8931±0.01160.8743±0.00000.8668±0.00090.8905±0.01450.8967±0.00160.8926±0.00190.8924±0.00000.8923±0.0013yeast60.7452±0.01320.7410±0.01310.7157±0.02100.7429±0.01770.7166±0.02290.7383±0.01420.7435±0.01460.7506±0.00000.7430±0.0013glass90.8944±0.00000.8963±0.00150.8625±0.00190.8963±0.00180.8028±0.00090.8966±0.00190.8779±0.02380.8804±0.00000.9110±0.0171pageb00.9631±0.00100.9495±0.00060.9446±0.00030.9729±0.00150.9145±0.04190.9499±0.00120.9495±0.00090.9564±0.00000.9528±0.0054abalone00.7476±0.01130.7506±0.01730.6043±0.00960.7490±0.00840.6746±0.02200.7397±0.01390.7743±0.01550.7144±0.00000.7629±0.0120dermat1.000±0.00001.000±0.00001.000±0.00001.000±0.0000/1.000±0.00001.000±0.00001.000±0.00001.000±0.0000

續表

圖7給出了各個算法在所有數據集上的均值，可以看出，NA-SMO方法整體上要優于其他對比方法.表6給出了各個算法分別在KEEL數據集上10次實驗的F_measure均值及對應的標準差，其余3個評價指標見本文附件.由表6可以看出，本文的方法在19個數據集上取得最佳效果.在Recall、G-mean和AUC 上分別在39、19和19個數據集上達到最佳效果(具體結果見附件).表7給出了各個算法在UCI數據集上10次實驗的Recall、F_measure、G_mean、AUC均值及對應的標準差.其中，MWMO算法在計算多個UCI數據集時出現內存不足現象，導致無法得出結果.從表7可以看出，本文的方法也取得較好的效果(Recall:4/6、F_measure:5/6、G_mean:5/6、AUC:5/6).

圖7 算法性能及其標準差Fig.7 Algorithm performance and the standard deviation

表7 算法在UCI數據集上的結果Table 7 Comparison results on UCI datasets

為進一步對比算法的性能，本文將8個對比算法分別與NA-SMO進行了Wilcoxon Signed Rank Test(威爾科克森符號秩檢驗)，顯著性水平選取0.05.表8給出了keel數據集上的檢驗結果，由于在UCI數據集上，存在部分方法沒有得到實驗結果，因此無法符號秩和檢驗.如表8所示，從檢驗結果來看，本文的算法在絕大多數(26/28)的對比中都與對比算法有顯著的差異.結合前文的詳細性能對比結果可知，本文的方法與對比算法相比，具有一定的優勢.

表8 Wilcoxon Signed Rank Test的結果Table 8 Result of Wilcoxon Signed Rank Test

為進一步詳細說明Wilcoxon Signed Rank Test的結果[39]，本文選擇25個數據集在Recall指標上進行了Wilcoxon T值檢驗，結果如表9所示.以其中一個T值為例進行分析，例如， ROS有4個數據集的效果好于NA-SMO，但NA-SMO有21個好于ROS，將正Rank累加后得值299，負Rank累加后取絕對值得值26，得到T值為最小值26，由威爾科克森符號秩檢驗T值臨界值表可得，在顯著性水平為0.05時25個數據集上T的臨界值為89，當T值低于或等于該臨界值時拒絕零假設，因此，NA-SMO在此25個數據集上的效果好于ROS.

表9 Wilcoxon T值檢驗對比結果Table 9 Result of Wilcoxon T test

5 總結與展望

不平衡數據學習近年來成為機器學習領域中的一個研究熱點.SMOTE作為不平衡數據學習中最為經典的過采樣方法之一，得到了廣泛的研究和應用.但該方法還存在著諸如近鄰選擇具有一定盲目性、線性插值可能引入額外噪聲樣本以及產生重疊樣本等問題，不少研究針對上述問題提出了一系列的改進算法.但很多改進方法并未考慮到樣本空間分布的特性.本文從樣本空間分布出發，提出了通過學習樣本鄰域，并利用鄰域信息約束過采樣過程中樣本合成的范圍并實現噪聲樣本檢測，從而盡可能避免噪聲樣本的產生以及不同類別樣本間發生重疊的可能性.

本文在55個KEEL數據集和6個UCI數據集上通過與8個算法的對比驗證了鄰域信息在不平衡數據學習中的有效性.未來的工作將從兩個方面展開，一是研究本文算法的加速方法；另一方面，將研究如何將鄰域信息應用到不平衡數據的欠采樣中，結合鄰域感知的思想進行不平衡數據的欠采樣學習.