基于二次隨機(jī)森林的不平衡數(shù)據(jù)分類算法

劉學(xué)+張素偉

摘要：不平衡數(shù)據(jù)集的分類問題是現(xiàn)今機(jī)器學(xué)習(xí)的一個(gè)熱點(diǎn)問題。傳統(tǒng)分類學(xué)習(xí)器以提高分類精度為準(zhǔn)則導(dǎo)致對(duì)少數(shù)類識(shí)別準(zhǔn)確率下降。本文首先綜合描述了不平衡數(shù)據(jù)集分類問題的研究難點(diǎn)和研究進(jìn)展，論述了對(duì)分類算法的評(píng)價(jià)指標(biāo)，進(jìn)而提出一種新的基于二次隨機(jī)森林的不平衡數(shù)據(jù)分類算法。首先，用隨機(jī)森林算法對(duì)訓(xùn)練樣本學(xué)習(xí)找到模糊邊界，將誤判的多數(shù)類樣本去除，改變?cè)?xùn)練樣本數(shù)據(jù)集結(jié)構(gòu)，形成新的訓(xùn)練樣本。然后再次使用隨機(jī)森林對(duì)新訓(xùn)練樣本數(shù)據(jù)進(jìn)行訓(xùn)練。通過對(duì)UCI數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)分析表明新算法在處理不平衡數(shù)據(jù)集上在少數(shù)類的召回率和F值上有提高。

關(guān)鍵詞：模式識(shí)別；不平衡數(shù)據(jù)；隨機(jī)森林；模糊邊界

引言

不平衡數(shù)據(jù)集是指數(shù)據(jù)集內(nèi)各類別所占比例不均，其中某個(gè)或某幾個(gè)類別比例遠(yuǎn)遠(yuǎn)小于其它類別。它廣泛存在于真實(shí)的應(yīng)用場景中，例如利用用戶提交數(shù)據(jù)檢測(cè)用戶詐騙的可能性，一般詐騙用戶數(shù)量遠(yuǎn)遠(yuǎn)小于普通用戶；利用檢測(cè)數(shù)據(jù)檢測(cè)病人的疾病，如癌癥，患癌癥的病人數(shù)量遠(yuǎn)遠(yuǎn)小于檢查的病人；其他有利用衛(wèi)星圖片油井定位、文本自動(dòng)分類、垃圾郵件過濾等。在上述應(yīng)用中，人們更關(guān)心的是對(duì)于少數(shù)類別的判斷，事實(shí)上少數(shù)類錯(cuò)判帶來的損失遠(yuǎn)遠(yuǎn)大于對(duì)多數(shù)類的錯(cuò)判，例如對(duì)于癌癥病人如果錯(cuò)判，延誤了最佳治療時(shí)機(jī)，會(huì)給癌癥病人帶來致命威脅。因此研究不平衡數(shù)據(jù)集分類問題具有重大的現(xiàn)實(shí)意義。

傳統(tǒng)分類方法以分類精度作為評(píng)判學(xué)習(xí)器的指標(biāo)，在不平衡數(shù)據(jù)集中，學(xué)習(xí)器的預(yù)測(cè)結(jié)果肯定更加偏向比例更大的類別。weiss的實(shí)驗(yàn)，以分類精度為準(zhǔn)則的學(xué)習(xí)器模型會(huì)導(dǎo)致識(shí)別少數(shù)類準(zhǔn)確率下降，這樣的分類學(xué)習(xí)器模型會(huì)傾向?qū)颖绢A(yù)測(cè)為多數(shù)類。

本文在研究不平衡數(shù)據(jù)集特點(diǎn)和隨機(jī)森林的特性基礎(chǔ)上，提出了針對(duì)不平衡數(shù)據(jù)的二次隨機(jī)森林分類算法，通過改變樣本數(shù)據(jù)結(jié)構(gòu)改善分類性能。

1不平衡數(shù)據(jù)的分類研究

由于多數(shù)類分類問題可以轉(zhuǎn)化為二分類問題，因此本文研究是基于二分類的不平衡數(shù)據(jù)集分類問題加以研究。正類為多數(shù)類，負(fù)類為少數(shù)類。

