Splitting Categorical Predictors Into Groups

How a Categorical Predictor Splits a Node

A tree split on a categorical predictor does not usually separate levels by a numerical threshold. Instead, it assigns the predictor's levels to two groups. One child receives observations whose level is in the first group; the other receives observations whose level is in the second. The split is binary even when the predictor has many categories.

For example, a hypothetical insurance model might split a node according to whether a policy's distribution channel is in the group {agent, broker} or the group {direct, online}. The labels themselves have no numerical order. What matters is whether that partition improves the tree's chosen prediction criterion.

The word “observed” matters: a level with no observations in the node cannot contribute evidence to that node's split. In practice, candidate splits must also respect any restrictions imposed by the tree-growing procedure, such as minimum child size. The calculations below assume the stated levels have observations and that no additional restrictions rule out a candidate.

Unordered Factors: Subsets, Not Thresholds

For an unordered factor, there is no meaningful sequence of levels. A candidate split can use any nonempty proper subset on one side, with all remaining levels on the other. If the levels are A, B, C, and D, for instance, {A, C} versus {B, D} is a valid split even though its groups are not consecutive in the alphabet.

A partition and its complement describe the same split: {A, C} versus {B, D} is identical to {B, D} versus {A, C}. The number of distinct binary partitions is therefore smaller than the number of subsets.

There are \(2^K\) subsets of \(K\) levels. Excluding the empty set and the full set leaves \(2^K-2\) nonempty, proper subsets. Each split is counted twice in that total, once for each side chosen as the subset, so division by two gives \(2^{K-1}-1\). With 4 levels this is 7 splits; with 10 levels it is 511; with 20 levels it is 524,287.

This count explains why a direct exhaustive search can become impractical for a factor with many levels. Tree methods may use restrictions or computational shortcuts, but those choices can change which candidate groupings are considered. A fitted tree's split should therefore be interpreted as the grouping selected under its search procedure, not necessarily as the result of checking every possible partition.

Evaluating a Regression Split

For a regression tree using squared error, each child predicts the mean response among observations in that child. A candidate category partition is scored by adding the squared errors in the two children. The preferred candidate, among those considered, has the smallest total child squared error.

Here \(L\) and \(R\) denote the two groups of observations created by the split, \(y_i\) is an observed response, and \(\bar{y}_g\) is the mean response in child \(g\). This comparison concerns the observations in the node being split; the parent-node error is the same for every candidate at that node.

Why the Regression Calculation Can Be Decomposed

A useful identity explains how category-level summaries relate to the child SSE. Suppose a child contains categories \(j\), with \(n_j\) observations, category mean \(\bar{y}_j\), and within-category SSE \(W_j=\sum_{i\in j}(y_i-\bar{y}_j)^2\). Its overall mean is \(\bar{y}\). Then

To see why, write each response's deviation as \(y_i-\bar{y}=(y_i-\bar{y}_j)+(\bar{y}_j-\bar{y})\), square it, and sum within category \(j\). The cross term is \(2(\bar{y}_j-\bar{y})\sum_{i\in j}(y_i-\bar{y}_j)\), which is zero because deviations from the category mean sum to zero. The remaining terms are the within-category SSE and \(n_j(\bar{y}_j-\bar{y})^2\). Summing over categories gives the identity. It shows that child error includes both variation within levels and variation between their means.

For the first child in the example, each category has within-category SSE 2, so the within-category total is \(2+2=4\). The category means are 1 and 3, each based on 2 observations, and the child mean is 2. The between-category term is \(2(1-2)^2+2(3-2)^2=4\). The child SSE is therefore \(4+4=8\), agreeing with the direct calculation.

Classification Splits and Weighted Impurity

For classification, a split is assessed by the impurity of each child, weighted by that child's share of the observations. For a binary response, Gini impurity is \(2p(1-p)\), where \(p\) is the proportion of one class in the node. It is zero when all observations belong to one class and is largest at \(p=0.5\). For a multiclass response, Gini impurity is \(1-\sum_c p_c^2\), where \(p_c\) is the proportion in class \(c\).

Here \(n_L\) and \(n_R\) are the child sizes, \(n=n_L+n_R\), and \(I_L,I_R\) are their impurities. When the parent node is fixed, the split with the largest reduction from parent impurity has the smallest weighted child impurity. The same weighted-comparison principle applies when using another impurity measure, such as entropy.

Ordered Factors: Adjacent Groups

An ordered factor has a meaningful sequence, such as low, moderate, high, and very high. If the split is required to respect that order, each candidate divides the sequence at a cut point: levels below the cut go left and levels above it go right. With \(K\) levels, there are \(K-1\) such adjacent splits, rather than \(2^{K-1}-1\) unrestricted partitions.

Whether to require adjacent groups is a modeling decision. An order does not imply equal spacing: the difference between “low” and “moderate” need not equal the difference between “high” and “very high.” Treating the labels as consecutive ranks for candidate splits is also not the same as treating their codes as a quantitative predictor with meaningful numerical distances. If nonadjacent groupings are allowed, an ordered factor can still have the full set of subset partitions.

Common Trap: Treating Category Codes as Measurements

Suppose four unordered levels happen to be stored as codes 1, 2, 3, and 4. Those codes identify levels; they do not establish a meaningful order or distance. A numerical threshold search would consider only the contiguous partitions {1} versus {2, 3, 4}, {1, 2} versus {3, 4}, and {1, 2, 3} versus {4}. It would miss valid noncontiguous subsets.

For a concrete check, suppose each level has four observations, with event counts 4, 0, 4, and 0, respectively. The unordered split {1, 3} versus {2, 4} makes both children pure, so weighted Gini is 0. A threshold search on the codes cannot make that split: its best candidate has weighted Gini \(1/3\) (the first or last cut). Thus coding labels as numbers can exclude a substantially better grouping. For a genuinely ordered factor, adjacent cuts may be appropriate; for an unordered factor, do not impose an order merely because software stores labels using integers.

Category-split search matters because a factor can represent meaningful groups that are not captured by one numerical threshold. At the same time, the number of candidate partitions grows rapidly, so the search method and any restrictions affect the result. Interpret the selected grouping in context, verify that its levels are genuinely categorical, and distinguish an ordered cut from an arbitrary subset split. These considerations are aligned with the SOA Exam PA (Predictive Analytics) syllabus.