HSMOTE－AdaBoost： 改進混合邊界重采樣集成分類算法

李 靜， 劉 姜， 倪 楓， 李笑語

（上海理工大學(xué)管理學(xué)院， 上海 200093）

0 引 言

在實際生活中，大部分的數(shù)據(jù)集都是不平衡的，即某些類會比其他類具有更多的實例，在這種情況下少數(shù)類的信息得不到充分的利用［1］。 類不平衡問題給標準的分類學(xué)習(xí)算法帶來了巨大的挑戰(zhàn)，在不平衡的數(shù)據(jù)集上，大多數(shù)分類器傾向于對少數(shù)實例進行錯誤分類，而不是對多數(shù)實例進行錯誤分類［2－4］。 但在現(xiàn)實生活中，少數(shù)類的錯分代價會遠高于多數(shù)類。 類不平衡問題普遍存在于許多領(lǐng)域，如網(wǎng)絡(luò)入侵檢測［5］、情感分析［6－7］、欺詐檢測［8－9］、醫(yī)療疾病診斷檢測［10］和故障診斷［11］等領(lǐng)域。 大多數(shù)標準分類算法往往表現(xiàn)出對多數(shù)類的偏倚，因此類的不平衡性往往會損害標準分類器的性能，尤其是對少數(shù)類的分類性能［12－13］。

目前，對于不平衡數(shù)據(jù)集分類問題的解決方案可以分為：數(shù)據(jù)級、算法級和集成層面［14－15］。 其中，數(shù)據(jù)級解決方案包括許多不同形式的重采樣技術(shù)，如隨機過采樣（ROS）和隨機欠采樣（RUS）［16－17］。其中，具有代表性的有Chawla 等學(xué)者［18］提出了一新型過采樣方法，SMOTE 在少數(shù)類樣本與其k 近鄰的連線上隨機生成新的樣本。 He 等學(xué)者［19］開發(fā)了一種自適應(yīng)合成采樣（ADASYN），使用密度分布來計算出每個少數(shù)樣本需要合成的新樣本數(shù)量。 此外，還有幾種混合的采樣技術(shù)，其中一些方法就是將過采樣與數(shù)據(jù)清理技術(shù)相結(jié)合，以減少過采樣方法引入的重疊。 典型的例子是SMOTE－Tomek［20］和SMOTE－ENN［21］。 這些數(shù)據(jù)級方法雖然簡單易用，但采樣方法難以修改數(shù)據(jù)的分布和偏好相關(guān)聯(lián)，一方面，欠采樣會使數(shù)據(jù)集中一些有價值的數(shù)據(jù)信息未能得到利用；另一方面，過采樣會生成多余數(shù)據(jù)，尤其是產(chǎn)生噪聲數(shù)據(jù)。 算法級的解決方案旨在開發(fā)新的算法或修改現(xiàn)有的算法，加強對少數(shù)類分類算法的學(xué)習(xí)。 研究中，最受歡迎的分支是代價敏感學(xué)習(xí)，例如，Ting［22］提出了一種實例加權(quán)方法來裁剪代價敏感樹以提高不平衡數(shù)據(jù)集的分類效果。Zhang 等學(xué)者［23］通過對目標函數(shù)中的多數(shù)類和少數(shù)類設(shè)置不同的代價，提出了一種代價敏感神經(jīng)網(wǎng)絡(luò)算法，使得少數(shù)類樣本盡可能地被識別。 其他基于原有算法的改進方案通常是對現(xiàn)有分類算法的改進，文獻［24－26］通過引入權(quán)重參數(shù)來調(diào)整分類決策函數(shù)，使其向少數(shù)類樣本偏倚。 然而算法的應(yīng)用具有特定的情形，大多數(shù)的分類模型一旦被確定，則不會動態(tài)地調(diào)整相應(yīng)的模型結(jié)構(gòu)及其參數(shù)，使得這些算法級改進方法無法動態(tài)地學(xué)習(xí)新增的樣本。

集成層面解決方案就是將多個弱分類模型通過一定方式進行組合，得到一個新的、泛化性能更好的強分類器。 Freund 等學(xué)者［27］提出的自適應(yīng)增強（Adaptive Boosting，AdaBoost）算法是Boosting 族中的代表算法。 與其他分類器相比，AdaBoost 能夠有效地避免過擬合。 文獻［28－29］分別將AdaBoost 與過采樣和欠采樣結(jié)合， 提出 SMOTEBoost 和RUSBoost 算法。 SMOTEBoost 運用SMOTE 進行少數(shù)類樣本的合成，經(jīng)過多次迭代得到最終的強分類器。 但SMOTEBoost 算法在訓(xùn)練過程中生成的噪聲數(shù)據(jù)會對分類性能產(chǎn)生影響。 RUSBoost 則采用欠采樣方法，先隨機刪除一些多數(shù)類樣本，隨后使用刪除后的數(shù)據(jù)構(gòu)造弱分類器。 文獻［30］提出一種新的學(xué)習(xí)算法PCBoost，該算法考慮了屬性特征，對少數(shù)類進行隨機過采樣，接著使用信息增益率來構(gòu)造弱分類器，訓(xùn)練中錯誤分類的樣本會被刪除。

