Editing Random forest (section)

=== Variable importance ===

Random forests can be used to rank the importance of variables in a regression or classification problem in a natural way.  The following technique was described in Breiman's original paper<ref name=breiman2001/> and is implemented in the [[R (programming language)|R]] package <code>randomForest</code>.<ref name="rpackage">{{cite web |url=https://cran.r-project.org/web/packages/randomForest/randomForest.pdf |title=Documentation for R package randomForest |first1=Andy |last1=Liaw | name-list-style = vanc | date=16 October 2012 |access-date=15 March 2013}}
</ref>

==== Permutation importance ====

To measure a feature's importance in a data set <math>\mathcal{D}_n =\{(X_i, Y_i)\}_{i=1}^n</math>, first a random forest is trained on the data.  During training, the [[out-of-bag error]] for each data point is recorded and averaged over the forest. (If bagging is not used during training, we can instead compute errors on an independent test set.)

After training, the values of the feature are permuted in the out-of-bag samples and the out-of-bag error is again computed on this perturbed data set. The importance for the feature is computed by averaging the difference in out-of-bag error before and after the permutation over all trees.  The score is normalized by the standard deviation of these differences.

Features which produce large values for this score are ranked as more important than features which produce small values. The statistical definition of the variable importance measure was given and analyzed by Zhu ''et al.''<ref>{{cite journal | vauthors = Zhu R, Zeng D, Kosorok MR | title = Reinforcement Learning Trees | journal = Journal of the American Statistical Association | volume = 110 | issue = 512 | pages = 1770–1784 | date = 2015 | pmid = 26903687 | pmc = 4760114 | doi = 10.1080/01621459.2015.1036994 }}</ref>

This method of determining variable importance has some drawbacks:
* When features have different numbers of values, random forests favor features with more values. Solutions to this problem include [[partial permutation]]s<ref>{{cite conference | author=Deng, H.| author2=Runger, G. | author3=Tuv, E. | title=Bias of importance measures for multi-valued attributes and solutions | conference=Proceedings of the 21st International Conference on Artificial Neural Networks (ICANN) | year = 2011 | pages=293–300 | url = https://www.researchgate.net/publication/221079908 }}</ref><ref>{{cite journal | vauthors = Altmann A, Toloşi L, Sander O, Lengauer T | title = Permutation importance: a corrected feature importance measure | journal = Bioinformatics | volume = 26 | issue = 10 | pages = 1340–7 | date = May 2010 | pmid = 20385727 | doi = 10.1093/bioinformatics/btq134 | doi-access = free }}</ref><ref name=":02">{{Cite journal |last1=Piryonesi S. Madeh |last2=El-Diraby Tamer E. |date=2020-06-01 |title=Role of Data Analytics in Infrastructure Asset Management: Overcoming Data Size and Quality Problems |journal=Journal of Transportation Engineering, Part B: Pavements |volume=146 |issue=2 |page=04020022 |doi=10.1061/JPEODX.0000175 |s2cid=216485629}}</ref> and growing unbiased trees.<ref>{{cite journal | last1 = Strobl | first1 = Carolin | last2 = Boulesteix | first2 = Anne-Laure | last3 = Augustin | first3 = Thomas | name-list-style = vanc | title = Unbiased split selection for classification trees based on the Gini index | journal = Computational Statistics & Data Analysis | volume = 52 | year = 2007 | pages = 483–501 | url = https://epub.ub.uni-muenchen.de/1833/1/paper_464.pdf | doi = 10.1016/j.csda.2006.12.030 | citeseerx = 10.1.1.525.3178 }}</ref><ref>{{cite journal|last1=Painsky|first1=Amichai|last2=Rosset|first2=Saharon| name-list-style = vanc |title=Cross-Validated Variable Selection in Tree-Based Methods Improves Predictive Performance|journal=IEEE Transactions on Pattern Analysis and Machine Intelligence|date=2017|volume=39|issue=11|pages=2142–2153|doi=10.1109/tpami.2016.2636831|pmid=28114007|arxiv=1512.03444|s2cid=5381516}}</ref>
* If the data contain groups of correlated features of similar relevance, then smaller groups are favored over large groups.<ref>{{cite journal | vauthors = Tolosi L, Lengauer T | title = Classification with correlated features: unreliability of feature ranking and solutions | journal = Bioinformatics | volume = 27 | issue = 14 | pages = 1986–94 | date = July 2011 | pmid = 21576180 | doi = 10.1093/bioinformatics/btr300 | doi-access = free }}</ref>
* If there are collinear features, the procedure may fail to identify important features. A solution is to permute groups of correlated features together.<ref name=":2">{{Cite web |title=Beware Default Random Forest Importances |url=http://explained.ai/decision-tree-viz/index.html |access-date=2023-10-25 |website=explained.ai}}</ref>

==== Mean decrease in impurity feature importance ====
This approach to feature importance for random forests considers as important the variables which decrease a lot the impurity during splitting.<ref>{{Cite book |last=Ortiz-Posadas |first=Martha Refugio |url=https://books.google.com/books?id=d6LTDwAAQBAJ&dq=Mean+Decrease+in+Impurity+Feature+Importance&pg=PA116 |title=Pattern Recognition Techniques Applied to Biomedical Problems |date=2020-02-29 |publisher=Springer Nature |isbn=978-3-030-38021-2 |language=en}}</ref> It is described in the book ''Classification and Regression Trees'' by Leo Breiman<ref>{{Cite book |last=Breiman |first=Leo |url=https://www.taylorfrancis.com/books/mono/10.1201/9781315139470/classification-regression-trees-leo-breiman |title=Classification and Regression Trees |date=2017-10-25 |publisher=Routledge |isbn=978-1-315-13947-0 |location=New York |doi=10.1201/9781315139470}}</ref> and is the default implementation in [[Scikit-learn|<code>sci-kit learn</code>]] and [[R (programming language)|R]]. The definition is:<math display="block">\text{unormalized average importance}(x)=\frac{1}{n_T} \sum_{i=1}^{n_T} \sum_{\text{node }j \in T_i | \text{split variable}(j) = x} p_{T_i}(j)\Delta i_{T_i}(j),</math>where 

* <math>x</math> is a feature
* <math>n_T</math> is the number of trees in the forest
* <math>T_i</math> is tree <math>i</math>
* <math>p_{T_i}(j)=\frac{n_j}{n}</math> is the fraction of samples reaching node <math>j</math>
* <math>\Delta i_{T_i}(j)</math> is the change in impurity in tree <math>t</math> at node <math>j</math>.

As impurity measure for samples falling in a node e.g. the following statistics can be used:
*[[Entropy (information theory)|Entropy]]
*[[Gini coefficient]]
*[[Mean squared error]]

The normalized importance is then obtained by normalizing over all features, so that the sum of normalized feature importances is 1.

The <code>sci-kit learn</code> default implementation can report misleading feature importance:<ref name=":2" />
* it favors high cardinality features
* it uses training statistics and so does not reflect a feature's usefulness for predictions on a test set<ref>https://scikit-learn.org/stable/auto_examples/inspection/plot_permutation_importance.html 31. Aug. 2023</ref>