一種基于置換的組合分類器剪枝方法

，

(信陽師范學(xué)院，河南 信陽 464000)

在過去的十幾年里，組合分類方法研究一直是機器學(xué)習(xí)和數(shù)據(jù)挖掘中熱門的研究領(lǐng)域。給定相同的訓(xùn)練信息，組合分類器往往比單個分類器表現(xiàn)出更好的泛化能力，這是因為其創(chuàng)建有差異且具備高準(zhǔn)確率的基分類器。

構(gòu)建有差異且具備高準(zhǔn)確率組合分類器的方法有很多。例如，通過抽樣為每個基分類器構(gòu)建有差異的訓(xùn)練集；通過操縱特征基將訓(xùn)練集映射到不同的特征空間，進而為基分類器構(gòu)建不同的訓(xùn)練集(如COPEN[1])；通過操縱算法的參數(shù)或結(jié)構(gòu)從而構(gòu)建準(zhǔn)確且有差異的組合分類器。

然而，大部分組合分類器的方法存在一個共同的問題：傾向于構(gòu)建大量的基分類器，這樣不但需要大量的存儲空間，而且增加了組合分類器的預(yù)測響應(yīng)時間。在一些實際應(yīng)用(如數(shù)據(jù)流)中，最小化運行時間是至關(guān)重要的。組合剪枝(組合選擇，組合瘦身)是處理該問題的一種有效方法，即選擇全部基分類器的一個子集作為子組合分類器，用于預(yù)測未知樣例[2-6]。

本文將置換策略引入組合分類器剪枝問題中，進而提出了基于基分類器置換的組合分類器剪枝方法(EPR，Ensemble Pruning via base-classifier Replacement)。同時，使用差異性方法分析了EPR的性質(zhì)，基于該性質(zhì)，提出了一種基于差異性的度量指標(biāo)(Diversity-based Measure)以評估分類器相對于組合分類器的重要性，進而用該度量指標(biāo)指導(dǎo)EPR搜索最優(yōu)或次優(yōu)目標(biāo)。

1 問題定義及算法基本思想

設(shè)H={h1,h2,…,hM}是一個包含M個成員的組合分類器，所要考慮的問題是：如何從H中選擇子組合分類器S，使得|S|<

本文使用基于置換策略的貪心方法剪枝組合分類器。用H中的成員初始化子組合分類器S為預(yù)定義大小，然后迭代地用較好的基分類器置換S中最差的基分類器，直到置換不能進行，其核心是設(shè)計有效的度量指標(biāo)評估一個分類器相對于組合分類器的重要性。

2 EPR的相關(guān)性質(zhì)分析

本文采用由Ho提出的0/1差異性度量(0/1 loss-based disagreement measure)描述組合分類器成員間的配對差異性。其具體定義如下：

(1)

其中，N是實例集D的大小。

由定義1可知，分類器hi和hj間的差異性實質(zhì)上是hi和hj有且僅有一個分類器正確分類實例集D中的實例比例。

定義2 給定實例集D，分類器h對組合分類器S的差異性貢獻定義為h與S中所有的分類器差異性之和，即

(2)

定理1 定義2中分類器h對組合分類器S的差異性貢獻值也可寫為

(3)

定義3 組合分類器S的差異性(DivD(S))為S中每個分類器差異性貢獻之和，即

(4)

引理1 設(shè)h′S是一個基分類器，S′=S{h}∪{h′}是一個組合分類器，即：S′是由h′置換S中的h獲得的。如果ConDivD(h′,S′)>ConDivD(h,S)，那么，S′比S更優(yōu)越，即：DivD(S′) >DivD(S)。

其中,

(5)

類似地，我們可以證明

(6)

由S′=S{h}∪{h′}得

S′{h′}=S{h},S′{h′,hj}=S{h,hj}

(7)

組合式(5)、式(6)和式(7)得

DivD(S′)-DivD(S)=2(ConDivD(h′,S′)-

ConDivD(h,S))

(8)

故，Div(S′)>Div(S)如果ConDivD(h′,S′) >ConDivD(h,S)。

定理2 設(shè)h′?S是一個基分類器，設(shè)S′=S{h}∪{h′}是一個組合分類器，即：S′是由h′置換S中的分類器h獲得。那么，式(9)成立

DivD(S′)∝ConDivD(h′,S{h})-ConDivD(h,S{h})

(9)

證明：由引理1中的等式(8)得

DivD(S′)=

DivD(S)+2(ConDivD(h′,S′)-ConDivD(h,S))=

DivD(S)+2(ConDivD(h′,S′{h})-

ConDivD(h,S{h}))

(10)

由式(10)和已知條件S′=S{h}∪{h′}可以看出，式(9)成立。

