Decision Trees

2.4 — Decision Trees

Recall first. If you could ask only yes/no questions to predict whether a customer churns, what would make one question better than another?

A tree is a sequence of local questions

A decision tree recursively partitions the feature space. An internal node tests a feature and threshold (for example, attendance < 70); a branch records the outcome; a leaf stores a prediction. For classification the leaf commonly predicts the majority class or class proportions. For regression it commonly predicts the mean target of its training samples.¹²

                 hours < 4?
                 /       \
              yes         no
          attendance     pass
             <70?
           /     \
        fail     pass

The prediction path is easy to trace and trees can represent nonlinear relationships and interactions without requiring feature scaling. A feature can be numeric or categorical depending on the implementation. A tree’s prediction is piecewise constant: each region has one leaf value.

How a split is chosen

At a node, the learner considers candidate splits and measures how impure the child nodes would be. A weighted child impurity is:

Impurity_after = (n_L/n) I(L) + (n_R/n) I(R)
Gain = I(parent) − Impurity_after

Choose the split with the largest gain (equivalently smallest weighted child impurity), subject to stopping rules. Classification commonly uses Gini impurity or entropy; regression commonly uses squared-error/variance reduction. Topic 2.5 works the Gini calculation explicitly.

A greedy tree chooses the best current split; it does not generally search the globally best whole tree. It continues recursively until a stopping rule, then may be pruned. Typical controls include max_depth, min_samples_split, min_samples_leaf, and cost-complexity pruning. Deep unrestricted trees have low training error but can have high variance.¹

Strengths and trade-offs

Strengths: human-readable paths, no standardization requirement, nonlinear boundaries, automatic interactions, and mixed-scale predictors. Weaknesses: instability to small data changes, greedy suboptimality, axis-aligned boundaries, and overfitting. A tree can also favor features with many possible split points; validation and, where appropriate, permutation-based interpretation help avoid naive importance claims.

Feature importance is not the same as causal importance. A split on attendance may predict outcome because it proxies many factors, not because changing attendance alone guarantees the leaf difference.

Worked split calculation

At a node, six students have labels [1,1,1,0,0,0]. A candidate split gives left [1,1,0] and right [1,0,0].

Parent has p₁=3/6=0.5, so Gini is 1−0.5²−0.5²=0.5. Each child has two classes with proportions 2/3,1/3, hence Gini 1−(2/3)²−(1/3)²=2/9. Weighted child impurity is (3/6)(2/9)+(3/6)(2/9)=2/9; gain is 0.5−2/9=5/18≈0.278. Compare this with other candidate splits and choose the one with greatest gain.

Exercise

A tree’s training accuracy is 100%, validation accuracy 72%, and its depth is 30. Name the likely issue and two remedies. Why is scaling features not the first remedy?

Exam lens

Draw node → test → branches → leaf. Explain recursive greedy splitting, impurity reduction, stopping/pruning, and why a deep tree overfits. Keep classification impurity and regression loss separate.

Rapid revision checklist

• Can I define node, branch, leaf, split, and path?
• Can I write the weighted-child impurity and gain formula?
• Can I state the usual leaf prediction for classification and regression?
• Can I name two controls against tree overfitting?

Key takeaways

• A tree makes a prediction by following feature tests to a leaf.
• Splits are selected by impurity/loss reduction, usually greedily.
• Trees capture nonlinear interactions without scaling but are high-variance when unrestricted.
• Gini is a classification impurity; regression uses a numeric loss such as squared error.

Sources