一種基于樣本空間的類別不平衡數(shù)據(jù)采樣方法

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

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

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

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

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

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

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

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

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

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

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

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

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

1 相關(guān)工作

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

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

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

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

在相似性度量方面,歐氏距離作為一種簡(jiǎn)單有效的評(píng)價(jià)方式被廣泛使用,其計(jì)算公式見下:

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

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

2 問題描述

2.1 偽負(fù)樣本采樣方法

算法中使用的主要符號(hào)及說明如表1 所示.

表1 符號(hào)及說明Table 1 Symbols and their explanations

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

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

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

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

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

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

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

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

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

2.3 算法描述

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

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

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

算法1.基于偽負(fù)樣本的采樣方法

2.4 對(duì)比采樣方法

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

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

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

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

3 數(shù)據(jù)集及算法評(píng)價(jià)指標(biāo)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.5 評(píng)價(jià)指標(biāo)

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

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

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

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

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

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

4 實(shí)驗(yàn)與性能分析

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

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

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

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

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

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

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

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

由數(shù)據(jù)集與分類器的特點(diǎn)可以知道,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é)實(shí)驗(yàn)結(jié)果,本節(jié)使用的分類器是支持向量機(jī)(SVM)和邏輯回歸(LR),因?yàn)樗鼈儗?duì)不平衡數(shù)據(jù)集具有不同敏感性,SVM 對(duì)不平衡數(shù)據(jù)不敏感而LR 對(duì)不平衡較為敏感,如果PNS 算法在這兩個(gè)分類器上都表現(xiàn)良好,那么可以推斷出PNS 算法對(duì)大多數(shù)分類器均具有較好的提升效果.

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

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

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

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

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

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

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

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

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

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

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

由表6 可以看出,PNS 在處理高不平衡數(shù)據(jù)時(shí),是具有競(jìng)爭(zhēng)力的方法.與其他4種采樣方法相比,PNS 在4 個(gè)數(shù)據(jù)的絕大多數(shù)評(píng)價(jià)指標(biāo)上取得了最好結(jié)果.在只考慮F-score、MCC和AUC 這3 個(gè)指標(biāo)時(shí),PNS 采樣在SVM 分類器和LR 分類器的4 個(gè)數(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ù)時(shí)具有較好的綜合性能.在考慮Sen 作為評(píng)價(jià)指標(biāo)時(shí),PNS 采樣算法在SVM 的3 個(gè)數(shù)據(jù)集和LR 的2 個(gè)數(shù)據(jù)集上得到最好結(jié)果.說明PNS 在高不平衡比例數(shù)據(jù)中依然能很好識(shí)別出少數(shù)類樣本.

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

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

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

4.4 采樣方法時(shí)間性能對(duì)比

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

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

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

表7 不同采樣方法時(shí)間對(duì)比Table 7 Runtime comparison of different sampling methods

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

5 結(jié)束語

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

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