組合分類器剪枝方法的研究.pdf

1、組合分類器學(xué)習(xí)是機(jī)器學(xué)習(xí)、模式識別和數(shù)據(jù)挖掘中非常活躍的研究領(lǐng)域。已有的研究表明，給定相同的訓(xùn)練信息，組合分類器往往表現(xiàn)出比單個(gè)分類器更好的泛化能力。然而，大部分組合分類器學(xué)習(xí)方法都存在共同的問題:傾向于構(gòu)建大量基分類器模型。大量基分類器不僅需要大量存儲(chǔ)空間而且增加了組合分類器預(yù)測響應(yīng)時(shí)間。另外，在組合分類器中，某些基分類器不僅無助于提高組合分類器的泛化能力，而且還可能降低組合分類器的分類準(zhǔn)確率。組合分類器剪枝是處理該問題的一種有效方法

2、，受到了廣泛關(guān)注。
　　 組合分類器剪枝有兩種方法:一種方法是從給定的基分類器中選擇一個(gè)最優(yōu)或次最優(yōu)的子集，構(gòu)建組合分類器;另一種方法是從組合分類器整體考慮，直接對每個(gè)基分類器剪枝。關(guān)于基分類器的選擇，已經(jīng)提出了一些算法，但仍然需要進(jìn)一步研究，而第二種方法則很少有人涉及。由于兩種方法都面臨搜索指數(shù)級空間問題，因此窮舉搜索是計(jì)算不可行的。解決這些問題的關(guān)鍵是(1)構(gòu)建好的度量指標(biāo)，評估基分類器選擇和基分類器剪枝，指導(dǎo)搜索過程;(2

3、)尋找合適的選擇和剪枝方法。本文針對以上問題，研究組合分類器的剪枝，并進(jìn)一步把剪枝的思想融入基于決策樹的組合分類器的構(gòu)建中，直接構(gòu)建更有效的組合分類器。本文主要貢獻(xiàn)和創(chuàng)新點(diǎn)如下:
　　 1)提出了基于邊界的組合分類器剪枝方法。根據(jù)邊界理論，構(gòu)造了一種基于邊界的度量指標(biāo)(MBM，Margin-basedMeasure)用于評估基分類器相對于組合分類器的重要性。根據(jù)MBM，設(shè)計(jì)了一種基于邊界的貪心組合分類器剪枝算法(MBMEP，MB

4、M-basedEnsemblePruning)，以降低組合分類器規(guī)模并提高它的分類準(zhǔn)確率。實(shí)驗(yàn)結(jié)果表明:即使直接使用訓(xùn)練實(shí)例集作為剪枝集，MBMEP也能顯著地降低組合分類器的規(guī)模并提高它的分類準(zhǔn)確率;與已有的組合分類器剪枝方法相比，MBMEP在大部分?jǐn)?shù)據(jù)集上都具有更好的泛化性能。
　　 2)提出了基于置換策略的組合分類器剪枝方法(EPR，EnsemblePruningviabase-classifierReplacement)。

5、與傳統(tǒng)組合分類器剪枝方法不同，EPR初始化子組合分類器S為預(yù)定義大小，然后迭代地通過用較好的基分類器置換S中最差的基分類器，直到置換不能進(jìn)行。為了確定是否應(yīng)該進(jìn)行置換，本文提出一種基于差異性的度量指標(biāo)，用于度量基分類器對組合分類器的貢獻(xiàn)。實(shí)驗(yàn)結(jié)果表明，EPR能夠有效地降低組合分類器規(guī)模并提高它的泛化能力。
　　 3)提出了一種基于貢獻(xiàn)增益的森林剪枝方法FTCG(ForestTrimmingbasedonContributionG

6、ain)。基于決策樹的組合分類器可以被視為一個(gè)森林。與對每棵決策樹分別進(jìn)行剪枝的傳統(tǒng)剪枝方法不同，森林剪枝把所有的決策樹看作一個(gè)整體，更加關(guān)注剪掉決策樹的分枝對組合分類器性能的影響。為了確定森林的哪些分枝可以被剪枝，本文提出一種稱作貢獻(xiàn)增益的度量，評估剪掉決策樹的一棵子樹對組合分類器性能的影響。實(shí)驗(yàn)結(jié)果表明，無論森林是基于某種森林學(xué)習(xí)方法構(gòu)建的還是某種傳統(tǒng)組合分類器剪枝算法的結(jié)果，無論每棵決策樹是剪枝過的還是未剪枝的，F(xiàn)TCG都能進(jìn)一步

7、降低每棵決策樹的規(guī)模，并且在大部分?jǐn)?shù)據(jù)集上顯著地提高了的森林的分類準(zhǔn)確率。
　　 4)提出了一種新的基于決策樹的組合分類器學(xué)習(xí)方法FL(Forest Learning)。與bagging和adaboost等傳統(tǒng)的組合分類器學(xué)習(xí)算法不同，F(xiàn)L不采用抽樣或加權(quán)抽樣，而是直接在訓(xùn)練集上學(xué)習(xí)一個(gè)森林，作為組合分類器。首先，使用傳統(tǒng)的方法構(gòu)建森林的第一棵;然后，逐一構(gòu)建新的決策樹添加到森林中。在構(gòu)建新的決策樹時(shí)，結(jié)點(diǎn)的每次劃分都考慮對組合