Induced Subgraph Game for Ensemble Selection

Ensemble methodology has proved to be one of the strongest machine learning techniques. In spite of its huge success, most ensemble methods tend to generate unnecessarily large number of classifiers, which entails an increase in memory storage, computational cost, and even a reduction in the generalization performance of the ensemble. Ensemble selection addresses these shortcomings by searching for a fraction of individual classifiers that performs as good as, or better than the entire ensemble. In this paper, we formulate ensemble selection problem as a coalitional game played on a graph. The proposed game aims at capturing two crucial concepts that affect the performance of an ensemble: accuracy and diversity. Most importantly, it ranks every classifier based on its contribution in keeping a proper balance between these two notions using Shapley value. To demonstrate the validity and the effectiveness of the proposed approach, we carried out experimental comparisons with some major selection techniques based on 35 UCI benchmark datasets. The results reveal that our approach significantly improves the original ensemble and performs better than the other methods in terms of classification accuracy, pruning ratio, and computational cost.