Bayesian clustering for email campaign detection

ABSTRACT

We discuss the problem of clustering elements according to the sources that have generated them. For elements that are characterized by independent binary attributes, a closed-form Bayesian solution exists. We derive a solution for the case of dependent attributes that is based on a transformation of the instances into a space of independent feature functions. We derive an optimization problem that produces a mapping into a space of independent binary feature vectors; the features can reflect arbitrary dependencies in the input space. This problem setting is motivated by the application of spam filtering for email service providers. Spam traps deliver a real-time stream of messages known to be spam. If elements of the same campaign can be recognized reliably, entire spam and phishing campaigns can be contained. We present a case study that evaluates Bayesian clustering for this application.

REFERENCES

• 1: Peter Haider , Ulf Brefeld , Tobias Scheffer, Supervised clustering of streaming data for email batch detection, Proceedings of the 24th international conference on Machine learning, p.345-352, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273540]
• 2: Katherine A. Heller , Zoubin Ghahramani, Bayesian hierarchical clustering, Proceedings of the 22nd international conference on Machine learning, p.297-304, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102389]
• 3: Lau, J., & Green, P. (2007). Bayesian Model-Based Clustering Procedures. Journal of Computational and Graphical Statistics, 16, 526--558.
• 4: Teo, C., Globerson, A., Roweis, S., & Smola, A. (2008). Convex Learning with Invariances. Advances in Neural Information Processing Systems, 20, 1489--1496.
• 5: Geoffrey I. Webb , Janice R. Boughton , Zhihai Wang, Not So Naive Bayes: Aggregating One-Dependence Estimators, Machine Learning, v.58 n.1, p.5-24, January 2005 [doi>10.1007/s10994-005-4258-6]
• 6: Williams, C. (2000). A MCMC approach to hierarchical mixture modelling. Advances in Neural Information Processing Systems, 12, 680--686.
• 7: Zijian Zheng , Geoffrey I. Webb, Lazy Learning of Bayesian Rules, Machine Learning, v.41 n.1, p.53-84, Oct. 2000 [doi>10.1023/A:1007613203719]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
          Subjects: Algorithms

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

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

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Feature evaluation and selection
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory