史穎，亓慧

(1.太原師范學(xué)院 科研處,山西 晉中 030619;2.太原師范學(xué)院 計(jì)算機(jī)系,山西 晉中 030619)

一種去冗余抽樣的非平衡數(shù)據(jù)分類方法

史穎1，亓慧2

(1.太原師范學(xué)院 科研處,山西 晉中 030619;2.太原師范學(xué)院 計(jì)算機(jī)系,山西 晉中 030619)

欠抽樣是一類常見的解決非平衡數(shù)據(jù)分類的技術(shù)。傳統(tǒng)抽樣方法(如Kennard-Stone抽樣和密度保持抽樣)只考慮保持?jǐn)?shù)據(jù)分布。已有欠抽樣方法側(cè)重抽取分類邊界附近的樣本,這樣抽取的樣本可能改變數(shù)據(jù)的原始分布特征,從而影響分類效果。提出數(shù)據(jù)冗余度的概念,即如果一個(gè)多數(shù)類樣本處于多數(shù)類的密集區(qū)且距離分類邊界或少數(shù)類樣本較遠(yuǎn),則樣本冗余度較高。去冗余抽樣(Redundancy-removed Sampling,RRS)采用傳統(tǒng)抽樣規(guī)則去掉多數(shù)類中冗余度相對(duì)較高的樣本。這樣的樣本子集盡量包含對(duì)分類最有幫助的樣本和保持原始數(shù)據(jù)分布,且兩類樣本數(shù)量相對(duì)均衡。實(shí)驗(yàn)結(jié)果表明,經(jīng)RRS抽樣的分類結(jié)果的總體精度高于其他抽樣方法,尤其在分類精度較低的數(shù)據(jù)集上。同時(shí),少數(shù)類樣本的判別精度也有所提高。

非平衡數(shù)據(jù);分類;抽樣法;去冗余抽樣

0 引言

在實(shí)際的模式識(shí)別問題中,有很多原始數(shù)據(jù)是非平衡的,即不同類別下的樣本量差別較大,如詐騙網(wǎng)站遠(yuǎn)少于正常網(wǎng)站,癌癥患者遠(yuǎn)遠(yuǎn)少于非癌癥患者等。通常人們對(duì)數(shù)據(jù)中稀有類別的學(xué)習(xí)有著更為濃郁的興趣。然而多數(shù)分類算法是針對(duì)相對(duì)平衡的類分布或相等的誤分損失而設(shè)計(jì)的。當(dāng)處理非平衡數(shù)據(jù)時(shí),模型的分類效果不盡人意,尤其是類別之間的誤分率通常差別較大[1]。

非平衡數(shù)據(jù)自提出以來持續(xù)受到學(xué)者的關(guān)注和研究。目前常見的非平衡數(shù)據(jù)分類方法主要有:抽樣方法(Sampling Methods)、代價(jià)敏感法(Cost-Sensitive Methods)、集合劃分法[2]、基于核的方法[3]以及主動(dòng)學(xué)習(xí)[4-5]等。采樣方法主要是通過增加少數(shù)類樣本或減少多數(shù)類樣本使得樣本相對(duì)平衡[6-7]。代價(jià)敏感法采用不同的誤分代價(jià)或損失來處理非平衡數(shù)據(jù)分類問題。本文主要研究非平衡數(shù)據(jù)的抽樣學(xué)習(xí)方法。

