COMP4318 · Machine Learning and Data Mining
Decision Trees & Ensembles
Week 5 covers decision-tree induction with entropy and information gain (and Gini as an alternative), pruning, then ensembles — bagging, boosting (AdaBoost and gradient boosting) and random forests. The information-gain calculation is a near-certain exam item, and the ensemble comparison (bagging vs boosting, naming a random forest from pseudocode) is a recurring short-answer. The homework quiz (h5) drills the entropy arithmetic.
What this chapter covers
- 01Top-down recursive divide-and-conquer tree induction; a node becomes a leaf when it is pure
- 02Entropy H(S) = −Σ pᵢ·log2(pᵢ) in bits (with log2(0) = 0); pure = 0, 50/50 = 1
- 03Information gain Gain(S,A) = H(S) − Σ (|Sᵢ|/|S|)·H(Sᵢ); pick the attribute with the highest gain
- 04Highly-branching-attribute bias and the gain-ratio fix; Gini index as CART's alternative purity measure
- 05Pruning: pre- vs post-pruning (post preferred), validated on a hold-out set
- 06Ensembles work when the base classifiers are accurate (error < 0.5 for binary) AND diverse
- 07Bagging (bootstrap samples, ~63% appear, parallel, equal weight) vs Boosting (sequential, reweight hard cases)
- 08AdaBoost (weighted vote by accuracy) and Gradient Boosting (each tree fits the residuals); Random Forest = bagging + a random feature subset per split
Entropy and information gain of a split
- +1Parent entropy: with 4 Play and 4 No, H(S) = −(4/8)log2(4/8) − (4/8)log2(4/8) = −0.5·(−1) − 0.5·(−1) = 1 bit (a 50/50 split is maximally impure).
- +1Split on Windy: Windy=No has 5 examples (4 Play, 1 No); Windy=Yes has 3 examples (0 Play, 3 No).
- +1Child entropies: H(Windy=No) = −(4/5)log2(4/5) − (1/5)log2(1/5) = 0.722 bits; H(Windy=Yes) = 0 (pure, all No).
- +1Weighted child entropy H(S|Windy) = (5/8)·0.722 + (3/8)·0 = 0.451 bits.
- +1Information gain = H(S) − H(S|Windy) = 1 − 0.451 = 0.549 bits.
Key terms
- Entropy
- H(S) = −Σ pᵢ·log2(pᵢ), the impurity of a set in bits (log2(0) taken as 0); 0 = pure, 1 = an even two-class split.
- Information gain
- Gain(S,A) = H(S) − Σ(|Sᵢ|/|S|)·H(Sᵢ), the drop in entropy from splitting on attribute A; trees pick the highest-gain attribute.
- Gini index
- CART's alternative purity measure to entropy; like entropy it is 0 for a pure node and larger for mixed nodes.
- Bagging
- Bootstrap aggregation: build M classifiers on M bootstrap samples (drawn with replacement) in parallel and combine by majority vote (average for regression); best for unstable learners like trees.
- Boosting (AdaBoost)
- Sequential ensembling that reweights the examples the previous model got wrong; AdaBoost increases misclassified weights and combines by a weighted vote based on each model's accuracy.
- Random Forest
- Bagging of unpruned decision trees with an added random subset of k features considered at each split; combined by majority vote and robust to overfitting.
Decision Trees & Ensembles FAQ
Entropy or Gini — does it matter which I use?
Both measure node impurity and usually pick similar splits; entropy (with information gain) is the ID3/C4.5 default and Gini is CART's measure. In this unit the information-gain calculation with entropy is the examinable routine, so master that; know Gini exists as CART's alternative and quote it if asked.
What's the difference between bagging and boosting?
Both combine many same-type learners by voting/averaging. Bagging builds them in parallel on independent bootstrap samples with equal weight, reducing variance. Boosting builds them sequentially, each focusing on the examples the previous got wrong, and combines by a performance-weighted vote — reducing bias as well. Random forest is bagging plus a random feature subset per split.
Why does an ensemble beat a single tree?
Because independent errors cancel. If the base classifiers are individually accurate (error below 0.5 for a binary problem) and diverse (their errors are not the same), the majority vote is more likely to be right than any single member — the ensemble error drops well below the individual error. Diversity is why bagging perturbs the data and random forests perturb the features.
How is the decision-tree question usually marked in the exam?
Method by method: computing the parent entropy, the child entropies, the weighted child entropy, and the gain each earn marks, plus a mark for interpreting the result (e.g. noting a pure child or choosing the best attribute). Show the entropy formula explicitly and keep the log base 2.
Exam move
Make the entropy/information-gain routine second nature: parent entropy, each child's entropy, the weighted sum, then the gain — always base-2, always with the minus sign, and note pure children (entropy 0) to save time. Rehearse comparing two candidate attributes' gains and choosing the larger. On the ensemble side, be able to write the bagging-vs-boosting contrast in one line and to name a random forest from its pseudocode plus two advantages. When the arithmetic slips, ask Sia to recompute a split with fresh counts and check your logs.
Working through Decision Trees & Ensembles in COMP4318? Sia is AskSia’s AI Machine Learning tutor — ask any COMP4318 Decision Trees & Ensembles question and get a clear, step-by-step explanation grounded in how COMP4318 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
