張永清 盧榮釗 喬少杰 韓楠 GUTIERREZ Louis Alberto 周激流

不平衡數(shù)據(jù)廣泛存在于實際應(yīng)用中,如何有效處理類別不平衡數(shù)據(jù)已成為目前機器學(xué)習(xí)領(lǐng)域一個重要的研究熱點.許多生物信息學(xué)中的分類問題都面臨不平衡數(shù)據(jù)的問題,如基因表達數(shù)據(jù)[1]、蛋白質(zhì)?DNA 結(jié)合數(shù)據(jù)[2]、mRNA 中的甲基化位點[3]、拼接位置預(yù)測[4]、microRNAs 的預(yù)測[5]、蛋白質(zhì)相互作用預(yù)測[6]等.此外,不平衡數(shù)據(jù)還廣泛存在于醫(yī)療診斷[7?8]、詐騙交易[9]和網(wǎng)絡(luò)入侵[10]等領(lǐng)域.在數(shù)據(jù)不平衡問題中,由于負樣本(多數(shù)類)的數(shù)量遠遠大于正樣本(少數(shù)類)的數(shù)量,使得少數(shù)類樣本難以被分類器有效學(xué)習(xí).此外,現(xiàn)有的機器學(xué)習(xí)算法一般假定類分布均衡或樣本錯分代價相同.然而,真實應(yīng)用中通常少數(shù)類樣本比多數(shù)類本更為重要,錯分代價更高.所以對不平衡數(shù)據(jù)的學(xué)習(xí)一般無法取得令人滿意的結(jié)果.

現(xiàn)有方法一般通過數(shù)據(jù)預(yù)處理的方式來重構(gòu)數(shù)據(jù)集,以減少學(xué)習(xí)過程中樣本偏態(tài)分布的負面影響,重采樣方法是其中經(jīng)典的方法.重采樣主要分為欠采樣和過采樣,使用欠采樣算法可能會移除多數(shù)類中潛在的有用信息,導(dǎo)致分類性能降低,并且可能破壞樣本原始分布.過采樣算法會增加樣本量,這會增加算法的時間成本,也容易導(dǎo)致過擬合[11].此外,新生成的樣本不能保證與原數(shù)據(jù)有相同的分布.大多數(shù)方法將數(shù)據(jù)采樣到所有類別樣本數(shù)量一致為止,采樣比例不僅取決于不平衡比例,還取決于數(shù)據(jù)的空間分布情況.因此重采樣算法的一個難點在于如何確定采樣比例,即 如何合理地根據(jù)數(shù)據(jù)本身的特點確定具有最佳分類性能的采樣比例.

基于上述問題,亟需提出一種先進的數(shù)據(jù)采樣方法來處理正負樣本比例不平衡問題.本文研究基于以下幾點考慮:

1)在不平衡數(shù)據(jù)中,負樣本數(shù)量占據(jù)了絕大多數(shù),雖然負樣本與正樣本屬于不同的類別,但是在負樣本中可能包括潛在的正樣本,這是之前的研究沒有考慮的.

2)如何根據(jù)數(shù)據(jù)整體的空間分布特點,自適應(yīng)地確定采樣比例.

3)基于混合采樣方法能很好地避免單獨使用欠采樣和過采樣帶來的問題.

為解決上述問題,本文提出了一種新的基于樣本空間的不平衡數(shù)據(jù)采樣方法,偽負樣本采樣方法(Pseudo-negative sampling,PNS),本文主要貢獻有:

1)提出了偽負樣本概念.在大量的負樣本中存在與正樣本有類似分布的樣本,因此與正樣本具有很高的相似度,可以將它們定義為被錯分了的正樣本.基于這一觀察,本文首次提出偽負樣本概念,將與正樣本相似度很高的負樣本標記為偽負樣本.

2)根據(jù)數(shù)據(jù)空間分布,提出一種度量正樣本和負樣本之間相似性的方法.算法工作原理為: 使用歐氏距離評價樣本之間的相似性,首先計算正樣本的空間中心,然后將正樣本到空間中心的平均距離作為判斷是否為偽負樣本的閾值,最后分別計算每個負樣本到空間中心的距離.如果其距離小于閾值,則將此負樣本標記為偽負樣本.將其添加到正樣本集中.

3)通過正負樣本之間的相似距離,自適應(yīng)地確定不平衡數(shù)據(jù)采樣的比例.

4)在多個UCI 數(shù)據(jù)、KEEL 數(shù)據(jù)和真實生物信息數(shù)據(jù)上進行了大量實驗,全面驗證了算法的準確率、敏感性、特異性、馬修斯相關(guān)系數(shù)(Matthews correlation coefficient,MCC)、F-score和時間效率等性能評價指標.引入對比算法,從多角度驗證所提出方法的性能優(yōu)勢.

本文結(jié)構(gòu)如下: 第1 節(jié)綜述主流的類不平衡數(shù)據(jù)解決方法;第2 節(jié)詳細說明本文提出的PNS 采樣算法;第3 節(jié)介紹本文使用的數(shù)據(jù)集和算法評價指標;第4 節(jié)對本文提出的采樣方法的實驗結(jié)果進行分析;第5 節(jié)對本文工作進行總結(jié)和展望.

1 相關(guān)工作