最簡單的抽樣方法是隨機(jī)重抽樣和欠抽樣,即隨機(jī)復(fù)制一些少數(shù)類樣本或隨機(jī)刪除多數(shù)類樣本。然而隨機(jī)復(fù)制樣本并沒有增加樣本的信息,甚至有可能導(dǎo)致過擬合[8]。而隨機(jī)刪除樣本可能刪去一些比較重要的(如類別邊界附近)樣本。簡單集成法(EasyEnsemble)[9]將多數(shù)類樣本集隨機(jī)劃分為若干個(gè)子集,并將這些子集分別與少數(shù)類樣本集建立若干分類模型,最終將其集成。文獻(xiàn)[10]提出了3種欠抽樣法,NearMiss-1, NearMiss-2和“most distant”。 NearMiss-1是抽取那些到最近的三個(gè)少數(shù)類樣本距離均值較小的多數(shù)類樣本;NearMiss-2是抽取那些到最遠(yuǎn)的三個(gè)少數(shù)類樣本距離均值較小的多數(shù)類樣本;“most distant”是抽取那些到最近的三個(gè)少數(shù)類樣本距離均值較大的多數(shù)類樣本。考慮到隨機(jī)復(fù)制樣本的不足,文獻(xiàn)[11]提出了經(jīng)典的SMOTE算法,其核心思想是將少數(shù)類樣本和其近鄰進(jìn)行線性組合從而生成新的少數(shù)類樣本。后續(xù)很多學(xué)者將其改進(jìn),形成新的方法,如Borderline-SMOTE[12]、SMOTEpTomek[13]、SMOTEBoost[14]?；诰垲惖某闃铀惴梢愿鶕?jù)特定的問題對(duì)多數(shù)類樣本進(jìn)行削減,從而處理非平衡問題。面向非平衡數(shù)據(jù)的抽樣方法通過新增少數(shù)類樣本或刪除多數(shù)類樣本使得樣本趨于平衡,然而在增刪的過程中免不了會(huì)改變多數(shù)類或少數(shù)類的樣本分布,這樣就會(huì)對(duì)分類邊界產(chǎn)生影響,進(jìn)而干擾部分?jǐn)?shù)據(jù)的正確分類。一般多數(shù)類誤分為少數(shù)類的代價(jià)要大于少數(shù)類誤分為多數(shù)類的代價(jià)[15-16]。

除上述非平衡數(shù)據(jù)抽樣方法外,還有其他常規(guī)抽樣方法,如Kennard-Stone(KS)抽樣、Kohonen(KH)抽樣、SPXY(sample set partitioning based on joint x-y distance)和密度保持抽樣(Density-preserving sampling,DPS)等[17]。文獻(xiàn)[18]在用神經(jīng)網(wǎng)絡(luò)做分類的結(jié)果表明,采用KS抽樣要優(yōu)于隨機(jī)抽樣、系統(tǒng)抽樣和KH抽樣。文獻(xiàn)[19]中偏最小二乘回歸的研究結(jié)果表明SPXY抽樣效果好于隨機(jī)抽樣和KS抽樣。文獻(xiàn)[20]經(jīng)過DPS抽樣的多個(gè)分類模型的誤差估計(jì)精度與分層10折交叉驗(yàn)證方法相差不大,但前者穩(wěn)定性更高。綜合上述研究可見,KS和DPS是相對(duì)較好的抽樣方法。然而這些傳統(tǒng)抽樣方法并未見用于非平衡數(shù)據(jù)的抽樣及分類,因此將這兩種方法引入非平衡數(shù)據(jù)的欠抽樣技術(shù)[21]。

本文從欠抽樣的角度解決數(shù)據(jù)非平衡問題。鑒于非平衡抽樣的分布可能不穩(wěn)定,常規(guī)抽樣沒有考慮樣本對(duì)分類的重要程度,利用所定義的樣本冗余度挑選多余的樣本,借助常規(guī)抽樣的規(guī)則確保抽樣的分布穩(wěn)定性。這樣的去冗余抽樣可以兼顧多數(shù)類樣本分布和分類邊界,盡量去除對(duì)分類結(jié)果影響不大的樣本,從而獲得滿意的分類結(jié)果。

1 抽樣方法

