Bagged random-forest construction on a fixed finite sample

Fix training data $D=((x_i,y_i){)}_{i=1}^n$ with $n\ge 1$, features $x_i\in {\mathbb{R}}^p$ with $p\ge 1$, and one response mode: regression with $y_i\in \mathbb{R}$, or classification with labels in a fixed ordered finite set $\mathcal{C}=\{c_1<\cdots <c_J\}$, $J\ge 1$. Choose a finite integer depth cap $d_{\max }\ge 0$, an integer tree count $B\ge 1$, and a feature count $m\in \{1,\dots ,p\}$. Choosing $m=p$ disables feature randomization.

For every tree index $b\in \{1,\dots ,B\}$, draw $n$ independent uniform indices $I_{b1},\dots ,I_{bn}$ from $\{1,\dots ,n\}$ and put $N_{bi}=\mathrm{\mid }\{r:I_{br}=i\}\mathrm{\mid }$. For every possible binary node address $\nu$ of depth less than $d_{\max }$, draw a subset $M_{b,\nu }$ uniformly from the $m$-element subsets of $\{1,\dots ,p\}$. All bootstrap-index and feature-subset draws are mutually independent across trees, index positions, and node addresses. Write ${\mathrm{\Theta }}_b=(N_{b1},\dots ,N_{bn},(M_{b,\nu }{)}_{\nu })$; thus the ${\mathrm{\Theta }}_b$ are independent with a common law conditional on the fixed data and chosen settings.

At a node with bootstrap position set $I$, define ${\bar{y}}_I=\mathrm{\mid }I{\mathrm{\mid }}^{-1}{\sum }_{r\in I}{y}_{I_{br}}$ in regression. In classification define $q_{Ik}=\mathrm{\mid }I{\mathrm{\mid }}^{-1}\mathrm{\mid }\{r\in I:y_{I_{br}}=c_k\}\mathrm{\mid }$ and choose one fixed impurity, either misclassification $1-{\max }_k{q}_{Ik}$, Gini $1-{\sum }_k{q}_{Ik}^2$, or entropy $-{\sum }_k{q}_{Ik}\log q_{Ik}$, with $0\log 0=0$.

For tree $b$, write the resampled rows as $D_b^{\ast }=((x_{I_{br}},y_{I_{br}}){)}_{r=1}^n$, so bootstrap positions remain distinct even when they contain the same original row. Build $T_b$ from $D_b^{\ast }$, starting at the root with position set $I=\{1,\dots ,n\}$. At a node of depth $d<d_{\max }$, form the candidate midpoint thresholds between consecutive distinct observed values using the coordinates in that node's set $M_{b,\nu }$. A candidate at coordinate $j$ and threshold $t$ partitions the current bootstrap positions into $I_L=\{r\in I:x_{I_{br},j}\le t\}$ and $I_R=\{r\in I:x_{I_{br},j}>t\}$; only candidates with both children nonempty are used. Score each candidate by ${\sum }_{r\in I_L}(y_{I_{br}}-{\bar{y}}_{I_L}{)}^2+{\sum }_{r\in I_R}(y_{I_{br}}-{\bar{y}}_{I_R}{)}^2$ in regression or by $\mathrm{\mid }{I}_L\mathrm{\mid }{Q}_{I_L}+\mathrm{\mid }{I}_R\mathrm{\mid }{Q}_{I_R}$ in classification, where $Q$ is the chosen impurity. Select a candidate of least score, breaking ties by coordinate index and then cut index, and recurse on its two children. If $d=d_{\max }$ or there is no candidate, make the node a leaf. When $m=p$, this is the greedy CART growth procedure on the bootstrap sample; when $m<p$, the same procedure restricts each node's candidate coordinates to its sampled subset. Each regression leaf predicts its sample mean; each classification leaf predicts its most frequent class, choosing the least class index in a tie. Define $h(x,{\mathrm{\Theta }}_b)$ by following the unique tree path for $x$.

For regression, the finite-forest prediction is $B^{-1}{\sum }_{b=1}^{B}h(x,{\mathrm{\Theta }}_b)$. For classification, it is the class receiving the largest number of votes, with the least class index breaking ties. For a training observation $i$, let $O_i=\{b:N_{bi}=0\}$. Its out-of-bag prediction is formed using only trees indexed by $O_i$, with the same regression average or classification vote rule; if $O_i=\mathrm{\varnothing }$, no out-of-bag prediction is returned. An out-of-bag prediction is a diagnostic computed from this finite forest, not an exact identity for its full-forest prediction or risk.

The data flow is shown below. The arrows mean that the same fixed $D$ and the independent randomization vector determine each tree, and the stated aggregation combines the resulting predictions; the diagram records the procedure and is not a proof of a performance claim.

Finite tree structure, leaf predictions, and classification impurities

Greedy CART split scores, midpoint candidates, and deterministic ties

Breiman, “Random Forests,” §§1, 3.1, and 11, printed pp. 5–7, 11, and 25–26

Hastie, Tibshirani, and Friedman, The Elements of Statistical Learning, §15.2, Algorithm 15.1, and §15.3.1, printed pp. 587–593