Decision Trees: Splits, Information Gain, and the ID3 Algorithm

the idea: a tree of questions

Back to the CI pass/fail problem, but with a completely different kind of model. Instead of computing a weighted sum like logistic regression, a decision tree asks a sequence of questions about the features and follows the answer down a branch, until it reaches a leaf that holds the prediction:


touches_slow_suite?
├── yes ─── lines_changed > 500?
│           ├── yes ─── predict: FAIL
│           └── no  ─── predict: PASS
└── no  ─── predict: PASS

Each internal node asks about one feature, each edge is an answer, and each leaf is a final prediction. No math is required to read a trained tree out loud as a set of rules — that's the property that makes decision trees the most immediately interpretable model in this track so far.

how a tree is built: greedy, one split at a time

Training a decision tree means choosing which feature to ask about at each node, and where. The standard approach, ID3, builds the tree top-down and greedily:

Step	What happens
1	At the current node, try every available feature (and every candidate split point) as the next question
2	Score each candidate by how much it improves the purity of the resulting groups (information gain, below)
3	Commit to the single best-scoring question for this node
4	Split the data into branches by the answer, and recurse into each branch as a fresh subproblem
5	Stop a branch when it's pure (all one class) or a stopping rule below kicks in

Greedy means step 3 never reconsiders — once a question is chosen for a node, ID3 moves on and never looks back to check whether a different early question would have led to a better tree overall. That makes training fast, but it means ID3 finds a good tree, not provably the best possible one; a different early split could, in principle, have set up better splits two levels down that greedy search never gets to see.

measuring a good split: entropy and information gain

Entropy measures how mixed a group of labels is — 0 when a group is perfectly pure (every example is the same class), and highest when a group is split as evenly as possible between classes:


entropy(S) = -sum(p_i * log2(p_i) for each class i)

# a set that's 100% one class: entropy = 0  (nothing left to learn)
# a perfect 50/50 split of two classes: entropy = 1  (maximally uncertain)

Information gain is how much entropy a candidate split removes: the entropy before splitting, minus the size-weighted average entropy of the groups it produces after splitting. A worked example makes this concrete. Say 10 historical CI runs split 4 failed / 6 passed:


entropy(all 10 runs) = -0.4*log2(0.4) - 0.6*log2(0.6) = 0.971

# candidate split A: touches_slow_suite (yes/no)
#   yes -> 5 runs, 4 failed / 1 passed  -> entropy = 0.722
#   no  -> 5 runs, 0 failed / 5 passed  -> entropy = 0.000  (pure!)
weighted entropy after split A = 0.5*0.722 + 0.5*0.000 = 0.361
information gain(A) = 0.971 - 0.361 = 0.610          # big improvement

# candidate split B: author == "alice" (yes/no)
#   yes -> 5 runs, 2 failed / 3 passed  -> entropy = 0.971
#   no  -> 5 runs, 2 failed / 3 passed  -> entropy = 0.971  (same mix as before splitting)
weighted entropy after split B = 0.5*0.971 + 0.5*0.971 = 0.971
information gain(B) = 0.971 - 0.971 = 0.000          # no improvement at all

Split A tells you something real — knowing touches_slow_suite almost perfectly separates the failures. Split B tells you nothing — failures are just as mixed on either side of it as they were before, so ID3 would never choose it while option A is on the table. This is exactly the statistical test step 2 above is doing, repeated for every candidate feature at every node. (Gini impurity is a common alternative to entropy for this same scoring step — different formula, same purpose, and the choice rarely changes which split wins.)

splitting on continuous features

touches_slow_suite is naturally yes/no, but lines_changed is a number — there's no fixed list of "answers" to branch on. The fix is a threshold: sort the observed values, try splitting at the midpoint between each consecutive pair (so 10 training values produce 9 candidate thresholds), score each one with information gain exactly like before, and keep the best. A single feature can even be used more than once down different branches of the same tree — lines_changed > 200 near the root and lines_changed > 800 further down are genuinely different questions, unlike asking the same yes/no question about a category twice.

when to stop: avoiding an overgrown tree

Left unconstrained, ID3 keeps splitting until every leaf is perfectly pure — which, taken to the extreme, means a leaf for every single training example. That's not a generalizing model, it's a lookup table with extra steps: a full overfitting failure, covered in depth in a dedicated page later in this track. In practice, a tree stops growing a branch when any of these hit first:

Stopping rule	What it prevents
Max depth reached	a tree with hundreds of sequential questions, each one narrower and less reliable than the last
Min samples per leaf	a leaf making a confident prediction off of 1-2 training examples
Min information gain to split	splitting further even when the best remaining question barely helps
Node already pure	splitting a group that's already all one class — nothing left to gain

decision trees for regression

The same tree structure adapts to predicting run_duration_minutes — the regression target from Linear Regression — with two changes. Splits are no longer scored by entropy (there's no "class" to be pure about); instead each candidate split is scored by how much it reduces the variance of the duration values in the resulting groups, the same instinct as entropy applied to a continuous target. And each leaf's prediction is simply the average duration of the training examples that landed there, instead of a class label.

where decision trees win, and where they don't

	Strength	Weakness
Interpretability	a trained tree reads as a flowchart of plain if/else rules — no coefficients to interpret	a deep tree with dozens of splits loses that readability fast
Feature prep	handles numeric and categorical features natively, no scaling/normalization needed (unlike linear/logistic regression)	—
Stability	—	a small change in the training data can flip an early split, cascading into a very different tree — this instability is the main reason ensembles of trees (random forests, gradient boosting) exist, covered in a dedicated page later in this track
Optimality	—	greedy search finds a good tree, not the provably best one — this is an NP-hard problem in general, so every practical algorithm makes this same trade-off

practical notes

from sklearn.tree import DecisionTreeClassifier| https://scikit-learn.org/stable/modules/generated/sklearn.tree.DecisionTreeClassifier.html | classification version -- criterion='entropy' or 'gini' selects the split-scoring rule discussed above |'dt_sk1'

DecisionTreeClassifier(max_depth=5, min_samples_leaf=10)| | the two stopping-rule knobs used most often in practice -- tune these before touching anything else |'dt_sk2'

from sklearn.tree import DecisionTreeRegressor| https://scikit-learn.org/stable/modules/generated/sklearn.tree.DecisionTreeRegressor.html | regression version -- same API, predicts the run-duration-style continuous target instead of a class |'dt_sk3'

from sklearn.tree import plot_tree; plot_tree(model, feature_names=cols)| https://scikit-learn.org/stable/modules/generated/sklearn.tree.plot_tree.html | renders the actual learned tree -- the fastest way to sanity-check whether it learned something sensible or something spurious |'dt_sk4'

where to go from here

Logistic Regression — the weighted-sum-based alternative this page's whole approach deliberately avoids.
Train/Test Splits & Cross-Validation — the honest way to check whether a tree like this one actually generalizes.
Ensemble Methods (intermediate, later in this track) — how random forests and gradient boosting fix a single tree's instability.

reference

scikit-learn — Decision Trees
Google — Decision Forests: Decision Trees