An optimal pruning algorithm of classifier ensembles: dynamic programming approach

In recent years, classifier ensemble techniques have drawn the attention of many researchers in the machine learning research community. The ultimate goal of these researches is to improve the accuracy of the ensemble compared to the individual classifiers. In this paper, a novel algorithm for building ensembles called dynamic programming-based ensemble design algorithm (DPED) is introduced and studied in detail. The underlying theory behind DPED is based on cooperative game theory in the first phase and applying a dynamic programming approach in the second phase. The main objective of DPED is to reduce the size of the ensemble while encouraging extra diversity in order to improve the accuracy. The performance of the DPED algorithm is compared empirically with the classical ensemble model and with a well-known algorithm called “the most diverse.” The experiments were carried out with 13 datasets from UCI and three ensemble models. Each ensemble model is constructed from 15 different base classifiers. The experimental results demonstrate that DPED outperforms the classical ensembles on all datasets in terms of both accuracy and size of the ensemble. Regarding the comparison with the most diverse algorithm, the number of selected classifiers by DPED across all datasets and all domains is less than or equal to the number selected by the most diverse algorithm. Experiment on blog spam dataset, for instance, shows that DPED provides an accuracy of 96.47 compared to 93.87 obtained by the most diverse using 40% training size. Finally, the experimental results verify the reliability, stability, and effectiveness of the proposed DPED algorithm.