史明華,吳廣潮

(華南理工大學(xué)數(shù)學(xué)學(xué)院,廣東 廣州 510641)

0 引 言

在分類(lèi)問(wèn)題中，不平衡分類(lèi)問(wèn)題是許多研究者探索過(guò)的一個(gè)非常重要的分支[1-2]。它在實(shí)際應(yīng)用中隨處可見(jiàn)，如人臉識(shí)別[3]、醫(yī)療診斷[4]、故障診斷[5]等。此外，隨著信息技術(shù)的不斷進(jìn)步，不平衡問(wèn)題變得越來(lái)越重要。在許多實(shí)際二分類(lèi)問(wèn)題中，一個(gè)類(lèi)(多數(shù)類(lèi))的樣本明顯多于另一個(gè)類(lèi)(少數(shù)類(lèi))，具有這種特征的數(shù)據(jù)集被稱(chēng)作不平衡數(shù)據(jù)集[6]。對(duì)于不平衡數(shù)據(jù)集，傳統(tǒng)分類(lèi)器的分類(lèi)結(jié)果更多地偏向于多數(shù)類(lèi)。

目前，針對(duì)不平衡數(shù)據(jù)集分類(lèi)性能提高的解決辦法主要圍繞在數(shù)據(jù)層面和算法層面展開(kāi)。數(shù)據(jù)層面通過(guò)欠采樣、過(guò)采樣以及混合采樣等數(shù)據(jù)重采樣方法，算法層面通過(guò)改進(jìn)已有的分類(lèi)算法，如代價(jià)敏感學(xué)習(xí)[7-8]、單類(lèi)學(xué)習(xí)[9]和集成學(xué)習(xí)[10-11]等來(lái)提高分類(lèi)性能。本文從數(shù)據(jù)層面上來(lái)平衡數(shù)據(jù)分布。

欠采樣通過(guò)減少多數(shù)類(lèi)樣本使之與少數(shù)類(lèi)平衡，最簡(jiǎn)單常用的欠采樣方法是隨機(jī)欠采樣，該方法縮短了訓(xùn)練時(shí)間，但是易丟失多數(shù)類(lèi)樣本中的關(guān)鍵信息。而過(guò)采樣與欠采樣相反，最簡(jiǎn)單常用的過(guò)采樣方法是隨機(jī)過(guò)采樣，該方法使得少數(shù)類(lèi)樣本中有大量重復(fù)數(shù)據(jù)，在訓(xùn)練中容易過(guò)擬合。為了避免隨機(jī)過(guò)采樣中出現(xiàn)過(guò)擬合問(wèn)題，文獻(xiàn)[12]提出了SMOTE算法，該算法對(duì)少數(shù)類(lèi)及其近鄰之間進(jìn)行隨機(jī)線(xiàn)性插值得到新的少數(shù)類(lèi)樣本，可以在一定程度上避免過(guò)擬合問(wèn)題，但是增加了類(lèi)之間重疊的可能性。文獻(xiàn)[13]提出了一種自適應(yīng)數(shù)據(jù)合成方法ADASYN，該方法可以根據(jù)少數(shù)類(lèi)樣本的分布自適應(yīng)地合成少數(shù)類(lèi)樣本，相比較容易分類(lèi)的區(qū)域，在較難分類(lèi)的區(qū)域合成更多的樣本，可以減少原始不平衡數(shù)據(jù)分布引入的學(xué)習(xí)偏差，還可以自適應(yīng)地改變決策邊界，專(zhuān)注于那些難以學(xué)習(xí)的樣本。混合采樣則是欠采樣與過(guò)采樣的結(jié)合。文獻(xiàn)[14-15]中的實(shí)驗(yàn)顯示，混合采樣后分類(lèi)器的性能幾乎都是優(yōu)于單個(gè)采樣方法的。