除了類間不平衡度較大易造成對(duì)少數(shù)類的識(shí)別率降低外，Japkowicz等人的實(shí)驗(yàn)研究表明，類間不平衡度（正負(fù)類比例）并不是導(dǎo)致傳統(tǒng)分類算法性能下降的首要原因，事實(shí)上當(dāng)類間重疊度低時(shí)，傳統(tǒng)的機(jī)器算法如C4.5、BP神經(jīng)網(wǎng)絡(luò)和SVM的分類性能仍較好，而當(dāng)類間重疊度較高時(shí)，傳統(tǒng)分類算法性能下降。以二維數(shù)據(jù)為例，如圖1所示，當(dāng)類間重疊度較低時(shí)，正負(fù)類邊界清楚，少數(shù)類的信息并沒有被淹沒，而當(dāng)圖2所示類間重疊度高意味著正負(fù)類之間的邊界模糊，少數(shù)類信息淹沒在多數(shù)類中。分類算法的實(shí)質(zhì)是建立一套規(guī)則，將數(shù)據(jù)集空間劃分為不同類的區(qū)域，由于重疊度較高勢(shì)必導(dǎo)致分類算法的學(xué)習(xí)性能下降。

由于樣本比例懸殊和重疊度較高是導(dǎo)致不平衡數(shù)據(jù)集學(xué)習(xí)困難的主要原因，現(xiàn)有的研究也是集中在數(shù)據(jù)抽樣技術(shù)和分類算法改進(jìn)兩方面。

1.1基于數(shù)據(jù)采樣

數(shù)據(jù)抽樣技術(shù)的目的是調(diào)整少數(shù)類和多數(shù)類的比例，降低數(shù)據(jù)不平衡度，抽樣技術(shù)分為兩類：向下抽樣，即減少多數(shù)類數(shù)量；向上抽樣，即增加少數(shù)類數(shù)量。常用的方法有：

隨機(jī)向下抽樣：隨機(jī)去掉樣本中的多數(shù)類，以降低不平衡度?？赡軙?huì)造成多數(shù)類表達(dá)能力的缺失。

隨機(jī)向上抽樣：隨機(jī)復(fù)制樣本中的少數(shù)類達(dá)到增加少數(shù)類樣本數(shù)量的效果，可能會(huì)造成對(duì)于少數(shù)類的過學(xué)習(xí)。

虛擬少數(shù)類向上采樣（synthetic minority over-sampling technique，SMOTE）：它基于如下假設(shè)，兩個(gè)距離較近的少數(shù)類樣本之間仍是少數(shù)類，人工構(gòu)造新少數(shù)樣本。SMOTE算法步驟如表1：

SMOTE算法雖然避免了抽樣的隨機(jī)性，但依然存在一些不足，例如新樣本的有效性，如有k個(gè)近鄰中有散列點(diǎn)可能造成新樣本點(diǎn)的有效性差。另外可能增加邊界的點(diǎn)，使兩類的邊界更加模糊。對(duì)于孤立少數(shù)樣本，smote算法會(huì)產(chǎn)生更多噪聲。

以上都是基于采樣技術(shù)，改變?cè)瓨颖緮?shù)據(jù)集的分布結(jié)構(gòu)，以達(dá)到降低數(shù)據(jù)集不平衡度的效果。

1.2算法改進(jìn)

支持向量機(jī)利用核函數(shù)將線性不可分轉(zhuǎn)化為特征空間線性可。傳統(tǒng)SVM（支持向量機(jī)）分類面會(huì)偏向少數(shù)類，Wu等人通過調(diào)整邊界，修改核函數(shù)修正偏差。傳統(tǒng)集成分類算法錯(cuò)分樣本和正分樣本的權(quán)重相同，導(dǎo)致對(duì)少數(shù)類分類效果差，Joshi等人針對(duì)此提出在每次迭代時(shí)賦予正分樣本和錯(cuò)分樣本不同的權(quán)重，提高對(duì)少數(shù)類的分類效果。

基于分類算法的改進(jìn)沒有改變?cè)瓨颖緮?shù)據(jù)集分布結(jié)構(gòu)，其核心是側(cè)重對(duì)少數(shù)類的劃分，加大少數(shù)類的誤判代價(jià)，使學(xué)習(xí)器對(duì)少數(shù)類敏感。但當(dāng)少數(shù)類樣本不能反映其真實(shí)分布時(shí)，容易出現(xiàn)過擬合現(xiàn)象。

2隨機(jī)森林

隨機(jī)森林（Random Forest，RF）是一種基于Bagging和隨機(jī)子空間技術(shù)得到集成分類學(xué)習(xí)器模型，2001年，由Breiman明確提出。它由多個(gè)分類回歸樹（Classification and Regression Tree，CART）組成，并最終通過投票來決定最優(yōu)分類結(jié)果。RF算法流程如表2：

隨機(jī)森林已經(jīng)被證明有分類效果更加準(zhǔn)確、不易產(chǎn)生過擬合、平衡誤差和多分類泛化能力顯著等優(yōu)點(diǎn)，此外隨機(jī)森林根據(jù)需求不僅可以輸出所屬類別還能輸出屬于該類別的概率。因?yàn)镃ART樹也是對(duì)特征空間進(jìn)行隨機(jī)子空間劃分從而判斷類別，故CART樹錯(cuò)判的樣例也集中在兩類之間邊界和類間重疊度較高的區(qū)域，因此可以利用隨機(jī)森林的特性，根據(jù)錯(cuò)判率找到重疊度較高的區(qū)域。

