Minimum Splits Based Discretization for Continuous Features

IJCAI 1997

TL;DR

This paper introduces a novel approach to discretizing continuous features for decision tree learning, moving beyond traditional binary splits to explore multi-way splits. Their method, "minimum splits," efficiently finds optimal multi-way splits by minimizing the number of intervals while respecting an impurity threshold, leading to shallower, more interpretable decision trees with comparable or better performance than existing methods.

What Problem Does This Paper Address?

Decision tree algorithms often struggle with continuous features. While some methods discretize these features into intervals, the dominant approach has been binary splitting (dividing into two intervals). This can lead to deep, complex trees where a single continuous feature might be split multiple times across different nodes, obscuring its true structure. The paper argues that this binary-splitting bias can cause algorithms to miss simpler, more effective multi-way splits that could classify more examples at higher levels of the tree. The challenge is that searching for optimal multi-way splits is computationally much more complex than for binary splits.

Methods

The authors propose a two-step approach to find optimal multi-way splits:

  1. Minimum Splits: They define "minimum splits" as splits that minimize the number of intervals for a given impurity threshold. This is a necessary condition for a good split. They develop a dynamic programming algorithm to find these minimum splits efficiently, running in quadratic time with respect to the number of initial bins (unique values). They also offer a faster, linear-time greedy approximation algorithm.
  2. Optimal Split Selection: From the set of minimum splits (called "candidate splits"), they select the "best" split by minimizing the product of the number of intervals and the impurity (e.g., entropy). This product is interpreted as minimizing the total entropy across all intervals, not just the average.

Datasets

The paper evaluates their methods on 15 datasets from the UCI repository, all of which contain continuous features. They compare their proposed "Dynamic" (using the DP minimum splits) and "Greedy" algorithms against the then-current release of C4.5 (Release 8), which uses an MDL-inspired penalty for binary splits of continuous features.

Key Insights and Ideas

  • Multi-way splits can be superior: The paper provides a strong argument that multi-way splits, when structured well, can lead to more intuitive and efficient decision trees compared to repeatedly applying binary splits.
  • "Minimum splits" as a foundation: Defining minimum splits as a prerequisite for good splits simplifies the search space and provides a principled way to explore multi-way partitioning.
  • Product of intervals and impurity: Using the product $I \times \text{impurity}$ as a selection criterion for the best split is a novel way to balance the number of branches with the purity of the resulting nodes, aiming for overall lower entropy.
  • Testing depth as a key metric: The authors introduce "testing depth" as a measure of tree simplicity, which captures how many tests are needed on average to classify an example. They find their multi-way splits significantly reduce this metric compared to C4.5.

Key Results

  • Improved Tree Structure: Decision trees built using their multi-way splitting methods (Dynamic and Greedy) are generally shallower and have more "parallel" branches, making them easier to understand than the "nested" structures often produced by C4.5.
  • Reduced Testing Depth: Both Dynamic and Greedy algorithms consistently produced decision trees with significantly lower testing depths across all 15 datasets compared to C4.5(R8).
  • Competitive Performance:
    • The "Dynamic" algorithm (using the full DP approach) often outperformed "Greedy" in terms of tree size, error rate, and testing depth.
  • "Dynamic" and "Greedy" showed advantages over C4.5(R8) in tree size (Dynamic won 12/15 datasets) and error rate (Dynamic won 8/15 datasets).
  • On testing depth, both Dynamic and Greedy consistently outperformed C4.5(R8).
  • Running Time: The Dynamic programming approach was the slowest, while the Greedy and C4.5(R8) were comparable. The hybrid approach (not fully evaluated but discussed) is suggested as a way to balance speed and quality.

Limitations and Future Work

  • Computational Cost: The dynamic programming algorithm for finding minimum splits is quadratic in the number of initial bins, which can be expensive for datasets with many unique continuous values. The greedy algorithm offers a faster approximation.
  • Hybrid Approach: The paper suggests a hybrid approach (greedy followed by DP) as a promising direction to achieve both speed and quality, but it was not fully evaluated in this study.
  • Over-splitting Control: While their method aims to control over-splitting through minimum splits and the impurity product, the paper notes that ensuring a minimal number of examples per interval might still be necessary to avoid splits on very small subsets of data.
  • Future Work: The authors believe that multi-way splitting with careful control of over-splitting is a powerful technique for handling continuous values and warrants further exploration in various application domains.

Summary updated

BibTeX
@inproceedings{1997minimum,
  title = {{Minimum Splits Based Discretization for Continuous Features}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1997},
}
Figure