Categorical Feature Handling in Boosted Trees
Why categorical features are awkward for trees
A tree split on a numeric feature is a simple threshold: $x_j \leq t$. A categorical feature has no inherent order, so a split must instead partition its categories into two groups: $x_j \in S$ vs. $x_j \notin S$. For a feature with $k$ categories, there are $2^{k-1} - 1$ possible binary partitions — exhaustive search is fine for small $k$ but explodes combinatorially for high-cardinality features like user IDs or zip codes, which is the core engineering problem every boosting library has to solve.
One-hot encoding: simple but costly at high cardinality
The naive fix is one-hot encoding: turn a $k$-category feature into $k$ binary columns. This sidesteps the partition problem entirely (each binary column gets an ordinary threshold split) but it fragments the data — each resulting feature is sparse and a tree needs multiple splits to express a relationship that a single native categorical split could capture in one step. For high-cardinality features, one-hot encoding also massively inflates the feature space and dilutes the signal available to each individual split.
Optimal partitioning via Fisher's algorithm
For regression trees (and binary classification, approximately), Fisher (1958) showed that if you sort categories by their mean target value, the optimal binary partition into two groups is guaranteed to be found among splits along that sorted order — reducing the search from $2^{k-1}$ candidate partitions to just $k-1$. LightGBM implements exactly this: sort categories by $\frac{\sum \text{gradient}}{\sum \text{hessian}}$ (the natural per-category 'target affinity' under the current boosting loss) and search only along that ordering. This gives native categorical splits at a tractable cost without needing one-hot encoding at all.
import numpy as np
# Toy example: 5 categories, each with a mean target value
categories = ["A", "B", "C", "D", "E"]
mean_target = {"A": 0.1, "B": 0.8, "C": 0.3, "D": 0.9, "E": 0.2}
# Fisher's method: sort by mean target, then only consider
# the k-1 splits along that sorted order (not all 2^(k-1) partitions)
sorted_cats = sorted(categories, key=lambda c: mean_target[c])
print("Sorted order:", sorted_cats) # ['A', 'E', 'C', 'B', 'D']
candidate_splits = []
for i in range(1, len(sorted_cats)):
left, right = sorted_cats[:i], sorted_cats[i:]
candidate_splits.append((left, right))
for left, right in candidate_splits:
print(f" split: {left} vs {right}")
# Only 4 candidate splits needed instead of 2^4 - 1 = 15 possible partitions
Target-based category encoding is leakage-prone without care
| Method | Search space | Leakage risk | Handles high cardinality |
|---|---|---|---|
| One-hot encoding | k independent binary splits | None | Poor — sparse, dilutes signal |
| Fisher optimal partition | k-1 ordered splits | Low if target stats regularized | Good |
| Naive target mean encoding | 1 numeric feature | High without safeguards | Good, but risky |
What's next?
Handling categories well only prevents one kind of overfitting; boosted trees still need a mechanism to decide when to simply stop adding more trees altogether, which is a distinct and equally important regularization lever in the training loop.
I build these systems professionally.
Whether it's a RAG pipeline, analytics migration, or AI workflow — let's talk.