Categorical Splits in Decision Trees

Splitting on a numeric feature like leverage ratio is straightforward: try every threshold between sorted values and pick the best. A categorical feature like GICS sector, with say 11 values, has no natural order to sweep a threshold across — a split has to choose which subset of categories goes left. With 11 categories there are $2^{10}-1 = 1023$ ways to divide them. A feature with 50 or 500 categories makes brute-force search infeasible.

The analogy: sorting by rank versus sorting by suit

Splitting a numeric feature is like sorting cards by rank — a natural order makes a threshold a single obvious cut. Splitting a categorical feature is like sorting by suit with no inherent order — "hearts and spades one way, clubs and diamonds the other" is a choice of grouping, and there are many groupings to consider with no built-in sense of which to try first.

The mechanics: reducing an exponential search to a sorted one

Trying every subset is exponential, $2^{q-1}-1$ for $q$ categories, infeasible past roughly 20–25 levels. For binary classification (and similarly for regression), sort categories by the proportion of the positive class within each, then only consider splits along that sorted order — turning the categorical search back into a threshold search. This works because the best possible subset split, under Gini or squared-error, is guaranteed to appear somewhere along this sorted ordering.

$$\text{sort categories by } \hat p(\text{class}=1\mid\text{category}), \quad \text{search only the } q-1 \text{ splits along this order.}$$

In plain English: sort categories by how strongly each associates with the positive outcome, and only consider dividing that sorted list into a "low" group and "high" group — an exponential search reduced to a linear one, with no loss of optimality for a single split.

Worked example: sorting sectors by default rate

Splitting on sector (6 categories) to predict bond default: Utilities 2%, Staples 3%, Healthcare 5%, Industrials 9%, Energy 14%, Discretionary 18%. Instead of checking all 31 subsets, check only the 5 splits along this sorted order. Suppose the best split (by Gini reduction) is {Utilities, Staples, Healthcare} (avg 3.3%) versus {Industrials, Energy, Discretionary} (avg 13.7%) — a clean grouping found directly, without enumerating the other 26 subsets.

The log curve above illustrates the shape of the savings: search cost grows only with the number of categories once sorted, not with $2^q$ — the difference between a search that scales and one that doesn't.

What this means in practice

High-cardinality categoricals (tickers, order IDs, exchange codes) are where careless categorical splitting causes trouble: with enough categories, a tree can find a subset split that perfectly separates training data by chance, especially with few observations per category. Cross-validation and minimum-leaf-size constraints matter more here than for numeric splits, precisely because the search space is so much larger.