Decision Trees and Rule-Based Splits

By the end of this lesson, you will be able to...

• compare candidate tree splits by how much label mixing they remove;

• trace one student's prediction through a learned sequence of questions;

• explain why a readable tree can still overfit and how stopping or pruning changes that risk.

Idea in one sentence: A decision tree learns a sequence of local questions that makes each group less mixed, then predicts from the labels that reached the final group.

Core Insight

Logistic regression turned several inputs into one global risk score. That is useful when one weighted boundary is a good approximation. But some patterns look more like local rules:

missing assignment?
  yes -> risk often high
  no  -> attendance may matter next

The naive view is that a decision tree is simply a checklist a person wrote. A trained tree looks like a checklist, but it earns each question by comparing candidate splits on labeled examples.

The mechanism is recursive:

mixed group of examples
-> test candidate questions
-> choose the question that makes child groups least mixed
-> repeat within each child group
-> stop and predict from the final group

The same flexibility that makes a tree easy to inspect also lets it create tiny, brittle exceptions. A path being explainable is not evidence that it will generalize.

A Small Group That Needs a First Question

The support team again predicts a later withdrawal outcome using evidence available at week two. These six rows are a synthetic teaching dataset.

At the root, three students withdrew and three did not. A model that always predicts the majority has no preference here. The tree needs a question that separates the labels into more predictable groups.

Two candidate questions are available:

Q1: attendance below 70%?
Q2: first assignment missing?

The tree does not ask which question sounds more convincing to us. It asks which question reduces the label mixture in these training rows.

Gini Impurity Makes “Less Mixed” Calculable

For a binary node with positive-label proportion p, Gini impurity is:

Gini = 1 − p² − (1 − p)²

• A pure node with all yes or all no has Gini 0.
• A 50/50 node has Gini 0.5, its highest value for two classes.

The root has three yes labels and three no labels, so p = 3/6 = 0.5:

root Gini = 1 − 0.5² − 0.5² = 0.5

For a split, compute each child's impurity and weight it by the child's size. Lower weighted impurity is better.

Candidate Q1: attendance below 70%?

yes: A, B, E -> 2 withdrew, 1 did not -> Gini = 4/9 ≈ 0.444
no:  C, D, F -> 1 withdrew, 2 did not -> Gini = 4/9 ≈ 0.444

Both children have three rows, so the weighted impurity is 0.444. The improvement from the root is only about 0.500 − 0.444 = 0.056.

Candidate Q2: first assignment missing?

yes: A, B -> 2 withdrew, 0 did not -> Gini = 0
no:  C, D, E, F -> 1 withdrew, 3 did not -> Gini = 0.375

The weighted impurity is:

(2/6)(0) + (4/6)(0.375) = 0.250

This split improves impurity by 0.500 − 0.250 = 0.250, which is larger than Q1's improvement. The tree chooses Q2 as its root split.

Gini is not decoration. It converts “this question creates cleaner groups” into a repeatable comparison.

The Tree Repeats Locally

After the first split, the missing-assignment branch is already pure: A and B both withdrew. The tree can stop there and predict withdraw for similar training-region examples.

The submitted-assignment branch still contains C, D, E, and F, with one withdrawal and three non-withdrawals. The tree can test another question inside that branch. For example, attendance separates E from the other three:

first assignment missing?
├── yes -> predict withdraw (A, B)
└── no
    ├── attendance below 70%? yes -> predict no withdrawal (E)
    └── attendance below 70%? no  -> predict no withdrawal (C, D, F)

This shallow tree makes C a training mistake because the final leaf has two no labels and one yes label. A deeper tree might add another question, such as a recent quiz decline, to isolate C. That could be useful if the additional pattern repeats in new cohorts; it could also memorize C's accident.

Trace a new student G with a submitted assignment and attendance of 62%:

missing assignment? -> no
attendance below 70%? -> yes
leaf prediction -> no withdrawal

The prediction is a visible path, not an explanation of why G will or will not withdraw. It says that G landed in a region whose training examples had that majority label.

So far, the mechanism is clear: a tree selects a locally useful split, partitions the data, repeats within each partition, and predicts using a leaf's observed label mix.

What a Leaf Can Report

A classification leaf need not be read as only a hard label. In the branch containing C, D, and F, one of the three training examples withdrew. A basic leaf can report both:

predicted class: no withdrawal
training proportion for withdrawal in this leaf: 1 / 3

The first line follows the majority label. The second line describes the training composition of that region. Neither number is automatically a calibrated estimate for future students, especially when a leaf is small. A leaf with 1 / 1 looks completely certain on training data but has almost no evidence behind it.

That is why the number of examples at a leaf changes the interpretation. Compare these two leaves:

The path tells us which questions were asked. The leaf count tells us how much local training evidence arrived at the end of that path. Both should be visible during review.

A Split Can Sound Sensible and Do Nothing

