Decision tree induction
Decision tree induction: principles (entropy, impurity), attribute selection (information gain, gain ratio, Gini), handling continuous/missing data, pruning, algorithms (ID3, C4.5, CART) with worked traces and exam tips.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Decision trees are a simple, interpretable method engineers use to build classifiers from labeled data. They are used in systems that require readable rules (fault diagnosis, feature engineering, decision support) and as base learners inside ensemble methods (bagging, boosting).
Key ideas
Start simple from first principles.
Decision tree: a flowchart-like tree where each internal node tests an attribute, each branch corresponds to an attribute value (or range), and each leaf assigns a class (label). Use when we want a readable model mapping instances (attribute vectors) to classes.
Instance / Example: a record with values for attributes and a class label.
Attribute (feature): a named variable used for splitting. Attributes are categorical (finite values) or continuous (numeric).
Pure node: a node is pure when all instances in it have the same class. A pure node is a leaf.
Impurity measure: a function that measures the disorder of class labels at a node. Common measures: entropy, Gini index, misclassification error.
Entropy (for a set S with c classes): Definition: entropy H(S) = - Σ_{i=1..c} p_i log2 p_i, where p_i is the fraction of examples in S of class i. Entropy is 0 when node is pure, maximum when classes are uniformly distributed.
Expected information after a split: if attribute A divides S into subsets S_v (one for each value v), expected information is H_A(S) = Σ_v (|S_v|/|S|) H(S_v).
Information gain: Gain(S, A) = H(S) - H_A(S). Select attribute with maximum gain (ID3 uses this). Gain measures reduction in entropy.
Derivation (common exam request): start from H(S). After splitting by A, average remaining entropy is the weighted sum H_A(S). Reduction = H(S) - H_A(S). Show algebra of weighted sum to arrive at formula above.
Bias of information gain: IG prefers attributes with many values. To correct, gain ratio (used in C4.5) divides IG by the split information: GainRatio(S, A) = Gain(S, A) / SplitInfo(S, A), where SplitInfo = - Σ_v (|S_v|/|S|) log2(|S_v|/|S|).
Gini index (used by CART): Gini(S) = 1 - Σ_i p_i^2. For a split, Gini gain = Gini(S) - Σ_v (|S_v|/|S|) Gini(S_v). CART grows binary trees (two-way splits) and chooses splits minimizing weighted Gini impurity.
Handling continuous attributes: convert to binary test A <= t? vs A > t? Choose threshold t by sorting distinct values and evaluating candidate thresholds at midpoints between consecutive values where class label changes. Select t maximizing IG (or minimizing Gini).
Missing values: common strategies: (1) ignore the example for that attribute when computing splits, (2) treat "missing" as a separate attribute value, (3) distribute example fractionally across branches proportional to branch probabilities (used in C4.5).
Stopping criteria: stop when node is pure, or when no attributes remain, or when number of instances < min_samples, or maximum tree depth reached, or splitting gives no significant gain.
Overfitting and pruning: large trees can memorize noise. Pre-pruning stops growth early (min samples, min gain). Post-pruning grows full tree then prune subtrees if pruning reduces expected error (reduced-error pruning) or by cost-complexity methods (CART uses cost-complexity pruning with a parameter α balancing tree size vs error).
Complexity: building a full tree with n examples and d attributes can be O(d n log n) total if numeric attributes are presorted; without presorting a naive implementation can be O(d n^2). For categorical attributes with at most k values, evaluating a split at a node is O(n k). Greedy search is local and not guaranteed globally optimal (finding the optimal tree of bounded size is NP-hard).
Algorithms: ID3: categorical attributes, IG, no pruning. C4.5: handles continuous attributes, missing values, uses gain ratio and post-pruning (pessimistic error pruning with a confidence factor). CART: binary splits, uses Gini, supports regression trees too.
Diagram to draw (exam): draw a binary decision tree with a root node labelled "A" with two branches labelled "A=Yes" and "A=No"; on left leaf label "Class=Positive (3/3)" and on right show an internal node labelled "B" splitting into leaves with class labels and instance counts; annotate that internal nodes are tests, leaves are class outputs, branch labels are test outcomes.
Formulas
H(S) = - Σ_{i=1..c} p_i · log2(p_i) where p_i = |S_i| / |S|, a unitless probability. Applies to any node S for c classes.
Gain(S, A) = H(S) - Σ_v (|S_v| / |S|) · H(S_v) where S_v are subsets after splitting on attribute A.
SplitInfo(S, A) = - Σ_v (|S_v| / |S|) · log2(|S_v| / |S|) (unitless). Used in gain ratio.
GainRatio(S, A) = Gain(S, A) / SplitInfo(S, A) (unitless; guard against SplitInfo=0).
Gini(S) = 1 - Σ_{i=1..c} p_i^2 (unitless). For binary class with p positive = p, Gini = 2p(1-p).
GiniGain(S, A) = Gini(S) - Σ_v (|S_v|/|S|) · Gini(S_v) (unitless). Applies to CART-like selection.
Error_rate(S) = 1 - max_i p_i (misclassification error at node S; unitless). At a leaf, predict the majority class; probability estimates can use class frequencies with Laplace correction.
For continuous attribute splitting: candidate thresholds t are midpoints (x_i + x_{i+1})/2 after sorting unique x values; evaluate Gain(S, A <= t).
Worked examples
Example 1 — categorical attributes; choose root by information gain. Data (6 instances): attributes A ∈ {Yes, No}, B ∈ {High, Low}, Class ∈ {Positive, Negative} 1: A=Yes, B=High, Class=Positive 2: A=Yes, B=High, Class=Positive 3: A=No, B=High, Class=Negative 4: A=No, B=Low, Class=Negative 5: A=No, B=Low, Class=Positive 6: A=Yes, B=Low, Class=Positive
Step 1: compute H(S). Positives = 4, Negatives = 2, |S|=6.
H(S) = - (4/6)·log2(4/6) - (2/6)·log2(2/6) = 0.918295 bits.
Step 2: Gain for A. A=Yes: 3 instances (all Positive) so H=0. A=No: 3 instances (1 Positive, 2 Negative) so H = 0.918295. Weighted H_A = (3/6)·0 + (3/6)·0.918295 = 0.4591475.
Gain(S,A) = 0.918295 - 0.4591475 = 0.4591475 bits.
Step 3: Gain for B. B=High: 3 instances (2 Pos, 1 Neg) H=0.918295. B=Low: 3 instances (2 Pos, 1 Neg) H=0.918295. Weighted H_B = 0.918295.
Gain(S,B) = 0.918295 - 0.918295 = 0.0 bits.
Conclusion: choose attribute A as root (highest information gain). Final answer: root = A with Gain = 0.45915 bits (rounded).
Example 2 — continuous attribute splitting; choose best threshold. Data (6 instances): X values and class (2, Neg), (3, Neg), (5, Pos), (7, Pos), (9, Pos), (10, Neg)
Step 1: H(S) with 3 Pos, 3 Neg -> H(S) = 1.0 bit.
Step 2: candidate thresholds are midpoints between consecutive X values where labels change: 4 and 9.5. (If you also test all midpoints 2.5, 4, 6, 8, 9.5 you will get the same best t but do extra work.) Evaluate Gain for each. (Full arithmetic shown in key ideas; here condensed.)
- t=2.5: left 1 example (Neg) H_left=0, right H_right=0.97095 -> weighted H=0.809125 -> Gain=0.190875
- t=4: left 2 examples (both Neg) H_left=0, right 4 examples (3 Pos,1 Neg) H_right=0.811278 -> weighted H=0.540852 -> Gain=0.459148
- t=6: left 3 examples (2 Neg,1 Pos) H_left=0.918295, right 3 examples (2 Pos,1 Neg) H_right=0.918295 -> weighted H=0.918295 -> Gain=0.081705
- t=8: Gain=0.0
- t=9.5: symmetric to 2.5 -> Gain=0.190875
Conclusion: choose threshold t = 4 (between 3 and 5) with information gain ≈ 0.45915 bits.
(These calculations should be rechecked by the reviewer; see verify list.)
Common mistakes
- Using information gain directly without considering split information (gain ratio) for high-cardinality attributes.
- For continuous attributes, testing thresholds at every value instead of midpoints between distinct sorted values (extra work but equivalent if done correctly).
- Miscounting class frequencies when calculating p_i (off-by-one errors).
- Not handling ties or zero split-information safely (division by zero in gain ratio).
For your exam
Typical question types:
- Definitions and short notes (define entropy, information gain, Gini index, pruning). Include formulas and intuition.
- Derivations: derive Gain(S,A) from entropy and expected post-split entropy.
- Numerical: compute entropy and information gain on a small dataset and pick root; compute best numeric split threshold.
- Algorithms: describe ID3/C4.5/CART differences and pruning methods; draw a decision tree for given data.
- Programs/pseudocode: give greedy tree induction pseudocode (split by best attribute, recurse).
Full-mark answers include: clear definitions (bold the term), formula stated and symbols explained, step-by-step arithmetic for numericals with counts and intermediate results shown, diagram drawn and labelled if required, and discussion of assumptions (e.g., attributes independent in naive Bayes is different topic — just mention relation to ensembles or others).
Quick check
- What is the entropy of a node with class distribution [3 positive, 1 negative]?
- Which impurity measure does CART use?
- How do you choose candidate thresholds for a numeric attribute when building a decision tree?
Answers: 1) 0.811278 bits (H = -0.75·log2 0.75 - 0.25·log2 0.25). 2) Gini index. 3) Sort distinct values and take midpoints between consecutive values where class labels differ; evaluate gain for each midpoint.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?