Decision Trees and Random Forests: From Cricket Team Selection to Patient Diagnosis

Every selection committee for the Indian cricket team runs an algorithm, even if nobody calls it that. A selector doesn't average forty numbers about a player into one score. He asks questions in sequence: Is the domestic average above 40? If yes, is the strike rate above 130? If a player clears both bars, he's in; if he clears neither, he's out; the players in between get argued over using a third fact — how they've played under pressure. That sequence of yes/no questions, each one narrowing down the decision, is a decision tree. It is also, almost exactly, the algorithm this chapter formalizes, trains on real numbers, and then strengthens by building many such trees at once — the same idea a hospital triage system uses when it asks about fever, then cough, then oxygen saturation, before deciding whether a patient needs immediate attention.

By the end of this chapter you will be able to build a decision tree by hand from a small dataset — computing the exact quantity, in bits, that tells the algorithm which question to ask first — and explain, with a real variance formula, why a "forest" of such trees is more reliable than any single tree, including the one a human selector builds in his head.

1. From a selector's instinct to a formal tree

Suppose eight players are up for selection, and the committee has three yes/no facts about each one: is the domestic batting average above 40, is the strike rate above 130, and does the player have a reputation for a strong "big-match temperament" (rated High or Low from past knockout performances). Here is the actual record of who got selected:

Player  Avg>40  SR>130  Temp=High  Selected
  1       Y       Y        Y          Y
  2       Y       Y        N          Y
  3       Y       N        Y          Y
  4       Y       N        N          Y
  5       N       Y        Y          Y
  6       N       Y        N          N
  7       N       N        Y          N
  8       N       N        N          N

Five of eight were selected, three were not. A decision tree is a flowchart, built from exactly this table, that asks the fewest and most useful yes/no questions needed to sort every row correctly into "Selected" or "Not Selected." The two problems the algorithm has to solve are: (1) which question to ask first, and (2) when to stop asking. Both are answered with a number called entropy.

2. Entropy: measuring how mixed up a group is

Before comparing questions, we need a way to measure how "impure" or mixed a group of outcomes is. A group that's all-Selected or all-Not-Selected is perfectly pure — there's nothing left to decide. A group that's a 50-50 mix is maximally uncertain — you'd need one more yes/no question, on average, to pin down the answer, similar to guessing a coin flip.

Claude Shannon's entropy formula captures exactly this "how many yes/no questions on average" intuition. For a group with class probabilities p₁, p₂, …, pₖ:

H(S) = -Σ pᵢ · log₂(pᵢ)

Base 2 is used deliberately, not decoratively: log₂ converts a probability into "number of binary yes/no questions needed," because 1 bit of entropy is exactly the uncertainty of one fair coin flip (p = 0.5 gives H = -0.5·log₂0.5 - 0.5·log₂0.5 = -0.5·(-1) - 0.5·(-1) = 1). A pure group (p = 1 for one class) gives H = -1·log₂1 = -1·0 = 0 — zero uncertainty, zero questions needed.

Apply it to our root group of 8 players: 5 Selected (p = 5/8 = 0.625), 3 Not Selected (p = 3/8 = 0.375).

H(root) = -(0.625 · log₂0.625 + 0.375 · log₂0.375)
        = -(0.625 · (-0.678) + 0.375 · (-1.415))
        = 0.4238 + 0.5306
        = 0.9544 bits

So on average you'd need just under one more yes/no question to know whether a random player from this group of 8 was selected. That 0.9544 is our baseline. Every candidate question we could ask next will be judged by how much it reduces this number.

3. Information gain: choosing the best question

When we split the 8 players into two groups using a question, each resulting group has its own, hopefully lower, entropy. Information gain is the entropy we started with, minus the entropy left over after the split (weighted by how large each resulting group is):

IG(S, question) = H(S) - Σ (|Sᵥ| / |S|) · H(Sᵥ)