本文提出一種新的平衡數(shù)據(jù)方法,該方法先對(duì)樣本聚類(lèi)，然后根據(jù)每一簇中多數(shù)類(lèi)樣本與少數(shù)類(lèi)樣本的比值(不平衡比(Imbalance Ration, IR))大小對(duì)簇中樣本進(jìn)行處理，構(gòu)建新的樣本集，再采用GBDT分類(lèi)器對(duì)樣本進(jìn)行分類(lèi)。

1 相關(guān)知識(shí)

1.1 SMOTE算法

SMOTE算法是由Chawla等人[12]提出的一種過(guò)采樣算法，該算法的主要思想為：先對(duì)少數(shù)類(lèi)樣本計(jì)算其少數(shù)類(lèi)k近鄰，接著在少數(shù)類(lèi)樣本之間進(jìn)行線(xiàn)性插值生成新的少數(shù)類(lèi)樣本。對(duì)于少數(shù)類(lèi)中每一個(gè)樣本xi，以歐氏距離為標(biāo)準(zhǔn)計(jì)算它到少數(shù)類(lèi)樣本集中所有樣本的距離，得到其最近鄰，隨機(jī)選取近鄰xj，然后由以下公式構(gòu)建新的樣本：

xnew=xi+δ(xj-xi)

其中，δ為0～1之間的隨機(jī)數(shù)。

1.2 K-means算法

K-means算法[16]是經(jīng)典的基于劃分的聚類(lèi)方法。該算法按照相似度將樣本分成不同的簇，簇間相似度低，簇內(nèi)相似度高。具體算法流程描述如下：

輸入：數(shù)據(jù)集X={x1,x2,…,xn}，生成簇個(gè)數(shù)k

輸出：簇集{c1,c2,…,ck}

1)從X中隨機(jī)選取k個(gè)值作為初始簇心{μ1,μ2,…,μk}

2)foriinndo

forjinkdo

dji=‖xi-μj‖2//計(jì)算樣本與簇心之間的歐氏距離,將樣本與距離最近的簇心歸為一簇

3)forjinkdo

返回步驟2，直到當(dāng)前簇心不再更新

1.3 GBDT算法

梯度提升決策樹(shù)(Gradient Boost Decision Tree, GBDT)是2001年由Friedman等人[17-18]提出的一種有效的機(jī)器學(xué)習(xí)算法，可以用于解決分類(lèi)和回歸問(wèn)題。該算法將損失函數(shù)的負(fù)梯度作為當(dāng)前模型數(shù)據(jù)殘差的近似值,根據(jù)近似殘差值擬合一個(gè)CART回歸樹(shù),不斷重復(fù)此過(guò)程,進(jìn)而減少上個(gè)模型的殘差，并在殘差減少的梯度方向上訓(xùn)練建立新的模型。GBDT的具體算法的流程描述如下：

輸入：數(shù)據(jù)集{(x1,y1),(x2,y2),…,(xn,yn)}，迭代次數(shù)M(生成樹(shù)的樹(shù)目)

輸出：強(qiáng)學(xué)習(xí)器F(x)

1)初始化弱學(xué)習(xí)器：

2)forminMdo

foriinndo

forjinJdo

//括號(hào)中內(nèi)容為真則I=1,否則I=0

3)返回：

2 基于聚類(lèi)的混合采樣算法

對(duì)于均衡不平衡數(shù)據(jù)，大多數(shù)的采樣方法針對(duì)類(lèi)間不平衡問(wèn)題，即類(lèi)與類(lèi)之間數(shù)量的不平衡，沒(méi)有考慮類(lèi)內(nèi)樣本的分布不均衡問(wèn)題。這2種不平衡問(wèn)題均會(huì)對(duì)分類(lèi)效果造成影響，因此本文提出基于聚類(lèi)的混合采樣(Hybrid Sampling Based on Clustering, HSBC)算法。該算法通過(guò)控制參數(shù)去噪聲，并由混合采樣均衡對(duì)應(yīng)簇的2類(lèi)樣本數(shù)量。

2.1 基于聚類(lèi)的混合采樣算法

