An experimental comparison of naive Bayesian and keyword-based anti-spam filtering with personal e-mail messages

ABSTRACT

The growing problem of unsolicited bulk e-mail, also known as “spam”, has generated a need for reliable anti-spam e-mail filters. Filters of this type have so far been based mostly on manually constructed keyword patterns. An alternative approach has recently been proposed, whereby a Naive Bayesian classifier is trained automatically to detect spam messages. We test this approach on a large collection of personal e-mail messages, which we make publicly available in “encrypted” form contributing towards standard benchmarks. We introduce appropriate cost-sensitive measures, investigating at the same time the effect of attribute-set size, training-corpus size, lemmatization, and stop lists, issues that have not been explored in previous experiments. Finally, the Naive Bayesian filter is compared, in terms of performance, to a filter that uses keyword patterns, and which is part of a widely used e-mail reader.

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: W.W. Cohen. Learning Rules that Classify E-Mail. In Proc. of the AAAI Spring Symposium on Machine Learning in Information Access, Stanford, California, 1996.
• 3: Lorrie Faith Cranor , Brian A. LaMacchia, Spam!, Communications of the ACM, v.41 n.8, p.74-83, Aug. 1998 [doi>10.1145/280324.280336]
• 4: Hamish Cunningham , Yorick Wilks , Robert J. Gaizauskas, GATE: a General Architecture for Text Engineering, Proceedings of the 16th conference on Computational linguistics, August 05-09, 1996, Copenhagen, Denmark [doi>10.3115/993268.993365]
• 5: I. Dagan, Y. Karov and D. Roth. Mistake-Driven Learning in Text Categorization. In Proc. of the 2 na Conference on Empirical Methods in Natural Language Processing, pp. 55- 63, Providence, Rhode Island, 1997.
• 6: P. Domingos and M. Pazzani. Beyond Independence: Conditions for the Optimality of the Simple Bayesian Classifier. In Proc. o f the 13 th International Conference on Machine Learning, pp. 105-112, Bari, Italy, 1996.
• 7: R.O. Duda and P.E. Hart. Bayes Decision Theory. Chapter 2 in Pattern Classification and Scene Analysis, pp. 10-43. John Wiley, 1973.
• 8: D. Forsyth. Finding Naked People. In Proc. of the 4 th European Conference on Computer Vision, Cambridge, England, 1996.
• 9: K.T. Frantzi. Automatic Recognition of Multi-Word Terms. PhD Thesis, Manchester Metropolitan University, England, 1998.
• 10: 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]
• 11: C.L. Green and P. Edwards. Using Machine Learning to Enhance Software Tools for lnternet Information Management. In Proc. o f the AAAI Workshop on Internet-Based Information Systems, pp. 48-55, Portland, Oregon, 1996.
• 12: Robert J. Hall, How to avoid unwanted email, Communications of the ACM, v.41 n.3, p.88-95, March 1998 [doi>10.1145/272287.272329]
• 13: Nicholas Kushmerick, Learning to remove Internet advertisements, Proceedings of the third annual conference on Autonomous Agents, p.175-181, April 1999, Seattle, Washington, United States [doi>10.1145/301136.301186]
• 14: K. Lang. Newsweeder: Learning to Filter Netnews. In Proc. of the 12 th International Conference on Machine Learning, pp. 331-339, Stanford, California, 1995.
• 15: P. Langley, I. Wayne and K. Thompson. An Analysis of Bayesian Classifiers. In Proc. o f the 10 h National Conference on Artificial Intelligence, pp. 223-228, San Jose, California, 1992.
• 16: David D. Lewis, Feature selection and feature extraction for text categorization, Proceedings of the workshop on Speech and Natural Language, February 23-26, 1992, Harriman, New York [doi>10.3115/1075527.1075574]
• 17: 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]
• 18: David D. Lewis , Kimberly A. Knowles, Threading electronic mail: a preliminary study, Information Processing and Management: an International Journal, v.33 n.2, p.209-217, March 1997 [doi>10.1016/S0306-4573(96)00063-5]
• 19: Hang Li , Kenji Yamanishi, Document classification using a finite mixture model, Proceedings of the 35th annual meeting on Association for Computational Linguistics, p.39-47, July 07-12, 1997, Madrid, Spain
• 20: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 21: T.R. Payne and P. Edwards. Interface Agents that Learn: An Investigation of Learning Issues in a Mail Agent Interface. Applied Artificial Intelligence, 11 (1): 1-32, 1997.
• 22: Ellen Riloff , Wendy Lehnert, Information extraction as a basis for high-precision text classification, ACM Transactions on Information Systems (TOIS), v.12 n.3, p.296-333, July 1994 [doi>10.1145/183422.183428]
• 23: M. Sahami, S. Dumais, D. Heckerman, and E. Horvitz. A Bayesian Approach to Filtering Junk E-Mail. In Learning for Text Categorization - Papers fi'om the AAA1 Workshop, pp. 55-62, Madison Wisconsin. AAAI Technical Report WS-98- 05, 1998.
• 24: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 25: E. Spertus. Smokey: Automatic Recognition of Hostile Messages. In Proc. of the 14 th National Conference on AI and th the 9 Conference on Innovative Applications of A1, pp. 1058- 1065, Providence, Rhode Island, 1997.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Information filtering

Additional Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.3 Communications Applications
          Subjects: Electronic mail

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Algorithms, Human Factors, Performance, Reliability, Theory

Keywords:
evaluation (general), filtering&slash;routing, machine learning and IR, test collections, text categorization