where each Sᵥ is one branch created by the question. Let's compute this for all three candidate questions.

Question: Avg > 40? Splits the 8 players into {1,2,3,4} (all Selected) and {5,6,7,8} (1 Selected, 3 Not).

H(Avg=Y) = H(4 Selected, 0 Not) = 0        (perfectly pure!)
H(Avg=N) = H(1 Selected, 3 Not) = -(0.25·log₂0.25 + 0.75·log₂0.75)
         = -(0.25·(-2) + 0.75·(-0.415)) = 0.5 + 0.3113 = 0.8113

IG(Avg) = 0.9544 - (4/8·0 + 4/8·0.8113) = 0.9544 - 0.4056 = 0.5488 bits

Question: SR > 130? Splits into {1,2,5,6} (3 Selected, 1 Not) and {3,4,7,8} (2 Selected, 2 Not).

H(SR=Y) = H(3,1) = 0.8113   (same shape as above)
H(SR=N) = H(2,2) = 1        (maximum uncertainty — a coin flip)

IG(SR) = 0.9544 - (0.5·0.8113 + 0.5·1) = 0.9544 - 0.9056 = 0.0488 bits

Question: Temp = High? By the same arithmetic (splits into {1,3,5,7}: 3 Selected/1 Not, and {2,4,6,8}: 2 Selected/2 Not), IG(Temp) = 0.0488 bits too.

Avg>40 gains more than ten times as much information as either other question (0.5488 vs 0.0488 bits) — and it produces one perfectly pure branch outright. A greedy tree-building algorithm (this specific procedure is called ID3) always asks the highest-information-gain question first, so Avg>40 becomes the root of the tree, exactly matching a selector's real instinct that domestic run-scoring consistency matters most.

The Avg=Yes branch is already pure (4/4 Selected) — that becomes a leaf, no further questions needed. The Avg=No branch {5,6,7,8} still has entropy 0.8113, so we recurse: repeat the entire information-gain calculation using only these four rows. Splitting this subset on SR>130 gives {5,6} (1 Selected, 1 Not; H=1) and {7,8} (0 Selected, 2 Not; H=0), for IG = 0.8113 - (0.5·1 + 0.5·0) = 0.3113 bits — splitting on Temp gives an identical 0.3113 by the same symmetry, so we take SR>130 (ties are broken by earlier feature order). The SR=No branch {7,8} is pure — a "Not Selected" leaf. The SR=Yes branch {5,6} still has one Selected and one Not Selected, so we ask the last remaining question, Temp=High, which separates player 5 (Selected) from player 6 (Not Selected) perfectly — two final pure leaves, IG = 1 full bit, and no rows left to split further. The tree is complete:

4. The other impurity measure: Gini index

