Bayesscher Spamfilter

Der Bayes-Spamfilter ist ein statistischer Filter zur Klassifizierung unerwünschter E-Mail-Nachrichten (Spam) durch den naiven Bayes-Klassifikator. Bei dieser Methode werden dem Filter vom Benutzer Beispielmails für Spam vorgelegt. In der Folge versucht der Filter, aus diesen Mails Wörter zu extrahieren, die charakteristisch für Spam sind. Nach der Trainingsphase soll der Filter in der Lage sein, ankommende E-Mails anhand des Vorkommens dieser Wörter als Spam zu klassifizieren.

E-Mails werden mit Hilfe des bayesschen Filters folgendermaßen untersucht: Von charakteristischen Wörtern in einer E-Mail (Ereignis) wird auf die Eigenschaft geschlossen, gänzlich unerwünscht zu sein (Spam). Dieses statistische Filtern, zuerst 1998 von Sahami et al.^[1] vorgeschlagen und ab 2002 durch einen einflussreichen Artikel von Paul Graham^[2] popularisiert, soll vorhersagen, ob es sich bei einer Nachricht um Spam handelt.

Das System wird von vielen Programmen zur Spamerkennung genutzt und ist beispielsweise in den E-Mail-Programmen Pegasus Mail, Opera Mail und Mozilla Thunderbird implementiert.

Statistische Gegenmaßnahmen basieren auf Wahrscheinlichkeitsmethoden, abgeleitet aus dem Satz von Bayes. Bayessche Filter sind oft „lernend“ (auch „selbstlernend“) organisiert und setzen auf Worthäufigkeiten in bereits vom Benutzer erhaltenen und klassifizierten E-Mails.

Ein bayesscher Filter wird durch seinen Benutzer trainiert, indem dieser seine E-Mails in erwünschte und unerwünschte Nachrichten einteilt. Der bayessche Filter stellt nun eine Liste mit Wörtern zusammen, die in unerwünschten E-Mails vorkommen. Hat der Benutzer beispielsweise E-Mails mit den Begriffen „Sex“ und „Viagra“ als Spam gekennzeichnet, haben alle E-Mails mit diesen Begriffen eine hohe Spamwahrscheinlichkeit. Begriffe aus erwünschten E-Mails wie „Verabredung“ oder „Bericht“ führen dann im Gegenzug zu einer Herabstufung der negativen Bewertung. Allerdings reichen einzelne Schlüsselwörter nicht aus, relevant ist die Summe der Bewertungen der einzelnen Wörter.

Der Filter erreicht bereits nach kurzem Training mit wenigen E-Mails hohe Trefferquoten – auch wenn für den produktiven Einsatz ein Training mit mehreren hundert E-Mails beider Kategorien empfohlen wird. Ein Risiko für den Benutzer sind falsch-positive – also solche E-Mails, die fälschlicherweise als Spam erkannt werden. Dieses Risiko lässt sich durch das Markieren von erwünschten E-Mails verringern, ist aber insbesondere für Unternehmen problematisch.

Die Versender von Spam ergreifen Gegenmaßnahmen gegen Bayes-Filter. Werbebotschaften werden in Bildern gezeigt, die der Filter nicht untersuchen kann. Auch werden verdächtige Begriffe bewusst falsch (beispielsweise „V|agra“ oder „Va1ium“) oder mit eingestreuten Leerzeichen geschrieben. Allerdings bewertet der Filter auch HTML-Tags wie „img“ und „src“ negativ, so dass Bilder in E-Mails ebenfalls mit einer höheren Spamwahrscheinlichkeit bewertet werden. Auch werden vermehrt zufällige Zitate aus der Weltliteratur (auch in weißer Schrift oder als Meta-Tag unlesbar) eingefügt, um die statistischen Maßnahmen in die Irre zu führen. Dies ist aber keine erfolgreiche Strategie, weil zufällig ausgewählte „harmlose“ Begriffe oder Sätze weder eine besonders hohe noch eine besonders niedrige Spamwahrscheinlichkeit erzielen, so dass sie letztendlich keine Rolle spielen.

Eine Besonderheit in nicht englischsprachigen Ländern entsteht durch den Umstand, dass Spam überwiegend in englischer Sprache verfasst wird. Die Trefferwahrscheinlichkeit eines bayesschen Filters dürfte daher in diesen Ländern höher liegen, aber auch die Gefahr, dass eine erwünschte englischsprachige Mail fälschlicherweise als Spam markiert wird.

