A Chi-MIC Based Adaptive Multi-Branch Decision Tree

Jiahao Ye, Jingjing Yang, Jiang Yu, Siqiao Tan, Feng Luo, Zheming Yuan, Yuan ChenIEEE Access 2021 · OpenReview

Abstract

The Chi-MIC Based Adaptive Multi-Branch Decision Tree (CMDT) is a novel classification algorithm designed to address the inherent limitations of traditional decision trees, such as rigid binary splitting and poor performance on imbalanced datasets. By integrating the Maximal Information Coefficient (MIC) for discretization and local chi-square tests for adaptive pruning, CMDT achieves superior predictive accuracy while maintaining the interpretability of tree-based models. Experimental results on 11 UCI benchmark datasets demonstrate that CMDT significantly outperforms standard classifiers like CART and CHAID, particularly in real-world scenarios characterized by class imbalance.

Introduction

Decision trees (DTs) remain a cornerstone of data science due to their inherent interpretability. However, traditional models like ID3 or C4.5 often struggle with two major issues: rigid splitting mechanisms that fail to capture complex non-linear relationships in numerical data, and a bias toward majority classes in imbalanced datasets. This paper introduces CMDT to bridge the performance gap between interpretable trees and complex "black-box" models without sacrificing human-readable logic.

Methodology

The CMDT algorithm introduces three primary innovations to enhance tree construction and pruning:

  • Chi-MIC Discretization: For numerical attributes, the algorithm utilizes an improved version of the Maximal Information Coefficient (Chi-MIC). Instead of simple binary cuts, it employs unequal interval optimization to identify the most statistically significant splitting points, allowing the tree to capture non-linear associations.
  • Local Chi-Square Pruning: To prevent overfitting, CMDT implements a backtracking method using local chi-square tests. This ensures that every split is statistically justified; if a split does not provide a significant improvement in p-value, the branches are simplified or merged.
Adaptive multi-branch merging process using chi-square tests.
  • Weighted Decision-Making: To handle class imbalance, the algorithm uses a "corrective sample size" based on prior probabilities. This re-weights the decision-making table at the leaf nodes to ensure minority classes are not overwhelmed by the majority.

Experimental Setup

The algorithm was evaluated using 11 benchmark datasets from the UCI Machine Learning Repository, covering fields from life sciences to social sciences. These included seven balanced sets (e.g., Wine, Forest Types, Vehicle) and four imbalanced sets (e.g., Cardiotocography, Page Blocks). The datasets varied in scale from 134 to over 10,000 samples to ensure robust testing across different data shapes.

Key Results

CMDT was compared against 12 other classifiers, including CART, CHAID, SVM, and Naive Bayes. The results highlighted the model's robustness and superior accuracy:

  • Balanced Data: CMDT achieved the highest average Weighted Accuracy (WA) of 86.74%, significantly outperforming CART (78.55%).
  • Imbalanced Data: The performance gap widened in imbalanced scenarios, with CMDT reaching an average WA of 77.14%, while the second-best model (KNNC) trailed at 68.85% and CART fell to 62.42%.
Performance comparison of CMDT against other classifiers across balanced and imbalanced datasets.

Discussion and Conclusion

The transition from simple heuristics like Gini impurity to statistical rigor via chi-square tests allows CMDT to naturally curb overfitting while capturing more complex data structures. While the computational intensity of the MIC algorithm is a current limitation for very large datasets, the authors suggest that future work on parallel algorithms and faster MIC approximations will make CMDT a highly viable tool for large-scale, interpretable machine learning.

Source: J. Ye et al., "A Chi-MIC Based Adaptive Multi-Branch Decision Tree," in IEEE Access, vol. 9, pp. 78962-78972, 2021.

Summary updated

BibTeX
@inproceedings{ye2021chi,
  author = {Jiahao Ye and Jingjing Yang and Jiang Yu and Siqiao Tan and Feng Luo and Zheming Yuan and Yuan Chen},
  title = {{A Chi-MIC Based Adaptive Multi-Branch Decision Tree}},
  booktitle = {IEEE Access},
  year = {2021},
  url = {https://openreview.net/forum?id=Sgj1yaNeiLq},
}
Figure