Chapter overview

Decision tree classification turns data into a hierarchy of if-then rules. At every internal node, the algorithm selects a feature and threshold that separates the training labels as effectively as possible. A new observation follows one branch at a time until it reaches a leaf, where the tree returns a predicted class and an estimated class probability.

Trees are popular because their logic can be displayed, they capture nonlinear relationships and interactions, and they usually do not need feature scaling. Their flexibility is also their central weakness: an unrestricted tree can memorize small details, change substantially after a modest data perturbation, and generalize poorly. This chapter therefore treats complexity control and pruning as essential parts of tree modeling.

Learning objectives

• Identify the root node, internal nodes, decision rules, branches, and leaf nodes.
• Explain how a classification tree converts leaf class counts into predictions and probabilities.
• Calculate and interpret Gini impurity, entropy, weighted impurity, and information gain.
• Explain how feature thresholds are evaluated during greedy recursive partitioning.
• Control complexity with max_depth, min_samples_split, min_samples_leaf, and max_leaf_nodes.
• Use cost-complexity pruning and validation data to select ccp_alpha.
• Visualize a fitted tree and trace the decision path for individual observations.
• Recognize the advantages, limitations, and common failure modes of a single decision tree.

Chapter map

Table 16.1. Chapter structure

16.1 Tree structure

A classification tree organizes decisions as a top-down hierarchy. Every observation begins at the same root, follows rules through internal nodes, and ends in exactly one leaf.

Figure 16.1. Anatomy of a small classification tree

Root node

The root node contains every training observation available to the tree. Its rule creates the first and usually most globally influential partition. A root such as mean radius <= 15.05 sends observations satisfying the condition to the left child and the remaining observations to the right child. The first rule is not automatically the most important causal factor; it is simply the split that best improves the chosen training criterion at that moment.

Internal node and decision rule

An internal node is a nonterminal region that can still be divided. Its decision rule normally has the form feature <= threshold for continuous features. The rule is local: it is evaluated only for observations that have already reached that node. This is why the same feature may appear more than once and why a feature can have different effects in different regions of the tree.

Branches

A branch is the connection created by an outcome of a decision rule. In a binary tree, the left branch conventionally represents a true <= condition and the right branch represents the complementary > condition. A complete root-to-leaf path is a conjunction of rules: all conditions along the path must hold for the observation to enter that leaf.

Leaf node, predicted class, and class probability

A leaf node is terminal: no additional split is applied. The predicted class is normally the class with the largest training count, or weighted count, among observations in that leaf. The class probability is estimated from the class proportions inside the leaf. With 30 training observations in a leaf, of which 24 are class 1 and 6 are class 0, the estimated probability of class 1 is 24 / 30 = 0.80.

Trace one prediction

Read the learned rules as text

Table 16.2. Reading a classification tree

16.2 How a tree selects splits

At each node, the algorithm compares candidate feature-threshold pairs and chooses a partition that produces purer child nodes. This is a greedy decision: it optimizes the current split without solving for the globally best possible tree.

Figure 16.2. Greedy split selection at one node

Purity and impurity

A node is pure when all training observations inside it have the same class label. Impurity increases as the class distribution becomes more mixed. A useful split decreases impurity by separating observations into children whose class distributions are more homogeneous than the parent distribution.

Gini impurity

Gini impurity can be interpreted as the probability of a label disagreement under a simple random-label thought experiment based on the node proportions. It is zero for a pure node. For a balanced binary node with proportions 0.5 and 0.5, Gini impurity is 0.5, its binary maximum.

Entropy

Entropy measures uncertainty in the class distribution. A pure node has entropy zero because its label is certain. A balanced binary node has maximum entropy of 1 bit when logarithms use base 2. Entropy places a different numerical emphasis on mixed distributions than Gini impurity, but the two criteria often produce similar trees.

Worked impurity example

Suppose a parent node contains 10 observations: 6 positive and 4 negative. Candidate split A produces a left child with 4 positive and 0 negative observations and a right child with 2 positive and 4 negative observations. The parent Gini impurity is 0.48. The left child impurity is 0, and the right child impurity is approximately 0.444. Weighting by child sizes gives 0.267, so the Gini reduction is approximately 0.213.

Table 16.3. Manual Gini calculation

Weighted impurity and information gain