上述研究中，雖然有不少基于采樣方法與AdaBoost 進行結(jié)合，但在采樣方法上還需做進一步探討。 由于集成學(xué)習(xí)在分類性能上的優(yōu)越性以及過采樣方法使用的普遍性，本文重點關(guān)注采樣方法與集成學(xué)習(xí)結(jié)合構(gòu)建分類器。 現(xiàn)有的過采樣方法容易引入影響分類性能的噪聲樣本，而欠采樣則會丟失有用的多數(shù)類樣本的特征信息，尤其是位于分類邊界的多數(shù)類樣本。

針對以上數(shù)據(jù)級改進方案中采樣方法存在易受噪聲影響和丟失多數(shù)類樣本特征信息的問題，本文考慮了多數(shù)類樣本的類內(nèi)差異，并保留邊界多數(shù)類樣本；對少數(shù)類和多數(shù)類采取融合SMOTE 過采樣和RUS 欠采樣的混合采樣策略，并結(jié)合集成技術(shù)AdaBoost，提出了HSMOTE－AdaBoost 算法。 首先，針對少數(shù)類樣本中數(shù)據(jù)缺少和噪聲干擾的問題，引入經(jīng)典的SMOTE 采樣算法和K 近鄰噪聲清除算法。 其次，由于現(xiàn)有的大多數(shù)算法尚未考慮到多數(shù)類樣本之間的類內(nèi)差異，本文基于平均歐式距離識別并保留邊界多數(shù)類樣本，再對剩下的樣本進行隨機欠采樣。 最后， 運用以J48 為基分類器的AdaBoost 算法進行分類。 結(jié)果表明，本文所提出的HSMOTE－AdaBoost 算法與傳統(tǒng)的SMOTE－Boost，RUS－ Boost， PC － Boost 算法及改進后的算法KSMOTE－AdaBoost［31］相比，具有更好的分類效果。

1 理論基礎(chǔ)

1.1 SMOTE 算法

Chawla 等學(xué)者［18］于2002 年提出了少數(shù)類樣本合成技術(shù)，即SMOTE。 該算法的流程步驟如下：

原始訓(xùn)練樣本為Tra，少數(shù)類樣本是P，多數(shù)類樣本是NP＝ ｛p1，p2，…，ppnum｝，N＝ ｛n1，n2，…，nnmum｝，這里pnum，nmum分別表示少數(shù)類樣本個數(shù)和多數(shù)類樣本個數(shù)。

（1）計算少數(shù)類中的每個樣本點pi與所有的少數(shù)類樣本P的歐式距離，得到樣本點的k 近鄰。

（2）依據(jù)樣本的采樣倍率U， 在k 近鄰之間進行線性插值。

（3）合成新的少數(shù)類樣本：

其中，dj是少數(shù)類樣本點與其近鄰的距離；rj是介于0 到1 之間的隨機數(shù)。

（4）新合成的少數(shù)類樣本與原始訓(xùn)練樣本Tra進行合并，得到新的訓(xùn)練樣本。

1.2 AdaBoost 算法

AdaBoost 算法是經(jīng)典的Boosting 算法，通過迭代的方式不斷提高被誤判樣本的權(quán)值，從而進行樣本權(quán)值的更新，分類器在下一次分類會把重心放在那些被誤分的樣本上，以此來達到正確分類所有樣本的目的。 算法的訓(xùn)練過程如下：

輸入Tra＝｛（X1，Y1），（X2，Y2），…，（Xn，Yn）｝為訓(xùn)練數(shù)據(jù)集，Xi表示樣本實例，Yi為類標簽集合，Yi∈｛＋1，－1｝，i＝ 1，2，…，n；迭代循環(huán)次數(shù)為M

輸出最終分類器G（X）

2： form＝1 toM：

2.1： 使用具有權(quán)值分布Dm的訓(xùn)練數(shù)據(jù)集進行學(xué)習(xí)，得到基本分類器Gm（X）

2.2： 算出Gm（X） 在訓(xùn)練數(shù)據(jù)集上的分類誤差率：

