不平衡數據多粒度集成分類算法研究*

陳麗芳，代 琪，趙佳亮

(華北理工大學理學院,河北 唐山 063210)

1 引言

不平衡數據分類問題是機器學習和數據挖掘領域的研究熱點，不平衡數據集指的是數據集中各類別的樣本數量不均衡，導致學習機學習少數類樣本信息量不足，嚴重影響傳統分類算法的分類性能[1]。傳統分類算法雖然在結構上存在一定差異，卻共同遵循誤差最小化原則。在平衡數據集上，采用誤差最小化原則能夠得到最優結果，針對不平衡數據，此原則將會導致分類面向多數類偏移，難以得到準確的分類結果[2]。傳統分類器不能有效地表現不平衡數據集的結構特征，難以確定不平衡數據集的真實分類邊界，導致少數類樣本分類精度降低。

集成學習(Ensemble Learning)融合了多個弱學習機的學習框架，與傳統分類器相比，集成學習框架下的分類器具有更高的泛化性能和分類精度。曹雅茜等[3]利用高斯混合分布的概率模型構造平衡數據集，擴大少數類樣本的潛在決策域，過濾冗余噪聲特征，并對錯分樣本和剩余特征賦權，通過加權集成策略獲得最終分類結果。陳圣靈等[4]根據基分類器分類結果對少數類樣本進行過采樣，增大少數類樣本的權重，并借鑒Focal Loss思想根據基分類器分類結果直接優化自適應提升算法Adaboost(Adaptive boosting)權重，提升分類器的分類精度。Borowska等[5]提出一種新穎的粗粒度計算方法，通過形成信息粒，并分析其在少數類樣本中的包容程度，獲得給定問題的分類結果。Barua等[6]提出一種多數加權少數樣本的過采樣算法MWMOTE(Majority Weighted Minority Oversampling TEchnique)，以信息豐富但難以學習的少數類樣本為基礎，根據歐氏距離確定此類樣本與多數類樣本之間的權重，使用聚類算法從已經賦權的少數類樣本中生成樣本，從而提升模型的分類性能。Alam等[7]提出一種基于遞歸的集成分類算法，并將其應用于多類不平衡數據分類問題，分析結果表明，該算法在多類分類問題或不平衡數據回歸分析中具有更高的性能。張宗堂等[8]通過隨機子空間法提取訓練樣本集，在各訓練子集上構建基分類器，在Adaboost集成框架下，迭代形成最終集成分類器。鄭建華等[9]采用混合采樣策略提升隨機森林基分類器多樣性，在采樣后的平衡子集上訓練子樹，構建改進的隨機森林算法。Zhu等[10]提出基于樹的空間劃分算法SPT(Space Partition Tree)，將數據遞歸劃分為2個子空間，并在集成框架下構建分類模型，通過合并所有決策子空間，為原始問題提供了新的決策域。Collell等[11]將閾值移動技術與Bagging集成分類算法結合，引入決策閾值移動方法，利用后驗概率估計不平衡數據分類的最大性能。Zhu等[12]利用相空間重構方法構建高維特征空間分布模型，通過隨機森林選擇不同特征進行分類，并輸出具有不同屬性特征的分類結果。Wang等[13]提出一種迭代度量學習IML(Iterative Metric Learning)方法，探索不平衡數據之間的相關性，構建有效的分類數據空間，尋找最穩定的鄰域，從而提升分類模型的分類精度。

目前，對于序貫三支決策的分類算法已有少量研究[14]，主要是將序貫三支決策作為分類器，通過計算樣本分類代價，對樣本進行分類，當不確定域為空集時，模型分類結束。雖然該算法在平衡數據集上能夠有效地分類，但針對不平衡數據，尤其是高度不平衡數據，該算法難以合理地設置代價矩陣和少數類樣本的決策代價，直接應用該算法處理不平衡數據，仍然存在難以識別少數類樣本、分類精度偏低的問題。因此，將序貫三支決策的粒化思想作為數據預處理方法，在集成學習框架下，分別以各粒層空間中粒化數據作為基分類器的訓練集，構建粒化基分類器，能夠有效地提升對不平衡數據的分類精度。