Das Filtern auf statistischen Grundlagen ist eine Text-Klassifikation. Eine Anzahl von Forschern der angewandten Linguistik, die sich mit maschinellem Lernen befassen, haben sich bereits diesem Problem gewidmet. Eine Weiterentwicklung im Bereich der E-Mail-Verarbeitung ist der Markow-Spamfilter, bei der nicht nur einzelne Wörter, sondern ganze Wortketten und Kombinationsmöglichkeiten bewertet werden.

Der Satz von Bayes lautet

${\displaystyle P(A|B)\;=\;{\frac {P(B|A)\cdot P(A)}{P(B)}},}$

wobei ${\displaystyle P(A|B)}$ die bedingte Wahrscheinlichkeit des Ereignisses A unter der Voraussetzung genannt wird, dass (vorher) Ereignis B eingetreten ist.

${\displaystyle P({\text{Suchwort kommt vor}}|{\text{Spam}})\,}$

wäre demnach die Wahrscheinlichkeit dafür, dass das betreffende Suchwort in einer E-Mail vorkommt, wenn es sich bei ihr um eine Spam-Mail handelt, und umgekehrt

${\displaystyle P({\text{Spam}}|{\text{Suchwort kommt vor}})\,}$

die in diesem Zusammenhang interessierende Wahrscheinlichkeit, dass eine E-Mail Spam ist, wenn sie das betreffende Suchwort enthält. Gemäß der obigen Bayes-Formel lässt diese Wahrscheinlichkeit sich nun wie folgt berechnen:

${\displaystyle P({\text{Spam}}|{\text{Suchwort kommt vor}})\;=\;{\frac {P({\text{Suchwort kommt vor}}|{\text{Spam}})\cdot P({\text{Spam}})}{P({\text{Suchwort kommt vor}})}}.}$

In E-Mail-Programmen mit (lernenden) Naive-Bayes-Klassifikator werden sehr effizient Spam-Mails ausgefiltert.^[3] Es gibt dabei zwei Klassen von E-Mails: Spam- und Nicht-Spam-E-Mails (${\displaystyle C=\{Spam,{\overline {Spam}}\}}$). Eine E-Mail besteht dabei aus einzelnen Wörtern ${\displaystyle W_{i}}$. Aus alten, bereits klassifizierten E-Mails kann man für jedes Wort ${\displaystyle W_{i}}$ die Wahrscheinlichkeit schätzen, dass es in einer Spam- oder Nicht-Spam-E-Mail vorkommt, also:

${\displaystyle P(W_{i}|Spam)={\frac {{\text{Anzahl der Spam-E-Mails mit dem Wort }}W_{i}}{\text{Anzahl der Spam-E-Mails}}}}$

${\displaystyle P(W_{i}|{\overline {Spam}})={\frac {{\text{Anzahl der Nicht-Spam-E-Mails mit dem Wort }}W_{i}}{\text{Anzahl der Nicht-Spam-E-Mails}}}}$

Für eine neue E-Mail ${\displaystyle W}$ ist nun die Frage zu beantworten: Ist die Wahrscheinlichkeit ${\displaystyle P(Spam|W)}$ größer oder kleiner als die Wahrscheinlichkeit ${\displaystyle P({\overline {Spam}}|W)}$? Ist ${\displaystyle P(Spam|W)<P({\overline {Spam}}|W)}$, wird man die neue E-Mail als Nicht-Spam klassifizieren, anderenfalls als Spam.

Für die Wahrscheinlichkeit ${\displaystyle P(Spam|W)}$ gilt nach dem Satz von Bayes:

${\displaystyle P(Spam|W)={\frac {P(Spam\cap W)}{P(W)}}={\frac {P(W|Spam)P(Spam)}{P(W)}}}$.

${\displaystyle P(W)}$ ist die Wahrscheinlichkeit, dass die E-Mail ${\displaystyle W}$ auftritt. Da diese unabhängig von ${\displaystyle P({\overline {Spam}}|W)}$ und ${\displaystyle P(Spam|W)}$ ist, nimmt sie immer denselben Wert an und kann vernachlässigt werden. Daher betrachten die E-Mail-Programme den Ausdruck

${\displaystyle Q={\frac {P(Spam|W)}{P({\overline {Spam}}|W)}}={\frac {P(W|Spam)P(Spam)}{P(W)}}{\frac {P(W)}{P(W|{\overline {Spam}})P({\overline {Spam}})}}={\frac {P(W|Spam)P(Spam)}{P(W|{\overline {Spam}})P({\overline {Spam}})}}}$

