Pruning and Stopping

## Why a tree needs to be stopped at all A CART tree is grown greedily. At each node the algorithm scans candidate feature-and-threshold cuts and keeps the one that most reduces impurity in the two children. Nothing in that loop knows when to quit: as long as a node still holds rows with different labels, some cut will reduce impurity, so the recursion continues until every leaf is pure or holds rows that are identical in the features. Take a 30-day hospital readmission model grown that way. The tree ends with roughly one patient per leaf and reports 100% training accuracy. That number is a tautology, not evidence: each training patient is being looked up in a leaf that was carved around that patient. A new patient falls into a leaf shaped by one other person's idiosyncrasies, and the prediction is whatever that single person's outcome happened to be. So growth has to be told when to stop. The controls that do it are applied *during* construction, which is what distinguishes them from pruning a finished tree. ## The four limits **Maximum depth.** A hard cap on how many splits separate the root from any leaf. A depth-4 tree has at most 16 leaves and at most 4 conditions on any decision path. It is the bluntest control: it applies the same budget to every branch, whether that branch carries 60% of the training rows or 0.5% of them. **Minimum samples to split an internal node.** A node holding fewer rows than the threshold is turned into a leaf without any cut being considered. This looks at the *parent*. **Minimum samples per leaf.** A candidate split is rejected if either child would end up below the floor. This looks at the *children*, and it is the stronger of the two sample rules: with a floor of 50, no leaf anywhere in the tree can hold fewer than 50 training rows, so every leaf prediction rests on at least that many observations. It adapts to the data — dense regions can still go deep, sparse branches stop early — which is why it is usually a better knob than depth alone. **Minimum impurity decrease.** A split is accepted only if the impurity it buys clears a threshold. The quantity compared is normally *weighted* by how much of the training set reaches the node: ``` decrease = (N_t / N) * ( impurity(t) - (N_L/N_t)*impurity(L) - (N_R/N_t)*impurity(R) ) ``` where `N` is the training-set size, `N_t` the rows at node `t`, and `N_L`, `N_R` the rows going left and right. The weighting matters: a deep node holding 1% of the data must produce a hundred times the local impurity drop of a root-level split to clear the same threshold. Set the threshold at 0.001 and a candidate split that moves Gini by 0.0004 is refused outright — the node stays a leaf unless some other candidate does better. Many implementations also expose a cap on the total number of leaves, which grows the tree best-first and stops at the budget rather than capping depth uniformly. ## How they interact These limits are not independent. A leaf-size floor of 50 on a 900-row dataset already implies at most 18 leaves, which implies an effective depth of about 4 even with no depth cap. Setting several tight limits at once makes it hard to say which one is actually binding, so when tuning, it is common to move one of them — usually the leaf-size floor or the depth cap — and leave the others loose. Also note what these limits do *not* do. They are checked one split at a time with no lookahead, so a split whose value only appears one level lower is simply never taken. And a limit that is too tight underfits: a depth cap of 2 on a problem with five interacting features cannot express the answer regardless of how much data you have. ## What to say about defaults Out of the box, most tree implementations set none of these meaningfully: depth is unlimited, the split threshold is 2 rows, the leaf floor is 1 row, and the impurity threshold is 0. In other words, the default behaviour *is* growth to purity. That is a deliberate choice, because the same code is reused inside averaged ensembles where deep individual trees are acceptable — but for a single tree that you intend to read or deploy, leaving the defaults is the mistake. Pick a leaf-size floor that reflects how many observations you need behind each prediction, then check the choice on held-out data rather than on the training score.