Cost Complexity Pruning Quiz & Flashcards

Study Notes

The tuning parameter α controls the trade-off between subtree complexity and its fit to the training data.
When α = 0, the subtree T will simply equal T0.

Cost complexity pruning is a method to select a small set of subtrees for consideration.
It is also known as weakest link pruning.
The algorithm for cost complexity pruning involves:
- Growing a large tree using recursive binary splitting and stopping according to the stopping condition.
- Applying cost complexity pruning to obtain a sequence of best subtrees as a function of α.
- Using k-fold cross-validation to choose α.
- Returning the subtree that corresponds to the chosen value of α.

A classification tree is used to predict a qualitative response.
The classification error rate is the fraction of training observations in a region that do not belong to the most common class.
The classification error rate is not sufficient for tree-growing, and alternative measures are preferable.

The Gini index is a measure of total variance across K classes.
It takes on a small value if all the p_mk's are close to zero or one.
The Gini index is a measure of node purity, with a small value indicating that a node contains predominantly observations from a single class.

An alternative to the Gini index is entropy, given by the formula -∑p_mk log p_mk.
The entropy takes on a value near zero if the p_mk's are all near zero or near one.
The Gini index and entropy are quite similar numerically.

A better strategy is to grow a very large tree T0 and then prune it back to obtain a subtree.
This approach is preferable because it allows for a more exhaustive search of possible subtrees.