Decision Tree Pruning with Cost-Complexity
Tree Models & Ensembles DS practice problem on Onlearn.
Difficulty: hard.
Topics: Understanding Cost-Complexity Pruning (CCP) in Decision Trees, Gini Impurity, Weakest Link Pruning, Effective Alpha Calculation, Post-pruning Techniques, Structural Risk Minimization, Supervised Learning, Statistical Learning Theory, Optimization, Computational Complexity, Decision Theory, Bias-Variance Tradeoff, Recursive Partitioning, Model Regularization, Overfitting Mitigation, Tree Traversal Algorithms.
Implement a function that performs cost complexity pruning on a binary decision tree. Given a tree structure where each node has 'impurity', 'n samples', and 'children' (or None), calculate the effective alpha for each subtree and return the pruned tree structure where all subtrees with effective alpha <= threshold are collapsed into leaf nodes.