基于DBSCAN聚類分解和過采樣的隨機森林不平衡數據分類算法

趙小強, 姚青磊

(1. 蘭州理工大學 電氣工程與信息工程學院, 甘肅 蘭州 730050; 2. 蘭州理工大學 甘肅省工業過程先進控制重點實驗室, 甘肅 蘭州 730050; 3. 蘭州理工大學 國家級電氣與控制工程實驗教學中心, 甘肅 蘭州 730050)

隨著計算機、通信技術的快速發展,互聯網和工業等領域產生了大量的數據,如何在這些大量數據中找到并使用有價值的數據已成為目前研究的熱點.因此,數據挖掘引起了人們的極大關注,而數據不平衡問題是數據挖掘中的一個難點,該問題是指在數據集中某一類的實例數量遠遠少于其他類的實例數量的情況,其中實例數較多的稱為多數類(負類),實例數較少的稱為少數類(正類),多數類和少數類數量的比例稱為不平衡比率.傳統的機器學習算法,如SVM[1-2]、決策樹[3]、KNN[4]等都是假定數據集是在平衡的情況下進行分類的.而在現實生活中,許多領域都存在不平衡數據,如信用卡詐騙[5]、蛋白質分類[6]、故障診斷[7]和癌癥診斷[8]等.若使用傳統的機器學習分類算法,在處理不平衡數據集時會為了追求較高的準確率而導致分類算法偏向于負類.但是在二分類中,正類負類的錯分代價往往是不同的,例如在信用卡詐騙中,將詐騙事件誤判為正常事件會導致不可預估的損失;在癌癥診斷中,將發病群體比較少的癌癥患者誤判成正常人,會導致病人錯過最佳的治療時機,嚴重的可能導致生命威脅.因此,研究高效的不平衡數據分類算法很有意義.

近年來,有許多國內外學者對不平衡數據分類問題進行了大量的研究.在處理不平衡數據分類問題時,改進方法主要包括兩個層面:數據預處理層面和分類算法層面.數據預處理層面也稱為數據平衡方法,通過對不平衡數據進行采樣來改變數據樣本分布或消除不平衡性,其代表性的方法包括欠采樣、過采樣和混合采樣.分類算法層面是對現有的算法進行修改,提高模型對少數類的識別能力,典型的算法包括代價敏感法、單類學習法和集成學習法.

Chawla等[9]提出了一種稱為SMOTE(synthetic minority oversampling technique)的過采樣算法,該算法不像隨機過采樣算法只是單純地復制或者簡單地旋轉來增加樣本個數,而是通過合成新的、無重復的小樣本并進行插值處理擴充樣本數量,并且該方法沒有造成數據丟失.Pakrashi等[10]基于一種訓練多類集成分類模型的新視角,利用卡爾曼濾波器的傳感器融合特性,將多個獨立的多類分類器組合在一起,構建了多類集成分類算法.Chawla等[11]在SMOTE的基礎上,將SMOTE與AdaBoost結合,提出了SMOTEBoost算法,該算法從少數類中合成實例從而間接改變權重,進一步地提升了分類模型的性能,但是如果原始數據集的不平衡率比較高,使用過采樣算法得到最理想的平衡數據集(不平衡率為1∶1)時,生成的假樣本會更多,會導致數據集樣本數量特別大,從而拖慢算法運行速度.Seiffert等[12]基于SMOTEBoost算法,提出了一種基于隨機欠采樣和boosting結合的混合算法,稱為RUSBoost,隨機欠采樣隨機刪除大多數實例以形成平衡的數據集,但是由于隨機欠采樣的局限性,得到的數據集可能會丟失一部分多數類中的有用信息.Rayhan等[13]提出了一種基于聚類的欠采樣和Adaboost結合的算法,稱為CUSBoost,該算法將原始數據集分為多數類和少數類,并使用k-means聚類算法將多數類分成多個簇,然后通過隨機選擇50%的實例對多數類進行欠采樣,達到在欠采樣的情況下盡可能地保留多數類有用信息.Ahmed等[14]將欠采樣和過采樣算法結合起來,提出了RSYNBagging算法,該算法在奇數次迭代的過程中使用隨機欠采樣算法,在偶數次迭代中使用ADASYN過采樣算法,并使用集成學習中的Bagging算法進行投票得到分類結果.Elyan等[15]提出了CDSMOTE算法,該算法使用k-means聚類算法將多數類分為多個簇,然后將少數類樣本應用SMOTE算法來平衡數據集,避免了信息丟失,但是由于分類器較為單一,沒有達到好的效果.上述方法雖然都在一定程度上提高了不平衡數據的分類性能,但是會存在數據丟失或者數據量過大等問題.