如何處理類別不平衡數(shù)據(jù)是分類中的一個關(guān)鍵問題,并受到廣泛關(guān)注.現(xiàn)有方法可分為數(shù)據(jù)預(yù)處理[12?14]、代價敏感學(xué)習(xí)[15]和集成學(xué)習(xí)[16]三類.

數(shù)據(jù)預(yù)處理是最常用的方法,因為它獨立于分類器,具有很好的適應(yīng)性,主要包括過采樣[17]和欠采樣[18].過采樣是通過創(chuàng)建新的少數(shù)類樣本來消除偏態(tài)分布的危害,提高少數(shù)類的分類性能.最簡單的方法是隨機過采樣(Random over-sampling,ROS),即隨機復(fù)制少數(shù)類樣本,缺點是少數(shù)類沒有增加任何額外信息,只是簡單復(fù)制,從而增加過擬合的風(fēng)險,并且新的數(shù)據(jù)使訓(xùn)練分類器所需時間增加.在改進的過采樣方法中,Chawla等[19]提出了Synthetic minority oversampling technique(SMOTE)算法,在少數(shù)類樣本中隨機插值鄰居樣本來生成新樣本.但這種方法容易產(chǎn)生分布邊緣化問題,新生成樣本可能會模糊正樣本和負樣本的邊界.雖然使數(shù)據(jù)集的平衡性得到了改善,但加大了分類算法進行分類的難度.Douzas等[20]將深度學(xué)習(xí)模型中的生成對抗網(wǎng)絡(luò)用于少數(shù)類樣本的合成,很好地平衡了數(shù)據(jù)集,并取得了較好結(jié)果.欠采樣是通過移除多數(shù)類樣本來消除偏態(tài)分布的危害,從而提高少數(shù)類的分類性能.最簡單的方法是隨機欠采樣(Random under-sampling,RUS),即隨機地去掉一些多數(shù)類樣本,缺點是可能會丟失一些重要信息,對已有息利用不充分.Wilson[21]提出了一種最近鄰規(guī)則欠抽樣(Edited nearest neighbor,ENN)方法,基本思想是刪除其最近的3 個近鄰樣本中具有2 個或者2 個以上類別不同的樣本.但是大多數(shù)的多數(shù)類樣本附近的樣本都是多數(shù)類的,所以該方法所能刪除的多數(shù)類樣本十分有限.因此,Laurikkala[22]在ENN 的基礎(chǔ)上提出了鄰域清理規(guī)則欠采樣方法 (Neighborhood cleaning,NCL),核心思想是找出每個樣本的3 個最近鄰樣本,若該樣本是多數(shù)類樣本且其3 個最近鄰中有2 個以上是少數(shù)類樣本,則刪除它;反之,當該樣本是少數(shù)類,并且其3 個最近鄰中有2 個以上是多數(shù)類樣本,則去除近鄰中的多數(shù)類樣本.但是該方法中未能考慮到在少數(shù)類樣本中存在的噪聲樣本,而且這種方法刪除的多數(shù)類樣本大多屬于邊界樣本,對后續(xù)分類器的分類會產(chǎn)生很大的不良影響.

傳統(tǒng)分類器在訓(xùn)練時,往往以最小化錯誤率為目標,這一目標是基于假設(shè): 不同類之間的錯誤分類具有相同代價,因此不同類的錯分可以被同等對待.然而在類別不平衡數(shù)據(jù)集中,多數(shù)類與少數(shù)類之間的錯分代價往往是不同的,錯分少數(shù)類具有更高的代價.基于這一前提,代價敏感方法通過引入代價矩陣為不同錯分類型賦予不同代價,然后以最小化代價值為目標來構(gòu)造分類器.Zhang等[23]將代價敏感學(xué)習(xí)應(yīng)用于不平衡數(shù)據(jù)的多分類,通過一對一分解,將多分類問題轉(zhuǎn)化成多個二分類子問題并使用代價敏感的反向傳播神經(jīng)網(wǎng)絡(luò)進行獨立學(xué)習(xí),從而減小平均誤分代價.Liu等[24]提出了一種新的代價敏感的支持向量機(Support vector machine,SVM)算法,該算法首先使用過濾式方法對特征進行挑選,同時對于代價敏感SVM 中的參數(shù),使用元優(yōu)化算法進行優(yōu)化.實驗表明,該方法在對乳腺癌數(shù)據(jù)的預(yù)測上取得了較好結(jié)果.

集成學(xué)習(xí)方法的主要思想是將多個不同的弱學(xué)習(xí)器組合在一起,形成一個強學(xué)習(xí)器.通過利用每個基學(xué)習(xí)器之間的差異,來改善模型的泛化性能.經(jīng)典的方法有 Bagging和Boosting 等.Breiman[25]將自采樣引入集成學(xué)習(xí)提出了Bagging 集成方法,他通過從原始數(shù)據(jù)集不斷采樣產(chǎn)生新的數(shù)據(jù)子集來訓(xùn)練每個新的分類器,由于數(shù)據(jù)子集的不同,保證了基分類器具有一定的多樣性.Schapire[26]則提出了Boosting 集成方法,AdaBoost[27]是其中的代表性方法,它使用整個數(shù)據(jù)集來不斷地訓(xùn)練分類器,在每一個分類器被訓(xùn)練出來后,后面的分類器將更多關(guān)注被錯分的樣本,從而提高少數(shù)類的精度.關(guān)注的方法是為樣本設(shè)置權(quán)重,被前一個分類器正確分類的樣本,權(quán)重將降低,反之將權(quán)重提高.

