Adaptive MSD-Splitting (AMSD): Improving C4.5 and Random Forests on Skewed Data

Paper Overview

• Field: Machine Learning
• Author: Jake Lee
• Published: 2026-04-21
• arXiv: 2604.19722

Summary

The discretization of continuous numerical attributes remains a persistent computational bottleneck in decision tree induction, particularly as dataset dimensions scale. Building on the recently proposed MSD-Splitting technique — which bins continuous data using the empirical mean and standard deviation to dramatically improve the efficiency and accuracy of the C4.5 algorithm — this paper introduces Adaptive MSD-Splitting (AMSD).

While standard MSD-Splitting is highly effective for approximately symmetric distributions, its rigid adherence to fixed one-standard-deviation cutoffs can lead to catastrophic information loss on highly skewed data, a common artifact in real-world biomedical and financial datasets. AMSD addresses this by dynamically adjusting the standard deviation multiplier based on feature skewness, shrinking intervals in dense regions to preserve discriminative resolution.

The authors further integrate AMSD into ensemble methods, proposing a Random Forest–AMSD (RF-AMSD) framework.

Key Results

• Empirical evaluation on Census Income, Heart Disease, Breast Cancer, and Forest Covertype datasets shows AMSD improves accuracy by 2–4% over standard MSD-Splitting.
• AMSD maintains a nearly O(N) time complexity reduction compared to O(N log N) exhaustive search.
• The Random Forest extension achieves optimal accuracy at a fraction of standard computational cost, confirming the feasibility of adaptive statistical binning in large-scale ensemble learning architectures.

Original Abstract (excerpt)

> The discretization of continuous numerical attributes remains a persistent computational bottleneck in the induction of decision trees, particularly as dataset dimensions scale. Building upon the recently proposed MSD-Splitting technique -- which bins continuous data using the empirical mean and standard deviation to dramatically improve the efficiency and accuracy of the C4.5 algorithm -- we introduce Adaptive MSD-Splitting (AMSD). While standard MSD-Splitting is highly effective for approximately symmetric distributions, its rigid adherence to fixed one-standard-deviation cutoffs can lead to catastrophic information loss in highly skewed data, a common artifact in real-world biomedical and financial datasets. AMSD addresses this by dynamically adjusting the standard deviation multiplier ...

Full paper: <https://arxiv.org/abs/2604.19722>