本文提出新的算法平衡數(shù)據(jù)集，首先對(duì)數(shù)據(jù)集做聚類(lèi)，對(duì)每一簇樣本求不平衡比(IR)，當(dāng)IR過(guò)大或過(guò)小時(shí)，將該簇中數(shù)目較少的樣本視作噪聲刪去，其余的簇根據(jù)IR分別作混合采樣，以均衡類(lèi)內(nèi)分布。HSBC算法合成樣本過(guò)程如下：

1)由K-means算法將原始數(shù)據(jù)集分成多個(gè)簇。

2)對(duì)每一簇樣本計(jì)算不平衡比。

3)根據(jù)IR對(duì)相應(yīng)簇進(jìn)行剔除部分樣本或混合采樣處理。

4)輸出新數(shù)據(jù)集。

詳細(xì)算法步驟如下：

輸入：數(shù)據(jù)集S

輸出：新數(shù)據(jù)集Snew

1)Snew=[] //放置新樣本

2)Kmeans(S)→clusters

//Kmeans算法生成多個(gè)簇clusters

3)forc∈clusters do

if IR(c)>=m1：

Snew.append(maj_sample)

elif 1

kmeans=Kmeans(count(c)/2)

center_maj=kmeans.fit(maj_sample)

cluster_new=SMOTE.fit_sample(center_maj∪min _sample)

Snew.append(cluster_new)

elifm2

kmeans=Kmeans(count(c)/2)

center_min =kmeans.fit(min _sam mple)

Snew.append(center_min ∪maj_sample)

else:

Snew.append(min _sample)

4)ReturnSnew

其中，maj_count(c)指c簇中多數(shù)類(lèi)樣本個(gè)數(shù)，min_count(c)指c簇中少數(shù)類(lèi)樣本個(gè)數(shù)，maj_sample指c簇中多數(shù)類(lèi)樣本，count(c)指c簇總樣本個(gè)數(shù)，min_sample指c簇中少數(shù)類(lèi)樣本。

當(dāng)m1越大時(shí)，簇內(nèi)少數(shù)類(lèi)樣本相對(duì)越少，IR大于m1時(shí)，將少數(shù)類(lèi)樣本視作噪聲去掉；同理，IR小于m2時(shí)，將多數(shù)類(lèi)樣本去掉；若簇內(nèi)IR小于m1而又大于1時(shí)，多數(shù)類(lèi)樣本多，少數(shù)類(lèi)樣本少，先對(duì)多數(shù)類(lèi)樣本聚成子簇，用子簇心代替多數(shù)類(lèi)樣本以減少樣本個(gè)數(shù)，再對(duì)少數(shù)類(lèi)樣本運(yùn)用SMOTE生成新的少數(shù)類(lèi)樣本；若簇內(nèi)IR大于m2而又小于1時(shí)，少數(shù)類(lèi)樣本個(gè)數(shù)多，多數(shù)類(lèi)樣本個(gè)數(shù)少，對(duì)少數(shù)類(lèi)樣本聚成子簇以減少樣本個(gè)數(shù)，再對(duì)多數(shù)類(lèi)樣本運(yùn)用SMOTE合成新的多數(shù)類(lèi)樣本。通過(guò)以上操作，較好地均衡了類(lèi)內(nèi)樣本分布。

2.2 HSBC-GBDT算法

數(shù)據(jù)集經(jīng)過(guò)預(yù)處理、HSBC算法處理后得到較為均衡的數(shù)據(jù)集，然后將該數(shù)據(jù)集放入GBDT分類(lèi)器。具體的算法流程如圖1所示。

圖1 HSBC-GBDT算法流程圖

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

為驗(yàn)證算法的有效性，實(shí)驗(yàn)選取了5個(gè)UCI數(shù)據(jù)集[19]，實(shí)驗(yàn)思路：先選取不平衡數(shù)據(jù)集，將字符型變量轉(zhuǎn)化為數(shù)值型變量，并做歸一化處理。然后用本文提出的數(shù)據(jù)處理算法與傳統(tǒng)算法處理數(shù)據(jù)，再用GBDT分類(lèi)器對(duì)數(shù)據(jù)分類(lèi)。對(duì)比實(shí)驗(yàn)結(jié)果表明，本文提出的算法具有更好的性能。

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

