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

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

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

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

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

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

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

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