集成學習是目前常用的不平衡數據分類框架，與傳統分類器相比，在處理不平衡數據方面，具有更高的分類性能和泛化能力[15,16]。學者們主要從改變賦權方法和提升基分類器差異性2個角度提升模型的分類精度。文獻[3-7]使用新的賦權方法改變樣本或基分類器的權重，從而提升集成分類算法的分類性能。文獻[8-13]通過不同的數據劃分方法，提高集成分類算法基分類器的差異性。空間劃分在一定程度上可以有效提升模型的分類精度，但存在穩定性差、泛化能力弱等問題。

因此，本文提出基于序貫三支決策的多粒度集成分類算法MGE-S3WD(Multi-Granularity Ensemble classification algorithm based on Sequential Three-Way Decision)，通過序貫三支決策粒化數據集可以有效地提升訓練子集的差異性，降低數據集的不平衡比，從而提升算法的穩定性和泛化能力。首先，利用二元關系逐層添加屬性，實現數據集的動態劃分；其次，構建代價矩陣，計算正域、邊界域和負域的閾值，形成多層次粒結構；再次，對各粒層空間上的數據子集按照定義的融合規則，形成新的空間劃分訓練子集；最后，在各訓練子集上構建基分類器，并對基分類器分類結果進行集成，獲得最終分類結果，以KEEL不平衡數據庫(Knowledge Extraction based on Evolutionary Learning imbalanced data sets)中的不平衡數據集作為實驗數據，驗證算法分類性能。

2 預備知識

2.1 序貫三支決策

三支決策[17]是處理不確定復雜問題的有效策略，其主要思想是“三分而治”，即將一個整體劃分為3個相互獨立的區域，根據不同區域的特征選擇不同的處理方法。序貫三支決策[18]是一種處理動態決策問題的模型，根據層次粒結構的序關系可以分為3種情況：自頂向下、自底向上和自中向外。自頂向下是一種常見的粒結構解決方法，主要是從低層次粒度向高層次粒度發展。

根據n個等價關系，可以在不同的條件屬性集下得到論域的不同劃分，且滿足：

[X]Cn?…?[X]C2?[X]C1

(1)

其中，X表示多個樣本的矩陣形式， [X]Ci表示不同條件屬性下得到信息粒，Ci,i=1,…,n為條件屬性集，Cn表示使用所有條件屬性進行劃分，以此類推。

由此可以得到一個n層的粒結構，可以表示為：

GS=(GS1,GS2,…,GSn)

(2)

GSi=(Ui,Ei,Ci,[X]Ci)

(3)

其中,GSi表示第i個粒結構，Ui為粒結構中的非空有限集，Ei為Ui中存在的等價關系，同樣，此處的Ci表示粒結構中的條件屬性集。

在多層次粒結構中，每一層屬性的選擇方式取決于動態決策任務的目標。在序貫三支決策中，對劃分到邊界域的對象，只有最后一層采用二支決策，其余粒層均采用三支決策。因此，需要根據實際情況，在每個粒層上分別設置合理的三支決策閾值[19]。

(4)

(5)

BND(αi,βi)(vi)=

{x∈Ui+1|βiivi(Desi(X))iαi}

(6)

其中,x表示待決策樣本，viDesi(X)表示待決策對象集，POS(αi,βi)(vi)表示正域，NEG(αi,βi)(vi)表示負域，BND(αi,βi)(vi)是邊界域，邊界域中的對象均被延遲決策。隨著從低層獲取更多的信息，邊界域逐漸縮小，對象逐漸從BND被劃分到POS和NEG。最終在最底層實現簡單的二支決策。

定義2[14]給定一個決策表S=(U,Ct=C∪D,{Va|a∈Ci},{Ia|a∈Ci})，假設有n+1層粒層空間，n≥1,在決策表S上的粒化定義為：

G={g(Ci)|Ci?C}

(7)

其中，g(Ci)為某一特定相同粒度的信息粒集合對U的劃分，C為決策表中條件屬性集，D為決策表中決策屬性集，Va為每個屬性a∈Ci的值的集合，Ia為每個屬性a∈Ci的信息函數，Ci,1≤i≤n，是條件屬性子集，且滿足條件C1?C2?…?Cn?Cn+1=C。