目前常采用的欠抽樣方法主要有以下幾種:隨機(jī)欠抽樣(RS)隨機(jī)刪除多數(shù)類樣本,使得兩類樣本數(shù)平衡;NearMiss-1 method(NM-1)抽取那些到最近的三個(gè)少數(shù)類樣本距離均值較小的多數(shù)類樣本;NearMiss-2 method(NM-2)抽取那些到最遠(yuǎn)的三個(gè)少數(shù)類樣本距離均值較小的多數(shù)類樣本;Most distance method(MD)抽取那些到最近的三個(gè)少數(shù)類樣本距離均值較大的多數(shù)類樣本;Cluster-Based Sampling(CBS)采用k-means聚類,選取距離類中心最近的樣本為各類的代表樣本。

非平衡數(shù)據(jù)容易使得分類邊界傾向于少數(shù)類,即可能將部分少數(shù)類樣本錯(cuò)分為多數(shù)類樣本。欠抽樣方法可以解決數(shù)據(jù)量上的不對(duì)等,然而上述欠抽樣方法抽取的樣本子集可能會(huì)改變?cè)紭颖镜姆植继卣?進(jìn)而影響分類效果,圖1的實(shí)驗(yàn)結(jié)果說明了這一問題。

Fig.1 Influence of the data distribution on classification圖1 數(shù)據(jù)分布對(duì)分類面的影響

原始數(shù)據(jù)均勻分布在[0,1]*[0,1]的二維平面內(nèi),真實(shí)分類面是一個(gè)反比例函數(shù)(圖1中的虛線)。圖1中分別包含了146個(gè)正類樣本和239個(gè)負(fù)類樣本。雖然正負(fù)類樣本數(shù)量相差不大,但正類樣本在下方較為稀疏,這樣就與原始的均勻分布有所區(qū)別。最終導(dǎo)致分類面向正類的稀疏部分產(chǎn)生偏移,即有部分正類樣本會(huì)誤分為負(fù)類。因此,抽樣子集的分布可能干擾分類邊界。在做欠抽樣時(shí)需要盡量保持?jǐn)?shù)據(jù)的分布不變。

為保持樣本分布,簡要介紹兩種欠抽樣算法。

KS抽樣算法

用于欠抽樣的KS方法是對(duì)多數(shù)類樣本進(jìn)行KS抽樣使得兩類樣本數(shù)平衡。

DPS抽樣算法

經(jīng)過DPS抽樣后原始集合被劃分為兩個(gè)近似同分布的集合。通過子集再次DPS抽樣可以將集合再一次變小,直到達(dá)到所需規(guī)模。用于欠抽樣的DPS-1是采用DPS方法將多數(shù)類樣本劃分為同分布的若干個(gè)子集,將與原多數(shù)類數(shù)據(jù)集相似度最大的子集作為新的多數(shù)類樣本集。用于欠抽樣的DPS-2與DPS-1的區(qū)別在于它選擇與原多數(shù)類數(shù)據(jù)集相似度最小的子集作為新的多數(shù)類樣本集。

2 去冗余抽樣

如果兩個(gè)多數(shù)類樣本距離較近且距離少數(shù)類樣本較遠(yuǎn),則認(rèn)為這兩個(gè)樣本是冗余的,有一個(gè)多數(shù)類樣本可去除。這樣的去冗余處理一方面盡量保持了多數(shù)類樣本的分布,同時(shí)將距離邊界或少數(shù)類樣本較遠(yuǎn)的多數(shù)類冗余樣本做了縮減,這樣就兼顧多數(shù)類樣本的同分布性質(zhì)和樣本的重要度。

RRS算法

雖然兩個(gè)距離少數(shù)類樣本較遠(yuǎn)且彼此較近的多數(shù)類樣本是冗余的,但如果將兩個(gè)樣本都去除,則數(shù)據(jù)的分布很容易產(chǎn)生變化,本文提出的RRS算法是將一個(gè)去除,另一個(gè)保留,這樣就兼顧了樣本的冗余程度和數(shù)據(jù)的整體分布。

3 實(shí)驗(yàn)結(jié)果及分析

