Bayes-Spamfilter

26.05.2025

Der Bayes-Spamfilter ist ein statistischer Filter, der versucht, E-Mails oder Kommentare (allgemein: Texte) auf Basis von Wahrscheinlichkeiten als erwünscht (Ham) oder unerwünscht (Spam) zu klassifizieren. Die Basis hierfür sind bekannte Daten (Texte), die der Anwender im Vorfeld als erwünscht bzw. unerwünscht klassifiziert hat. In dieser Lernphase extrahiert der Filter aus den Texten Wörter, die charakteristisch für Ham oder Spam sind. Der Filter ist danach in der Lage, neue Texte aufgrund des Vorkommens dieser Wörter als Spam zu erkennen.

Die Mathematik dahinter

Der Satz von Bayes ist ein mathematischer Satz aus der Wahrscheinlichkeitsrechung, der für die Berechnung bedingter Wahrscheinlichkeiten verwendet wird. Mit dem Satz wird die Wahrscheinlichkeit eines Ereignisses A berechnet unter der Bedingung, dass vorher ein Ereignis B eingetreten ist.

Der Satz lautet:

P(A|B) = \frac{P(B|A) \cdot P(A)}{P(B)}

Dabei ist

P(A|B) die bedingte Wahrscheinlichkeit des Ereignisses A unter der Voraussetzung, dass vorher das Ereignis B eingetreten ist,
P(B|A) die bedingte Wahrscheinlichkeit des Ereignisses B unter der Voraussetzung, dass vorher das Ereignis A eingetreten ist,
P(A) die à-priori-Wahrscheinlichkeit des Ereignisses A und
P(B) die à-priori-Wahrscheinlichkeit des Ereignisses B.

Übertragen wir das auf die Spam-Erkennung: die Wahrscheinlichkeit, dass es sich um Spam handelt, falls im Text das Wort W vorkommt (das ist das, was uns interessiert) ist

P(S|W) = \frac{P(W|S) \cdot P(S)}{P(W)}

Gleichermaßen gilt für die Wahrscheinlichkeit, dass es sich um Ham handelt, falls in dem Text das Wort W vorkommt (auch das interessiert uns), die Gleichung

P(H|W) = \frac{P(W|H) \cdot P(H)}{P(W)}

Für einen neuen Text W muss die Frage beantwortet werden, ob die Wahrscheinlichkeit P(S|W) größer ist als die Wahrscheinlichkeit P(H|W). Wenn also

P(S|W) > P(S|H)

ist, wird W als Spam klassifiziert, andernfalls als Ham. Alternativ zum Größenvergleich kann auch der Quotient

Q = \frac{P(S|W)}{P(H|W)} = \frac{\frac{P(W|S) \cdot P(S)}{P(W)}}{\frac{P(W|H) \cdot P(H)}{P(W)}} = \frac{P(W|S) \cdot P(S)}{P(W)} \cdot \frac{P(W)}{P(W|H) \cdot P(H)} = \frac{P(W|S) \cdot P(S)}{P(W|H) \cdot P(H)}

berechnet werden, was - wie wir später sehen werden - bei der Implementierung ein paar Vorteile bringt. Ist Q > 1, wird der Text als Spam klassifiziert, ansonsten als Ham.

Der Text W besteht aus den Wörtern w_i. Sei N_S die Anzahl der Spam-Texte, N_H die Anzahl der Ham-Texte, N_S,i die Anzahl der Spam-Texte, die das Wort w_i enthalten, und N_H,i die Anzahl der Ham-Texte, die das Wort w_i enthalten. Dann gilt:

P(S) = \frac{N_{S}}{N_{S} + N_{H}}

P(H) = \frac{N_{H}}{N_{S} + N_{H}}

P(w_{i} |S) = \frac{N_{S,i}}{N_{S}}

P(w_{i} |H) = \frac{N_{H,i}}{N_{H}}

Wir treffen hier die Annahme, dass diese Wörter unabhängig voneinander sind. Das ist in echten Texten nicht der Fall: auf das Wort "Nordrhein" folgt mit großer Wahrscheinlichkeit "Westfalen". Beim "naiven" Bayes-Spamfilter, dessen Implementierung ich hier vorstelle, wird dieser Zusammenhang aber vernachlässigt. Daher gelten die Wörter w_i als stochastisch unabhängig voneinander, und die Gesamtwahrscheinlichkeit ergibt sich aus dem Produkt der Einzelwahrscheinlichkeiten, also