2.2 集成學習

集成學習是一種機器學習框架，通過構建并結合多個學習機完成學習任務，從而獲得比單一學習機更好的泛化性能。根據各基學習機數據之間是否存在依賴關系，集成學習可以分為2類：一類是具有強依賴關系的學習算法，以boosting算法為代表[20]；另一類是不存在依賴關系的學習算法，以隨機森林為代表[21]。根據不同的數據集，可以選擇“同質”弱學習機，也可以選擇“異質”學習機，較多研究者更傾向于選擇“同質”弱學習機進行集成學習[22]。CART(Classification And Regression Trees)決策樹具有較高的分類精度和穩定性，因此本文選擇CART決策樹作為集成分類算法的基分類器。

3 算法設計與模型構建

3.1 算法設計

基于序貫三支決策的多粒度集成分類算法MGE-S3WD流程圖如圖1所示。其中，Ai表示條件屬性集C中的第i個屬性。

Figure 1 Flowchart of multi-granularity ensemble classification algorithm based on sequential three-way decision圖1 基于序貫三支決策的多粒度集成分類算法流程圖

該算法具體流程描述如下：

(1)數據集粒層劃分。

Step 1數據集中各屬性之間的量綱或取值范圍存在一定差異性，因此，為了避免這些因素的影響，利用最大-最小歸一化方法對數據集中的數據進行歸一化處理，如式(8)所示：

(8)

Step 2文獻[23-25]中將屬性均勻離散為3個區間，且分類或回歸性能較好。因此，本文按照此方式對屬性進行離散化處理。如果需要更細的劃分，可以選擇更多的粒化區間，粒化區間越多，粒層空間越細，劃分過程的時間復雜度越高。

Step 3選擇2個屬性作為初始屬性集，使用二元關系的交運算(如式(9)所示)劃分粒層空間，形成初始粒層空間Ω0，并逐層添加屬性，動態劃分數據集，最終形成n個粒層空間Ωn。

令R和S是U上的2個二元關系，定義二元關系的交運算[26]為：

R∩S={(x,y)|xRy∧xSy}

(9)

(2)粒層空間上的三支劃分。

Step 4[27]設置決策結果的代價矩陣，如表1所示。

Table 1 Cost matrix表1 代價矩陣

其中，xC(P)表示類別C中屬于正類P的樣本；xC(N)表示類別C中屬于負類N的樣本；λPP表示將正類樣本分到正域的代價；λBP表示將正類樣本分到邊界域的代價；λNP表示將正類樣本分到負域的代價；λPN表示將負類樣本分到正域的代價；λBN表示將負類樣本分到邊界域的代價；λNN表示將負類樣本分到負域的代價。

Step 5[27]根據式(10)和式(11)計算閾值α和β。

(10)

(11)

Step 6[27]根據式(11)計算對應粒層空間上各區域的條件概率，并將粒層空間上的子空間劃分為正域、邊界域和負域。

(12)

因此，當Pr(Si)≥0.75時，數據子集Si為正域；當0.75>Pr(Si)>0.4時，數據子集Si為不確定域；當Pr(Si)≤0.4時，數據子集Si為負域。

(3)粒層空間上融合數據子集。

Step 7分別將初始粒層空間Ω0至第n層粒層空間Ωn上的子集按照正域與邊界域、正域與負域、邊界域與負域組成新的訓練子集Di。

算法偽代碼如算法1所示：

算法1不平衡數據多粒度集成分類算法

輸出：測試集集成分類結果。

1.functioncalculateP(data)

2.G[ ]:list forG-mean

3. predict[ ]:list fory_predict

4.foriinit tolen(zong_ls) byincrdo

5.ls_bian[ ]:list for Boundary domain

6.ls_fu[ ]:list for Negative domain

7.ls_zheng[ ]:list for Positive domain

8.forcinit tozong_ls[i] byincrdo

9.p=len(list(set(len(zong_ls)).intersection(set(c))))/len(c);

10.ifp≥0.75then

11.ls_zheng←c

12.elif0.4

13.ls_bian←c

14.else

15.ls_fu←c

16.endfor

17.clf=DecisionTreeClassifier(criterion='gini');

18.ifclf.score>0.5then