A candidate split must be evaluated using both children. The child impurities are weighted by the proportion of node observations sent to each child; otherwise a tiny pure child could make a poor split look attractive. Information gain is the parent impurity minus the weighted child impurity. The tree selects a candidate with the largest improvement under the configured criterion and constraints.

Feature thresholds

For a continuous feature, candidate thresholds are considered between ordered training values that reach the current node. A threshold partitions the cases into feature <= threshold and feature > threshold. The selected threshold depends on the labels and on any sample or class weights; it is not simply the feature mean or median.

Gini versus entropy

Table 16.4. Comparing classification criteria

Recursive partitioning is greedy

After choosing the best available split at the root, the algorithm repeats the search independently inside each child. It does not usually revisit the root after discovering later branches. This greedy strategy makes tree induction computationally practical, but a locally best early decision may prevent a better overall structure. Different training samples or equal-quality candidate splits can therefore lead to different trees.

16.3 Tree complexity

Tree growth must be controlled. Complexity parameters can stop weak or overly specific branches before they are created, while cost-complexity pruning removes branches after an initial tree has been grown.

Figure 16.3. Controlling tree complexity

Maximum depth

max_depth limits the number of successive decisions from the root to the deepest leaf. A shallow tree is easier to explain and normally has lower variance, but it can miss real structure. An unrestricted depth allows the algorithm to continue until another stopping condition applies and can produce a large, highly specific tree.

Minimum samples per split

min_samples_split specifies how many training observations an internal node must contain before it may be split. Raising the value prevents the algorithm from dividing very small nodes. It does not guarantee large leaves by itself because a permitted split can still send only a few observations to one child.

Minimum samples per leaf

min_samples_leaf requires each resulting leaf to contain at least a specified number of training observations. This directly prevents tiny terminal regions and usually smooths class probability estimates. Both min_samples_split and min_samples_leaf can be integers or fractions of the training size in scikit-learn.

Maximum number of leaf nodes

max_leaf_nodes places a global limit on the number of terminal regions. In scikit-learn, the tree grows in best-first fashion under this constraint, prioritizing nodes with the strongest relative impurity reduction. Limiting leaves can be more directly connected to the number of distinct rule-based segments than limiting depth.

Table 16.5. Main complexity controls

Study depth and leaf-size effects

Cost-complexity pruning

Minimal cost-complexity pruning balances empirical fit against the size of the subtree. scikit-learn exposes this trade-off through ccp_alpha. With ccp_alpha = 0, no cost-complexity pruning is applied. As alpha increases, branches with insufficient improvement relative to their complexity are removed, so node count and depth generally decrease in steps.

Selecting a pruning strength

Pre-pruning versus post-pruning

Table 16.6. Complexity-control strategies

16.4 Advantages

A single decision tree is often a valuable first nonlinear classifier because its mechanism is transparent, its preprocessing demands are modest, and its learned rules can be inspected directly.

Easy to visualize

A small tree can be drawn as a flow of rules from the root to leaves. The diagram can show feature thresholds, impurity, sample counts, class distributions, and predicted classes. This visibility supports teaching, debugging, stakeholder discussion, and discovery of suspicious leakage features. Very large trees, however, cease to be meaningfully interpretable even if they remain technically drawable.

Nonlinear relationships and feature interactions

Axis-aligned rules divide feature space into regions, allowing a tree to represent nonlinear class boundaries. Hierarchical rules also create interactions: a threshold for one feature may matter only after another feature has placed an observation in a specific branch. No explicit polynomial or interaction term is required.

Scaling is usually unnecessary

A tree compares one feature with a threshold at a time. Multiplying a feature by a positive constant changes the numerical threshold but does not change the ordering of observations, so standardization normally does not improve the split geometry. This differs from KNN, support vector machines, and regularized linear models, whose calculations depend directly on feature scale.

Mixed feature patterns

After appropriate encoding, a tree can combine binary indicators, counts, continuous measurements, ordinal values, and one-hot encoded categories in different branches. It can also ignore features that do not provide useful impurity reduction. This flexibility is especially attractive for tabular problems containing thresholds, exceptions, and conditional rules.

Table 16.7. Practical advantages with caveats

Verify scale invariance

16.5 Limitations

The interpretability of a small tree should not obscure the statistical weaknesses of a single deep tree. High variance, instability, greedy search, and piecewise-constant predictions require careful validation.

