基于集成學(xué)習(xí)和代價(jià)敏感的類別不平衡數(shù)據(jù)分類算法

賀指陳

（廣東工業(yè)大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院 廣東 廣州 510520）

0 引言

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

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

一個(gè)方向是數(shù)據(jù)預(yù)處理方案，包括欠采樣方法、過采樣方法和混合采樣方法。欠采樣是指減少多數(shù)類樣本的數(shù)量使之與少數(shù)類樣本的數(shù)量達(dá)到平衡，隨機(jī)欠采樣算法的優(yōu)點(diǎn)是簡單快速，但是它可能會(huì)遺漏樣本中的重要信息導(dǎo)致算法分類邊界變得模糊。過采樣方法是通過生成新的少數(shù)類的樣本使之與多數(shù)類樣本達(dá)到平衡。隨機(jī)簡單過采樣因?yàn)槠潆S機(jī)性容易使分類邊界侵入多數(shù)類的區(qū)域?qū)е滦Ч患选hawle，Bowyer & Hall等[6]的SMOTE算法是一種典型的過采樣方法，它采用的采樣策略是每次隨機(jī)在兩個(gè)近鄰的少數(shù)類樣本點(diǎn)之間隨機(jī)生成新的樣本點(diǎn)，通過迭代不斷生成新少數(shù)類樣本點(diǎn)來平衡數(shù)據(jù)集的不平衡性。Han，Wang & Mao等[7]認(rèn)為更重要且難以區(qū)分的樣本集中在分類邊界上，對(duì)此提出了Borderline-SMOTE算法，該算法更加重視在分類邊界附近的少數(shù)類樣本，通過迭代，在分類邊界附近生成新的樣本點(diǎn)使分類邊界變得清晰。混合采樣是對(duì)多數(shù)類集合進(jìn)行欠采樣，少數(shù)類集合進(jìn)行過采樣組成新的訓(xùn)練集合再進(jìn)行分類器的訓(xùn)練。馮宏偉等[8]的BMS方法引進(jìn)“變異系數(shù)”識(shí)別出邊界域和非邊界域，進(jìn)而過采樣邊界域中的少數(shù)類樣本，欠采樣非邊界域中的多數(shù)類樣本來解決問題。

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

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

1 相關(guān)工作

1.1 Adaboost算法

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

Adaboost算法執(zhí)行步驟如下：

根據(jù)對(duì)Adaboost算法的研究，不難知道Adaboost算法雖然能關(guān)注到那些難被分類的樣本，但是在處理類別不均衡的分類問題時(shí)，因?yàn)樯贁?shù)類集合樣本數(shù)目的絕對(duì)稀少會(huì)讓整個(gè)算法收斂的很慢以至于效果不佳。同時(shí)Adaboost算法有對(duì)噪聲點(diǎn)很敏感這一缺點(diǎn)，所以噪聲點(diǎn)對(duì)算法的分類邊界也會(huì)有很大的影響。

1.2 EasyEnsemble算法

EasyEnsemble是一種帶雙層結(jié)構(gòu)的集成算法，綜合了Boosting、Bagging和欠采樣技術(shù)，先從多數(shù)類中挑選出個(gè)樣本數(shù)量等于少數(shù)類樣本數(shù)量的子集，再將子集與少數(shù)類集合成個(gè)新的訓(xùn)練集，再將訓(xùn)練集用Adaboost算法進(jìn)行訓(xùn)練生成弱分類器，最后將所有的弱分類器結(jié)合成強(qiáng)分類器。

EasyEnsemble算法執(zhí)行步驟如下：

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

2 基于集成學(xué)習(xí)和代價(jià)敏感的類別不平衡數(shù)據(jù)分類算法

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

其中，n為少數(shù)類樣本數(shù)量，m為多數(shù)類樣本數(shù)量，k為數(shù)據(jù)樣本數(shù)量。

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

USCensemble算法執(zhí)行步驟如下：

3 實(shí)驗(yàn)結(jié)果與分析

3.1 評(píng)價(jià)標(biāo)準(zhǔn)

