Bayes-Klassifikator

Ein Bayes-Klassifikator (Aussprache: [bɛi:z], benannt nach dem englischen Mathematiker Thomas Bayes), ist ein aus dem Bayestheorem hergeleiteter Klassifikator. Er ordnet jedes Objekt der Klasse zu, zu der es mit der größten Wahrscheinlichkeit gehört, oder bei der durch die Einordnung die wenigsten Kosten entstehen. Genau genommen handelt es sich um eine mathematische Funktion, die jedem Punkt eines Merkmalsraums eine Klasse zuordnet.

Um den Bayes-Klassifikator zu definieren, wird ein Kostenmaß benötigt, das jeder möglichen Klassifizierung Kosten zuweist. Der Bayes-Klassifikator ist genau derjenige Klassifikator, der die durch alle Klassifizierungen entstehenden Kosten minimiert. Das Kostenmaß wird gelegentlich auch Risikofunktion genannt; man sagt dann, der Bayes-Klassifikator minimiere das Risiko einer Fehlentscheidung und sei über das minimum-risk-Kriterium definiert.

Wird ein primitives Kostenmaß verwendet, das ausschließlich bei Fehlentscheidungen Kosten verursacht, so minimiert der Bayes-Klassifikator die Wahrscheinlichkeit einer Fehlentscheidung. Man sagt dann, er sei über das Maximum-a-posteriori-Kriterium definiert.

Beide Formen setzen voraus, dass die Wahrscheinlichkeit, dass ein Punkt des Merkmalsraums zu einer bestimmten Klasse gehört, bekannt ist, jede Klasse also durch eine Wahrscheinlichkeitsdichte beschrieben wird. In der Realität sind diese Dichtefunktionen aber nicht bekannt; man muss sie abschätzen. Dazu vermutet man hinter jeder Klasse einen Typ von Wahrscheinlichkeitsverteilung - in der Regel eine Normalverteilung - und versucht anhand der vorhandenen Daten, deren Parameter abzuschätzen.

Weit häufiger wird der Bayes-Klassifikator jedoch zur Beurteilung anderer Klassifikatoren verwendet: Man entwirft künstlich einige Klassen und deren Wahrscheinlichkeitsdichten, erzeugt mit diesem Modell eine zufällige Stichprobe und lässt den anderen Klassifikator die Objekte dieser Stichprobe in Klassen einteilen. Das Ergebnis vergleicht man mit der Einordnung, die der Bayes-Klassifikator vorgenommen hätte. Da der Bayes-Klassifikator in diesem Fall optimal ist, erhält man eine Abschätzung, wie nahe der andere Klassifikator am Optimum liegt. Gleichzeitig liefert der Bayes-Klassifikator eine untere Schranke für die Fehlerwahrscheinlichkeit aller anderen Klassifikatoren in diesem Szenario; besser als der optimale Bayes-Klassifikator können diese nicht werden.

Naiver Bayes-Klassifikator

Aufgrund seiner schnellen Berechenbarkeit bei guter Erkennungsrate sehr beliebt ist auch der Naive Bayes-Klassifikator. Mittels des naiven Bayes-Klassifikators ist es möglich, die Zugehörigkeit eines Objektes (Klassenattribut) zu einer Klasse zu bestimmen. Er basiert auf dem Bayesschen Theorem. Man könnte einen naiven Bayes-Klassifikator auch als sternförmiges Bayessches Netz betrachten.

Grundannahme ist dabei, dass jedes Attribut nur vom Klassenattribut abhängt. Obwohl dies in der Realität selten zutrifft, erzielen naive Bayes-Klassifikatoren bei praktischen Anwendungen häufig gute Ergebnisse, solang die Attribute nicht zu stark korreliert sind.

Für den Fall starker Abhängigkeiten zwischen den Attributen ist eine Erweiterung des naiven Bayes-Klassifikators um einen Baum zwischen den Attributen sinnvoll. Das Ergebnis wird baumerweiterter naiver Bayes-Klassifikator genannt.

Mathematische Definition

Ein Bayes-Klassifikator b ist eine Funktion, die Vektoren aus dem f-dimensionalen reellwertigen Merkmalsraum auf eine Menge von Klassen C abbildet:

$b: \mathbb{R}^{f} \rightarrow C$

Für gewöhnlich gilt $C := \left\{ 0, 1 \right\}$ oder $C := \left\{-1, +1\right\}$ für den Fall, dass zwei Klassen betrachtet werden oder $C := \left\{1, \ldots, c\right\}$, falls $c \geq 3$ Klassen betrachtet werden.

Klassifizierung bei normalverteilten Klassen

Werden zwei Klassen durch Normalverteilungen beschrieben, so ist die aus dem Bayes-Klassifikator resultierende Entscheidungsgrenze dazwischen quadratisch. Werden die Normalverteilungen darüber hinaus durch die gleiche Kovarianzmatrix beschrieben, ist die dazwischen liegende Entscheidungsgrenze sogar linear. In diesen beiden Fällen lässt sich die Diskriminanzfunktion besonders einfach beschreiben, was die Klassifikation einfach und effizient berechenbar macht.

Beispiel

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

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

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

Für die Wahrscheinlichkeit P(Spam | W) gilt nach dem Theorem von Bayes:

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

Die Wahrscheinlichkeit, dass die E-Mail W auftritt, also P(W), lässt sich jedoch nicht schätzen, denn in der Regel tritt jede E-Mail nur einmal auf. Daher betrachten die E-Mail-Programme den Ausdruck

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

und ist Q größer als 1, dann klassifizieren wir die E-Mail als Spam, sonst als Nicht-Spam. Die Wahrscheinlichkeit, dass überhaupt eine E-Mail Spam bzw. Nicht-Spam ist, können wir wieder aus den alten E-Mails schätzen:

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

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

Besteht die E-Mail W aus den Wörtern W₁, ... W_n und treten diese Wörter unabhängig voneinander auf, so gilt

$P(W|Spam)=P(W_1 \cap ... \cap W_n|Spam) = P(W_1|Spam) ... P(W_n|Spam)$.

Die Wahrscheinlichkeit P(W_i | Spam) ist oben bereits angegeben worden und damit kann der Gesamtquotient berechnet werden:

$Q=\frac{P(Spam|W)}{P(\overline{Spam}|W)}=\frac{P(W_1|Spam)...P(W_n|Spam)P(Spam)}{P(W_1|\overline{Spam})...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 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 daran, 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 P(W_i | Spam), P(Spam) usw. ändern.
3. Obwohl die mathematisch-statistische Theorie die Unabhängigkeit der Wörter 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 $P(Spam|W)\,$ und $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.

Einzelnachweise

1. ↑ A. Linke (2003) Spam oder nicht Spam? E-Mail sortieren mit Bayes Filtern, c't 17/2003, S. 150