在相似性度量方面,歐氏距離作為一種簡單有效的評價方式被廣泛使用,其計算公式見下:

式中,X和Y表示2 個被考慮的樣本,xi與yi表示樣本X與Y的第i個特征,n表示特征數(shù).Elmore等[28]提出了基于歐氏距離的主成分分析(Principal component analysis,PCA)方法.該方法使用基于歐氏距離得到的相似度矩陣,識別彼此接近的參數(shù),為PCA 中相似性度量提供了更多選擇.Park等[29]在對歌曲的相似性識別中,結(jié)合歐氏距離和漢明距離,提出了一種新的距離度量方法,稱之為條件歐幾里得距離.

通過上述工作分析可知,現(xiàn)有研究工作中存在的突出問題: 1)采樣時,沒有充分考慮數(shù)據(jù)的空間分布特點,特別是正樣本集的分布,導(dǎo)致采樣具有較大盲目性;2)需要人為指定采樣比例,采樣比例應(yīng)該根據(jù)數(shù)據(jù)本身的特點確定,如何針對不同數(shù)據(jù)進行采樣比例的適應(yīng)性調(diào)整.

2 問題描述

2.1 偽負樣本采樣方法

算法中使用的主要符號及說明如表1 所示.

表1 符號及說明Table 1 Symbols and their explanations

在不平衡數(shù)據(jù)的負樣本集中,可能存在潛在的正樣本,本文稱之為偽負樣本.如果能有效地找出偽負樣本,將其加入到正樣本集中同時從負樣本集中刪除,便能得到一個數(shù)據(jù)分布更加合理的數(shù)據(jù)集.基于這個數(shù)據(jù)集訓(xùn)練的分類器可以更好地學(xué)習(xí)正樣本集,從而提高正樣本集的精確度.基于這一考慮,本文首次提出了偽負樣本采樣方法PNS.圖1 描述了如何從多數(shù)類中找出偽負樣本,圖1 中空心圓代表多數(shù)類,空心五星代表少數(shù)類.首先需要找到少數(shù)類的空間中心,圖1 中用實心五星表示,并得到所有少數(shù)類樣本到空間中心的平均歐氏距離,然后分別計算所有多數(shù)類樣本到空間中心的歐氏距離.若某個多數(shù)類樣本到空間中心的距離越近,則認為該多數(shù)類樣本與少數(shù)類樣本相似性越高.如果某個多數(shù)類樣本到空間中心的距離小于平均歐氏距離,則將此負樣本認定為潛在的正樣本即偽負樣本.

圖1 偽負樣本采樣方法Fig.1 Pseudo-negative sampling method

式中,k表示迭代次數(shù),表示相似性大于閾值的負樣本,表示上一次迭代后得到的偽負樣本集.同理,表示上一次迭代后得到的負樣本集.

迭代結(jié)束之后,將偽負樣本集加入到正樣本集當中,同時得到了平衡后的負樣本集.具體計算過程將在第2.3 節(jié)給出.

2.2 基于歐氏距離的PNS 采樣算法

PNS 算法是基于正樣本集空間位置的,因此,首先需要找到正樣本的空間中心點,空間中心點C是所有正樣本的平均值,計算方法如下:

式中,dist() 表示正樣本與空間中心C之間的歐氏距離.然后,計算每個負樣本與正樣本集的相似性,正樣本集使用空間中心C代替,計算公式如下:

式中,i=1,2,3,···,n.dist() 表示負樣本與空間中心C之間的歐氏距離,計算結(jié)果即為樣本具有的相似性大小.然后將每個負樣本的相似性與閾值meanDist進行比較,如果小于閾值,則認定該負樣本為偽負樣本,定義如下:

最終,將偽負樣本集加入到正樣本并從負樣本集中刪除,最終得到采樣后的數(shù)據(jù)集:

2.3 算法描述

基于上述討論,給出本文算法的形式化描述,如算法1 所示.

算法基本步驟為: 第7～13 步將原始數(shù)據(jù)集分成正樣本集和負樣本集;第14～17 步計算正樣本的空間中心C;第18～21 步計算少數(shù)類到空間中心的平均距離meanDist;第22～24 步計算每個多數(shù)類到平均中心的距離Distancei;第25～29 步根據(jù)多數(shù)類樣本距離與平局距離判斷某個多數(shù)類是否為偽負樣本,如果是,則加入偽負樣本;最后返回采樣后的數(shù)據(jù)集.其中,dist(A,B) 表示計算A點到B點的歐氏距離.

算法復(fù)雜性分析: 本文提出的算法還具有良好的時間復(fù)雜度,由算法1 中可以看出,耗時操作主要集中在5 個循環(huán)操作上: 1)樣本分離操作,時間復(fù)雜度為 O (k),其中k代表樣本總數(shù).2)計算正樣本中心,時間復(fù)雜度為 O (m),m表示正樣本數(shù)量.3) 計算正樣本到中心的平均距離,時間復(fù)雜度為O(m).4)計算每個負樣本到中心的距離,時間復(fù)雜度為 O (n),n表示負樣本數(shù)量.5)將每個負樣本到中心的距離與平均距離進行比較,時間復(fù)雜度為O(n). 綜上,PNS 算法的總時間復(fù)雜度為O(k+2×m+2×n)n),由于在數(shù)據(jù)集中k等于m加上n,因此原式可化簡為 O (3×k).由此看出,PNS 算法的時間復(fù)雜度較低,是一種高效的算法.

