Bayes-Klassifikator

Grundidee und Definition

Ein Bayes-Klassifikator ist ein aus dem Satz von Bayes hergeleiteter Klassifikator. Er ordnet jedem Objekt die Klasse zu, zu der es mit der größten Wahrscheinlichkeit gehört, oder wählt bei unterschiedlichen Fehlentscheidungskosten die Einordnung mit den geringsten erwarteten Kosten. Formal ist er eine Funktion, die jeden Punkt eines Merkmalsraums einer Klasse zuweist. Bayes-Klassifikatoren sind Beispiele für Bayessche Netze.

Ein Feature-Vektor beschreibt ein Objekt durch mehrere messbare Merkmale, die Features. Für einen f-dimensionalen reellwertigen Merkmalsraum und eine Klassenmenge C lautet die Abbildung:

ĉ^Bayes: ℝ^f → C

Der Klassifikator wählt die Klasse mit der größten A-posteriori-Wahrscheinlichkeit, also mit der höchsten Wahrscheinlichkeit nach Berücksichtigung der beobachteten Features:

ĉ^Bayes(f₁,…,fₙ) = arg max_c p(C=c | f₁,…,fₙ) = arg max_c [p(C=c)p(f₁,…,fₙ | C=c) / p(f₁,…,fₙ)] ∝ arg max_c p(C=c)p(f₁,…,fₙ | C=c).

Dabei ist p(C=c) die A-priori-Wahrscheinlichkeit der Klasse c, also ihre Wahrscheinlichkeit vor Betrachtung der Features. Sie kann beispielsweise anhand der Häufigkeit der Klasse im Trainingsdatensatz geschätzt werden. p(f₁,…,fₙ | C=c) ist die bedingte Wahrscheinlichkeit, die beobachteten Features bei gegebener Klasse c anzutreffen. Der Nenner p(f₁,…,fₙ) ist für alle verglichenen Klassen gleich und beeinflusst deshalb die Wahl des Maximums nicht.

Der Bayes-Klassifikator setzt voraus, dass die Wahrscheinlichkeitsdichte jeder Klasse bekannt ist. In realen Aufgaben sind diese Dichtefunktionen meist unbekannt und müssen aus Daten geschätzt werden. Dazu nimmt man für jede Klasse einen Verteilungstyp an, in der Regel eine Normalverteilung, und bestimmt dessen Parameter aus den vorhandenen Daten.

Entscheidung als Kostenminimierung

Zur Herleitung wird ein Kostenmaß benötigt, das jeder möglichen Klassifizierung Kosten zuweist. Dieses Maß heißt auch Verlustfunktion oder Risikofunktion. Der Bayes-Klassifikator minimiert die erwarteten Kosten aller Klassifizierungen und damit das Risiko einer Fehlentscheidung. Er ist in diesem Sinn durch das Minimum-Risk-Kriterium definiert.

Wenn nur falsche Entscheidungen Kosten verursachen, minimiert der Bayes-Klassifikator die Wahrscheinlichkeit einer Fehlklassifikation. Typisch ist die 0-1-Verlustfunktion:

L(x,y) = 1 − δₓ,ᵧ = {0, falls x=y; 1, falls x≠y}.

δₓ,ᵧ bezeichnet das Kronecker-Delta. Eine richtige Klassifikation hat somit den Verlust 0, eine falsche den Verlust 1.

Der erwartete Fehler beziehungsweise Bayes-Fehler (EPE) ist:

EPE = Eₓ[∑_c L(c, ĉ(x))P(C=c | x)].

Dabei ist x ein Feature-Vektor, E der Erwartungswert, c eine Klasse und P(C=c | x) die bedingte Wahrscheinlichkeit der Klasse c beim gegebenen Vektor x. Für die 0-1-Verlustfunktion lässt sich dies umformen zu:

EPE = Eₓ[∑_{c≠ĉ(x)} P(C=c | x)] = Eₓ[1 − P(C=ĉ(x) | x)].

Wegen der Gegenwahrscheinlichkeit wird der erwartete Fehler genau dann minimal, wenn P(C=ĉ(x) | x) maximal ist. Deshalb wählt der Bayes-Klassifikator die Klasse mit der höchsten A-posteriori-Wahrscheinlichkeit. Diese Entscheidungsregel heißt Maximum-a-posteriori-Kriterium.

