Decision trees and random forests

In short

A decision tree is a flowchart-like model that repeatedly splits data on one feature at a time until each leaf is reasonably pure, giving a prediction rule a human can read off the diagram. A random forest grows many de-correlated trees on bootstrap samples with random feature subsets and averages (or votes over) them, trading the single tree's interpretability for much lower variance and strong accuracy on tabular data. Both are standard in GATE DA/CS (entropy, information gain, Gini numericals), in university ML papers (ID3/C4.5/CART algorithms, pruning) and in placement rounds at TCS, Infosys, Wipro, Mu Sigma, Fractal, ZS, Flipkart and bank/NBFC analytics teams. In Indian industry they are the default first model for credit scoring, fraud flags, churn and claim triage because they handle mixed feature types, need little scaling and produce auditable rules — useful under RBI's expectation that a lender can explain a rejection.

Explained

Structure and basic definitions

• Root node: the full training set; internal (decision) node: a test on one feature; branch: an outcome of the test; leaf (terminal) node: a prediction.
• Depth of a node = number of edges from the root; depth of the tree = longest root-to-leaf path. Size = number of nodes/leaves.
• Prediction at a leaf: majority class (classification) or mean of target values (regression); class probability = fraction of each class in that leaf.
• Each leaf corresponds to an axis-parallel hyper-rectangle in feature space — trees carve the space into boxes, so they cannot represent an oblique boundary (like x₁ + x₂ > 5) except as a staircase.
• Non-parametric, greedy, recursive partitioning: the tree chooses the locally best split at each node; it never backtracks, so the result need not be the globally smallest tree (finding the optimal tree is NP-hard).
• A tree is a hypothesis in disjunctive normal form: each root-to-leaf path is a conjunction of tests; the class is the disjunction of its paths.

Split criteria (impurity measures)

• Entropy of a node with class proportions p₁…p_k: H = −Σ pᵢ log₂ pᵢ, in bits. 0 for a pure node, max log₂k for a uniform mix (1 bit for two equal classes).
• Information gain IG = H(parent) − Σ (nⱼ/n) H(childⱼ) — the weighted-average impurity drop. ID3 picks the feature with maximum IG.
• Bias of IG: it favours features with many distinct values (a customer-ID column gives perfectly pure leaves and IG = H(parent), yet is useless). C4.5 fixes this with gain ratio = IG / SplitInfo, where SplitInfo = −Σ (nⱼ/n) log₂(nⱼ/n) penalises many-way splits.
• Gini index = 1 − Σ pᵢ² = probability that two randomly drawn items from the node differ in class. Max 0.5 for two balanced classes. CART uses Gini and makes only binary splits.
• Gini vs entropy: both are concave and agree on most splits; entropy costs a logarithm, Gini is cheaper, so scikit-learn defaults to Gini. Misclassification error (1 − max pᵢ) is not used for growing because it is piecewise linear and often gives zero gain for a useful split; it is used for pruning.
• CHAID uses a chi-square test of independence for categorical targets; splitting stops when no split is significant (typical α = 0.05).
• Regression trees: impurity = variance or SSE within the node; the split maximises variance reduction (equivalently minimises Σ SSE of children). Criterion options in sklearn: squared_error, absolute_error, friedman_mse, poisson.

Building a tree step by step (CART)

1. Start with all n training rows at the root.
2. For every feature and every candidate threshold, compute the impurity of the two children and the weighted impurity.
   • Numeric feature: sort the distinct values, test midpoints between consecutive values (at most n−1 thresholds) with test x ≤ t.
   • Categorical feature: binary partitions of the category set; for a two-class target the categories can be ordered by the positive-class rate, which reduces 2^m−1−1 subsets to m−1 cuts.
3. Pick the split with the largest impurity decrease; create two children and send each row down the matching branch.
4. Recurse on each child.
5. Stop when: node is pure, node size < min_samples_split, a child would be smaller than min_samples_leaf, depth = max_depth, impurity decrease < min_impurity_decrease, or no feature separates the rows.
6. Label each leaf (majority class / mean) and optionally prune.
7. Complexity: training is roughly O(d · n log n) with pre-sorted features; prediction is O(depth) ≈ O(log n) for a balanced tree — one reason trees are used in low-latency scoring.
8. Missing values: C4.5 sends a fractional instance down every branch weighted by branch frequency; CART uses surrogate splits (a correlated backup feature). scikit-learn's trees accepted missing values in numeric features from version 1.3 onward (behaviour depends on version — check before relying on it); the usual Indian-industry practice is still explicit imputation or a "missing" category.

