Stopping Rules for Classification Tree Growth

Why Classification Trees Need Stopping Rules

A classification tree can keep dividing its training observations into smaller groups as long as it can find eligible splits. Without constraints, this process may produce many small terminal nodes, including nodes whose apparent class purity reflects only a few observations. Stopping rules limit the tree while it is being grown: they specify when a node is not allowed to split further.

Three common restrictions are a maximum depth, a minimum node-size requirement, and a minimum impurity decrease. Each answers a different question. Depth controls how many levels the tree can have; a size rule prevents splits that create undersized children; an impurity rule requires a split to improve class separation enough to justify the added branches. A split must satisfy every applicable restriction.

Definition: A growth-stopping rule is a condition checked while constructing a tree that prevents a node from being split further when the condition is not met. A post-growth pruning procedure starts with a larger, already-grown tree and removes branches afterward. These are different stages: stopping limits which splits are made, while pruning removes splits that have already been made.

Three Restrictions on Further Splitting

For precise calculations, let a node $t$ contain $n_t$ training observations distributed among $K$ classes. Write $n_{tk}$ for the number of observations in class $k$, so the observed class proportion in that node is $p_{tk}=n_{tk}/n_t$. A candidate split sends the observations into children $t_1,\ldots,t_J$, where $n_{t_j}$ is the size of child $j$. The examples below use Gini impurity; the same stopping logic can be used with another specified impurity measure.

Definition: Under the Gini criterion, the impurity of a node $t$ is $$ I(t)=1-\sum_{k=1}^{K}p_{tk}^{\,2}. $$ For a candidate split, its weighted child impurity is $\sum_{j=1}^{J}(n_{t_j}/n_t)I(t_j)$. The local impurity reduction is the parent impurity minus this weighted child impurity. A minimum impurity-decrease rule permits the split only if its local reduction is at least the stated threshold.

Maximum depth. Depth counts the number of edges from the root to a node. For the convention used here, the root has depth 0, and a node at depth $d$ may be split only when $d<D_{\max}$. Its children then have depth $d+1$. Some software reports depth using a different convention, so a problem should be answered using its stated definition rather than an assumed one.

Minimum node size. A common rule requires each child created by a split to contain at least a specified minimum number of observations, often called the minimum leaf size or minimum bucket size. A different setting, sometimes called a minimum split size, instead requires the parent node to contain a specified number before it can be considered for splitting. These settings are not interchangeable. Unless stated otherwise, the examples here use a minimum child-node size.

Minimum impurity decrease. A split must reduce impurity by at least a specified amount. The threshold is applied to the reduction, not to the child impurity alone. In this tutorial it is a local, unscaled reduction; some implementations define a threshold using a reduction scaled by the size of the full training set. Always check which definition the problem gives.

Why the Weighted Reduction Is the Relevant Comparison

The child impurities must be weighted by child size because a split sends an observation to child $t_j$ with empirical proportion $n_{t_j}/n_t$. Giving a small child the same weight as a large child would not describe the average impurity of the observations after the split.

To see why the reduction formula follows, first note that the parent class proportion is the size-weighted average of the child proportions:

p_{tk}=\sum_{j=1}^{J}\frac{n_{t_j}}{n_t}p_{t_jk}.

Using Gini impurity, the difference between parent impurity and weighted child impurity is therefore

\begin{aligned} I(t)-\sum_{j=1}^{J}\frac{n_{t_j}}{n_t}I(t_j) &=\sum_{j=1}^{J}\frac{n_{t_j}}{n_t}\sum_{k=1}^{K}p_{t_jk}^{\,2} -\sum_{k=1}^{K}p_{tk}^{\,2}. \end{aligned}

The terms $1$ in the Gini formulas cancel because the child weights sum to 1. This establishes that the local reduction compares the parent’s impurity with the average impurity experienced by an observation after it is routed to its child. A positive reduction means the split lowers weighted impurity; a minimum-decrease rule requires that improvement to be large enough.

Checking Several Rules Together

