基于集成學習和代價敏感的類別不平衡數據分類算法

賀指陳

（廣東工業大學數學與統計學院 廣東 廣州 510520）

0 引言

現實生活中充斥著大量的類別不平衡的數據，類別不平衡的數據有著其某一類別樣本數量遠遠多余其他類別的樣本數量的數據特點。樣本多的類別為多數類，反之樣本少的類別叫作少數類，即多數類樣本數量遠遠大于少數類樣本數量的數據集稱之為類別不平衡數據，如垃圾短信識別[1]、客戶行為異常識別[2]、信用卡欺詐檢測[3]、故障檢測[4]等數據都是類別不平衡的數據。

傳統的分類算法在處理類別不平衡數據時會傾向于把少數類和多數類分為一類，由于少數類樣本量很少，這樣處理整體的正確率盡管比較高，但是忽略掉了更應被重視的少數類，在實際應用中往往不能起到研究人員想要的效果[5]。為了較好地解決這個問題，研究人員提出了兩個方向的解決方案。

一個方向是數據預處理方案，包括欠采樣方法、過采樣方法和混合采樣方法。欠采樣是指減少多數類樣本的數量使之與少數類樣本的數量達到平衡，隨機欠采樣算法的優點是簡單快速，但是它可能會遺漏樣本中的重要信息導致算法分類邊界變得模糊。過采樣方法是通過生成新的少數類的樣本使之與多數類樣本達到平衡。隨機簡單過采樣因為其隨機性容易使分類邊界侵入多數類的區域導致效果不佳。Chawle，Bowyer & Hall等[6]的SMOTE算法是一種典型的過采樣方法，它采用的采樣策略是每次隨機在兩個近鄰的少數類樣本點之間隨機生成新的樣本點，通過迭代不斷生成新少數類樣本點來平衡數據集的不平衡性。Han，Wang & Mao等[7]認為更重要且難以區分的樣本集中在分類邊界上，對此提出了Borderline-SMOTE算法，該算法更加重視在分類邊界附近的少數類樣本，通過迭代，在分類邊界附近生成新的樣本點使分類邊界變得清晰?；旌喜蓸邮菍Χ鄶殿惣线M行欠采樣，少數類集合進行過采樣組成新的訓練集合再進行分類器的訓練。馮宏偉等[8]的BMS方法引進“變異系數”識別出邊界域和非邊界域，進而過采樣邊界域中的少數類樣本，欠采樣非邊界域中的多數類樣本來解決問題。

另一個方向是從算法本身出發，其中常見的有代價敏感算法、集成學習。代價敏感算法[9]通過對樣本賦予不同的權重更加重視少數類樣本的分類來解決此問題。集成學習方法主要可以分為 bagging和 boosting兩類，bagging是一種并行的算法，主要代表是隨機森林[10]（RandomForest），它利用bootstrap從原數據集中對屬性隨機采樣出多個不同屬性的子集作為訓練集，對每個采樣出來的子集進行訓練，然后把訓練出多棵決策樹整合成森林。Boosting串行的算法，其主要代表是Adaboost[11]算法，通過訓練弱分類器不斷地更新訓練數據集的樣本權重和分類器的權重，正確劃分的樣本權重會被降低，錯誤劃分的樣本權重會被增大。最后將所有的弱分類器進行加權和運算組成一個強分類器集。Zhang[12]在Adaboost算法基礎上提出了錯分代價因子并將其加入到了樣本權重的更新中，使得少數類錯分時其對應的樣本權重可以快速提高。Chawla，Lazarevic & Hall等[13]提出SMOTEBoost，將過采樣思想與Adaboost結合以此解決少數類樣本識別困難的問題。王和閆[14]提出USCboost算法，結合了Adacost算法和欠采樣的思想，在每個基分類器訓練完成之后，再根據多數類樣本的樣本權重，從大到小進行欠采樣之后與少數類結合成臨時訓練集，以此訓練下一個基分類器。Easyensemble是Liu，Wu & Zhou等[15]提出的一種集成學習的算法，該算法的結構與隨機森林算法類似，先將多數類集合進行欠采樣，采樣出多個子集再分別與少數類集合結合成多個臨時訓練集，再以Adaboost算法對每個臨時訓練集進行訓練，生成基分類器。

