稀有類分類問題研究

毛海濤，郭華平

(信陽師范學院 計算機與信息技術(shù)學院，河南 信陽 464000)

?

稀有類分類問題研究

毛海濤，郭華平*

(信陽師范學院 計算機與信息技術(shù)學院，河南 信陽 464000)

摘要：稀有類問題又稱為不平衡類問題，可以描述為從一個分布極不平衡的數(shù)據(jù)集中識別那些所占比例極少卻意義顯著的少數(shù)類實例。識別并正確分類稀有類實例，對現(xiàn)實生活具有重要的意義。本文探討了稀有類的特征、影響稀有類分類的因素，重點闡述了現(xiàn)行的稀有類分類方法。

關(guān)鍵詞：稀有類；分類；分類方法；評價標準

稀有類問題又稱為不平衡類問題，可以描述為從一個分布極不平衡的數(shù)據(jù)集中識別那些所占比例極少卻意義顯著的少數(shù)類實例。在實際應(yīng)用領(lǐng)域，正確識別并分類稀有類實例往往比正確識別多數(shù)類實例如更有意義。例如，醫(yī)療診斷過程中，絕大多數(shù)檢驗者為健康人只有少數(shù)檢驗者為癌癥患者，顯然，如何識別少數(shù)癌癥患者比正確識別健康人更為重要。

在不平衡數(shù)據(jù)集中稀有類實例數(shù)目所占比例非常稀少，分布不平衡，因此傳統(tǒng)的分類算法在分類稀有類時效果不佳。本文從稀有類的特征，影響分類的因素，主要分類方法及評價標準等方面對現(xiàn)階段業(yè)界在稀有類分類問題的研究給予論述。

1稀有類問題的特征

(1)稀有且難區(qū)性：在數(shù)據(jù)集中，目標類樣本所占比例非常稀少，分布又不平衡，稀有類實例的識別區(qū)分度非常低，難于區(qū)分。

(2)廣范應(yīng)用性：稀有類分類問題廣泛應(yīng)用于生活的各個領(lǐng)域，如：疾病診斷、網(wǎng)絡(luò)安全監(jiān)測、軍事情報分析等。以社會安全分析為例，在和平穩(wěn)定的社會大環(huán)境下，大多數(shù)的安全分析都是正確的，如果極端暴恐小概率事件不能提前有效分析出來，就會對國家安全造成難以估量的影響。

(3)復雜多態(tài)性：多數(shù)類和目標類都有多個子類，不同的子類又具有不同的特性，從而導致分類情況更加復雜。

2影響稀有類分類效果的因素

目前分類有很多經(jīng)典的算法，如：貝葉斯算法[1]、決策樹算法[2]、神經(jīng)網(wǎng)絡(luò)學習算法[3]、SVM算法[4]、Adaboost[5]、Bagging[6]等。

不過在不平衡數(shù)據(jù)集的使用過程中，上述幾種算法的準確率不是很高[7]。經(jīng)研究發(fā)現(xiàn)，稀有類分類的準確率受諸多因素影響。

2.1不平衡的類分布影響分類效果

在不平衡數(shù)據(jù)集中，目標類樣本所占比例非常低，數(shù)據(jù)分布不平衡，難以構(gòu)建恰當?shù)乃惴Ｐ?，造成?shù)據(jù)分類準確率不高。

2.2不恰當?shù)脑u價標準影響分類性能

在數(shù)據(jù)挖掘領(lǐng)取，衡量分類器的主要依據(jù)是評價標準，在傳統(tǒng)的分類算法中，衡量算法性能的主要指標是分類正確率。但是，不平衡數(shù)據(jù)集不同于正常的數(shù)據(jù)集，僅以正確率來評價不平衡數(shù)據(jù)集的分類優(yōu)劣性，有失偏頗。

2.3不恰當?shù)臍w納偏置影響樣本分布