這里，I為指示函數(shù)：

2.3：計算Gm（X） 的系數(shù)：

2.4：更新訓(xùn)練數(shù)據(jù)集的權(quán)值分布：

其中，Zm為規(guī)范化因子，計算公式為：

3： 構(gòu)建基本分類器的線性組合：

4： 得到最終的分類器：

2 HSMOTE－AdaBoost 算法

針對不平衡數(shù)據(jù)的二分類問題，過采樣會增加多余數(shù)據(jù)引入噪聲樣本，而欠采樣會丟失一些有用信息，這2 個問題極大地影響了算法的分類性能。HSMOTE－AdaBoost 算法考慮了邊界多數(shù)類樣本特征信息的價值，將SMOTE 算法和RUS 算法進行了結(jié)合，并針對RUS 算法中存在隨機刪除邊界多數(shù)類樣本的問題進行了改進。 位于2 個類邊界上的實例是該分類樣本的必要實例，在確定決策邊界時至關(guān)重要，將其刪除會降低分類器的性能。 因此，本文提出的HSMOTE－AdaBoost 算法考慮了邊界多數(shù)類樣本，并試圖保持必要的多數(shù)類實例，分類模型圖如圖1 所示。 首先，使用SMOTE 過采樣合成少數(shù)類實例，以平衡數(shù)據(jù)集；接著，刪除原始數(shù)據(jù)中的一些噪聲數(shù)據(jù)，提高合成樣本的質(zhì)量；然后，識別多數(shù)類的邊界實例，并將其添加到輸出數(shù)據(jù)集中。 同時，對剩余的數(shù)據(jù)進行隨機欠采樣。 最后，使用AdaBoost 集成算法生成強分類器，實驗結(jié)果表明該分類器的性能得到了有效的提升。

圖1 分類模型圖Fig. 1 Classification model diagram

2.1 算法HSMOTE－AdaBoost 的訓(xùn)練過程

（1）合成少數(shù)類樣本。 將合成少數(shù)類過采樣（SMOTE）預(yù)處理技術(shù)應(yīng)用到數(shù)據(jù)集Timbal中，在少數(shù)類中引入人工實例，生成數(shù)據(jù)集T⌒imbal。 具體步驟詳述如下。

①原始訓(xùn)練樣本是Timbal，少數(shù)類樣本為P，多數(shù)類是N，P＝（p1，p2，…，pn），N＝（n1，n2，…，nm），n，m分別表示少數(shù)類樣本個數(shù)及多數(shù)類樣本個數(shù)。計算少數(shù)類樣本點pj與少數(shù)類P的歐式距離，得到該樣本點的k 近鄰。

②依據(jù)采樣倍率U在k 近鄰中進行線性插值。

③合成新的少數(shù)類樣本：

其中，di表示少數(shù)類樣本點與其近鄰的距離，ri是介于0 到1 之間的隨機數(shù)。

④新合成的少數(shù)類樣本和原始訓(xùn)練樣本進行合并，從而得到新的訓(xùn)練樣本T⌒imbal。

（2）識別和刪除噪聲。 若少數(shù)類樣本點在k 近鄰中有k′個多數(shù)類樣本，顯然0 ≤k′ ≤k，若k′ ≤，則為噪聲。

（3）識別多數(shù)類的邊界樣本Nborder，并將其放入輸出數(shù)據(jù)集Tbal中。 具體步驟分述如下。

①算出各多數(shù)類樣本點ni（i＝1，2，……，m）到少數(shù)類樣本點pj（j＝1，2，…，n） 的距離之和為

②求平均距離：

③當多數(shù)類樣本ni滿足時，將其劃分到Tbal中。

（4）對數(shù)據(jù)集E應(yīng)用隨機欠采樣，將隨機選取的樣本推送到輸出數(shù)據(jù)集Tbal，并推得：

（5）將處理后的平衡數(shù)據(jù)集作為模型的輸入，使用AdaBoost 集成技術(shù)得到最終的分類結(jié)果。

2.2 算法HSMOTE－AdaBoost 的詳細步驟

輸入D為數(shù)據(jù)集，K為過采樣算法中選擇的最近鄰個數(shù)，M為迭代的次數(shù)

輸出集成分類器

1： 將數(shù)據(jù)集D分成10 份，其中2 份為測試集TestData，剩下即訓(xùn)練集TrainData

2： 運用SMOTE 過采樣算法生成新的少數(shù)類樣本

3： 用k 近鄰算法得到少數(shù)類樣本的最近鄰集合，依據(jù)判別條件對噪聲樣本進行識別及刪除。 判別條件為：若少數(shù)類樣本中k 近鄰超過2／3 的樣本是多數(shù)類，則為噪聲樣本