算法1.基于偽負樣本的采樣方法

2.4 對比采樣方法

本文使用ROS、RUS、Adaptive synthetic sampling (ADASYN)和SMOTE 作為對比采樣算法與PNS 進行比較.其中,RUS 屬于欠采樣,其余方法屬于過采樣.ROS與RUS 均是隨機采樣,前者通過隨機復(fù)制少數(shù)類樣本對數(shù)據(jù)進行采樣,后者通過刪除多數(shù)類樣本進行采樣.這兩種方法具有實現(xiàn)簡單,采樣效果較好的特點.

SMOTE[19]方法基于少數(shù)類間的相似性合成新樣本.對于少數(shù)類樣本集Smin,首先計算得到每個樣本xi∈Smin的K近鄰.K近鄰被定義為距xi最近的K個樣本,距離計算通常是歐氏距離,整數(shù)K是人工指定的超參數(shù).為了合成新樣本,隨機從K個近鄰樣本中選擇一個求出兩者的差,然后乘以介于[0,1]之間的特征向量差異隨機數(shù),最后加上原始特征xi.

式中,xi∈Smin是正在被考慮的樣本,是xi其中一個K近鄰樣本,且[0,1] 是一個隨機數(shù).因此,根據(jù)式(10)得到的合成實例是所考慮的xi與隨機選取的K近鄰的連線線段上的一個點.SMOTE 的提出避免了ROS 帶來的過擬合問題,同時顯著提高分類器性能.已經(jīng)在各種領(lǐng)域得到了廣泛認可.

He等[30]基于對SMOTE 的改進提出了ADASYN 采樣.ADASYN 的主要思想是根據(jù)少數(shù)類的分布自適應(yīng)合成新樣本: 在合成新樣本過程中,分類困難的少數(shù)類樣本會生成更多樣本,反之則會生成較少樣本,以此將決策邊界轉(zhuǎn)移到難以學(xué)習(xí)的樣本上.該方法與SMOTE 的不同點主要在于對少數(shù)類合成樣本的控制.在SMOTE 中,對每個少數(shù)類都合成相同數(shù)量的樣本,而在ADASYN 中,處于邊界的少數(shù)類將合成更多樣本.對邊界的檢測通過樣本的K近鄰得到,如果一個少數(shù)類的K近鄰存在越多的多數(shù)類,那么這個少數(shù)類被認為離邊界越近,會合成更多樣本.

3 數(shù)據(jù)集及算法評價指標

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

為評價不同樣本采樣方法在不同數(shù)據(jù)集上的預(yù)測性能,并與其他常用采樣方法進行比較,本文使用了7 個UCI 數(shù)據(jù)集[31]、4 個KEEL 數(shù)據(jù)集[32]和2個真實的生物信息學(xué)數(shù)據(jù)集.如表2 所示.

表2 不平衡數(shù)據(jù)集信息Table 2 Information of the imbalanced dataset

所有數(shù)據(jù)集用于二分類問題,如果出現(xiàn)多分類數(shù)據(jù)集,則將其中某一類作為正樣本集,剩下的所有類統(tǒng)一合并為負樣本集.正負樣本數(shù)據(jù)集的不平衡比例從4 到130 不等,較大的不平衡比例表示正樣本集和負樣本集之間數(shù)量差異較大.

3.2 UCI 數(shù)據(jù)集

Ecoli 數(shù)據(jù)集包含35 個少數(shù)類和301 個多數(shù)類,有7 個特征.該數(shù)據(jù)是一組蛋白質(zhì)定位點數(shù)據(jù),特征包括氨基酸序列和來源信息,使用這些信息預(yù)測蛋白質(zhì)的定位位點.

SatImage 數(shù)據(jù)中包含衛(wèi)星圖像3×3 鄰域中的像素的多光譜值,以及與每個鄰域中的中心像素相關(guān)聯(lián)的分類.通過整合不同類型和分辨率的空間數(shù)據(jù)(包括多光譜和雷達數(shù)據(jù)、地圖指示地形、土地利用等)對場景的解釋預(yù)計將具有重要意義.這個數(shù)據(jù)集中包含626 個少數(shù)類和5 809 個多數(shù)類,有36個特征.

Abalone 是一個通過物理測量來預(yù)測鮑魚年齡的數(shù)據(jù)集,物理測量預(yù)測鮑魚年齡是一項既枯燥又耗時的工作,因此使用已有數(shù)據(jù)進行預(yù)測將是更省時的選擇.這個數(shù)據(jù)集包含390 個少數(shù)類和3 787個多數(shù)類,有8 個特征.

Balance 數(shù)據(jù)集是用來模擬心理實驗結(jié)果的,每個例子都被分類為天平的左端、右端或是平衡.屬性包括左權(quán)重、左距離、右權(quán)重和右距離.

SolarFlare 數(shù)據(jù)集記錄了太陽耀斑的數(shù)量,每個屬性計算24 小時內(nèi)某類太陽耀斑的數(shù)量,每個實例表示太陽上1 個活動區(qū)域內(nèi)所有種類耀斑數(shù)量.該數(shù)據(jù)包含69 個少數(shù)類和1 320 個多數(shù)類,有10 個特征.