Overfitting and pruning

• An unrestricted tree grows until every leaf is pure — training error 0, high variance, poor generalisation. Trees are low-bias, high-variance learners.
• Pre-pruning (early stopping): max_depth, min_samples_split, min_samples_leaf, max_leaf_nodes, min_impurity_decrease. Cheap, but can stop before a split that only pays off two levels down (the horizon effect).
• Post-pruning: grow fully, then cut back. Reduced-error pruning removes a subtree if validation accuracy does not fall. Cost-complexity (weakest-link) pruning, CART: minimise R_α(T) = R(T) + α·|leaves(T)|; increasing α gives a nested sequence of trees, and α is chosen by cross-validation (ccp_alpha in sklearn).
• Rule post-pruning (C4.5): convert paths to rules, drop conditions that do not hurt accuracy; produces a compact rule set.
• Class imbalance: use class_weight='balanced', or resample; accuracy on a 99:1 dataset is meaningless.

Bagging and random forests

• Bootstrap sample: draw n rows with replacement; about 1 − (1 − 1/n)ⁿ → 63.2% of rows appear at least once, the remaining ≈36.8% are out-of-bag (OOB) for that tree.
• Bagging (Breiman, 1996): train B trees on B bootstrap samples, average predictions. Averaging B i.i.d. estimators with variance σ² gives σ²/B; but bagged trees are correlated, so variance → ρσ² + (1−ρ)σ²/B. The floor ρσ² is why bagging alone plateaus.
• Random forest (Breiman, 2001) = bagging + random feature subspace: at *every split* consider only a random subset of max_features features (defaults: √d for classification, d (or d/3 in older/other implementations) for regression). This lowers ρ, so the ensemble variance falls further; each tree is slightly worse but the forest is better.
• Trees are grown deep and unpruned (variance is handled by averaging), and are fully parallel — n_jobs=-1.
• Aggregation: hard majority vote or, better, average of class probabilities (soft voting); mean of predictions for regression.
• OOB error: predict each row using only the trees that did not see it — a built-in validation estimate, roughly comparable to k-fold CV, free of a separate split (oob_score=True).
• Extremely Randomised Trees (Extra-Trees): thresholds are picked at random instead of optimised, and (by default) no bootstrap — faster, even lower variance, slightly more bias.
• Key hyperparameters: n_estimators (more is never worse for accuracy, only slower — no overfitting risk from B), max_features (the main accuracy knob), max_depth/min_samples_leaf (control for noisy data), bootstrap, class_weight, max_samples.
• Random forest vs boosting: forests build deep trees in parallel to cut variance; gradient boosting adds shallow trees sequentially to cut bias. Forests are harder to overfit and need less tuning; boosting usually wins on accuracy when tuned.

Feature importance and interpretability

• MDI / Gini importance: sum over all nodes splitting on feature f of (n_node/n)·impurity decrease, averaged over trees, normalised to 1. Fast, but biased towards high-cardinality and continuous features and computed on training data.
• Permutation importance: shuffle one column in held-out data and measure the drop in score. Model-agnostic, uses unseen data, but splits credit unpredictably among correlated features.
• Drop-column importance: refit without the feature — most faithful, most expensive.
• Correlated features share importance, so a near-zero score does not prove irrelevance.
• A single shallow tree is directly interpretable (and exportable as IF-THEN rules, export_text); a 500-tree forest is not — explain it with partial dependence plots, SHAP values or a surrogate tree.
• Indian regulatory angle: RBI's Digital Lending guidelines and its FREE-AI/model-risk expectations require a lender to give the principal reason for a credit decision, so pure black-box forests are usually paired with reason codes or a simpler challenger model; the Digital Personal Data Protection Act, 2023 governs the personal data fed to such models (its rules were notified in 2025 with phased implementation — check the current commencement dates).

Advantages and limitations

• Shared strengths: no feature scaling, handles non-linear interactions automatically, robust to outliers in features, handles irrelevant features reasonably.
• Shared weaknesses: axis-parallel boundaries only; poor on sparse high-dimensional text compared with linear models; biased towards the majority class under imbalance; cannot extrapolate trends (a regression tree predicts a flat value outside the observed range); large forests are memory-heavy at inference.