定理2表明，在空間{S′|S′=S{h}∪{h′},h∈S}中搜索具有最大差異性的最優(yōu)子組合分類器S′，等價于在S中搜索分類器h∈S，使得式(9)右項最大。還可用式(11)選擇候選分類器h作為被h′置換的對象,以確保DivD(S′)最大。如果h=h′，則置換不會發(fā)生。

(11)

3 基于差異的度量指標(biāo)

根據(jù)定理1和定理2，這里設(shè)計了一個基于差異的度量指標(biāo)。根據(jù)定理2和式(11)，定義h被h′置換時的貢獻增益(Contribution Gain，CG)為

CGDpr(h′,h)=ConDpr(h′,S{h})-ConDpr(h,S{h})

(12)

其中，Dpr為剪枝集;ConDpr(h,S)表示基分類器h對組合分類器S的貢獻，定義為

(13)

EPR用式(14)選擇分類器h作為候選被h′置換，如果h=h′，則置換不發(fā)生，其中式(14)是由式(11)和(12)演化而來的。

(14)

4 實 驗

4.1 數(shù)據(jù)集及實驗設(shè)置

從UCI數(shù)據(jù)庫中隨機選取24個實例集，它們的細(xì)節(jié)描述見表1。對于每個實例集，執(zhí)行一次10折交叉驗證：將每個實例集隨機地劃分為10個不相交的子集。對于每個子集，其他9個子集被當(dāng)作訓(xùn)練集，該子集用來測試集評估算法的性能。對于每次試驗，使用bagging建立包含200個基分類器的分類器庫，其中，基分類器由剪枝C4.5建立。

本文設(shè)計了2組實驗：第一組實驗評估CG的性能；第二組實驗評估EPR的性能。對于第一組實驗，選擇CG、IC[7]、UWA[8]以及COM[9]監(jiān)督EPR的搜索過程(分別表示為EPR-CG、EPR-IC、EPR-UWA以及EPR-COM)。對于第二組實驗，將EPR與基于向前選擇和向后移除的組合分類器剪枝方法相比較，其中，CG和IC被選為候選指標(biāo)監(jiān)督搜索過程。為了便于說明，令F-*(B-*)表示向前(向后)組合分類器剪枝方法，其中“*”表示度量指標(biāo)。例如，F(xiàn)-CG(B-CG)表示使用度量指標(biāo)CG監(jiān)督向前(向后)組合分類器剪枝方法。

4.2 實驗結(jié)果

4.2.1 第一組實驗

本實驗分析了指標(biāo)CG的性能。相關(guān)的結(jié)果如表2所示，其中，粗體表示相應(yīng)的算法在相應(yīng)的實例集上準(zhǔn)確率最高。為了清晰，表2省略了算法在相應(yīng)實例集上的標(biāo)準(zhǔn)差。作為參照，表2給出了bagging(分類器庫)的準(zhǔn)確率。

表1 24個實例集的具體信息描述

由表2可知：

(1)EPR-CG可以大幅度降低組合分類器的規(guī)模，并能有效地提高原組合分類器性能(本實驗有20個實例集顯著提高了組合分類器的準(zhǔn)確率)；

(2)相比于其他指標(biāo)，CG更適合監(jiān)督EPR剪枝的過程。具體地，EPR-CG在絕大部分實例集上較高的準(zhǔn)確率數(shù)為14個，其他依次是EPR-IC 5個、EPR-UWA 5個、EPR-CON 2個和bagging 1個。它們的平均準(zhǔn)確率分別為86.86%、86.75%、86.65%、86.26%和86.27%。EPR總體上能有效地提高組合分類器的分類準(zhǔn)確率。

表 2 算法在24個實例集的平均準(zhǔn)確率

根據(jù)文獻[9]，當(dāng)比較兩個或多個算法時,比較它們在每個實例集上的序(rank)以及在所有實例集上的平均序(average rank across all data sets)。在一個實例集上，準(zhǔn)確率最高的分類器的序為1.0，準(zhǔn)確率次高的分類器的序為2.0，以此類推。算法在每個實例上的序如表3所示。

表3的內(nèi)容進一步證實了上面的結(jié)論，即EPR方法能有效地提高組合分類器的性能；較之于其他度量標(biāo)準(zhǔn)，CG更適于監(jiān)督EPR剪枝組合分類器。具體情況是，EPR-CG以1.75的平均序排名第一位，緊隨其后的算法依次是EPR-IC，EPR-UWA和EPR-CON，它們的平均序分別為2.71，2.73和3.60，Bagging以4.08的平均序落到了最后一位。

4.2.2 第二組實驗

本實驗比較了EPR與向前、向后組合分類器剪枝算法性能，使用度量指標(biāo)CG與IC作為代表，監(jiān)督EPR搜索子組合分類器空間。相關(guān)結(jié)果如表4和表5所示，其中，表4為EPR-CG、F-CG和B-CG在每個實例集上平均準(zhǔn)確率和序，表5為EPR-IC、F-IC

表3 算法在每個實例集上的序

