Understanding Random Forests: From Theory to Practice

Abstraction: Random forests theory, variable importances, and fast scikit-learn implementation

Key points:

• Random forests reduce high variance of single decision trees by averaging M randomized trees; as M→∞ variance approaches ρ(x)σ², where ρ is inter-tree correlation
• MDI (mean decrease in impurity) variable importance provides a three-level decomposition of mutual information: per-variable, per-degree of interaction, per-interaction term (Louppe et al., 2013)
• MDI biases: relevant variables may get zero importance (masking); high-cardinality variables are favored with finite data; can be corrected by limiting tree depth
• scikit-learn Random Forest ~203s fit time vs Weka ~1028s and R randomForest ~13427s on the same benchmark; uses Python + Cython (~3000 lines Cython)
• Extra-Trees algorithm (random threshold selection) further reduces complexity from Θ(MKN log²N) to Θ(MKN log N)
• Random Patches subsampling: training on small random subsets of samples and features reduces memory and time with minimal accuracy loss

Connections: Scikit Learn · Random Forests · Decision Trees · Bias Variance Tradeoff · Variable Importance

Source: http://www.slideshare.net/glouppe/understanding-random-forests-from-theory-to-practice