Key points

• Decision tree - recursive, greedy, axis-parallel partitioning of feature space into pure regions.
• Entropy - −Σ pᵢ log₂ pᵢ; 0 if pure, 1 bit for a 50:50 binary node.
• Information gain - parent entropy minus weighted child entropy; the ID3 split criterion.
• Gain ratio - IG divided by split information; C4.5's fix for the many-valued-attribute bias.
• Gini index - 1 − Σ pᵢ²; max 0.5 for two balanced classes; CART's default, cheaper than entropy.
• CART - binary splits only, Gini for classification, variance/SSE for regression, cost-complexity pruning.
• ID3 / C4.5 / CART / CHAID - the four examinable algorithms: IG / gain ratio / Gini / chi-square.
• Regression tree - minimises within-node variance; leaf predicts the mean; output is piecewise constant.
• Pre-pruning vs post-pruning - stop early with depth/size limits vs grow fully then cut by R_α(T) = R(T) + α|leaves|.
• Bias-variance - a deep tree is low-bias/high-variance; averaging reduces variance without raising bias much.
• Bagging - bootstrap + aggregate; variance σ²/B only if trees were independent.
• Random forest - bagging plus a random feature subset at each split, to de-correlate trees (ρ ↓).
• max_features - √d (classification) is the main tuning knob; too large → correlated trees, too small → weak trees.
• OOB error - the ≈36.8% of rows left out of each bootstrap give a free validation estimate.
• n_estimators - more trees never overfit; they only cost time and memory.
• MDI importance is biased; prefer permutation importance on held-out data.
• Trees need no scaling - splits depend on order, not distance, unlike kNN/SVM.
• Forests cannot extrapolate - predictions are bounded by the training target range.

Formulas and examples

Example 1 — Entropy and information gain (ID3), placement-offer data (14 rows). Target: Placed (Yes/No) — 9 Yes, 5 No.

• H(S) = −(9/14)log₂(9/14) − (5/14)log₂(5/14) = −0.643(−0.637) − 0.357(−1.485) = 0.410 + 0.530 = 0.940 bits.
• Split on CGPA band → High (5 rows: 4 Y, 1 N), Mid (5 rows: 3 Y, 2 N), Low (4 rows: 2 Y, 2 N).
  • H(High) = −0.8log₂0.8 − 0.2log₂0.2 = 0.258 + 0.464 = 0.722
  • H(Mid) = −0.6log₂0.6 − 0.4log₂0.4 = 0.442 + 0.529 = 0.971
  • H(Low) = 1.000
  • Weighted = (5/14)(0.722) + (5/14)(0.971) + (4/14)(1.000) = 0.258 + 0.347 + 0.286 = 0.891
  • IG(CGPA) = 0.940 − 0.891 = 0.049 bits
• Split on Internship → Yes (7 rows: 6 Y, 1 N), No (7 rows: 3 Y, 4 N).
  • H(Yes) = −(6/7)log₂(6/7) − (1/7)log₂(1/7) = 0.191 + 0.401 = 0.592
  • H(No) = −(3/7)log₂(3/7) − (4/7)log₂(4/7) = 0.524 + 0.461 = 0.985
  • Weighted = 0.5(0.592) + 0.5(0.985) = 0.789 → IG(Internship) = 0.151 bits
• ID3 splits the root on Internship (0.151 > 0.049).
• Gain ratio check: SplitInfo(Internship) = −2 × 0.5log₂0.5 = 1.000 → gain ratio = 0.151. SplitInfo(CGPA) = −[0.357log₂0.357 × 2 + 0.286log₂0.286] = 0.531 + 0.531 + 0.516 = 1.578 → gain ratio = 0.049/1.578 = 0.031. Internship still wins.

Example 2 — Gini index for the same two candidate splits.

