摘  要： 探討了影響稀有類(lèi)分類(lèi)的各個(gè)因素，針對(duì)影響稀有類(lèi)中的一個(gè)因素——樣本大小對(duì)稀有類(lèi)的影響進(jìn)行了研究。
關(guān)鍵詞： 分類(lèi)；稀有類(lèi)；組合分類(lèi)器；樣本大小

   分類(lèi)是數(shù)據(jù)挖掘中的重要任務(wù)之一，在商業(yè)、金融、電訊、DNA分析、科學(xué)研究等諸多領(lǐng)域具有廣泛的應(yīng)用。統(tǒng)計(jì)學(xué)、機(jī)器學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)等領(lǐng)域的研究者提出了很多分類(lèi)方法[1]。分類(lèi)稀有類(lèi)是分類(lèi)中的一個(gè)重要問(wèn)題。這個(gè)問(wèn)題可以描述為從一個(gè)分布極不平衡的數(shù)據(jù)集中標(biāo)識(shí)出那些具有顯著意義卻很少發(fā)生的實(shí)例。分類(lèi)稀有類(lèi)在現(xiàn)實(shí)生活中的很多領(lǐng)域都有廣泛的應(yīng)用。例如，網(wǎng)絡(luò)侵入檢測(cè)、欺騙探測(cè)和偏差探測(cè)。在網(wǎng)絡(luò)入侵中，一個(gè)計(jì)算機(jī)通過(guò)猜測(cè)一個(gè)密碼或打開(kāi)一個(gè)ftp數(shù)據(jù)連接進(jìn)行遠(yuǎn)程攻擊。雖然這種網(wǎng)絡(luò)行為不常見(jiàn)，但識(shí)別并分析出這種行為對(duì)于網(wǎng)絡(luò)安全很有必要。