Yest_ME2 數(shù)據(jù)集是一個酵母菌數(shù)據(jù)集,用于預(yù)測酵母菌蛋白質(zhì)的定位位點.該數(shù)據(jù)包含51 個少數(shù)類和1 433 個多數(shù)類,有8 個特征數(shù).

3.3 真實生物數(shù)據(jù)

SPECT 數(shù)據(jù)集是心臟單質(zhì)子發(fā)射計算機斷層掃描圖像的診斷結(jié)果.每個病人被分為正常和異常兩類.數(shù)據(jù)包含對267 個SPECT 圖像集(患者)的數(shù)據(jù)處理結(jié)果.提取總結(jié)原始SPECT 圖像的特征,得到44 個連續(xù)特征.在267 個樣本中,包含55 個正常病人(少數(shù)類)和212 個異常病人(多數(shù)類).

SNP 是指在基因組上單個核苷酸的變異,變異形式包括缺失、顛換、變異和插入.在人類基因組中大概每1 000 個堿基就有一個SNP,因此SNP 的數(shù)量是相當龐大的.研究表明,SNP 同人群分類,遺傳疾病都有密切聯(lián)系.該數(shù)據(jù)包含183 個少數(shù)類和2 891個多數(shù)類,25 個特征.

3.4 KEEL 數(shù)據(jù)集

本文使用KEEL 數(shù)據(jù)集的4種酵母菌數(shù)據(jù)集,原始數(shù)據(jù)集是一個多分類數(shù)據(jù)集.在Yeast1289vs7中,將屬于VAC 的樣本標記為正樣本,屬于NUC、CYT、POX和ERL 的標記為負樣本.Yeast1458vs7屬于VAC 的樣本標記為正樣本,屬于NUC、ME2、ME3和POX 的標記為負樣本.在Yeast4和Yeast5 中,分別將ME2、ME1 標記為正樣本,將其他所有樣本均標記為負樣本.所有數(shù)據(jù)集包含8 個特征.

3.5 評價指標

不平衡數(shù)據(jù)學(xué)習(xí)的困難不僅體現(xiàn)在分類器的訓(xùn)練上,同時還在于如何客觀評價不平衡分類器的性能上.使用總體精度已經(jīng)不能客觀評價不平衡分類器的性能,因為不平衡數(shù)據(jù)中多數(shù)類與少數(shù)類具有不同的重要性,對少數(shù)類的錯誤將導(dǎo)致更嚴重的錯誤.而總體精度忽略了這一關(guān)鍵因素,即使將結(jié)果全部預(yù)測為多數(shù)類,仍能得到較高總體精度,難以準確反應(yīng)出分類器在不平衡數(shù)據(jù)集上的性能.本節(jié)介紹本文使用的評價指標,并給出計算公式.

分類性能的評估主要基于混淆矩陣,以二分類為例,表3 展示了其混淆矩陣.TP表示正確預(yù)測到的正樣本個數(shù),TN表示正確預(yù)測到的負樣本個數(shù),FN表示正樣本預(yù)測為負樣本的個數(shù),FP表示負樣本預(yù)測為正樣本的個數(shù).

表3 分類混淆矩陣Table 3 The confuse matrix of classification

常見的不平衡數(shù)據(jù)分類問題評價指標有: 準確率(Accuracy,Acc)、敏感性(Sensibility,Sen)、特異性(Specificity,Spe)、MCC、F-score和Area under curve (AUC),計算公式如下:

F-score 綜合考慮了查全率與查準率,是兩者的調(diào)和平均數(shù),其值接近其中較小者.在不平衡中,只有當查全率與查準率同時較大時,F-score 才會增大.recall 代表查全率,表示在原始樣本的正樣本中,最后被正確預(yù)測為正樣本的概率,計算方法與Sen 相同;precision 為查準率,表示預(yù)測結(jié)果中,正確預(yù)測為正樣本的概率如下:

AUC 是Receiver operating characteristic(ROC)曲線下面積,ROC 圖由真陽性率(TP-rate)與假陽性率(FP-rate)作圖而成,ROC 空間中的任意一個點對應(yīng)分類器在給定分布上的性能,當真陽性率與假陽性率比值越大時,ROC 就將越接近圖形左上角,此時將得到更大的AUC 值,這也意味著分類器結(jié)果越理想,AUC 也是評價分類器在不平衡數(shù)據(jù)上性能的重要指標之一.

4 實驗與性能分析

為驗證本文方法的有效性,使用13 個數(shù)據(jù)集進行實驗.實驗中使用隨機森林(Random forest,RF)[33?34]、SVM[35?36]、邏輯回歸(Logistics regression,LR)[37?38]和決策樹(Decision tree,DT)[39?40]作為分類器.RF 屬于Bagging 集成的分類器,由于使用了多個分類器,效果通常好于使用單個分類器.SVM 在處理小樣本高維度的數(shù)據(jù)時有其特有的優(yōu)勢,因為SVM 最終的決策函數(shù)由少數(shù)支持向量確定,復(fù)雜性僅僅取決于支持向量數(shù)目而不是原始的樣本空間.LR 計算代價不高且容易實現(xiàn),此外,LR 對數(shù)據(jù)中小噪聲具有一定魯棒性.DT 算法是一種基于概率的分析方法,在訓(xùn)練時不需要任何領(lǐng)域的先驗知識和參數(shù)假設(shè),計算量相對較小且準確性高,適合用于高維數(shù)據(jù).