High variance and overfitting

An unrestricted tree can keep splitting until leaves are pure or too small to divide. Training accuracy may then approach 100%, while validation accuracy stops improving or declines. The tree has learned local accidents, mislabeled observations, and sampling noise rather than stable structure. Complexity controls reduce this variance at the cost of added bias.

Instability to small data changes

A small change in the training sample can alter the best root split. Because every later split depends on the earlier hierarchy, the entire tree may reorganize. Two trees with similar predictive accuracy can therefore present noticeably different rules and feature importances. Fixing random_state improves reproducibility for a given dataset, but it does not remove sampling instability.

Greedy optimization

The algorithm selects the best current split and recurses. It does not explore every possible future tree because exhaustive global search would be impractical. A locally strong split can block a better later structure, and correlated features may substitute for one another depending on small criterion differences.

Additional practical limitations

• Axis-aligned partitions: complex diagonal boundaries may require many step-like regions.
• Biased importance measures: impurity-based importance can favor variables with many possible split points.
• Weak probability estimates: small or pure leaves can produce overconfident class proportions.
• Poor extrapolation: a tree predicts from existing leaf regions rather than extending a smooth trend.
• Class imbalance: impurity improvement and majority-class leaves can under-serve rare classes unless metrics and weights are chosen carefully.

Table 16.8. Diagnosing common tree problems

Measure instability with repeated splits

Practical lab — Train, visualize, and prune a decision tree

Students build a classification tree for the Breast Cancer Wisconsin diagnostic dataset, compare training and validation performance, visualize an initial tree, generate a cost-complexity pruning path, select ccp_alpha without touching the test set, refit the chosen tree, and report final test results. The dataset is educational and must not be treated as a clinical decision system.

Lab objectives

• Create reproducible 60/20/20 training, validation, and test subsets with stratification.
• Train an unrestricted baseline and inspect its depth, leaves, nodes, and accuracy gap.
• Visualize the upper levels of the tree with feature and class names.
• Generate candidate ccp_alpha values from the training data only.
• Compare subtree size, training accuracy, and validation accuracy across alpha values.
• Select the simplest best-validation tree and freeze its configuration.
• Refit on development data and evaluate once on the untouched test set.
• Trace one test observation through the final tree and inspect feature importance cautiously.

Experimental design

Table 16.9. Practical lab design

Step 1 — Load and inspect the data

In this dataset, target 0 represents malignant and target 1 represents benign. Attach these meanings to every class-specific result so that recall or error counts are not interpreted for the wrong class.

Step 2 — Create protected subsets

Step 3 — Train an unrestricted baseline

Step 4 — Visualize the upper tree

Limiting max_depth inside plot_tree changes only the drawing, not the fitted baseline_tree. The hidden lower branches still exist and still affect predictions. Record the root rule, the dominant classes in the first children, and any feature that appears repeatedly.

Step 5 — Generate the pruning path

Step 6 — Evaluate every candidate on validation data

Step 7 — Plot the pruning trade-off

Questions for the pruning curves

• How does node count change as ccp_alpha increases?
• Where is the gap between training and validation accuracy largest?
• Does validation accuracy improve after removing some branches?
• Is the highest validation score achieved by one alpha or a plateau of candidates?
• At what point does excessive pruning reduce both training and validation performance?

Step 8 — Select alpha without using the test set

Step 9 — Refit and evaluate once

Step 10 — Visualize and export the pruned tree

Step 11 — Trace one test observation

Step 12 — Inspect feature importance cautiously

Expected observations

• The unrestricted tree usually achieves extremely high training accuracy and uses more nodes than the selected pruned tree.
• Increasing ccp_alpha removes branches in discrete steps rather than continuously shrinking every rule.
• Moderate pruning may preserve or improve validation accuracy while substantially simplifying the tree.
• Excessive pruning eventually produces a tree that is too small and underfits.
• The final test score can be below the best validation score because selection favored some validation-specific noise.
• Leaf probabilities are constant for all observations that enter the same leaf.

Lab deliverables

• A reproducible notebook containing the complete workflow and outputs.
• A diagram of the initial tree's first three levels.
• A table of ccp_alpha, node count, depth, leaves, training accuracy, and validation accuracy.
• Two labeled pruning curves: accuracy versus alpha and node count versus alpha.
• The selected alpha and the predeclared tie-breaking rule.
• A final confusion matrix, classification report, and complete pruned-tree visualization.
• A 200–300 word interpretation of overfitting, pruning, final complexity, and limitations.

