Theorem von Bayes/Beispiel: Spam Mail filtering

Aus MM*Stat

Wechseln zu: Navigation, Suche

Beispiel: E-Mail filtering

https://de.wikipedia.org/wiki/Satz_von_Bayes Jeder der E-Mail benutzt kennt das Problem: man erhält Tag für Tag Spam-Mails, die meist von der E-Mail-Software in den Junk Ordner verschoben wird. Eine Methode um Spam-Mails zu erkennen ist der Bayes-Filter.

Deutscher Strassenpenner wurde zum Superreichen mit einem Vermögen von 82.000.000 Euro (Mio. Euro) ...und das in nur einem Jahr!

Diese Geschichte ist erst paar Tage alt. Doch schon sehr viele TV-Sender berichteten darüber...

...

Für Anfänger hat er jetzt eine Webseite erstellt, die jedem ganz leicht zeigt wie er es gemacht hat und wie es geht!

1000 Mal möchte er dieses System kostenfrei weitergeben. Danach wird es 1499 Euro kosten. Es ist nur noch für 49 Interessenten kostenfrei erhältlich, danach wird die Seite offline genommen!

Naive Bayes Filter

Der Naive Bayes Filter berechnet die Wahrscheinlichkeit des Ereignisses SPAM = {E-Mail ist SPAM} anhand der Worte, die in der E-Mail verwendet werden.


\begin{align}
P(SPAM|Deutscher\text{ }Strassenpenner..)&=\frac{P(SPAM\cap \{Deutscher\text{ }Strassenpenner...\})}{P(Deutscher\text{ }Strassenpenner...)}\\
&= \frac{P(Deutscher\text{ }Strassenpenner...|SPAM)\cdot P(SPAM)}{P(Deutscher\text{ }Strassenpenner...)}
\end{align}

Wird die totale Wahrscheinlichkeit


\begin{align}
P(Deutscher\text{ }Strassenpenner...)&=P(SPAM\cap \{Deutscher\text{ }Strassenpenner...\})\\
&+P(\overline{SPAM}\cap \{Deutscher\text{ }Strassenpenner...\})\\
&=P(Deutscher\text{ }Strassenpenner...|SPAM)\cdot P(SPAM)\\
&+P(Deutscher\text{ }Strassenpenner...|\overline{SPAM})\cdot P(\overline{SPAM})
\end{align}

weiter aufgelöst, dann sieht man die Anwendung des Theorem von Bayes. Wäre jetzt

P(SPAM|Deutscher\text{ }Strassenpenner..) > c

dann würde eine E-Mail als SPAM Mail klassifiziert und in den Junk Ordner verschoben statt in die Inbox.

Problem: Totale Wahrscheinlichkeit

Um sich die Berechnung der totalen Wahrscheinlichkeit zu ersparen wird stattdessen


\frac{P(SPAM|Deutscher\text{ }Strassenpenner..)}{P(\overline{SPAM}|Deutscher\text{ }Strassenpenner..)}
= \frac{P(Deutscher\text{ }Strassenpenner...|SPAM)\cdot P(SPAM)}{P(Deutscher\text{ }Strassenpenner...|\overline{SPAM})\cdot P(\overline{SPAM})} > c

betrachtet, da sich die totale Wahrscheinlichkeit hier rauskürzt. Man schaut also darauf wie viel wahrscheinlicher ist es, dass eine E-Mail mit dem Text Deutscher Strassenpenner... eine SPAM E-Mail ist im Verhältnis dazu sie keine SPAM E-Mail ist. c liegt meist in einem Bereich von 5 - 10.

Problem: Wahrscheinlichkeit des E-Mail Textes

Die Wahrscheinlichkeit, dass der gesamte E-Mail Text so auftritt ist jedoch sehr gering. Um dieses Problem zu umgehen wird angenommen, dass eine (bedingte) Unabhängigkeit der Worte gilt, also:




P(Deutscher\text{ }Strassenpenner...|SPAM) = P(Deutscher|SPAM)\cdot P(Strassenpenner|SPAM)\cdot ...

bzw.


P(Deutscher\text{ }Strassenpenner...|\overline{SPAM}) = P(Deutscher|\overline{SPAM})\cdot P(Strassenpenner|\overline{SPAM})\cdot ...

Die Wahrscheinlichkeit, dass dieser Text als SPAM E-Mail auftritt, wird zurückgeführt auf die Wahrscheinlichkeit das jedes der Einzelworte in einer SPAM E-Mail auftritt. Formal gilt das natürlich nicht, z.B. werden die Worte Viagra und Sex nicht unabhängig voneinander in E-Mails auftreten. Das Ziel ist es jedoch nicht die exakten Wahrscheinlichkeiten zu berechnen, sondern eine hinreichend gute Heuristik zur Identifikation von SPAM E-Mails zu bekommen!

Damit haben wir alle Daten zusammen um den obigen Quotienten zu schätzen und nachzuschauen, ob er größer oder kleiner als c ist:

  • Anhand der eingegangenen E-Mails und der E-Mails im Junk Ordner können wir P(SPAM) und P(\overline{SPAM}) schätzen.
  • Anhand der Texte der E-Mails in Nicht-Junk-Ordnern und der Texte in E-Mails im Junk Ordner können wir für jedes Wort

P(Wort|SPAM) und P(Wort|\overline{SPAM}) schätzen.

Typischerweise werden auch nicht alle Worte in einer E-Mail verwendet, sondern nur die fünf bis zehn Worte, die die höchste Wahrscheinlichkeit für P(Wort|SPAM) oder P(Wort|\overline{SPAM}) haben.

Lernende Naive Bayes Filter

Die Naive Bayes Filter können auch relativ schnell neue SPAM E-Mails erkennen, vorausgesetzt wir helfen dem Algorithmus. Denn wenn wir eine SPAM-Mail als nicht SPAM-Mail klassifizieren oder eine Nicht-SPAM-Mail als SPM-Mail, dann verändern wir auch die geschätzten Wahrscheinlichkeiten für P(Wort|SPAM), P(Wort|\overline{SPAM}), P(SPAM) und P(\overline{SPAM}).

Weitere Methoden

Neben dem Naive Bayes Filtering gibt es eine Vielzahl weitere Methoden um SPAM Mail zu filtern:

  • Whitelist: Listen von vertrauenswürdigen E-Mail-Adressen, deren E-Mails immer bekommen möchte, z.B. das eigene Adressbuch
  • Blacklist: Listen von Spammer-E-Mail-Adressen
  • Distributed Checksum Clearinghouse: Für jede E-Mail wird eine Prüfsumme generiert und an einen zentralen Server geschickt. Ist diese E-Mail bereits woanders als SPAM-Mail registriert worden, dann wird sie auch lokal als SPAM-Mail behandelt