Banzhaf Random Forests
  Random forests are a type of ensemble method which makes predictions by
combining the results of several independent trees. However, the theory of
random forests has long been outpaced by their application. In this paper, we
propose a novel random forests algorithm based on cooperative game theory.
Banzhaf power index is employed to evaluate the power of each feature by
traversing possible feature coalitions. Unlike the previously used information
gain rate of information theory, which simply chooses the most informative
feature, the Banzhaf power index can be considered as a metric of the
importance of each feature on the dependency among a group of features. More
importantly, we have proved the consistency of the proposed algorithm, named
Banzhaf random forests (BRF). This theoretical analysis takes a step towards
narrowing the gap between the theory and practice of random forests for
classification problems. Experiments on several UCI benchmark data sets show
that BRF is competitive with state-of-the-art classifiers and dramatically
outperforms previous consistent random forests. Particularly, it is much more
efficient than previous consistent random forests.
