Supervised Clustering of Streaming Data for Email Batch Detection

Supervised Clustering of Streaming Data for Email Batch Detection
Peter Haider - Max Planck Institute for Computer Science, Germany Ulf Brefeld - Max Planck Institute for Computer Science, Germany Tobias Scheffer - Max Planck Institute for Computer Science, Germany
We address the problem of detecting batches of emails that have been created according to the same template. This problem is motivated by the desire to filter spam more effectively by exploiting collective information about entire batches of jointly generated messages. The application matches the problem setting of supervised clustering, because examples of correct clusterings can be collected. Known decoding procedures for supervised clustering are cubic in the number of instances. When decisions cannot be reconsidered once they have been made allowing to the streaming nature of the data all then the decoding problem can be solved in linear time. We devise a sequential decoding procedure and derive the corresponding optimization problem of supervised clustering. We study the impact of collective attributes of email batches on the effectiveness of recognizing spam emails.

Peter Haider - Max Planck Institute for Computer Science, Germany
Ulf Brefeld - Max Planck Institute for Computer Science, Germany
Tobias Scheffer - Max Planck Institute for Computer Science, Germany

We address the problem of detecting batches of emails that have been created according to the same template. This problem is motivated by the desire to filter spam more effectively by exploiting collective information about entire batches of jointly generated messages. The application matches the problem setting of supervised clustering, because examples of correct clusterings can be collected. Known decoding procedures for supervised clustering are cubic in the number of instances. When decisions cannot be reconsidered once they have been made allowing to the streaming nature of the data all then the decoding problem can be solved in linear time. We devise a sequential decoding procedure and derive the corresponding optimization problem of supervised clustering. We study the impact of collective attributes of email batches on the effectiveness of recognizing spam emails.