• G(S) = 1 − (9/14)² − (5/14)² = 1 − 0.4133 − 0.1276 = 0.4592
• Internship: G(Yes) = 1 − (6/7)² − (1/7)² = 1 − 0.7347 − 0.0204 = 0.2449; G(No) = 1 − (3/7)² − (4/7)² = 1 − 0.1837 − 0.3265 = 0.4898. Weighted = 0.5(0.2449) + 0.5(0.4898) = 0.3673 → Gini gain 0.0919.
• CGPA: G(High) = 1 − 0.64 − 0.04 = 0.32; G(Mid) = 1 − 0.36 − 0.16 = 0.48; G(Low) = 0.50. Weighted = 0.357(0.32) + 0.357(0.48) + 0.286(0.50) = 0.1143 + 0.1714 + 0.1429 = 0.4286 → Gini gain 0.0306.
• Same ranking as entropy — Internship chosen. (Note how a 7/7 split with purity 6:1 beats a three-way split that leaves every branch mixed.)

Example 3 — Numeric threshold for a regression tree (salary in ₹ lakh per annum). Experience (years) x = 1, 2, 3, 4, 5; Salary y = 4, 5, 7, 10, 14 (₹ lakh).

• ȳ = 8, SSE(parent) = 16 + 9 + 1 + 4 + 36 = 66.
• Try x ≤ 2.5: left {4,5}, mean 4.5, SSE = 0.25 + 0.25 = 0.5; right {7,10,14}, mean 10.333, SSE = 11.111 + 0.111 + 13.444 = 24.667. Total = 25.167.
• Try x ≤ 3.5: left {4,5,7}, mean 5.333, SSE = 1.778 + 0.111 + 2.778 = 4.667; right {10,14}, mean 12, SSE = 4 + 4 = 8. Total = 12.667.
• Try x ≤ 1.5: left {4}, SSE 0; right {5,7,10,14}, mean 9, SSE = 16 + 4 + 1 + 25 = 46. Total = 46.
• Try x ≤ 4.5: left {4,5,7,10}, mean 6.5, SSE = 6.25 + 2.25 + 0.25 + 12.25 = 21; right {14}, SSE 0. Total = 21.
• Best split is x ≤ 3.5 (SSE 12.667, reduction 53.333). Leaves predict ₹5.33 lakh and ₹12 lakh — note the piecewise-constant output: a 6-year candidate is also predicted ₹12 lakh (no extrapolation).

Example 4 — Cost-complexity pruning. A subtree with 4 leaves misclassifies 10 of 200 training rows; collapsing it to one leaf misclassifies 22.

• R(T_full) = 10/200 = 0.05, |leaves| = 4; R(T_leaf) = 22/200 = 0.11, |leaves| = 1.
• Break-even α: 0.05 + 4α = 0.11 + α → 3α = 0.06 → α = 0.02. For ccp_alpha > 0.02 the subtree is pruned; below it, kept. At α = 0.03: full = 0.05 + 0.12 = 0.17 vs leaf = 0.11 + 0.03 = 0.14 → prune.

Example 5 — Forest variance and OOB. Single tree variance σ² = 0.09, pairwise correlation ρ = 0.4, B = 100 trees.

• Var = 0.4(0.09) + 0.6(0.09)/100 = 0.036 + 0.00054 = 0.03654 (SD 0.191 vs single tree 0.300 — a 36% drop in SD).
• Lower ρ to 0.15 via max_features=√d: Var = 0.0135 + 0.000765 = 0.014265 (SD 0.119) — de-correlation helps far more than adding trees.
• With n = 10,000 rows, in-bag ≈ 6,321 distinct rows; OOB ≈ 3,679 rows per tree, and each row is OOB for ≈36.8 of 100 trees — enough votes for a stable OOB score.

from sklearn.ensemble import RandomForestClassifier
from sklearn.tree import DecisionTreeClassifier, export_text
from sklearn.inspection import permutation_importance

tree = DecisionTreeClassifier(criterion="gini", max_depth=4,
                              min_samples_leaf=20, ccp_alpha=0.002,
                              class_weight="balanced", random_state=42).fit(X_tr, y_tr)
print(export_text(tree, feature_names=list(X_tr.columns)))   # auditable rules

rf = RandomForestClassifier(n_estimators=500, max_features="sqrt",
                            min_samples_leaf=5, oob_score=True,
                            class_weight="balanced_subsample",
                            n_jobs=-1, random_state=42).fit(X_tr, y_tr)
print(rf.oob_score_)                                          # free validation estimate
print(permutation_importance(rf, X_te, y_te, n_repeats=10, random_state=42).importances_mean)

Where it is used