Extension challenges

• Replace the single validation set with StratifiedKFold cross-validation and report mean plus standard deviation for each alpha.
• Compare cost-complexity pruning with max_depth and min_samples_leaf under the same validation procedure.
• Use class_weight='balanced' and compare malignant-class recall, precision, and F1 rather than accuracy alone.
• Bootstrap the development data, refit several pruned trees, and measure how often the root feature changes.
• Compare impurity-based feature importance with permutation importance on validation data.

Common mistakes and corrections

Table 16.10. Frequent decision-tree errors

Knowledge check

Choose one answer for each question. Complete the questions before consulting the answer key.

1. What does every observation encounter first in a decision tree?

• A. A leaf node
• B. The root node
• C. A confusion matrix
• D. A scaling transformation

2. What normally determines the predicted class of a leaf?

• A. The class with the largest leaf count
• B. The deepest feature
• C. The global feature mean
• D. A random label

3. A pure classification node has Gini impurity equal to:

• A. -1
• B. 0
• C. 0.5 for every problem
• D. The sample size

4. Information gain compares:

• A. Test and training size
• B. Parent impurity with weighted child impurity
• C. Feature scales
• D. Prediction time and fit time

5. Why must child impurity be weighted?

• A. Children may contain different numbers of observations
• B. Every feature needs standardization
• C. Entropy cannot use probabilities
• D. Trees require equal class counts

6. Which change usually makes leaves larger and the tree smoother?

• A. Decrease min_samples_leaf
• B. Increase min_samples_leaf
• C. Remove random_state
• D. Standardize every feature

7. What does a larger ccp_alpha generally encourage?

• A. More branches
• B. A smaller pruned subtree
• C. More features in the dataset
• D. A different target

8. Why can a single tree be unstable?

• A. It never uses labels
• B. Small data changes can alter early splits and later branches
• C. Scaling always changes class labels
• D. It averages thousands of trees

9. Which statement about scaling is most accurate?

• A. Trees always fail without StandardScaler
• B. Trees usually do not need scaling, but other preprocessing may still be required
• C. Scaling removes overfitting
• D. Scaling converts classification to regression

10. When should the final test set be evaluated?

• A. During every alpha comparison
• B. Before selecting a criterion
• C. Once after the modeling choices are frozen
• D. To decide the train-validation split

Answer key and explanations

Table 16.11. Knowledge-check solutions

Score interpretation

• 9–10 correct: ready to train, interpret, and prune a classification tree with honest validation.
• 7–8 correct: solid understanding; revisit impurity reduction or complexity controls where needed.
• 5–6 correct: repeat the worked split calculation and pruning-path lab.
• 0–4 correct: review tree anatomy, leaf predictions, and the distinction between training and validation performance.

Chapter summary

• A decision tree routes each observation from a root through internal rules and branches to one terminal leaf.
• The leaf predicts the class with the largest training count or weighted count and estimates probabilities from leaf proportions.
• Gini impurity and entropy quantify class mixing; useful splits reduce weighted impurity.
• Split search is greedy and recursive, so a locally best decision is not guaranteed to produce a globally optimal tree.
• Maximum depth, minimum split size, minimum leaf size, and maximum leaves control growth before pruning.
• Cost-complexity pruning uses ccp_alpha to trade fit against subtree size and must be tuned without the test set.
• Trees capture nonlinear relationships and interactions and normally do not require feature scaling.
• A single tree can overfit, vary substantially across samples, and produce unstable rules or importance rankings.
• Interpretability depends on restraint: a small validated tree is understandable; a huge tree is merely visible.

Key vocabulary

Table 16.12. Essential terminology

Further reading

• scikit-learn: DecisionTreeClassifier
• scikit-learn user guide: decision trees
• scikit-learn: plot_tree
• scikit-learn example: cost-complexity pruning

What’s next?

The next chapter studies ensemble classification models. Random forests reduce the variance of individual trees by combining many randomized trees, while gradient boosting builds trees sequentially to correct earlier errors. The contrast explains why one transparent but unstable learner can become the foundation of highly accurate ensemble methods.