Introduction
ChiMerge is a robust, automated algorithm designed to convert continuous numeric data into discrete categories by analyzing class distributions. By utilizing the $\chi^2$ (chi-square) statistic to merge similar adjacent intervals, it creates "class-aware" discretizations that preserve predictive information far better than traditional "blind" binning methods. This approach is particularly valuable for machine learning algorithms—such as early decision trees and rule-based systems—that require categorical input.
The Discretization Challenge
The primary challenge in discretization is that "blind" methods often destroy the very patterns a model needs to learn. For example, simple methods like equal-width (splitting the range into $N$ equal pieces) or equal-frequency (putting the same number of points in each bin) ignore the labels in the data. This can lead to poor classification performance; for instance, an equal-frequency bin might lump a $50,000 earner with a $500,000 earner simply because there are few data points in between, even if their behaviors (classes) are wildly different.
The ChiMerge Algorithm
Randy Kerber introduces ChiMerge as a "bottom-up" supervised discretization algorithm. Unlike top-down methods that split the data, ChiMerge starts with the most granular view possible and iteratively simplifies it through a merging process.
- Initialization: The algorithm sorts training examples by the attribute being discretized. Initially, every unique value is treated as its own interval.
- The $\chi^2$ Test: The algorithm examines every pair of adjacent intervals and calculates a $\chi^2$ statistic. This statistical test checks the "null hypothesis" that the class proportions in the two intervals are independent of the intervals themselves.
- Low $\chi^2$: Indicates that class distributions are similar, suggesting the intervals should be merged.
- High $\chi^2$: Indicates that class distributions are significantly different, suggesting the intervals should remain separate.
- Merging: In each iteration, the pair of intervals with the lowest $\chi^2$ value is merged.
- Termination: The process repeats until all remaining adjacent intervals have a $\chi^2$ value above a user-defined significance threshold (typically 0.90 or 0.95).
Key Insights and Performance
ChiMerge operationalizes the intuition that a high-quality discretization should have consistent class frequency within an interval but distinct frequencies between adjacent intervals.
Experimental Results
The paper evaluates ChiMerge using classic benchmarks: the Iris dataset, Glass fragment classification, and a large Thyroid disease dataset. As shown in the results below, ChiMerge consistently outperforms standard binning techniques and matches or exceeds the performance of more complex recursive top-down methods like D-2.
On the Thyroid dataset, ChiMerge achieved an error rate of 9.8%, significantly better than equal-width (18.3%) and equal-frequency (16.4%).
Advantages of Static Discretization
While some algorithms discretize "on the fly" during training, ChiMerge is a "static" pre-processor. This can lead to massive computational speedups—up to 50-fold—because the model does not have to re-calculate splits at every node of a decision tree. Furthermore, because it is a merging process driven by statistical significance, ChiMerge is inherently more robust to outliers than top-down splitting methods.
Limitations and Future Directions
Despite its strengths, ChiMerge is a supervised algorithm and requires labeled data, making it unsuitable for unsupervised clustering. Additionally, its local analysis (comparing only adjacent intervals) might miss broader patterns involving multiple intervals simultaneously.
To handle cases where the expected frequency of a class in an interval is very low (less than 1.0), Kerber suggests a heuristic fix—capping the denominator at 0.5—to prevent artificially inflated $\chi^2$ values. Future work may involve evolving the algorithm to create a generalization hierarchy, allowing models to adjust data granularity dynamically.
Summary updated