3基于二次隨機(jī)森林的算法改進(jìn)

分類算法的改進(jìn)多是在算法進(jìn)行優(yōu)化沒有改變數(shù)據(jù)集的結(jié)構(gòu)，而隨機(jī)森林可以偵測(cè)出混雜在少數(shù)類樣本空間中的多數(shù)類，不妨利用這種特性，將利用隨機(jī)森林偵測(cè)到的噪音去除或者將多數(shù)類別去除，再對(duì)修改過的訓(xùn)練集進(jìn)行隨機(jī)森林訓(xùn)練，這樣可以減小數(shù)據(jù)集的不平衡度，同時(shí)降低數(shù)據(jù)重疊度，可以稱這種算法為TRF（two randomforst）流程如表3：

4不平衡數(shù)據(jù)集分類評(píng)價(jià)方法

根據(jù)具體應(yīng)用場景，不同分類學(xué)習(xí)器模型考慮的評(píng)價(jià)指標(biāo)不同。不過常見的評(píng)價(jià)指標(biāo)是基于表4的混淆矩陣。

5實(shí)驗(yàn)結(jié)果

為了驗(yàn)證TRF算法對(duì)不平衡數(shù)據(jù)集的分類性能，選擇5組不平衡程度大小不一的UCI數(shù)據(jù)集來交叉驗(yàn)證算法有效性。

5.1數(shù)據(jù)集的預(yù)處理

對(duì)具備多個(gè)種類的數(shù)據(jù)集合并某些類或者單獨(dú)比較兩個(gè)類別；對(duì)類型數(shù)據(jù)采用one-hot編碼，變成數(shù)值型數(shù)據(jù)；對(duì)錯(cuò)值進(jìn)行改正，對(duì)空值進(jìn)行填充，對(duì)數(shù)據(jù)集進(jìn)行隨機(jī)排序和抽樣。UCI的數(shù)據(jù)集信息如表5。

由于在不平衡數(shù)據(jù)集的實(shí)際應(yīng)用場景中，少數(shù)類的召回率（識(shí)別出少數(shù)類的數(shù)目）提高對(duì)業(yè)務(wù)至關(guān)重要，同時(shí)不應(yīng)該出現(xiàn)準(zhǔn)確率降低太多（識(shí)別少數(shù)類的范圍擴(kuò)大）的情形出現(xiàn)，由于F值兼顧了準(zhǔn)確率和召回率，并偏向兩者之間較小的值，因此如果F值增大說明準(zhǔn)確率和召回率都得到了一定提高。因此最終確定召回率和F值作為分類性能的評(píng)價(jià)指標(biāo)。為了讓算法之間性能比較更加具備客觀性，以下結(jié)論都是進(jìn)行10次實(shí)驗(yàn)平均以后得到的結(jié)果。

圖1和圖2分別給出了一次隨機(jī)森林和二次隨機(jī)森林算法在不同數(shù)據(jù)集上召回率和F值的比較。

可以看出在Sonar數(shù)據(jù)集上表現(xiàn)性能良好，說明基于二次隨機(jī)森林的分類算法適用于一般數(shù)據(jù)集，在不平衡度同時(shí)在Vehicle、Satimage、Glass和Abalone基于二次隨機(jī)森林的分類算法的兩個(gè)度量指標(biāo)都優(yōu)于一次隨機(jī)森林算法，實(shí)驗(yàn)結(jié)果表明基于二次隨機(jī)森林的分類算法在處理不平衡數(shù)據(jù)集問題上有良好的性能。

6結(jié)論

不平衡數(shù)據(jù)集的分類學(xué)習(xí)由于其特殊性給傳統(tǒng)分類算法帶來極大挑戰(zhàn)，本文從抽樣技術(shù)和算法改進(jìn)兩方面概述了現(xiàn)今對(duì)不平衡數(shù)據(jù)集的學(xué)習(xí)研究，根據(jù)隨機(jī)森林的特性，提出采用二次隨機(jī)森林算法，改變?cè)?xùn)練數(shù)據(jù)集結(jié)構(gòu)，通過在UCI數(shù)據(jù)集上的實(shí)驗(yàn)證明此算法較普通的隨機(jī)森林算法在召回率和F值指標(biāo)上表現(xiàn)較好，在處理不平衡數(shù)據(jù)集上有明顯優(yōu)勢(shì)。