Classification and regression tree

A classification and regression tree recursively splits covariate space into axis-aligned regions and assigns a constant prediction to each terminal region.

Recursive partitioning repeatedly selects a split of one current region, then applies the same splitting rule independently to the resulting child regions.

For class proportions $p_1,\dots ,p_K$ in a tree node, Gini impurity is $1-{\sum }_k{p}_k^2$. For two classes it is twice $p(1-p)$; omitting the constant factor does not change the selected split.

A random forest aggregates deeply grown decision trees fitted to bootstrap samples, while restricting each split to a random subset of predictor coordinates. Classification uses a majority vote over the trees.

The out-of-bag error predicts each training observation using only trees whose bootstrap samples omitted it, then averages the resulting losses.