Branching on Attribute Values in Decision Tree Generation

Usama M. FayyadAAAI 1994

Introduction

Standard decision tree induction algorithms, such as ID3 and its successors like C4.5, often suffer from a phenomenon known as "over-partitioning." When these algorithms encounter a categorical attribute, they typically create a separate branch for every unique value present in the training data. While straightforward, this approach leads to several significant drawbacks: reduced data density in lower nodes, the inclusion of irrelevant attribute values that do not aid classification, and a lack of robustness when encountering unseen values during testing.

To address these issues, researchers developed the GID3 algorithm, which introduced the concept of grouping less informative values into a "DEFAULT" branch. However, GID3 required a manually tuned "tolerance level" (TL). This paper introduces GID3*, a parameter-free evolution that automates branching decisions through a novel metric called the "Tear" measure.

The GID3* Algorithm: Attribute Phantomization

The core innovation of GID3 is attribute phantomization. Instead of branching on all $r$ values of an attribute, the algorithm identifies a subset of $s$ "important" values ($s \le r$). These important values receive their own branches, while all remaining values are lumped into a single DEFAULT* branch.

Comparison of decision tree structures generated by ID3 and GID3* algorithms from a sample dataset.

Selection Logic and the "Tear" Measure

To determine which values merit an individual branch, GID3* employs a two-step selection process:

  1. Entropy Minimization: It first identifies the attribute-value pair that minimizes class entropy.
  2. The Tear Measure: This novel metric evaluates how effectively a specific attribute value "tears" classes apart by calculating the normalized vector difference between class distributions.

If an attribute value's Tear score is significantly lower than that of the "best" value (determined by entropy), it is deemed irrelevant for individual branching and relegated to the DEFAULT branch. This process is further refined by a "band-pass filter" weighting factor ($\beta = 25$) to prevent bias from extremely frequent or rare values.

Experimental Evaluation

The authors evaluated GID3* against ID3, C4 (referred to as ID3-IV), and the original GID3 across a variety of domains, including synthetic Reactive Ion Etching (RIE) data, 100 randomly generated synthetic domains, and real-world UCI benchmarks like SOYBEAN and HARR90.

Key Results: Accuracy and Compactness

The results consistently demonstrated that GID3 produces smaller, more accurate trees. In the RIE domain, GID3 achieved an error rate of approximately 2%, a stark contrast to the 15-16% error rates observed with ID3 and C4. Furthermore, GID3* maintained this performance without the need for manual parameter tuning, often outperforming the best-case scenarios of the original GID3.

Average error rate ratios and standard deviations across various algorithms, with GID3* as the baseline (1.0).

As shown in the performance metrics, GID3* serves as a robust baseline, consistently yielding lower average error rates and fewer leaves than standard ID3 variants across diverse datasets.

Conclusion and Future Work

The "DEFAULT" branch in GID3* serves a dual purpose: it keeps the tree compact by filtering out noise and provides a built-in mechanism for handling previously unseen attribute values. While the algorithm shows clear empirical advantages, particularly in discrete-valued domains, future work remains to explore the interaction between attribute phantomization and continuous-value discretization. Additionally, deeper theoretical analysis of the Tear measure could provide a formal explanation for the algorithm's consistent superiority over manually tuned predecessors.

Summary updated

BibTeX
@inproceedings{fayyad1994branching,
  author = {Usama M. Fayyad},
  title = {{Branching on Attribute Values in Decision Tree Generation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure