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, tatsächlich krank zu sein, auch wenn der Test positiv ist, beträgt also nur knapp 25%. Das liegt an der geringen Wahrscheinlichkeit, überhaupt krank zu sein (nur 1%). Diese hebelt einen vermeintlich zuverlässigen Test (98% True-Positive, 97% True-Negative) komplett aus. Daher benötigt man bei medizinischen Tests bzw. überall, wo die Ausprägungen (ja/nein) so ungleich verteilt sind, deutlich bessere Tests.

 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) = \frac{P(x| K_i) * P(K_i)}{P(x)}

Im Endeffekt interessiert uns nur der Zähler, da der Nenner P(x) gar nicht von der Klasse abhängt. P(Ki) sind die a priori Wahrscheinlichkeiten, also eine Annahme, wie häufig die einzelnen Klassen vorkommt. Man kann diese a priori Wahrscheinlichkeiten auch als das Vorwissen bezeichnen. Gibt es keine theoretische Annahmen, diese Wahrscheinlichkeiten zu setzen, dann 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. erstmal davon ausgehen, dass jede Klasse gleich wahrscheinlich ist.

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 nun?

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 bedeutet, dass sich die beiden Ereignisse nicht beeinflussen. Mathematisch drückt man es so aus, dass die Wahrscheinlichkeit, dass das Ereignis xj eintritt, sich nicht durch das Eintreten von Ereignis xk ändert. Alles unter der Bedingung, dass Ki gegeben ist. Daher spricht man von bedingter Unabhängigkeit.

Nehmen wir zum Beispiel einen Würfel, der zweimal geworfen wird. Das Ereignis, dass ich im ersten Wurf eine 1 würfel, gegeben dass der erste Wurf ungerade ist, ist unabhängig vom Ereignis, dass der zweite Wurf eine 3 würfelt, gegeben dass der erste Wurf ungerade ist.

Diese “naive” Annahme 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 Ki, die gegeben die Beobachtung x1, .., xn am wahrscheinlichsten ist. Statistisch sagt man dazu die maximale a-posteriori-Wahrscheinlichkeit. Das bedeutet, dass wir das i 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 \mu_i und die Standardabweichung \sigma_i, 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}\]

GRATIS 5-Tage Minikurs: Datenanalyse in R

Du kennst Dich noch nicht so gut damit aus, wie man einen Datensatz in R analysiert? Ich bin da, um Dir zu helfen. Hole Dir jetzt meinen kostenlosen Datenanalyse mit R – Kurs und fange an, Dir diese zukunftsweisenden Skills anzueignen.

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.

#sofern noch nicht installiert, einmalig das Package herunterladen und installieren
#install.packages("naivebayes")
 
library(naivebayes)
 
## 1. Beispiel: Normalverteilung positiv ##############################
n <- 1000
trainsize <- 0.8 * n
set.seed(1)
df <- data.frame(ID=1:n,x=rnorm(n))
df$Klasse <- ifelse(df$x > 0, TRUE, FALSE) 
 
#Split in Trainings- und Testdatensatz
trainRows <- sample(n, trainsize, replace = FALSE)
train <- df[trainRows,]
test <- df[setdiff(1:n,trainRows),]

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.

# Naive Bayes
nb <- naive_bayes(Klasse ~ x, data = train)
 
# Vorhersage auf Testdatensatz
test$predicted <- predict(nb,test)
Kontingenztafel <- table(test[,c("Klasse","predicted")])
Kontingenztafel
Accuracy <- (Kontingenztafel[1,1] + Kontingenztafel[2,2])/sum(Kontingenztafel)
sprintf("Accuracy: %1.1f%%", 100*Accuracy)
 
## 2. Beispiel: Klassifikation des Iris-Datensatzes ###################
trainRows <- sample(nrow(iris), nrow(iris)*0.8, replace = FALSE)
train <- iris[trainRows,]
test <- iris[setdiff(1:nrow(iris),trainRows),]  
 
# Naive Bayes
nb <- naive_bayes(Species ~ ., train)
 
# Vorhersage auf Testdatensatz
test$predicted <- predict(nb,test)
Kontingenztafel <- table(test[,c("Species","predicted")])
Kontingenztafel
Accuracy <- sum(diag(Kontingenztafel))/sum(Kontingenztafel)
sprintf("Accuracy: %1.1f%%", 100*Accuracy)

 

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

## 2. Beispiel: Klassifikation des Iris-Datensatzes ###################
trainRows <- sample(nrow(iris), nrow(iris)*0.8, replace = FALSE)
train <- iris[trainRows,]
test <- iris[setdiff(1:nrow(iris),trainRows),]  
 
# Naive Bayes
nb <- naive_bayes(Species ~ ., train)
 
# Vorhersage auf Testdatensatz
test$predicted <- predict(nb,test)
Kontingenztafel <- table(test[,c("Species","predicted")])
Kontingenztafel
Accuracy <- sum(diag(Kontingenztafel))/sum(Kontingenztafel)
sprintf("Accuracy: %1.1f%%", 100*Accuracy)

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.

Happy coding,
Euer Holger

GRATIS 5-Tage Minikurs: Datenanalyse in R

Du kennst Dich noch nicht so gut damit aus, wie man einen Datensatz in R analysiert? Ich bin da, um Dir zu helfen. Hole Dir jetzt meinen kostenlosen Datenanalyse mit R – Kurs und fange an, Dir diese zukunftsweisenden Skills anzueignen.

LERNE DATA SCIENCE mit R

Ein Data Science Experte ist in der heutigen datengetriebenen Welt viel gefragt. Mit der entsprechenden Erfahrung kann man sich den gutbezahlten, interessanten Job aussuchen. In meinem Onlinekurs Data Science mit R lernst Du die Grundlagen.