Splitting Numerical Features in Decision Trees

You have a house and you want to know if it's worth over $300k. You know its square footage and number of bedrooms. These are numbers — 1200 sq ft, 3 bedrooms, on up. But a decision tree needs a yes/no question at every split. How do you turn a continuous number into a yes/no test?

You could ask "is sq_ft > 1200?" or "is sq_ft > 1500?" — the possible split points are infinite. The tree handles this by testing a finite set of thresholds 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.

What It Is

For categorical features, a split is simple: pick a value of the feature and partition the data. But continuous values have no natural categories — you need to choose a threshold. This is not like splitting on zip codes, where each group is already defined. A numerical split must carve a real-valued feature at some cut point, and the tree has to find the best one automatically.

The Plan — Three Phases to Finding the Best Numerical Split

We'll walk through how a decision tree handles continuous features. First we generate threshold candidates for sq_ft, then compute Information Gain for each one. Next we do the same for bedrooms. Finally we compare and see how the algorithm breaks ties.

Phase 1: Generate and Evaluate Thresholds for sq_ft

The goal: find the single sq_ft threshold that best separates affordable from expensive houses.

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, so the exact midpoint is just a convention.

Sorted unique sq_ft 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.

✓ Phase 1 complete. Best sq_ft threshold: $t=1300$ with IG = 1.0 — perfect separation.

Phase 2: Evaluate Thresholds for Bedrooms

Let's test the other feature with the same approach. Sorted unique bedroom values: [2, 3, 4, 5]. Three candidates: 2.5, 3.5, 4.5.

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.

✓ Phase 2 complete. Bedrooms threshold $t=3.5$ also achieves IG = 1.0 — a tie with sq_ft.

Phase 3: Break the Tie

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.

Trace Table: Numerical Split Search

✓ Phase 3 complete. Tie broken in favor of sq_ft.

sklearn Confirmation

Let's verify with sklearn. We set max_depth=1 to only grow one split — we just want to see which feature the tree picks at the root. We use random_state=42 for reproducible results, even though the tie-break here depends on column order, not randomness.

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']))

Root split:
  Feature: sq_ft
  Threshold: 1300.00
  Left samples: 4
  Right samples: 4

|--- sq_ft <= 1300.00
|   |--- class: 0
|--- sq_ft >  1300.00
|   |--- class: 1

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.

Related Concepts

The threshold scan here — evaluate all $n-1$ midpoints, pick max IG — is CART's algorithm. The same brute-force approach underlies every gradient boosting library; XGBoost, LightGBM, and CatBoost all evaluate threshold candidates per feature, though they use histogram approximations (pre-binning into 256 buckets) to avoid the full $O(n)$ scan at scale. The max_features parameter introduced here is the key mechanism that makes individual trees in a Random Forest uncorrelated — and uncorrelated errors average to near-zero.

Honest Limitations

Here's a scalability wall I've hit: the threshold scan is $O(n\log n+np)$ per node. On a dataset with 10M samples and 1000 features, a full scan at every node is prohibitive — I once watched a single tree train for 45 minutes before I killed it. sklearn's HistGradientBoostingClassifier pre-bins features into 256 buckets before training, which is dramatically faster at the cost of slightly approximate thresholds. It's now my go-to for large datasets.

I've also been surprised by how unstable tied thresholds make a tree. The winner depends on column order — which is arbitrary. I've had production models silently change their root split because a teammate reordered feature columns during preprocessing. Now I always fix column order and version it alongside the model artifact.

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?