Der Naive Bayes-Algorithmus ist ein probabilistischer Klassifikationsalgorithmus. Puh, schon ein schwieriger Ausdruck. Klassifikationsalgorithmus heißt aber nur, dass der Algorithmus Beobachtungen verschiedenen Klassen zuordnet. Und probabilistisch, dass es mit Wahrscheinlichkeiten zu tun hat. Denn der Naive Bayes-Algorithmus gibt uns für jede Klasse eine Wahrscheinlichkeit, dass die Beobachtung (x1,…,xn) zu dieser Klasse Ki gehört.

Mathematisch ausgedrückt: P(K_i | x_1, \dots, x_n)

Wenn wir genau sind, dann gibt es nicht den Naive Bayes-Algorithmus, sondern das beschreibt eine Klasse von Algorithmen, die alle auf dem gleichen Prinzip beruhen.

So, aber wie funktionieren die Algorithmen nun? Wie der Name vermuten lässt, hat es mit Bayes Theorem zu tun. Ich hole jetzt etwas aus, aber der Satz von Bayes ist wirklich wichtig und nicht so schwer zu verstehen.

Der Satz von Bayes

Bei dem Satz von Bayes geht es um bedingte Wahrscheinlichkeiten, also die Wahrscheinlichkeit eines Ereignisses A, wenn ein Ereignis B eingetreten ist. Man schreibt die Wahrscheinlichkeit dann als P( A | B ).

Der Satz von Bayes sagt: P( A | B ) = \frac{ P(B|A)*P(A) }{P(B)}

Schauen wir uns das mal an einem Beispiel an. Nehmen wir an, wir machen einen medizinischen Test auf eine Krankheit. Der Test hat eine Sensitivität von 98%, d.h. die Wahrscheinlichkeit für ein positives Testergebnis gegeben die Krankheit beträgt 98%. Man sagt dazu auch die True-Positive-Rate. Zudem hat der Test eine Spezifität von 97%, d.h. die Wahrscheinlichkeit für ein negatives Testergebnis unter der Voraussetzung, dass man die Krankheit nicht hat, beträgt 97%. Das nennt man auch die True-Negative-Rate.

Wenn wir jetzt noch wissen, dass die Krankheit bei 1% der Bevölkerung vorkommt, können wir mit Hilfe des Satzes von Bayes ausrechnen, wie wahrscheinlich es ist, dass jemand tatsächlich die Krankheit hat, wenn der Test positiv ausfällt.

Die Wahrscheinlichkeit, krank zu sein, wenn der Test positiv ist, beträgt also nur knapp 25%. Das liegt vor allem an der geringen Wahrscheinlichkeit, überhaupt krank zu sein.

Jetzt kennen wir den Satz von Bayes. Und den wollen wir nutzen. Oben steht ja, dass der Algorithmus P(Ki | x1,…,xn) ausspucken soll. Das könnten wir doch nach dem Satz von Bayes umstellen.

P(K_i | x) = fraq{P(x| K_i) * P(K_i)}{P(x)}

Im Endeffekt interessiert uns nur der Zähler, da er gar nicht von der Klasse abhängt. P(Ki) ist die a priori Wahrscheinlichkeit, also eine Annahme, wie häufig die Klasse vorkommt. Um diese zu bestimmen, zählt man für gewöhnlich das Auftreten der einzelnen Klassen in einem Test-Datensatz. Man kann aber auch eine Gleichverteilung annehmen, d.h. jede Klasse ist a priori gleich wahrscheinlich.

Für den Naive Bayes-Algorithmus brauchen wir jetzt aber noch die zweite Zutat, die Naivität, damit wir weiterkommen.

Warum heißt der Naive Bayes-Algorithmus naiv?

Nein, der Algorithmus ist nicht simpel. Er benutzt einfach nur die „naive“ Annahme der bedingten Unabhängigkeit. Was heißt das konkret.

Wir hatten ja weiter oben die Gleichung P(Ki | x) = P(x| Ki) * P(Ki) ) / P(x). Der Zähler auf der rechten Seite entspricht der gemeinsamen Verteilung, also P(Ki, x1, …, xn). Und jetzt kommt die bedingte Unabhängigkeit ins Spiel: Wir treffen die Annahme, dass xj und xk gegeben Ki unabhängig sind. Das ist in der Realität zwar meistens nicht richtig, aber in der Praxis hat das erstaunlich wenig Einfluß. Damit wird P(Ki, x1, …, xn) zum Produkt der einzelnen Wahrscheinlichkeiten P(xj | Ki), j = 1, …, n

Nun fügen wir alles zusammen:

P(K_i | x) = \frac{1}{Z} P(K_i) \prod_j^n P(x_j | K_i)

wobei Z = P(x) nur ein Skalierungsfaktor ist.