Naiver Bayes-Klassifikator

Der naive Bayes-Klassifikator vereinfacht die Berechnung durch die Annahme, dass die Features bei gegebener Klasse voneinander unabhängig sind. Dann zerfällt ihre gemeinsame bedingte Wahrscheinlichkeit in ein Produkt:

ĉ^Bayes(f₁,…,fₙ) = arg max_c p(C=c | f₁,…,fₙ) ∝ arg max_c p(C=c) ∏_{i=1}^n p(fᵢ | C=c).

Anschaulich hängt nach dieser Annahme jedes Attribut nur vom Klassenattribut ab. Der Klassifikator kann deshalb als sternförmiges Bayessches Netz dargestellt werden: Die Klasse steht im Zentrum und ist mit allen Features verbunden.

Die Unabhängigkeitsannahme trifft in der Realität nur selten vollständig zu. Trotzdem liefern naive Bayes-Klassifikatoren in praktischen Anwendungen häufig gute Ergebnisse, solange die Attribute nicht zu stark korreliert sind, also nicht zu eng miteinander zusammenhängen. Ihre Vorteile sind die schnelle Berechenbarkeit und eine häufig gute Erkennungsrate.

Bei starken Abhängigkeiten zwischen den Attributen kann das Modell um einen Baum aus Abhängigkeiten zwischen den Attributen erweitert werden. Diese Variante heißt baumerweiterter naiver Bayes-Klassifikator.

Normalverteilte Features und Entscheidungsgrenzen

Eine Entscheidungsgrenze trennt die Bereiche des Merkmalsraums, die verschiedenen Klassen zugeordnet werden. Beim Bayes-Klassifikator enthält sie die Punkte, an denen jeweils benachbarte Klassen dieselbe A-posteriori-Wahrscheinlichkeit besitzen.

Wird für die bedingten Wahrscheinlichkeiten eine Normalverteilung angenommen,

p(X | C=c) ∼ 𝒩(μ_c, σ_c),

so ist die resultierende Entscheidungsgrenze quadratisch. Werden die Normalverteilungen aller Klassen zusätzlich durch dieselbe Kovarianzmatrix beschrieben, ist die Entscheidungsgrenze linear. Die Kovarianzmatrix beschreibt dabei die Streuungen der Features und ihre gemeinsamen Abhängigkeiten. In beiden Fällen lässt sich die Diskriminanzfunktion, also die für den Klassenvergleich verwendete Entscheidungsfunktion, besonders einfach darstellen. Dadurch ist die Klassifikation effizient berechenbar.

Vor dem Einsatz eines Gaußschen Bayes-Klassifikators sollten die Features beispielsweise mit der Yeo-Johnson-Transformation vorverarbeitet werden, damit sie möglichst normalverteilt sind.

Anwendungen und Bewertung anderer Klassifikatoren

Eine praktische Anwendung ist der Bayes-Spamfilter, der Nachrichten anhand ihrer Merkmale einer Klasse wie Spam oder Nicht-Spam zuordnet.

Der Bayes-Klassifikator wird außerdem häufig als Vergleichsmaßstab für andere Klassifikatoren eingesetzt. Dazu werden künstliche Klassen und ihre Wahrscheinlichkeitsdichten festgelegt. Aus diesem Modell erzeugt man eine zufällige Stichprobe und lässt einen anderen Klassifikator deren Objekte einordnen. Anschließend vergleicht man seine Entscheidungen mit denen des Bayes-Klassifikators.

Da der Bayes-Klassifikator bei vollständig bekanntem Modell optimal ist, bleibt in diesem Fall nur der irreduzible Bayes-Fehler, also der unvermeidbare Fehler aufgrund überlappender Klassenwahrscheinlichkeiten. Der Vergleich zeigt, wie nahe ein anderer Klassifikator am erreichbaren Optimum liegt. Zugleich bildet der Bayes-Klassifikator in diesem Szenario eine untere Schranke für die Fehlerwahrscheinlichkeit aller anderen Klassifikatoren: Kein anderer Klassifikator kann eine geringere Fehlerwahrscheinlichkeit als der optimale Bayes-Klassifikator erreichen.