Mining needle in a haystack: classifying rare classes via two-phase rule induction

ABSTRACT

Learning models to classify rarely occurring target classes is an important problem with applications in network intrusion detection, fraud detection, or deviation detection in general. In this paper, we analyze our previously proposed two-phase rule induction method in the context of learning complete and precise signatures of rare classes. The key feature of our method is that it separately conquers the objectives of achieving high recall and high precision for the given target class. The first phase of the method aims for high recall by inducing rules with high support and a reasonable level of accuracy. The second phase then tries to improve the precision by learning rules to remove false positives in the collection of the records covered by the first phase rules. Existing sequential covering techniques try to achieve high precision for each individual disjunct learned. In this paper, we claim that such approach is inadequate for rare classes, because of two problems: splintered false positives and error-prone small disjuncts. Motivated by the strengths of our two-phase design, we design various synthetic data models to identify and analyze the situations in which two state-of-the-art methods, RIPPER and C4.5 rules, either fail to learn a model or learn a very poor model. In all these situations, our two-phase approach learns a model with significantly better recall and precision levels. We also present a comparison of the three methods on a challenging real-life network intrusion detection dataset. Our method is significantly better or comparable to the best competitor in terms of achieving better balance between recall and precision.

REFERENCES

• 1: [1] R. C. Agarwal and M. V. Joshi. PNrule: A new framework for learning classifier models in data mining (a case study in network intrusion detection). In Proceedings of First SIAM Conference on Data Mining, Chicago, April 2001. Expanded version available as IBM Research Division Report, RC 21719, April 2000.
• 2: Leo Breiman, Bagging predictors, Machine Learning, v.24 n.2, p.123-140, Aug. 1996 [doi>10.1023/A:1018054314350]
• 3: Peter Clark , Tim Niblett, The CN2 Induction Algorithm, Machine Learning, v.3 n.4, p.261-283, March 1989 [doi>10.1023/A:1022641700528]
• 4: William W. Cohen , Yoram Singer, A simple, fast, and effective rule learner, Proceedings of the sixteenth national conference on Artificial intelligence and the eleventh Innovative applications of artificial intelligence conference innovative applications of artificial intelligence, p.335-342, July 18-22, 1999, Orlando, Florida, United States
• 5: [5] W. W. Cohen. Fast effective rule induction. In Proc. of Twelfth International Conference on Machine Learning, Lake Tahoe, California, 1995.
• 6: [6] A. Danyluk and F. Provost, Small disjuncts in action: Learning to diagnose errors in the local loop of the telephone network. In Proc. of Tenth International Conference on Machine Learning, pages 81-88. Morgan Kaufmann, 1993.
• 7: [7] C. Elkan. Results of the KDD'99 classifier learning contest. In http:///www-cse.ucsd.edu/~elkan/clresults.html, September 1999.
• 8: [8] R. C. Holte, L. Acker, and B. Porter. Concept learning and the problem of small disjuncts. In Proc. of Eleventh International Joint Conference on Artificial Intelligence (IJCAI-89), Pages 813-818, 1989.
• 9: [9] R. Michalski, I. Mozetic, J. Hong, and N. Lavrac. The multi-purpose incremental learning system AQ15 and its testing application to three medical domains. In Proc. of Fifth National Conference on AI (AAAI-86). pages 1041-1045, Philadelphia, 1986.
• 10: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 11: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 12: Robert E. Schapire , Yoram Singer, Improved Boosting Algorithms Using Confidence-rated Predictions, Machine Learning, v.37 n.3, p.297-336, Dec. 1999 [doi>10.1023/A:1007614523901]
• 13: Y.-S. Shih, Families of splitting criteria for classification trees, Statistics and Computing, v.9 n.4, p.309-315, November 1999 [doi>10.1023/A:1008920224518]
• 14: C. J. Van Rijsbergen, Information Retrieval, Butterworth-Heinemann, Newton, MA, 1979
• 15: [15] G. M. Weiss. Learning with rare cases and small disjuncts. In Proc. of Twelfth International Conference on Machine Learning, pages 558-565, Lake Tahoe, California, 1995.
• 16: Sholom M. Weiss , Nitin Indurkhya, Lightweight Rule Induction, Proceedings of the Seventeenth International Conference on Machine Learning, p.1135-1142, June 29-July 02, 2000

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation

General Terms:
Algorithms, Design, Management, Measurement, Performance, Theory