High-Cardinality Predictors And Impurity Importance

Why the Number of Split Opportunities Matters

A decision tree searches for a split that reduces impurity. A predictor with many distinct values can offer many candidate split points, while a predictor with only a few values may offer very few. Even when neither predictor has a genuine relationship with the response, searching more alternatives creates more opportunities to find an apparently favorable split by chance. A forest can then repeatedly select the high-cardinality predictor and assign it substantial impurity-based importance.

This is a property of the selection procedure, not proof that every high-cardinality predictor is misleading. The size of the effect depends on the data, split constraints, tree-building procedure, and the predictor's relationship with the response. The key interpretation is that impurity importance can reflect both predictive signal and the number of opportunities a predictor had to win the split search.

Definition: At a node containing $n_t$ observations, let $I(t)$ denote the node's impurity. For a split into left and right children, with $n_L+n_R=n_t$, the decrease in impurity is $$ \Delta I(t)=I(t)-\frac{n_L}{n_t}I(L)-\frac{n_R}{n_t}I(R). $$ The split is useful to the tree-building criterion when this decrease is positive. Mean decrease in impurity (MDI) for a predictor sums its decreases over the nodes where it is used, weighting each node's decrease by the proportion of the training observations reaching that node, and then typically averages over trees. Implementations may differ in normalization and weighting details.

Impurity and Candidate Splits

For a classification tree using the Gini impurity, if the proportions in the node's $C$ classes are $p_1,\ldots,p_C$, then

I_G(t)=1-\sum_{c=1}^{C}p_c^2.

A node with all observations in one class has Gini impurity zero. A node split into children is assessed by comparing its impurity with the size-weighted average impurity of those children. For a regression tree using squared-error splitting, the corresponding impurity is the within-node mean squared deviation from the node mean; the same weighted-decrease structure applies.

For a numeric predictor with $q$ distinct observed values, the usual candidate cutpoints lie between successive sorted values, giving at most $q-1$ cutpoints. For an unordered categorical predictor with $L$ levels, an exhaustive search over binary partitions has $2^{L-1}-1$ distinct partitions: a partition and its complement describe the same split. Actual algorithms may use restrictions or shortcuts, so these counts describe the exhaustive possibilities, not necessarily every implementation.

Worked Example: Comparing Two Candidate Splits

A hypothetical tree is built from 10 policy records, five in each of two outcome classes. A numeric predictor has many distinct values and one candidate cutpoint divides the records into two groups of five. One child contains four records from class A and one from class B; the other contains one from class A and four from class B. Calculate the Gini decrease for this split. Then compare it with a second predictor's best split, whose Gini decrease is 0.14.

Method. Calculate the parent Gini impurity, calculate each child's impurity, and subtract the weighted child average from the parent. This comparison avoids treating the unweighted sum of child impurities as the split score.

At the parent, the class proportions are $5/10$ and $5/10$, so $$ I_G(t)=1-\left(\frac{5}{10}\right)^2-\left(\frac{5}{10}\right)^2 =1-0.25-0.25=0.50. $$ Each child has proportions $4/5$ and $1/5$, in either order. Thus each child's Gini impurity is $$ 1-\left(\frac45\right)^2-\left(\frac15\right)^2 =1-\frac{16}{25}-\frac{1}{25} =\frac{8}{25}=0.32. $$ Each child has five of the ten records, so the weighted child impurity is $$ \frac{5}{10}(0.32)+\frac{5}{10}(0.32)=0.32. $$ The split decrease is $0.50-0.32=0.18$. Since $0.18>0.14$, the tree's greedy criterion prefers this candidate over the other predictor's stated best split.

Check. The decrease is positive and less than the parent impurity. The high-cardinality predictor wins this local comparison, but the calculation does not establish that it will predict well on new data. The common mistake is to infer importance as evidence of genuine signal from a single winning split.

Why More Candidates Can Win by Chance

