基于二次隨機森林的不平衡數據分類算法

劉學+張素偉

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

關鍵詞：模式識別；不平衡數據；隨機森林；模糊邊界

引言

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

傳統分類方法以分類精度作為評判學習器的指標，在不平衡數據集中，學習器的預測結果肯定更加偏向比例更大的類別。weiss的實驗，以分類精度為準則的學習器模型會導致識別少數類準確率下降，這樣的分類學習器模型會傾向將樣本預測為多數類。

本文在研究不平衡數據集特點和隨機森林的特性基礎上，提出了針對不平衡數據的二次隨機森林分類算法，通過改變樣本數據結構改善分類性能。

1不平衡數據的分類研究

由于多數類分類問題可以轉化為二分類問題，因此本文研究是基于二分類的不平衡數據集分類問題加以研究。正類為多數類，負類為少數類。

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

由于樣本比例懸殊和重疊度較高是導致不平衡數據集學習困難的主要原因，現有的研究也是集中在數據抽樣技術和分類算法改進兩方面。

1.1基于數據采樣

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

隨機向下抽樣：隨機去掉樣本中的多數類，以降低不平衡度。可能會造成多數類表達能力的缺失。

隨機向上抽樣：隨機復制樣本中的少數類達到增加少數類樣本數量的效果，可能會造成對于少數類的過學習。

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

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

以上都是基于采樣技術，改變原樣本數據集的分布結構，以達到降低數據集不平衡度的效果。

1.2算法改進

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

基于分類算法的改進沒有改變原樣本數據集分布結構，其核心是側重對少數類的劃分，加大少數類的誤判代價，使學習器對少數類敏感。但當少數類樣本不能反映其真實分布時，容易出現過擬合現象。

2隨機森林

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

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

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

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

4不平衡數據集分類評價方法

根據具體應用場景，不同分類學習器模型考慮的評價指標不同。不過常見的評價指標是基于表4的混淆矩陣。

5實驗結果

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

5.1數據集的預處理

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

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

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

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

6結論

不平衡數據集的分類學習由于其特殊性給傳統分類算法帶來極大挑戰，本文從抽樣技術和算法改進兩方面概述了現今對不平衡數據集的學習研究，根據隨機森林的特性，提出采用二次隨機森林算法，改變原訓練數據集結構，通過在UCI數據集上的實驗證明此算法較普通的隨機森林算法在召回率和F值指標上表現較好，在處理不平衡數據集上有明顯優勢。