ID3 and its successor C4.5 use entropy. A different, equally common algorithm called CART (Classification and Regression Trees — this is what scikit-learn's DecisionTreeClassifier uses by default) measures impurity with the Gini index instead:

Gini(S) = 1 - Σ pᵢ²

For our root group (p = 5/8 Selected, 3/8 Not):

Gini(root) = 1 - ((5/8)² + (3/8)²) = 1 - (0.3906 + 0.1406) = 0.4688

Gini has an intuitive reading too: it's the probability you'd misclassify a randomly picked row if you labelled it by randomly guessing according to the group's own class proportions. Entropy and Gini nearly always rank candidate questions the same way (Gini(Avg=Y)=0, Gini(Avg=N)=1-(0.25²+0.75²)=0.375, giving the same Avg>40 root here too) because both are concave functions that are zero exactly when a group is pure and maximal exactly at a 50-50 split — they just curve slightly differently in between. Gini avoids computing logarithms, which is why CART, tuned for speed on huge datasets, prefers it; the resulting trees are very rarely different in practice.

5. Verifying the tree in code

from sklearn.tree import DecisionTreeClassifier

# columns: [Avg>40, SR>130, Temp=High]   1 = Yes, 0 = No
X = [[1,1,1],[1,1,0],[1,0,1],[1,0,0],
     [0,1,1],[0,1,0],[0,0,1],[0,0,0]]
y = [1,1,1,1,1,0,0,0]          # 1 = Selected, 0 = Not Selected

clf = DecisionTreeClassifier(criterion="entropy", random_state=0)
clf.fit(X, y)

# a new player: Avg>40 = No, SR>130 = Yes, Temp = High
new_player = [[0, 1, 1]]
print(clf.predict(new_player))          # [1]  -> matches player 5's pattern exactly
print(clf.score(X, y))                  # 1.0  -> fits all 8 training rows perfectly

Trace it by hand against the tree we built: the new player fails Avg>40 (goes right), passes SR>130 (goes right again), and has Temp=High (goes left) — landing exactly on the "SELECTED, Player 5" leaf. Since new_player is in fact identical to row 5 of our own training table, and every one of the 8 rows is a distinct combination of three binary features, the tree can and does reproduce all 8 labels without contradiction — clf.score returns 1.0 because our hand-computed tree fits the training table with zero errors, which is itself the warning sign for the next section.

6. Misconception #1: information gain isn't "fair" to every feature

A dangerous flaw hides inside plain information gain. Imagine adding a fourth column to our table: a unique Player ID (1 through 8). Splitting on Player ID creates eight branches, each containing exactly one row — every single branch is perfectly pure, so H after the split is 0, giving IG = 0.9544 - 0 = 0.9544 bits, the maximum possible gain, higher than Avg>40's 0.5488! A naive ID3 implementation would happily pick Player ID as the root split. This is obviously useless — a "rule" that memorizes one player per branch tells you nothing about a ninth player. The bias is structural: information gain rewards questions with many possible answers, because more branches means more chances to isolate single rows into pure leaves.

The real fix (used in C4.5) is gain ratio: divide information gain by the entropy of the split itself — GainRatio = IG / SplitInfo, where SplitInfo = -Σ(|Sᵥ|/|S|)·log₂(|Sᵥ|/|S|) measures how many, and how unevenly sized, the branches are. Player ID, splitting 8 rows into eight singleton branches, has SplitInfo = log₂8 = 3 — a huge penalty — dragging its gain ratio down to 0.9544/3 ≈ 0.318, well below Avg>40's ratio of 0.5488/1 = 0.5488 (Avg>40 splits an even 4-4, so SplitInfo = 1). Whenever you see a categorical feature with many unique values in real data — a phone number, a pincode, a jersey number — treat unpenalized information gain on it with suspicion.

7. Why a single tree overfits

Our hand-built tree scored 8/8 on its own training data — impressive until you realize that's exactly the problem. A tree is allowed to keep splitting until every leaf is pure, which means it can carve out a rule to explain literally any noisy row, including the ones caused by a selector's bad day or a fluke domestic season. If a ninth player has Avg>40 = No, SR>130 = Yes, Temp = High, and gets selected only because of a wildcard reason our tree never saw (say, a specialist death-overs bowling skill), a fully-grown tree that has memorized only three features will still confidently, and possibly wrongly, classify him by whatever pattern happened to fit the training eight. This is called overfitting: low error on training data, high error on new data, because the tree fit noise, not signal. The usual fixes — capping tree depth, requiring a minimum number of rows per leaf, or pruning branches that don't improve accuracy on held-out data — all trade a little training accuracy for a lot of generalization. But there's a more powerful fix that doesn't require choosing a depth limit at all: stop relying on one tree.

8. Bootstrap sampling: the "bagging" in Random Forest

A Random Forest trains many decision trees, each on a slightly different dataset drawn from the same original data, then lets them vote. Each tree's dataset is a bootstrap sample: draw n rows with replacement from the original n rows, so some rows appear two or three times and others don't appear at all.

How much of the original data does a typical bootstrap sample actually leave out? The probability a specific row is not chosen on one draw is (n-1)/n. Since we draw n times independently (with replacement), the probability that row is missed in all n draws is:

P(row never chosen) = (1 - 1/n)ⁿ

Using the standard calculus limit lim_n→∞ (1 + x/n)ⁿ = eˣ with x = -1:

lim(n→∞) (1 - 1/n)ⁿ = e⁻¹ ≈ 0.368

So for reasonably large n, about 36.8% of the original rows are left out of any given bootstrap sample — these are called out-of-bag (OOB) rows for that tree. Because each tree never saw its own OOB rows during training, testing that tree on them gives an honest, free estimate of generalization error — no separate validation set needed. This is a genuine, provable property of sampling with replacement, not a rule of thumb.

9. Misconception #2: "Random Forest" isn't just many trees on random data

The most common misunderstanding is thinking a Random Forest is simply many decision trees, each trained on a different bootstrap sample, with their votes averaged. That alone is called bagging, and it is not enough — because in our cricket data, Avg>40 dominates so strongly (IG = 0.5488, more than ten times its rivals) that almost every bootstrap sample would still pick Avg>40 as its root split. The resulting trees would all look nearly identical near the top, differing only in minor details lower down — highly correlated trees. And correlated votes don't cancel out noise the way independent votes do.

Random Forest's actual second ingredient — the "random" — is this: at every single split, each tree is only allowed to consider a random subset of the features, not all of them. For a dataset with p total features, a classification forest typically samples √p features at each split (regression forests typically use p/3). With only three features in our toy example, a Random Forest tree might be forced to choose its root split from just {SR>130, Temp=High} — deliberately forbidden from using Avg>40 at that node even though it's the strongest predictor. This forced restriction is precisely what decorrelates the trees.

Here is why decorrelation matters, with the actual variance algebra. Suppose we average B trees, each an unbiased estimator with variance σ², and each pair of trees has the same correlation ρ with each other. Using Var(X+Y) = Var(X) + Var(Y) + 2·Cov(X,Y), and Cov(Xᵢ,Xⱼ) = ρσ² for any pair i≠j:

Var(ΣXᵢ) = Σᵢ Var(Xᵢ) + Σ_{i≠j} Cov(Xᵢ,Xⱼ)
         = B·σ² + B(B-1)·ρσ²

Var(mean) = Var(ΣXᵢ) / B²
          = σ²/B + ((B-1)/B)·ρσ²

Now let B → ∞ (imagine an enormous forest). The first term σ²/B vanishes, but the second term (B-1)/B approaches 1, so:

Var(mean) → ρσ²    as B → ∞

This is the entire argument in one line: adding more trees can only ever shrink the forest's variance down to ρσ² — never below it. If your trees are highly correlated (ρ close to 1, as plain bagging alone would produce here), a thousand trees give you barely more protection against noise than ten. The random-feature-subset step exists specifically to push ρ down, so that ρσ² — the floor the forest's variance can never go below — is genuinely small. This is precisely why a bagging-only forest is a strictly weaker algorithm than a true Random Forest, and it is the single fact this section wants you to be able to reproduce and explain, not just quote.

10. From cricket to the clinic: patient diagnosis

The same machine now works on a hospital's triage desk. Instead of {Avg>40, SR>130, Temp=High}, the features become patient measurements: fever above 100.4°F, persistent cough, resting oxygen saturation below 94%, breathlessness on exertion, recent travel or contact history. Instead of "Selected/Not Selected," the label is a diagnosis category needing urgent review or not. A single decision tree here has exactly the overfitting risk our cricket tree had — it might latch onto some coincidental combination in the training patients (say, a specific age plus a specific symptom pairing that happened to co-occur by chance in the hospital's limited historical records) and apply that pattern confidently to a patient it has no real basis for judging. A Random Forest of, say, 200 such trees, each trained on a bootstrap sample of past patients and restricted to a random handful of symptoms per split, votes instead — and because the trees are decorrelated by construction, their majority vote washes out exactly the kind of coincidental single-tree pattern that caused the overfitting risk. This is also why Random Forests are commonly used, alongside other models, to rank feature importance in screening tools: by measuring how much each feature's presence in a tree's splits reduces impurity, averaged across all trees in the forest, clinicians get a data-driven signal of which symptoms are actually carrying diagnostic weight versus which ones are just noise the forest has already learned to discount.

