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

(1.南京郵電大學(xué) 自動(dòng)化學(xué)院、人工智能學(xué)院，江蘇 南京 210003； 2.南京郵電大學(xué) 現(xiàn)代郵政學(xué)院，江蘇 南京 210003)

0 引 言

傳統(tǒng)機(jī)器學(xué)習(xí)中研究的分類(lèi)算法假定數(shù)據(jù)集是平衡的，即數(shù)據(jù)集中各類(lèi)別樣本數(shù)大致相等[1]。但在如軟件缺陷預(yù)測(cè)、醫(yī)療診斷、目標(biāo)檢測(cè)等相當(dāng)多的應(yīng)用場(chǎng)景下，數(shù)據(jù)的類(lèi)別分布是不平衡的[2]。以提高總體分類(lèi)準(zhǔn)確率為目標(biāo)的傳統(tǒng)機(jī)器學(xué)習(xí)分類(lèi)算法在平衡數(shù)據(jù)集上取得了較好的分類(lèi)效果，但在不平衡數(shù)據(jù)集上，這些算法的決策傾向于多數(shù)類(lèi)[3]，使得少數(shù)類(lèi)樣本的分類(lèi)準(zhǔn)確率遠(yuǎn)低于多數(shù)類(lèi)樣本的分類(lèi)準(zhǔn)確率。而在軟件缺陷預(yù)測(cè)或醫(yī)療診斷等類(lèi)不平衡場(chǎng)景下，準(zhǔn)確預(yù)測(cè)出屬于少數(shù)類(lèi)的有缺陷或患病樣本恰恰是分類(lèi)算法的目標(biāo)。

為解決上述問(wèn)題，提出基于Bagging集成學(xué)習(xí)的多集類(lèi)不平衡學(xué)習(xí)算法。該算法主要由基于Bagging的多集構(gòu)建和特征提取與多集融合兩個(gè)模塊構(gòu)成?；贐agging的多集構(gòu)建通過(guò)重采樣構(gòu)建多個(gè)多數(shù)類(lèi)與少數(shù)類(lèi)樣本數(shù)大致相等的平衡訓(xùn)練集并有效去除多數(shù)類(lèi)樣本中的噪聲樣本；特征提取與多集融合部分提高樣本分離度并融合多個(gè)訓(xùn)練集所訓(xùn)練的分類(lèi)器的預(yù)測(cè)結(jié)果，提升算法分類(lèi)性能。

1 相關(guān)工作

近年來(lái)，針對(duì)類(lèi)不平衡分類(lèi)問(wèn)題，國(guó)內(nèi)外學(xué)者提出了很多創(chuàng)新性的方法，大致可歸于重采樣法(resampling technique)[4-6]、代價(jià)敏感學(xué)習(xí)(cost-sensitive learning)[7]和集成學(xué)習(xí)(ensemble learning)[8-9]。

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

基于代價(jià)敏感學(xué)習(xí)[7]的方法關(guān)注與錯(cuò)分樣本有關(guān)的代價(jià)。這些方法通常構(gòu)建一個(gè)代價(jià)矩陣，這個(gè)矩陣可以被認(rèn)為是對(duì)于將某類(lèi)樣本錯(cuò)分為另一類(lèi)的懲罰的數(shù)值表示。傳統(tǒng)分類(lèi)算法中不同類(lèi)別的樣本錯(cuò)分的代價(jià)(損失)是相同的，但代價(jià)矩陣對(duì)少數(shù)類(lèi)樣本錯(cuò)分為多數(shù)類(lèi)賦予更大的代價(jià)，使得少數(shù)類(lèi)樣本的權(quán)重提高，從而緩解算法決策傾向于多數(shù)類(lèi)的問(wèn)題。

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

圖1 Bagging結(jié)構(gòu)