The reason for the bias can be seen without assuming that any candidate split contains real information. Imagine that each candidate split produces a score that is only random noise. The tree selects the largest score. If one predictor supplies many candidate splits and another supplies only a few, the first predictor has more chances to produce an unusually large score.

A simple calculation makes the direction of the effect explicit. Suppose, only for illustration, that $K$ candidate scores are independent and uniformly distributed between zero and $a$. Let $M_K$ be their maximum. For $0\leq x\leq a$, the event $M_K\leq x$ requires every score to be at most $x$, so

P(M_K\leq x)=\left(\frac{x}{a}\right)^K.

For a nonnegative random variable bounded by $a$, its expectation is the integral from zero to $a$ of the probability that it exceeds $x$. Therefore

E[M_K]=\int_0^a \left[1-\left(\frac{x}{a}\right)^K\right]dx =a-\frac{a}{K+1} =\frac{aK}{K+1}.

This illustrative model is not a claim that real candidate-split scores are independent or uniform. In practice, scores from nearby cutpoints are generally dependent. The derivation establishes the general multiple-opportunity logic: maximizing over more candidates can increase the expected winning score even when the candidates carry no signal.

Worked Example: Quantifying the Search Advantage

In a hypothetical null setting, suppose a low-cardinality predictor offers two candidate splits and a high-cardinality predictor offers 20. For illustration, model each candidate's noise-only score as independent and uniform from 0 to 0.10. Calculate the expected best score for each predictor and explain what the comparison does and does not show.

Method. Apply $E[M_K]=aK/(K+1)$ with $a=0.10$. This calculation isolates the effect of searching over different numbers of candidates; it does not model all dependencies in a real tree.

For two candidates, $$ E[M_2]=\frac{0.10(2)}{2+1}=\frac{0.20}{3}=0.0667 $$ to four decimal places. For 20 candidates, $$ E[M_{20}]=\frac{0.10(20)}{20+1}=\frac{2.00}{21}=0.0952 $$ to four decimal places. Thus, in this illustrative model, the predictor with 20 candidate splits has the larger expected winning noise score.

Check. Both expected scores are between zero and 0.10, and the second is closer to the upper bound because it is the maximum of more candidates. These values are not estimates of a real forest's bias; they demonstrate why a larger search can raise a best split score by chance.

Reading an Impurity-Importance Ranking

MDI accumulates selected split gains; it does not give every predictor the same number of chances to be selected. In a forest, a high-cardinality variable may be selected at many nodes across many trees. Its MDI can therefore be high even if its apparent gains arise partly from searching many cutpoints or category partitions. This issue concerns the ranking's interpretation, not whether the arithmetic sum of the selected gains was calculated correctly.

An identifier with many distinct values is a useful warning case. It may allow many cutpoints that isolate small groups of observations. If a split happens to align with response noise in the training data, the tree can record a positive impurity decrease. Repetition across trees can build up MDI. A large MDI for such an identifier should prompt scrutiny rather than an automatic conclusion that the identifier is substantively useful.

Worked Example: Identifying a High-Cardinality Ranking Bias

A hypothetical forest is built to classify whether a device requires service within 30 days. A policy reference code has one distinct value for almost every training record; a recorded inspection category has only four levels. Across three trees, the weighted impurity decreases attributed to the reference code are 0.08, 0.05, and 0.03. Those attributed to inspection category are 0.06 and 0.04, with no contribution in the third tree. Calculate the summed scores and normalized shares, then interpret the ranking.

Method. Sum each predictor's weighted decreases, then divide by the total across these two predictors to obtain shares. This makes the ranking's arithmetic transparent while avoiding the mistake of reading the larger share as proof of greater generalizable value.

The reference-code total is $$ 0.08+0.05+0.03=0.16, $$ and the inspection-category total is $$ 0.06+0.04+0=0.10. $$ The total importance represented by these two predictors is $0.16+0.10=0.26$. Their normalized shares are $$ \frac{0.16}{0.26}=0.6154 \qquad\text{and}\qquad \frac{0.10}{0.26}=0.3846, $$ to four decimal places. The reference code ranks first, with a share of about 61.54%, compared with 38.46% for inspection category. Averaging both totals over the same three trees would divide both by three and leave the ranking unchanged.