11. Algorithmic cost, and where this sits in your exams

Building one decision tree of depth d over n training rows and p features costs roughly O(n·p·d) in the worst case — at each of the O(d) levels, evaluating every feature's best split point requires scanning (and typically pre-sorting) all n rows, giving an O(n·p) cost per level; for a reasonably balanced tree d ≈ log n, so total cost is often written O(n·p·log n). A Random Forest of B such trees costs roughly B times that per tree, but since each tree only searches a random subset of √p features per split, the constant per tree actually shrinks even as B grows — one reason Random Forests parallelize well (each tree can be built on a separate core, since bootstrap samples are independent of each other).

Within CBSE's Artificial Intelligence (Code 843) and Computer Science curricula, decision trees and classification are core topics, and this entropy/information-gain computation is exactly board-exam material. At the competitive level, this is squarely GATE's Data Science and AI (DA) paper syllabus — entropy, Gini index, and ensemble methods appear directly. Note honestly: JEE Main/Advanced and BITSAT do not test machine learning algorithms — their syllabi are physics, chemistry, and mathematics — so don't expect a decision-tree question there; if you're preparing for a computing olympiad, the transferable skill is the recursive tree-construction algorithm itself (a clean example of a greedy, recursive divide-and-conquer procedure) and its complexity analysis above.

