Abstract
Classification algorithms face difficulties when one or more classes have limited training data. We are particularly interested in classification trees, due to their interpretability and flexibility. When data are limited in one or more of the classes, the estimated decision boundaries are often irregularly shaped due to the limited sample size, leading to poor generalization error. We propose a novel approach that penalizes the Surface-to-Volume Ratio (SVR) of the decision set, obtaining a new class of SVR-Tree algorithms. We develop a simple and computationally efficient implementation while proving estimation consistency for SVR-Tree and rate of convergence for an idealized empirical risk minimizer of SVR-Tree. SVR-Tree is compared with multiple algorithms that are designed to deal with imbalance through real data applications.
The Challenge of Imbalanced Data
In domains such as fraud detection, medical diagnosis, and rare event prediction, datasets are often characterized by a severe class imbalance. Standard classification trees, like the Classification and Regression Tree (CART) algorithm, are frequently employed in these settings due to their interpretability. However, they struggle to generalize when the minority class is sparse.
In such cases, standard tree algorithms tend to "chase" individual minority points, resulting in decision boundaries that are highly fragmented, "jagged," or spindly. These irregularly shaped regions often represent noise rather than the underlying data distribution, leading to high variance and poor predictive performance on unseen data. While heuristic sampling methods like SMOTE (Synthetic Minority Over-sampling Technique) are common, they often lack a principled geometric foundation and can struggle as the dimensionality of the feature space increases.
SVR-Tree: Regularizing by Shape
To address these limitations, this research introduces SVR-Tree, a novel algorithm that incorporates a geometric penalty into the tree-building process. Instead of merely penalizing the number of nodes (as in traditional pruning), SVR-Tree penalizes the Surface-to-Volume Ratio (SVR) of the decision regions for the minority class.
Geometric Intuition
The core idea is that "regularly shaped" regions—those with a low surface area relative to their volume (like a square or a cube)—are more likely to represent true patterns than thin, elongated, or fragmented regions. By penalizing high SVR, the algorithm discourages the model from creating the complex, spindly boundaries that characterize overfitting in imbalanced settings.
Algorithmic Implementation
The SVR-Tree objective function minimizes a weighted sum of signed tree impurity (a proxy for classification error) and the SVR of the minority class decision set. The authors implemented this using a greedy, breadth-first search algorithm. At each potential split, the algorithm evaluates the trade-off between impurity reduction and the resulting geometric regularity of the decision regions. This approach maintains a computational complexity of $O(dn \log n)$, comparable to standard tree algorithms.
Experimental Evaluation
The researchers evaluated SVR-Tree across 12 diverse datasets from the UCI and KEEL repositories, covering medical, biological, and image data. The degree of imbalance varied significantly, with minority class proportions ranging from 3.4% to 34.9%.
Key Results
SVR-Tree was compared against several benchmarks, including CART with oversampling, SMOTE, Borderline-SMOTE, ADASYN, and Hellinger Distance Decision Trees (HDDT).
- Predictive Accuracy: SVR-Tree consistently outperformed competitors in terms of True Positive Rate (TPR) and G-mean, a metric specifically designed to balance performance across majority and minority classes.
- Robustness to Redundancy: A variant called "SVR-Select" incorporates a feature selection threshold. In experiments with added redundant features, SVR-Select maintained high performance while other methods experienced significant degradation.
- Case Study (Segment Dataset): On the "Segment" dataset, SVR-Select achieved a G-mean of 0.9863, notably higher than SMOTE (0.9820) and the baseline CART (0.9817).
Conclusion
SVR-Tree represents a significant advancement in classification for imbalanced data by shifting the focus from sampling heuristics to the geometric regularity of decision boundaries. By penalizing the Surface-to-Volume Ratio, the algorithm produces models that are both interpretable and robust. Beyond its empirical success, the method is supported by theoretical proofs of estimation consistency and convergence rates, providing a rigorous statistical foundation for its application in high-stakes, data-sparse environments.
Summary updated