A candidate split is allowed only if it meets all the applicable conditions. Passing the impurity threshold does not override a depth limit or an undersized child, and satisfying the size requirement does not compensate for an impurity decrease below threshold.

Worked Example: A Split That Meets All Three Conditions

A node at depth 1 contains 20 observations, with 10 in each of two classes. A candidate split creates children with class counts $(8,2)$ and $(2,8)$. The maximum depth is 2, the minimum child size is 6, and the minimum local Gini reduction is 0.15. Decide whether the node may be split. Use the method of checking depth, child sizes, and impurity reduction separately.

Depth check. The node has depth $1<2$, so it is eligible under the maximum-depth rule. The proposed children would have depth 2, which does not exceed the stated maximum.

Child-size check. The child sizes are $8+2=10$ and $2+8=10$. Each is at least 6, so the size condition is met.

Impurity check. The parent has class proportions $10/20=0.5$ and $10/20=0.5$, giving $I(t)=1-(0.5)^2-(0.5)^2=0.5$. In either child, the proportions are $0.8$ and $0.2$, so its Gini impurity is $1-(0.8)^2-(0.2)^2=1-0.64-0.04=0.32$. The weighted child impurity is $(10/20)(0.32)+(10/20)(0.32)=0.32$. Thus the local reduction is $0.50-0.32=0.18$, which is at least 0.15.

Conclusion and check. The split is permitted: it meets the depth limit, both children meet the minimum size, and its reduction $0.18$ meets the threshold $0.15$. The children contain $10+10=20$ observations, matching the parent total. A common mistake would be to stop after finding a good impurity reduction; the depth and child-size conditions must also be checked.

Worked Example: Correctly Weighting an Uneven Split

A node contains 10 observations: 6 in class A and 4 in class B. A candidate split creates children with class counts $(4,0)$ and $(2,4)$. The minimum child size is 2, the node is below the maximum depth, and the minimum local Gini reduction is $\tau=0.10$. Decide whether the split is allowed. The method is to calculate parent impurity, weighted child impurity, and their difference.

The parent class proportions are $6/10$ and $4/10$. Its impurity is $1-(6/10)^2-(4/10)^2=1-0.36-0.16=0.48$.

The first child has size 4 and contains only class A, so its impurity is $1-1^2-0^2=0$. The second child has size 6, with proportions $2/6$ and $4/6$. Its impurity is $1-(2/6)^2-(4/6)^2=1-4/36-16/36=16/36=4/9$.

Weighting by the child sizes gives $(4/10)(0)+(6/10)(4/9)=4/15$, or approximately $0.2667$. The local reduction is $0.48-4/15=36/75-20/75=16/75$, or approximately $0.2133$. Each child has at least 2 observations, and the depth condition is satisfied. Since $16/75\approx0.2133\geq0.10$, the split is allowed.

Check and common mistake. The child sizes sum to $4+6=10$. Treating the weighted child impurity as 0.40 would be an incorrect calculation: the second child’s impurity is $4/9$, weighted by $6/10$, not by an incorrect weight or an unweighted average. The correct weighted impurity is $4/15$, and the correct reduction is $16/75$; it meets, rather than fails, the threshold.

Worked Example: When Different Candidates Fail for Different Reasons

A node at depth 3 contains 9 observations, with class counts $(5,4)$. The maximum depth is 4, the minimum child size is 3, and the minimum local Gini reduction is 0.02. Two candidate splits are available: candidate A creates children $(1,1)$ and $(4,3)$; candidate B creates children $(2,1)$ and $(3,3)$. Decide whether either split is permitted. Use the same three-condition check for each candidate.

The parent impurity is $1-(5/9)^2-(4/9)^2=1-25/81-16/81=40/81$. The depth condition allows consideration of a split because $3<4$.