傳統(tǒng)算法在應(yīng)用過程中，歸納特定樣本時都會設(shè)置一個偏置[8]。通過歸納偏置，可以提高分類器的泛化能力。但在稀有類的分類過程中，如果同樣使用歸納偏置，就會把少數(shù)類樣本誤分為多數(shù)類，導致錯誤的分類結(jié)果，影響分類精度。

3稀有類數(shù)據(jù)常用分類方法

在一般的分類過程中，經(jīng)常會采用抽樣的分類方法。在對稀有類分類進行研究時，也可以使用抽樣的分類方法。抽樣算法的基本思想是通過抽樣來改變數(shù)據(jù)集中的樣本分布。在抽樣過程中平衡數(shù)據(jù)分布，在平衡的數(shù)據(jù)集上構(gòu)建學習模型，如隨機過采樣[9]、SMOTE[10]、隨機欠采樣[11]以及綜合采樣[12]等算法。

3.1隨機過采樣

隨機過采樣算法的核心思想是從稀有類中隨機抽取一個樣本集E并將其加入的訓練數(shù)據(jù)集中。具體地，假設(shè)數(shù)據(jù)集中稀有類(正類)樣本集為Dp，使用又放回重復抽樣方法從Dp中抽取一個子集E，并將該子集加入到源訓練數(shù)據(jù)集D中。通過這種方法，Dp的大小增加了|E|，進而相應(yīng)地調(diào)整了D的數(shù)據(jù)分布。該過程如圖1所示，其中，▲代表稀有類樣本，○代表多數(shù)類樣本。值得注意的是，這種方法提供了一種隨意改變數(shù)據(jù)分布的一種機制。同時，該方法既容易理解也容易可視化，因此，該方法一直受到研究者們的關(guān)注。

不均衡數(shù)據(jù)集 均衡數(shù)據(jù)集不均衡數(shù)據(jù)集均衡數(shù)據(jù)集

圖1隨機過采樣將不均衡數(shù)據(jù)集轉(zhuǎn)換為均衡數(shù)據(jù)集圖2隨機欠采樣將不均衡數(shù)據(jù)集轉(zhuǎn)換成均衡數(shù)據(jù)集

3.2隨機欠采樣

與隨機過采樣向訓練數(shù)據(jù)集中添加樣本的做法不同，隨機欠采樣技術(shù)則是通過隨機的移除多數(shù)類樣本以調(diào)整數(shù)據(jù)樣本分布。具體地，設(shè)Dn為負類樣本集，從Dn選擇一個子集E，并從D中移除這些實例集，直到|D| =||Dn| +|Dp|-|E|。該過程如圖2所示，其中，▲代表稀有類樣本，○代表多數(shù)類樣本。

比較過抽樣和欠抽樣技術(shù)，我們?nèi)菀装l(fā)現(xiàn)，他們的功能似乎很相似，其原因是他們都能改變原始數(shù)據(jù)集的大小，同時能保證處理后的數(shù)據(jù)集是平衡的，即：多數(shù)類和少數(shù)類實例數(shù)目相當。當然，這兩種方法各存有不足之處，例如，在欠抽樣技術(shù)中，從多數(shù)類實例中移除大量的負類樣本有可能導致分類器不能獲得保留在負類樣本中的概念模式。在過抽樣技術(shù)中，隨機的添加重復的樣本可能導致某些樣本出現(xiàn)頻度過高，進而導致模型過分擬合訓練數(shù)據(jù)集。

3.3SMOTE算法

SMOTE(Synthetic Minority Oversampling TEchnique)是一種典型的人工合成過抽樣技術(shù)，該技術(shù)已經(jīng)成功地應(yīng)用到很多實際應(yīng)用中。該技術(shù)根據(jù)正類實例間的特征相似性來人工合成新的正類實例。具體如下，對于正類實例集Dp∈D，考慮Dp中的每個實例xi∈Dp的k-近鄰，其中該k-近鄰定義為Dp中的k個實例與xi的歐幾里德距離最小的前k個實例。然后，從這k-近鄰中隨機的選擇一個近鄰，并在相應(yīng)的特征向量上乘以一個[0, 1]的因子，并加上xi以獲得新實例，形式化地

