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

By Gary M. Weiss, Foster J. Provost. Journal of Artificial Intelligence Research, 2003

1,022 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence

View Paper: https://www.semanticscholar.org/paper/a3dae3c8ac14be25d287f27e5383cc7fb7907e51

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

An experimental comparison of classification algorithms for imbalanced credit scoring data sets (2012, background): “In Weiss and Provost (2003) it was found that the naturally occurring class distributions in the 25 data sets looked at, often did not produce the best-performing classifiers.”
Analysis of preprocessing vs. cost-sensitive learning for imbalanced classification. Open problems on intrinsic data characteristics (2012, background): “The aim of this paper is to develop a thorough experimental study to analyze the possible differences between preprocessing techniques and costsensitive learning for addressing classification with imbalanced data.”
Exploring the effects of quantity and location of pseudo-absences and sampling biases on the performance of distribution models with limited point occurrence data (2011, background): “Minority-class predictions have a higher error rate than majority-class predictions (if there is no evidence favouring one classification over another, modelling methods tend to predict the majority class; see Weiss & Provost 2003).”
RUSBoost: A Hybrid Approach to Alleviating Class Imbalance (2010, background): “often considered to be near optimal [10].”
TESSERACT: Eliminating Experimental Bias in Malware Classification across Space and Time (2018, methodology): “Our tuning algorithm is inspired by one proposed by Weiss and Provost [55]; they propose a progressive sampling of training objects to collect a dataset that improves AUROC performance of the minority class in an imbalanced dataset.”
KBA: kernel boundary alignment considering imbalanced data distribution (2005, background): “Oversampling [7], [26] is the opposite of the under-sampling approach.”
Editorial: special issue on learning from imbalanced data sets (2004, background): “Conversely, in certain cases, the data abounds and it is for the scientist to decide which examples to select and in what quantity [56].”
Precision-Recall versus Accuracy and the Role of Large Data Sets (2019, background): “A crucial clue to the nature of the problem was provided by a substantial empirical study by Weiss and Provost (2003): In a study of a ﬁxed decision tree learning algorithm on twenty-six data sets, they determined that indeed, the use of the natural class distribution provided close to the optimal…”
Does cost-sensitive learning beat sampling for classifying rare classes? (2005, methodology): “[17] Weiss, G., and Provost, F. Learning when training data are costly: the effect of class distribution on tree induction.”
Classification with class imbalance problem: A review (2015, background): “Although there are many efforts in managing class imbalance problems through sampling, a study in [35] argued that there is no formal standard to define the most suitable class distribution, and experiments conducted by [20] discovered that often, a 50:50 imbalance ratio between minority class and m”
Outlier Analysis (2013, background): “Some examples of cost-sensitive decision trees are discussed in [450, 463].”
A theoretical distribution analysis of synthetic minority oversampling technique (SMOTE) for imbalanced learning (2023, neutral): “Albisua et al. (2013) extend the analysis developed by Weiss and Provost (2003) by conducting experiments on several sampling methods and different classifiers.”
Cell phone-based biometric identification (2010, methodology): “Because the positive class is so rare (on average it contains 1/36 of the data), most classification methods will tend to generate classifiers that do not perform well at predicting this (rare) class [15].”
Churn in Social Networks (2010, result): “Similar to [68], one observation is that an equal distribution between both classes is not fruitful, but that otherwise there is no optimal choice for all cases.”
Mining with rarity: a unifying framework (2004, methodology): “The author would therefore like to thank Haym Hirsh and Foster Provost for their collaboration on this earlier research.”