一種基于樣本空間的類別不平衡數據采樣方法

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

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

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

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

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

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

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

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

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

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

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

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

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

1 相關工作

如何處理類別不平衡數據是分類中的一個關鍵問題,并受到廣泛關注.現有方法可分為數據預處理[12?14]、代價敏感學習[15]和集成學習[16]三類.

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

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

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

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

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

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

2 問題描述

2.1 偽負樣本采樣方法

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

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

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

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

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

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

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

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

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

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

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

2.3 算法描述

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

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

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

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

2.4 對比采樣方法

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

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

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

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

3 數據集及算法評價指標

3.1 數據集

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

表2 不平衡數據集信息Table 2 Information of the imbalanced dataset

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

3.2 UCI 數據集

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

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

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

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

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

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

3.3 真實生物數據

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

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

3.4 KEEL 數據集

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

3.5 評價指標

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

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

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

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

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

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

4 實驗與性能分析

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

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

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

4.1 UCI和真實數據集上分類性能對比

實驗設計如下: 首先使用PNS 算法對數據進行預處理,然后分別使用四種不同的分類器對處理后的數據進行訓練學習.實驗目的是評價不同分類器對不平衡數據的敏感性并為后面實驗選擇合適的分類器提供參考.

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

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

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

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

4.2 采樣方法分類性能比較

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

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

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

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

表5 偽負樣本采樣與ROS,RUS,SMOTE,ADASYN 采樣方法對比結果 (續表)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 數據集上取得了最好的結果.在Balance數據集上分別是SMOTE和ADASYN 算法得到較好結果,這是因為過少的特征數不利于偽負樣本的選擇,因此無法準確找到所有偽負樣本導致數據沒有得到很好的平衡,同時LR 分類器對不平衡數據較為敏感.在Yeast_ME2 數據集上所得結果與SVM分類器SNP 數據集結果原因類似.

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

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

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

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

4.3 高不平衡比例數據對比分析

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

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

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

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

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

4.4 采樣方法時間性能對比

本文算法的另一個優勢是相對較少的訓練時間.表7 展示了不同采樣方法在UCI 數據集上的時間消耗對比.

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

相比于上述采樣方法,本文所提出的采樣方法PNS 則不改變原始樣本集的數量,僅改變了數據分布,不會因為引入數據而增加時間成本,也不會刪除數據而導致訓練不充分,所以具有較好的結果.表7 是各采樣方法在不同數據集上使用不同分類器的算法運行時間,每次實驗均為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 所用時間處在同一個量級.使用過采樣平衡數據時,時間成本的增加在所難免,而隨著不平衡比例的增大,時間成本也會相應增大,這不利于處理極度不平衡數據.欠采樣雖然減少了時間開銷,但是不能得到滿意結果.PNS 方法很好地解決了上述問題,在不增加時間成本的同時提高分類器性能,將時間花銷控制在可接受范圍.

5 結束語

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

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