The Attribute Selection Problem in Decision Tree Generation

Usama M. Fayyad, Keki B. IraniAAAI 1992

Abstract

Traditional decision tree induction relies heavily on impurity-based splitting criteria like Information Gain. This paper argues that such measures are fundamentally flawed for multi-class separation, often leading to over-fragmented and unnecessarily complex trees. We introduce Class SEParation (C-SEP) measures, specifically the Orthogonality (ORT) metric, which prioritizes maximizing the distance between class distributions. Our proposed algorithm, O-BTree, utilizes binary splits and the ORT measure to produce trees that are significantly smaller and more accurate than those generated by standard impurity-based methods.

Introduction

Top-down induction of decision trees (TDIDT) is a cornerstone of machine learning. The efficiency and accuracy of these trees depend almost entirely on the attribute selection measure used at each node. For decades, metrics like Entropy and the Gini Index have been the standard. However, these measures focus on node "purity" rather than explicit class separation, which can lead to suboptimal tree structures.

The Limitations of Impurity Measures

Impurity measures aim to create subsets where a single class dominates. While intuitive, this approach suffers from several drawbacks. First, it often causes "over-fragmentation," where a single class is split across multiple branches, increasing the tree's "bushiness" without improving predictive power. Second, these measures are often insensitive to the specific classes being moved; they only care about the resulting distribution's entropy. Finally, in datasets with a dominant majority class, the entropy measure becomes "depressed," making it difficult to distinguish between the utility of different potential splits.

Figure 1: Comparison of partitions induced by different attributes, illustrating how traditional gain measures may fail to capture optimal class separation.

As shown in Figure 1, an attribute with lower Information Gain (0.43) may actually provide a much cleaner separation of classes than one with higher Gain (0.51), highlighting the "Information Paradox" inherent in traditional metrics.

The C-SEP Approach and ORT

To address these issues, the authors propose Class SEParation (C-SEP) measures. Unlike impurity metrics, C-SEP focuses on the distance between class distributions in the resulting subsets. The primary metric introduced is Orthogonality (ORT). By treating class distributions as vectors in a multi-dimensional space, ORT measures the angle between them. A 90-degree angle (orthogonality) indicates perfect separation, while parallel vectors suggest the split failed to distinguish between classes.

The O-BTree Algorithm

The ORT measure is implemented in the O-BTree algorithm. O-BTree departs from the multi-way branching of algorithms like ID3, instead favoring binary splits. This "Binary Tree Hypothesis" posits that branching on the single best attribute-value pair leads to more efficient and interpretable trees. By avoiding the noise of forced multi-way branches for every attribute value, O-BTree maintains a focus on the most discriminative features.

Experimental Results

The performance of O-BTree was evaluated against standard algorithms (ID3, GID3*, etc.) using both synthetic (RIE) and real-world datasets (AUTO, SOYBEAN, MUSHROOM). In the RIE domain, O-BTree consistently identified the optimal tree structure with the minimum number of leaves.

Figure 5: Relative ratios of error rates across various datasets, showing O-BTree consistently achieving lower error rates compared to traditional methods.

As shown in Figure 5, O-BTree consistently achieved lower error rates across all tested real-world datasets. Notably, on the SOYBEAN dataset, the error rate was nearly half that of ID3-BIN. Furthermore, the trees produced were significantly smaller, enhancing both their generalizability and interpretability.

Conclusion

By shifting the focus from node purity to class separation, the ORT measure and the O-BTree algorithm provide a more robust framework for decision tree induction. This approach effectively mitigates the over-fragmentation common in entropy-based methods, resulting in trees that are both more accurate and more compact, particularly in complex multi-class domains.

Summary updated

BibTeX
@inproceedings{fayyad1992attribute,
  author = {Usama M. Fayyad and Keki B. Irani},
  title = {{The Attribute Selection Problem in Decision Tree Generation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1992},
}
Figure