Bayes-Klassifikator

Ein Bayes-Klassifikator (IPA: [ˈbɛɪ̯z.klasifiˌkaːtoːɐ̯], anhören^ⓘ, 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. Formal handelt es sich um eine mathematische Funktion, die jedem Punkt eines Merkmalsraums eine Klasse zuordnet.

Bayes-Klassifikatoren sind Beispiele für Bayessche Netze.

Definition

Ein Bayes-Klassifikator ${\hat {c}}^{\text{Bayes}}$ ist eine Funktion, die Feature-Vektoren aus dem $f$-dimensionalen reellwertigen Merkmalsraum auf eine Menge von Klassen $C$ abbildet:

${\hat {c}}^{\text{Bayes}}\colon \mathbb {R} ^{f}\rightarrow C$

Der Bayes-Klassifikator weist einem Feature-Vektor diejenige Klasse zu, deren A-posteriori-Wahrscheinlichkeit (beim vorliegenden Feature Vektor) maximal ist:

${\hat {c}}^{\text{Bayes}}(f_{1},\dots f_{n})=\arg \max _{c}p(C=c|f_{1},\dots f_{n})=\arg \max _{c}{\frac {p(C=c)p(f_{1},\dots f_{n}|C=c)}{p(f_{1},\dots f_{n})}}\propto \arg \max _{c}p(C=c)p(f_{1},\dots f_{n}|C=c),$

wobei $p(C=c)$ die apriori Auftrittswahrscheinlichkeit der Klasse $c$ ist und $p(f_{1},\dots f_{n}|C=c)$ die bedingte Auftrittswahrscheinlichkeit der Features $f_{1},\dots f_{n}$ für die gegebene Klasse. Die apriori Auftrittswahrscheinlichkeit der Klasse $c$ kann zum Beispiel durch die Auftrittshäufigkeit der Klasse im Trainingsdatensatz geschätzt werden.

Beide Formen (Naiver Bayes-Klassifikator und Bayes-Klassifikator) 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.

Naiver Bayes-Klassifikator

Beispiel eines Naiven Bayes-Klassifikators, welcher als Bayessches Netz dargestellt ist

Der Naive Bayes-Klassifikator nimmt (in naiver Weise) an, dass die A-posteriori-Verteilung aus Wahrscheinlichkeiten aufgebaut ist, bei denen (bei gegebener Klasse) die Features unabhängig voneinander sind:

${\hat {c}}^{\text{Bayes}}(f_{1},\dots f_{n})=\arg \max _{c}p(C=c|f_{1},\dots f_{n})\propto \arg \max _{c}p(C=c)\prod _{i=1}^{n}p(f_{i}|C=c)$

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.

Klassifizierung bei normalverteilten Features

Die Entscheidungsgrenze enthält beim Bayes-Klassifikator diejenigen Punkte mit gleicher A-posteriori-Wahrscheinlichkeit (je benachbarter Klasse). Wird angenommen, dass die bedingten Wahrscheinlichkeiten $p(X|C=c)\sim {\mathcal {N}}(\mu _{c},\sigma _{c})$ Normalverteilungen sind, so ist die aus dem Bayes-Klassifikator resultierende Entscheidungsgrenze 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. Soll ein Gaussian Bayes-Klassifikator eingesetzt werden, so sollten die Features zum Beispiel mit der Yeo-Johnson-Transformation präprozessiert werden um sie möglichst normalverteilt zu machen.

Herleitung

Um den Bayes-Klassifikator herzuleiten, 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, siehe auch Empirische Risikominimierung.

Wird ein primitives Kostenmaß verwendet, das ausschließlich bei Fehlentscheidungen Kosten verursacht, so minimiert der Bayes-Klassifikator die Wahrscheinlichkeit einer Fehlentscheidung. Typischerweise wird als Kostenmaß die folgende 0-1 Verlustfunktion gewählt:

$L(x,y)=1-\delta _{x,y}={\begin{cases}0&{\text{if }}x=y\\1&{\text{if }}x\neq y\end{cases}},$

wobei $\delta _{x,y}$ das Kronecker-Delta ist.

Der erwartete Fehler (also die Risikofunktion) ist dann der Bayes Fehler (EPE):

$EPE=E_{x}[\sum _{c\in \{c\}}L(c,{\hat {c}}(x))P(C=c|x)]$

wobei x ein Feature-Vektor, $E[]$ der Erwartungswert, c ist eine Klasse, P(C=c|x) ist die bedingte Wahrscheinlichkeit einer Klasse c bei gegebenem Feature-Vektor x.

$EPE=E_{x}\left[\sum _{c\in \{c\}}L(c,{\hat {c}}(x))P(C=c|x)\right]=E_{x}\left[\sum _{c\in \{c\},c\neq {\hat {c}}(x)}P(C=c|x)\right]=E_{x}[1-P(C={\hat {c}}(x)|x)]$,

wobei das letzte Gleichheitszeichen aufgrund der Gegenwahrscheinlichkeit gilt. Diese Verlustfunktion EPE ist minimal, falls $P(C={\hat {c}}(x)|x)$ maximal ist (was durch die Definition des Bayes-Klassifikator gewährleistet wird).

Man sagt dann, der Bayes-Klassifikator sei über das Maximum-a-posteriori-Kriterium definiert.

Anwendungen

Ein Beispiel für eine praktische Anwendung eines Bayes-Klassifikator ist der Bayes-Spamfilter.

Der Bayes-Klassifikator auch häufig 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 (und dann nur der irreduzible Bayes-Fehler vorliegt), 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.