On Biases in Estimating Multi-Valued Attributes

Igor KononenkoIJCAI 1995

Abstract

Decision tree induction algorithms frequently exhibit a bias toward attributes with a large number of possible values, potentially leading to overfitting on high-cardinality data. This paper evaluates eleven attribute selection measures using Monte Carlo simulations to determine their stability and bias. The results demonstrate that while traditional measures like Information Gain and the Gini-index suffer from a significant linear bias, normalized measures often over-correct, penalizing informative multi-valued attributes. The author proposes a novel approach based on the Minimum Description Length (MDL) principle, which provides a more stable and conservative estimation, alongside highlighting the robustness of the RELIEF-based measure.

Introduction

In machine learning, building an effective decision tree requires a robust heuristic to determine the "best" attribute for splitting data at each node. Ideally, this measure should identify the attribute providing the most information about the target class. However, a well-known flaw in early algorithms like ID3 is the "multi-valued bias," where attributes with many possible values (e.g., a Unique ID) are favored over simpler, more predictive ones (e.g., a Boolean flag). This paper investigates whether proposed statistical fixes hold up in realistic scenarios where attributes contain varying degrees of useful information.

Experimental Methodology

Rather than relying on static datasets, the study utilizes Monte Carlo simulations to precisely control variables. Each trial involves 600 training instances, with results averaged over 1000 random generations. The simulations vary the number of classes ($C = 2, 5, 10$) and the number of attribute values ($V = 2, 5, 10, 20, 40$). This setup allows for the testing of both "irrelevant" attributes (pure noise) and "informative" attributes (probabilistically related to the class) across eleven different selection measures categorized into four groups: information-based, statistical/probabilistic, algorithm-derived (RELIEF), and MDL-based.

The Linear Bias Trap

The study confirms that traditional measures, including Information Gain and the Gini-index, are highly prone to overfitting. These measures exhibit a linear increase in value as the number of attribute values increases, regardless of the attribute's actual utility. This means that in a dataset with many high-cardinality features, these heuristics will consistently "cheat" by selecting noise over signal.

Information Gain exhibits a linear bias, increasing as the number of attribute values grows, even for irrelevant data.

Similarly, the Gini-index shows a clear upward trend as the number of values ($V$) increases, demonstrating that statistical measures are not inherently immune to this cardinality bias.

The Gini-index similarly demonstrates a linear bias relative to the number of attribute values (V) and classes (C).

The Normalization Paradox and Statistical Failures

To combat linear bias, researchers previously suggested "normalized" measures like the Gain Ratio and Distance Measure. However, this study reveals a "normalization paradox": while these measures reduce noise-driven bias, they exhibit an exponential bias against informative multi-valued attributes. They essentially penalize high-quality attributes simply for having many values.

Furthermore, the paper critiques the use of statistical tests like $\chi^2$. While theoretically unbiased for random noise, they become practically useless for high-quality attributes. These statistics approach a value of 1.0 so rapidly that standard numerical precision cannot distinguish between a "good" attribute and a "great" one, making them ineffective for ranking top-tier candidates.

MDL and RELIEF: Robust Alternatives

The paper introduces a novel measure based on the Minimum Description Length (MDL) principle. By treating attribute selection as a data compression problem, the MDL measure balances the "cost" of an attribute's complexity (number of values) against its informational gain. This measure shows a slight negative bias as the number of values increases, making it a "conservative" estimator that only selects multi-valued attributes if they are significantly more informative than simpler alternatives.

Additionally, the measure derived from the RELIEF algorithm performed exceptionally well. Unlike myopic measures, RELIEF can detect interactions between attributes and maintains a more stable, logarithmic bias for irrelevant attributes compared to the linear bias of traditional metrics.

Conclusion

The investigation highlights that most traditional attribute selection measures are fundamentally biased toward high-cardinality data. While normalization attempts often over-correct, the MDL principle and the RELIEF algorithm offer more stable and reliable alternatives for building robust decision trees in complex, multi-valued domains. Future work will focus on refining the RELIEFF extension to better handle noise and multi-class problems.

Summary updated

BibTeX
@inproceedings{kononenko1995biases,
  author = {Igor Kononenko},
  title = {{On Biases in Estimating Multi-Valued Attributes}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1995},
}
Figure