和B-IC在每個實例集上的平均準(zhǔn)確率和序。粗體表示相應(yīng)算法在相應(yīng)實例集上具有最高的準(zhǔn)確率。

直覺上，EPR-*、F-*及B-*性能相當(dāng)，因為這些剪枝方法的思想類似(都是貪心組合分類器剪枝方法)。事實上，表4和表5結(jié)果驗證了該直覺：不管度量指標(biāo)是CG還是IC，這3種算法在每個實例集上準(zhǔn)確率差異都較小。

從表4和表5還可以看出，盡管這幾種方法準(zhǔn)確率差異不大，但是，在大部分實例集上，EPR算法略優(yōu)于其他2種算法。當(dāng)CG作為度量指標(biāo)時，EPR在19個實例集上準(zhǔn)確率較高，其他依次是F-CG為9個和B-CG為6個，它們的平均序為：EPR-CG 為1.44、F-CG為2.27和B-CG為2.29。在表4中，EPR-IC在18個實例集上準(zhǔn)確率較高，其他依次是F-IC為 7個和B-IC為5個。它們的平均序為：EPR-IC為1.46、B-IC為2.21和F-IC為2.33。該結(jié)果表明，相比于其他高級組合分類器剪枝方法，EPR能尋找到準(zhǔn)確率更高的子組合分類器。

另外，仔細(xì)觀察表4和表5可知，基于向前選擇的組合分類器剪枝方法與基于向后移除的組合分類器剪枝方法性能相當(dāng)。

綜上說述：

(1)不管采用上述哪種指標(biāo)監(jiān)督EPR搜索過程，EPR總能顯著降低組合分類器規(guī)模并有效提高它的泛化能力；

表 4 算法EPR-CG、F-CG和B-CG在每個實例集上的平均準(zhǔn)確率和序

表5 算法EPR-IC、F-IC和B-IC在每個實例集上的平均準(zhǔn)確率和序

(2)本文設(shè)計的基于差異性的指標(biāo)較適于監(jiān)督EPR搜索過程；

(3)較之于其他高級組合分類器剪枝方法，EPR略顯優(yōu)勢。

5 結(jié) 語

本文提出了一種EPR組合分類器剪枝方法。它利用置換方法搜索最優(yōu)或次優(yōu)子組合分類器。為了評估基分類器對組合分類器的貢獻，使用差異性度量理論分析了EPR的性質(zhì)，根據(jù)該性質(zhì)，設(shè)計了一個基于差異性的度量指標(biāo)，監(jiān)督EPR搜索子組合分類空間。

有很多指標(biāo)可用于監(jiān)督組合分類器剪枝過程，因此將這些指標(biāo)用于指導(dǎo)EPR搜索子組合分類器是未來值得研究的一項工作。

參考文獻:

[1] Zhang D, Chen S, Zhou Z H,et al.Constraint Projections for Ensemble Learning[C]//Proceedings of the 23rd AAAI Conference on Artificial Intelligence (AAAI’08).Quebec:AAAI Press，2008: 758-763.

[2] Partalas I, Tsoumakas G, Vlahavas I P.An Ensemble Pruning Primer[C]//Applications of Supervised and Unsupervised Ensemble Methods.Berlin: Springer, 2009: 1-13.

[3] Li N, Yu Y, Zhou Z H.Diversity Regularized Ensemble Pruning[C]//Flach P A , Bie T D, Cristianini N, et al.Proceedings of European Conference on Machine Learning and Knowledge Discovery in Databases.Berlin:Springer, 2012: 330-345.

[4] Tamon C, Xiang J.On the Boosting Pruning Problem[C]//Proceedings of the 11th European Conference on Machine Learning.Berlin:Springer, 2000: 404-412.

[5] Xu L L, Li B, Chen E H.Ensemble Pruning via Constrained Eigen-Optimization[C]//Proceedings of the 12th IEEE International Conference on Data Mining.Los Alamitos:IEEE Press, 2012: 715-724.

[6] Guo L, Boukir S.Margin-based Ordered Aggregation for Ensemble Pruning[J].Pattern Recognition Letters, 2013, 34: 603-609.

[7] Lu Z, Wu X D, Zhu X Q, et al.Ensemble Pruning Via Individual Contribution Ordering[C]//Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.NY:ACM New York, 2010: 871-880.

[8] Partalas I, Tsoumakas G, Vlahavas I P.An Ensemble Uncertainty Aware Measure for Directed Hill Climbing Ensemble Pruning[J].Machine Learning, 2010, 81(3): 257—282.

[9] Banfield R E, Hall L O, Bowyer K W, et al.Ensemble Diversity Measures and Their Application to Thinning[J].Information Fusion, 2005, 6(1): 49-62.

[10] Demsar J.Statistical Comparisons of Classers over Multiple Data Sets[J].Journal of Machine Learning Research, 2006(7): 1-30.