3.4綜合采樣技術(shù)

當采用欠采樣技術(shù)進行分類時，多數(shù)類在分類過程中會丟失有用的信息；而當采用過采樣技術(shù)進行分類時需要增加很多訓練時間和復雜度來處理少數(shù)類數(shù)據(jù)，甚至會使分類器過分擬合。通過研究發(fā)現(xiàn)，可以將欠采樣和過采樣技術(shù)進行整合，也可以很好地解決不平衡數(shù)據(jù)集的分類問題，這種新技術(shù)就是綜合采樣技術(shù)。

參考文獻：

[1]D.Heckerman.Bayesian Networks for Data Mining[J].Data Mining and Knowleged Discovery, 1997：79-119.

[2]K. Alsabti, S. Ranka , and V. Singh.CLOUDS： A Decision Tree Classifier for Large Datasets[C]. In Proc. of the 4th Intl. Conf. on Knowledge Discovery and Data Mining, New York, 1998：79-119.

[3]C.M.Bishop.Neural Networks for Pattern Recognition[J].Oxford Univerity Press,Oxford,U.K., 1995.

[4]Duda,R.O,Hart,P.E,Stork,D.G李虹東,姚天翔譯.模式分類[M].第二版.北京：機械出版社, 2007：373-375.

[5]E.S.Robert.Theoretical view of boosting[C]//In：Proc of Europea rence on Cn Confeomputational Learning Theory. Nordkiechen, germany. Springer-Verlag, 1999:1-10.

[6]L.Breiman.“Bagging predictors” Machine Learning. 1996,24(1):123-140.

[7]高嘉偉，梁吉業(yè).非平衡數(shù)據(jù)集分類問題研究進展[J].計算機科學，2008，35(4):10-13.

[8]谷瓊.面向非均衡數(shù)據(jù)集的機器學習及在地學數(shù)據(jù)處理中的應(yīng)用[D]. 武漢：中國地質(zhì)大學，2009.

[9]Shao Kuoyi，Zhai Yun，Sui Haifeng et al.A New Over-sample Method Based on Distribution Density[J].Journal of Computers, 2014，9(2):483-490.

[10]N.V.Chawla,K.W.Bowyer.SMOTE：synthetic minority over-sampling technique,Journal of Artificial Intelligence Research. Vol 2002 (16):341-378.

[11]C.Li. Classifying Imbalanced Data Using A Bagging Ensemble Variation (BEV). Proceedings of the 45th annual southeast regional conference,March 23-24, 2007, Winston-Salem, North Carolina.

[12]J.Laurikkala.Improving Identification of Difficult Small Classes by Balancing Class Distribution. Proceedings of the 8th Conference on AI in Medicine Europe:Artificial. 2001：63-66.

(編輯：嚴佩峰)

On the Classification of Rare Class

MAO Hai-tao,GUO Hua-ping

(School of Computer and Information Technology, Xinyang Normal University,Xinyang 464000, China)

Abstract：Imbalanced problem, also called class-imbalance problem, is characterized as recognizing the rare class examples from the data with severe class distribution skews. However, it is very important to correctly classify the rare class examples. In this paper, we study the characters of imbalance problem, the factors influencing its performance, the classifier method and the corresponding evaluations.

Keywords：rare class;classification;classification methods;evaluation measure

中圖分類號：TP274

文獻標識碼：A

文章編號：2095-8978(2016)01-0121-03

作者簡介：毛海濤(1983—)，男，河南上蔡人，助教，碩士，主要研究方向為數(shù)據(jù)挖掘，數(shù)字圖像處理.*通訊作者：郭華平(1982—)，男，河南固始人，講師，博士，CCF會員(No. E200034572M)，主要研究方向為機器學習、數(shù)據(jù)挖掘.

基金項目：信陽師范學院2015年度青年基金項目(15044)

收稿日期：2015-10-26