19.predict←y_predict

20.endfor

21.returnpredict

3.2 模型構建

在不同粒層空間的訓練子集Di上構建CART決策樹，訓練基分類器。分類模型構造過程如下所示：

步驟1數據動態劃分。利用二元關系動態劃分數據集，構建序貫三支決策粒化算法，科學地粒化數據集，獲得不同的粒層空間Ω0,Ω1,…,Ωn。

步驟2融合數據子集。將粒層空間上劃分形成的數據子集按照正域與邊界域、正域與負域、邊界域與負域融合數據，形成數據子集Di。

步驟3構建分類模型。以粒層空間中形成的數據子集Di作為模型的訓練數據集，構建CART決策樹。根據式(13)計算數據子集Di的基尼系數，如果基尼系數小于閾值，則返回決策子樹，當前節點停止遞歸。

在分類問題中，數據集中類別數目為m，樣本p屬于第i類的概率為Pi，則該樣本的基尼系數為：

(13)

樣本集S′的基尼系數為：

(14)

其中，|S′|表示集合S′的總樣本數，|Di|表示集合S′中屬于第i類的樣本數。基尼指數表示集合S′的不確定性。

計算當前節點各特征值對數據子集Di的基尼系數。

選擇基尼系數最小的特征A和對應的特征值a。根據最優特征和最優特征值，將數據子集劃分為2部分，同時建立當前節點的左右節點，對左右子節點遞歸生成決策樹。

4 仿真實驗與性能分析

4.1 數據集和仿真環境

基于Python實現算法仿真。系統環境：CPU：Intel i5-6500；RAM：8 GB；操作系統：Windows 10 專業版；解釋器：Python 3.7。

MGE-S3WD算法主要使用KEEL不平衡數據庫中的26組數據集進行仿真實驗，數據集基本信息如表2所示。表2中不平衡比IR(Imbalance Ratio)表示多數類樣本與少數類樣本數量的比值。實驗過程中，所有數據集均按照訓練集80%，測試集20%的比例隨機劃分。

4.2 性能分析

MGE-S3WD算法以CART決策樹作為分類工具，構建分類模型，并與文獻[8]中的隨機子空間集成分類算法(RSboost)、隨機森林算法(RF)、Stacking集成框架下的分類算法進行對比實驗，RSboost分類算法采用文獻[8]中給出的運算過程及默認參數，而隨機森林算法和Stacking集成分類算法均采用默認參數。

仿真過程中，采用五折交叉驗證的方式以G-mean和F-measure12個指標的均值作為算法最終分類得分，驗證算法的分類性能，通過2個評價指標的標準差驗證算法的穩定性，算法的G-mean值如表3所示，最優結果均以加粗的形式在表格中標出。

Table 2 Data sets basic information表2 數據集基本信息

分析表3中各分類算法的G-mean值可以看出，MGE-S3WD算法在ecoli1、ecoli4、glass0、glass1、glass2、glass4、glass6、haberman、poker-8-9_vs_5、vehicle1、yeast4、yeast5、yeast6 13個數據集上的分類精度明顯優于其他3種集成分類算法，在不平衡比較高的數據集上，MGE-S3WD能取得更高的分類精度。在new-thyroid1、newthyroid2 2個數據集上，RSboost集成分類算法優于其他算法；在ecoli3、vehicle3、vowel0 3個數據集上，基于Stacking集成的分類算法優于其他算法；在ecoli2、page-blocks0、pima、vehicle0、vehicle2、wisconsin、yeast1、yeast3 8個數據集上，隨機森林算法優

Table 3 Classification G-mean of each algorithm表3 各算法分類G-mean值

于其他算法，而MGE-S3WD是次優的分類算法。在高度不平衡數據集中，少數類樣本數量有限，傳統集成框架下的分類算法學習少數類樣本的信息量較少，導致分類精度偏低，分析算法的分類結果可以發現，MGE-S3WD更擅長高度不平衡數據的分類問題。

標準差是衡量算法穩定性的重要指標，標準差越低則算法的穩定性越好，反之穩定性越差。通過圖2中各數據集上標準差均值可以看出，本文算法在不平衡數據集上的整體穩定性明顯優于其他3類集成分類算法。

