When building decision trees or ensembles like Random Forests and Gradient Boosting Tools, we rely on feature importance metrics to tell us which variables drive our model's decisions. However, standard tree induction algorithms possess a fundamental flaw: they are profoundly biased toward features with high cardinality—variables with a large number of unique categories or continuous values.
This bias means that a completely random, uninformative feature with thousands of unique values (like a User ID or a high-precision timestamp) will routinely be ranked as more important than a highly predictive binary feature (like a medical test result). To understand why this happens and how to fix it, we must look at how trees select their splits.
The Intuition: The Split Point Lottery
To understand why decision trees "cheat" in favor of high-cardinality features, imagine a game where you are trying to find a pattern in random noise.
When a decision tree evaluates a feature at a given node, it searches for a threshold or partition that best separates the target variable into pure subsets. For a binary feature (e.g., True or False), the algorithm has exactly one candidate split point to evaluate.
Now consider a continuous feature or a categorical feature with 1,000 unique levels. For a continuous variable, there are 999 potential split points. For an un-ordered categorical variable, there are $2^{999}-1$ possible ways to partition those categories into two groups.
Each candidate split point is like a ticket in a lottery. Because the high-cardinality feature holds thousands of times more tickets than the binary feature, it is vastly more likely to stumble upon a "lucky" split that happens to reduce training impurity purely by chance. As Zhang et al. demonstrate in Unbiased Gradient Boosting Decision Tree with Unbiased Feature Importance, standard gain estimation is mathematically biased toward non-negative values regardless of a feature's actual utility. The greedy algorithm evaluates the maximum gain across all possible splits; the maximum of many random variables is systematically larger than the maximum of just one.
The Mathematical Mechanism of Impurity Gain
This selection bias was identified early in the history of machine learning. Igor Kononenko, in the seminal paper On Biases in Estimating Multi-Valued Attributes, showed that traditional metrics like Information Gain and the Gini Index exhibit a linear bias where their scores increase proportionally with the number of attribute values.
When we aggregate these splits across an entire ensemble, we get Mean Decrease Impurity (MDI), the default feature importance metric in packages like scikit-learn. MDI sums up the total impurity reduction contributed by a feature across all trees.
In an ideal world with infinite data, MDI acts as a perfect information-theoretic decomposition. As Louppe et al. proved in Understanding variable importances in forests of randomized trees, totally randomized trees can isolate true variable relevance asymptotically. However, in practical, finite-sample regimes, this theoretical guarantee breaks down. The model begins to overfit the training data by carving it into smaller and smaller leaves using these high-cardinality features.
Binary Feature (1 Split Point) High-Cardinality Feature (Many Split Points)
[ Node ] [ Node ]
/ \ / | | \
[Yes] [No] [V1] [V2] [V3] [V4]...
(Low chance of accidental split) (High chance of finding an accidental
impurity reduction by pure luck)
This structural preference is not limited to categorical variables. As noted by Liu et al. in ControlBurn: Feature Selection by Sparse Forests, decision trees frequently exhibit a strong bias toward continuous features over discrete ones for the exact same reason: continuous variables provide a much larger pool of potential split thresholds.
Why This Matters: The Cost of Misleading Explanations
The consequences of high-cardinality bias extend far beyond suboptimal training metrics; they fundamentally undermine model interpretability and fairness.
- Misleading Domain Insights: In high-stakes domains like healthcare, this bias can be dangerous. Ward et al., in Explainable artificial intelligence for pharmacovigilance: What features are important when predicting adverse outcomes?, observed that standard tree-based importance metrics can rank random noise or unique administrative identifiers above actual clinical risk factors.
- Persistent Fairness Distortions: Shifting the objective function from accuracy to fairness does not eliminate the structural flaw. Little et al. demonstrated in Fair Feature Importance Scores for Interpreting Decision Trees that impurity-based metrics maintain their high-cardinality bias even when evaluating how much a feature contributes to systemic bias, potentially masking the true variables driving disparate impact.
- Overfitting and Generalization Collapse: When a model prioritizes high-cardinality features, it constructs overly complex trees with tiny leaf sizes. Peng et al. in Nonparametric Feature Selection by Random Forests and Deep Neural Networks and Zhu in Classification Optimization Clustering Model Simulation Based on User Interest emphasize that this false prioritization of uninformative variables leads to inefficient data splitting and poor generalization on unseen data. This pattern repeats across applications, from user interest clustering to natural language tasks like coreference resolution (Kobdani et al.).
How Modern Approaches De-Bias Tree Ensembles
To combat this, researchers have developed techniques that decouple feature evaluation from the training data splits.
Out-of-Bag (OOB) Evaluation
The core reason standard MDI fails is that it evaluates a split's quality on the same training data used to create the split. In A Debiased MDI Feature Importance Measure for Random Forests, Li et al. proposed MDI-oob. By mathematically reframing MDI as a sample covariance, they calculate the feature importance using only out-of-bag data—samples that a specific tree did not see during training.
If a tree splits on a noisy, high-cardinality feature, that split will fail to generalize to the out-of-bag data, and its calculated covariance will drop to zero or negative values. This penalty effectively neutralizes the advantage of having more split points.
Unbiased Gain and Data Splitting
For gradient boosting models, where out-of-bag samples are not naturally generated via bagging, alternative data-splitting frameworks are required. The UnbiasedGBM framework introduced by Zhang et al. isolates the split-finding step from the gain-estimation step. By calculating the final feature gain on an independent partition of the data, they ensure that lucky training splits do not translate into inflated feature importance scores.
Advanced Sampling and Structural Regularization
Other approaches target the underlying game-theoretic or structural properties of the ensemble:
- SHAFF: Benard et al. developed SHAFF: Fast and consistent SHApley eFfect estimates via random Forests, which uses advanced importance sampling within the tree structures to efficiently estimate Shapley effects, discounting noisy high-cardinality variables.
- Granular Computing: Zhenggang et al. in Parallel Decision Tree Algorithm Based on Granular Computing redefined information entropy through "data granules" to prevent high-cardinality attributes from dominating the splitting process.
By shifting away from naive in-sample impurity metrics toward validation-based or structurally regularized alternatives, modern machine learning pipelines can extract feature importances that reflect true predictive signal rather than the sheer quantity of unique values.
Key Foundational Work
On Biases in Estimating Multi-Valued Attributes (1995) — contributed 3 concept elements to this direction.
Flexibly Exploiting Prior Knowledge in Empirical Learning (1995) — contributed 1 concept elements to this direction.
Mining Approximate Top-K Subspace Anomalies in Multi-Dimensional Time-Series Data (2007) — contributed 1 concept elements to this direction.