Decision Tree Pruning

Tree Pruning

• 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

• 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 α.

Classification Trees

• 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.

Gini Index

• 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.

Entropy

• 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.

Tree Pruning Strategy

• 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.