Splitting Numerical Features in Decision Trees

The previous posts used categorical features with a finite set of values. For numerical features like sq_ft or age, the split can occur at infinitely many points. Decision trees handle this by generating a finite set of threshold candidates, evaluating each, and picking the best one.

Anchor dataset: 8-sample house classification. Predict whether a house is expensive (price > $300k).

import numpy as np
import pandas as pd

data = pd.DataFrame({
    'sq_ft':     [650, 850, 1100, 1200, 1400, 1600, 1900, 2100],
    'bedrooms':  [2, 2, 3, 3, 3, 4, 4, 5],
    'expensive': [0, 0, 0, 0, 1, 1, 1, 1]  # 1 if price > $300k
})
# 4 affordable (0), 4 expensive (1). Root H = 1.0 bit (perfectly mixed)

Root entropy: $H=-(0.5{\log }_{2}0.5+0.5{\log }_{2}0.5)=1.0$ bit.

Why Categorical Splits Don't Work for Numbers

For categorical features with $K$ values, we test each possible binary partition (left branch vs right branch). For 2 values: one partition. For 3 values: 3 partitions.

For a continuous feature with $n$ unique values: there are $n-1$ distinct orderings — but infinitely many possible split points. The solution: threshold candidates are the $n-1$ midpoints between consecutive sorted unique values.

Any split point between $x_i$ and $x_{i+1}$ produces the same left/right partition. The exact midpoint is conventional — what matters is which samples go left and which go right.

Generating Threshold Candidates for sq_ft

Sorted unique values: [650, 850, 1100, 1200, 1400, 1600, 1900, 2100]

7 midpoint candidates:

Computing IG for Each Threshold

Root $H=1.0$ bit. For each threshold: compute left/right class distributions, entropy, weighted average, and IG.

Computing $H$ for $t=750$ right node (6 expensive out of 7, 1 affordable):

$H=-(1/7){\log }_2(1/7)-(6/7){\log }_2(6/7)=-(1/7)(-2.807)-(6/7)(-0.222)=0.401+0.190=0.592$

Best split: $t=1300$ with IG = 1.0 — all 4 affordable houses have sq_ft ≤ 1300 and all 4 expensive have sq_ft > 1300. Perfect separation in one split.

All affordable houses (blue circles) are left of the green line; all expensive (red squares) are right. The IG bar chart shows $t=1300$ towering above all others.

Threshold Candidates for Bedrooms

Sorted unique bedroom values: [2, 3, 4, 5]. Three candidates: 2.5, 3.5, 4.5.

bedrooms ≤ 3.5 also achieves IG = 1.0 — a perfect tie with sq_ft ≤ 1300.

How the Algorithm Handles Tied Splits

When multiple thresholds (or features) produce the same IG, sklearn picks the first feature encountered in sorted order. With sq_ft as feature 0 and bedrooms as feature 1, sq_ft wins the tie.

This means feature column order in the input matrix can affect the tree structure when splits are tied. In practice, exact ties are rare on large datasets with continuous features — unique thresholds from different features rarely produce identical IG.

sklearn Confirmation

from sklearn.tree import DecisionTreeClassifier, export_text
import numpy as np

X = data[['sq_ft', 'bedrooms']].values
y = data['expensive'].values

dt = DecisionTreeClassifier(criterion='entropy', max_depth=1, random_state=42)
dt.fit(X, y)

print("Root split:")
print(f"  Feature: {'sq_ft' if dt.tree_.feature[0]==0 else 'bedrooms'}")
print(f"  Threshold: {dt.tree_.threshold[0]:.2f}")
print(f"  Left samples: {dt.tree_.n_node_samples[1]}")
print(f"  Right samples: {dt.tree_.n_node_samples[2]}")
print()
print(export_text(dt, feature_names=['sq_ft', 'bedrooms']))

One split, two leaves, 100% training accuracy. The threshold is exactly 1300 (sklearn uses the actual feature value at the split, not the midpoint).

Computational Complexity

At each node:

• For each of $p$ features: sort $n$ values → $O(n\log n)$, then scan $n-1$ thresholds → $O(n)$
• Total per node: $O(np\log n)$

For a full tree of depth $d$ (worst case: balanced binary tree with $2^d$ nodes, each containing $n/2^d$ samples):

$\text{Total}={\sum }_{k=0}^d{2}^k\times O\left(\frac{n}{2^k}\cdot p\cdot \log \frac{n}{2^k}\right)\approx O(n\cdot p\cdot d)$

For a full tree with $d=\log n$ (one sample per leaf): $O(np\log n)$.

High Cardinality and max_features

With 100,000 unique sq_ft values: 99,999 threshold candidates per feature. With 100 features: 10 million IG computations per node.

sklearn's max_features='sqrt' subsamples features at each split: only $\sqrt{p}$ features are considered. This is the key trick used in Random Forest — each tree considers a random subset of features, making trees different from each other (decorrelated), which reduces variance when averaging.

Test Your Understanding

1. For $t=750$: the left node has 1 sample (all affordable), the right has 7. The weighted entropy is $0+(7/8)\times H(1/7,6/7)=0.518$. IG = 0.482. Why isn't this as good as $t=1300$ (IG=1.0), even though the left node is also pure?

2. The algorithm evaluates $n-1$ midpoints, not arbitrary real-valued thresholds. Prove that using the midpoint vs any value between $x_i$ and $x_{i+1}$ produces the same left/right partition and hence the same IG.

3. bedrooms ≤ 3.5 and sq_ft ≤ 1300 both achieve IG=1.0. If bedrooms were listed first in the DataFrame (column 0), which split would sklearn choose? Write the exact code change needed to verify this.

4. Computational complexity is $O(np\log n)$ per node. sklearn's max_features='sqrt' reduces this to $O(n\sqrt{p}\log n)$. For $n=10,000$ and $p=100$: compute the speedup factor. What is the tradeoff?

5. After the root split at $t=1300$, both child nodes are pure ($H=0$). Would the tree continue splitting if you removed the max_depth=1 constraint? What does sklearn do at a pure node?