Local sparsity control for naive Bayes with extreme misclassification costs

ABSTRACT

In applications of data mining characterized by highly skewed misclassification costs certain types of errors become virtually unacceptable. This limits the utility of a classifier to a range in which such constraints can be met. Naive Bayes, which has proven to be very useful in text mining applications due to high scalability, can be particularly affected. Although its 0/1 loss tends to be small, its misclassifications are often made with apparently high confidence. Aside from efforts to better calibrate Naive Bayes scores, it has been shown that its accuracy depends on document sparsity and feature selection can lead to marked improvement in classification performance. Traditionally, sparsity is controlled globally, and the result for any particular document may vary. In this work we examine the merits of local sparsity control for Naive Bayes in the context of highly asymmetric misclassification costs. In experiments with three benchmark document collections we demonstrate clear advantages of document-level feature selection. In the extreme cost setting, multinomial Naive Bayes with local sparsity control is able to outperform even some of the recently proposed effective improvements to the Naive Bayes classifier. There are also indications that local feature selection may be preferable in different cost settings.

REFERENCES

• 1: Chidanand Apté , Fred Damerau , Sholom M. Weiss, Automated learning of decision rules for text categorization, ACM Transactions on Information Systems (TOIS), v.12 n.3, p.233-251, July 1994 [doi>10.1145/183422.183423]
• 2: P. N. Bennett. Assessing the calibration of Naive Bayes posterior estimates. Technical Report CMU-CS-00-155, Computer Science Department, School of Computer Science, Carnegie Mellon University, 2000.
• 3: Paul N. Bennett, Using asymmetric distributions to improve text classifier probability estimates, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860457]
• 4: Paul N. Bennett , Susan T. Dumais , Eric Horvitz, Probabilistic combination of text classifiers using reliability indicators: models and results, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564413]
• 5: A. Bradley. The use of the area under the ROC curve in the evaluation of machine learning algorithms. Pattern Recognition, 30(7):1145--1159, 1997.
• 6: R. Caruana and A. Niculescu-Mizil. Predicting good probabilities with supervised learning. In Proceedings of the American Meteorology Conference (AMS2005), 2005.
• 7: Abdur Chowdhury , Ophir Frieder , David Grossman , Mary Catherine McCabe, Collection statistics for fast duplicate document detection, ACM Transactions on Information Systems (TOIS), v.20 n.2, p.171-191, April 2002 [doi>10.1145/506309.506311]
• 8: William W. Cohen , Yoram Singer, Context-sensitive learning methods for text categorization, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.307-315, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243278]
• 9: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 10: Fedro Domingos, Control-Sensitive Feature Selection for Lazy Learners, Artificial Intelligence Review, v.11 n.1-5, p.227-253, Feb. 1997 [doi>10.1023/A:1006508722917]
• 11: Pedro Domingos , Michael Pazzani, On the Optimality of the Simple Bayesian Classifier under Zero-One Loss, Machine Learning, v.29 n.2-3, p.103-130, Nov./Dec. 1997 [doi>10.1023/A:1007413511361]
• 12: C. Elkan. The foundations of cost-sensitive learning. In Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, pages 973--978, 2001.
• 13: George Forman, An extensive empirical study of feature selection metrics for text classification, The Journal of Machine Learning Research, 3, 3/1/2003
• 14: Nir Friedman , Dan Geiger , Moises Goldszmidt, Bayesian Network Classifiers, Machine Learning, v.29 n.2-3, p.131-163, Nov./Dec. 1997 [doi>10.1023/A:1007465528199]
• 15: P. Graham. A plan for spam, 2002. Available from World Wide Web: http://www.paulgraham.com/spam.html.
• 16: Ron Kohavi , George H. John, Wrappers for feature subset selection, Artificial Intelligence, v.97 n.1-2, p.273-324, Dec. 1997 [doi>10.1016/S0004-3702(97)00043-X]
• 17: M. Kukar. Transductive reliability estimation for medical diagnosis. Artificial Intelligene in Medicine, 29:81--106, 2003.
• 18: David D. Lewis, Naive (Bayes) at Forty: The Independence Assumption in Information Retrieval, Proceedings of the 10th European Conference on Machine Learning, p.4-15, April 21-23, 1998
• 19: David D. Lewis , Robert E. Schapire , James P. Callan , Ron Papka, Training algorithms for linear text classifiers, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.298-306, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243277]
• 20: Christopher D. Manning , Hinrich Schütze, Foundations of statistical natural language processing, MIT Press, Cambridge, MA, 1999
• 21: A. McCallum and K. Nigam. A comparison of event models for Naive Bayes text classification. In Proceedings of the AAAI-98 Workshop on Learning for Text Categorization, 1998.
• 22: Dunja Mladenić , Janez Brank , Marko Grobelnik , Natasa Milic-Frayling, Feature selection using linear classifier weights: interaction with classification models, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1009034]
• 23: Dunja Mladenic , Marko Grobelnik, Feature Selection for Unbalanced Class Distribution and Naive Bayes, Proceedings of the Sixteenth International Conference on Machine Learning, p.258-267, June 27-30, 1999
• 24: Dmitry Pavlov , Ramnath Balasubramanyan , Byron Dom , Shyam Kapur , Jignashu Parikh, Document preprocessing for naive Bayes classification and clustering with mixture of multinomials, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1016922]
• 25: J. C. Platt. Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods. In A. Smola, P. Bartlett, B. Schölkopf, and D. Schuurmans, editors, Advances in Large Margin Classifiers, pages 61--74. MIT Press, 1999.
• 26: F. Provost. Learning with imbalanced data sets 101. In Proceedings of the AAAI'2000 Workshop on Imbalanced Data Sets, 2000.
• 27: Foster Provost , Tom Fawcett, Robust Classification for Imprecise Environments, Machine Learning, v.42 n.3, p.203-231, March 2001 [doi>10.1023/A:1007601015854]
• 28: J. Rennie, L. Shih, J. Teevan, and D. Karger. Tackling the poor assumptions of Naive Bayes text classifiers. In Proceedings of the Twentieth International Conference on Machine Learning, 2003.
• 29: Marco Saerens , Patrice Latinne , Christine Decaestecker, Adjusting the outputs of a classifier to new a priori probabilities: a simple procedure, Neural Computation, v.14 n.1, p.21-41, January 2002 [doi>10.1162/089976602753284446]
• 30: Geoffrey I. Webb , Michael J. Pazzani, Adjusted Probability Naive Bayesian Induction, Selected papers from the 11th Australian Joint Conference on Artificial Intelligence on Advanced Topics in Artificial Intelligence, p.285-295, July 13-17, 1998
• 31: Yiming Yang , Jan O. Pedersen, A Comparative Study on Feature Selection in Text Categorization, Proceedings of the Fourteenth International Conference on Machine Learning, p.412-420, July 08-12, 1997
• 32: Bianca Zadrozny , Charles Elkan, Obtaining calibrated probability estimates from decision trees and naive Bayesian classifiers, Proceedings of the Eighteenth International Conference on Machine Learning, p.609-616, June 28-July 01, 2001
• 33: Bianca Zadrozny , Charles Elkan, Transforming classifier scores into accurate multiclass probability estimates, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775151]
• 34: Jian Zhang , Yiming Yang, Probabilistic score estimation with piecewise logistic regression, Proceedings of the twenty-first international conference on Machine learning, p.115, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015335]

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Measurement

Keywords:
feature selection, high recall classification, naive Bayes, text categorization