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.
@cite_29: A heuristic analysis is presented in this paper based on a simplified version of RF denoted RF0. The results from RF0 support the empirical results from RF. RF0 regression is consistent using a value of mtry that does not depend on the number of cases N The rate of convergence to the Bayes rule depends only on the number of strong variables and not on how many noise variables are also present.. This also implies consistency for the two class RF0 classification. The analysis also illuminates why RF is able to handle large numbers of input variables and what the role of mtry is.
Despite the successful applications of random forests in practice, the mathematical properties behind them have not been well understood. For example, the early theoretical work of @cite_29 , which is essentially based on mathematical heuristics, is not formalized to rigorous theory.