　普通分類(lèi)問(wèn)題中，各個(gè)類(lèi)包含的數(shù)據(jù)分布比較平衡，稀有類(lèi)分類(lèi)問(wèn)題中，數(shù)據(jù)的分布極不平衡。例如：將一批醫(yī)療數(shù)據(jù)分類(lèi)為“癌癥患者”和“非癌癥患者”兩個(gè)類(lèi)，其中 “癌癥患者”是小比例樣本(假設(shè)占總樣本的1%)，稱(chēng)其為目標(biāo)類(lèi)，“非癌癥患者”為多數(shù)類(lèi)樣本，稱(chēng)為非目標(biāo)類(lèi)，從大量數(shù)據(jù)中正確識(shí)別“癌癥患者”就是稀有類(lèi)分類(lèi)問(wèn)題。由于在數(shù)據(jù)集中所占比率太小，使得稀有類(lèi)分類(lèi)問(wèn)題比普通分類(lèi)問(wèn)題更具挑戰(zhàn)性。
　研究表明，解決稀有類(lèi)分類(lèi)問(wèn)題的方法總體上可以分為：基于數(shù)據(jù)集的、算法的[2]，以及使用組合分類(lèi)器方法，如Bagging、Random Forest及Rotation Forest等。
　影響稀有類(lèi)分類(lèi)的因素有很多，本文針對(duì)其中的一個(gè)因素——樣本大小進(jìn)行研究。實(shí)驗(yàn)基于上述的若干組合分類(lèi)器，在特定的類(lèi)比率[3]下通過(guò)改變樣本大小，觀察樣本大小對(duì)稀有類(lèi)分類(lèi)的影響。
1 影響稀有類(lèi)分類(lèi)的因素
　通常認(rèn)為影響稀有類(lèi)分類(lèi)的因素是不平衡的類(lèi)分布(Imbalanced class distribution)，但是大量的研究和實(shí)驗(yàn)證明，數(shù)據(jù)的不平衡性只是影響稀有類(lèi)分類(lèi)的一個(gè)因素，還有一些重要的因素影響稀有類(lèi)分布，如小樣本規(guī)格(Small sample size)和分離性(Separability)[2]。下面簡(jiǎn)單討論這些因素對(duì)稀有類(lèi)分類(lèi)的影響。
　(1)不平衡的類(lèi)分布：研究表明，類(lèi)分布越是相對(duì)平衡的數(shù)據(jù)分類(lèi)的性能越好。參考文獻(xiàn)[4]探討了訓(xùn)練集的類(lèi)分布和判定樹(shù)分類(lèi)性能的關(guān)系，但是不能確定多大的類(lèi)分布比率使得分類(lèi)性能下降。研究表明，在有些應(yīng)用中1:35時(shí)不能很好地建立分類(lèi)器，而有的應(yīng)用中1:10時(shí)就很難建立了。
　(2)樣本大?。航o定特定的類(lèi)分布比率(稀有類(lèi)實(shí)例和普通類(lèi)實(shí)例的比值)，樣本大小在確定一個(gè)好的分類(lèi)模型中起著非常重要的作用，要在有限的樣本中發(fā)現(xiàn)稀有類(lèi)內(nèi)在的規(guī)律是不可能的。如對(duì)于一個(gè)特定的數(shù)據(jù)集，類(lèi)分布比率為1:20，其中稀有類(lèi)實(shí)例為5個(gè)，非稀有類(lèi)實(shí)例為100個(gè)。改變?cè)摂?shù)據(jù)集的樣本大小，使得稀有類(lèi)實(shí)例為50個(gè)，非稀有類(lèi)實(shí)例為1 000個(gè)。結(jié)果是類(lèi)分布同樣為1:20，但是前者沒(méi)有后者提供的稀有類(lèi)信息量大，稀有類(lèi)分類(lèi)的性能沒(méi)有后者高。
　(3)分離性：從普通類(lèi)中區(qū)分出稀有類(lèi)是稀有類(lèi)分類(lèi)的關(guān)鍵問(wèn)題。假定每個(gè)類(lèi)中存在高度可區(qū)分模式，則不需要很復(fù)雜的規(guī)則區(qū)分它們。但是如果在一些特征空間上不同類(lèi)的模式有重疊就會(huì)極大降低被正確識(shí)別的稀有類(lèi)實(shí)例數(shù)目。
　根據(jù)以上分析可知，由于影響稀有類(lèi)分類(lèi)的因素多種多樣，使得稀有類(lèi)分類(lèi)問(wèn)題更加復(fù)雜，分類(lèi)的性能降低。本文在其他因素相同的前提下研究樣本大小對(duì)稀有類(lèi)分類(lèi)的影響。實(shí)驗(yàn)證明在類(lèi)分布相同的情況下，樣本越大稀有類(lèi)分類(lèi)的性能越好。
2 稀有類(lèi)分類(lèi)的評(píng)估標(biāo)準(zhǔn)
　常用的分類(lèi)算法的評(píng)估標(biāo)準(zhǔn)有：預(yù)測(cè)的準(zhǔn)確率、速度、強(qiáng)壯性、可規(guī)模性及可解釋性。通常使用分類(lèi)器的總準(zhǔn)確率來(lái)評(píng)價(jià)普通類(lèi)的分類(lèi)效果。而對(duì)于稀有類(lèi)分類(lèi)問(wèn)題，由于關(guān)注的焦點(diǎn)不同，僅用準(zhǔn)確率是不合適的。
　在稀有類(lèi)分類(lèi)問(wèn)題中應(yīng)更關(guān)注稀少目標(biāo)類(lèi)的正確分類(lèi)率。在評(píng)價(jià)稀有類(lèi)分類(lèi)時(shí)，還應(yīng)該采用其他的評(píng)價(jià)標(biāo)準(zhǔn)。
　這里假設(shè)只考慮包含兩個(gè)類(lèi)的二元分類(lèi)問(wèn)題，設(shè)C類(lèi)為目標(biāo)類(lèi)，即稀有類(lèi)，NC為非目標(biāo)類(lèi)。根據(jù)分類(lèi)器的預(yù)測(cè)類(lèi)標(biāo)號(hào)和實(shí)際類(lèi)標(biāo)號(hào)的分布情況存在如表1所示的混合矩陣(Confusion Matrix)。
    根據(jù)表1得到如下度量：
  