4： 基于所有多數(shù)類樣本點對各個少數(shù)類樣本點的平均歐式距離識別邊界多數(shù)類樣本，并將其單獨放在NewTrainData中。 識別條件為：若該多數(shù)類樣本點到所有少數(shù)類樣本點的歐式距離之和小于平均距離，則該樣本點為邊界多數(shù)類樣本點

5： 對剩余的數(shù)據(jù)進行隨機欠抽樣得到NewTrainData

6： 賦予NewTrainData中每個實例相同的權(quán)重。

7： form＝1 toM

8： 根據(jù)實例的權(quán)值有放回地抽樣得到Dm

9： 由Dm得到基分類器Gm（X）

10： 使用Gm（X） 對NewTrainData中的實例進行分類，根據(jù)式（12）計算Gm（X） 的錯誤率em：

其中，wm，i表示第m輪中第i個實例Xi的權(quán)值；Gm（Xi） ≠Yi表示實例Xi被錯分；Yi為類標簽。

11： ifem ＞0.5 then 轉(zhuǎn)步驟7

12： end if

13： for 對正確分類的每個實例執(zhí)行如下步驟：

15： 歸一化所有實例的權(quán)值

16： end for

17： 將每個類的權(quán)值賦予0，對TestData的所有實例執(zhí)行以下步驟

18： fori＝1 toM：

19： 根據(jù)式（13）計算Gi（X） 對測試集中實例Xi的權(quán)值Wi：

20： 將Wi加到Gi（X） 所預(yù)測的類上，若Xi被正確分類，則其值為0，否則為1。

21： end for

22： 返回權(quán)值最大的類，即為Xi的類別

23： end for

3 仿真實驗

3.1 實驗數(shù)據(jù)集

實驗使用來自KEEL 公開數(shù)據(jù)集的6 組數(shù)據(jù)集，考慮了數(shù)據(jù)集的樣本數(shù)、特征數(shù)及不平衡率。 實驗之前對數(shù)據(jù)集進行預(yù)處理，將訓(xùn)練集和測試集歸一化到［0，1］區(qū)間，表1 展示了實驗數(shù)據(jù)集的基本信息。

表1 實驗數(shù)據(jù)集Tab. 1 Experimental dataset

3.2 性能評價指標

在對數(shù)據(jù)集進行二分類時，不能簡單地采用整體精確度的高低來評價分類器性能的優(yōu)劣。 因為即使分類器對少數(shù)類樣本的識別完全錯誤，總體的精確度也會比較高，所以僅靠這個單一評價指標并沒有參考價值。 為了全面體現(xiàn)分類性能，本文采用了綜合評價指標F － measure，G － mean和AUC，F(xiàn) －measure，G － mean和AUC取值均在0 到1 之間，且值越大，說明分類器的分類性能越好。 在介紹這些指標前，先引入混淆矩陣。 混淆矩陣［32］可以將預(yù)測分類結(jié)果和實際分類結(jié)果以矩陣的形式直觀地表示出來。 混淆矩陣見表2。

表2 混淆矩陣Tab. 2 Confusion matrix

根據(jù)表2 可得到以下評價指標。

（1）召回率（Recall）。 指真少數(shù)類占所有少數(shù)類的比例。 可由如下公式來求值：

（2） 精確率（Precision）。 指真少數(shù)類占所有被預(yù)測為少數(shù)類的比例。 可由如下公式來求值：

（3）F － measure［33］，又稱F － Score，兼顧精確度和召回率。 可由如下公式來求值：

其中，α是取值為1 的比例系數(shù)。

（4）G － mean［34］。 是一種有效衡量不平衡數(shù)據(jù)分類方法的指標，只有正類、負類兩者召回率都高時，G － mean值才會高，表明分類器的分類性能較優(yōu)。 可由如下公式來求值：

（5）AUC［35］。ROC曲線以假正率（FPrate）和真正率（TPrate） 為軸，以可視化的方式展現(xiàn)正確分類的收益和誤分類的代價之間的關(guān)聯(lián)。ROC曲線下方的面積稱為AUC（Area Under Curve），AUC可以量化分類器的預(yù)測性能，AUC的取值范圍為0 到1，AUC值越高，模型的預(yù)測性能越好。

3.3 實驗設(shè)置

