# Reference for random forests

I would like to understand how do the Boruta package work. Could you suggest some references for the theoretical aspect of so-called random forests?

Below are two illustrative examples of why am I attracted by the Boruta algorithm.

First example:

> set.seed(666)
> # simulates data
> # y does not depend on x4
> # y depends on x1, x2, x3 only through x3
> x1 <- rnorm(50); x2 <- rnorm(50) ; x3 <- (x1+x2)^2; x4 <- rnorm(50)
> y <- x3+rnorm(50,0.1)
>
> # lm() only indicates x3 is "important"
> summary(lm(y~x1+x2+x3+x4))

Call:
lm(formula = y ~ x1 + x2 + x3 + x4)

Residuals:
Min      1Q  Median      3Q     Max
-3.0000 -0.7137  0.0352  0.7082  1.7918

Coefficients:
Estimate Std. Error t value Pr(>|t|)
(Intercept)   0.1875     0.1874   1.000    0.323
x1           -0.1541     0.1469  -1.049    0.300
x2            0.1153     0.1949   0.591    0.557
x3            0.9097     0.0501  18.160   <2e-16 ***
x4            0.1263     0.1518   0.832    0.410
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 1.123 on 45 degrees of freedom
Multiple R-squared: 0.9013,     Adjusted R-squared: 0.8925
F-statistic: 102.7 on 4 and 45 DF,  p-value: < 2.2e-16

> # Boruta indicates x1, x2, x3 are important
> Boruta(y~x1+x2+x3+x4, maxRuns=500)
Boruta performed 174 randomForest runs in 10.409 secs.
3 attributes confirmed important: x1 x2 x3
1 attributes confirmed unimportant: x4


Second example:

> set.seed(421)
> # simulates data
> # y does not depend on u1
> # y does not depend on u2
> # but y depends on u1+u2
> nsims <- 100
> u1 <- runif(nsims)
> u2 <- runif(nsims)
> x <- (u1+u2)-floor(u1+u2)
> y <- rnorm(nsims, x,.05)
>
> # lm() does not detect some dependence
> summary(fit <- lm(y~u1))

Call:
lm(formula = y ~ u1)

Residuals:
Min      1Q  Median      3Q     Max
-0.5411 -0.2234  0.0005  0.2197  0.4901

Coefficients:
Estimate Std. Error t value Pr(>|t|)
(Intercept)  0.55721    0.05902   9.442 1.97e-15 ***
u1          -0.07858    0.09714  -0.809    0.421
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 0.2668 on 98 degrees of freedom
Multiple R-squared: 0.006633,   Adjusted R-squared: -0.003503
F-statistic: 0.6544 on 1 and 98 DF,  p-value: 0.4205

> summary(fit <- lm(y~u2))

Call:
lm(formula = y ~ u2)

Residuals:
Min       1Q   Median       3Q      Max
-0.53996 -0.21855  0.01298  0.22406  0.49940

Coefficients:
Estimate Std. Error t value Pr(>|t|)
(Intercept)  0.47022    0.05124   9.178 7.38e-15 ***
u2           0.09435    0.09298   1.015    0.313
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 0.2663 on 98 degrees of freedom
Multiple R-squared: 0.0104,     Adjusted R-squared: 0.000299
F-statistic:  1.03 on 1 and 98 DF,  p-value: 0.3127

> summary(fit <- lm(y~u1+u2))

Call:
lm(formula = y ~ u1 + u2)

Residuals:
Min       1Q   Median       3Q      Max
-0.53400 -0.22071  0.00699  0.21612  0.54375

Coefficients:
Estimate Std. Error t value Pr(>|t|)
(Intercept)  0.51609    0.06840   7.545 2.45e-11 ***
u1          -0.09978    0.09859  -1.012    0.314
u2           0.11176    0.09455   1.182    0.240
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 0.2663 on 97 degrees of freedom
Multiple R-squared: 0.02074,    Adjusted R-squared: 0.0005478
F-statistic: 1.027 on 2 and 97 DF,  p-value: 0.3619

>
> # Boruta() does
> Boruta(y~u1)
Boruta performed 44 randomForest runs in 6.328125 secs.
No attributes has been deemed important
1 attributes confirmed unimportant: u1
> Boruta(y~u2)
Boruta performed 20 randomForest runs in 2.8125 secs.
No attributes has been deemed important
1 attributes confirmed unimportant: u2
> Boruta(y~u1+u2)
Boruta performed 48 randomForest runs in 6.796875 secs.
2 attributes confirmed important: u1 u2
No attributes has been deemed unimportant

• I would say this question has to do with so called "all relevant feature selection" algorithm, not RF per se, so that you might want to think of a more informative title for your question. BTW, you didn't tell us what the supplied R code is supposed to show, although it looks like it has to do with the significant $t$-values (LM) vs. selected features (Boruta). – chl Jan 27 '12 at 22:01
• Ok - I have just added some comments in the code as well as another example – Stéphane Laurent Feb 4 '12 at 8:33

Random forest is a machine learning algorithm proposed by Breiman in this paper (there is also a webpage about it). Its significant property is that it can calculate an importance measure for attributes showing more-less how they were useful for the model -- it is usually better than correlation with a decision or linear model coefficient significance since it can handle some nonlinearity and multiattribute interactions without blowing the roof with overfitting or combinatorical explosion, but it is obviously far from perfectly recreating underlying Bayes net.

Now, this measure works quite well as a ranking of features, but it is not a complete answer for neither of feature selection problems -- one needs some cutoff to select minimal optimal (i.e. set of attributes on which model works best) and all relevant sets (i.e. set of attributes which are objectively connected to the decision).

Minimal optimal problem is usually quite easy and can be done with recursive feature elimination or (even better) with some regularization-supporting algorithm.

On the other hand, all relevant problem is very pesky and usually requires some explicit or implicit contrast attributes to obtain the importance threshold and some stabilization and "robustization" of importance measure -- Boruta is one of the RF wrapper algorithms trying to do this by extending the data set with artificial random attributes and iterating RF training progressively purging attributes claimed unimportant.

Note: there are of course non-RF based methods to deal with both feature selection problems, either using other importance sources, adding feature selection to internal optimization of the model or simply performing some more or less complex correlation tests between attributes and decision. For some more ramblings about this topic, you can skim this preprint.
For this two-problems-Bayes-net vision of feature selection, see this paper.

• +1, nice, clear & informative. @StéphaneLaurent, if you think this answers the question you had, you should click the check mark next to it. – gung - Reinstate Monica Jan 29 '12 at 21:40
• Sorry I do not see where is the check mark ? – Stéphane Laurent Jan 31 '12 at 13:26
• ok - now I see :) – Stéphane Laurent Feb 3 '12 at 20:36
• Unfortunately, the notes on Breiman and Cutler's webpage assume the user knows about the construction of single classification trees... and I don't know :( Does anybody know a document with more mathematical definitions ? – Stéphane Laurent Feb 25 '12 at 8:34