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

史穎，亓慧

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

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

史穎1，亓慧2

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

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

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

0 引言

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

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

最簡單的抽樣方法是隨機重抽樣和欠抽樣,即隨機復制一些少數(shù)類樣本或隨機刪除多數(shù)類樣本。然而隨機復制樣本并沒有增加樣本的信息,甚至有可能導致過擬合[8]。而隨機刪除樣本可能刪去一些比較重要的(如類別邊界附近)樣本。簡單集成法(EasyEnsemble)[9]將多數(shù)類樣本集隨機劃分為若干個子集,并將這些子集分別與少數(shù)類樣本集建立若干分類模型,最終將其集成。文獻[10]提出了3種欠抽樣法,NearMiss-1, NearMiss-2和“most distant”。 NearMiss-1是抽取那些到最近的三個少數(shù)類樣本距離均值較小的多數(shù)類樣本;NearMiss-2是抽取那些到最遠的三個少數(shù)類樣本距離均值較小的多數(shù)類樣本;“most distant”是抽取那些到最近的三個少數(shù)類樣本距離均值較大的多數(shù)類樣本?？紤]到隨機復制樣本的不足,文獻[11]提出了經(jīng)典的SMOTE算法,其核心思想是將少數(shù)類樣本和其近鄰進行線性組合從而生成新的少數(shù)類樣本。后續(xù)很多學者將其改進,形成新的方法,如Borderline-SMOTE[12]、SMOTEpTomek[13]、SMOTEBoost[14]?；诰垲惖某闃铀惴梢愿鶕?jù)特定的問題對多數(shù)類樣本進行削減,從而處理非平衡問題。面向非平衡數(shù)據(jù)的抽樣方法通過新增少數(shù)類樣本或刪除多數(shù)類樣本使得樣本趨于平衡,然而在增刪的過程中免不了會改變多數(shù)類或少數(shù)類的樣本分布,這樣就會對分類邊界產(chǎn)生影響,進而干擾部分數(shù)據(jù)的正確分類。一般多數(shù)類誤分為少數(shù)類的代價要大于少數(shù)類誤分為多數(shù)類的代價[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]。文獻[18]在用神經(jīng)網(wǎng)絡做分類的結(jié)果表明,采用KS抽樣要優(yōu)于隨機抽樣、系統(tǒng)抽樣和KH抽樣。文獻[19]中偏最小二乘回歸的研究結(jié)果表明SPXY抽樣效果好于隨機抽樣和KS抽樣。文獻[20]經(jīng)過DPS抽樣的多個分類模型的誤差估計精度與分層10折交叉驗證方法相差不大,但前者穩(wěn)定性更高。綜合上述研究可見,KS和DPS是相對較好的抽樣方法。然而這些傳統(tǒng)抽樣方法并未見用于非平衡數(shù)據(jù)的抽樣及分類,因此將這兩種方法引入非平衡數(shù)據(jù)的欠抽樣技術(shù)[21]。

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

1 抽樣方法

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

非平衡數(shù)據(jù)容易使得分類邊界傾向于少數(shù)類,即可能將部分少數(shù)類樣本錯分為多數(shù)類樣本。欠抽樣方法可以解決數(shù)據(jù)量上的不對等,然而上述欠抽樣方法抽取的樣本子集可能會改變原始樣本的分布特征,進而影響分類效果,圖1的實驗結(jié)果說明了這一問題。

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

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

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

KS抽樣算法

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

DPS抽樣算法

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

2 去冗余抽樣

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

RRS算法

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

3 實驗結(jié)果及分析

(1)實驗數(shù)據(jù)、抽樣比較方法及評價指標

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

表1 實驗用到的數(shù)據(jù)集

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

模型誤差度量主要采用靈敏度、特異度、準確度和G-means進行綜合評價。

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

表2 分類結(jié)果標識

(2)結(jié)果分析

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

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

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

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

圖2對比了各種方法的G-means值。從圖中可以看出,無抽樣方法的G-means值在后五組數(shù)據(jù)均為最低,其中最后兩組數(shù)據(jù)對應的值為零?？梢娫诜诸惥容^低的情況下,無抽樣的G-means更能體現(xiàn)抽樣方法的作用。RRS的G-means在所有數(shù)據(jù)上均為最大。在前兩組數(shù)據(jù)上模型的分類精度較高,G-means值較大,RRS方法略優(yōu)于其他方法;在后面四組數(shù)據(jù)上模型分類效果較差,這時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的相對穩(wěn)定的欠抽樣方法。

Fig.2 G-means圖2 G-means

4 結(jié)論

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

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

[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ù)極速學習機集成學習[J].南京大學學報自然科學,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學習算法[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

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

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

TP301

A

0253-2395(2017)02-0255-07