基于以上研究，本文將代價敏感思想引入Easyensemble算法，提出了USCensemble算法。該算法能有效減少噪聲的影響，改進了欠采樣的策略，將欠采樣重心放在難以分類的多數類樣本點上的同時，保留了臨時訓練集的隨機性，提升了類別不平衡數據分類任務的分類性能。

1 相關工作

1.1 Adaboost算法

由多個分類器組合在一起共同完成任務的集成學習有著很好的泛化能力，集成學習不僅要求基分類器的效果好，還要求基分類器互不相同。Adaboost算法是一種典型的集成學習算法，每一輪通過弱分類器的預測結果來調整樣本權重與分類器權重。分類正確的樣本其樣本權重降低，分類錯誤的權重升高，更加關注被錯分的樣本，使下一輪訓練時著重改正之前的錯誤。最后通過加權平均法來整合所有的分類器以求理想的分類器有著不錯的分類效果。通常將少數類記為1，多數類記為-1。

Adaboost算法執行步驟如下：

根據對Adaboost算法的研究，不難知道Adaboost算法雖然能關注到那些難被分類的樣本，但是在處理類別不均衡的分類問題時，因為少數類集合樣本數目的絕對稀少會讓整個算法收斂的很慢以至于效果不佳。同時Adaboost算法有對噪聲點很敏感這一缺點，所以噪聲點對算法的分類邊界也會有很大的影響。

1.2 EasyEnsemble算法

EasyEnsemble是一種帶雙層結構的集成算法，綜合了Boosting、Bagging和欠采樣技術，先從多數類中挑選出個樣本數量等于少數類樣本數量的子集，再將子集與少數類集合成個新的訓練集，再將訓練集用Adaboost算法進行訓練生成弱分類器，最后將所有的弱分類器結合成強分類器。

EasyEnsemble算法執行步驟如下：

在EasyEnsemble算法中θi為調節參數，這一參數不僅需要自己調試，同時會根據臨時數據集數量的不同而需要計算多個θi，這讓EasyEnsemble算法的前期工作變得復雜。同時每一組訓練集都是隨機抽樣，不能保證分類器的多樣性，可能會丟失原數據集的某些特征，以至于在某些情況下效果不好。

2 基于集成學習和代價敏感的類別不平衡數據分類算法

通過對類別不平衡數據和現有針對此問題的分類算法所存在的不足進行研究，Adaboost算法雖然能在迭代過程中不停地提高錯分樣本的權重，但是由于此類數據多數類樣本數量與少數類樣本數量之比往往很大，以及數據本身類別之間的區分難度、特征維度等因素，容易導致Adaboost收斂過慢，效果不佳。于是本文算法將代價敏感思想引入Adaboost算法，賦予少數類樣本更大的錯分代價，使每一次迭代都能快速提高錯誤分類的少數類的樣本權重，降低多數類的樣本權重。

其中，n為少數類樣本數量，m為多數類樣本數量，k為數據樣本數量。

考慮到EasyEnsemble算法結構能減少Adaboost算法中噪音的影響和分類邊界附近有著更豐富的分類信息，本文提出了一類新的算法（USCensemble），該算法的關鍵是每個臨時訓練集是根據上一個分類器得到結果生成的，從多數類中選出權重重大的樣本作為子集并與少數類樣本結合作為臨時訓練集。本文新引入錯分代價Ci和樣本權重調節因子βi。具體計算公式如下：

USCensemble算法執行步驟如下：

3 實驗結果與分析

