基于聚類混合采樣的不平衡數據分類

史明華,吳廣潮

(華南理工大學數學學院,廣東 廣州 510641)

0 引 言

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

目前，針對不平衡數據集分類性能提高的解決辦法主要圍繞在數據層面和算法層面展開。數據層面通過欠采樣、過采樣以及混合采樣等數據重采樣方法，算法層面通過改進已有的分類算法，如代價敏感學習[7-8]、單類學習[9]和集成學習[10-11]等來提高分類性能。本文從數據層面上來平衡數據分布。

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

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

1 相關知識

1.1 SMOTE算法

SMOTE算法是由Chawla等人[12]提出的一種過采樣算法，該算法的主要思想為：先對少數類樣本計算其少數類k近鄰，接著在少數類樣本之間進行線性插值生成新的少數類樣本。對于少數類中每一個樣本xi，以歐氏距離為標準計算它到少數類樣本集中所有樣本的距離，得到其最近鄰，隨機選取近鄰xj，然后由以下公式構建新的樣本：

xnew=xi+δ(xj-xi)

其中，δ為0～1之間的隨機數。

1.2 K-means算法

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

輸入：數據集X={x1,x2,…,xn}，生成簇個數k

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

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

2)foriinndo

forjinkdo

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

3)forjinkdo

返回步驟2，直到當前簇心不再更新

1.3 GBDT算法

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

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

輸出：強學習器F(x)

1)初始化弱學習器：

2)forminMdo

foriinndo

forjinJdo

//括號中內容為真則I=1,否則I=0

3)返回：

2 基于聚類的混合采樣算法

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

2.1 基于聚類的混合采樣算法

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

1)由K-means算法將原始數據集分成多個簇。

2)對每一簇樣本計算不平衡比。

3)根據IR對相應簇進行剔除部分樣本或混合采樣處理。

4)輸出新數據集。

詳細算法步驟如下：

輸入：數據集S

輸出：新數據集Snew

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

2)Kmeans(S)→clusters

//Kmeans算法生成多個簇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簇中多數類樣本個數，min_count(c)指c簇中少數類樣本個數，maj_sample指c簇中多數類樣本，count(c)指c簇總樣本個數，min_sample指c簇中少數類樣本。

當m1越大時，簇內少數類樣本相對越少，IR大于m1時，將少數類樣本視作噪聲去掉；同理，IR小于m2時，將多數類樣本去掉；若簇內IR小于m1而又大于1時，多數類樣本多，少數類樣本少，先對多數類樣本聚成子簇，用子簇心代替多數類樣本以減少樣本個數，再對少數類樣本運用SMOTE生成新的少數類樣本；若簇內IR大于m2而又小于1時，少數類樣本個數多，多數類樣本個數少，對少數類樣本聚成子簇以減少樣本個數，再對多數類樣本運用SMOTE合成新的多數類樣本。通過以上操作，較好地均衡了類內樣本分布。

2.2 HSBC-GBDT算法

數據集經過預處理、HSBC算法處理后得到較為均衡的數據集，然后將該數據集放入GBDT分類器。具體的算法流程如圖1所示。

圖1 HSBC-GBDT算法流程圖

3 實驗結果與分析

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

3.1 數據集

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

表1 數據集描述

數據集數目類別數目特征數目不平衡比ecoli336259,7773.36ionosphere351225,126341.79bank45214000,521167.68blood748570,17843.20abalone41772870,130782.20

3.2 評價指標

對于不平衡問題，本文采用F1-value、AUC作為評價指標，其中多數類為負類，少數類為正類。分類結果的混淆矩陣如表2所示。

表2 二分類混淆矩陣

分類預測正類預測負類實際正類TPFN實際負類FPTN

查準率：

precision=TP/(TP+FP)

查全率：

recall=TP/(TP+FN)

F1-value：

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

3.3 實驗結果

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

表3 各算法在不同數據集上的F1-value對比

算法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 各算法在不同數據集上的AUC值對比

算法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可知,本文提出的采樣算法提高了分類效果，在ecoli、ionosphere、blood、abalone這4個數據集上F1-value均高于其他采樣算法。ecoli數據集上提高了7.1個百分點，提高最少的ionosphere數據集上也有2.2個百分點，平均提高約5.4個百分點。表4實驗數據同樣表明了HSBC算法的優(yōu)越性，除了bank數據集，其他數據集經HSBC-GBDT操作后AUC更高，其中blood數據集上最多提高了6.2個百分點，提高最少的ionosphere數據集上也有1.6個百分點，平均提高約3.6個百分點。

由表3和表4可知，本文新提出的HSBC-GBDT分類模型在數據集ecoli、ionosphere、blood、abalone上，F1-value與AUC相對更高，分類效果比對比模型更好。在數據集bank中HSBC-GBDT的F1-value與AUC稍微偏低，這是因為bank數據集不平衡率較高，易將少數類樣本視作噪聲刪去，導致HSBC-GBDT算法表現效果稍差。

圖2 F1-value變化曲線

圖3 AUC變化曲線圖

為了更直觀地分析各算法的分類效果，圖2和圖3分別繪制了5個數據集放入6種算法中F1-value及AUC折線圖。由圖可以觀察到：當不平衡數據集不做任何處理，直接用GBDT算法分類時，效果較差，說明重采樣對解決不平衡問題有顯著效果。在ecoli、bank、abalone數據集中，經過隨機欠采樣處理后分類效果較好，這是因為隨機欠采樣的隨機性，效果時好時壞?？傮w來說，HSBC-GBDT相比較其他算法分類性能更優(yōu)，具有更強的魯棒性。

4 結束語

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