Figure 2 Classification G-mean standard deviation of each algorithm圖2 各算法分類G-mean標準差均值

F-measure1是衡量不平衡數據分類算法性能的重要指標，與G-mean值不同的是，F-measure1指準確率(P)與召回率(R)之間的關系，從式(15)可以看出，準確率與召回率是兩組互相矛盾的指標，當準確率較高時，F-measure1值有可能偏低。

(15)

準確率P=TP/(TP+FP)，召回率R=TP/(TP+FN)，其中TP為少數類樣本正確分類的樣本數目，FN為少數類樣本錯誤分類的樣本數目，TN為多數類樣本正確分類的樣本數目，FP為多數類樣本錯誤分類的樣本數目。

分析表4中各分類算法的F-measure1值可以看出，在glass1、glass2、glass4、haberman、new-thyroid1、newthyroid2、poker-8-9_vs_5、vehicle1、yeast4、yeast5 10個數據集上，MGE-S3WD的F-measure1值優于其他3種集成分類算法；而其他數據集上不同集成分類算法各有優勢，對比各類算法的G-mean值可以看出，在部分數據集上，當G-mean值較高時，F-measure1值偏低。

通過分析圖3中各分類算法的F-measure1值標準差均值可以得出，在F-measure1評價指標下，MGE-S3WD算法的標準差明顯優于其他3種集成分類算法，因此，從算法的穩定性而言，MGE-S3WD算法優于其他3類集成分類算法。

運算時間是評價算法運算效率的重要指標，時間越短，算法的計算效率越高，圖4是各數據集上各算法的運算時間，單位為秒。分析圖4中數據可以看出，RF的運算時間最短，其主要原因是，其余3種算法在數據預處理過程消耗的時間較長，而RF在預處理階段只進行采樣，不需要更多的計算，因此，RF的運算效率高于其他3種集成分類算法。雖然MGE-S3WD算法的計算時間長于其他分類算法，但該算法能夠有效提升模型分類精度和穩定性，因此，犧牲少量運算效率提升模型的分類精度和穩定性是值得的。

Table 4 Classification F-measure1of each algorithm表4 各算法分類F-measure1值

Figure 3 Classification F-measure1 standard deviation of each algorithm圖3 各算法分類F-measure1標準差

Figure 4 Classification operation time of each algorithm圖4 各算法分類運算時間

綜合分析各算法的G-mean、F-measure1及算法運算時間可以得出，MGE-S3WD在處理高度不平衡數據時，算法的分類精度和穩定性明顯優于其他3種集成分類算法。但是，在部分不平衡比較低數據集上，該算法不能很好地劃分正域、邊界域和負域，導致集成學習的基分類器差異性較差，因此，從分類算法在各數據集上的總體分類精度而言，該算法低于隨機森林算法(RF)2%左右。從穩定性而言，該算法的穩定性明顯優于其他3種集成分類算法，因此，針對不平衡比較低的數據集，可以通過犧牲少量分類精度來提升模型的穩定性。如果需要較高F-measure1值，則建議選擇隨機森林算法，但隨機森林算法的隨機性較強，穩定性較差。如果需要較高的運算效率，建議選擇RSboost集成分類算法，該算法在小規模數據集上，運算效率較高，隨著數據集數據規模的增大，隨機子空間劃分時間越長，因此，當處理較大規模數據時，建議選擇隨機森林算法或Stacking集成分類算法。

5 結束語

不平衡數據的分類問題在數據挖掘領域備受關注，傳統集成分類算法并未對數據進行有效的預處理，數據集不同的分布情況對集成分類算法精度影響較大。本文采用序貫三支決策的多粒度集成分類算法可以有效降低數據子集的不平衡比，提升基分類器差異性，避免分類模型過擬合。實驗結果表明，該算法能夠有效識別少數類樣本，提升算法分類精度，尤其是針對高度不平衡數據提升效果更明顯。該算法通過引入代價敏感序貫三支決策的思想對數據進行預處理，將各粒層空間劃分為正域、邊界域和負域，并將各區域有規律地組合，形成新的數據子集，提高了集成分類算法的分類精度和穩定性。該算法粒化時間較長，因此，如何提升運算效率是未來的研究方向。