本文從UCI數(shù)據(jù)集中采用了ecoli、bank、blood、ionosphere、abalone這5個(gè)不平衡數(shù)據(jù)集。其中ecoli數(shù)據(jù)集將類(lèi)別標(biāo)簽為“im”的樣本記作少數(shù)類(lèi)樣本，abalone數(shù)據(jù)集將類(lèi)別標(biāo)簽為“F”的樣本記作少數(shù)類(lèi)樣本。數(shù)據(jù)集分布如表1所示。

表1 數(shù)據(jù)集描述

數(shù)據(jù)集數(shù)目類(lèi)別數(shù)目特征數(shù)目不平衡比ecoli336259,7773.36ionosphere351225,126341.79bank45214000,521167.68blood748570,17843.20abalone41772870,130782.20

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

對(duì)于不平衡問(wèn)題，本文采用F1-value、AUC作為評(píng)價(jià)指標(biāo)，其中多數(shù)類(lèi)為負(fù)類(lèi)，少數(shù)類(lèi)為正類(lèi)。分類(lèi)結(jié)果的混淆矩陣如表2所示。

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

分類(lèi)預(yù)測(cè)正類(lèi)預(yù)測(cè)負(fù)類(lèi)實(shí)際正類(lèi)TPFN實(shí)際負(fù)類(lèi)FPTN

查準(zhǔn)率：

precision=TP/(TP+FP)

查全率：

recall=TP/(TP+FN)

F1-value：

ROC曲線(xiàn)以FP/(TN+FP)為橫軸，TP/(TP+FN)為縱軸，曲線(xiàn)越靠近左上角分類(lèi)效果越好。學(xué)習(xí)器進(jìn)行比較時(shí)，若一個(gè)分類(lèi)器的曲線(xiàn)被另一個(gè)學(xué)習(xí)器的曲線(xiàn)完全“包住”，則后者性能高于前者。若2條曲線(xiàn)交叉，則難斷兩者孰優(yōu)孰劣，可引入ROC曲線(xiàn)下的面積，即AUC[20]。

3.3 實(shí)驗(yàn)結(jié)果

本文實(shí)驗(yàn)均在Jupyter Notebook上運(yùn)行，其中在HSBC算法中，m1取10，m2取0.2時(shí)算法總體來(lái)看效果最好，因此本次實(shí)驗(yàn)取該值。對(duì)于每個(gè)數(shù)據(jù)集，按7：3的比例劃分為訓(xùn)練集與測(cè)試集，5個(gè)數(shù)據(jù)集分別經(jīng)過(guò)不做均衡化處理、隨機(jī)欠采樣(RUS)、隨機(jī)過(guò)采樣(ROS)、SMOTE算法、ADASYN算法及HSBC算法后使用GBDT算法對(duì)新訓(xùn)練集進(jìn)行分類(lèi)。F1-value及AUC對(duì)比結(jié)果見(jiàn)表3和表4，其中最大值用粗體標(biāo)出。

表3 各算法在不同數(shù)據(jù)集上的F1-value對(duì)比

算法ecoliionospherebankbloodabaloneGBDT0.7500.9100.4380.4420.330RUS-GBDT0.7610.8970.5110.4730.558ROS-GBDT0.7580.8940.5520.4940.550SMOTE-GBDT0.7110.9050.5780.4960.542ADASYN-GBDT0.6980.9130.5850.4890.537HSBC-GBDT0.7690.9160.5710.5390.593

表4 各算法在不同數(shù)據(jù)集上的AUC值對(duì)比

算法ecoliionospherebankbloodabaloneGBDT0.8740.9230.6570.6320.570RUS-GBDT0.8760.9110.8160.6220.664ROS-GBDT0.8610.9080.8120.6440.659SMOTE-GBDT0.8780.9160.7740.6530.642ADASYN-GBDT0.8560.9110.7810.6460.651HSBC-GBDT0.8810.9240.7970.6840.692

