稀有類分類問題研究

毛海濤，郭華平

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

?

稀有類分類問題研究

毛海濤，郭華平*

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

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

關(guān)鍵詞：稀有類；分類；分類方法；評價(jià)標(biāo)準(zhǔn)

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

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

1稀有類問題的特征

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

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

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

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

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

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

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

在不平衡數(shù)據(jù)集中，目標(biāo)類樣本所占比例非常低，數(shù)據(jù)分布不平衡，難以構(gòu)建恰當(dāng)?shù)乃惴Ｐ停斐蓴?shù)據(jù)分類準(zhǔn)確率不高。

2.2不恰當(dāng)?shù)脑u價(jià)標(biāo)準(zhǔn)影響分類性能

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

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

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

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

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

3.1隨機(jī)過采樣

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

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

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

3.2隨機(jī)欠采樣

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

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

3.3SMOTE算法

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

3.4綜合采樣技術(shù)

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

參考文獻(xiàn)：

[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].第二版.北京：機(jī)械出版社, 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ìn)展[J].計(jì)算機(jī)科學(xué)，2008，35(4):10-13.

[8]谷瓊.面向非均衡數(shù)據(jù)集的機(jī)器學(xué)習(xí)及在地學(xué)數(shù)據(jù)處理中的應(yīng)用[D]. 武漢：中國地質(zhì)大學(xué)，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.

(編輯：嚴(yán)佩峰)

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

中圖分類號(hào)：TP274

文獻(xiàn)標(biāo)識(shí)碼：A

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

作者簡介：毛海濤(1983—)，男，河南上蔡人，助教，碩士，主要研究方向?yàn)閿?shù)據(jù)挖掘，數(shù)字圖像處理.*通訊作者：郭華平(1982—)，男，河南固始人，講師，博士，CCF會(huì)員(No. E200034572M)，主要研究方向?yàn)闄C(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘.

基金項(xiàng)目：信陽師范學(xué)院2015年度青年基金項(xiàng)目(15044)

收稿日期：2015-10-26