在分類器參數(shù)選擇上,為了最大化突出采樣方法自身的特點,參數(shù)均使用默認參數(shù)設(shè)置: SVM 的懲罰系數(shù)為1,核方法為徑向基函數(shù)核(Radial basis function,RBF),gamma 值為1;LR 使用saga作為求解器;DT 使用基尼系數(shù)評價特征劃分質(zhì)量;RF 使用具有隨機屬性選擇的決策樹作為基分類器,包含50 個獨立的決策樹,每棵決策樹同樣使用基尼系數(shù)評價劃分質(zhì)量.

為保證訓(xùn)練效果,本文使用5 折交叉驗證的方法,將數(shù)據(jù)集隨機分成5 份,每次將其中4 份作為訓(xùn)練集,剩下的1 份作為測試集,重復(fù)5 次.最后將5 次實驗評價結(jié)果的平均值作為交叉驗證的結(jié)果.所有結(jié)果均為5 次5 折交叉驗證結(jié)果.實驗硬件環(huán)境為CPU i5-3230m、操作系統(tǒng)為 Windows10、開發(fā)語言為Python、集成開發(fā)環(huán)境為 Pycharm、使用外部庫Numpy、Sklearn和Imbalancelearn.

4.1 UCI和真實數(shù)據(jù)集上分類性能對比

實驗設(shè)計如下: 首先使用PNS 算法對數(shù)據(jù)進行預(yù)處理,然后分別使用四種不同的分類器對處理后的數(shù)據(jù)進行訓(xùn)練學(xué)習(xí).實驗?zāi)康氖窃u價不同分類器對不平衡數(shù)據(jù)的敏感性并為后面實驗選擇合適的分類器提供參考.

在7 個UCI 數(shù)據(jù)集和2 個真實數(shù)據(jù)集上的結(jié)果如表4 所示.由表4 可以看出,SVM 在SPECT、Abalone、SolarFlare、Yeast_ME2、Ecoli 這5 個數(shù)據(jù)集的大多數(shù)指標上取得最佳值,RF 在Abalone_19、SatImage、Balance和SNP 這4 個數(shù)據(jù)集的多數(shù)指標上取得最佳值.除Ecoli 數(shù)據(jù)集的Spe指標,Abalone 的Sen指標以及Abalone_19的AUC指標以外,其余最高值均出自SVM與RF.因此相比LR與DT,SVM與RF 具有更好的分類效果.這說明SVM與RF 對不平衡數(shù)據(jù)更具有魯棒性.

表4 偽負樣本采樣在分類器SVM、LR、DT、RF上的結(jié)果Table 4 Results of pseudo-negative sampling on classifiers including SVM,LR,DT and RF

RF 使用了決策樹的集成方法,并且隨機森林中每棵決策樹的特征選擇具有一定隨機性,這增大了決策樹間的差異,從而使集成效果更好,因此RF 的結(jié)果要優(yōu)于DT,集成方法也是解決不平衡的重要方法之一.SVM 使用核方法將數(shù)據(jù)映射到高維空間進行劃分,而且SVM 的超平面只與支持向量有關(guān),與離決策超平面的數(shù)據(jù)的多少并不重要,因此使得SVM 對不平衡本身并不十分敏感.LR 在預(yù)測時會考慮所有樣本點到?jīng)Q策平面的距離,雖然使用了非線性函數(shù)進行映射,但也無法很好消除其影響,因此,容易受不平衡影響.

由數(shù)據(jù)集與分類器的特點可以知道,SVM 趨向于在小樣本量的不平衡數(shù)據(jù)集上具有更好的效果,而RF 趨向于在大樣本量不平衡數(shù)據(jù)集上表現(xiàn)更佳.這也恰恰符合SVM與RF 在平衡數(shù)據(jù)集上的表現(xiàn),這說明PNS 算法已經(jīng)將原始的不平衡數(shù)據(jù)有效采樣成了更平衡的數(shù)據(jù),起到了平衡數(shù)據(jù)集,提高分類器性能的作用.

4.2 采樣方法分類性能比較

根據(jù)第4.1 節(jié)實驗結(jié)果,本節(jié)使用的分類器是支持向量機(SVM)和邏輯回歸(LR),因為它們對不平衡數(shù)據(jù)集具有不同敏感性,SVM 對不平衡數(shù)據(jù)不敏感而LR 對不平衡較為敏感,如果PNS 算法在這兩個分類器上都表現(xiàn)良好,那么可以推斷出PNS 算法對大多數(shù)分類器均具有較好的提升效果.

實驗設(shè)計如下: 由于偽負樣本采樣無需指定采樣比例,會根據(jù)數(shù)據(jù)集自適應(yīng)確定采樣比例,因此本文對比相同采樣比例下各采樣方法的性能.首先使用偽負樣本采樣方法對原始數(shù)據(jù)進行采樣,得到平衡后的比例,然后按照平衡后的比例使用對比算法重新對原始數(shù)據(jù)進行采樣得到采樣結(jié)果,最后使用5 折交叉驗證對采樣數(shù)據(jù)集進行評價,并重復(fù)5次試驗取平均值.在對比實驗中,將本文提出的PNS 算法與4種數(shù)據(jù)采樣方法進行對比.對比算法包括ROS、RUS、SMOTE和ADASYN.結(jié)果如表5所示.

