Decision Trees & Ensembles
Finding the Best Split: Gini vs Entropy
A decision tree recursively partitions data by asking yes/no questions about features. At each node, the algorithm searches every feature and every threshold, choosing the split that most reduces impurity — the mix of classes in each resulting region.
Two standard impurity measures:
- Gini impurity: 1 − Σ pᵢ² — probability that a random sample is misclassified. Ranges 0 (pure) to 0.5 (balanced binary). Slightly faster to compute.
- Entropy: −Σ pᵢ log₂(pᵢ) — information required to describe the outcome. Ranges 0 to log₂(K) for K classes. Can produce more balanced trees.
In practice, the two produce very similar trees. Use Gini (the sklearn default) unless you have a specific reason to prefer entropy.
from sklearn.tree import DecisionTreeClassifier, export_text from sklearn.datasets import load_iris X, y = load_iris(return_X_y=True) # criterion='gini' (default) or 'entropy' tree = DecisionTreeClassifier( criterion='gini', max_depth=4, # limit tree depth to prevent overfitting min_samples_leaf=5, # each leaf needs at least 5 samples random_state=42 ) tree.fit(X, y) # Print the tree rules as text print(export_text(tree, feature_names=load_iris().feature_names)) # The path any single sample takes through the tree node_indicator = tree.decision_path(X[:1]) print(f"Leaf node for sample 0: {tree.apply(X[:1])[0]}")
Why Unbounded Trees Memorise Instead of Learn
An unconstrained decision tree will grow until every leaf contains exactly one training sample — achieving 100% training accuracy but generalising poorly. This is the quintessential overfitting example in ML.
from sklearn.model_selection import cross_val_score import numpy as np depths = range(1, 20) cv_scores = [] for d in depths: dt = DecisionTreeClassifier(max_depth=d, random_state=42) scores = cross_val_score(dt, X, y, cv=5) cv_scores.append(scores.mean()) best_depth = depths[np.argmax(cv_scores)] print(f"Best depth: {best_depth}, CV accuracy: {max(cv_scores):.3f}") # Other pruning knobs: dt = DecisionTreeClassifier( max_depth=5, # max levels min_samples_split=20, # node needs 20 samples to be split min_samples_leaf=10, # leaf needs 10 samples minimum max_leaf_nodes=50, # cap on total number of leaves ccp_alpha=0.01 # cost-complexity pruning (post-training) )
Many Imperfect Trees Beat One Perfect One
Random Forests address the high variance of decision trees through bagging (bootstrap aggregating). Each tree is trained on a random bootstrap sample (with replacement) of the data, and at each split only a random subset of features is considered. The forest's prediction is the majority vote (classification) or average (regression) of all trees.
The two sources of randomness — data sampling and feature sampling — ensure that trees are decorrelated. Averaging decorrelated predictions reduces variance much more effectively than averaging correlated ones.
from sklearn.ensemble import RandomForestClassifier from sklearn.metrics import classification_report rf = RandomForestClassifier( n_estimators=200, # number of trees; more = more stable, diminishing returns past ~200 max_features='sqrt', # features per split: sqrt(n) for classification (default) max_depth=None, # trees grow fully — variance is controlled by averaging oob_score=True, # out-of-bag score: free validation estimate n_jobs=-1, # use all CPU cores random_state=42 ) rf.fit(X_train, y_train) # OOB score: accuracy on samples not used to train each tree print(f"OOB score: {rf.oob_score_:.3f}") preds = rf.predict(X_test) print(classification_report(y_test, preds))
oob_score=True gives you a validation estimate without holding out a separate validation set — very useful when data is limited.Sequential Error Correction
While Random Forests build trees in parallel (independently), gradient boosting builds them sequentially. Each new tree learns to correct the residual errors of all previous trees, following the gradient of the loss function. The result is usually more accurate than bagging, but more sensitive to hyperparameters and overfitting.
from sklearn.ensemble import GradientBoostingClassifier from xgboost import XGBClassifier # pip install xgboost # sklearn GradientBoosting — solid, slower on large data gb = GradientBoostingClassifier( n_estimators=200, learning_rate=0.05, # shrinks each tree's contribution; lower = better but needs more trees max_depth=4, subsample=0.8, # fraction of samples per tree (stochastic GB) random_state=42 ) # XGBoost — faster, regularisation built in, handles missing values xgb = XGBClassifier( n_estimators=200, learning_rate=0.05, max_depth=4, subsample=0.8, colsample_bytree=0.8, # fraction of features per tree reg_alpha=0.1, # L1 regularisation reg_lambda=1.0, # L2 regularisation eval_metric='logloss', random_state=42 ) xgb.fit( X_train, y_train, eval_set=[(X_test, y_test)], verbose=False )
Which Features Matter — and the Caveats
Tree-based models record how much each feature reduced impurity across all splits. sklearn exposes this as feature_importances_. It's fast and built-in, but has a known bias: high-cardinality features appear artificially important, even if they're not causal.
import pandas as pd # Built-in importance (mean decrease in impurity) importances = pd.Series( rf.feature_importances_, index=feature_names ).sort_values(ascending=False) print(importances.head(10)) # Permutation importance — more honest, model-agnostic # Shuffles one feature at a time, measures accuracy drop from sklearn.inspection import permutation_importance result = permutation_importance( rf, X_test, y_test, n_repeats=10, random_state=42 ) perm_imp = pd.Series( result.importances_mean, index=feature_names ).sort_values(ascending=False) print(perm_imp.head(10))