Not every available question is useful. Imagine a third candidate feature, opened_orientation_email?, that is yes for three students and no for three students. Suppose each child happens to contain the same label balance as the root: half withdrew and half did not.

root Gini: 0.500
yes child Gini: 0.500
no child Gini: 0.500
weighted child Gini: 0.500

This split has impurity reduction 0. It partitions rows but does not make labels less predictable. A trained tree should prefer the missing-assignment split, whose weighted impurity was 0.250.

This distinction corrects another tempting model: more branching is not automatically more learning. A branch earns its place only when it improves the chosen criterion enough to justify its added complexity. Later tree controls can require a minimum impurity decrease for exactly this reason.

For a numerical feature such as attendance percentage, a learner tries candidate thresholds such as attendance <= 62% or attendance <= 70%, evaluates their weighted impurity, and keeps the best local threshold. The threshold is learned from the training rows; it is not automatically a meaningful policy boundary for staff. A learned split at 68.5% may predict well yet still require careful explanation before it is used to guide outreach.

Greedy Local Choices Are Not a Global Proof

The root chose the best immediate impurity reduction among the questions it considered. It did not search every possible complete tree and prove that its final structure is globally optimal. Practical tree learners use greedy, local choices because exhaustive tree search is expensive.

That creates a boundary. A split can be best at the current node and still lead to a less useful overall tree than a different early split would have. It also means that small changes in a small dataset can select a different root and a different set of later rules.

Trade-off: Trees represent nonlinear, local rule patterns without needing one global score, and their paths are easy to inspect. This costs stability: small data changes or rare values can alter the learned structure. They can still fail when features are unavailable at prediction time, labels are biased, or leaves become too small to represent future cases. Signals to watch are validation performance, leaf sample counts, tree depth, and large changes in structure across resampled data.

Stop Before the Tree Learns Every Exception

A fully grown tree can keep adding splits until leaves contain one or very few training rows. Training accuracy can then look excellent because each exception receives its own rule.

Common controls put a cost on that specificity:

• max_depth limits how many questions a path may ask;
• min_samples_leaf requires enough examples in a final group;
• min_samples_split prevents splitting very small groups;
• pruning removes branches whose complexity is not justified by validation evidence.

These controls do not make the tree automatically fair, causal, or correct. They express a preference for rules supported by more than a tiny training fragment. Choose them from validation evidence, not because a particular depth sounds reasonable.

Check Your Understanding

Check 1: A node has four examples: three positive and one negative. Is its Gini impurity lower or higher than a 50/50 node?

Think first, then reveal.

Answer: Lower. Its Gini is 1 − 0.75² − 0.25² = 0.375, compared with 0.5 for a 50/50 node. It is less mixed, though not pure.

Check 2: A tree leaf contains nine training examples: eight no and one yes. What class does a standard majority-label leaf predict?

Think first, then reveal.

Answer: no. The leaf can still be wrong for some future cases; its prediction reflects the training-label majority in that region.

Check 3: Why is a tree with one example per leaf risky even if every path can be read aloud?

Think first, then reveal.

Answer: It may have memorized training quirks rather than learned a pattern that repeats. Readability helps inspection, not generalization.

Practice: Review a Proposed Split

A support dataset has eight examples at a node: four later withdrew and four did not. A candidate split creates a left child with three withdrawals and one non-withdrawal, and a right child with one withdrawal and three non-withdrawals.

1. Calculate the Gini impurity of each child.
2. Calculate the weighted impurity after the split.
3. Say whether it improves on the root impurity of 0.5.
4. Name one reason to validate the resulting tree before using it.

Self-check: Each child has proportions 3/4 and 1/4, so each Gini is 0.375. The weighted impurity is also 0.375, an improvement of 0.125 over the root. Validation is still needed because the apparent split may not persist in a future cohort.

Connections and Next Step

Decision trees replace logistic regression's global weighted score with local partitions of feature space. Both models need time-valid features, held-out evaluation, and an action policy. Their inductive biases differ: one expects a global score; the other expects useful conditional rules.

The next lesson, Naive Bayes for Text Classification, offers another contrast. It classifies sparse text by accumulating token evidence under an explicit independence assumption.

Resources

• [TUTORIAL] scikit-learn: Decision Trees — Focus: candidate splits, Gini impurity, greedy growth, and limits of individual trees.
• [TUTORIAL] scikit-learn: Cost-complexity pruning — Focus: control tree size with validation-based pruning.
• [REFERENCE] scikit-learn: DecisionTreeClassifier — Focus: split criteria and controls such as depth, leaf size, and pruning parameter.

Key Takeaways

1. A decision tree learns rule-like questions from data by choosing splits that reduce label mixing.
2. Gini impurity compares candidate splits through the weighted impurity of their child nodes.
3. A leaf predicts from the labels that reached it; its path is inspectable but is not a causal explanation.
4. Depth limits, minimum leaf sizes, pruning, and validation defend against brittle, overfit trees.