An efficient ensemble pruning approach based on simple coalitional games

A novel methodology for pruning an ensemble of learning models is proposed.The new technique uses Banzhaf power index and minimal winning coalition concepts.A new representation for non-monotonic simple coalitional games is introduced.A pseudo-polynomial time algorithm for computing Banzhaf power index is provided.The new approach efficiency is shown through extensive experiments on 58 datasets. We propose a novel ensemble pruning methodology using non-monotone Simple Coalitional Games, termed SCG-Pruning. Our main contribution is two-fold: (1) Evaluate the diversity contribution of a classifier based on Banzhaf power index. (2) Define the pruned ensemble as the minimal winning coalition made of the members that together exhibit moderate diversity. We also provide a new formulation of Banzhaf power index for the proposed game using weighted voting games. To demonstrate the validity and the effectiveness of the proposed methodology, we performed extensive statistical comparisons with several ensemble pruning techniques based on 58 UCI benchmark datasets. The results indicate that SCG-Pruning outperforms both the original ensemble and some major state-of-the-art selection approaches.