Cheat sheet · Machine Learning

Decision Trees & Random Forests cheat sheet

The key ideas on one page — plus common pitfalls and interview tips. Skim it before an interview, or print it for revision.

Decision trees are interpretable, axis-aligned recursive partitioners that overfit easily; random forests reduce variance via bagging plus per-split feature randomization, giving a strong, low-tuning baseline for tabular data. This sheet covers the math, training mechanics, hyperparameters, importance/interpretation, and how they compare to gradient boosting.

Decision Tree Fundamentals

A tree recursively splits the feature space into axis-aligned regions; each leaf predicts a constant: majority class (classification) or mean target (regression).
Greedy, top-down (CART): at each node pick the (feature, threshold) that maximizes impurity decrease — no backtracking, so trees are locally optimal, not globally.
CART produces strictly binary splits; ID3/C4.5 allow multi-way categorical splits. sklearn implements an optimized CART variant.
Trees handle mixed feature types, are invariant to monotonic feature transforms (no scaling/normalization needed), and capture non-linear interactions automatically.
Fully grown trees have low bias but very high variance — they memorize training data, hence pruning or ensembling is essential.
Prediction is O(depth), ~O(log n) for a balanced tree; training cost is roughly O(n · m · depth), i.e. ~O(n · m · log n) for a balanced tree (n samples, m features).

Split Criteria & Formulas

Gini impurity: G = 1 − Σ p_k², minimized at 0 (pure node), max 1 − 1/K for K classes. Slightly faster than entropy and usually near-identical results.
Entropy: H = − Σ p_k log2 p_k; Information Gain = H(parent) − Σ (n_child/n) · H(child). Both are computed over the class proportions p_k at a node.
Gini and entropy rarely disagree on the chosen split; Gini tends to isolate the most frequent class, entropy is marginally more balanced. Default to Gini for speed.
Regression splits minimize weighted child variance / MSE (criterion='squared_error'), or MAE ('absolute_error') for robustness to outliers.
Cost-complexity (post) pruning minimizes R_α(T) = R(T) + α·|leaves|; larger α → smaller tree. Tune α via cross-validation (ccp_alpha in sklearn; cost_complexity_pruning_path gives candidate alphas).
Information-gain ratio (C4.5) divides gain by the split's intrinsic info (entropy of the partition) to penalize high-cardinality features that raw IG over-favors.

Random Forest Mechanics

Bagging: train B trees each on a bootstrap sample (~63.2% unique rows; the remaining ~36.8% are out-of-bag) and average (regression) or majority-vote / average class probabilities (classification) to cut variance.
Feature randomization: at each split consider only a random subset of features (max_features ≈ √m classification, ~m/3 regression by classic guidance) — this decorrelates trees, the key edge over plain bagging.
Variance of the average ≈ ρσ² + (1−ρ)σ²/B; lowering pairwise tree correlation ρ (via feature subsampling) is what makes the ensemble strong as B grows.
Trees are grown deep (low bias, high variance) intentionally — variance is reduced by averaging, not by pruning individual trees.
OOB error is a free, near-unbiased validation estimate computed from each tree's out-of-bag samples — no separate holdout needed (set oob_score=True, bootstrap=True).
Embarrassingly parallel: trees train independently (n_jobs=-1). Adding trees never overfits; accuracy only plateaus while compute grows.

Key Hyperparameters & Tuning

n_estimators: more trees = more stable estimate; pick the largest you can afford, then stop when OOB/CV plateaus. It is not a regularizer.
max_features: the most impactful RF knob — smaller values decorrelate trees (lower variance, higher bias). Tune this first. sklearn default is 'sqrt' for the classifier and 1.0 (all features) for the regressor since v1.1.
max_depth / min_samples_leaf / min_samples_split: control individual-tree complexity; raise min_samples_leaf to regularize on noisy data (sklearn defaults: depth=None, leaf=1, split=2).
max_samples (bootstrap fraction) and bootstrap=True/False trade variance vs. bias; subsampling speeds up large datasets.
class_weight='balanced' or 'balanced_subsample' for imbalanced targets; tune the decision threshold on probabilities rather than relying on the default 0.5.
Tune with RandomizedSearchCV or Bayesian/Optuna over max_features, max_depth, min_samples_leaf; RFs are forgiving, so defaults already give a strong baseline.

