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 unnecessary large number of classifiers, which entails an increase in memory storage, computational cost, and even a reduction of 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 the problem of ensemble selection as a coalitional game in a graph form, and name the approach ISCG-Ranking. 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 several state-of-the-art techniques on 26 UCI benchmark datasets. The results reveal that ISCG-Ranking significantly improves the original ensemble and performs better than other methods in most cases.