Boosting for Learning Multiple Classes with Imbalanced Class Distribution
ProceedingsPublished 1 December 2006
Yanmin Sun, Mohamed S. Kamel, Yang Wang
Citations302
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A cost-sensitive boosting algorithm is developed to improve the classification performance of imbalanced data involving multiple classes and applies Genetic Algorithm to search the optimum cost setup of each class.
Abstract
Classification of data with imbalanced class distribution has posed a significant drawback of the performance attainable by most standard classifier learning algorithms, which assume a relatively balanced class distribution and equal misclassification costs. This learning difficulty attracts a lot of research interests. Most efforts concentrate on bi-class problems. However, bi-class is not the only scenario where the class imbalance problem prevails. Reported solutions for bi-class applications are not applicable to multi-class problems. In this paper, we develop a cost-sensitive boosting algorithm to improve the classification performance of imbalanced data involving multiple classes. One barrier of applying the cost-sensitive boosting algorithm to the imbalanced data is that the cost matrix is often unavailable for a problem domain. To solve this problem, we apply Genetic Algorithm to search the optimum cost setup of each class. Empirical tests show that the proposed cost-sensitive boosting algorithm improves the classification performances of imbalanced data sets significantly.
Keywords
Computer ScienceEngineeringBusiness, Management and Accounting
The MIT Press eBooksAdaptation in Natural and Artificial Systems
35,568 Citations1992John H. Holland
Initially applying his concepts to simply defined artificial systems with limited numbers of parameters, Holland goes on to explore their use in the study of a wide range of complex, naturally occuring processes, concentrating on systems having multiple factors that interact in nonlinear ways.
C4.5: Programs for Machine Learning
23,665 Citations1992J. R. Quinlan
A complete guide to the C4.5 system as implemented in C for the UNIX environment, which starts from simple core learning methods and shows how they can be elaborated and extended to deal with typical problems such as missing data and over hitting.
Journal of Computer and System SciencesA Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting
20,320 Citations1997Yoav Freund, Robert E. Schapire
Pattern RecognitionThe use of the area under the ROC curve in the evaluation of machine learning algorithms
7,233 Citations1997Andrew P. Bradley
AUC exhibits a number of desirable properties when compared to overall accuracy: increased sensitivity in Analysis of Variance (ANOVA) tests; a standard error that decreased as both AUC and the number of test samples increased; decision threshold independent; and it is invariant to a priori class probabilities.
The Annals of StatisticsAdditive logistic regression: a statistical view of boosting (With discussion and a rejoinder by the authors)
6,842 Citations2000Jerome H. Friedman, Trevor Hastie +1 more
This work shows that this seemingly mysterious phenomenon of boosting can be understood in terms of well-known statistical principles, namely additive modeling and maximum likelihood, and develops more direct approximations and shows that they exhibit nearly identical results to boosting.
Intelligent Data AnalysisThe class imbalance problem: A systematic study1
3,298 Citations2002Nathalie Japkowicz, Shaju Stephen
The assumption that the class imbalance problem does not only affect decision tree systems but also affects other classification systems such as Neural Networks and Support Vector Machines is investigated.
Improved boosting algorithms using confidence-rated predictions
2,568 Citations1998Robert E. Schapire, Yoram Singer
The Annals of StatisticsBoosting the margin: a new explanation for the effectiveness of voting methods
2,313 Citations1998Peter L. Bartlett, Yoav Freund +2 more
It is shown that techniques used in the analysis of Vapnik's support vector classifiers and of neural networks with small weights can be applied to voting methods to relate the margin distribution to the test error.
ACM SIGKDD Explorations NewsletterEditorial
2,035 Citations2004Nitesh V. Chawla, Nathalie Japkowicz +1 more
Machine LearningImproved Boosting Algorithms Using Confidence-rated Predictions
1,959 Citations1999Robert E. Schapire, Yoram Singer
Several improvements to Freund and Schapire's AdaBoost boosting algorithm are described, particularly in a setting in which hypotheses may assign confidences to each of their predictions.
The foundations of cost-sensitive learning
1,835 Citations2001Charles Elkan
It is argued that changing the balance of negative and positive training examples has little effect on the classifiers produced by standard Bayesian and decision tree learning methods, and the recommended way of applying one of these methods is to learn a classifier from the training set and then to compute optimal decisions explicitly using the probability estimates given by the classifier.
ACM SIGKDD Explorations NewsletterMining with rarity
1,386 Citations2004Gary M. Weiss
It is demonstrated that rare classes and rare cases are very similar phenomena---both forms of rarity are shown to cause similar problems during data mining and benefit from the same remediation methods.
Machine LearningMachine Learning for the Detection of Oil Spills in Satellite Radar Images
1,253 Citations1998Miroslav Kubát, Robert C. Holte +1 more
This case study relates issues as problem formulation, selection of evaluation measures, and data preparation to properties of the oil spill application, such as its imbalanced class distribution, that are shown to be common to many applications.
Journal of Artificial Intelligence ResearchLearning When Training Data are Costly: The Effect of Class Distribution on Tree Induction
928 Citations2003Gary M. Weiss, Foster Provost
A "budget-sensitive" progressive sampling algorithm is introduced for selecting training examples based on the class associated with each example and it is shown that the class distribution of the resulting training set yields classifiers with good (nearly-optimal) classification performance.
Analysis and visualization of classifier performance: comparison under imprecise class and cost distributions
723 Citations1997Foster Provost, Tom Fawcett
The ROC convex hull method combines techniques from ROC analysis, decision analysis and computational geometry, and adapts them to the particulars of analyzing learned classifiers to present a method for the comparison of classifier performance that is robust to imprecise class distributions and misclassification costs.
IEEE Transactions on Knowledge and Data EngineeringAn instance-weighting method to induce cost-sensitive trees
491 Citations2002Kai Ming Ting
The algorithm incorporating the instance-weighting method is found to be better than the original algorithm in in of total misclassification costs, the number of high cost errors, and tree size two-class data sets.
Elsevier eBooksReducing Misclassification Costs
343 Citations1994Michael J. Pazzani, Christopher J. Merz +4 more
Algorithms for learning classification procedures that attempt to minimize the cost of misclassifying examples are explored and the Reduced Cost Ordering algorithm, a new method for creating a decision list, is described and compared to a variety of inductive learning approaches.
Evaluating boosting algorithms to classify rare classes: comparison and improvements
271 Citations2002Manjunath V. Joshi, Vipin Kumar +1 more
The authors evaluate three existing categories of boosting algorithms from the single viewpoint of how they update the example weights in each iteration, and propose enhanced algorithms in two of the categories, and justify their choice of weight updating parameters theoretically.
A Comparative Study of Cost-Sensitive Boosting Algorithms
266 Citations2000Kai Ming Ting
Machine LearningSupervised Versus Unsupervised Binary-Learning by Feedforward Neural Networks
148 Citations2001Nathalie Japkowicz
This paper describes a connectionist unsupervised approach to binary classification and compares its performance to that of its supervised counterpart, MLP, and concludes that autoassociator is more efficient than MLP in multi-modal domains, and it is more accurate thanMLP inMulti- modal domains for which the negative class creates a particularly strong need for specialization or the positive class creating a particularly weak needs for specialization.
Lecture notes in computer scienceParameter Inference of Cost-Sensitive Boosting Algorithms
51 Citations2005Yanmin Sun, Andrew K. C. Wong +1 more
Three versions of cost-sensitive AdaBoost algorithms where the parameters for sample weight updating are induced are proposed and their identification abilities on the small classes are tested on four “real world” medical data sets taken from UCI Machine Learning Database based on F-measure.