Selection Bias Toward High Cardinality Features in Trees

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 237 papers54 conceptsfrozen 2026-10-04

In the ideal world of machine learning, a model selects features based solely on their predictive power. However, decision trees and their ensemble descendants—such as Random Forests—suffer from a systematic "cheating" mechanism known as selection bias. These algorithms frequently favor features with a high number of unique values (high cardinality) or continuous ranges, even when those features contain nothing but random noise.

The Multi-Valued Attribute Trap

The root of this bias lies in how decision trees partition data. Algorithms like ID3 and CART use heuristics such as Information Gain or the Gini Index to decide which attribute to split on. As Igor Kononenko 0001 demonstrated in On Biases in Estimating Multi-Valued Attributes, these metrics are fundamentally biased toward attributes with many possible values.

To understand why, imagine a dataset where one feature is a "Unique ID" and another is a "Boolean Flag." The Unique ID provides a perfect partition of the training data, reducing impurity to zero instantly, even though it has zero predictive power for new, unseen data. Jinhua Zhu notes in Classification Optimization Clustering Model Simulation Based on User Interest that this leads to inefficient splitting and poor generalization, as the model mistakes the granularity of the data for actual signal.

Why Trees Prefer Continuous Data

This bias extends beyond categorical variables to continuous ones. In ControlBurn: Feature Selection by Sparse Forests, Brian Liu and colleagues explain that continuous features offer a much larger number of potential split points compared to binary or low-cardinality features.

Every unique value in a continuous feature represents a potential threshold for a split. In a finite sample, a feature with thousands of possible split points is statistically more likely to find a partition that reduces impurity by sheer chance. Marvin N. Wright highlights this danger in Random forests for survival analysis using maximally selected rank statistics, showing that clinical "gold standard" binary variables are often buried under noisy continuous data because the tree algorithm is attracted to the flexibility of the latter.

The Failure of Mean Decrease Impurity

The most common way to measure feature importance in Random Forests is Mean Decrease Impurity (MDI). While MDI is computationally efficient, it exacerbates selection bias. Gilles Louppe and colleagues proved in Understanding variable importances in forests of randomized trees that while MDI works in theoretical infinite-data regimes, it fails in practical, finite-sample applications by inflating the importance of high-cardinality variables.

This inflation is linked to tree depth. As Xiao Li 0051 explains in A Debiased MDI Feature Importance Measure for Random Forests, deeper trees provide more opportunities for high-cardinality noise to coincidently align with the target variable. This creates a "masking effect" where truly relevant but low-cardinality features—like a specific genotype in a medical study—are ranked lower than irrelevant high-cardinality noise, as noted by Dhruv Agarwal in Predicting Onset of Dementia in Parkinson's Disease Patients.

Toward Unbiased Feature Importance

To fix these distortions, researchers have moved toward "out-of-sample" evaluations. Giles Hooker and Zhengze Zhou proposed an unbiased modification in Unbiased Measurement of Feature Importance in Tree-Based Methods that ensures irrelevant features receive a score of zero on average by using data not seen during the split-finding process.

Similarly, the MDI-oob measure developed by Xiao Li 0051 reframes impurity reduction as a sample covariance and evaluates it using "out-of-bag" data. By separating the data used to find the split from the data used to evaluate its importance, these methods neutralize the "split point advantage" of high-cardinality features. Other approaches, such as the conditional inference trees used by Andreas Groll in Prediction of the FIFA World Cup 2018, change the splitting criterion itself to be statistically independent of the number of categories, ensuring a level playing field for all variable types.

Papers in this version

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 19 papers
  2. Version 1 · 2026-10-04 · 37 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_impurity_based_importance_bias_1d254555,
  title = {impurity-based importance bias},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/impurity-based-importance-bias/rdr_1d254555387841eab43c9f2e78932b33},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_selection_bias_toward_high_cardinality_f_1d254555_v1,
  title = {Selection Bias Toward High Cardinality Features in Trees},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/selection-bias-toward-high-cardinality-features-in-trees/rdr_1d254555387841eab43c9f2e78932b33/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}