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.

A surrogate split uses another predictor to approximate the left-versus-right assignments made by a tree node's primary split. It can route observations whose primary predictor is missing. Surrogates are ranked by agreement with the primary split on observations where both predictors are known, accounting for trivial majority assignments. This differs from simply filling a missing predictor with its sample mean.

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.