2002 Digital Symposium Collection

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

Mahesh V. Joshi, Ramesh C. Agarwal, and Vipin Kumar
View Paper (PDF)

Return to Classification and Clustering

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 propose a two-phase rule-induction method for effectively learning the signatures of rare classes. The key novel feature of our method is that it separately conquers the objectives of achieving high recall and high precision, by focusing on the rare class. The first phase of our learner 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. The focus of this paper is on core rule-induction methods that do not use meta-techniques such as bagging or boosting. Existing sequential covering core techniques try to achieve good precision for every disjunctive rule in the induced definition of the class. This strategy may not be suitable for rare classes. In this paper, we show that two other state-of-the-art core methods, RIPPER and C4.5rules, are inadequate to handle rare classes. Using synthetic datasets, we identify and analyze the situations in which these methods either fail to learn a model or learn a very poor model, whereas our method learns a model with reasonably high recall and precision levels. These synthetically created situations are representative of fairly complex models expected to appear in real applications. We also present results that compare our method with RIPPER and C4.5rules on a real-life network intrusion detection dataset. Our method either significantly outperforms or is comparable to the bet competitor, on the counts of both recall and precision.