12. Check your understanding

1. A group of 10 patients has 6 labelled "needs review" and 4 labelled "routine." Compute H(S) for this group, showing your log₂ calculation (you should get something close to, but not exactly, 1 bit — explain in one sentence why it's below 1 rather than above).
2. Splitting those same 10 patients on "fever above 100.4°F?" gives one branch of 5 patients (5 needs-review, 0 routine) and another branch of 5 patients (1 needs-review, 4 routine). Compute the information gain of this split and state, using the number, whether this is a stronger or weaker root question than our cricket example's Avg>40 split.
3. Explain, in your own words and without saying "it's more random," exactly what a plain bagging forest (bootstrap sampling only, no random feature subsets) would do differently from a true Random Forest on a dataset where one feature has an information gain ten times larger than every other feature — and why that difference matters for the variance formula Var(mean) → ρσ².
4. Using the OOB derivation, if a bootstrap sample is drawn from n = 500 patients, roughly how many distinct patients (not draws) do you expect to appear in that sample at least once? (Hint: use the 63.2% figure, not 36.8%.)
5. A dataset has a "Patient Registration Number" column, unique to every row. Explain why plain information gain would rate this column as an excellent root split, and name the exact quantity that gain ratio divides by to correct this.

Summary

A decision tree turns a table of yes/no facts into a flowchart of questions, chosen greedily by whichever question most reduces entropy (or Gini index) at each step — information gain is that reduction, computed exactly as H(parent) minus the row-weighted average of H(children). Left unchecked, a tree happily grows until every leaf is pure, which makes it fit its training rows perfectly and, for the same reason, unreliably on new ones; plain information gain also mis-ranks any feature with many unique values, which gain ratio corrects. A Random Forest survives both problems by voting across many trees, each grown on a bootstrap sample (leaving ~36.8% of rows out-of-bag for free validation) and each restricted, at every split, to a random subset of features — a restriction that is not optional decoration but the entire mechanism that keeps the trees' votes statistically decorrelated, which the variance formula Var(mean) = σ²/B + ((B-1)/B)ρσ² proves is the only thing standing between "more trees" and "more of the same mistake."