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

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

（上海理工大學管理學院， 上海 200093）

0 引 言

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

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

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

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

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

1 理論基礎

1.1 SMOTE 算法

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

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

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

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

（3）合成新的少數類樣本：

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

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

1.2 AdaBoost 算法

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

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

輸出最終分類器G（X）

2： form＝1 toM：

2.1： 使用具有權值分布Dm的訓練數據集進行學習，得到基本分類器Gm（X）

2.2： 算出Gm（X） 在訓練數據集上的分類誤差率：

這里，I為指示函數：

2.3：計算Gm（X） 的系數：

2.4：更新訓練數據集的權值分布：

其中，Zm為規范化因子，計算公式為：

3： 構建基本分類器的線性組合：

4： 得到最終的分類器：

2 HSMOTE－AdaBoost 算法

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

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

2.1 算法HSMOTE－AdaBoost 的訓練過程

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

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

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

③合成新的少數類樣本：

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

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

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

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

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

②求平均距離：

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

（4）對數據集E應用隨機欠采樣，將隨機選取的樣本推送到輸出數據集Tbal，并推得：

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

2.2 算法HSMOTE－AdaBoost 的詳細步驟

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

輸出集成分類器

1： 將數據集D分成10 份，其中2 份為測試集TestData，剩下即訓練集TrainData

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

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

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

5： 對剩余的數據進行隨機欠抽樣得到NewTrainData

6： 賦予NewTrainData中每個實例相同的權重。

7： form＝1 toM

8： 根據實例的權值有放回地抽樣得到Dm

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

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

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

11： ifem ＞0.5 then 轉步驟7

12： end if

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

15： 歸一化所有實例的權值

16： end for

17： 將每個類的權值賦予0，對TestData的所有實例執行以下步驟

18： fori＝1 toM：

19： 根據式（13）計算Gi（X） 對測試集中實例Xi的權值Wi：

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

21： end for

22： 返回權值最大的類，即為Xi的類別

23： end for

3 仿真實驗

3.1 實驗數據集

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

表1 實驗數據集Tab. 1 Experimental dataset

3.2 性能評價指標

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

表2 混淆矩陣Tab. 2 Confusion matrix

根據表2 可得到以下評價指標。

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

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

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

其中，α是取值為1 的比例系數。

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

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

3.3 實驗設置

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

3.4 實驗結果分析

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

表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 結束語

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

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