很多文獻(xiàn)提出了基于Bagging思想的改進(jìn)算法。如文獻(xiàn)[10]提出了一種隨機(jī)平衡采樣Bagging 算法，該方法通過(guò)隨機(jī)平衡采樣算法，在不改變數(shù)據(jù)集大小的前提下平衡了數(shù)據(jù)集，但該方法隨機(jī)舍棄大量多數(shù)類(lèi)樣本，導(dǎo)致多數(shù)類(lèi)分布信息損失。文獻(xiàn)[11]則提出了一種基于概率閾值Bagging算法的不平衡數(shù)據(jù)分類(lèi)方法，該方法首先利用Bagging集成算法得到一個(gè)良好的后驗(yàn)概率估計(jì)，然后根據(jù)最大化性能測(cè)量值來(lái)選取恰當(dāng)?shù)拈撝?。但在?shí)際操作過(guò)程中選擇適當(dāng)?shù)母怕书撝捣浅＠щy，且該方法只以提升平均準(zhǔn)確率或F1-score這一單一評(píng)價(jià)指標(biāo)為優(yōu)化目標(biāo)，在相當(dāng)多的場(chǎng)景下，僅這一個(gè)指標(biāo)并不能有效地評(píng)價(jià)算法的類(lèi)不平衡分類(lèi)性能。文獻(xiàn)[12]利用SMOTE算法生成少數(shù)類(lèi)樣本并在Bagging集成中提高少數(shù)類(lèi)樣本的權(quán)重來(lái)處理不平衡數(shù)據(jù)集的分類(lèi)問(wèn)題，但該方法易出現(xiàn)過(guò)擬合的問(wèn)題。

2 基于Bagging的多集類(lèi)不平衡學(xué)習(xí)算法

基于Bagging集成學(xué)習(xí)的多集類(lèi)不平衡學(xué)習(xí)算法由兩部分構(gòu)成：基于Bagging的多集構(gòu)建部分、特征提取與多集融合部分，其結(jié)構(gòu)如圖2所示?；贐agging的多集構(gòu)建部分通過(guò)基于K-means[13]的欠采樣算法和SMOTE過(guò)采樣算法[5]構(gòu)建多個(gè)平衡訓(xùn)練集；特征提取與多集融合部分利用線(xiàn)性判別分析(LDA)[14]對(duì)數(shù)據(jù)投影后用近鄰分類(lèi)器分類(lèi)，并通過(guò)投票融合多個(gè)訓(xùn)練集的分類(lèi)預(yù)測(cè)結(jié)果。

圖2 算法結(jié)構(gòu)

2.1 基于Bagging的多集構(gòu)建

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

對(duì)于少數(shù)類(lèi)樣本，文中以μ的采樣率從原始數(shù)據(jù)集中的少數(shù)類(lèi)樣本中隨機(jī)采樣，并依據(jù)這些樣本使用SMOTE算法[5]進(jìn)行過(guò)采樣，直至少數(shù)類(lèi)樣本數(shù)量與多數(shù)類(lèi)樣本數(shù)量大致相等。新樣本生成公式如下：

(1)

2.2 特征提取與多集融合

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

圖3 基于Bagging的多集構(gòu)建流程

(2)

其中，Sb為類(lèi)間散度矩陣，Sw為類(lèi)內(nèi)散度矩陣，計(jì)算公式如下：

(3)

(4)

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

(5)

其中，μP和μN(yùn)分別是少數(shù)類(lèi)與多數(shù)類(lèi)樣本的均值。

樣本經(jīng)過(guò)投影矩陣W投影后，可利用近鄰分類(lèi)器給出待分類(lèi)樣本的分類(lèi)預(yù)測(cè)。對(duì)于每一個(gè)平衡訓(xùn)練集，都可由上述步驟得到待分類(lèi)樣本的一個(gè)分類(lèi)預(yù)測(cè)。最后通過(guò)多數(shù)投票融合多個(gè)訓(xùn)練集的分類(lèi)預(yù)測(cè)，得到待分類(lèi)樣本的最終分類(lèi)結(jié)果。

基于Bagging集成學(xué)習(xí)的多集類(lèi)不平衡學(xué)習(xí)算法如下所示。

