鄰域感知的不平衡數(shù)據(jù)集過采樣方法

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

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

1 引 言

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

當(dāng)前對(duì)不平衡數(shù)據(jù)學(xué)習(xí)的研究大致可以分為算法層面和數(shù)據(jù)集層面的兩類方法.基于算法層面的典型方法有代價(jià)敏感學(xué)習(xí)[12-15]和核方法[16-19]等，此類方法將不同的數(shù)據(jù)賦予不同的研究權(quán)重，進(jìn)而對(duì)樣本進(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)致模型過擬合.為克服上述缺點(diǎn)，Nitesh V.Chawla等人在2002年提出SMOTE(Synthetic Minority Over-sampling Technique)方法[20].該方法對(duì)少數(shù)類樣本計(jì)算其k近鄰，隨機(jī)選擇其中一個(gè)近鄰樣本，通過線性插值生成新樣本，以此使少數(shù)類和多數(shù)類樣本在數(shù)量上達(dá)到平衡.然而，由于SOMTE并未考慮所選的近鄰樣本的空間分布特征，從而增加了樣本間發(fā)生重疊的概率.

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

SMOTETomek方法由Batista等人于2003年提出[26].SMOTETomek屬于過采樣與欠采樣的聯(lián)合方法，該方法結(jié)合SMOTE和Tomek links[27]，先對(duì)少數(shù)類樣本進(jìn)行過采樣，使數(shù)據(jù)樣本達(dá)到平衡.然后結(jié)合Tomek links技術(shù)，清除多數(shù)類和少數(shù)類相互糾纏的樣本(即噪聲樣本和邊界樣本).類似的方法還有SMOTEENN[28]，相對(duì)于SMOTETomek方法，SMOTEENN會(huì)對(duì)數(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)行邊界樣本的挖掘.因此，如何有效地利用樣本分布信息實(shí)現(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).同時(shí)為了盡可能地挖掘樣本的有效鄰域并探測(cè)噪聲樣本.本文采用了集成策略來克服隨機(jī)初始化所造成的鄰域挖掘過程的不確定性，提高鄰域挖掘范圍和噪聲樣本的識(shí)別能力.

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

2 相關(guān)工作

2.1 SMOTE

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

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

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

3)從k個(gè)近鄰樣本中隨機(jī)選擇一個(gè)樣本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個(gè)近鄰樣本，選擇其中的一個(gè)近鄰樣本B，那么樣本x1就是利用公式(1)得到的一個(gè)合成樣本.

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

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

這兩個(gè)樣本不處于同一區(qū)域，此時(shí)合成的樣本x2可能會(huì)落入多數(shù)類區(qū)域內(nèi)，從而引入了新的噪聲樣本.同時(shí)，有可能產(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ò)模型的自動(dòng)確定，而不需要預(yù)先對(duì)網(wǎng)絡(luò)結(jié)構(gòu)參數(shù)進(jìn)行設(shè)定.文獻(xiàn)[34]給出了M-P神經(jīng)元結(jié)點(diǎn)的幾何意義，即：利用三層神經(jīng)網(wǎng)絡(luò)來構(gòu)造分類器等同于尋找能夠劃分不同類型的輸入向量的鄰域集合.構(gòu)造性神經(jīng)網(wǎng)絡(luò)中以超球體作為樣本的鄰域，每一個(gè)超球體都是一個(gè)局部模式的學(xué)習(xí)函數(shù).

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

(2)

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

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

(3)

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

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

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

(4)

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

3.2 鄰域融合

由于鄰域信息的挖掘過程帶有隨機(jī)性，所以不同的初始化對(duì)應(yīng)的鄰域信息挖掘會(huì)有所差異，如圖4(a)-圖4(c)所示，其中圓形區(qū)域表示的是對(duì)應(yīng)的鄰域.以圖4 (a)和圖4 (b)為例，在圖4 (a)中，一次鄰域信息挖掘后，得到以A、C、D、E、F為鄰域中心的樣本鄰域.此時(shí)，以A為中心的鄰域包含樣本G，以C為中心的鄰域包含樣本H，以D為中心的鄰域包含樣本I，以F為中心的鄰域包含樣本B，以E為中心的鄰域?yàn)閱螛颖距徲?圖4 (b)給出的是另一次鄰域信息挖掘后得到的以B、D、E、G、H為鄰域中心的樣本鄰域.此時(shí)，樣本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

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

(5)

定義少數(shù)類樣本所在局部鄰域?yàn)镻LN(Positive Local Neighborhood)，如公式(6)所示.

PLN=∪Nl

(6)

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

3.3 噪聲樣本檢測(cè)

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

(7)

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

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

(8)

其中x為合成的樣本集.

如圖5所示，假設(shè)E為噪聲樣本，選擇E與其近鄰樣本B合成新樣本x8，該樣本落在以B為中心的鄰域內(nèi)，并不會(huì)落入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. 計(jì)算鄰域半徑θi/*公式(2)～公式(4)*/;

5.Ni=(xi,θi);

6.ENDFOR

8.ENDFOR

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

10.WHILEDm′∪Dm

11.FORRANDOMxq∈Dm:

12. 計(jì)算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)行多次鄰域信息挖掘，因此，所獲取的任意兩個(gè)少數(shù)類鄰域的復(fù)雜度有所不同.在最佳的情況下，所有少數(shù)類樣本都包含在一個(gè)少數(shù)類鄰域中，此時(shí)需要計(jì)算ND-1個(gè)距離，每次計(jì)算的復(fù)雜度為O(f)，因此，總復(fù)雜度等于O((ND-1)f).最壞的情況下，每一個(gè)少數(shù)類鄰域僅包含一個(gè)少數(shù)類樣本，此時(shí)有Nm個(gè)少數(shù)類鄰域.在這種情況下，少數(shù)類鄰域的復(fù)雜度包含Nm次信息挖掘.對(duì)于第一個(gè)少數(shù)類鄰域，其復(fù)雜度等于O((ND-1)f)，類似的，對(duì)于第i個(gè)少數(shù)類鄰域，其復(fù)雜度等于O((ND-i)f)，對(duì)于最后一個(gè)少數(shù)類鄰域，其復(fù)雜度等于O((ND-Nm)f).它們構(gòu)成一個(gè)等差數(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個(gè)少數(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 實(shí)驗(yàn)及分析

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

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

本文的實(shí)驗(yàn)中數(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 評(píng)價(jià)指標(biāo)

本文以處理二分類問題為主要研究對(duì)象，將少數(shù)類視為正例，多數(shù)類視為負(fù)例.在實(shí)驗(yàn)中根據(jù)真實(shí)類別和分類器預(yù)測(cè)類別，可以組合成真正例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等常用的性能評(píng)價(jià)指標(biāo).

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

(9)

(10)

(11)

(12)

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

4.3 分類器

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

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

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

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

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

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

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

表4 KEEL數(shù)據(jù)集對(duì)應(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ù)類樣本被誤分為噪聲樣本.同時(shí)，在5折交叉中也出現(xiàn)了某一次或多次訓(xùn)練集中噪聲樣本數(shù)量為0的情況，說明在某次劃分?jǐn)?shù)據(jù)集時(shí)，并未使原數(shù)據(jù)集中的正常少數(shù)類樣本孤立.為了避免這種由交叉驗(yàn)證過程中產(chǎn)生的樣本分布的變化，本文方法并不刪除測(cè)試集上探測(cè)出的可能的噪聲樣本，而是在過采樣時(shí)避免在此類可能的噪聲樣本形成的鄰域附近合成少數(shù)類樣本，從而達(dá)到避免引入新的噪聲樣本的可能.

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

4.6 對(duì)比實(shí)驗(yàn)

本文選擇5個(gè)過采樣方法Random Over Sampling[3]、SMOTE[20]、BorderlineSMOTE[21]、ADASYN[22]和MWMOTE[23]，以及兩種混合采樣方法SMOTETomek[26]、SMOTEENN[28]、CCR[31].在對(duì)比實(shí)驗(yàn)中，分別用縮寫ROS、SMO、B-SMO、ADAS、MWMO、SMO-T、SMO-E、CCR代替上述8個(gè)算法，用NA-SMO代替本文的NA-SMOTE.實(shí)驗(yàn)中，利用SMOTE合成樣本時(shí)，其最近鄰個(gè)數(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給出了各個(gè)算法在所有數(shù)據(jù)集上的均值，可以看出，NA-SMO方法整體上要優(yōu)于其他對(duì)比方法.表6給出了各個(gè)算法分別在KEEL數(shù)據(jù)集上10次實(shí)驗(yàn)的F_measure均值及對(duì)應(yīng)的標(biāo)準(zhǔn)差，其余3個(gè)評(píng)價(jià)指標(biāo)見本文附件.由表6可以看出，本文的方法在19個(gè)數(shù)據(jù)集上取得最佳效果.在Recall、G-mean和AUC 上分別在39、19和19個(gè)數(shù)據(jù)集上達(dá)到最佳效果(具體結(jié)果見附件).表7給出了各個(gè)算法在UCI數(shù)據(jù)集上10次實(shí)驗(yàn)的Recall、F_measure、G_mean、AUC均值及對(duì)應(yīng)的標(biāo)準(zhǔn)差.其中，MWMO算法在計(jì)算多個(gè)UCI數(shù)據(jù)集時(shí)出現(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)一步對(duì)比算法的性能，本文將8個(gè)對(duì)比算法分別與NA-SMO進(jìn)行了Wilcoxon Signed Rank Test(威爾科克森符號(hào)秩檢驗(yàn))，顯著性水平選取0.05.表8給出了keel數(shù)據(jù)集上的檢驗(yàn)結(jié)果，由于在UCI數(shù)據(jù)集上，存在部分方法沒有得到實(shí)驗(yàn)結(jié)果，因此無法符號(hào)秩和檢驗(yàn).如表8所示，從檢驗(yàn)結(jié)果來看，本文的算法在絕大多數(shù)(26/28)的對(duì)比中都與對(duì)比算法有顯著的差異.結(jié)合前文的詳細(xì)性能對(duì)比結(jié)果可知，本文的方法與對(duì)比算法相比，具有一定的優(yōu)勢(shì).

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

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

表9 Wilcoxon T值檢驗(yàn)對(duì)比結(jié)果Table 9 Result of Wilcoxon T test

5 總結(jié)與展望

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

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