3 組合分類(lèi)器介紹
　組合分類(lèi)器是目前機(jī)器學(xué)習(xí)和模式識(shí)別方面研究的熱門(mén)領(lǐng)域之一，大量研究表明，在理論和實(shí)驗(yàn)中，組合方法比單個(gè)分類(lèi)模型有明顯的優(yōu)勢(shì)。組合方法由訓(xùn)練數(shù)據(jù)構(gòu)建一組基分類(lèi)器，通過(guò)對(duì)每個(gè)基分類(lèi)器的預(yù)測(cè)進(jìn)行投票后分類(lèi)。常用的組合分類(lèi)器有：Bagging、Random Forest及Rotation Forest。
3.1 Bagging介紹
　Bagging[5]算法是一種投票方法，各個(gè)分類(lèi)器的訓(xùn)練集由原始訓(xùn)練集利用可重復(fù)取樣(bootstrap sampling)技術(shù)獲得，訓(xùn)練集的規(guī)模通常與原始訓(xùn)練集相當(dāng)?；舅枷肴缦拢航o定s個(gè)樣本的集合S，其過(guò)程如下：對(duì)于迭代t(t=1，2，...，T)，訓(xùn)練集St采用放回選樣，由原始樣本集S選取。由于使用放回選樣，S的某些樣本可能不在St中，而其他的可能出現(xiàn)多次。由每個(gè)訓(xùn)練集St學(xué)習(xí)，得到一個(gè)分類(lèi)算法Ct。為對(duì)一個(gè)未知的樣本X分類(lèi)，每個(gè)分類(lèi)算法Ct返回它的類(lèi)預(yù)測(cè)，算作一票。Bagging的分類(lèi)算法C*統(tǒng)計(jì)得票，并將得票最高的類(lèi)賦予X[1]。
3.2 Random Forest介紹
　隨機(jī)森林是一種組合分類(lèi)器方法， 構(gòu)成隨機(jī)森林的基本分類(lèi)器是決策樹(shù)?；舅枷肴缦拢菏紫仍O(shè)定森林中有M棵樹(shù)，即有M個(gè)決策樹(shù)分類(lèi)器，且全體訓(xùn)練數(shù)據(jù)的樣本總數(shù)為N。使用bagging方法，即通過(guò)從全體訓(xùn)練樣本中隨機(jī)地有放回地抽取N個(gè)樣本，形成單棵決策樹(shù)的訓(xùn)練集。重復(fù)M次這樣的抽樣過(guò)程分別得到M棵決策樹(shù)的學(xué)習(xí)樣本。單棵決策樹(shù)建造過(guò)程不進(jìn)行剪枝，森林形成之后，對(duì)于一個(gè)新的樣本，每棵樹(shù)都得出相應(yīng)的分類(lèi)結(jié)論，最后由所有樹(shù)通過(guò)簡(jiǎn)單多數(shù)投票決定分類(lèi)結(jié)果。
3.3 Rotation Forest介紹
　Rotation Forest是一個(gè)基于判定樹(shù)的組合分類(lèi)器，其基本思想如下：假設(shè)x=[x1，…，xn]為不含類(lèi)標(biāo)號(hào)的數(shù)據(jù)集X的一個(gè)元組，則該數(shù)據(jù)集可以表示為N×n的矩陣；定義Y=[y1，…，yN]為X中元組對(duì)應(yīng)的類(lèi)標(biāo)號(hào)集合，其中yi∈{w1，…，wc}；定義D1，…，DL為組合方法中的基分類(lèi)器；F為屬性集合。Rotation Forest意在建立L個(gè)不同的準(zhǔn)確的分類(lèi)器。特征集F被劃分成K個(gè)子集，在每個(gè)子集上運(yùn)用PCA[6](principal component analysis)進(jìn)行特征提取，合并所有的主成份重建一個(gè)新的特征集，原始數(shù)據(jù)被映射到新的特征空間?；谛碌臄?shù)據(jù)集訓(xùn)練得到Di分類(lèi)器。L次不同的屬性集劃分得到L個(gè)不同的提取特征集，映射原始數(shù)據(jù)得到L個(gè)不同的數(shù)據(jù)集，分別訓(xùn)練得到L個(gè)分類(lèi)器。對(duì)于未知樣本的實(shí)例X，組合L個(gè)分類(lèi)器計(jì)算每個(gè)類(lèi)的置信度，將其歸類(lèi)于置信度最高的類(lèi)中[6，7]。
4 實(shí)驗(yàn)結(jié)果及其分析
   為了驗(yàn)證稀有類(lèi)分類(lèi)算法受到樣本規(guī)格大小的影響，使用UCI機(jī)器學(xué)習(xí)庫(kù)[8]中的稀有類(lèi)數(shù)據(jù)集sick作為實(shí)驗(yàn)數(shù)據(jù)集。實(shí)驗(yàn)環(huán)境選擇weka平臺(tái)，使用weka平臺(tái)提供的unsupervised resample數(shù)據(jù)預(yù)處理方法改變樣本的大小。實(shí)驗(yàn)采用十折交叉驗(yàn)證的方法統(tǒng)計(jì)分類(lèi)的準(zhǔn)確率。