針對這些問題,本文提出了一種基于DBSCAN聚類分解和過采樣的隨機森林不平衡數據分類算法,該算法通過將不平衡數據集分為多數類和少數類,先將DBSCAN算法應用于多數類進行聚類,將多數類分解為多個子類,然后使用Borderline-SMOTE過采樣算法對少數類數據進行處理,最后將這個方法和隨機森林結合起來.經實驗驗證,該算法能有效地提升不平衡數據的分類效果.

1 相關算法

DBSCAN[16](density-based spatial clustering of applications with noise)是一種基于密度的聚類算法,它的目的是發現任意形狀的簇,參數描述了領域的樣本分布緊密程度,其中定義了密度的領域半徑,定義了核心點的閾值.

當設定eps和MinPts=5之后,算法原理如圖1所示.該算法選定某個核心對象(圖中黃色點),不斷向密度可達的區域擴張,由密度可達的關系導出最大密度相連的樣本集合,這個集合就是一個簇.

圖1 DBSCAN算法原理圖

1.2 Borderline-SMOTE算法

Borderline-SMOTE[17]是一種改進的SMOTE算法.如圖2所示,該算法將少數類樣本按邊界分為三類,周圍一半以上是少數類樣本的稱為Safe,一半以下是少數類樣本的稱為Danger,周圍沒有少數類樣本的稱為Noise.由于Safe群體被誤分可能較小,而Danger群體被誤分可能很大,所以Borderline-SMOTE算法只對Danger群體樣本進行采樣處理.

圖2 少數類樣本邊界劃分Fig.2 Minority sample boundary division

2 基于DBSCAN聚類分解和過采樣的隨機森林不平衡數據分類算法

本文提出一種基于密度的聚類分解技術和過采樣技術相結合的隨機森林不平衡數據分類算法,通過將DBSCAN算法應用于不平衡數據集,來對數據集中多數類進行聚類分解,將多數類劃分為多個子類,以降低多數類在數據集中的優勢;然后使用過采樣技術,增加少數類的個數,提高少數類在數據集中的優勢.對于不平衡數據集A,先將其分解為數據集Ac,然后計算類分解之后類別的平均值,如果少數類數據個數仍然少于平均值個數,再使用過采樣算法,以重新評估分解后的數據集Ac,且使用過采樣算法后,會創建一個新的數據集Aco,這個新數據集是類分解和過采樣之后的結果,最后將隨機森林分類技術應用于數據集Aco.基于DBSCAN聚類分解和過采樣的隨機森林不平衡數據分類流程圖如圖3所示.

圖3 基于DBSCAN聚類分解和過采樣的隨機森林不平衡數據分類算法流程圖

通過DBSCAN聚類分解和過采樣方法得到平衡數據集,再建立隨機森林分類模型,設隨機森林分類模型規模為t,則具體步驟如下:

輸入:不平衡樣本集A,隨機森林決策樹數量t.

輸出:分類結果.

Step1:對樣本集A中多數類negative=(n1,n2,…,nm)使用DBSCAN聚類算法,最終劃分為簇c1,c2,…,cn.

Step2:計算簇c1,c2,…,cn的平均值,若少數類樣本數量大于平均值,則轉至Step5;若少數類樣本數量小于平均值,則選取最接近平均值的一個子類作為過采樣數量標準,計算少數類樣本個數pnum,多數類子類樣本個數nnum.

