Decision Tree Learning

A decision tree makes exactly one decision repeatedly: which feature and threshold best clean up the rows in front of me? Cleaning up is a measurable quantity called purity, and the two standard measures differ only in their arithmetic, not their intent. Get the numbers straight on one node before looking at any algorithm.

Your current node holds 12 examples: 9 positive, 3 negative. The positive fraction is p = 0.75. Three candidates for "how mixed is this node":

Gini    = 1 - sum(p_k^2)      = 1 - (0.75^2 + 0.25^2) = 1 - 0.625 = 0.375
Entropy = -sum(p_k log2 p_k)  = -0.75*log2(0.75) - 0.25*log2(0.25)
                               = 0.75*0.415 + 0.25*2.0   = 0.811
Misclass = min(p, 1-p)        = 0.25

Read the three numbers as answers to the same question. Gini impurity is the probability that two rows drawn at random from the node disagree in class — for two classes that is 2p(1−p), which at p = 0.75 gives 0.375. Entropy is the average information content in bits: log base 2 because each flip of a fair coin carries exactly one bit, so a 9/3 node (0.811 bits) sits closer to certainty than a 6/6 node (1.0 bit, a full coin flip of uncertainty). Both are 0 on a pure node and both peak at 50/50 (Gini 0.5, entropy 1.0). The misclassification rate also hits 0 when pure — which is exactly why it fails as a split criterion: it only notices when the majority flips. Take a 99/1 node of 100 rows and split it into a 50/1 child and a perfectly pure 49-row child. The parent's error rate is 0.01; the support-weighted child error is (51/100) × (1/51) + 0 = 0.01 — exactly zero gain, despite creating a pure 49-row leaf. Gini (gain 0.0002) and entropy (gain ~0.01 bits) both credit the split, because they respond to the whole distribution rather than only its argmax. That is the practical reason trees use Gini or entropy.

import numpy as np

def gini(y):
    _, counts = np.unique(y, return_counts=True)
    p = counts / counts.sum()
    return 1 - (p ** 2).sum()

def entropy(y):
    _, counts = np.unique(y, return_counts=True)
    p = counts / counts.sum()
    return -(p * np.log2(p)).sum()

node = np.array([1]*9 + [0]*3)
print(gini(node), entropy(node))    # 0.375  0.811

Nothing about either formula is binary-specific. On a three-way node with class counts [5, 4, 3] the same equations give Gini = 1 − (0.417² + 0.333² + 0.25²) = 0.653 and entropy = −Σ p_k log2 p_k = 1.554 bits, comfortably below the maximum log2(3) = 1.585 for three classes. Two more mechanisms you have already met also flow through these formulas. Class weights enter impurity by weighting each row's contribution to the counts, so class_weight='balanced' from Class Imbalance Remedies makes a minority-heavy split look better than the raw row counts would suggest — that is how a tree stops defaulting to majority leaves. And on regression trees, the identical framework replaces impurity with variance: leaf cost is the mean squared error of the target within the leaf, and a split's gain is the variance reduction it buys. Same recursion, different measure of "mixed".

Which should you pick? Empirically they produce nearly identical trees — Breiman's original CART experiments showed negligible differences — because a split that most reduces one most reduces the other; the ranking of candidate splits is what matters, and the two criteria rarely disagree on the winner. scikit-learn defaults to criterion='gini'; entropy (and the newer alias log_loss, which is entropy in nats) are drop-in alternatives. The deeper skill is the second chapter's question: given a parent impurity and several possible child groups, how much did a candidate split actually buy?

Take the 9/3 node from the last chapter — entropy 0.811 — and two candidate splits. Split A creates children with (7 positive, 1 negative) and (2, 2). Split B creates (5, 3) and (4, 0). Which is better? The criterion is information gain: parent impurity minus the child impurities weighted by how many rows each child received.

gain = H(parent) - sum_j (n_j / n) * H(child_j)

Split A: H(7/1) = 0.5435, H(2/2) = 1.0
         gain_A = 0.811 - (8/12 * 0.5435 + 4/12 * 1.0) = 0.811 - 0.696 = 0.115

Split B: H(5/3) = 0.9544, H(4/0) = 0.0
         gain_B = 0.811 - (8/12 * 0.9544 + 4/12 * 0.0) = 0.811 - 0.636 = 0.175

Split B wins. The weighting is the whole lesson: Split A produced a beautifully pure 7/1 child, but it also wasted four rows on a perfectly mixed 2/2 child that learned nothing. Split B's smaller-looking pure child (4/0) was enough to pull the weighted child entropy below A's. Every greedy tree builder — CART, C4.5, CHAID — runs this arithmetic at every node for every feature and takes the maximum; the tree is nothing but this comparison, recursively applied.

Continuous features require one more mechanism. For age, you sort the n distinct values and try every midpoint between adjacent values as a threshold: n−1 candidates, each scored by the formula above. That sounds expensive and is handled in practice by presorting, histogram binning, and early stopping on provably useless cuts — which is why scikit-learn builds a tree over a million rows in seconds. Categorical features are handled by enumerating partitions (or, in modern scikit-learn, native categorical splits) rather than imposing an order that does not exist.

