Decision Trees: Entropy, Gini Impurity, Pruning, and Ensembles

A decision tree recursively divides a dataset into regions that are increasingly pure with respect to the target variable.

For classification, common split criteria include entropy and Gini impurity:

Entropy: H(S) = -Σ pᵢ log₂ pᵢ
Gini:    G(S) = 1 - Σ pᵢ²

ID3 selects features by information gain. C4.5 uses gain ratio to reduce the bias toward high-cardinality attributes. CART commonly uses Gini impurity for classification and squared error for regression, producing binary splits.

A fully grown tree can memorize noise. Pre-pruning limits depth, minimum samples, or minimum improvement. Post-pruning removes branches after growth according to validation performance or a complexity penalty.

Random forests train many decorrelated trees on bootstrap samples and random feature subsets, then aggregate their predictions. Gradient-boosted trees build trees sequentially to correct previous residuals. XGBoost adds regularization, optimized split search, and efficient handling of sparse data.

Evaluate trees with a validation strategy appropriate to the data, inspect class imbalance and leakage, and tune complexity rather than relying only on training accuracy.