對(duì)于類別不平衡的分類算法，一般常用于評(píng)價(jià)分類算法的指標(biāo)，如準(zhǔn)確率和錯(cuò)誤率已經(jīng)不能很好地評(píng)價(jià)算法性能了。因?yàn)榉诸惼鲿?huì)傾向于將少數(shù)類分到多數(shù)類去，由于少數(shù)類的樣本數(shù)量絕對(duì)稀少，這樣很輕松就能得到很高的準(zhǔn)確率。然而這樣并不能滿足算法希望更關(guān)注于少數(shù)類的分類狀況的需要。在二分類問題中，一般將數(shù)目少的類別（少數(shù)類）視為正例，數(shù)目多的類別（多數(shù)類）視為負(fù)例，混淆矩陣見表1。TP（TRUE POSITIVE）正類樣本分為正類的頻數(shù)，F(xiàn)P（FALSE POSITIVE）負(fù)類樣本分為正類樣本的頻數(shù)，F(xiàn)N（FALSE NEGATIVE）正類樣本分為負(fù)類的頻數(shù)，TN（TRUE NEGATIVE）負(fù)類樣本分為負(fù)類的頻數(shù)，見表1。

表1 混淆矩陣

類別不平衡分類算法需要新的評(píng)價(jià)指標(biāo)，因?yàn)槿蝿?wù)是對(duì)類別不平衡的樣本進(jìn)行分類，更關(guān)注少數(shù)類的分類情況，所以本文選取Recall、f1-measure值和g-mean值來對(duì)算法效果進(jìn)行評(píng)價(jià)。

3.2 實(shí)驗(yàn)方法

本文選擇Adaboost、Adacost、USCboost、EasyEnsemble 4種算法作為對(duì)比算法，都采用深度為5的算法作為基分類器。在10個(gè)uci數(shù)據(jù)集上進(jìn)行性能評(píng)測(cè)，數(shù)據(jù)集信息見表2；本文將數(shù)據(jù)集的目標(biāo)類別設(shè)置為正類，其他類別設(shè)置為負(fù)類。因?yàn)镋asyEnsemble和本文的USCboost算法都有多層結(jié)構(gòu)，此時(shí)需要事先設(shè)定基分類器。表2第4列給出了基分類器設(shè)置，例如3*9表示在abalone數(shù)據(jù)集上采樣出9組子集，每組子集數(shù)據(jù)訓(xùn)練3次，其他類同。為保證公平性，Adaboost、Adacost、USCboost算法都訓(xùn)練27個(gè)基訓(xùn)練器，采用了10倍交叉驗(yàn)證，以考察算法的泛化性，見表2。

表2 實(shí)驗(yàn)數(shù)據(jù)集

3.3 結(jié)果與分析

實(shí)驗(yàn)分析了5種算法在10個(gè)uci數(shù)據(jù)集下各自的Recall值、f1-measure值和g-mean值，并加粗了每組數(shù)據(jù)下數(shù)值最高的評(píng)價(jià)指標(biāo)，見表3。

表3 不同算法R、f1、G值對(duì)比

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

為了更直觀地對(duì)比3種算法的性能，圖1、圖2和圖3展示了USCboost算法、EasyEnsemble算法和USCensemble算法在10個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果柱狀圖。其中，橫坐標(biāo)表示數(shù)據(jù)集，縱坐標(biāo)表示實(shí)驗(yàn)評(píng)價(jià)指標(biāo)數(shù)值取值范圍?？梢园l(fā)現(xiàn)USCensemble在分類任務(wù)中往往有較高的Recall值，能有效將正類樣本識(shí)別出來，這是因?yàn)閁SCensemble任務(wù)，采取了多層結(jié)構(gòu)能有效地避免噪聲的影響，同時(shí)在采樣分組時(shí)能關(guān)注那些在分類邊界附近分錯(cuò)了的樣本點(diǎn)，實(shí)現(xiàn)了有著較高Recall值的同時(shí)，保持不錯(cuò)的f1-measure值和g-mean值的目的，證實(shí)了該方法的有效性。

4 結(jié)語

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