Learning on the border: active learning in imbalanced data classification

ABSTRACT

This paper is concerned with the class imbalance problem which has been known to hinder the learning performance of classification algorithms. The problem occurs when there are significantly less number of observations of the target concept. Various real-world classification tasks, such as medical diagnosis, text categorization and fraud detection suffer from this phenomenon. The standard machine learning algorithms yield better prediction performance with balanced datasets. In this paper, we demonstrate that active learning is capable of solving the class imbalance problem by providing the learner more balanced classes. We also propose an efficient way of selecting informative instances from a smaller pool of samples for active learning which does not necessitate a search through the entire dataset. The proposed method yields an efficient querying system and allows active learning to be applied to very large datasets. Our experimental results show that with an early stopping criteria, active learning achieves a fast solution with competitive prediction performance in imbalanced data classification.

REFERENCES

• 1: N. Abe. Invited talk: Sampling approaches to learning from imbalanced datasets: Active learning, cost sensitive learning and beyond. Proc. of ICML Workshop: Learning from Imbalanced Data Sets, 2003.
• 2: R. Akbani, S. Kwek, and N. Japkowicz. Applying support vector machines to imbalanced datasets. Proc. of European Conference on Machine Learning, pages 39--50, 2004.
• 3: Antoine Bordes , Seyda Ertekin , Jason Weston , Léon Bottou, Fast Kernel Classifiers with Online and Active Learning, The Journal of Machine Learning Research, 6, p.1579-1619, 12/1/2005
• 4: P. K. Chan and S. J. Stolfo. Toward scalable learning with non-uniform class and cost distributions: A case study in credit card fraud detection. In Proc. of ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, 1998.
• 5: N. V. Chawla, K. W. Bowyer., L. O. Hall, and W. P. Kegelmeyer. Smote: Synthetic minority over-sampling technique. Journal of Artificial Intelligence Research (JAIR), 16:321--357, 2002.
• 6: 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]
• 7: Susan Dumais , John Platt , David Heckerman , Mehran Sahami, Inductive learning algorithms and representations for text categorization, Proceedings of the seventh international conference on Information and knowledge management, p.148-155, November 02-07, 1998, Bethesda, Maryland, United States [doi>10.1145/288627.288651]
• 8: J. W. Grzymala-Busse, Z. Zheng, L. K. Goodwin, and W. J. Grzymala-Busse. An approach to imbalanced datasets based on changing rule strength. In Proc. of In Learning from Imbalanced Datasets, AAAI Workshop, 2000.
• 9: J. Huang, S. Ertekin, and C. L. Giles. Efficient name disambiguation for large scale datasets. In Proc. of European Conference on Principles and Practice of Knowledge Discovery in Databases (ECML/PKDD), 2006.
• 10: N. Japkowicz. A novelty detection approach to classification. In Proc. of the Int. Joint Conference on Artificial Intelligence (IJCAI), pages 518--523, 1995.
• 11: N. Japkowicz. The class imbalance problem: Significance and strategies. In Proc. of 2000 Int. Conference on Artificial Intelligence (IC-AI'2000), volume 1, pages 111--117, 2000.
• 12: Nathalie Japkowicz , Shaju Stephen, The class imbalance problem: A systematic study, Intelligent Data Analysis, v.6 n.5, p.429-449, October 2002
• 13: Miroslav Kubat , Robert C. Holte , Stan Matwin, Machine Learning for the Detection of Oil Spills in Satellite Radar Images, Machine Learning, v.30 n.2-3, p.195-215, Feb./ March, 1998
• 14: M. Kubat and S. Matwin. Addressing the curse of imbalanced training datasets: One sided selection. Proc. of Int. Conference on Machine Learning (ICML), 30(2-3), 1997.
• 15: C. X. Ling and C. Li. Data mining for direct marketing: Problems and solutions. In Knowledge Discovery and Data Mining, pages 73--79, 1998.
• 16: Xu-Ying Liu , Jianxin Wu , Zhi-Hua Zhou, Exploratory Under-Sampling for Class-Imbalance Learning, Proceedings of the Sixth International Conference on Data Mining, p.965-969, December 18-22, 2006 [doi>10.1109/ICDM.2006.68]
• 17: M. Pazzani, C. Merz, P. Murphy, K. Ali, T. Hume, and C. Brunk. Reducing misclassification costs. In Proc. of 11th Int. Conference on Machine Learning (ICML), 1994.
• 18: F. Provost. Machine learning from imbalanced datasets 101. In Proc. of AAAI Workshop on Imbalanced Data Sets, 2000.
• 19: Predrag Radivojac , Nitesh V. Chawla , A. Keith Dunker , Zoran Obradovic, Classification and knowledge discovery in protein databases, Journal of Biomedical Informatics, v.37 n.4, p.224-239, August 2004 [doi>10.1016/j.jbi.2004.07.008]
• 20: Bhavani Raskutti , Adam Kowalczyk, Extreme re-balancing for SVMs: a case study, ACM SIGKDD Explorations Newsletter, v.6 n.1, June 2004 [doi>10.1145/1007730.1007739]
• 21: Greg Schohn , David Cohn, Less is More: Active Learning with Support Vector Machines, Proceedings of the Seventeenth International Conference on Machine Learning, p.839-846, June 29-July 02, 2000
• 22: Alex J. Smola , Bernhard Schökopf, Sparse Greedy Matrix Approximation for Machine Learning, Proceedings of the Seventeenth International Conference on Machine Learning, p.911-918, June 29-July 02, 2000
• 23: Simon Tong , Daphne Koller, Support vector machine active learning with applications to text classification, The Journal of Machine Learning Research, 2, p.45-66, 3/1/2002
• 24: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.m Miscellaneous

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Concept learning; Induction

General Terms:
Algorithms, Experimentation

Keywords:
active learning, imbalanced data, support vector machines