Tree pruning refers to the reduction of splits in the tree (simplifying the model) to reduce variance and result in more interpretable results.
Pruning a regression tree prevents overfitting the training data so the tree does a better job capturing the test data.

Tree pruning

1. Use recursive binary splitting to grow a large tree on the training data, stopping only when each terminal node has fewer than some minimum number of observations.
2. Apply cost complexity pruning to the large tree in order to obtain a sequence of best subtrees, as a function of α.
3. Use K-fold cross-validation to choose α. That is, divide the training observations into K folds. For each k = 1, . . . , K:
(a) Repeat Steps 1 and 2 on all but the kth fold of the training data. (b) Evaluate the mean squared prediction error on the data in the
left-out kth fold, as a function of α.
Average the results for each value of α, and pick α to minimize the
average error.

4. Return the subtree from Step 2 that corresponds to the chosen value

University of Michigan - Ann Arbor

The predictor space ($X_1, X_2, …, X_p$) is divided into J non-overlapping regions. Then make the same prediction for each observation that falls into the region $R_j$, and the predicted value is the mean of the response values for the training observations in $R_j$. The goal is to find the matrix region that minimizes the RSS of the model $\sum_{j=1}^{J} \sum_{i \in R_j} (y_i - \hat{y}_{R_j})^2$. 

Recursion Binary Splitting: from the top of the tree (*top-down*), the prediction space is split to two new branches, and the determination of the optimal (*best*) split is limited to a particular step instead of some future step. 

Cost Complexity pruning, as known as Weakest Link Pruning, is able to avoid overfitting. 
$$ \sum_{m=1}^{|T|} \sum_{i:x_i \in {R_m}} (y_i - \hat{y}_{R_m})^2 + \alpha |T| $$


Regression Tree

James, G., Witten, D., Hastie, T., & Tibshirani, R. (2013). An introduction to statistical learning (Vol. 112, pp. 3-7). New York: springer.

Learn Before

Related

Learn After