由表5 可以看出,PNS 算法具有最好的綜合性能.F-score、MCC和AUC 被認為是在類別不平衡情況下的綜合評價指標.它們綜合了正樣本正確率和負樣本正確率,能客觀評價不平衡分類器的性能.在這3 個指標上使用SVM 分類器時,算法在SPECT、Ecoli、SatImage、Abalone、Balance、Solar-Flare、Yeast_ME2和Abalone_19 數(shù)據(jù)集上取得了最好的結(jié)果.而在SNP 數(shù)據(jù)集上,則是ADASYN 算法取得了較好的結(jié)果,這是因為它們合成的樣本擴充了少數(shù)類,同時未減少多數(shù)類樣本,使其有更高的Sen 值,但是與PNS 相比,它們的Spe 值更低,這說明它們是通過犧牲Spe 來提高其他性能指標的.

表5 偽負樣本采樣與ROS,RUS,SMOTE,ADASYN 采樣方法對比結(jié)果Table 5 Comparison of pseudo-negative sampling with the methods of ROS、RUS、SMOTE、ADASYN

表5 偽負樣本采樣與ROS,RUS,SMOTE,ADASYN 采樣方法對比結(jié)果 (續(xù)表)Table 5 Comparison of pseudo-negative sampling with the methods of ROS、RUS、SMOTE、ADASYN (continued table)

當使用LR 分類器時,PNS 算法在SPECT、Ecoli、SNP、SatImage、Abalone、SolarFlare、Abalone_19 數(shù)據(jù)集上取得了最好的結(jié)果.在Balance數(shù)據(jù)集上分別是SMOTE和ADASYN 算法得到較好結(jié)果,這是因為過少的特征數(shù)不利于偽負樣本的選擇,因此無法準確找到所有偽負樣本導(dǎo)致數(shù)據(jù)沒有得到很好的平衡,同時LR 分類器對不平衡數(shù)據(jù)較為敏感.在Yeast_ME2 數(shù)據(jù)集上所得結(jié)果與SVM分類器SNP 數(shù)據(jù)集結(jié)果原因類似.

在不平衡數(shù)據(jù)集的分類當中,少數(shù)類的正確率(即Sen)往往受到更多重視,因為少數(shù)類通常受到更多關(guān)注而Sen 則反映了分類器發(fā)現(xiàn)少數(shù)類的能力.在Sen 指標下,PNS 采樣算法在SVM 的6 個數(shù)據(jù)集和LR 的7 個數(shù)據(jù)集上取得最好結(jié)果,這表明本文提出的算法對少數(shù)類具有很強的辨別能力.從側(cè)面也證實了,分類正確率作為不平衡數(shù)據(jù)分類的評價指標有時并不能有效地衡量分類器的分類效果.

圖2 給出了4 個數(shù)據(jù)集在SVM 分類器下不同采樣方法的ROC 曲線.由圖可知,PNS 采樣算法在4 個數(shù)據(jù)集上擁有更好的ROC 曲線,曲線下面積均大于其他采樣方法,證明了該方法的優(yōu)越性.

圖2 4 個UCI 數(shù)據(jù)集在SVM 分類器下的ROC 曲線Fig.2 ROC curve of four UCI datasets in SVM

綜上所述,PNS 采樣算法相比ADASYN、ROS、SMOTE、RUS 算法,對數(shù)據(jù)具有更好的適應(yīng)性,因為PNS 考慮了數(shù)據(jù)集的樣本分布,從根本上緩解了不平衡數(shù)據(jù)少數(shù)類被忽略的問題,并且在提高少數(shù)類正確率的同時,其他指標保持不變,因此從整體上提高了分類器的性能.此外,由于PNS 在對不平衡數(shù)據(jù)具有不同敏感性的SVM與LR 分類器上取得最好結(jié)果,說明了PNS 的采樣結(jié)果可以適用于多數(shù)分類器.

4.3 高不平衡比例數(shù)據(jù)對比分析

本節(jié)選擇不平衡比例大于20 的KEEL 數(shù)據(jù),將所提出的PNS 方法與ROS、RUS、SMOTE和ADASYN 進行比較,以驗證PNS 采樣方法在處理高不平衡數(shù)據(jù)時的有效性.實驗設(shè)計思路和所用分類器與第4.2 節(jié)相同.實驗結(jié)果如表6 所示.

由表6 可以看出,PNS 在處理高不平衡數(shù)據(jù)時,是具有競爭力的方法.與其他4種采樣方法相比,PNS 在4 個數(shù)據(jù)的絕大多數(shù)評價指標上取得了最好結(jié)果.在只考慮F-score、MCC和AUC 這3 個指標時,PNS 采樣在SVM 分類器和LR 分類器的4 個數(shù)據(jù)集上獲得了最好結(jié)果.以Yeast1289vs7數(shù)據(jù)集為例,在SVM 分類器上的F-score、MCC和AUC 值分別為0.909、0.848和0.980;在LR 分類器上的值分別為0.780、0.627和0.902.均優(yōu)于其他采樣方法,這充分說明了PNS 在處理高不平衡比例數(shù)據(jù)時具有較好的綜合性能.在考慮Sen 作為評價指標時,PNS 采樣算法在SVM 的3 個數(shù)據(jù)集和LR 的2 個數(shù)據(jù)集上得到最好結(jié)果.說明PNS 在高不平衡比例數(shù)據(jù)中依然能很好識別出少數(shù)類樣本.

