陳麗芳，代 琪，趙佳亮

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

1 引言

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

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

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

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

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

2 預備知識

2.1 序貫三支決策

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

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

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

(1)

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

由此可以得到一個n層的粒結(jié)構(gòu)，可以表示為：

GS=(GS1,GS2,…,GSn)

(2)

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

(3)

其中,GSi表示第i個粒結(jié)構(gòu)，Ui為粒結(jié)構(gòu)中的非空有限集，Ei為Ui中存在的等價關(guān)系，同樣，此處的Ci表示粒結(jié)構(gòu)中的條件屬性集。

在多層次粒結(jié)構(gòu)中，每一層屬性的選擇方式取決于動態(tài)決策任務的目標。在序貫三支決策中，對劃分到邊界域的對象，只有最后一層采用二支決策，其余粒層均采用三支決策。因此，需要根據(jù)實際情況，在每個粒層上分別設置合理的三支決策閾值[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。最終在最底層實現(xiàn)簡單的二支決策。

定義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的信息函數(shù)，Ci,1≤i≤n，是條件屬性子集，且滿足條件C1?C2?…?Cn?Cn+1=C。

2.2 集成學習

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

3 算法設計與模型構(gòu)建

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)數(shù)據(jù)集粒層劃分。

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

(8)

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

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

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

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

(9)

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

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

Table 1 Cost matrix表1 代價矩陣

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

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

(10)

(11)

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

(12)

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

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

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

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

算法1不平衡數(shù)據(jù)多粒度集成分類算法

輸出：測試集集成分類結(jié)果。

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 模型構(gòu)建

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

步驟1數(shù)據(jù)動態(tài)劃分。利用二元關(guān)系動態(tài)劃分數(shù)據(jù)集，構(gòu)建序貫三支決策粒化算法，科學地?；瘮?shù)據(jù)集，獲得不同的粒層空間Ω0,Ω1,…,Ωn。

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

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

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

(13)

樣本集S′的基尼系數(shù)為：

(14)

其中，|S′|表示集合S′的總樣本數(shù)，|Di|表示集合S′中屬于第i類的樣本數(shù)?；嶂笖?shù)表示集合S′的不確定性。

計算當前節(jié)點各特征值對數(shù)據(jù)子集Di的基尼系數(shù)。

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

4 仿真實驗與性能分析

4.1 數(shù)據(jù)集和仿真環(huán)境

基于Python實現(xiàn)算法仿真。系統(tǒng)環(huán)境：CPU：Intel i5-6500；RAM：8 GB；操作系統(tǒng)：Windows 10 專業(yè)版；解釋器：Python 3.7。

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

4.2 性能分析

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

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

Table 2 Data sets basic information表2 數(shù)據(jù)集基本信息

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

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

于其他算法，而MGE-S3WD是次優(yōu)的分類算法。在高度不平衡數(shù)據(jù)集中，少數(shù)類樣本數(shù)量有限，傳統(tǒng)集成框架下的分類算法學習少數(shù)類樣本的信息量較少，導致分類精度偏低，分析算法的分類結(jié)果可以發(fā)現(xiàn)，MGE-S3WD更擅長高度不平衡數(shù)據(jù)的分類問題。

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

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

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

(15)

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

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

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

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

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

5 結(jié)束語

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