und ist ${\displaystyle Q}$ größer als 1, dann wird die E-Mail als Spam klassifiziert, sonst als Nicht-Spam. Die Wahrscheinlichkeit, dass überhaupt eine E-Mail Spam bzw. Nicht-Spam ist, kann wieder aus den alten E-Mails geschätzt werden:

${\displaystyle P(Spam)={\frac {\text{Anzahl der Spam-E-Mails}}{\text{Anzahl aller E-Mails}}}}$ und

${\displaystyle P({\overline {Spam}})={\frac {\text{Anzahl der Nicht-Spam-E-Mails}}{\text{Anzahl aller E-Mails}}}}$.

Besteht die E-Mail ${\displaystyle W}$ aus den Wörtern ${\displaystyle W_{1},\dotsc ,W_{n}}$ und treten diese Wörter unabhängig voneinander auf, so gilt

${\displaystyle P(W|Spam)=P(W_{1}\cap \dotsb \cap W_{n}|Spam)=P(W_{1}|Spam)\dotsm P(W_{n}|Spam)}$.

Die Wahrscheinlichkeit ${\displaystyle P(W_{i}|Spam)}$ ist oben bereits angegeben worden und damit kann der Gesamtquotient berechnet werden:

${\displaystyle Q={\frac {P(Spam|W)}{P({\overline {Spam}}|W)}}={\frac {P(W_{1}|Spam)\dotsm P(W_{n}|Spam)P(Spam)}{P(W_{1}|{\overline {Spam}})\dotsm P(W_{n}|{\overline {Spam}})P({\overline {Spam}})}}}$.

Am Schluss noch drei Bemerkungen:

1. In der Praxis wird eine E-Mail als Spam klassifiziert, wenn beispielsweise ${\displaystyle Q>10}$ gilt, also die Wahrscheinlichkeit eine Spam-E-Mail zu sein wesentlich größer ist als eine Nicht-Spam-E-Mail. Der Grund liegt darin, dass eine als Spam klassifizierte E-Mail meist automatisch in einen Junk-Ordner verschoben wird, ohne dass der Empfänger sie noch einmal zu sehen bekommt. Dies ist fatal, wenn die E-Mail fälschlicherweise als Spam klassifiziert wird. Dann möchte man lieber ab und zu in seinem Inbox-Ordner eine Spam-Mail finden.
2. Dieser Filter heißt lernender Filter, da mit der Kennzeichnung von neuen E-Mails als Junk in der Inbox sich die Wahrscheinlichkeiten ${\displaystyle P(W_{i}|Spam)}$, ${\displaystyle P(Spam)}$ usw. ändern.
3. Obwohl die mathematisch-statistische Theorie die Unabhängigkeit der Wörter ${\displaystyle W_{i}}$ fordert, ist dies in der Praxis nicht erfüllt, z. B. werden die Wörter Viagra und Sex oft in einem Zusammenhang auftreten. Trotz der Verletzung dieser Voraussetzung funktionieren die Naive-Bayes-Filter in der Praxis sehr gut. Der Grund liegt darin, dass die exakten Wahrscheinlichkeiten ${\displaystyle P(Spam|W)}$ und ${\displaystyle P({\overline {Spam}}|W)}$ gar nicht benötigt werden. Es muss nur sichergestellt sein, dass man korrekt sagen kann, welche von den beiden Wahrscheinlichkeiten die größere ist.
   Daher werden meist aus der E-Mail auch nur ca. zehn Wörter zur Klassifizierung herangezogen: jeweils die fünf mit der höchsten Wahrscheinlichkeit, in einer Spam- bzw. Nicht-Spam-E-Mail vorzukommen.

• Die Mathematik im Bayes Spamfilter, die benötigten Hilfsmittel und ein Rechenbeispiel (Memento vom 31. Januar 2020 im Internet Archive)

1. ↑ M. Sahami, S. Dumais, D. Heckerman, E. Horvitz: A Bayesian approach to filtering junk e-mail, AAAI'98 Workshop on Learning for Text Categorization, 1998.
2. ↑ P. Graham: A Plan for Spam, August 2002.
3. ↑ A. Linke (2003) Spam oder nicht Spam? E-Mail sortieren mit Bayes Filtern, c’t 17/2003, S. 150