Der Naive Bayes Algorithmus wählt nun die Klasse, die gegeben die Beobachtung x1, .., xn am wahrscheinlichsten ist. Statistisch sagt man dazu die maximale a-posteriori-Wahrscheinlichkeit. Das bedeutet, dass wir das k wählen, für das die Wahrscheinlichkeit maximal wird. Mathematisch ausgedrückt:

    \[argmax_{i} P(K_i) \prod_j P(x_j | K_i)\]

Finally: Das Event Model

Eine Sache fehlt noch. Wir müssen uns Gedanken machen, wie wir p(xj | Ki) bestimmen. Dazu gibt es verschiedene Annahmen über die Verteilung der Features

Gaussian Naive Bayes

Die zugrunde liegende Annahme ist, dass die x, die zu einer Klasse Ki gehören, normalverteilt sind. Damit das so sein kann, sollten die x natürlich erstmal metrisch sein.

Bestimmen wir also den Mittelwert mui und die Standardabweichung sigmai, dann können wir die Wahrscheinlichkeit einer bestimmten Ausprägung von x wie folgt berechnen:

    \[P(x = y | K_i) = \frac{1}{\sqrt{2\pi\sigma_i^2}}e^{-\frac{(y-\mu_i)^2}{2\sigma_i^2}}\]

Multinomial Naive Bayes

In diesem Fall ist die Annahme, dass eine multinomiale Verteilung zugrunde liegt, wie sie beim mehrmaligen Werfen eines k-seitigen Würfels. Eine Ausprägung des Features xj entspricht zum Beispiel der Häufigkeit des Auftretens eines Ereignisses j

    \[P(x | K_i) = \frac{(\sum x_j)!}{\prod x_j!} \prod p_{ij}^{x_j}\]

Bernoulli Naive Bayes

In diesem Fall ist die Annahme, dass die Features x unabhängige binäre Variablen (ja/nein) sind, also zum Beispiel das Auftauchen einer bestimmten Eigenschaft

    \[P(x | K_i) = \prod_j p_{ij}^{x_j}(1-p_{ij})^{1-x_j}\]

Beispiele für Naive Bayes in R

In R gibt es meines Wissens zwei Packages, die Naive Bayes implementiert haben. Das ist zum einen das Package e1071, welches eine ganze Reihe statistische Methoden wie support vector machines und eben auch Naive Bayes implementiert hat. Zum anderen gibt es das Package NaiveBayes, welches ich hier benutze.

Die Anwendung des Naive Bayes-Algorithmus ist ganz einfach in einer Zeile gemacht. Man braucht aber natürlich ein bisschen Code drumherum.

Im ersten Beispiel ziehen wir 1000x aus der Standardnormalverteilung und ordnen den Wert einer Klasse (TRUE) zu, wenn der Wert größer als 0 ist. Andernfalls gehört er zur anderen Klasse (FALSE).

Den Datensatz splitten wir zufällig in einen Trainingsdatensatz und einen Testdatensatz, wobei der Trainingsdatensatz 80% des gesamten Datensatzes umfasst.

Nachdem wir dann den Naive Bayes-Algorithmus darauf losgelassen haben, überprüfen wir am Testdatensatz, wie gut er funktioniert hat. Dazu lassen wir den Testdatensatz anhand predict klassifizieren und schauen uns die Kontingenztafel an und berechnen die Accuracy, also den Anteil an richtig zugeordneten Klassen.

Wir sehen, dass Naive Bayes dieses Beispiel sehr gut vorhersagt. Die Accuracy liegt bei 98,5%

Vorhersage (predict)
TRUEFALSE
Test-DatensatzTRUE1010
FALSE396

Im zweiten Beispiel benutzen wir den Iris-Datensatz, der mit R mitgeliefert wird und ein beliebter Anschauungsdatensatz für zahlreiche Beispiele ist.

Wie im ersten Beispiel splitten wir wieder zufällig in Trainings- und Testdatensatz. Dann wollen wir die drei Arten (Species) anhand der anderen Variablen mittels Naive Bayes klassifizieren. Das wenden wir dann auf den Testdatensatz an und schauen uns an, wie gut der Algorithmus war

Hier ist Naive Bayes sogar perfekt. Die Accuracy liegt bei 100%, es wurden alle Arten korrekt klassifiziert.

Vorhersage (predict)
SetosaVersicolorVirginica
Test-DatensatzSetosa
1000
Versicolor0120
Virginica008

So, jetzt könnt ihr selber loslegen. Schnappt euch einen interessanten Datensatz, schmeißt den Naive Bayes-Algorithmus drauf und schaut, wie gut er abschneidet. So bekommt ihr auch ein Gefühl dafür, wann er gut geeignet ist und wann eher nicht so.