Introduction
A classification tree turns a sequence of questions about predictors into a class prediction. To build one by hand, start with all labelled training cases at the root, compare admissible splits, and select a split that reduces impurity. Then repeat the comparison within each resulting node, subject to the chosen stopping rules. At the end, each terminal node, or leaf, summarizes the cases that reach it.
The calculations have two distinct purposes. Impurity reduction guides which question to ask at a node; the class proportions at a leaf describe the labelled cases that reached it. The leaf prediction is usually the most frequent class, but a predicted class is not the same thing as the full set of class proportions.
This tutorial uses Gini impurity for its hand calculations. For class proportions \(p_1,\ldots,p_K\) at a node, Gini impurity is \(1-\sum_{k=1}^{K}p_k^2\). It is zero when all cases belong to one class and larger when the classes are more evenly represented. The same construction process can use another impurity measure, such as entropy, provided the measure is used consistently when comparing candidate splits.
How to Choose and Apply a Split
A candidate split divides the cases in a node into two or more child groups. For a binary predictor, the split may separate its two values. For a categorical predictor with more values, an admissible split may group levels into subsets. For a numeric predictor, a threshold \(c\) divides cases according to whether the predictor is at most \(c\) or greater than \(c\). Only the cases reaching the current node are used in its split calculation.
If a node has \(n\) cases and its split creates \(J\) children, let \(n_j\) be the number of cases in child \(j\), and let \(G_j\) be that child’s Gini impurity. The weighted impurity after splitting is the average child impurity, weighted by the fraction of cases in each child. The gain is the parent impurity minus this weighted value.
The weighting follows directly from considering a randomly selected training case from the parent node. The probability that it enters child \(j\) is \(n_j/n\). If it enters that child, the child’s impurity is \(G_j\). Thus the expected impurity after the split is the sum of each child’s impurity multiplied by its probability of receiving the case. A larger gain means a greater reduction in this expected impurity. A split with gain zero does not improve the chosen impurity measure.
Count its cases by class and calculate its impurity.
For each candidate, count the classes in every child and calculate the weighted child impurity and gain.
Select the candidate with the greatest gain, using a stated tie rule if needed.
Apply the stated stopping rule separately at each child. At every leaf, calculate class proportions and record the predicted class.
Worked Construction from Categorical Predictors
Worked Example: Comparing Root Splits and Growing Both Branches
A hypothetical insurer labels eight historical claim files as class A or class B and records two categorical predictors, \(X\) and \(Z\). The table shows every case. Use Gini impurity, first compare \(X\) and \(Z\) at the root, and then split each non-pure child if an available predictor gives a positive gain. If a leaf has a tie, predict class A.
| Case | \(X\) | \(Z\) | Class |
|---|---|---|---|
| 1 | Red | Low | A |
| 2 | Red | Low | A |
| 3 | Red | High | A |
| 4 | Red | High | B |
| 5 | Blue | Low | B |
| 6 | Blue | Low | B |
| 7 | Blue | High | A |
| 8 | Blue | High | B |
Step 1: Calculate root impurity. There are four A cases and four B cases, so \(p_A=p_B=4/8=1/2\). The root Gini impurity is \(1-(1/2)^2-(1/2)^2=1/2\).
Step 2: Evaluate the split on \(X\). The Red child has three A cases and one B case, so its impurity is \(1-(3/4)^2-(1/4)^2=6/16=3/8\). The Blue child has one A and three B, also giving impurity \(3/8\). Each child contains four of the eight cases. The weighted impurity is \((4/8)(3/8)+(4/8)(3/8)=3/8\), and the gain is \(1/2-3/8=1/8\).
Step 3: Evaluate the split on \(Z\). Low contains two A and two B; High also contains two A and two B. Each child has impurity \(1/2\). The weighted impurity is \((4/8)(1/2)+(4/8)(1/2)=1/2\), so the gain is \(1/2-1/2=0\). Choose \(X\) at the root because its gain is larger.
Step 4: Split the Red child on \(Z\). Among the four Red cases, Low contains two A and no B, with impurity zero. High contains one A and one B, with impurity \(1/2\). The weighted impurity within this node is \((2/4)(0)+(2/4)(1/2)=1/4\). Its parent impurity was \(3/8\), so the gain is \(3/8-1/4=1/8\). The Low leaf has proportions \(2/2=1\) for A and \(0/2=0\) for B, and predicts A. The High leaf has proportions \(1/2\) and \(1/2\), so the stated tie rule predicts A.
Step 5: Split the Blue child on \(Z\). Blue-Low contains two B and no A, giving impurity zero. Blue-High contains one A and one B, giving impurity \(1/2\). The weighted impurity is again \((2/4)(0)+(2/4)(1/2)=1/4\), and the gain is \(3/8-1/4=1/8\). Blue-Low predicts B with proportions \(0/2\) for A and \(2/2\) for B. Blue-High has proportions \(1/2\) for each class and predicts A by the tie rule.
The resulting paths are \(X=\text{Red}, Z=\text{Low}\) (predict A), \(X=\text{Red}, Z=\text{High}\) (predict A by tie), \(X=\text{Blue}, Z=\text{Low}\) (predict B), and \(X=\text{Blue}, Z=\text{High}\) (predict A by tie). The method is repeated at each child, not just at the root. The common mistake to avoid is to treat a root split as the entire tree, leaving the mixed Red and Blue nodes unexamined even though \(Z\) can split them.
Worked Construction with a Numeric Threshold
Worked Example: Choosing a Threshold and Continuing Within a Child
A hypothetical claims team records a numeric inspection score and a categorical channel for six labelled claims. The target is whether a claim is approved. Use Gini impurity, consider thresholds midway between successive distinct scores, and choose the lower threshold if equally good numeric thresholds are tied.
| Score | Channel | Class |
|---|---|---|
| 1 | Red | No |
| 2 | Red | No |
| 3 | Red | Yes |
| 4 | Blue | No |
| 5 | Red | Yes |
| 6 | Red | Yes |
Step 1: Establish parent impurity and candidates. There are three Yes and three No cases, so the root impurity is \(1-(3/6)^2-(3/6)^2=1/2\). The possible score thresholds are \(1.5,2.5,3.5,4.5,\) and \(5.5\).
Step 2: Calculate threshold gains. At \(1.5\), the left child is pure No and the right child has three Yes and two No, with impurity \(1-(3/5)^2-(2/5)^2=12/25\). Weighted impurity is \((1/6)(0)+(5/6)(12/25)=2/5\), giving gain \(1/10\). At \(2.5\), the left child has two No and impurity zero; the right child has three Yes and one No, with impurity \(1-(3/4)^2-(1/4)^2=3/8\). Weighted impurity is \((2/6)(0)+(4/6)(3/8)=1/4\), giving gain \(1/4\).
At \(3.5\), the two children each have one class represented once and the other twice, so each has impurity \(1-(1/3)^2-(2/3)^2=4/9\). Weighted impurity is \(4/9\), giving gain \(1/2-4/9=1/18\). At \(4.5\), the left child has three No and one Yes, giving impurity \(3/8\), while the right child is pure Yes. Weighted impurity is \((4/6)(3/8)+(2/6)(0)=1/4\), so gain is \(1/4\). At \(5.5\), the left child has three No and two Yes, while the right child is pure Yes; weighted impurity is \((5/6)(12/25)=2/5\), and gain is \(1/10\).
Step 3: Check the categorical candidate. Red contains three Yes and two No, so its impurity is \(12/25\); Blue contains one No, so its impurity is zero. The weighted impurity is \((5/6)(12/25)+(1/6)(0)=2/5\), giving gain \(1/10\). The best gain is \(1/4\), achieved by thresholds \(2.5\) and \(4.5\). Apply the stated tie rule and choose the lower threshold, \(2.5\).
Step 4: Continue within the right child. The cases with score greater than \(2.5\) are scores 3, 4, 5, and 6: three Yes and one No, with impurity \(3/8\). Within this node, Red contains three Yes and no No, and Blue contains no Yes and one No. Splitting on channel gives weighted impurity zero and gain \(3/8\). The resulting leaves are pure: score at most \(2.5\) predicts No; score greater than \(2.5\) and Red predicts Yes; score greater than \(2.5\) and Blue predicts No.
Common calculation trap. For the root split at \(2.5\), an unweighted average of the two child impurities would be \((0+3/8)/2=3/16\), yielding the incorrect gain \(1/2-3/16=5/16\). The children have sizes two and four, not equal sizes. The correct weighted impurity is \((2/6)(0)+(4/6)(3/8)=1/4\), and the correct gain is \(1/2-1/4=1/4\).
Leaf Proportions, Predictions, and Stopping
A split determines how cases are routed; the leaf summarizes the cases that arrive by that route. For example, if a leaf contains two cases in one class and one in another, its empirical proportions are \(2/3\) and \(1/3\). Under ordinary majority-class prediction, it predicts the class with proportion \(2/3\). These proportions describe the training cases at the leaf; they should not automatically be interpreted as perfectly calibrated probabilities for future cases.
A tree does not have to split every mixed node. It stops when the specified stopping conditions apply, such as reaching a maximum depth, having too few cases to split, having no admissible predictors left, or finding no split that meets a required improvement criterion. Those conditions should be applied to the node being considered. A leaf can therefore remain mixed, and its proportions should still be recorded even when its predicted class is unambiguous.
Worked Example: Recording an Impure Leaf at a Stopping Limit
A hypothetical service team classifies six policy inquiries as Renew or Not Renew and records the contact channel. Suppose the tree is restricted to depth one, so it may split the root once but cannot split its children. The hypothetical cases yield these channel totals: Web has two Renew and one Not Renew; Agent has one Renew and two Not Renew.
Step 1: Calculate root impurity. The root has three cases of each class, so \(G_{\text{root}}=1-(3/6)^2-(3/6)^2=1/2\).
Step 2: Calculate the channel split. In each child, the class proportions are \(2/3\) and \(1/3\), in opposite class order. Each child has impurity \(1-(2/3)^2-(1/3)^2=4/9\). Since each child has three of the six cases, weighted impurity is \((3/6)(4/9)+(3/6)(4/9)=4/9\). The gain is \(1/2-4/9=1/18\), approximately \(0.0556\). With channel as the available predictor, the split is made, subject to the stated depth limit.
Step 3: Record both leaves. The Web leaf has Renew proportion \(2/3\) and Not Renew proportion \(1/3\), so it predicts Renew. The Agent leaf has Renew proportion \(1/3\) and Not Renew proportion \(2/3\), so it predicts Not Renew. The leaves remain impure because the depth-one rule prevents further splitting. The method separates the split decision from the leaf prediction: the gain chooses the split, while the largest class proportion determines each leaf’s predicted class.
Common Construction Errors
- Using the wrong denominator. At every node, proportions use the number of cases reaching that node, not the total number of cases in the original data set.
- Forgetting child sizes. The post-split impurity is a size-weighted average. It is an ordinary average only when all children have the same size.
- Choosing a split from one child alone. A root candidate is evaluated across all of its children; a strong result in one child does not erase impurity in another.
- Confusing a leaf’s class proportions with its prediction. Record all proportions, then state the predicted class. If the largest proportion is tied, specify and apply a tie rule.
- Continuing without respecting the stopping rule. A possible split is not automatically performed if the tree’s stated restrictions prohibit it.
Check Your Understanding
For each problem, use Gini impurity unless another instruction is stated. Answers are given at the end of each item for checking.
- A root has five cases in class A and three in class B. Calculate its Gini impurity. (Answer: \(15/32=0.46875\).)
- A node has six cases, four A and two B. A candidate split creates one pure child of three A cases and a second child with one A and two B. Find the weighted child impurity and gain. (Answer: weighted impurity \(2/9\); gain \(2/9\).)
- A leaf contains five cases: three are Approved and two are Declined. State both empirical class proportions and the majority-class prediction. (Answer: Approved \(3/5=0.6000\), Declined \(2/5=0.4000\); predict Approved.)
- A root has eight cases, five A and three B. A split creates a child of two A cases and a child of three A and three B cases. Calculate the split gain. (Answer: \(3/32=0.09375\).)
- A root has ten cases, six A and four B. Candidate split Q produces children with counts \((4A,1B)\) and \((2A,3B)\); candidate split R produces \((3A,1B)\) and \((3A,3B)\). Which split has the greater Gini gain, and by how much? (Answer: Q has gain \(0.0800\), R has gain \(0.0300\); choose Q, by a gain difference of \(0.0500\).)