3.1 評價標準

對于類別不平衡的分類算法，一般常用于評價分類算法的指標，如準確率和錯誤率已經不能很好地評價算法性能了。因為分類器會傾向于將少數類分到多數類去，由于少數類的樣本數量絕對稀少，這樣很輕松就能得到很高的準確率。然而這樣并不能滿足算法希望更關注于少數類的分類狀況的需要。在二分類問題中，一般將數目少的類別（少數類）視為正例，數目多的類別（多數類）視為負例，混淆矩陣見表1。TP（TRUE POSITIVE）正類樣本分為正類的頻數，FP（FALSE POSITIVE）負類樣本分為正類樣本的頻數，FN（FALSE NEGATIVE）正類樣本分為負類的頻數，TN（TRUE NEGATIVE）負類樣本分為負類的頻數，見表1。

表1 混淆矩陣

類別不平衡分類算法需要新的評價指標，因為任務是對類別不平衡的樣本進行分類，更關注少數類的分類情況，所以本文選取Recall、f1-measure值和g-mean值來對算法效果進行評價。

3.2 實驗方法

本文選擇Adaboost、Adacost、USCboost、EasyEnsemble 4種算法作為對比算法，都采用深度為5的算法作為基分類器。在10個uci數據集上進行性能評測，數據集信息見表2；本文將數據集的目標類別設置為正類，其他類別設置為負類。因為EasyEnsemble和本文的USCboost算法都有多層結構，此時需要事先設定基分類器。表2第4列給出了基分類器設置，例如3*9表示在abalone數據集上采樣出9組子集，每組子集數據訓練3次，其他類同。為保證公平性，Adaboost、Adacost、USCboost算法都訓練27個基訓練器，采用了10倍交叉驗證，以考察算法的泛化性，見表2。

表2 實驗數據集

3.3 結果與分析

實驗分析了5種算法在10個uci數據集下各自的Recall值、f1-measure值和g-mean值，并加粗了每組數據下數值最高的評價指標，見表3。

表3 不同算法R、f1、G值對比

f1-measure值和g-mean是能體現類別不平衡分類算法性能的有效指標，從表3來看Adaboost算法在uci數據集上的Recall值、f1-measure值和g-mean值都不太理想，綜合表現較差，不能很好地完成類別不平衡的分類任務。盡管Adacost算法在一些數據集的表現非常不錯，但在大部分數據集上都沒有較高的f1-measure值和g-mean值。從f1-measure值和g-mean值上來看USCboost、EasyEnsemble、USCensemble算法對類別不平衡數據的分類任務有著較好的效果。這3種算法在處理類別不平衡數據分類任務時是有效的。

為了更直觀地對比3種算法的性能，圖1、圖2和圖3展示了USCboost算法、EasyEnsemble算法和USCensemble算法在10個數據集上的實驗結果柱狀圖。其中，橫坐標表示數據集，縱坐標表示實驗評價指標數值取值范圍?？梢园l現USCensemble在分類任務中往往有較高的Recall值，能有效將正類樣本識別出來，這是因為USCensemble任務，采取了多層結構能有效地避免噪聲的影響，同時在采樣分組時能關注那些在分類邊界附近分錯了的樣本點，實現了有著較高Recall值的同時，保持不錯的f1-measure值和g-mean值的目的，證實了該方法的有效性。

4 結語

本文通過對現有的Adaboost類算法在類別不平衡的分類任務上存在的問題進行研究。結合各類算法的優點，采取多層迭代的方式和代價敏感的思想，避免了噪聲的巨大影響，同時關注于分類邊界上的信息，使算法更在意少數類的分類情況而又不過度擬合。本文發現類別不平衡度對算法性能影響有限，而各類別之間的差異程度會對算法性能產生一定的影響。因此對數據集采取一定的預處理，深度挖掘原始數據的特征信息是否能提高算法的性能將是今后研究的重點。