Now the bias every interviewer probes: impurity criteria favor splits that create many children or split on high-cardinality features. Take an order_id column with 10,000 unique values — splitting on it makes 10,000 singleton children, each pure, and the gain is enormous, while generalization is exactly zero. The same pull appears more subtly: a feature with 20 distinct levels gets more candidate thresholds than a binary feature and will win more ties. C4.5's answer was the gain ratio, which divides gain by the split's own intrinsic entropy (split information) and thereby penalizes many-way splits; CART's answer was to restrict to binary splits, which caps how much damage any one feature can do at a node, plus the regularization it applies afterward (next topic). If a split looks too good, check the feature's cardinality first.

from sklearn.tree import DecisionTreeClassifier

tree = DecisionTreeClassifier(criterion="gini", splitter="best",
                              random_state=42)
tree.fit(X_train, y_train)
# inspect what the search chose
for feat, imp in zip(feature_names, tree.feature_importances_):
    print(f"{feat:20s} {imp:.3f}")

The greedy choice is also a horizon problem: a split with modest immediate gain may unlock an excellent split one level down, but no single-step search can see it. Greedy, one-step, myopic — hold that thought, because it is the root cause of both the failure mode in the next chapter and the pruning remedies after it.

One cost fact rounds out the mechanism: at each node the search sorts every continuous feature (O(n log n)) and scans the candidate thresholds, so a naive build is O(m · n log n) per node where m is the feature count. On a million rows that is noticeable, which is why scikit-learn presorts once and uses floating-point threshold deduplication, why histogram-based learners (LightGBM, XGBoost's hist) bucket features into 256 bins before searching, and why splitter='random' — evaluating a few random thresholds instead of all of them — exists as a speed/variance trade. For interview purposes: the tree-building bottleneck is the split search, not the recursion.

Fit a DecisionTreeClassifier() with scikit-learn's defaults on any tabular dataset with a few noisy labels and watch what happens: training accuracy climbs to 100.00% while test accuracy sits several points lower, and tree.get_depth() reports something like 34. Nothing crashed, no warning fired — an unconstrained tree keeps splitting until every leaf is pure, which means it keeps splitting until each remaining group is a single training row. It has not learned the pattern; it has stored the dataset. That is the default behavior, and it is why the first line you write in a serious tree model names its limits (the next topic's subject).

The mechanics make the memorization obvious. Every mislabeled row (that one spam email labeled ham) eventually gets its own leaf containing only itself, at a threshold tuned to isolate it — a private exception carved into the decision surface. Depth and node count scale with noise, and with continuous features you can always find some threshold that separates two remaining points, so the recursion does not stop on its own. A quick demonstration:

from sklearn.tree import DecisionTreeClassifier
from sklearn.metrics import accuracy_score

free = DecisionTreeClassifier(random_state=42).fit(X_tr, y_tr)
limited = DecisionTreeClassifier(max_depth=5, min_samples_leaf=20,
                                 random_state=42).fit(X_tr, y_tr)
for name, m in (("unconstrained", free), ("depth<=5", limited)):
    print(name, "train", accuracy_score(y_tr, m.predict(X_tr)),
          "test", accuracy_score(y_te, m.predict(X_te)),
          "depth", m.get_depth(), "leaves", m.get_n_leaves())
# unconstrained: train 1.000 test 0.812 depth 31 leaves 604
# depth<=5:      train 0.878 test 0.871 depth 5  leaves 27

The gap between 1.000 and 0.871 is the entire overfitting story in two numbers, and a train accuracy of exactly 1.0 is the diagnostic you should never ignore — no real model is perfect on real data.

Before you write trees off, catalog what made them attractive in the first place, because every property comes from what a split is. Splits are threshold comparisons on single features, so trees need no feature scaling — standardization cannot change an ordering, and a tree built on raw dollars and raw counts is identical to one built on z-scores. They handle mixed data natively: continuous, ordinal, and (in modern scikit-learn with categorical feature types) categorical inputs all fit the same split machinery, with no one-hot explosion. They capture feature interactions for free — the path income > 80k AND debt < 20k is just depth 2, where logistic regression would need an explicit interaction term. They give interpretable rules you can print and hand to a compliance team, and they produce feature importances as a by-product of the splits that were chosen.

They also have two structural weaknesses interviews expect you to name. First, axis-aligned boundaries: separating two classes along a diagonal needs a staircase of many splits, where one split would do — trees spend depth approximating simple oblique boundaries. Second, no extrapolation: a regression tree predicts the mean of its leaf, so its output can never exceed the largest training target — feed it a future time trend and it flatlines at the training maximum. And while modern scikit-learn trees accept categorical feature types natively, older pipelines one-hot encode first, which multiplies columns and can hand the high-cardinality bias an invitation; either way, missing values need a strategy (recent sklearn versions route them to the side that minimizes impurity) instead of the silent imputation other models assume.

All of this sets up the roadmap's through-line for this phase. The prior phase's topics — Class Imbalance Remedies — apply here unchanged (class_weight and sample_weight flow into the same impurity arithmetic, so weighted majority votes decide leaves), and the overfitting you just watched is controlled by constraining growth or trimming it back, which is precisely what Tree Pruning and Hyperparameters is about to teach.