基于Bagging集成學習的多集類不平衡學習

肖 梁，韓 璐，魏鵬飛，鄭鑫浩，張 上，吳 飛

(1.南京郵電大學 自動化學院、人工智能學院，江蘇 南京 210003； 2.南京郵電大學 現代郵政學院，江蘇 南京 210003)

0 引 言

傳統機器學習中研究的分類算法假定數據集是平衡的，即數據集中各類別樣本數大致相等[1]。但在如軟件缺陷預測、醫療診斷、目標檢測等相當多的應用場景下，數據的類別分布是不平衡的[2]。以提高總體分類準確率為目標的傳統機器學習分類算法在平衡數據集上取得了較好的分類效果，但在不平衡數據集上，這些算法的決策傾向于多數類[3]，使得少數類樣本的分類準確率遠低于多數類樣本的分類準確率。而在軟件缺陷預測或醫療診斷等類不平衡場景下，準確預測出屬于少數類的有缺陷或患病樣本恰恰是分類算法的目標。

為解決上述問題，提出基于Bagging集成學習的多集類不平衡學習算法。該算法主要由基于Bagging的多集構建和特征提取與多集融合兩個模塊構成。基于Bagging的多集構建通過重采樣構建多個多數類與少數類樣本數大致相等的平衡訓練集并有效去除多數類樣本中的噪聲樣本；特征提取與多集融合部分提高樣本分離度并融合多個訓練集所訓練的分類器的預測結果，提升算法分類性能。

1 相關工作

近年來，針對類不平衡分類問題，國內外學者提出了很多創新性的方法，大致可歸于重采樣法(resampling technique)[4-6]、代價敏感學習(cost-sensitive learning)[7]和集成學習(ensemble learning)[8-9]。

基于重采樣的方法可以分為欠采樣(undersampling)[4]方法和過采樣(oversampling)[5-6]方法。欠采樣方法通過減少多數類樣本來平衡少數類和多數類的分布,如Kubat等[4]提出單邊選擇算法去除多數類中的邊界和冗余樣本。過采樣方法向不平衡的數據集中添加采樣或生成的少數類樣本來平衡數據集。例如，Chawla等人[5]提出一種合成少數類樣本過采樣技術(SMOTE)，該方法隨機選擇一個少數類樣本及它的近鄰，并在兩者連線上隨機選取一點作為新生成的少數類樣本。帶多數類權重的少數類樣本過采樣技術(MWMOTE)[6]則根據少數類樣本近鄰中屬于多數類或少數類樣本的數量比例及距離計算信息權重，并依權重抽取樣本進行SMOTE式插值樣本生成。

基于代價敏感學習[7]的方法關注與錯分樣本有關的代價。這些方法通常構建一個代價矩陣，這個矩陣可以被認為是對于將某類樣本錯分為另一類的懲罰的數值表示。傳統分類算法中不同類別的樣本錯分的代價(損失)是相同的，但代價矩陣對少數類樣本錯分為多數類賦予更大的代價，使得少數類樣本的權重提高，從而緩解算法決策傾向于多數類的問題。

集成學習可以分為Boosting[8]和Bagging[9]兩類。Boosting算法一般在迭代的過程中通過提高在前一輪被分類器錯分的樣本(一般為少數類樣本)的權值，減小前一輪正確分類的樣本的權值，使得分類器更加關注被錯誤分類的少數類樣本。但選擇適當的權重非常困難。Bagging算法從原始數據集中多次有放回地抽取樣本構成多個訓練集，并用這些訓練集分別訓練得到多個分類模型，最后將每個模型得到的預測結果投票得到最終的分類結果，其結構如圖1所示。該算法有效提升了弱分類器的分類性能。

圖1 Bagging結構

很多文獻提出了基于Bagging思想的改進算法。如文獻[10]提出了一種隨機平衡采樣Bagging 算法，該方法通過隨機平衡采樣算法，在不改變數據集大小的前提下平衡了數據集，但該方法隨機舍棄大量多數類樣本，導致多數類分布信息損失。文獻[11]則提出了一種基于概率閾值Bagging算法的不平衡數據分類方法，該方法首先利用Bagging集成算法得到一個良好的后驗概率估計，然后根據最大化性能測量值來選取恰當的閾值。但在實際操作過程中選擇適當的概率閾值非常困難，且該方法只以提升平均準確率或F1-score這一單一評價指標為優化目標，在相當多的場景下，僅這一個指標并不能有效地評價算法的類不平衡分類性能。文獻[12]利用SMOTE算法生成少數類樣本并在Bagging集成中提高少數類樣本的權重來處理不平衡數據集的分類問題，但該方法易出現過擬合的問題。

2 基于Bagging的多集類不平衡學習算法

基于Bagging集成學習的多集類不平衡學習算法由兩部分構成：基于Bagging的多集構建部分、特征提取與多集融合部分，其結構如圖2所示。基于Bagging的多集構建部分通過基于K-means[13]的欠采樣算法和SMOTE過采樣算法[5]構建多個平衡訓練集；特征提取與多集融合部分利用線性判別分析(LDA)[14]對數據投影后用近鄰分類器分類，并通過投票融合多個訓練集的分類預測結果。

圖2 算法結構

2.1 基于Bagging的多集構建

為減少多數類樣本數量并去除其中的噪聲樣本，文中提出一種基于K-means[13]的欠采樣算法。首先對多數類樣本進行K-means聚類[13]，聚類數k取一個大于1的值。選取聚類后樣本數大于0.25nN的聚類中的樣本，將其余樣本視為噪聲樣本舍棄。與文獻[15]中選取聚類中心點作為欠采樣后的樣本的方法相比，文中方法保留了多數類樣本的分布信息并去除了其中的噪聲樣本，有利于后續的分類操作。同時，為減小訓練集樣本之間的相似度，每個訓練集中的多數類樣本從去噪后的多數類樣本中以λ的采樣率隨機采樣得到。

