Cost Complexity Pruning is a way to decide how much of the tree to use — how to select a small set of subtrees

Steps to calculating Cost Complexity Pruning:
1. Calculate total sum of squared residuals for each tree, often starting with the original then reducing by 1 leaf each time.
2. Calculate a Tree Score for each tree:
		$$ Tree Score = SSR + αT $$
   - Where αT is the tree complexity penalty — a function of how many leaves are in the given tree, which compensates for the difference in number of leaves between trees. 
   - alpha is the tuning parameter we find using cross validation and T is the Terminal, number of leaves.
3. Pick the tree with the lowest tree score


Cost Complexity Pruning

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.

University of Michigan - Ann Arbor

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

Building a regression tree

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

An Introduction to Statistical Learning with Applications in R

This video series goes into the fundamentals of machine learning.

[StatQuest with Josh Starmer]. (2020, February 21). Machine Learning [Video File]. Retrieved from [www.youtube.com/playlist?list=PLblh5JKOoLUICTaGLRoHQDuF_7q2GfuJF](https://www.youtube.com/playlist?list=PLblh5JKOoLUICTaGLRoHQDuF_7q2GfuJF) 

Learn Before

Related

Learn After