Why Categorical Predictors Need Subset Splits
A numeric predictor has a natural order, so a threshold can divide its values into a lower group and an upper group. Categorical levels do not necessarily have such an order. For a predictor recording a policy's distribution channel, for example, the levels might be “online,” “broker,” and “branch.” A classification tree can still make a binary split, but it must decide which levels go to one child and which go to the other.
The goal is to find a partition that separates observations with different class compositions. Once the partition is selected, the branches have a direct interpretation: one contains the observations whose predictor level belongs to a specified subset, and the other contains all remaining levels. The split does not assign an order to the categories.
A subset and its complement describe the same partition with the child labels reversed: \(S\) versus \(S^c\) is the same division as \(S^c\) versus \(S\). Therefore, there are \(2^{K-1}-1\) distinct nontrivial binary partitions of \(K\) levels. For three levels, there are three: each level by itself versus the other two. For four levels, there are seven: four singleton-versus-rest partitions and three distinct two-versus-two partitions.
The split criterion evaluates the class composition in each child, accounting for the child sizes. In the examples below, Gini impurity is used. For a node with positive-class proportion \(p\), its Gini impurity is \(2p(1-p)\). The weighted child impurity is the sum of each child’s impurity multiplied by that child’s fraction of the parent observations. The reduction is parent impurity minus weighted child impurity; a larger reduction indicates a stronger split by this criterion.
Worked Subset Splits
Worked Example: Comparing All Splits for Three Levels
A hypothetical claims triage team records the predictor level and whether a claim requires further review. The positive class means “requires review.” Counts are \(U: 6\) positive and \(2\) negative, \(V: 2\) positive and \(6\) negative, and \(W: 4\) positive and \(4\) negative. Using Gini impurity, compare the distinct partitions and identify the best split.
Method and parent impurity. There are \(24\) observations, with \(12\) positive and \(12\) negative. Thus \(p=12/24=0.5\), and the parent impurity is
There are three distinct partitions. For \(U\) versus \(\{V,W\}\), the left child has \(6\) positive and \(2\) negative observations, so its positive proportion is \(6/8=0.75\) and its impurity is \(2(0.75)(0.25)=0.375\). The right child has \(6\) positive and \(10\) negative observations, so its positive proportion is \(6/16=0.375\) and its impurity is \(2(0.375)(0.625)=0.46875\). Weighting by the child sizes gives
The reduction is \(0.5-0.4375=0.0625\). For \(V\) versus \(\{U,W\}\), the \(V\) child has \(2/8=0.25\) positive, while the other child has \(10/16=0.625\) positive. Their impurities are \(0.375\) and \(0.46875\), respectively, so the weighted child impurity is again \(0.4375\), giving a reduction of \(0.0625\).
For \(W\) versus \(\{U,V\}\), both children have a positive proportion of \(0.5\). Each child’s impurity is \(0.5\), so the weighted child impurity is \(0.5\) and the reduction is \(0\). The first two partitions tie for the largest reduction, \(0.0625\). Common mistake avoided: the tie does not make the reduction \(0.0938\); the child impurities must be weighted by their sizes before subtracting from the parent impurity.
Check. In the selected \(U\) split, the weighted child positive proportion is \((8/24)(0.75)+(16/24)(0.375)=0.5\), equal to the parent proportion. The calculation uses all \(24\) observations.
Worked Example: Finding a Two-Level Grouping
A hypothetical underwriting review data set has four levels of a categorical application source. For each level, the counts are \(A: 9\) positive and \(1\) negative, \(B: 7\) positive and \(3\) negative, \(C: 3\) positive and \(7\) negative, and \(D: 1\) positive and \(9\) negative. Find the best split by Gini reduction, checking both singleton-versus-rest and two-versus-two partitions.
Parent. Each level has \(10\) observations, so there are \(40\) observations total and \(20\) positive. The parent proportion is \(0.5\), and its Gini impurity is \(0.5\). Four levels give seven distinct partitions. Complementary subsets are counted only once.
Two-versus-two candidates. For \(\{A,B\}\) versus \(\{C,D\}\), the left child has \(16/20=0.8\) positive and Gini impurity \(2(0.8)(0.2)=0.32\). The right child has \(4/20=0.2\) positive and also has impurity \(0.32\). Both children have size \(20\), so the weighted impurity is \(0.32\), and the reduction is \(0.5-0.32=0.18\).
For \(\{A,C\}\) versus \(\{B,D\}\), each child has \(12\) positive out of \(20\), or proportion \(0.6\), giving impurity \(2(0.6)(0.4)=0.48\) in each child. The reduction is \(0.5-0.48=0.02\). For \(\{A,D\}\) versus \(\{B,C\}\), each child has \(10/20=0.5\) positive, so the reduction is \(0\).
Singleton-versus-rest candidates. For \(A\) versus \(\{B,C,D\}\), the \(A\) child has proportion \(0.9\) and impurity \(0.18\). The other child has \(11/30\) positive, so its impurity is
The weighted child impurity is \((10/40)(0.18)+(30/40)(418/900)=0.045+0.348333\ldots=0.393333\ldots\). The reduction is \(0.106666\ldots\), or \(0.1067\) to four decimal places. The \(D\)-versus-rest partition has the same reduction by symmetry. For \(B\) versus the rest, the child proportions are \(0.7\) and \(13/30\); the impurities are \(0.42\) and \(2(13/30)(17/30)=442/900\). The weighted impurity is \(0.25(0.42)+0.75(442/900)=0.473333\ldots\), giving reduction \(0.0267\). The \(C\)-versus-rest partition is symmetric and has the same reduction.
The largest reduction is \(0.18\) for \(\{A,B\}\) versus \(\{C,D\}\). The branch interpretation is that levels \(A\) and \(B\) form one child, while \(C\) and \(D\) form the other. Common mistake avoided: checking only singleton-versus-rest partitions would miss the best split.
Check. The chosen children each contain \(20\) observations, and their positive counts, \(16\) and \(4\), sum to the parent’s \(20\) positives.
Why the Gini Reduction Reflects Separation
For a binary response, the reduction from a split has a useful form. Let the left and right child weights be \(w_L\) and \(w_R\), with \(w_L+w_R=1\), and let their positive-class proportions be \(p_L\) and \(p_R\). The parent proportion is their weighted average, \(p=w_Lp_L+w_Rp_R\). The weighted Gini reduction is
To justify the identity, divide both sides by \(2\) and expand the left side as \(p-p^2-w_Lp_L+w_Lp_L^2-w_Rp_R+w_Rp_R^2\). Since \(p=w_Lp_L+w_Rp_R\), the linear terms cancel, leaving \(w_Lp_L^2+w_Rp_R^2-p^2\). Expanding \(p^2=(w_Lp_L+w_Rp_R)^2\) and using \(w_L+w_R=1\) gives \(w_Lw_R(p_L-p_R)^2\), as required.
This result explains two features of the criterion. First, a split has no Gini reduction if both children have the same positive proportion. Second, all else equal, a larger difference in child proportions produces a larger reduction. The child weights still matter: a very small child cannot be treated as though it contains half the parent observations.
Category Labels Are Not Numeric Measurements
A category may be stored as a number for data-processing purposes, but that does not make it quantitative. Suppose levels are coded as \(1\), \(2\), and \(3\). A numeric threshold at \(1.5\) divides level \(1\) from levels \(2\) and \(3\), while a threshold at \(2.5\) divides levels \(1\) and \(2\) from level \(3\). These are only two of the three possible partitions. The split \(\{1,3\}\) versus \(\{2\}\) cannot be represented by one threshold on this coding.
More importantly, the codes may be arbitrary. If the labels are recoded, the numeric thresholds can produce different groups even though the underlying observations and categories have not changed. A subset split instead refers to the category membership itself. An ordered categorical predictor may sometimes have a meaningful order, but treating it as numeric still imposes a particular threshold structure; that choice needs justification rather than being inferred from its storage format.
Worked Example: Interpreting a Split Without Imposing an Order
A hypothetical service team records the channel associated with an application and whether the application needs manual review. Counts are online: \(18\) positive and \(2\) negative; agent: \(8\) positive and \(12\) negative; branch: \(4\) positive and \(16\) negative. Select the best of the three distinct binary subset splits using Gini impurity, then explain why a numeric coding of the channels is not a general substitute.
Parent impurity. There are \(30\) positive and \(30\) negative observations, so the parent proportion is \(0.5\) and its Gini impurity is \(0.5\).
Online versus the other channels. The online child has \(18/20=0.9\) positive, with impurity \(2(0.9)(0.1)=0.18\). The other child has \(12/40=0.3\) positive, with impurity \(2(0.3)(0.7)=0.42\). Its weighted impurity is \((20/60)(0.18)+(40/60)(0.42)=0.06+0.28=0.34\). The reduction is \(0.5-0.34=0.16\).
Agent versus the other channels. The agent child has \(8/20=0.4\) positive and impurity \(0.48\). The other child has \(22/40=0.55\) positive and impurity \(2(0.55)(0.45)=0.495\). The weighted impurity is \((20/60)(0.48)+(40/60)(0.495)=0.16+0.33=0.49\), so the reduction is \(0.01\).
Branch versus the other channels. The branch child has \(4/20=0.2\) positive and impurity \(0.32\). The remaining child has \(26/40=0.65\) positive and impurity \(2(0.65)(0.35)=0.455\). The weighted impurity is \((20/60)(0.32)+(40/60)(0.455)=0.106666\ldots+0.303333\ldots=0.41\), giving a reduction of \(0.09\). Thus the best partition is online versus \(\{\text{agent},\text{branch}\}\), with reduction \(0.16\).
The resulting branches can be read as “online applications” and “applications through an agent or branch.” Suppose instead the labels are coded online \(=1\), agent \(=2\), branch \(=3\). A threshold at \(1.5\) happens to reproduce the best split in this coding. But with online \(=3\), agent \(=1\), branch \(=2\), the threshold at \(1.5\) isolates the agent level instead. The categories have not changed; only their arbitrary codes have. Common mistake avoided: a threshold on category codes can suggest a false order and omit valid subsets.
Check. The online child contains \(20\) observations, and the combined agent-and-branch child contains \(40\); their positive counts, \(18\) and \(12\), recover the parent total of \(30\).
Practical Checks When Evaluating a Split
Before accepting a proposed subset split, check both its arithmetic and its interpretation. Every observation must enter exactly one child, and the child class counts must add to the parent class counts. The weighted child impurity must use the fraction of observations in each child, not an unweighted average unless the child sizes are equal. Finally, compare distinct partitions rather than counting a subset and its complement as two different candidates.
- Read the branch condition literally. “Level is in \(S\)” goes to one child; “level is not in \(S\)” goes to the other.
- Keep category membership separate from numerical coding. Codes are labels unless the variable has a meaningful quantitative or ordered interpretation.
- Use the stated split criterion. The examples use Gini reduction; a choice made under one criterion should not be described as automatically optimal under every criterion.
- Check the parent totals. The weighted child proportions and class counts must be consistent with the parent node.
A categorical subset split is useful because it lets the tree group levels with similar response compositions without inventing a numeric distance or order between them. The resulting rule is concise, auditable, and directly connected to the observed categories.
Check Your Understanding
For each problem, treat positive and negative as the two response classes. Use Gini impurity where requested.
- A predictor has levels \(P: 7\) positive and \(3\) negative, \(Q: 3\) positive and \(7\) negative, and \(R: 2\) positive and \(8\) negative. Compare the three singleton-versus-rest partitions. Which has the greatest Gini reduction? (Answer: \(\{P\}\) versus \(\{Q,R\}\), with reduction \(0.0938\) to four decimal places.)
- Four equally sized levels have counts \(A: 8/2\), \(B: 6/4\), \(C: 4/6\), and \(D: 2/8\), where each pair is positive/negative. What is the greatest Gini reduction among the distinct partitions? (Answer: \(\{A,B\}\) versus \(\{C,D\}\), with reduction \(0.0800\).)
- A categorical predictor has five observed levels. How many distinct nontrivial binary subset partitions are possible if a subset and its complement count as the same partition? (Answer: \(2^{5-1}-1=15\).)
- A three-level predictor is coded \(1,2,3\), but its labels have no natural order. Explain what partition a threshold of \(1.5\) produces, and state one limitation of considering only numeric thresholds. (Answer: It separates level \(1\) from levels \(2\) and \(3\); it cannot represent every possible subset split, and recoding the labels can change the threshold partition.)
- A proposed split has child weights \(w_L=0.4\) and \(w_R=0.6\), with positive proportions \(p_L=0.8\) and \(p_R=0.3\). What is its Gini reduction? (Answer: \(2(0.4)(0.6)(0.8-0.3)^2=0.1200\).)