Bayes-Klassifikator - LinkFang.de





Bayes-Klassifikator


Dieser Artikel bedarf einer Überarbeitung.
Dieser Artikel oder Abschnitt bedarf einer Überarbeitung.

Ein Bayes-Klassifikator (Aussprache: [beɪz ], benannt nach dem englischen Mathematiker Thomas Bayes), ist ein aus dem Satz von Bayes 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 ist auch der naive Bayes-Klassifikator sehr beliebt. 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.

Die naive 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, solange 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 [math]b[/math] ist eine Funktion, die Vektoren aus dem [math]f[/math]-dimensionalen reellwertigen Merkmalsraum auf eine Menge von Klassen [math]C[/math] abbildet:

[math]b\colon \mathbb{R}^{f} \rightarrow C[/math]

Für gewöhnlich gilt [math]C := \{ 0, 1 \}[/math] oder [math]C := \{-1, +1\}[/math] für den Fall, dass zwei Klassen betrachtet werden, oder [math]C := \{1, \dotsc, c\}[/math], falls [math]c \geq 3[/math] 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 ([math]C = \{Spam, \overline{Spam}\}[/math]). Eine E-Mail besteht dabei aus einzelnen Wörtern [math]W_i[/math]. Aus alten, bereits klassifizierten E-Mails kann man für jedes Wort [math]W_i[/math] die Wahrscheinlichkeit schätzen, dass es in einer Spam- oder Nicht-Spam-E-Mail vorkommt, also:

[math]P(W_i|Spam) = \frac{\text{Anzahl der Spam-E-Mails mit dem Wort } W_i}{\text{Anzahl der Spam-E-Mails}}[/math]
[math]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}}[/math]

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

Für die Wahrscheinlichkeit [math]P(Spam|W)[/math] gilt nach dem Satz von Bayes:

[math]P(Spam|W)=\frac{P(Spam \cap W)}{P(W)}=\frac{P(W|Spam)P(Spam)}{P(W)}[/math].

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

[math]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})}[/math]

und ist [math]Q[/math] 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:

[math]P(Spam) = \frac{\text{Anzahl der Spam-E-Mails}}{\text{Anzahl aller E-Mails}}[/math] und
[math]P(\overline{Spam}) = \frac{\text{Anzahl der Nicht-Spam-E-Mails}}{\text{Anzahl aller E-Mails}}[/math].

Besteht die E-Mail [math]W[/math] aus den Wörtern [math]W_1, \dotsc, W_n[/math] und treten diese Wörter unabhängig voneinander auf, so gilt

[math]P(W|Spam)=P(W_1 \cap \dotsb \cap W_n|Spam) = P(W_1|Spam) \dotsm P(W_n|Spam)[/math].

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

[math]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})}[/math].

Am Schluss noch drei Bemerkungen:

  1. In der Praxis wird eine E-Mail als Spam klassifiziert, wenn beispielsweise [math]Q\gt10[/math] 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 [math]P(W_i|Spam)[/math], [math]P(Spam)[/math] usw. ändern.
  3. Obwohl die mathematisch-statistische Theorie die Unabhängigkeit der Wörter [math]W_i[/math] 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 [math]P(Spam|W)[/math] und [math]P(\overline{Spam}|W)[/math] 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

Kategorien: Klassifikationsverfahren | Bayessche Statistik | Wahrscheinlichkeitsrechnung

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Bayes-Klassifikator (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.