對于少數類樣本，文中以μ的采樣率從原始數據集中的少數類樣本中隨機采樣，并依據這些樣本使用SMOTE算法[5]進行過采樣，直至少數類樣本數量與多數類樣本數量大致相等。新樣本生成公式如下：

(1)

2.2 特征提取與多集融合

經過上述步驟可以得到多個平衡訓練集，但此時訓練集中多數類與少數類樣本的分離度不高，直接進行分類效果不佳。線性判別分析(LDA)[14]能將高維的樣本投影到一個最佳的判別矢量空間，在此空間中同一類的樣本間距近，不同類的樣本間距遠，使得樣本在該空間中有最佳的可分離性。故文中使用線性判別分析(LDA)對樣本進行特征提取，將樣本投影到一個分離度高的特征空間中。線性判別分析的損失函數如下：

圖3 基于Bagging的多集構建流程

(2)

其中，Sb為類間散度矩陣，Sw為類內散度矩陣，計算公式如下：

(3)

(4)

其中，C為數據集中樣本類別數，ni為第i類樣本的個數，xij為第i類樣本中的第j個樣本，μi為第i類樣本的均值。而對于文中所解決的二分類問題，投影矩陣可以由下式快速求得：

(5)

其中，μP和μN分別是少數類與多數類樣本的均值。

樣本經過投影矩陣W投影后，可利用近鄰分類器給出待分類樣本的分類預測。對于每一個平衡訓練集，都可由上述步驟得到待分類樣本的一個分類預測。最后通過多數投票融合多個訓練集的分類預測，得到待分類樣本的最終分類結果。

基于Bagging集成學習的多集類不平衡學習算法如下所示。

算法1：基于Bagging集成學習的多集類不平衡學習算法。

輸出：待分類樣本的分類預測P(x)。

2：forj=1→mdo

7:利用多數投票得到待分類樣本x最終的分類預測P(x)

3 實 驗

3.1 數據集

為了驗證該方法的有效性，在PC1，Abalone19，Glass5，Page-blocks0和Shuttle0vs4數據集[16]上進行了對比實驗。

PC1數據集為軟件缺陷預測數據集，不平衡比為13.4∶1。Abalone19是一個生物信息預測數據集，不平衡比為129.4∶1。Glass5和Shuttle0vs4都是物品分類數據集，不平衡比分別為22.8∶1和13.9∶1。Page-blocks0數據集的每個樣本為一個文件分類的特征表示，不平衡比為8.6∶1。各個數據集的相關屬性如表1和圖4所示。

表1 數據集相關屬性

圖4 數據集可視化

3.2 評價指標

采用類不平衡學習常用指標G-mean和AUC評估模型的預測效果。對于二分類問題，有如表2的混淆矩陣。

表2 二分類混淆矩陣

G-mean的定義如下：

(6)

對分類模型給出的樣本的分類預測概率，遍歷[0,1]上的所有截斷點(閾值)，以式(7)計算的假陽性率(FPR)為橫坐標，式(8)計算的真陽性率(TPR)為縱坐標，可繪制出受試者操作特征曲線(ROC)。ROC曲線下的面積即為AUC，如圖5所示。

(7)

(8)

圖5 AUC示意圖

通常認為，G-mean和AUC越高，則算法能在不影響多數類分類準確率的前提下提高少數類樣本的分類準確率，即算法對于不平衡數據集的分類效果越好。

3.3 算法參數設置

在實驗時，文中方法中的參數─多數類采樣率λ、少數類采樣率μ和多集數m分別取0.80、0.95和20，對于PC1和Page-blocks0數據集，聚類數k取9，對于Abalone19和Shuttle0vs4數據集，聚類數k取4，對于Glass5數據集，聚類數k則取2。

3.4 實驗設置及實驗結果

選擇基礎分類算法k最近鄰分類器(kNN)和線性判別分析加kNN(LDA-kNN)，以及文獻[6,17-19]中提出的類不平衡分類算法MWMOTE、EUSBoost、DBSMOTE和UCML作為對比方法。從數據集中多數類和少數類樣本中各隨機選取70%的樣本作為訓練樣本，其余樣本作為測試樣本，對各方法進行100次實驗，取實驗結果的平均值。各個算法在五個數據集上的G-mean和AUC如表3和表4所示。

表3 G-mean實驗值

表4 AUC實驗值

實驗結果顯示，與六個對比方法相比，文中方法在其中三個數據集上得到了最高的G-mean和AUC值，在另兩個數據集上的G-mean和AUC值也處于較高的水平。文中方法不僅平衡了數據集中多數類與少數類樣本的數量分布，同時去除了多數類中的噪聲樣本，還利用線性判別分析提高了多數類與少數類樣本的分離度，并利用Bagging集成學習思想提升弱分類器的分類性能，從而提升了算法總體的類不平衡分類性能。

4 結束語

提出了基于Bagging集成學習的多集類不平衡學習算法，算法由基于Bagging的多集構建和特征提取與多集融合兩個模塊構成。該算法有效地緩解了不平衡數據集樣本數量分布不均衡、存在噪聲樣本、類間分布重疊等問題。在PC1、Glass5、Shuttle0vs4等多個不同領域的不平衡數據集上的實驗表明，該算法對于類不平衡數據具有良好的分類性能。但該算法只適用于二分類場景下的不平衡數據分類，接下來將進一步研究多分類情況下的不平衡數據分類。