為了驗證本文所提出的算法的優(yōu)越性，將本文算法與傳統(tǒng)的SMOTE－Boost，RUS－Boost，PC－Boost及改進后的KSMOTE－AdaBoost 算法進行了比較。本文使用Python 語言，Spyder 開發(fā)環(huán)境對各種算法進行仿真實驗。 與以往文獻［36］一致，SMOTE 算法的k 近鄰數(shù)設(shè)為5 時所合成的少數(shù)類樣本質(zhì)量較高。 實驗選用J48 決策樹作為基分類器，調(diào)用Weka軟件中的C4.5 函數(shù)包實現(xiàn)J48 分類器。 實驗中將數(shù)據(jù)集的20%作為測試集，80%作為訓(xùn)練集，采用10 次五折交叉驗證的平均值作為最終的評價結(jié)果。

3.4 實驗結(jié)果分析

圖2～圖4 及表3～表5 列出了使用本文算法和其他4 種不同采樣方法與集成學(xué)習(xí)技術(shù)結(jié)合算法在6個不同數(shù)據(jù)集上的F － measure、G － mean值及AUC的比較結(jié)果和具體數(shù)值，其中加粗部分為在該數(shù)據(jù)集上的最優(yōu)結(jié)果。 從圖2～圖4 可以看出，由本文算法所得到的F － measure、G － mean及AUC值總體上優(yōu)于其他4 種對比算法。 從表3～表5 可以得出本文的分類模型在F － measure、G － mean及AUC值上均得到了提升，尤其是對比RUS－Boost 算法。 在數(shù)據(jù)集ecoli2、yeast1、glass6、ecoli3 上，其分類評估指標均優(yōu)于其他對比算法，F(xiàn)－measure的提升值高達22.97%，G － mean的提升值為13.88%，AUC的最高提升值為10.03%。 從表3 的F － measure值可看出，HSMOTEAdaBoost 算法除了在數(shù)據(jù)集ecoli1 略低于SMOTEBoost 之外，在其他5 個數(shù)據(jù)集上均有最佳表現(xiàn)。 從表4～表5 得出，在數(shù)據(jù)集glass1 上，G － mean值稍遜于KSMOTE－AdaBoost 算法，AUC指標略小于SMOTE－Boost 算法，但其F － measure的提升值為3.99%。原因在于其不平衡比率較小，邊界樣本的重要性未得到充分體現(xiàn)。 雖然在部分數(shù)據(jù)集中的AUC值與其他4 種算法相差不大，但是隨著不平衡率的提升，性能提升百分比在不斷增大，在不平衡比率最大的數(shù)據(jù)集ecoli3 上，相對于其他4 種算法，性能提升了10.03%。 此外，在部分數(shù)據(jù)集、如yeast1，ecoli2 中，使用HSMOTE－AdaBoost 算法優(yōu)于RUS－Boost 算法，這是因為在使用隨機欠采樣后有可能會刪除一些潛在、有價值的多數(shù)類樣本，而本文所提出的算法有效解決了這個問題，盡可能地保留了必要的實例從而提升了分類性能。

表3 不同算法的F－measureTab. 3 F－measure of different algorithms

表4 不同算法的G－meanTab. 4 G－mean of different algorithms

表5 不同算法的AUCTab. 5 AUC of different algorithms

圖2 不同算法的F－measure 對比圖Fig. 2 F－measure comparison of different algorithms

圖3 不同算法的G－mean 對比圖Fig. 3 G－mean comparison of different algorithms

圖4 不同算法的AUC 對比圖Fig. 4 AUC comparison of different algorithms

4 結(jié)束語

針對二分類問題中不平衡數(shù)據(jù)集造成分類器分類性能低下的問題，本文考慮了多數(shù)類樣本的類內(nèi)差異，并保留了必要的邊界多數(shù)類樣本，將SMOTE過采樣與隨機欠采樣組合運用及改進，并與AdaBoost 相結(jié)合提出了一種解決類不平衡問題的HSMOTE－AdaBoost 算法。 與傳統(tǒng)的SMOTE－Boost、RUS－Boost、PC－Boost 及改進后的算法KSMOTEAdaBoost 相比，實驗表明該算法訓(xùn)練的分類器能有效地處理類不平衡問題，分類性能更優(yōu)。

此外，本文的改進算法也存在進一步研究的價值，接下來可以結(jié)合其他經(jīng)典的集成算法研究其分類性能。 其次，從實驗結(jié)果可以發(fā)現(xiàn)，在類不平衡比率越大的數(shù)據(jù)集上的分類效果越好，亟需從理論上對該結(jié)果做進一步的探討和驗證。 最后，本文所提出的算法對二分類問題的分類性能提升比較明顯，然而在現(xiàn)實生活中的大多數(shù)數(shù)據(jù)都是多類別的，未來將著重研究如何提高多類別分類問題的分類性能。