P(W|S) = P(w_{1}, w_{2}, ... , w_{n} |S) = P(w_{1} |S) \cdot P(w_{2} |S) \cdot ... \cdot P(w_{n} |S) = \prod_{i = 1}^{n} P(w_{i} |S) = \prod_{i = 1}^{n} \frac{N_{S,i}}{N_{S}}

und

P(W|H) = P(w_{1}, w_{2}, ... , w_{n} |H) = P(w_{1} |H) \cdot P(w_{2} |H) \cdot ... \cdot P(w_{n} |H) = \prod_{i = 1}^{n} P(w_{i} |H) = \prod_{i = 1}^{n} \frac{N_{H,i}}{N_{H}}

Damit haben wir auf den rechten Seiten der Gleichungen

P(S|W) = \frac{P(W|S) \cdot P(S)}{P(W)}

und

P(S|H) = \frac{P(W|H) \cdot P(H)}{P(W)}

von ganz oben nur noch Ausdrücke, deren Werte aus der Lernphase bekannt sind und daher berechnet werden können. Bei der Ermittlung der Wahrscheinlichkeiten und des anschließenden Vergleichs kann der Term P(W) ignoriert werden, da er in beiden Gleichungen vorkommt. Bei der Berechnung des Quotienten fällt P(W) durch Kürzen raus.

Wir könnten jetzt sofort mit der Berechnung beginnen, müssen vorher aber noch zwei Probleme lösen.

Glättung

Es kann vorkommen, dass ein Wort w_i in der Lernphase zwar in einem Ham-Text, nicht aber in einem Spam-Text vorgekommen ist, dass also N_S,i = 0 ist. Damit ist auch P(w_i|S) = 0, und die Gesamtwahrscheinlichkeit P(W|S) für Spam wird ebenfalls Null. Die Idee, dieses Wort einfach von der Berechnung auszuschließen, hätte den gegenteiligen Effekt: P(W|S) wird dadurch größer, als es sein soll.

Die Lösung für dieses Problem ist, die Wahrscheinlichkeit für ein Wort nie Null werden zu lassen, indem man sie nach oben glättet. Wir beginnen jede Wortzählung also mit 1 anstatt mit 0. Dadurch wird in

P(w_{i} |S) = \frac{N_{S,i}}{N_{S}}

der Zähler immer > 0. Allerdings wird dann die Wahrscheinlichkeit für dieses Wort überschätzt, was durch Addition von 2 zum Nenner korrigiert wird. Die 2 deswegen, weil wir zwei Dinge im Auge behalten müssen: die Anzahl der Texte, die das Wort enthalten, und die Anzahl der Texte, die das Wort nicht enthalten. DIe Summe dieser beiden sollte im Nenner stehen, und durch die Addition von 2 wird das erreicht.

Nutzung von Logarithmen

Das Produkt vieler Wahrscheinlichkeiten wird betragsmäßig sehr klein, so dass die Genauigkeit einer Gleitkommanzahl (64 Bit nach IEE 754), insbesondere bei vielen Wörtern im zu analysierenden Text, nicht ausreichend ist. Abhilfe schafft die Verwendung von Logarithmen. Hierfür müssen die Formeln erweitert werden.

Nach den Logarithmengesetzen ist der Logarithmus des Produkts zweier Zahlen die Summe der Logarithmen dieser Zahlen. Analog ist der Logarithmus des Quotienten zweier Zahlen die Differenz der Logarithmen dieser Zahlen, also

ln(a \cdot b) = ln(a) + ln(b)

und

ln(\frac{a}{b}) = ln(a) - ln(b)

Ausgehend von

Q = \frac{P(W|S) \cdot P(S)}{P(W|H) \cdot P(H)} = \frac{\prod_{i = 1}^{n} \frac{N_{S,i}}{N_{S}} \cdot \frac{N_{S}}{N_{S} + N_{H}}}{\prod_{i = 1}^{n} \frac{N_{H,i}}{N_{H}} \cdot \frac{N_{H}}{N_{S} + N_{H}}} = \prod_{i = 1}^{n - 1} \frac{N_{H}}{N_{S}} \cdot \prod_{i = 1}^{n} \frac{N_{S,i}}{N_{H,i}}

bilden wir auf beiden Seiten den natürlichen Logarithmus und erhalten

ln(Q) = \sum_{i = 1}^{n - 1} \frac{N_{H}}{N_{S}} + \sum_{i = 1}^{n} \frac{N_{S,i}}{N_{H,i}}

