劉學(xué)+張素偉

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

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

引言

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

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

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

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

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

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

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

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

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

隨機向下抽樣：隨機去掉樣本中的多數(shù)類，以降低不平衡度?？赡軙斐啥鄶?shù)類表達能力的缺失。

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

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

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

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

1.2算法改進

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

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

2隨機森林

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

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

3基于二次隨機森林的算法改進

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

4不平衡數(shù)據(jù)集分類評價方法

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

5實驗結(jié)果

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

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

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

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

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

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

6結(jié)論

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