On-line spam filter fusion

ABSTRACT

We show that a set of independently developed spam filters may be combined in simple ways to provide substantially better filtering than any of the individual filters. The results of fifty-three spam filters evaluated at the TREC 2005 Spam Track were combined post-hoc so as to simulate the parallel on-line operation of the filters. The combined results were evaluated using the TREC methodology, yielding more than a factor of two improvement over the best filter. The simplest method -- averaging the binary classifications returned by the individual filters -- yields a remarkably good result. A new method -- averaging log-odds estimates based on the scores returned by the individual filters -- yields a somewhat better result, and provides input to SVM- and logistic-regression-based stacking methods. The stacking methods appear to provide further improvement, but only for very large corpora. Of the stacking methods, logistic regression yields the better result. Finally, we show that it is possible to select a priori small subsets of the filters that, when combined, still outperform the best individual filter by a substantial margin.

REFERENCES

• 1: Attia, J. Moving beyond sensistivity and specificity: using likelihood ratios to help interpret diagnostic tests. Australian Prescriber 26, 5 (2003), 111--113.
• 2: Brian T. Bartell , Garrison W. Cottrell , Richard K. Belew, Automatic combination of multiple ranked retrieval systems, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.173-181, July 03-06, 1994, Dublin, Ireland
• 3: N. J. Belkin , P. Kantor , E. A. Fox , J. A. Shaw, Combining the evidence of multiple query representations for information retrieval, Proceedings of the second conference on Text retrieval conference, p.431-448, May 1995, Washington, D.C., United States
• 4: Paul N. Bennett , Susan T. Dumais , Eric Horvitz, The Combination of Text Classifiers Using Reliability Indicators, Information Retrieval, v.8 n.1, p.67-100, January 2005 [doi>10.1023/B:INRT.0000048491.59134.94]
• 5: Jon Louis Bentley , Jerome H. Friedman, Data Structures for Range Searching, ACM Computing Surveys (CSUR), v.11 n.4, p.397-409, Dec. 1979 [doi>10.1145/356789.356797]
• 6: Cormack, G. V., and Bratko, A. Batch and on-line spam filter evaluation. In CEAS 2006 -- The 3rd Conference on Email and Anti-Spam (Mountain View, 2006).
• 7: Cormack, G. V., and Lynam, T. R. Overview of the TREC 2005 Spam Evaluation Track. In Fourteenth Text REtrieval Conference (TREC-2005) (Gaithersburg, MD, 2005), NIST.
• 8: Gordon V. Cormack , Thomas R. Lynam, Statistical precision of information retrieval evaluation, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148262]
• 9: Thomas G. Dietterich, Ensemble Methods in Machine Learning, Proceedings of the First International Workshop on Multiple Classifier Systems, p.1-15, June 21-23, 2000
• 10: Saso Džeroski , Bernard Ženko, Is Combining Classifiers with Stacking Better than Selecting the Best One?, Machine Learning, v.54 n.3, p.255-273, March 2004 [doi>10.1023/B:MACH.0000015881.36452.6e]
• 11: Fawcett, T. ROC graphs: Notes and practical considerations for researchers. Tech. Rep. HPL-2003-4, HP Laboratories, 2004.
• 12: Joydeep Ghosh, Multiclassifier Systems: Back to the Future, Proceedings of the Third International Workshop on Multiple Classifier Systems, p.1-15, June 24-26, 2002
• 13: David A. Hull , Jan O. Pedersen , Hinrich Schütze, Method combination for document filtering, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.279-287, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243275]
• 14: Thorsten Joachims, Making large-scale support vector machine learning practical, Advances in kernel methods: support vector learning, MIT Press, Cambridge, MA, 1999
• 15: Josef Kittler , Mohamad Hatef , Robert P. W. Duin , Jiri Matas, On Combining Classifiers, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.20 n.3, p.226-239, March 1998 [doi>10.1109/34.667881]
• 16: Komarek, P., and Moore, A. Fast robust logistic regression for large sparse datasets with binary outputs. In Artificial Intelligence and Statistics (2003).
• 17: Wai Lam , Kwok-Yin Lai, A meta-learning approach for text categorization, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.303-309, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.384011]
• 18: 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]
• 19: Lynam, T., and Cormack, G. TREC Spam Filter Evaluation Took Kit. http://plg.uwaterloo.ca/~trlynam/spamjig.
• 20: Thomas R. Lynam , Chris Buckley , Charles L. A. Clarke , Gordon V. Cormack, A multi-system analysis of document and term selection for blind feedback, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA [doi>10.1145/1031171.1031229]
• 21: Mark Montague , Javed A. Aslam, Condorcet fusion for improved retrieval, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584881]
• 22: Sakkis, G., Androutsopoulos, I., Paliouras, G., Karkaletsis, V., Spyropoulos, C. D., and Stamatopoulos, P. Stacking classifiers for anti-spam filtering of e-mail, 2001.
• 23: Fabrizio Sebastiani, Machine learning in automated text categorization, ACM Computing Surveys (CSUR), v.34 n.1, p.1-47, March 2002 [doi>10.1145/505282.505283]
• 24: Segal, R., Crawford, J., Kephart, J., and Leiba, B. SpamGuru: An enterprise anti-spam filtering system. In First Conference on Email and Anti-Spam (CEAS) (2004).
• 25: Shaw, J. A., and Fox, E. A. Combination of multiple searches. In Text REtrieval Conference (1994).
• 26: Voorhees, E. Fourteenth Text REtrieval Conference (TREC-2005). NIST, Gaithersburg, MD, 2005.
• 27: David H. Wolpert, Stacked generalization, Neural Networks, v.5 n.2, p.241-259, 1992 [doi>10.1016/S0893-6080(05)80023-1]
• 28: Yi Zhang, Using bayesian priors to combine classifiers for adaptive filtering, 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.1009052]

INDEX TERMS

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

General Terms:
Experimentation, Measurement

Keywords:
classification, email, filtering, spam