(1)實(shí)驗(yàn)數(shù)據(jù)、抽樣比較方法及評(píng)價(jià)指標(biāo)

文中使用了6組二分類非平衡數(shù)據(jù)來檢驗(yàn)各種抽樣方法的效果。數(shù)據(jù)來自UCI標(biāo)準(zhǔn)數(shù)據(jù)集,樣本特征數(shù)范圍是7-34,多數(shù)類與少數(shù)類的樣本比從1.79到11.59(如表1所示)。設(shè)多數(shù)類和少數(shù)類樣本量分別為M,m。少數(shù)類樣本隨機(jī)分為樣本量均為m/2的子集,一組用于訓(xùn)練,一組用于測(cè)試;多數(shù)類樣本隨機(jī)分為兩個(gè)子集,一個(gè)樣本量為m/2的子集用于測(cè)試,另一個(gè)樣本量為M-m/2的子集用于訓(xùn)練。采用各種抽樣方法從用于訓(xùn)練的多數(shù)類子集中抽取m/2個(gè)樣本用于訓(xùn)練,將少數(shù)類訓(xùn)練集和抽樣后的多數(shù)類訓(xùn)練集合并為最終訓(xùn)練集,給定模型在此訓(xùn)練集上訓(xùn)練,并在兩個(gè)樣本量相同的測(cè)試集上進(jìn)行測(cè)試,得到測(cè)試誤差。每個(gè)實(shí)驗(yàn)重復(fù)10次,誤差取平均值進(jìn)行統(tǒng)計(jì)。

表1 實(shí)驗(yàn)用到的數(shù)據(jù)集

實(shí)驗(yàn)將無抽樣數(shù)據(jù)分類結(jié)果作為參照,比較了9種抽樣方法的效果,包括基本的隨機(jī)欠抽樣(RS)、四種常用的非平衡抽樣方法(NM-1、NM-2、MD、CBS)、三種經(jīng)典的抽樣方法(KS、DPS-1、DPS-2)以及本文所提出的RRS方法。分類算法采用Libsvm工具箱,核函數(shù)是高斯核。

模型誤差度量主要采用靈敏度、特異度、準(zhǔn)確度和G-means進(jìn)行綜合評(píng)價(jià)。

其中,A、B、C、D定義如表2所示。

表2 分類結(jié)果標(biāo)識(shí)

(2)結(jié)果分析

表3列出了上述10種方法分類后的靈敏度、特異度和準(zhǔn)確度比較。從表3可以看出,無抽樣分類結(jié)果的靈敏度在除第2組數(shù)據(jù)的其它五組數(shù)據(jù)上都是最大,表明采用原始數(shù)據(jù)可以得到較好的分類靈敏度。RRS方法的靈敏度在第2組數(shù)據(jù)上最大,其他組數(shù)據(jù)上排名都僅次于無抽樣分類方法。而無抽樣分類結(jié)果的特異度在各組數(shù)據(jù)上都是最低,充分說明了抽樣的必要性。

特異度在幾個(gè)方法上都可能達(dá)到最大,而且RRS方法的特異度在兩個(gè)數(shù)據(jù)集上都是最大,在其他四個(gè)數(shù)據(jù)集上與最大值比較接近。

關(guān)鍵的準(zhǔn)確度指標(biāo)的最大值均為RRS方法,其準(zhǔn)確度排名均為第一?？梢?RRS能夠較好地兼顧多數(shù)類和少數(shù)類的分類準(zhǔn)確性。

續(xù)表3 分類結(jié)果比較

