Researches About Ensemble Pruning Measures And A GRASP Based Pruning Algorithm

Ensemble selection, which aims to select a proper subset of the original whole ensemble, can beseen as a combinatorial optimization problem, and usually can achieve a pruned ensemble with betterperformance than the original one. Ensemble selection by greedy methods has drawn a lot ofattentions and many greedy ensemble selection algorithms have been proposed recently, many ofwhich focus on the design of a new evaluation measure, or on the study about the effection ofdifferent search directions. And it is well accepted that diversity plays a crucial role in ensembleselection methods. Many evaluation measures based on diversity have been proposed and haveachieved a good success.Diversity and accuracy are two important properties of an ensemble. However, existing ensemblepruning methods always consider diversity and accuracy separately, while ignore the counterpart。Inour opinion they closely interrelate with each other, and should be considered simultaneously.Accordingly, three new evaluation measures, i.e., Simultaneous Diversity&Accuracy (SDAcc),Diversity-Focused-Two (DFTwo) and Accuracy-Reinforcement (AccRein), are developed for pruningthe ensemble by greedy ensemble pruning algorithm.Our motivation for SDAcc is to simultaneously consider both diversity and accuracy of thesubensemble and candidate classifier. With SDAcc, we do not give up those difficult samples in orderto further improve the generalization performance of the ensemble. Our inspiration ofDiversity-Focused-Two (DFTwo), stems from the notion that ensemble diversity attaches moreimportance to the difference among the classifiers in an ensemble. Finally, the proposal ofAccuracy-Reinforcement (AccRein) reinforces the concern about ensemble accuracy, in comparisonto DFTwo. Extensive experiments demonstrate that the proposed three pruning measures areboth efficient and effective.Most of the existing researches have neglected the substantial local optimal problem of greedymethods, which is just the central issue addressed in this paper, where a new Ensemble Selection(GraspEnS) algorithm based on Greedy Randomized Adaptive Search Procedure (GRASP) isproposed. The typical greedy ensemble selection approach is improved by the random factorincorporated into GraspEnS. Moreover, the GraspEnS algorithm realizes multi-start searching andappropriately expands the search range of the typical greedy approaches. Experimental resultsdemonstrate that the newly devised GraspEnS algorithm is able to solve the problem of starting pointand search strategy in greedy ensemble pruning algorithm. Thus, the algorithm can partially solve thelocal minima problem greedy algorithm, and ultimately achieve better pruning performance comparedwith its competitors.