Feature Importance & Interpretation

Impurity-based (MDI / Gini importance, rf.feature_importances_) is fast but biased toward high-cardinality and continuous features, and is computed on training data — treat with caution.
Permutation importance (shuffle one feature, measure score drop) is model-agnostic and should be computed on held-out data; preferred for reporting.
Correlated features split importance among themselves, making any single one look weak — clustering features or drop-column importance helps disentangle.
SHAP (TreeSHAP) gives consistent, locally-accurate, per-prediction attributions with directionality — the modern standard for explaining tree ensembles.
A single shallow tree is directly interpretable (follow the if/else path); a forest is not, hence the need for permutation/SHAP for global and local explanations.
Partial dependence (PDP) and ICE plots reveal the marginal effect and individual-level shape of a feature on predictions.

RF vs. Boosting & When to Use

RF = bagging (parallel, independent deep trees, variance reduction); boosting (XGBoost/LightGBM/CatBoost) = sequential shallow trees fitting residuals/gradients, reducing bias.
Boosting usually wins on raw accuracy for tabular data but needs careful tuning (learning rate, n_estimators, depth) and can overfit; RF is a robust, low-tuning baseline.
RF is more robust to noisy labels and hyperparameter choices; gradient boosting is more sensitive but more expressive.
For tabular/structured data, tree ensembles still routinely match or beat deep learning as of 2026 (cf. ongoing 'tabular DL' debate); reach for them before neural nets.
Use RF for a fast strong baseline, free OOB validation, and when interpretability via importances matters; switch to LightGBM/XGBoost/CatBoost (the latter two with native categorical support) when squeezing out maximum accuracy.
Neither extrapolates beyond the training range (piecewise-constant outputs) — a hard limit for trending time-series or out-of-range regression.

Common pitfalls

Treating n_estimators as a regularizer — more trees in an RF do not overfit; they only plateau. Overfitting is controlled via depth/leaf size/max_features.
Reporting impurity-based (MDI) importances without noting their bias toward high-cardinality and continuous features, and that they are computed on training data.
Computing permutation importance on training data instead of a held-out set, which inflates apparent importance.
Expecting trees/forests to extrapolate — predictions are constant outside the training feature range, breaking trending regression and time series.
Comparing an unpruned single tree to an RF and concluding trees are 'bad' rather than under-regularized (high variance).
Letting high-cardinality categorical features (e.g. IDs) leak or dominate splits; encode/aggregate them and watch for target leakage.
Ignoring class imbalance and judging on accuracy — use class_weight, balanced sampling, threshold tuning, and PR-AUC/F1.
Naive label/ordinal encoding of nominal categoricals in sklearn imposes a false ordering on splits (use native categorical handling like LightGBM/CatBoost, or one-hot for low cardinality).
Assuming feature scaling matters for trees as it does for linear/SVM models — trees are scale-invariant; but missing-value handling still differs by library (sklearn requires imputation, LightGBM/XGBoost handle NaN natively).

Interview tips

Be able to derive Gini and entropy from scratch and explain why splits maximize impurity decrease; expect to compute information gain on a small toy example.
Explain the bias-variance intuition: why deep trees are low-bias/high-variance and exactly how bagging + feature randomization reduces variance via decorrelation (the ρ in the variance formula).
Articulate the two sources of randomness in an RF (bootstrap rows + random feature subset per split) and why feature randomness is the crucial differentiator from plain bagging.
Contrast Random Forest vs. Gradient Boosting on parallel-vs-sequential, variance-vs-bias, tuning sensitivity, and typical accuracy.
Discuss OOB error: what it is, why it is approximately unbiased, and how it can substitute for a validation set.
Know the failure modes of feature importance (correlation, cardinality bias, train-set leakage) and the modern alternatives (permutation, TreeSHAP).
Explain why trees cannot extrapolate and what that means for regression and time-series problems.
Be ready to reason about computational complexity, parallelism, and memory for large datasets, plus practical handling of categoricals, missing values, and imbalance.

Read the full lesson