Pruning Decision Trees in R

In classification tasks within machine learning, Decision Trees are widely popular due to their intuitive nature and powerful ability to model non-linear relationships. However, as the volume of training data increases or the number of features grows, a maximum-depth decision tree constructed solely via greedy algorithms often falls into a state of "over-learning." In this state, the model not only memorizes the noise and outliers in the data but also captures correlations that do not actually exist between samples. This phenomenon is known as overfitting.

A severely overfitted decision tree typically manifests as: an excessive number of leaf nodes, extremely deep tree levels, extremely high prediction accuracy on the training set, yet poor performance on test sets. Such models have poor generalization capabilities and fail to accurately reflect the true patterns of the real world. To address this problem, Pruning techniques have emerged. The essence of pruning is to simplify the complexity of the decision tree by removing subtrees or nodes that contribute minimally to the model's classification, thereby improving its predictive performance on unseen data.
Pre-pruning, also known as early stopping, involves introducing constraints during the construction process of a decision tree to prevent it from growing too large. The core idea of this method is "to stop while things are going well"; after a node splits, if the gain from further splitting is insufficient to offset the risk of increasing model complexity, the expansion of that node is terminated prematurely.

Common pre-pruning strategies include:

  • Maximum Depth (Max Depth): Specifies the upper limit on the number of levels in the decision tree to prevent infinite growth.
  • Minimum Samples Split (Min Samples Split): Requires a node to contain at least N samples before it can be split, avoiding incorrect judgments based on very little data.
  • Minimum Impurity Decrease / Minimum Leaf Size: Allows splitting only if the purity improvement provided by a feature exceeds a preset threshold; or mandates that a leaf node must accommodate at least M samples.

Taking the rpart package in R as an example, the degree of pre-pruning can be flexibly controlled by setting specific parameters. The following code demonstrates how to construct a decision tree with a maximum depth of 5 and a minimum leaf size of 10:

library(rpart)

# Assume df is the training data frame and target_col is the name of the target variable
model <- rpart(target_col ~ ., data = df, 
               method = "class", 
               control = rpart.control(maxdepth = 5, minsplit = 20, minbucket = 10))

# View the structure of the pruned tree
print(model)
plot(model); text(model)

In this example, maxdepth=5 forces a limit on the height of the tree, while minbucket=10 ensures that each leaf node contains at least 10 samples. This strategy is computationally efficient but may sometimes lead to underfitting (Underfitting) due to premature stopping of splits, meaning the model becomes too simple and fails to capture key features within the data.

Post-pruning Strategies and Cross-Validation Optimization

To find the optimal balance between avoiding overfitting and preventing underfitting, Post-pruning is generally considered a more robust method. Post-pruning is a "remedy" operation performed after the decision tree has been fully constructed. Its basic workflow is: first generate a complete, unpruned decision tree, then remove subtrees from the bottom up, deciding whether to retain a branch by comparing the model's performance on a validation set before and after pruning.

The most classic post-pruning algorithm is Cp (Cost-Complexity Pruning), proposed by Masanori石原 (Masanori Ishibashi). This method calculates a weighted sum of "complexity" and "error rate" for each candidate node:
$$ \text{Score} = C_p + \alpha \times (\text{Node Complexity}) $$
Where $C_p$ is the estimate of the fitting error rate, $\alpha$ is a regularization parameter (controlling the pruning intensity), and "node complexity" usually refers to the number of leaf nodes. The algorithm's goal is to find an optimal subtree structure by adjusting $\alpha$ to minimize the Score.

In R language, post-pruning can be implemented using the cp (complexity parameter) within rpart.control. The default value for this parameter is automatically calculated based on cross-validation, but users can also specify it manually for finer control:

# Perform pruning using cp=0.15 as the complexity threshold
model_pruned <- rpart(target_col ~ ., data = df, 
                      method = "class", 
                      control = rpart.control(cp = 0.15))

# Or utilize the default automatic cross-validation calculation for the optimal cp value (requires setting nminsplit)
model_cv <- rpart(target_col ~ ., data = df, 
                  method = "class", 
                  control = rpart.control(minbucket = 20, minsplit = 40))

# Extract the pruned tree structure for predicting new data
predict(model_pruned, newdata = test_data)

The advantage of post-pruning lies in its utilization of information outside the training set (typically obtained via cross-validation), allowing for a more accurate assessment of the model's generalization error. Compared to pre-pruning, post-pruning often yields better classification accuracy and AUC values because it allows the model to fully fit data details initially, followed by the statistical removal of redundant parts.

Parameter Tuning and Precautions in Practice

In practical applications, the effectiveness of decision tree pruning is highly dependent on the selection of hyperparameters. Different dataset distributions, feature dimensions, and sample sizes may require vastly different cp thresholds or depth limits. Therefore, systematic Grid Search is a necessary step.

Combining the caret package in R facilitates convenient parameter tuning:

  1. Cross-validation Strategy: Employ K-fold cross-validation to evaluate model performance under different pruning degrees.
  2. Repeated Sampling: Run multiple times to stabilize results and avoid bias caused by randomness.
  3. Feature Importance Analysis: After pruning, use the varImp() function to check which features' contribution has significantly dropped, thereby judging whether the pruning is reasonable.

It is important to note that relying solely on error rate metrics (such as training set accuracy) to guide pruning is dangerous. One must always refer to misclassification counts or loss function change curves from the validation set. Furthermore, for imbalanced datasets, relying merely on error rates may fail to reflect the model's predictive capability for minority classes; in such cases, it is advisable to consider combining metrics like F1-Score for auxiliary evaluation.

In summary, decision tree pruning is a key technical means for improving the generalization capability of machine learning models. Whether adopting growth-restricting pre-pruning strategies or using cross-validation to find an optimal complexity via post-pruning, the core objective remains removing noise and retaining signal. Mastering the rpart package and its control parameters in R can help data scientists build classification models that are both concise and powerful.