　sick數(shù)據(jù)集的基本情況為：30個(gè)屬性(帶類(lèi)標(biāo)號(hào))、2個(gè)類(lèi)(0，1)，共有實(shí)例3 772條。其中sick和negative類(lèi)分別擁有實(shí)例數(shù)目3 541和231，分別占總樣本比例93.88％和6.12％。sick類(lèi)可看作稀有類(lèi)。
4.1 實(shí)驗(yàn)結(jié)果
　基于每個(gè)數(shù)據(jù)集，采用weka平臺(tái)提供的unsupervised resample數(shù)據(jù)預(yù)處理方法改變樣本規(guī)格的大小，使得實(shí)例數(shù)目分別是原始數(shù)據(jù)的倍到10倍不等。對(duì)這些處理后的數(shù)據(jù)集分別應(yīng)用組合分類(lèi)器bagging、FandomForest和Rotation Forest算法進(jìn)行分類(lèi)。
　表2是應(yīng)用Rotation Forest算法在處理后得到的sick數(shù)據(jù)集上關(guān)于sick類(lèi)的實(shí)驗(yàn)結(jié)果。sick數(shù)據(jù)集樣本被擴(kuò)充了若干倍不等。

   表3是應(yīng)用Random Forest算法在處理后得到的sick數(shù)據(jù)集上關(guān)于sick類(lèi)的實(shí)驗(yàn)結(jié)果。sick數(shù)據(jù)集樣本被擴(kuò)充了若干倍不等。

   表4是應(yīng)用Bagging算法在處理后得到的sick數(shù)據(jù)集上關(guān)于sick類(lèi)的實(shí)驗(yàn)結(jié)果。sick數(shù)據(jù)集被擴(kuò)充了若干倍不等。Bagging算法在sick數(shù)據(jù)集上實(shí)驗(yàn)時(shí)，樣本被擴(kuò)充到10倍后，recall值仍沒(méi)有達(dá)到1，后來(lái)實(shí)驗(yàn)又將樣本擴(kuò)充至12倍，但由于內(nèi)存不夠?qū)嶒?yàn)終止。

