Theorem von Bayes/Beispiel: Spam Mail filtering: Unterschied zwischen den Versionen

Aus MM*Stat

Wechseln zu: Navigation, Suche
(Lernende Naive Bayes Filter)
(Beispiel: E-Mail filtering)
 
(Eine dazwischenliegende Version desselben Benutzers wird nicht angezeigt)
Zeile 1: Zeile 1:
 
== Beispiel: E-Mail filtering ==
 
== Beispiel: E-Mail filtering ==
https://de.wikipedia.org/wiki/Satz_von_Bayes
+
<div style="float:right;width:300px;font-size:x-small">
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.
+
[[File:Spam_2.jpg|300px]]
 +
<center>Quelle: [https://commons.wikimedia.org/wiki/File:Spam_2.jpg Wikimedia Commons]</center>
 +
SPAM war ursprünglich ein Markenname für Dosenfleisch. Während der Rationierung in Großbritannien im 2. Weltkrieg war Spam eines der wenigen Nahrungsmittel, die praktisch überall und unbeschränkt erhältlich waren. Die Omnipräsenz dieses Fleisches, ähnlich wie später die unerwünschten E-Mails, förderte die Entwicklung des Begriffs. Mit HAM (= Schinken) wird demzufolge auch erwünschte E-Mail bezeichnet.
 +
</div>
 +
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, wie die folgende, zu erkennen ist der Naive-Bayes-Filter.
  
 
<center>
 
<center>
{| width="70%" style="border-style:solid; border-width:1px; border-color:gray; padding: 4px;"
+
{| width="60%" style="border-style:solid; border-width:1px; border-color:gray; padding: 4px;"
 
| <i>Deutscher Strassenpenner wurde zum Superreichen mit einem Vermögen von 82.000.000 Euro (Mio. Euro) ...und das in nur einem Jahr!
 
| <i>Deutscher Strassenpenner wurde zum Superreichen mit einem Vermögen von 82.000.000 Euro (Mio. Euro) ...und das in nur einem Jahr!
  

Aktuelle Version vom 5. Juli 2020, 07:13 Uhr

Beispiel: E-Mail filtering

Spam 2.jpg

Quelle: Wikimedia Commons

SPAM war ursprünglich ein Markenname für Dosenfleisch. Während der Rationierung in Großbritannien im 2. Weltkrieg war Spam eines der wenigen Nahrungsmittel, die praktisch überall und unbeschränkt erhältlich waren. Die Omnipräsenz dieses Fleisches, ähnlich wie später die unerwünschten E-Mails, förderte die Entwicklung des Begriffs. Mit HAM (= Schinken) wird demzufolge auch erwünschte E-Mail bezeichnet.

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, wie die folgende, zu erkennen ist der Naive-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 SPAM-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