圖2對(duì)比了各種方法的G-means值。從圖中可以看出,無抽樣方法的G-means值在后五組數(shù)據(jù)均為最低,其中最后兩組數(shù)據(jù)對(duì)應(yīng)的值為零。可見在分類精度較低的情況下,無抽樣的G-means更能體現(xiàn)抽樣方法的作用。RRS的G-means在所有數(shù)據(jù)上均為最大。在前兩組數(shù)據(jù)上模型的分類精度較高,G-means值較大,RRS方法略優(yōu)于其他方法;在后面四組數(shù)據(jù)上模型分類效果較差,這時(shí)RRS的G-means值相比于其他方法有明顯提升。除CBS和KS方法外,其他方法均有G-means值過低的表現(xiàn)。如random、NM-1和NM-2在數(shù)據(jù)5、6,MD在數(shù)據(jù)4,DPS-1和DPS-2在數(shù)據(jù)6。從G-means角度來看,CBS和KS是僅次于RRS的相對(duì)穩(wěn)定的欠抽樣方法。

Fig.2 G-means圖2 G-means

4 結(jié)論

針對(duì)非平衡數(shù)據(jù)分類問題,將KS抽樣和DPS方法用于欠抽樣。主要提出了去冗余抽樣,可以兼顧樣本的冗余程度和多數(shù)類樣本的整體分布,盡量去除對(duì)分類結(jié)果影響不大的樣本,從而有效降低樣本的非平衡以及樣本分布變化所產(chǎn)生的不利影響。實(shí)驗(yàn)結(jié)果表明,本文提出的方法對(duì)非平衡數(shù)據(jù)的分類結(jié)果明顯優(yōu)于其他方法,有效提高了少數(shù)類樣本的判別精度。

RRS為多類非平衡數(shù)據(jù)的抽樣提供了有益的參考。另外,在大數(shù)據(jù)背景下如何利用本文提出的抽樣方法實(shí)現(xiàn)數(shù)據(jù)的近似同分布?jí)嚎s是我們未來的工作。

[1]HeH,GarciaEA.LearningfromImbalancedData[J].IEEETransactionsonKnowledgeandDataEngineering,2009,21(9):1263-1284.DOI:10.1109/TKDE.2008.239.

[2] Chan P K,Stolfo S J.Toward Scalable Learning with Non-Uniform Class and Cost Distributions:A Case Study in Credit Card Fraud Detection[C]∥KDD.1998,98:164-168.

[3] Japkowicz N,Stephen S.The Class Imbalance Problem:A Systematic Study[J].IntelligentDataAnalysis,2002,6(5):429-449.

[4] Abe N.Invited Talk:Sampling Approaches to Learning from Imbalanced Datasets:Active Learning,Cost Sensitive Learning and Beyond[C]∥Proc.of ICML Workshop:Learning from Imbalanced Data Sets，2003,22.

[5] 邢勝,王熙照,王曉蘭.基于多類重采樣的非平衡數(shù)據(jù)極速學(xué)習(xí)機(jī)集成學(xué)習(xí)[J].南京大學(xué)學(xué)報(bào)自然科學(xué),2016,52(1):203-211.

[6] Estabrooks A,Jo T,Japkowicz N.A Multiple Resampling Method for Learning from Imbalanced Data Sets[J].ComputationalIntelligence,2004,20(1):18-36.

[7] Laurikkala J.Improving Identification of Difficult Small Classes by Balancing Class Distribution[C]∥Conference on Artificial Intelligence in Medicine in Europe.Springer Berlin Heidelberg,2001:63-66.

[8] Elkan C.The Foundations of Cost-sensitive Learning[C]∥International Joint Conference on Artificial Intelligence.Lawrence Erlbaum Associates Ltd,2001,17(1):973-978.

[9] Ting K M.An Instance-weighting Method to Induce Cost-sensitive Trees[J].IEEETransactionsonKnowledgeandDataEngineering,2002,14(3):659-665.

[10] Mani I,Zhang I.kNN Approach to Unbalanced Data Distributions:A Case Study Involving Information Extraction[C]∥Proceedings of Workshop on Learning from Imbalanced Datasets，2003.