由表3可知,本文提出的采樣算法提高了分類(lèi)效果，在ecoli、ionosphere、blood、abalone這4個(gè)數(shù)據(jù)集上F1-value均高于其他采樣算法。ecoli數(shù)據(jù)集上提高了7.1個(gè)百分點(diǎn)，提高最少的ionosphere數(shù)據(jù)集上也有2.2個(gè)百分點(diǎn)，平均提高約5.4個(gè)百分點(diǎn)。表4實(shí)驗(yàn)數(shù)據(jù)同樣表明了HSBC算法的優(yōu)越性，除了bank數(shù)據(jù)集，其他數(shù)據(jù)集經(jīng)HSBC-GBDT操作后AUC更高，其中blood數(shù)據(jù)集上最多提高了6.2個(gè)百分點(diǎn)，提高最少的ionosphere數(shù)據(jù)集上也有1.6個(gè)百分點(diǎn)，平均提高約3.6個(gè)百分點(diǎn)。

由表3和表4可知，本文新提出的HSBC-GBDT分類(lèi)模型在數(shù)據(jù)集ecoli、ionosphere、blood、abalone上，F(xiàn)1-value與AUC相對(duì)更高，分類(lèi)效果比對(duì)比模型更好。在數(shù)據(jù)集bank中HSBC-GBDT的F1-value與AUC稍微偏低，這是因?yàn)閎ank數(shù)據(jù)集不平衡率較高，易將少數(shù)類(lèi)樣本視作噪聲刪去，導(dǎo)致HSBC-GBDT算法表現(xiàn)效果稍差。

圖2 F1-value變化曲線(xiàn)

圖3 AUC變化曲線(xiàn)圖

為了更直觀(guān)地分析各算法的分類(lèi)效果，圖2和圖3分別繪制了5個(gè)數(shù)據(jù)集放入6種算法中F1-value及AUC折線(xiàn)圖。由圖可以觀(guān)察到：當(dāng)不平衡數(shù)據(jù)集不做任何處理，直接用GBDT算法分類(lèi)時(shí)，效果較差，說(shuō)明重采樣對(duì)解決不平衡問(wèn)題有顯著效果。在ecoli、bank、abalone數(shù)據(jù)集中，經(jīng)過(guò)隨機(jī)欠采樣處理后分類(lèi)效果較好，這是因?yàn)殡S機(jī)欠采樣的隨機(jī)性，效果時(shí)好時(shí)壞。總體來(lái)說(shuō)，HSBC-GBDT相比較其他算法分類(lèi)性能更優(yōu)，具有更強(qiáng)的魯棒性。

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

本文針對(duì)不平衡數(shù)據(jù)分類(lèi)問(wèn)題，提出了一種基于聚類(lèi)的混合采樣算法，首先對(duì)原始數(shù)據(jù)集聚類(lèi)，然后對(duì)每一簇樣本計(jì)算不平衡比，根據(jù)不平衡比的大小對(duì)該簇樣本做出相應(yīng)處理，以實(shí)現(xiàn)數(shù)據(jù)集的均衡。實(shí)驗(yàn)結(jié)果表明，本文所提算法與一般采樣算法相比具有更好的性能，并提高了不平衡數(shù)據(jù)集的分類(lèi)效果。但本文算法仍然存在不足，對(duì)于不平衡率較大的數(shù)據(jù)集，HSBC算法中m1取值較大時(shí)，相應(yīng)簇中少數(shù)類(lèi)樣本過(guò)少，對(duì)該簇進(jìn)行混合采樣，容易造成過(guò)擬合，取值較小時(shí)又不能很好地去除噪聲樣本。接下來(lái)的工作將致力于在HSBC算法的基礎(chǔ)上繼續(xù)改進(jìn)，使其能很好地適用于不平衡率較大的數(shù)據(jù)集。