A study of the behavior of several methods for balancing machine learning training data

ABSTRACT

There are several aspects that might influence the performance achieved by existing learning systems. It has been reported that one of these aspects is related to class imbalance in which examples in training data belonging to one class heavily outnumber the examples in the other class. In this situation, which is found in real world data describing an infrequent but important event, the learning system may have difficulties to learn the concept related to the minority class. In this work we perform a broad experimental evaluation involving ten methods, three of them proposed by the authors, to deal with the class imbalance problem in thirteen UCI data sets. Our experiments provide evidence that class imbalance does not systematically hinder the performance of learning systems. In fact, the problem seems to be related to learning with too few minority class examples in the presence of other complicating factors, such as class overlapping. Two of our proposed methods deal with these conditions directly, allying a known over-sampling method with data cleaning methods in order to produce better-defined class clusters. Our comparative experiments show that, in general, over-sampling methods provide more accurate results than under-sampling methods considering the area under the ROC curve (AUC). This result seems to contradict results previously published in the literature. Two of our proposed methods, Smote + Tomek and Smote + ENN, presented very good results for data sets with a small number of positive examples. Moreover, Random over-sampling, a very simple over-sampling method, is very competitive to more complex over-sampling methods. Since the over-sampling methods provided very good performance results, we also measured the syntactic complexity of the decision trees induced from over-sampled data. Our results show that these trees are usually more complex then the ones induced from original data. Random over-sampling usually produced the smallest increase in the mean number of induced rules and Smote + ENN the smallest increase in the mean number of conditions per rule, when compared among the investigated over-sampling methods.

REFERENCES

• 1: Batista, G. E. A. P. A., Bazan, A. L., and Monard, M. C. Balancing Training Data for Automated Annotation of Keywords: a Case Study. In WOB (2003), pp. 35--43.
• 2: Eric Bauer , Ron Kohavi, An Empirical Comparison of Voting Classification Algorithms: Bagging, Boosting, and Variants, Machine Learning, v.36 n.1-2, p.105-139, July-August 1999 [doi>10.1023/A:1007515423169]
• 3: Blake, C., and Merz, C. UCI Repository of Machine Learning Databases, 1998. http://www.ics.uci.edu/~mlearn/MLRepository.html.
• 4: Chawla, N. V. C4.5 and Imbalanced Data Sets: Investigating the Effect of Sampling Method, Probabilistic Estimate, and Decision Tree Structure. In Workshop on Learning from Imbalanced Data Sets II (2003).
• 5: Chawla, N. V., Bowyer, K. W., Hall, L. O., and Kegelmeyer, W. P. SMOTE: Synthetic Minority Over-sampling Technique. JAIR 16 (2002), 321--357.
• 6: Paolo Ciaccia , Marco Patella , Pavel Zezula, M-tree: An Efficient Access Method for Similarity Search in Metric Spaces, Proceedings of the 23rd International Conference on Very Large Data Bases, p.426-435, August 25-29, 1997
• 7: Pedro Domingos, MetaCost: a general method for making classifiers cost-sensitive, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.155-164, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312220]
• 8: Drummond, C., and Holte, R. C. C4.5, Class Imbalance, and Cost Sensitivity: Why Under-sampling beats Over-sampling. In Workshop on Learning from Imbalanced Data Sets II (2003).
• 9: César Ferri , Peter A. Flach , José Hernández-Orallo, Learning Decision Trees Using the Area Under the ROC Curve, Proceedings of the Nineteenth International Conference on Machine Learning, p.139-146, July 08-12, 2002
• 10: Hand, D. J. Construction and Assessment of Classification Rules. John Wiley and Sons, 1997.
• 11: Hart, P. E. The Condensed Nearest Neighbor Rule. IEEE Transactions on Information Theory IT-14 (1968), 515--516.
• 12: Japkowicz, N. Class Imbalances: Are We Focusing on the Right Issue? In Workshop on Learning from Imbalanced Data Sets II (2003).
• 13: Japkowicz, N., and Stephen, S. The Class Imbalance Problem: A Systematic Study. IDA Journal 6, 5 (2002), 429--449.
• 14: Kubat, M., and Matwin, S. Addressing the Course of Imbalanced Training Sets: One-sided Selection. In ICML (1997), pp. 179--186.
• 15: Laurikkala, J. Improving Identification of Difficult Small Classes by Balancing Class Distribution. Tech. Rep. A-2001-2, University of Tampere, 2001.
• 16: Ling, C. X., and Li, C. Data Mining for Direct Mining: Problems and Solutions. In KDD (1998), pp. 73--79.
• 17: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 18: Prati, R. C., Batista, G. E. A. P. A., and Monard, M. C. Class Imbalances versus Class Overlapping: an Analysis of a Learning System Behavior. In MICAI (2004), pp. 312--321. LNAI 2972.
• 19: Provost, F. J., and Fawcett, T. Analysis and Visualization of Classifier Performance: Comparison under Imprecise Class and Cost-Distributions. In KDD (1997), pp. 43--48.
• 20: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 21: Craig Stanfill , David Waltz, Toward memory-based reasoning, Communications of the ACM, v.29 n.12, p.1213-1228, Dec. 1986 [doi>10.1145/7902.7906]
• 22: Tomek, I. Two Modifications of CNN. IEEE Transactions on Systems Man and Communications SMC-6 (1976), 769--772.
• 23: Weiss, G. M., and Provost, F. Learning When Training Data are Costly: The Effect of Class Distribution on Tree Induction. JAIR 19 (2003), 315--354.
• 24: Wilson, D. L. Asymptotic Properties of Nearest Neighbor Rules Using Edited Data. IEEE Transactions on Systems, Man, and Communications 2, 3 (1972), 408--421.
• 25: D. Randall Wilson , Tony R. Martinez, Reduction Techniques for Instance-BasedLearning Algorithms, Machine Learning, v.38 n.3, p.257-286, March 2000 [doi>10.1023/A:1007626913721]
• 26: Bianca Zadrozny , Charles Elkan, Learning and making decisions when costs and probabilities are both unknown, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.204-213, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502540]