Candidate A. Its child sizes are 2 and 7. The child of size 2 is below the minimum size of 3, so this candidate is not permitted. For completeness, its impurity reduction is small as well: the child $(1,1)$ has impurity $1-(1/2)^2-(1/2)^2=1/2$, and the child $(4,3)$ has impurity $1-16/49-9/49=24/49$. Weighted child impurity is $(2/9)(1/2)+(7/9)(24/49)=1/9+8/21=31/63$. The reduction is $40/81-31/63=280/567-279/567=1/567$, below 0.02.

Candidate B. Its child sizes are 3 and 6, so both meet the minimum size. The $(2,1)$ child has impurity $1-4/9-1/9=4/9$; the $(3,3)$ child has impurity $1-1/4-1/4=1/2$. Weighted child impurity is $(3/9)(4/9)+(6/9)(1/2)=4/27+1/3=13/27$. The reduction is $40/81-13/27=40/81-39/81=1/81$, approximately $0.0123$, which is below 0.02.

Conclusion and check. Neither candidate is permitted. Candidate A fails the size rule and also fails the decrease threshold; candidate B passes the size rule but fails the decrease threshold. The child sizes in each candidate sum to 9. This example shows why a node’s eligibility cannot be decided from just one condition.

Stopping During Growth Is Not Post-Growth Pruning

A growth-stopping rule acts before the split is made. If a node reaches the maximum depth, has too few observations to create eligible children, or has no candidate split that meets the minimum impurity decrease, growth stops at that node. Its observations remain together in a terminal node.

Post-growth pruning is different: the tree is first grown to include branches that were allowed at the time, and a later procedure removes some of those branches. A tree restricted by a maximum depth may never contain branches beyond that depth; pruning cannot be described as though those branches had first been grown and then removed. Conversely, pruning can remove an existing branch even if the split that created it met the growth rules. The rules answer different questions and may be used at different stages of tree construction.

Common Exam Traps

Checking only one condition. A split with a large impurity reduction still fails if it violates the depth or child-size rule.
Using the wrong size requirement. A minimum parent size and a minimum child size impose different restrictions. Identify which one is stated.
Forgetting weights. The child impurity must be multiplied by its fraction of the parent observations before comparing it with the parent impurity.
Comparing impurity with the threshold. The threshold applies to the reduction, not to the weighted child impurity itself.
Mixing up growth and pruning. A stopping rule prevents a proposed split; pruning removes branches from a tree that has already grown.

Key takeaway: For each node, check whether depth permits a split, whether every resulting child meets the stated size requirement, and whether the split’s correctly weighted impurity reduction reaches its threshold. All required conditions must hold for the split to occur.

Check Your Understanding

For each problem, use the stated depth convention and local Gini-reduction definition. Check each applicable condition before deciding whether a split is allowed.

A node at depth 2 contains 14 observations, split into class counts $(7,7)$. A candidate split creates children $(4,1)$ and $(3,6)$. The maximum depth is 3, the minimum child size is 4, and the minimum decrease is 0.08. Is the split allowed? (Answer: Yes; parent impurity is 0.50, weighted child impurity is 0.40, and reduction is 0.10; depth and child sizes also pass.)
A node has class counts $(5,3)$. A proposed split creates children $(4,0)$ and $(1,3)$. The minimum child size is 2 and the minimum decrease is 0.10. Does the split qualify? (Answer: No; the size-1 child violates the minimum, although the reduction is $0.46875-0.1875=0.28125$, above the threshold.)
A node at depth 1 has class counts $(9,6)$, maximum depth 3, minimum child size 5, and minimum decrease 0.05. A split creates children $(6,2)$ and $(3,4)$. Decide whether it is allowed. (Answer: Yes; the parent impurity is $0.48$, weighted child impurity is $3/7$, and reduction is $9/175\approx0.0514$; both child sizes pass.)
Tree A is not allowed to split a node because it has reached its stated maximum depth. Tree B is first grown with that branch and then has the branch removed in a later procedure. Identify which is growth stopping and which is post-growth pruning. (Answer: Tree A uses a growth-stopping rule; Tree B undergoes post-growth pruning.)

What You'll Learn