　通過(guò)上述表格中的實(shí)驗(yàn)結(jié)果，可以看到隨著樣本規(guī)格變大，衡量稀有類(lèi)分類(lèi)的這些參數(shù)也呈遞增。這也意味著隨著稀有類(lèi)實(shí)例數(shù)目的增加，算法可以獲得更多關(guān)于稀有類(lèi)的信息，從而有利于對(duì)稀有類(lèi)實(shí)例的識(shí)別。
4.2 結(jié)果分析
    通常認(rèn)為影響稀有類(lèi)分類(lèi)的重要因素是數(shù)據(jù)分布的不平衡性，也就是說(shuō)對(duì)于稀有類(lèi)問(wèn)題，普通的分類(lèi)算法往往失效，但本文的實(shí)驗(yàn)結(jié)果表明，數(shù)據(jù)分布的不平衡性影響稀有類(lèi)分類(lèi)的一個(gè)因素，在特定的類(lèi)比率下，使樣本規(guī)格變大，普通的分類(lèi)算法往往也可以取得很好的分類(lèi)結(jié)果。
    本文對(duì)稀有類(lèi)分類(lèi)問(wèn)題進(jìn)行了研究，分析了影響稀有類(lèi)分類(lèi)問(wèn)題的因素，探討了稀有類(lèi)分類(lèi)的評(píng)估標(biāo)準(zhǔn)。針對(duì)影響稀有類(lèi)分類(lèi)的一個(gè)因素：樣本規(guī)格的大小進(jìn)行研究，在同等類(lèi)分布比率下，改變樣本規(guī)格的大小，在weka平臺(tái)下進(jìn)行實(shí)驗(yàn)，得到數(shù)據(jù)集中稀有類(lèi)的recall、precision和F-measure值。實(shí)驗(yàn)結(jié)果表明，在特定的類(lèi)比率下，使樣本規(guī)格變大，普通的分類(lèi)算法往往也可以取得很好的分類(lèi)結(jié)果。同時(shí)也說(shuō)明，數(shù)據(jù)分布的不平衡性只是影響稀有類(lèi)分類(lèi)的一個(gè)因素，即使數(shù)據(jù)分布極不平衡，通過(guò)增加樣本中稀有類(lèi)實(shí)例的數(shù)目(類(lèi)比率不變)，也可以提高稀有類(lèi)分類(lèi)的各個(gè)指標(biāo)。
    本文中的實(shí)驗(yàn)基于多個(gè)組合分類(lèi)器進(jìn)行，每個(gè)組合分類(lèi)器在每個(gè)數(shù)據(jù)集下的實(shí)驗(yàn)結(jié)果都表明了樣本大小是影響稀有類(lèi)分類(lèi)正確的重要因素。在數(shù)據(jù)分布及不平衡下提供足夠的稀有類(lèi)實(shí)例仍然可以獲得好的分類(lèi)結(jié)果。
參考文獻(xiàn)
[1] HAN J，KANBER M，著，數(shù)據(jù)挖掘：概念與技術(shù)[M]，范明，孟小峰，譯.北京：機(jī)械工業(yè)出版社，2001.
[2] Yanmin， Mobamed S. Kamel， Andrew K. C. Wong， Cost-sensitive boosting for classification of imbalanced data. Patter Recognition， 2007(10):3358-3378.
[3] VISA S，RALESCU A.Issues in mining imbalanced data sets-a review paper[C]. In Proceedings of the Sixteen Midwest Artificial Intelligence and Cognitive Science Conference， 2005:67-73.
[4] WEISS G，PROVOST F. Learning when training data are costly: the effect of class distribution on tree induction[C]. J. Aritif. Intell. Res， 2003(19):315-354.
[5] Breiman. Bagging predictiors[M]. Machine Learning， 1996，24:123-140.
[6] KUNCHEVA L I，RODRIGUEZ J J， An experimental study on Rotation Forest ensembles[C]. In: MCS 2007， Lecture Notes in Computer Science， vol. 4472， Springer， Berlin， 2007:459-468.
[7] RODRIGUEZ J J， KUNCHEVA L I， ALONSO C J. Rotation forest: a new classifier ensemble method[C]. IEEE Trans. Pattern Anal. Mach. Intell. 2006，28:1619-1630.
[8] BLAKE C.MERZ C.UCI repository of machine learning databases. http://www.ics.uci.edu/~mlearn/MLRepository.html. 1998.