[11] Chawla N V,Bowyer K W,Hall L O,etal.SMOTE:Synthetic Minority Over-sampling Technique[J].JournalofArtificialIntelligenceResearch,2002,16:321-357.[12] Han H,Wang W Y,Mao B H.Borderline-SMOTE:A New Over-sampling Method in Imbalanced Data Sets Learning[C]∥International Conference on Intelligent Computing.Springer Berlin Heidelberg,2005:878-887.

[13] Batista G E,Prati R C,Monard M C.A Study of the Behavior of Several Methods for Balancing Machine Learning Training Data[J].ACMSigkddExplorationsNewsletter,2004,6(1):20-29.

[14] Chawla N V,Lazarevic A,Hall L O,etal.SMOTEBoost:Improving Prediction of the Minority Class in Boosting[C]∥European Conference on Principles of Data Mining and Knowledge Discovery.Springer Berlin Heidelberg,2003:107-119.

[15] Liu X Y,Wu J,Zhou Z H.Exploratory Undersampling for Class-imbalance Learning[J].IEEE Transactions on Systems,Man,and Cybernetics,Part B (Cybernetics),2009,39(2):539-550.DOI:10.1109/TSMCB.2008.2007853.

[16] 郭虎升,亓慧,王文劍.處理非平衡數(shù)據(jù)的粒度SVM學(xué)習(xí)算法[J].計(jì)算機(jī)工程,2010,36(2):181-183.

[17] Jo T,Japkowicz N.Class Imbalances Versus Small Disjuncts[J].ACMSigkddExplorationsNewsletter,2004,6(1):40-49.

[18] Rajer-Kanducˇ K,Zupan J,Majcen N.Separation of Data on the Training and Test Set for Modelling:A Case Study for Modelling of Five Colour Properties of a White Pigment[J].ChemometricsandIntelligentLaboratorySystems,2003,65(2):221-229.

[19] Galvao R K H,Araujo M C U,Jose G E,etal.A Method for Calibration and Validation Subset Partitioning[J].Talanta,2005,67(4):736-740.

[20] Budka M,Gabrys B.Density-preserving Sampling:Robust and Efficient Alternative to Cross-validation for Error Estimation[J].IEEETransactionsonNeuralNetworksandLearningSystems,2013,24(1):22-34.DOI:10.1109/TNNLS.2012.2222925.[21] Frank A,Asuncion A.UCI Machine Learning Repository,University of California,School of Information and Computer Science,Irvine,CA,2010.http:∥archive.ics.uci.edu/ml/.

An Imbalanced Data Classification Approach Based on Redundancy-removed Sampling

SHI Ying1,QI Hui2

(1.Office of Science and Technology, Taiyuan Normal University, Jinzhong 030619,China;2.Department of Computer, Taiyuan Normal University, Jinzhong 030619,China)

Under-sampling is a common technique for classifying on imbalanced data.Traditional sampling methods (like Kennard-Stonesampling and density-preserving sampling) aim to keep the distribution of dataset. Existing under-sampling methods usually choose samples around the boundary whose distribution may be different with the original distribution，and the results may become worse. We proposed a redundancy about data, i.e., if a sample belonging to majority class lies in the dense area and is far away from the boundary or samples belonging to minority class, it has large redundancy. Redundancy-removed sampling (RRS) deletes samples with large redundancy in the same way with classical sampling methods. The subset obtained by RRS will refain samples which are valuable for classification but with the same distribution. Meanwhile, the amounts of the two class samples become balanced. The experimental results demonstrate that the accuracy by RRS is higher than those by other sampling approaches especially for the datasets with low classification accuracy. In addition,the accuracy of minority class is also improved.

imbalanced data;classification;sampling method;redundancy-removed sampling

10.13451/j.cnki.shanxi.univ(nat.sci.).2017.02.001

2016-10-25；

2016-11-25

山西省青年科學(xué)基金(201601D202040)

史穎(1990-),女,山西長治人,碩士,助教,主要從事圖像處理,機(jī)器學(xué)習(xí),三維重建等方面的研究。E-mail:wshsy123@126.com

TP301

A

0253-2395(2017)02-0255-07