关键词: 森林剪枝,组合选择,贡献增益

Abstract: An ensemble consisting of decision trees can be treated as a forest．We proposed a new strategy called forest thinning to reduce the ensemble size and improve its accuracy．Unlike traditional decision tree pruning methods,forest thinning treats all decision trees in a forest as a whole and try to evaluate the performance influence on the ensemble when a certain branch is pruned．To determine which branches should be pruned,we proposed a new metric called contribution gain．The contribution gain of a subtree is related not only to the accuracy of the host tree,but also to the diversity of trees in the ensemble,so it reasonably well measures how much improvement of the ensemble accuracy can be achieved when a subtree is pruned．With the contribution gain,we designed a forest thinning algorithm named FTCG(Forest Thinning via Contribution Gain)．Our experiments show that forest thinning can significantly reduce forests structure complexity and improve their accuracy in most of data sets,no matter ensembles are constructed by a certain algorithm such as bagging,or obtained by an ensemble selection algorithm such as EPIC [1],no matter whether each decision tree is pruned or unpruned.

Key words: Forest thinning,Ensemble selection,Contribution gain