Towards an optimally pruned classifier ensemble

Ensemble pruning is an important area of research in multiple classifier systems. Reducing ensemble size, by selecting diverse and accurate classifiers from a given pool is a popular strategy to improve ensemble performance. In this paper, we present Accu-Prune (AP) algorithm, a majority voting ensemble that uses accuracy ordering and reduced error pruning approach to identify an optimal ensemble from a given pool of classifiers. At each step, the ensemble is extended by adding two lower accuracy classifiers, implicitly adding diversity to the ensemble. The proposed approach closely mimics the results of the Brute Force (BF) search for optimal ensemble, while reducing the search space drastically. We propose that quality of an ensemble is determined by two factors-size and accuracy. Ideally, smaller ensembles are qualitywise preferable over large ensembles with same accuracy. Based on this notion, we design a deficit function to quantify the quality differential between two arbitrary ensembles. The function examines the performance and size difference between two ensembles to quantify the quality differential. Experimentation has been carried out on 25 UCI datasets and AP algorithm has been compared with BF search and other pruning algorithms. The deficit function is used to compare AP with BF search and a well known pruning algorithm, EPIC. Relevant statistical tests reveal that the generalization capability of AP algorithm is better than forward search and backward elimination, comparable to BF search and slightly inferior to EPIC. EPIC ensembles being significantly large, the quality differential between AP and EPIC ensembles is not significant. Thus, for limited memory applications, with tolerance for small amount of error, AP ensembles may be more appropriate.