算法1：基于Bagging集成學(xué)習(xí)的多集類(lèi)不平衡學(xué)習(xí)算法。

輸出：待分類(lèi)樣本的分類(lèi)預(yù)測(cè)P(x)。

2：forj=1→mdo

7:利用多數(shù)投票得到待分類(lèi)樣本x最終的分類(lèi)預(yù)測(cè)P(x)

3 實(shí) 驗(yàn)

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

為了驗(yàn)證該方法的有效性，在PC1，Abalone19，Glass5，Page-blocks0和Shuttle0vs4數(shù)據(jù)集[16]上進(jìn)行了對(duì)比實(shí)驗(yàn)。

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

表1 數(shù)據(jù)集相關(guān)屬性

圖4 數(shù)據(jù)集可視化

3.2 評(píng)價(jià)指標(biāo)

采用類(lèi)不平衡學(xué)習(xí)常用指標(biāo)G-mean和AUC評(píng)估模型的預(yù)測(cè)效果。對(duì)于二分類(lèi)問(wèn)題，有如表2的混淆矩陣。

表2 二分類(lèi)混淆矩陣

G-mean的定義如下：

(6)

對(duì)分類(lèi)模型給出的樣本的分類(lèi)預(yù)測(cè)概率，遍歷[0,1]上的所有截?cái)帱c(diǎn)(閾值)，以式(7)計(jì)算的假陽(yáng)性率(FPR)為橫坐標(biāo)，式(8)計(jì)算的真陽(yáng)性率(TPR)為縱坐標(biāo)，可繪制出受試者操作特征曲線(xiàn)(ROC)。ROC曲線(xiàn)下的面積即為AUC，如圖5所示。

(7)

(8)

圖5 AUC示意圖

通常認(rèn)為，G-mean和AUC越高，則算法能在不影響多數(shù)類(lèi)分類(lèi)準(zhǔn)確率的前提下提高少數(shù)類(lèi)樣本的分類(lèi)準(zhǔn)確率，即算法對(duì)于不平衡數(shù)據(jù)集的分類(lèi)效果越好。

3.3 算法參數(shù)設(shè)置

在實(shí)驗(yàn)時(shí)，文中方法中的參數(shù)─多數(shù)類(lèi)采樣率λ、少數(shù)類(lèi)采樣率μ和多集數(shù)m分別取0.80、0.95和20，對(duì)于PC1和Page-blocks0數(shù)據(jù)集，聚類(lèi)數(shù)k取9，對(duì)于Abalone19和Shuttle0vs4數(shù)據(jù)集，聚類(lèi)數(shù)k取4，對(duì)于Glass5數(shù)據(jù)集，聚類(lèi)數(shù)k則取2。

3.4 實(shí)驗(yàn)設(shè)置及實(shí)驗(yàn)結(jié)果

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

表3 G-mean實(shí)驗(yàn)值

表4 AUC實(shí)驗(yàn)值

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

4 結(jié)束語(yǔ)

提出了基于Bagging集成學(xué)習(xí)的多集類(lèi)不平衡學(xué)習(xí)算法，算法由基于Bagging的多集構(gòu)建和特征提取與多集融合兩個(gè)模塊構(gòu)成。該算法有效地緩解了不平衡數(shù)據(jù)集樣本數(shù)量分布不均衡、存在噪聲樣本、類(lèi)間分布重疊等問(wèn)題。在PC1、Glass5、Shuttle0vs4等多個(gè)不同領(lǐng)域的不平衡數(shù)據(jù)集上的實(shí)驗(yàn)表明，該算法對(duì)于類(lèi)不平衡數(shù)據(jù)具有良好的分類(lèi)性能。但該算法只適用于二分類(lèi)場(chǎng)景下的不平衡數(shù)據(jù)分類(lèi)，接下來(lái)將進(jìn)一步研究多分類(lèi)情況下的不平衡數(shù)據(jù)分類(lèi)。