Learning When Training Data are Costly: The Effect of Class Distribution on Tree Induction

Abstract

For large, real-world inductive learning problems, the number of training examples often must be limited due to the costs associated with procuring, preparing, and storing the training examples and/or the computational costs associated with learning from them. In such circumstances, one question of practical importance is: if only n training examples can be selected, in what proportion should the classes be represented? In this article we help to answer this question by analyzing, for a fixed training-set size, the relationship between the class distribution of the training data and the performance of classification trees induced from these data. We study twenty-six data sets and, for each, determine the best class distribution for learning. The naturally occurring class distribution is shown to generally perform well when classifier performance is evaluated using undifferentiated error rate (0/1 loss). However, when the area under the ROC curve is used to evaluate classifier performance, a balanced distribution is shown to perform well. Since neither of these choices for class distribution always generates the best-performing classifier, we introduce a budget-sensitive progressive sampling algorithm for selecting training examples based on the class associated with each example. An empirical analysis of this algorithm shows that the class distribution of the resulting training set yields classifiers with good (nearly-optimal) classification performance.

References in corpus (2)

• SMOTE: Synthetic Minority Over-sampling Technique
• Robust Classification for Imprecise Environments

Cited by in corpus (24)

• Fame for sale: efficient detection of fake Twitter followers
• Network-Based Marketing: Identifying Likely Adopters via Consumer Networks
• Smart Anomaly Detection in Sensor Systems: A Multi-Perspective Review
• Automatic Detection of Blue-White Veil and Related Structures in Dermoscopy Images
• A Survey of Predictive Modelling under Imbalanced Distributions
• Searches for the BSM scenarios at the LHC using decision tree based machine learning algorithms: A comparative study and review of Random Forest, Adaboost, XGboost and LightGBM frameworks
• A machine learning approach for identification and classification of symbiotic stars using 2MASS and WISE
• TESSERACT: Eliminating Experimental Bias in Malware Classification across Space and Time
• Machine-assisted discovery of relationships in astronomy
• Boosted decision trees in the era of new physics: a smuon analysis case study
• Learning Curves for Decision Making in Supervised Machine Learning: A Survey
• On the efficacy of old features for the detection of new bots
• Classification of field dwarfs and giants in RAVE and its use in stellar stream detection
• Double-Base Asymmetric AdaBoost
• Morse Code Datasets for Machine Learning
• Modeling of learning curves with applications to pos tagging
• CGMOS: Certainty Guided Minority OverSampling
• Reviving Threshold-Moving: a Simple Plug-in Bagging Ensemble for Binary and Multiclass Imbalanced Data
• Natural vs Balanced Distribution in Deep Learning on Whole Slide Images for Cancer Detection
• Who wins the Miss Contest for Imputation Methods? Our Vote for Miss BooPF
• Superensemble Classifier for Improving Predictions in Imbalanced Datasets
• Interpreting BERT architecture predictions for peptide presentation by MHC class I proteins
• Synthetic Embedding-based Data Generation Methods for Student Performance
• Probabilistic Diagnostic Tests for Degradation Problems in Supervised Learning