嚴(yán)遠(yuǎn)亭，戴 濤，張以文，趙 姝，張燕平

(安徽大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，合肥 230601)

1 引 言

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

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

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

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

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

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

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

本文的后續(xù)結(jié)構(gòu)分為4個部分.第2部分介紹并分析SMOTE；第3部分詳細(xì)介紹本文所提的算法；第4部分給出了本文的實驗結(jié)果及實驗分析；第5部分總結(jié)本文并對下一步工作進(jìn)行了展望.

2 相關(guān)工作

2.1 SMOTE

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

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

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

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

(1)

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

4)如果合成的樣本數(shù)量達(dá)到要求，則算法結(jié)束，否則，跳轉(zhuǎn)至步驟2.

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

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

2.2 SMOTE算法分析

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

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

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

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

3 本文方法

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

構(gòu)造性神經(jīng)網(wǎng)絡(luò)[33]與傳統(tǒng)神經(jīng)網(wǎng)絡(luò)的不同之處在于，它能夠構(gòu)造性的完成網(wǎng)絡(luò)模型的自動確定，而不需要預(yù)先對網(wǎng)絡(luò)結(jié)構(gòu)參數(shù)進(jìn)行設(shè)定.文獻(xiàn)[34]給出了M-P神經(jīng)元結(jié)點的幾何意義，即：利用三層神經(jīng)網(wǎng)絡(luò)來構(gòu)造分類器等同于尋找能夠劃分不同類型的輸入向量的鄰域集合.構(gòu)造性神經(jīng)網(wǎng)絡(luò)中以超球體作為樣本的鄰域，每一個超球體都是一個局部模式的學(xué)習(xí)函數(shù).

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

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

3.1 鄰域信息挖掘

如何有效地挖掘少數(shù)類樣本的鄰域，以便更好地約束樣本的過采樣過程十分重要.本文受構(gòu)造性神經(jīng)網(wǎng)絡(luò)的啟發(fā)，提出樣本鄰域挖掘方法.

假設(shè)訓(xùn)練集為D，記少數(shù)類樣本集為Dm，多數(shù)類樣本集為Dn.

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

(2)

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

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

(3)

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

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

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

(4)

通過標(biāo)記落在鄰域中的樣本，能夠得到一個少數(shù)類樣本鄰域.重復(fù)上述學(xué)習(xí)過程，直到數(shù)據(jù)集中的所有樣本均被標(biāo)記為止，此時學(xué)習(xí)任務(wù)結(jié)束,獲得少數(shù)類樣本鄰域集合{N1,N2,…,Nn}.

3.2 鄰域融合

由于鄰域信息的挖掘過程帶有隨機(jī)性，所以不同的初始化對應(yīng)的鄰域信息挖掘會有所差異，如圖4(a)-圖4(c)所示，其中圓形區(qū)域表示的是對應(yīng)的鄰域.以圖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形成單樣本鄰域.所以，不同的中心樣本選擇產(chǎn)生的樣本鄰域存在一定的差異.本文中，為避免隨機(jī)初始化造成的不確定性，本文利用集成策略，以盡可能地學(xué)習(xí)少數(shù)類樣本的鄰域范圍.

圖4 鄰域感知過程示意圖.(a),(b),(c)分別表示第1,2,3次鄰域信息挖掘結(jié)果,(d)表示三次挖掘的鄰域信息融合結(jié)果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

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

(5)

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

PLN=∪Nl

(6)

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

3.3 噪聲樣本檢測

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

(7)

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

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

(8)

其中x為合成的樣本集.

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

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

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

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

輸入：訓(xùn)練集D，訓(xùn)練次數(shù)W;

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

步驟：

1.數(shù)據(jù)預(yù)處理，得到少數(shù)類訓(xùn)練集Dm，少數(shù)類樣本數(shù)Nm，多數(shù)類訓(xùn) 練集Dn，多數(shù)類樣本數(shù)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. 輸出平衡數(shù)據(jù)集.

3.4 算法復(fù)雜度分析

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

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

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

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

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

4 實驗及分析

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

4.1 數(shù)據(jù)集

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

表1 KEEL數(shù)據(jù)集詳細(xì)信息Table 1 KEEL dataset details

表2 UCI數(shù)據(jù)集詳細(xì)信息Table 2 UCI dataset details

4.2 評價指標(biāo)

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

表3 混淆矩陣Table 3 Confusion matrix

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

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

(9)

(10)

(11)

(12)

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

4.3 分類器

當(dāng)前對不平衡數(shù)據(jù)的研究中，常用的分類器有SVM、Neural network、Na?ve Bayes等等，根據(jù)文獻(xiàn)[36]的統(tǒng)計，SVM是使用頻率最高的分類器，本文也選擇SVM作為基分類器.

4.4 集成次數(shù)性能的關(guān)系

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

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

圖6 算法性能與集成次數(shù)的關(guān)系示意圖Fig.6 Influence of independent ensemble number on algorithm performanc

4.5 噪聲數(shù)據(jù)探測

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

表4 KEEL數(shù)據(jù)集對應(yīng)的少數(shù)類噪聲樣本數(shù)量Table 4 Number of noise samples corresponding to KEEL datasets

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

表5 五折交叉訓(xùn)練中噪聲樣本數(shù)量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合成樣本時，其最近鄰個數(shù)均采用SMOTE算法中的默認(rèn)值，即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

續(xù)表

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

圖7 算法性能及其標(biāo)準(zhǔn)差Fig.7 Algorithm performance and the standard deviation

表7 算法在UCI數(shù)據(jù)集上的結(jié)果Table 7 Comparison results on UCI datasets

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

表8 Wilcoxon Signed Rank Test的結(jié)果Table 8 Result of Wilcoxon Signed Rank Test

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

表9 Wilcoxon T值檢驗對比結(jié)果Table 9 Result of Wilcoxon T test

5 總結(jié)與展望

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

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