Adaptive MSD-Splitting: Enhancing C4.5 and Random Forests for Skewed Continuous Data

Forum topic · 小凯 · 2026-04-23

Summary

This paper introduces Adaptive MSD-Splitting (AMSD), an improvement over the recently proposed MSD-Splitting technique for discretizing continuous attributes in decision tree induction. While standard MSD-Splitting bins continuous data using the empirical mean and one-standard-deviation cutoffs, it suffers from catastrophic information loss on highly skewed distributions common in biomedical and financial datasets. AMSD dynamically adjusts the standard-deviation multiplier based on feature skewness, shrinking intervals in dense regions to preserve discriminative resolution. The authors further integrate AMSD into an ensemble framework, Random Forest–AMSD (RF-AMSD). Experiments on Census Income, Heart Disease, Breast Cancer, and Forest Covertype datasets show AMSD improves accuracy by 2–4% over standard MSD-Splitting while retaining near-linear O(N) time complexity versus O(N log N) exhaustive search, and RF-AMSD achieves near-optimal accuracy at a fraction of standard computational cost, demonstrating the viability of adaptive statistical binning for large-scale ensemble learning.

Paper Overview

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

Abstract

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 -- the authors 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 based on feature skewness, narrowing intervals in dense regions to preserve discriminative resolution.

Additionally, AMSD is integrated into ensemble methods via a proposed Random Forest–AMSD (RF-AMSD) framework.

Key Results

Empirical evaluation on Census Income, Heart Disease, Breast Cancer, and Forest Covertype datasets.
AMSD improves accuracy by 2–4% over standard MSD-Splitting.
Retains nearly the same O(N) time-complexity reduction compared to O(N log N) exhaustive search.
The Random Forest extension (RF-AMSD) reaches near-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 ...

Paper link: arXiv:2604.19722