The Bayesian Spam Filter with NCD

Michal Prilepok, Jan Platos, Václav Snásel, Eyas El-QawasmehDATESO 2012

TL;DR

This paper introduces a novel spam detection method that combines a classic Bayesian filter with Normalized Compression Distance (NCD). By leveraging NCD to measure the similarity of email content, the authors aim to reduce false positives and improve overall spam detection accuracy, showing promising results in reducing error rates.

What Problem Does This Paper Address?

The ever-increasing volume of unsolicited emails, commonly known as spam, poses a significant challenge for both individual users and internet service providers. While various spam filtering techniques exist, a persistent problem is the low rate of accurately identifying spam without also flagging legitimate emails (false positives). This paper tackles the issue of improving spam detection accuracy, specifically by reducing the rate of falsely detected emails, which is a critical security concern.

Methods

The core of this research lies in enhancing a traditional Bayesian spam filter. The authors propose two main approaches:

  • Classic Bayesian Filter: This is the baseline, using probabilistic methods to classify emails based on the occurrence of words.
  • Bayesian Filter with Normalized Compression Distance (NCD): This is the novel contribution. NCD is a mathematical measure of similarity between objects, calculated by how much their combined compressed size differs from the sum of their individual compressed sizes. In this context, emails are treated as objects, and NCD is used to assess the similarity of a new email to known spam emails.
  • Implementation: The authors use the GZIP compression algorithm (specifically the DEFLATE method) to compute NCD.
  • Integration: NCD is applied as an additional check for emails that have a "spamcity" (a measure of how likely a word is to appear in spam) above a certain threshold (0.5). This means if an email is already flagged as potentially spam by the Bayesian filter, NCD is used to further refine the decision. Two variations are tested: one applying NCD to all emails with spamcity > 0.5, and another restricting it to a narrower interval (0.5 to 0.75).
  • Combination: The probabilities from the Bayesian filter and the NCD are combined using a Bayesian theorem to produce a final, more robust spam probability.

Datasets

The experiments were conducted on a database of 270,045 emails, comprising 170,750 (63.23%) spam emails and 99,295 (36.77%) ham (legitimate) emails. This dataset was sourced from the Text Retrieval Conference (TREC) archives from the years 2005, 2006, and 2007.

Key Insights and Ideas

  • NCD as a Similarity Metric for Text: The paper demonstrates that NCD, typically used for comparing various data types, can be effectively applied to measure the similarity of email content for spam detection. This is a novel application of NCD in this domain.
  • Complementary Strengths: The Bayesian filter excels at probabilistic classification based on word frequencies, while NCD provides a measure of content similarity. Combining them leverages the strengths of both approaches, potentially leading to more accurate decisions.
  • Targeted NCD Application: Applying NCD only to emails already flagged as potentially spam by the Bayesian filter is a smart strategy. It avoids unnecessary computational overhead for clearly legitimate or clearly spam emails, focusing the more computationally intensive NCD check where it's most likely to make a difference.
  • Trade-off between Speed and Accuracy: The introduction of NCD, while improving accuracy, inevitably slows down the filtering process. The paper explores different thresholds for NCD application to find a balance between speed and detection effectiveness.

Key Results

The paper presents a comparative analysis of three algorithms: a classic Bayesian filter, and two versions of the Bayesian filter combined with NCD.

  • Classic Bayesian Filter: Achieved a spam success rate of 94.50% and an error rate of 6.52% (total incorrectly marked emails). Its filtering speed was approximately 288 emails per second.
  • Bayesian Filter + NCD (spamcity > 0.5): This version significantly improved spam detection, reaching a success rate of 99.49% with a total error rate of 4.98%. However, the filtering speed dropped considerably to about 32.83 emails per second.
  • Bayesian Filter + NCD (0.5 < spamcity < 0.75): This version also achieved a 99.49% spam success rate with a total error rate of 4.98%. Its filtering speed was faster than the first NCD version, at approximately 192.59 emails per second, making it a more balanced approach.

Overall, the NCD-enhanced versions showed higher efficiency in spam detection, though the rate of incorrectly marked legitimate emails slightly increased in some configurations compared to the classic filter.

Limitations and Future Work

  • Speed Reduction: The primary limitation acknowledged is the significant decrease in filtering speed when NCD is employed, especially when applied broadly.
  • Ham Error Rate: While spam detection improved, the rate of incorrectly marking legitimate emails (ham error rate) saw a slight increase in the NCD-enhanced versions compared to the classic Bayesian filter.
  • Future Work: The authors suggest that the overall efficiency of the new algorithms was better than the original filter, implying that further refinement of the NCD application strategy could yield even better results. The paper also hints at exploring other heuristics and potentially using word sequences (n-grams) instead of individual words for even higher sensitivity.

Summary updated

BibTeX
@inproceedings{prilepok2012bayesian,
  author = {Michal Prilepok and Jan Platos and Václav Snásel and Eyas El-Qawasmeh},
  title = {{The Bayesian Spam Filter with NCD}},
  booktitle = {DATESO},
  year = {2012},
}
Figure