• Banking, NBFC and fintech credit scoring: HDFC, ICICI, Bajaj Finance, CIBIL/CRIF score-card development and challenger models; trees give the reason codes a loan rejection letter needs.
• Fraud and risk: UPI/card transaction fraud flags at NPCI-linked processors, insurance claim triage at ICICI Lombard/HDFC Ergo, GST/tax return anomaly screening.
• Telecom, e-commerce and OTT churn and propensity: Jio, Airtel, Flipkart, Swiggy, Zomato propensity-to-buy and next-best-offer models; forests on tabular clickstream aggregates.
• Analytics consulting and GCC roles: Mu Sigma, Fractal, ZS Associates, Tiger Analytics, EXL, Accenture — random forest is a standard interview and case-study model; data scientist, risk analyst, decision scientist job roles.
• Healthcare, agriculture and public sector: disease-risk screening from tabular diagnostics, ICAR/remote-sensing crop and soil classification, electricity-theft detection by discoms.
• Feature screening in any ML pipeline: a quick forest's importances shortlist variables before a costlier model.

Interview questions

• Q: Why does a decision tree need no feature scaling? A: Splits are threshold comparisons on one feature at a time, so only the rank order of values matters; monotonic transforms like standardising or log do not change the tree's structure.
• Q: Gini or entropy — which should you use? A: They almost always pick the same split; Gini avoids the logarithm so it is faster, which is why it is the default. Entropy slightly prefers more balanced splits.
• Q: Why does ID3 prefer attributes with many values, and how does C4.5 fix it? A: A many-valued attribute produces small, nearly pure branches, which inflates information gain; C4.5 divides gain by the split information, penalising high-cardinality splits.
• Q: What exactly does the "random" in random forest refer to? A: Two sources — a bootstrap sample of rows per tree, and a random subset of features considered at every split; the second is what de-correlates the trees.
• Q: Can a random forest overfit by adding more trees? A: No — extra trees only refine the average and plateau. Overfitting comes from very deep trees on noisy data, not from n_estimators.
• Q: What is OOB error and why is it useful? A: Each tree leaves out about 36.8% of rows; predicting those rows with only the trees that never saw them gives a validation estimate without a separate holdout.
• Q: Why are random forest trees grown unpruned? A: Deep trees are low-bias and high-variance; averaging many of them removes the variance, so pruning would only add bias.
• Q: Why should you be careful with feature_importances_? A: MDI importance is computed on training data and is biased towards continuous and high-cardinality features; use permutation importance on held-out data instead.
• Q: Can a regression tree predict a value outside the training range? A: No — every prediction is the mean of some training subset, so forests and trees cannot extrapolate a trend; use a linear or additive model for that.
• Q: How do random forests differ from gradient boosting? A: Forests build deep trees independently in parallel to reduce variance; boosting adds shallow trees sequentially, each correcting the previous residuals, to reduce bias — more accurate but more sensitive to tuning and overfitting.
• Q: A single data point changes and the whole tree looks different — why? A: Greedy splitting is unstable: a tiny change can flip the root split and cascade down the tree. Bagging exists precisely to average this instability away.
• Q: How do you handle class imbalance in trees and forests? A: Use class_weight='balanced'/balanced_subsample, resample or set a tuned probability threshold, and evaluate with precision-recall, F1 or AUC rather than accuracy.

Common mistakes

• Forgetting the weights |Sⱼ|/|S| when averaging child impurities, so information gain comes out wrong in the exam.
• Using natural log instead of log₂ for entropy without saying so — answers in nats then do not match the expected 0.940-style values.
• Computing entropy of the attribute's value distribution instead of the class distribution within each branch.
• Reporting training accuracy of a fully grown tree (always near 100%) as model performance, instead of CV or OOB accuracy.
• One-hot encoding a high-cardinality categorical feature before a forest: each dummy is a weak binary split, which dilutes importance and hurts accuracy — keep it as a category or use target/ordinal encoding.
• Trusting feature_importances_ for feature selection when features are correlated, or treating a zero importance as proof of irrelevance.
• Treating a random forest as explainable to a regulator; and raising n_estimators when the real problem is max_features, max_depth or an imbalanced target.

Related topics

Ensemble methods and gradient boosting · Overfitting, bias-variance and regularisation · Model evaluation metrics · Feature selection and model interpretability · Machine learning workflow · Linear and logistic regression