表6 高比例不平衡數(shù)據(jù)采樣對比Table 6 The comparison of high ratio imbalanced data

此外,圖3 給出了Yeast1289vs7和Yeast1458vs7兩個數(shù)據(jù)集在SVM 分類器下不同采樣方法的ROC曲線.由圖3 可知,相較于對比算法,PNS 的ROC曲線擁有更大的曲線下面積,其次是SMOTE、ADASYN和ROS,最后是RUS.由于RUS 移除了大量樣本,使得分類器對數(shù)據(jù)集學(xué)習(xí)不能很好學(xué)習(xí),從而導(dǎo)致欠擬合.SMOTE、ADASYN和ROS 方法生成的樣本可能存在噪音或異常值,導(dǎo)致分類效果不如PNS.這說明PNS 不改變數(shù)據(jù)集樣本數(shù)量是一種性能更加優(yōu)秀的采樣方法.

圖3 2 個KEEL 數(shù)據(jù)集在SVM 分類器下的ROC 曲線Fig.3 ROC curve of two KEEL datasets in SVM classifier

4.4 采樣方法時間性能對比

本文算法的另一個優(yōu)勢是相對較少的訓(xùn)練時間.表7 展示了不同采樣方法在UCI 數(shù)據(jù)集上的時間消耗對比.

過采樣為了平衡數(shù)據(jù)集會增加少數(shù)類樣本數(shù)量,當正負樣本比例越大同時需要越平衡的數(shù)據(jù)集時,過采樣將會生成大量的新樣本,這將顯著增加訓(xùn)練所需時間,并且大量的合成樣本可能導(dǎo)致過擬合現(xiàn)象.同時,相對于欠采樣而言,欠采樣去掉多數(shù)類樣本,使訓(xùn)練時間縮短,但是當少數(shù)類樣本很少時,欠采樣往往會刪除大部分多數(shù)類,這會導(dǎo)致嚴重的訓(xùn)練不足,分類器無法很好的學(xué)習(xí)數(shù)據(jù),從而使訓(xùn)練效果不盡人意.

相比于上述采樣方法,本文所提出的采樣方法PNS 則不改變原始樣本集的數(shù)量,僅改變了數(shù)據(jù)分布,不會因為引入數(shù)據(jù)而增加時間成本,也不會刪除數(shù)據(jù)而導(dǎo)致訓(xùn)練不充分,所以具有較好的結(jié)果.表7 是各采樣方法在不同數(shù)據(jù)集上使用不同分類器的算法運行時間,每次實驗均為5 次5 折交叉驗證時間總和,時間單位為秒.

表7 不同采樣方法時間對比Table 7 Runtime comparison of different sampling methods

由表7 可以看出,RUS 的總計用時最少,ADASYN的總計用時最多,分別為44.692 秒和567.057 秒.PNS、SMO-TE和ROS 的用時分別為197.954 秒、511.770 秒和530.303 秒.由于同屬于過采樣,所以ADASYN、S-MOTE與ROS 所用時間處在同一個量級.使用過采樣平衡數(shù)據(jù)時,時間成本的增加在所難免,而隨著不平衡比例的增大,時間成本也會相應(yīng)增大,這不利于處理極度不平衡數(shù)據(jù).欠采樣雖然減少了時間開銷,但是不能得到滿意結(jié)果.PNS 方法很好地解決了上述問題,在不增加時間成本的同時提高分類器性能,將時間花銷控制在可接受范圍.

5 結(jié)束語

本文提出了一種新型的基于樣本空間的不平衡數(shù)據(jù)采樣方法,即偽負樣本采樣方法PNS.實驗結(jié)果顯示,PNS 采樣方法普遍優(yōu)于其他常用數(shù)據(jù)采樣方法.在不平衡數(shù)據(jù)集中由于存在大量負樣本,使有的負樣本與正樣本具有相似的分布,與正樣本具有很高相似度,可以將其定義為被錯分的正樣本,基于這一考慮本文提出了偽負樣本的概念及其采樣方法.具體地,PNS 使用歐幾里得距離衡量正負樣本間的相似性,將得到的偽負樣本從負樣本中刪除并加入到正樣本中.本文方法根據(jù)樣本的空間分布自適應(yīng)地對數(shù)據(jù)進行采樣,不需要指定采樣比例,具有較強的適應(yīng)性,避免了采樣時選擇采樣比例的困難.混合采樣方法避免了單獨使用一種采樣方法帶來的問題.此外,該算法還具有良好的時間復(fù)雜性,采樣與訓(xùn)練時間明顯少于過采樣方法.因此,PNS 采樣方法為處理不平衡數(shù)據(jù)提供了一種可行的新思路.

未來工作包括: 1)將本文提出的偽負樣本算法與聚類算法結(jié)合[41?43],使用聚類方法獲得數(shù)據(jù)集的更多分布信息,這將有助于提高采樣的精準性;2)探索將現(xiàn)有的算法擴展到多分類的任務(wù);3)將算法應(yīng)用于大規(guī)模數(shù)據(jù)集.