Decision Trees and Ensembles
A tree splits the data one question at a time, choosing each split to make the resulting groups purer. One tree is easy to read and unstable; averaging many trees grown on resampled data usually trades that readability for accuracy.
What a learner can do afterwards
- Choose the first split of a small dataset using an impurity measure
- Construct before-and-after tree questions to show how changing training labels can change a tree's structure
- Explain how combining trees can reduce sampling variation when their errors differ
1 · Read
A decision tree sorts data by asking yes or no questions, one at a time. Imagine sorting fruit. First ask whether it is round, then whether it is red. Each answer sends the fruit down a different branch until it lands in a final group, like apple or banana. To classify something new, follow the same questions and branches to its group.
Entropy H is 0 for a pure group, about 0.811 for a 1:3 mix, 0.918 for 1:2, and 1 for 1:1. Swapping labels keeps H. For each split, add (group size / total) times H for both groups. Lower wins since the parent is the same. With 3 apples and 3 bananas, A gives 2 apples alone and 1 apple with 3 bananas: (2/6) times 0 + (4/6) times 0.811 = 0.541. B gives 2:1 and 1:2 groups: 0.918. Choose A; repeat within mixed groups.
Multiply each child entropy by its share of the rows, then add. The lower score gives the larger drop.
One tree is easy to read, but it can be twitchy. Change a few rows of training data and the whole tree can grow a different shape and give different answers. That instability is variance, the same swing from sample to sample you met with overfitting, and it is the price of letting a single tree chase every detail of its training rows.
A random forest trains each tree on a bootstrap sample drawn randomly with replacement. Samples usually differ but can coincide. Random feature subsets at splits help trees ask different questions. For two-class classification with an odd number of trees, each tree casts one vote and the majority wins. Combining trees can reduce sampling variation when their errors differ. Forests often improve accuracy and steadiness, but neither gain is guaranteed. Many trees are harder to explain than one.
Try thresholds halfway between adjacent x values. Choose lowest weighted entropy; break ties with the smaller threshold. With x=1,2,3,4 and labels A,A,B,B, ask x<2.5: yes A, no B. Change two labels to A,B,A,B. The root ties at 1.5 and 3.5, so use 1.5: yes A; on no ask x<2.5: yes B; on no ask x<3.5: yes A, no B. Pure groups become leaves; split mixed groups again. Two label edits changed one question into three.
Compare size-weighted child entropy. Small data edits can change a tree's branches. Combining resampled trees can steady predictions, but improvement is not guaranteed.
The readings on entropy-based splits and combining decision trees were written for this dataset.
More to read
Choosing branches with entropy
A decision tree predicts a category by following answers to branching questions until it reaches a leaf. Training chooses the questions by comparing how mixed the resulting groups are.
For two categories, use these rounded entropy values: a pure group has H=0; a 1:3 or 3:1 mix has H about 0.811; a 1:2 or 2:1 mix has H about 0.918; equal shares have H=1. These lookup values let you compare the examples here without calculating logarithms.
For each candidate split, multiply every child group's entropy by its fraction of the parent rows, then add the results. The parent entropy is the same for every candidate, so the smallest weighted child score gives the greatest reduction.
For 3 apples and 3 bananas, one split produces 2 apples alone and a group of 1 apple with 3 bananas. Its weighted score is (2/6) times 0 + (4/6) times 0.811, about 0.541. Another split produces groups of 2 apples with 1 banana and 1 apple with 2 bananas. Both children have entropy about 0.918, so their weighted score is also about 0.918. Choose the first split.
Apply the comparison again within mixed children. Pure children can become leaves. A completed tree classifies a new example by following its answers through the chosen questions.
Combining trees to reduce unstable predictions
You can trace a prediction through one tree, but that tree may be sensitive to its training sample. Altering a few records can change its branches and predictions substantially.
Random forests combine trees to reduce this variation. Bootstrap sampling draws training rows randomly and allows a row to appear more than once. Separate draws usually give the trees different training samples. Random feature subsets at splits help make their errors less alike.
For the two-class, odd-tree setting used in this lesson, collect one category vote from each tree. One category must receive more than half the votes, so use that majority as the prediction. Averaging predictions or votes can reduce variance when the trees' errors are not perfectly correlated. A forest is therefore often steadier and more accurate than an individual tree. Combining people's estimates can help for a similar reason when their errors differ, but neither improvement is guaranteed.
Naive Bayes is another classification method that uses probabilities. With a small dataset, you can practise training several resampled trees, combining their classifications and explaining why their combined answer may be more reliable.
2 · Watch
به انگلیسیTake it off screen
Where it sits
Learn first
Optional connections
This opens up
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.