Die Brüche werden ebenfalls umgeformt, und wir erhalten

ln(Q) = (n - 1) (ln(N_{H}) - (ln(N_{S})) + \sum_{i = 1}^{n} ln(N_{S,i}) - \sum_{i = 1}^{n} ln(N_{H,i})

Falls ln(Q) > 0, wird der Text als Spam klassifiziert, ansonsten als Ham.

Implementierung

In der Lernphase wird der Filter mit bekannten Ham- und Spam-Texten trainiert. Das Ergebnis dieser Analysen fließt in zwei Datenbank-Tabellen ein, die unten beschrieben sind. Die Trainingstexte werden dazu in einzelne Wörter (Token) zerlegt, deren Häufigkeit in Ham- bzw. Spam-Texten gespeichert werden.

Datenbank-Tabellen

Die Tabelle bayesfilter_message zählt in den Spalten ham bzw. spam die Anzahl der Ham- bzw. Spam-Texte. Vor der ersten Verwendung wird die Tabelle initialisiert.

  create table bayesfilter_message (
    spam int,
    ham  int
  );

  insert into bayesfilter_message values (0, 0);

Die Tabelle bayesfilter_word zählt für jedes Wort, in wievielen Ham- bzw. Spam-Texten dieses Wort vorkommt.

  create table bayesfilter_word (
    word varchar(255) collate utf8_bin primary key,
    spam int,
    ham  int
  );

Das Attribut collate utf8_bin wird benötigt, damit MySQL zwischen Groß- und Kleinbuchstaben unterscheiden kann.

Text in Wörter zerlegen

Zur Trennung des Textes in einzelne Wörter werden Leerzeichen, Tabulatoren, Zeilenumbrüche, Punkte, Kommata, Semikola und Doppelpunkte als Trennzeichen betrachtet. Doppelt vorkommende Wörter und leere Einträge werden entfernt. Die Funktion prepareMessage() hat als Parameter den zu zerlegenden Text und liefert ein Array mit den einzelnen Wörtern.

  function prepareMessage($s)
  {
    // Text trennen
    $a = preg_split("/[\s.,;:]+/", $s);
    // doppelte Einträge entfernen
    $a = array_unique($a);
    // leere Wörter entfernrn
    foreach ($a as $k => $v) {
      if ($v == "") {
        unset($a[$k]);
      }
    }
    return $a;
  } // prepareMessage

Spam und Ham eintragen

Wenn ein Text als Spam bzw. Ham eingetragen werden soll, wird er zuerst in einzelne Wörter zerlegt. Für jedes Wort wird in der Tabelle bayesfilter_word der Zähler für Spam bzw. Ham um eins erhöht. Wenn das Wort noch nicht vorhanden ist, wird eine Zeile in der Tabelle eingefügt. Am Ende wird noch der Zähler für Spam bzw. Ham in der Tabelle bayesfilter_message um eins erhöht.

  function addSpam($s)
  {
    $words = prepareMessage($s);

    $pdo = new PDO(...);
    $stmt = $pdo->prepare("start transaction");
    $stmt->execute();

    $stmt = $pdo->prepare("insert into bayesfilter_word (word, spam, ham)
                             values (:word, 1, 0)
                             on duplicate key update spam = spam + 1");

    foreach ($words as $word) {
      $stmt->execute(array("word" => $word));
    }

    $stmt = $pdo->prepare("update bayesfilter_message
                              set spam = spam + 1");
    $stmt->execute();

    $stmt = $pdo->prepare("commit");
    $stmt->execute();

    return;
  } // addSpam

  function addHam($s)
  {
    $words = prepareMessage($s);

    $pdo = new PDO(...);
    $stmt = $pdo->prepare("start transaction");
    $stmt->execute();

    $stmt = $pdo->prepare("insert into bayesfilter_word (word, spam, ham)
                             values (:word, 0, 1)
                             on duplicate key update ham = ham + 1");

    foreach ($words as $word) {
      $stmt->execute(array("word" => $word));
    }

    $stmt = $pdo->prepare("update bayesfilter_message
                              set ham = ham + 1");
    $stmt->execute();

    $stmt = $pdo->prepare("commit");
    $stmt->execute();

    return;
  } // addHam

Spam und Ham entfernen

Es kann vorkommen, dass in der Lernphase ein Text versehentlich in die falsche Kategorie aufgenommen wurde. Die Funktionen removeSpam() und removeHam() korrigieren die Zähler für einen falsch kategorisierten Text und rechnen ihn damit wieder aus der Statistik heraus.

Dafür wird der Text wieder in einzelne Wörter zerlegt. Falls das jeweilige Wort in der Tabelle bayesfilter_word vorhanden ist und der Zähler für Spam bzw. Ham größer als Null ist, wird der entsprechende Zähler um eins vermindert. Haben danach beide Zähler den Wert Null, wird das Wort aus der Tabelle gelöscht. Am Ende wird noch der Zähler für Spam bzw. Ham in der Tabelle bayesfilter_message um eins vermindert.

  function removeSpam($s)
  {
    $words = prepareMessage($s);

    $pdo = new PDO(...);
    $stmt = $pdo->prepare("start transaction");
    $stmt->execute();

    $stmt = $pdo->prepare("update bayesfilter_word
                              set spam = spam - 1
                            where word = :word
                              and spam > 0");

    foreach ($words as $word) {
      $stmt->execute(array("word" => $word));
    }

    $stmt = $pdo->prepare("delete from bayesfilter_word
                            where ham = 0 and spam = 0");
    $stmt->execute();

    $stmt = $pdo->prepare("update bayesfilter_message
                              set spam = spam - 1
                            where spam > 0");
    $stmt->execute();

    $stmt = $pdo->prepare("commit");
    $stmt->execute();

    return;
  } // removeSpam

  function removeHam($s)
  {
    $words = prepareMessage($s);

    $pdo = new PDO(...);
    $stmt = $pdo->prepare("start transaction");
    $stmt->execute();

    $stmt = $pdo->prepare("update bayesfilter_word
                              set ham = ham - 1
                            where word = :word
                              and ham > 0");

    foreach ($words as $word) {
      $stmt->execute(array("word" => $word));
    }

    $stmt = $pdo->prepare("delete from bayesfilter_word
                            where ham = 0 and spam = 0");
    $stmt->execute();

    $stmt = $pdo->prepare("update bayesfilter_message
                              set ham = ham - 1
                            where ham > 0");
    $stmt->execute();

    $stmt = $pdo->prepare("commit");
    $stmt->execute();

    return;
  } // removeHam

Klassifizierung eines Textes

Wie oben bereits erwähnt gibt es (mindestens) drei Alternativen, wie die Spam-Wahrscheinlichkeit eines Textes berechnet werden kann. Diese drei Alternativen werden nachfolgend vorgestellt.

Out-Of-The-Box-Implementierung

Diese Variante implementiert einfach die Berechnung des Quotienten nach der Formel

Q = \frac{P(W|S) \cdot P(S)}{P(W|H) \cdot P(H)}

Die à-priori-Wahrscheinlichkeiten für Spam und Ham werden in den Variablen $PS und $PH abgelegt. Danach wird für jedes Wort die Wahrscheinlichkeit des Auftretens in Spam- und Ham-Texten berechnet (zur Glättung der Werte siehe oben). Das Gesamtprodukt ist schließlich in den Variablen $PWS und $PWH zu finden. Am Ende der Funktion wird der Quotient berechnet und zurückgegeben.

  public function getRankOOTB($s)
  {
    // Text zerlegen
    $words = prepareMessage($s);
    // Gesamtzahl der Ham- und Spam-Texte ermitteln
    // Variablen initialisieren
    $counter = getMessageCounter();
    $NS = $counter["spam"];
    $NH = $counter["ham"];
    $PS = (1.0 * $NS) / ($NS + $NH);
    $PH = (1.0 * $NH) / ($NS + $NH);
    $PWS = 1.0;
    $PWH = 1.0;
    // Für jedes Wort in der Nachricht das Vorkommen in Ham- und Spam-Texten
    // ermitteln und die Wahrscheinlichkeiten multiplizieren
    $pdo = new PDO(...);
    $stmt = $pdo->prepare("select spam,
                                  ham
                             from bayesfilter_word
                            where word = :word");
    foreach ($words as $word) {
      $stmt->execute(array("word" => $word));
      $elem = $stmt->fetch();
      if ($elem) {
        $PWS *= ($elem["spam"] + 1) / ($NS + 2);
        $PWH *= ($elem["ham"] + 1) / ($NH + 2);
      }
    }
    $q = ($PWS * $PS) / ($PWH * $PH);
    return $q;
  } // getRankOOTB

Verwendung von BC Math

Die BC Math-Erweiterung in PHP stellt Funktionen zur Verfügung, die Zahlen beliebiger Länge und Genauigkeit von bis zu 2³¹-1 Dezimalstellen unterstützen. Intern werden die Zahlen als Strings dargestellt. Statt der in PHP eingebauten mathematischen Operationen wie z. B. + oder - werden die entsprechenden BC Math-Funktionen, im Beispiel hier bcadd() und bcsub(), verwendet.

Die BC Math-Variante zur Klassifizierung ist daher mehr oder weniger identisch zu der Funktion oben. Die wesentlichen Unterschiede sind die, dass durch Casts den Variablen String-Typen zugewiesen und die mathematischen Operatoren durch die entsprechenden bcXXX()-Funktionen ersetzt werden. Zusätzlich wird zu Beginn der Berechnung die Genauigkeit durch bcscale() auf 100 Dezimalstellen gesetzt.

  function getRankBCMath($s)
  {
    // Berechnungen mit 100 Dezimalstellen durchführen
    bcscale(100);
    // Text zerlegen
    $words = prepareMessage($s);
    // Gesamtzahl der Ham- und Spam-Nachrichten ermitteln
    // Variablen initialisieren
    $counter = getMessageCounter();
    $NS = (string) $counter["spam"];
    $NH = (string) $counter["ham"];
    $PS = bcdiv($NS, bcadd($NS, $NH));
    $PH = bcdiv($NH, bcadd($NS, $NH));
    $PWS = 1.0;
    $PWH = 1.0;
    // Für jedes Wort in der Nachricht das Vorkommen in Ham- und Spam-
    // Nachrichten ermitteln und die Wahrscheinlichkeiten multiplizieren
    $pdo = new PDO(...);
    $stmt = $pdo->prepare("select spam,
                                  ham
                             from bayesfilter_word
                            where word = :word");
    foreach ($words as $word) {
      $stmt->execute(array("word" => $word));
      $elem = $stmt->fetch();
      if ($elem) {
        $PWS = bcmul($PWS, bcdiv(bcadd($elem["spam"], "1"), bcadd($NS, "2")));
        $PWH = bcmul($PWH, bcdiv(bcadd($elem["ham"], "1"), bcadd($NH, "2")));
      }
    }
    $q = bcdiv(bcmul($PWS, $PS), bcmul($PWH, $PH));
    return $q;
  } // getRankBCMath

Nutzung von Logarithmen

Diese Variante der Berechnung implementiert die Formel

ln(Q) = (n - 1) (ln(N_{H}) - (ln(N_{S})) + \sum_{i = 1}^{n} ln(N_{S,i}) - \sum_{i = 1}^{n} ln(N_{H,i})

Die à-priori-Wahrscheinlichkeiten für Spam und Ham werden hier nicht benötigt. Vielmehr werden die natürlichen Logarithmen der Anzahl der Ham- und Spam-Texte in den Variablen $lnNH und $lnNS abgelegt. Für jedes Wort im Text wird ermittelt, wie oft dieses Wort in Spam- und Ham-Texten vorkommt. Die Logarithmen dieser Werte werden in den Variablen $sumLnNSi und $sumLnNHi aufsummiert. Am Ende der Funktion wird der Quotient nach der Formel oben berechnet und zurückgegeben.

  function getRankLogarithm($s)
  {
    // Text zerlegen
    $words = prepareMessage($s);
    // Gesamtzahl der Ham- und Spam-Nachrichten ermitteln
    // Variablen initialisieren
    $counter = getMessageCounter();
    $lnNH = log($counter["ham"] + 2);
    $lnNS = log($counter["spam"] + 2);
    $sumLnNHi = 0.0;
    $sumLnNSi = 0.0;
    // Für jedes Wort in der Nachricht das Vorkommen in Ham- und Spam-
    // Nachrichten ermitteln in die Logarithmen aufsummieren.
    $pdo = new PDO(...);
    $stmt = $pdo->prepare("select spam,
                                  ham
                             from bayesfilter_word
                            where word = :word");
    foreach ($words as $word) {
      $stmt->execute(array("word" => $word));
      $elem = $stmt->fetch();
      if ($elem) {
        $sumLnNSi += log($elem["spam"] + 1);
        $sumLnNHi += log($elem["ham"] + 1);
      }
    }
    $q = (count($words) - 1) * ($lnNH - $lnNS) + $sumLnNSi - $sumLnNHi;

    return $q;
  } // getRankLogarithm

Die PHP-Fragmente oben enthalten zur besseren Lesbarkeit keine Statements zur Fehlerbehandlung.