Interpretation and check. The two shares sum to 1.0000. The reference code's many distinct values offer many possible cutpoints, so its first-place MDI ranking may be inflated by split-search opportunities. The ranking alone does not show that the code would be useful for future devices. As discussed in the earlier material on permutation variable importance, checking predictive degradation under an appropriate permutation-based assessment can provide a different perspective; neither ranking should be interpreted without its method and context.

Practical Interpretation and Exam Traps

The high-cardinality effect is most relevant when an importance ranking is treated as a direct measure of a predictor's substantive or predictive value. MDI is tied to the tree's training split criterion and the set of candidates it searched. It can favor a variable because it offers many opportunities to achieve a reduction, rather than because that variable has a stable relationship with the response.

Do not turn this into an absolute rule that high-cardinality predictors must rank first or must be removed. A high-cardinality predictor can carry genuine signal, and a low-cardinality predictor can be irrelevant. The appropriate conclusion is narrower: the number of candidate splits can affect MDI, so a raw ranking is not a fair comparison of predictive value in every setting. Also, a predictor with many observed values may have fewer usable candidates after constraints such as minimum node size are applied.

When interpreting a ranking, distinguish three questions: how the importance score was calculated, how many split opportunities the predictors had, and whether the ranking is supported by evidence of predictive performance beyond the training split search. The earlier material on permutation importance provides a complementary assessment, but it too has its own interpretation and limitations.

Trap: equating a larger MDI with a stronger real relationship. Correct the interpretation by considering candidate counts and whether the predictor has credible predictive value.
Trap: counting category levels as the number of candidate splits. For exhaustive binary splits of $L$ unordered levels, the count is $2^{L-1}-1$, not $L$.
Trap: forgetting the node-size weights. A split's impurity decrease is weighted by the proportions of observations in its children; it is not simply the unweighted sum of child impurities.
Trap: claiming the bias is inevitable or identical in every implementation. The effect depends on available candidates, constraints, dependence among candidate scores, and how the forest computes importance.

Key takeaway: Impurity importance accumulates the gains from splits a tree selected. When a predictor offers many candidate splits, the best observed gain can be elevated by chance, so a high MDI ranking—especially for a near-identifier—does not by itself establish generalizable predictive value.

Check Your Understanding

For each question, distinguish the split-search count or impurity calculation from the broader interpretation of a predictor ranking.

A numeric predictor has 9 distinct observed values and the tree considers every cutpoint between adjacent values. How many candidate cutpoints are available? (Answer: 8.)
An unordered categorical predictor has 6 levels and the algorithm exhaustively considers binary partitions, counting complementary partitions only once. How many distinct partitions are available? (Answer: $2^{5}-1=31$.)
A classification node has 20 observations, 10 in each of two classes. A split makes two children of size 10, with class counts 7 and 3 in one child and 3 and 7 in the other. Calculate the Gini decrease. (Answer: parent $=0.50$, each child $=1-(49/100+9/100)=0.42$, weighted child impurity $=0.42$, decrease $=0.08$.)
Across a forest, predictor H has weighted impurity decreases 0.12 and 0.07; predictor L has 0.11 and 0.04. Calculate their normalized shares among these two predictors and state the ranking caution if H has many more distinct values. (Answer: H $=0.19$, L $=0.15$, total $=0.34$; H share $=0.5588$, L share $=0.4412$. H ranks first by MDI, but its greater split-search opportunity may inflate that ranking.)
In the illustrative independent-uniform model with candidate scores from 0 to 0.10, compare the expected maximum for 4 candidates with that for 9 candidates. (Answer: $0.10(4/5)=0.0800$ and $0.10(9/10)=0.0900$, respectively; the larger candidate set has the larger expected maximum.)

What You'll Learn