Learning classifier models for predicting rare phenomena
Vipin Kumar, Ramesh K. Agarwal, Mahesh V. Joshi · 2002
The problem of predicting rarely occurring phenomena is faced in many critical domains such as network intrusion detection, fraud detection, weblog analysis, document categorization, and genomics. This thesis treats it as a supervised problem and explores various methods of learning classifier models for a given rare class, with the goal of correctly predicting a large fraction of its future occurrences with high precision. A two phase rule induction algorithm PNrule and a ripple down rule induction algorithm CREDOS are proposed to learn single classifier models. Using synthetic problems of varying degrees of separability, multi-modality, and rarity, these methods are compared with existing methods such as RIPPER, C4.5rules, and the Naive Bayesian classifier. In order to facilitate proper comparison between classifiers, a new method is proposed to directly address the desired goal based on recall and precision. Also, some composite metrics are argued to be more suitable than others using an objective analysis not dependent on any specific application domain. Algorithmic comparisons on controlled and real world experiments yield many interesting insights as to which algorithmic features are crucial for addressing different problem characteristics effectively. Boosting is a powerful method to learn an ensemble of weak models with a promise of improving the classification accuracy. This promise is evaluated in the context of rare class problems, where accuracy metric is less meaningful. A comparative analysis of the effect of weight update mechanisms of various algorithms on the more relevant recall and precision metrics leads to two new enhanced algorithms. It is qualitatively argued that boosting cannot guarantee an explicit learning ability of PNrule when it uses a base learner employing implicit learning of false positives. Finally, detailed theoretical analysis of the interaction between the three primary components of boosting; viz. the base learner accuracy, the weight update mechanism, and ensemble voting; is conducted to argue that boosting performance is critically dependent on the choice of its base learner. All the new boosting algorithms, arguments, and insights are empirically validated on synthetic as well as real world benchmark problems.