Step3:對少數類按邊界劃分為Safe樣本、Danger樣本、Noise樣本,將Danger樣本記為{p′1,p′2,…,p′a},樣本個數記為dnum.計算Danger樣本中每個樣本p′i與少數類positive的k近鄰,根據nnum和pnum的比例設置一個采樣比例以確定采樣倍率N,根據采樣倍率N隨機選擇s個k近鄰與樣本p′i進行線性插值,合成少數樣本pnew:

pnew=p′i+rand(0,1)×dj(j=1,2,…,s)

(1)

其中:dj代表p′i與其s個k近鄰的距離.

Step4:將合成少數樣本加入原本的少數類中,構成新的少數類positive-c1.

Step5:將多數類子集和少數類數據集共同合成一個新的平衡數據集Aco.

Step6:計算新的平衡數據集Aco樣本個數N,利用Bootstrap有放回地隨機抽取N次,生成和原訓練集樣本個數相同的子訓練集,這個過程重復t次,得到t個子訓練集,構建t棵分類決策樹.

Step7:分裂時從訓練樣本的R個特征中隨機選擇r個特征個數(r

Step8:使用生成的t棵決策樹組成隨機森林,最終的輸出結果由每個決策樹的分類結果投票決定.

2.1 聚類分解

聚類分解是將聚類算法應用于數據集上,將數據集中的同一類數據分為一組,以分解為多個子集,其目的主要有兩個,一是降低多數類的優勢,二是不會產生任何的數據信息丟失.當今流行的方法是使用k-means算法對數據集進行聚類,但是該方法易受噪聲的干擾.針對這個問題,本文使用了對噪聲不敏感的DBSCAN聚類算法,將該算法應用于數據集的多數類上,來生成多個多數類子類,從而減少了異常值對模型的影響,并且不用像k-means算法那樣預先設置k值.

應用聚類分解之后,其結果如圖4所示,圖4a表示二分類不平衡數據集的原始數據分布,圖4b表示使用DBSCAN聚類分解之后的數據分布.圖4a和圖4b中是相同的數據集,但是集群分布不同.通過聚類分解之后,將negative類別分解為negative-c1、negative-c2等(圖4b中分別用c1、c2等表示),這樣,就可以在保留所有數據信息的同時改變數據集的分布.

圖4 聚類分解應用于不平衡數據集

二進制分類任務如下式所示:

h(X):X→Y

(2)

在h(X)中,將每個實例xi映射到yi∈{N,P}.在使用聚類分解之后,得到一個新的分類任務h′(X):

h′(X):X→Y′

(3)

將每個實例xi映射到y′i∈{Nc1,Nc2,Nc3,…,P}.轉換數據可以將負類N聚類成多個子類,有效地降低了負類N在數據集中的主導地位,這也意味著通過聚類分解方法,將原始的二進制分類問題轉化成了多分類問題.

2.2 少數類過采樣

由于樣本的分布緊密程度不盡相同,在應用DBSCAN聚類分解算法以后,從原始的多數類實例中可能會產生新的多數類或少數類,所以,需要計算少數類的樣本數量是否超過多數類子類的平均樣本數,如果沒有超過,則需對少數類進行過采樣.

當今最流行的過采樣算法是Chawla提出的SMOTE算法,SMOTE算法通過特征空間而不是數據空間來使用k近鄰算法進行生成合成實例,有多位學者[18]驗證了該算法在不平衡數據上得到了不錯的效果.但是使用SMOTE算法生成的樣例可能會出現樣本重疊、噪聲等問題[19],為了避免這些問題,本文采用Borderline-SMOTE算法來進行過采樣處理,它只對Danger群體的邊界樣本進行過采樣處理,這樣可以很好地避免少數類中的噪聲問題,并且降低了少數類樣本中的類內不平衡問題的影響.

Borderline-SMOTE算法和SMOTE算法一樣需要選擇一個多數類和一個少數類作為輸入,多數類的樣本數量是對少數類樣本合成數量的參考標準.在本文中,選擇使用最接近平均值線的多數類子類樣本作為Borderline-SMOTE的多數類輸入,例如在圖4b中,被選用的多數類子類為negative-c1.使用過采樣方法的目的是增加少數類樣本數量,進一步減少不平衡比率,降低多數類優勢,使正負兩類趨于平衡,提高少數類樣本的分類精度.

2.3 隨機森林

集成學習的原理是將多個弱分類器結合起來,以獲得比單一弱分類器更好的結果,最常用的集成學習算法分為Boosting和Bagging.隨機森林[20]是Bagging算法的變體,是一種包含多個決策樹的集成算法,它訓練樣本時采用Bootstrap技術,從原始數據集中有放回地隨機抽取N個樣本作為一棵樹的訓練集,每次隨機選擇訓練樣本特征中的一部分構建決策樹,每棵決策樹訓練生長過程中不進行剪枝,最后采用投票的方式決定分類器最終的結果.由于隨機森林的隨機性,避免了過擬合的風險,提高了分類準確率[21].

3 實驗結果與分析

本文實驗是在Windows10系統、AMD 7-4800處理器、NVIDIA GTX 1650ti顯卡、16GB內存的計算機上進行,編程語言為Python,使用PyCharm平臺實現.

3.1 實驗數據

本文使用KEEL公共數據庫(http://www.keel.es)[22]中的36個數據集,這些數據集全都常用于不平衡數據分類中.如表1所列,每個數據集具有不同的不平衡比率、不同的實例數量、不同特征的二分類數據集.

Glass數據集的屬性有9個,屬性名稱分別為RI、Na、Mg、Al、Si、K、Ca、Ba、Fe.Glass0是Glass數據集的一個版本,其中第0類屬于正類,其余屬性屬于負類;Glass2中第2類屬于正類,其余屬性屬于負類;Glass-0-1-2-3_vs_4-5-6中0、1、2、3類屬于正類,4、5、6類屬于負類.

Yeast是一個酵母菌數據集,用于預測酵母菌蛋白質的定位位點.在yeast數據集中屬性有8個,屬性名稱分別為Mcg、Gvh、Alm、Mit、Erl、Pox、Vac、Nuc.Yeast1中Nuc屬于正類,其余屬性屬于負類;Yeast-1-2-8-9_vs_7中Vac屬于正類,Nuc、Cyt、Pox、Erl類屬于負類;Yeast-1_vs_7中Pox屬性已被刪除,Vac屬于正類,Nuc屬于負類.

表1 數據集

3.2 評價指標

不平衡數據分類的難點不只體現在分類模型的訓練上,還體現在如何正確地評價不平衡分類模型的性能上.在不平衡數據處理中,因為不平衡數據中多數類和少數類具有不同的錯分代價,少數類的錯分可能帶來比較嚴重的后果,即便總體準確率較高,但并不代表分類模型是有效的,因此傳統評價指標不能很好地反映分類模型的性能好壞.

對于不平衡數據的分類性能評價,有相關學者在混淆矩陣的基礎上,提出了F-measure、G-mean等一系列評價標準.混淆矩陣如表2所列.

表2 混淆矩陣

相關評估指標如下:

Precision表示精確率,也稱為查準率,表示預測為正類的樣本中真正的正類樣本所占的比例,其公式為

(4)

Recall表示召回率,也稱為查全率,表示正類樣本中被預測正確的樣本所占的比例,公式為

(5)

F-measure也稱為F-score,是可以兼顧精確率和召回率的最佳組合,公式為

(6)

其中:β為參數,當β=1時,稱為F1值.

G-mean也稱為G均值,是一種衡量數據集整體分類性能的綜合評價指標,如下式所示:

(7)

ROC曲線(receiver operating characteristic curve)是表示以假陽性率(FPR)為橫軸和以真陽性率(TPR)為豎軸的曲線,曲線越靠近坐標軸左上角代表分類器性能越好.ROC曲線與坐標軸圍成的面積被稱為AUROC(area under the receiver operating characteristic curve)值,AUROC值越大,代表分類器性能越好.假陽性率和真陽性率公式如下:

(8)

(9)

3.3 實驗結果

為驗證本文所提算法(DBSRF)的有效性,使用Precision、Recall、F1Score、AUROC、G-mean 5個評價指標對數據集進行實驗驗證.在實驗中,DBSCAN算法敏感參數設定為eps=0.5,MinPts=5;SMOTE、Borderline-SMOTE、ADASYN算法近鄰數k設置為5;Borderline-SMOTE算法中最近鄰參數m設置為10;Adaboost、Bagging、隨機森林(RF)使用C4.5決策樹作為基分類器,集成學習的n_estimators設置為50,n_estimators在Adaboost和Bagging中代表迭代次數,在隨機森林代表生成的決策樹數量.數據集按照70%和30%的比率分為訓練集和測試集,實驗進行五倍交叉驗證訓練.

3.3.1不同過采樣方法對比

為證明所選過采樣方法的有效性,在DBSCAN聚類分解和隨機森林分類框架的前提下,使用不同的過采樣方法對數據集進行處理,其中對比的過采樣方法有SMOTE、Borderline-SMOTE和ADASYN.ADASYN[23]算法對不同的少數類樣本賦予不同的權重,從而生成不同數量的樣本,其中較難學習的少數類樣本比容易學習的少數類樣本產生更多的合成數據,因此,ADASYN算法在減少類不平衡的同時,將分類決策邊界向較難學習的少數類方向移動.

在KEEL數據集中選取6組不平衡數據集進行實驗驗證,其結果如表3所列.由表3可知,Borderline-SMOTE在6組數據集中,有4組數據集在五個指標中全優,這是因為該算法僅使用邊界上的少數類樣本來合成新樣本,減少了噪聲的干擾.

3.3.2與基于Adaboost和Bagging算法的對比

為驗證本文數據預處理方法的有效性,將聚類分解過采樣部分與Adaboost和Bagging分別結合.

LIUBoost[24]是將代價敏感和欠采樣結合,并與Adaboost結合的混合算法,首先使用欠采樣方法來平衡數據集,同時保留有關實例局部特征的重要信息,并將該信息合并到Adaboost的權重更新方程中,最大限度地減少了欠采樣帶來的信息損失.本文提出算法使用Adaboost分類器時,對比RUSBoost和LIUBoost算法,性能指標使用AUROC.其五次平均分數如表4所列,在驗證的17個數據集中10個表現最優.由于篇幅限制,在表4中只列出隨機選取的10個數據集的結果.

表3 不同過采樣方法的性能對比

表4 不同數據預處理方法與Adaboost結合的AUROC值對比

UnderBagging是一種基于Bagging的隨機欠采樣算法,數據預處理部分僅對原始數據集進行欠采樣;SMOTEBagging將SMOTE過采樣算法應用在少數類上并與Bagging結合,顯示出了更高的分類精度;ADASYNBagging類似于SMOTEBagging,將ADASYN應用于少數類實例,為較難分類的少數類實例生成更多的合成樣本,同時使用Bagging保持多數類實例不受影響,該方法保持了采樣率的固定,并且不需要額外的參數調整.本文提出算法使用Bagging分類器時,與四種基于Bagging的算法進行對比,性能指標使用AUROC.其五次平均分數如表5所列,在驗證的10個數據集中9個表現最優.

表5 不同數據預處理方法與Bagging結合的AUROC值對比

這可以驗證本文提出的算法在處理不平衡問題時是有效的,優勢在于聚類分解可以降低多數類優勢,并只對少數類邊界樣本進行過采樣,減少了噪聲的干擾,提高了分類模型的性能.

3.3.3不同分類器對比

為驗證分類器在聚類分解和過采樣方法前提下的有效性,將本文所提出的DBSCAN聚類分解和Borderline-SMOTE方法對不平衡數據集進行處理,再使用5種不同的分類器對處理過的數據集進行訓練學習,得到分類結果,其中所選分類器有SVM、Adaboost、Bagging、XGBoost和隨機森林(RF).SVM在處理小樣本高維度的數據時占有優勢;Adaboost不改變訓練數據,迭代時提升錯分樣本權重;在Bagging中只取初始訓練樣本中的一部分來訓練,再對分類任務使用簡單投票法;XGBoost考慮了訓練數據為稀疏值的情況,可以自動學習出它的分裂方向;隨機森林在訓練過程中加入了隨機屬性選擇.此實驗的目的是在聚類分解和過采樣的前提下選擇最合適的分類器.

在驗證的13個數據集中有10個數據集4個指標結果最優、1個數據集3個指標結果最優.由于篇幅限制,在表6中只列出了其中4個數據集的實驗結果.由此可以看出,在本文數據預處理的前提下,隨機森林分類器比SVM、Adaboost、Bagging、XGBoost的分類性能表現更好.

表6 DBSCAN聚類分解和過采樣前提下的不同分類算法的結果

3.3.4 與基于隨機森林的算法對比

為了驗證分類性能,選取使用隨機森林分類的方法進行對比,其中分為兩部分,一部分是欠采樣與隨機森林結合的算法對比,另一部分是過采樣與隨機森林結合的算法對比.

與欠采樣部分中的對比算法有三種,分別為:(1) 傳統隨機森林算法(RF),該算法直接采用Bootstrap對不平衡數據集隨機抽樣形成訓練樣本;(2) 隨機欠采樣與隨機森林結合算法(URF),該算法對多數類樣本進行隨機欠采樣,再與少數類樣本混合形成訓練樣本;(3)k-means聚類算法欠采樣與隨機森林結合算法(CUSRF)[25],該算法對多數類樣本進行聚類形成多個簇,再對每個簇進行隨機欠采樣,與少數類樣本混合形成訓練樣本.在驗證的8個數據集中有5個數據集表現最優,其中shuttle-c2-vs-c4數據集中4個指標全為1.由于篇幅限制,在表7中只列出了其中4個數據集的實驗結果.

與過采樣部分中對比的算法分別為:(1) SMOTE與隨機森林結合算法(SM+RF);(2) 加權SMOTE與隨機森林結合(WSM+RF),該算法在SMOTE算法中讓靠近類別中心和邊界的樣本生成更多的假樣本數量;(3) SMOTE與加權隨機森林(SM+WRF),該算法在決策樹訓練階段,給每棵樹賦予一個權重;(4) 加權SMOTE與加權隨機森林結合(WSM+WRF)[26],該算法先對少數類樣本進行加權過采樣,然后在分類階段增加分類效果好的決策樹權重.G-mean值如圖5所示,從圖5可以看到,本文算法在驗證的數據集中G-mean值全部最優.

表7 欠采樣策略與隨機森林結合方法與本文方法的綜合性能對比

圖5 過采樣策略與隨機森林結合方法與本文方法的G-mean值對比Fig.5 Comparison of the G-mean value between the combination of oversampling strategy and random forest method and the method in this paper

4 結論

本文針對不平衡數據提出了一種基于DBSCAN聚類算法對多數類分解和Borderline-SMOTE對少數類進行過采樣的隨機森林不平衡數據分類算法,該算法在不損失多數類樣本數據信息的前提下降低了多數類在數據集中的優勢,并通過過采樣方法增加少數類實例,進一步降低了不平衡率,從而改進了結果.經實驗證明,對于不同不平衡率、不同樣本數量的數據集,本文算法與當前流行不平衡數據處理方法對比,結果顯示本文算法有效地提高了不平衡數據分類性能.下一步將考慮如何減少對聚類結果的依賴,并對大數據集中的不平衡問題進行研究.