1.9. Naive Bayes#

Naive Bayes-Methoden sind eine Reihe von überwachten Lernalgorithmen, die auf der Anwendung des Satzes von Bayes mit der „naiven“ Annahme der bedingten Unabhängigkeit zwischen jedem Merkmalspaar basieren, gegeben den Wert der Klassenvariable. Der Satz von Bayes besagt folgende Beziehung, gegeben die Klassenvariable \(y\) und den abhängigen Merkmalsvektor \(x_1\) bis \(x_n\):

\[P(y \mid x_1, \dots, x_n) = \frac{P(y) P(x_1, \dots, x_n \mid y)} {P(x_1, \dots, x_n)}\]

Unter Verwendung der naiven Annahme der bedingten Unabhängigkeit, dass

\[P(x_i | y, x_1, \dots, x_{i-1}, x_{i+1}, \dots, x_n) = P(x_i | y),\]

für alle \(i\), vereinfacht sich diese Beziehung zu

\[P(y \mid x_1, \dots, x_n) = \frac{P(y) \prod_{i=1}^{n} P(x_i \mid y)} {P(x_1, \dots, x_n)}\]

Da \(P(x_1, \dots, x_n)\) gegeben die Eingabe konstant ist, können wir die folgende Klassifizierungsregel verwenden:

\[ \begin{align}\begin{aligned}P(y \mid x_1, \dots, x_n) \propto P(y) \prod_{i=1}^{n} P(x_i \mid y)\\\Downarrow\\\hat{y} = \arg\max_y P(y) \prod_{i=1}^{n} P(x_i \mid y),\end{aligned}\end{align} \]

und wir können die Maximum-A-Posteriori (MAP)-Schätzung verwenden, um \(P(y)\) und \(P(x_i \mid y)\) zu schätzen; das erstere ist dann die relative Häufigkeit der Klasse \(y\) im Trainingsdatensatz.

Die verschiedenen Naive Bayes-Klassifikatoren unterscheiden sich hauptsächlich durch die Annahmen, die sie bezüglich der Verteilung von \(P(x_i \mid y)\) treffen.

Trotz ihrer offensichtlich übersimplifizierten Annahmen haben sich Naive Bayes-Klassifikatoren in vielen realen Situationen, wie berühmt-berüchtigt der Dokumentenklassifizierung und Spamfilterung, recht gut bewährt. Sie erfordern eine geringe Menge an Trainingsdaten, um die notwendigen Parameter zu schätzen. (Zu theoretischen Gründen, warum Naive Bayes gut funktioniert und auf welchen Datentypen, siehe die untenstehenden Referenzen.)

Naive Bayes-Lerner und -Klassifikatoren können im Vergleich zu ausgefeilteren Methoden extrem schnell sein. Die Entkopplung der bedingten Merkmalsverteilungen der Klassen bedeutet, dass jede Verteilung unabhängig als eindimensionale Verteilung geschätzt werden kann. Dies hilft wiederum, Probleme zu mildern, die aus dem Fluch der Dimensionalität entstehen.

Auf der anderen Seite ist Naive Bayes zwar als anständiger Klassifikator bekannt, aber als schlechter Schätzer, sodass die Wahrscheinlichkeitsausgaben von predict_proba nicht zu ernst genommen werden sollten.

Referenzen#

1.9.1. Gaußscher Naive Bayes#

GaussianNB implementiert den Gaußschen Naive Bayes-Algorithmus für die Klassifizierung. Die Likelihood der Merkmale wird als Gaußsch angenommen

\[P(x_i \mid y) = \frac{1}{\sqrt{2\pi\sigma^2_y}} \exp\left(-\frac{(x_i - \mu_y)^2}{2\sigma^2_y}\right)\]

Die Parameter \(\sigma_y\) und \(\mu_y\) werden mittels Maximum-Likelihood geschätzt.

>>> from sklearn.datasets import load_iris
>>> from sklearn.model_selection import train_test_split
>>> from sklearn.naive_bayes import GaussianNB
>>> X, y = load_iris(return_X_y=True)
>>> X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.5, random_state=0)
>>> gnb = GaussianNB()
>>> y_pred = gnb.fit(X_train, y_train).predict(X_test)
>>> print("Number of mislabeled points out of a total %d points : %d"
...       % (X_test.shape[0], (y_test != y_pred).sum()))
Number of mislabeled points out of a total 75 points : 4

1.9.2. Multinomialer Naive Bayes#

MultinomialNB implementiert den Naive Bayes-Algorithmus für multinomisch verteilte Daten und ist eine der beiden klassischen Varianten von Naive Bayes, die in der Textklassifizierung verwendet werden (wobei die Daten typischerweise als Wortvektoranzahlen dargestellt werden, obwohl sich tf-idf-Vektoren in der Praxis ebenfalls gut bewähren). Die Verteilung wird durch Vektoren \(\theta_y = (\theta_{y1},\ldots,\theta_{yn})\) für jede Klasse \(y\) parametrisiert, wobei \(n\) die Anzahl der Merkmale ist (in der Textklassifizierung die Größe des Vokabulars) und \(\theta_{yi}\) die Wahrscheinlichkeit \(P(x_i \mid y)\) ist, dass Merkmal \(i\) in einer Stichprobe vorkommt, die zur Klasse \(y\) gehört.

Die Parameter \(\theta_y\) werden durch eine geglättete Version der Maximum-Likelihood-Schätzung, d.h. relative Häufigkeitszählung, geschätzt:

\[\hat{\theta}_{yi} = \frac{ N_{yi} + \alpha}{N_y + \alpha n}\]

wobei \(N_{yi} = \sum_{x \in T} x_i\) die Anzahl der Male ist, mit denen Merkmal \(i\) in allen Stichproben der Klasse \(y\) im Trainingsdatensatz \(T\) vorkommt, und \(N_{y} = \sum_{i=1}^{n} N_{yi}\) die Gesamtzahl aller Merkmale für die Klasse \(y\) ist.

Die Glättungsprior \(\alpha \ge 0\) berücksichtigt Merkmale, die nicht in den Lernstichproben vorhanden sind, und verhindert Nullwahrscheinlichkeiten bei weiteren Berechnungen. Die Einstellung \(\alpha = 1\) wird als Laplace-Glättung bezeichnet, während \(\alpha < 1\) als Lidstone-Glättung bezeichnet wird.

1.9.3. Complement Naive Bayes#

ComplementNB implementiert den Complement Naive Bayes (CNB)-Algorithmus. CNB ist eine Anpassung des Standard-Multinomial-Naive-Bayes (MNB)-Algorithmus, die sich besonders gut für unausgewogene Datensätze eignet. Insbesondere verwendet CNB Statistiken aus dem *Komplement* jeder Klasse, um die Gewichte des Modells zu berechnen. Die Erfinder von CNB zeigen empirisch, dass die Parameterschätzungen für CNB stabiler sind als die für MNB. Darüber hinaus übertrifft CNB MNB regelmäßig (oft um einen erheblichen Betrag) bei Textklassifizierungsaufgaben.

Gewichtsberechnung#

Das Verfahren zur Berechnung der Gewichte ist wie folgt:

\[ \begin{align}\begin{aligned}\hat{\theta}_{ci} = \frac{\alpha_i + \sum_{j:y_j \neq c} d_{ij}} {\alpha + \sum_{j:y_j \neq c} \sum_{k} d_{kj}}\\w_{ci} = \log \hat{\theta}_{ci}\\w_{ci} = \frac{w_{ci}}{\sum_{j} |w_{cj}|}\end{aligned}\end{align} \]

wobei die Summen über alle Dokumente \(j\) gebildet werden, die nicht zur Klasse \(c\) gehören, \(d_{ij}\) entweder der Zähl- oder tf-idf-Wert von Begriff \(i\) im Dokument \(j\) ist, \(\alpha_i\) ein Glättungshyperparameter wie in MNB ist und \(\alpha = \sum_{i} \alpha_i\). Die zweite Normierung adressiert die Tendenz, dass längere Dokumente die Parameterschätzungen in MNB dominieren. Die Klassifizierungsregel lautet:

\[\hat{c} = \arg\min_c \sum_{i} t_i w_{ci}\]

d.h. ein Dokument wird der Klasse zugeordnet, die die *schlechteste* Komplement-Übereinstimmung aufweist.

Referenzen#

1.9.4. Bernoulli Naive Bayes#

BernoulliNB implementiert die Naive Bayes-Trainings- und Klassifizierungsalgorithmen für Daten, die nach multivariaten Bernoulli-Verteilungen verteilt sind; d.h. es können mehrere Merkmale vorhanden sein, aber jedes wird als binärwertige (Bernoulli, boolesche) Variable angenommen. Daher erfordert diese Klasse, dass Stichproben als binärwertige Merkmalsvektoren dargestellt werden; wenn andere Daten übergeben werden, kann eine BernoulliNB-Instanz ihre Eingabe binarisieren (abhängig vom binarize-Parameter).

Die Entscheidungsregel für Bernoulli Naive Bayes basiert auf

\[P(x_i \mid y) = P(x_i = 1 \mid y) x_i + (1 - P(x_i = 1 \mid y)) (1 - x_i)\]

was sich von der Regel des multinomialen NB dadurch unterscheidet, dass es das Nichtauftreten eines Merkmals \(i\), das ein Indikator für Klasse \(y\) ist, explizit bestraft, während die multinominale Variante ein nicht auftretendes Merkmal einfach ignorieren würde.

Im Fall der Textklassifizierung können MerkmalOccurrence-Vektoren (anstelle von Wortanzahl-Vektoren) zum Trainieren und Verwenden dieses Klassifikators verwendet werden. BernoulliNB kann auf einigen Datensätzen besser abschneiden, insbesondere bei kürzeren Dokumenten. Es ist ratsam, beide Modelle auszuwerten, falls die Zeit es erlaubt.

Referenzen#

1.9.5. Kategorialer Naive Bayes#

CategoricalNB implementiert den kategorialen Naive Bayes-Algorithmus für kategorial verteilte Daten. Er geht davon aus, dass jedes Merkmal, das durch den Index \(i\) beschrieben wird, seine eigene kategoriale Verteilung hat.

Für jedes Merkmal \(i\) im Trainingsdatensatz \(X\) schätzt CategoricalNB eine kategoriale Verteilung für jedes Merkmal i von X, bedingt auf die Klasse y. Die Indexmenge der Stichproben wird als \(J = \{ 1, \dots, m \}\) definiert, wobei \(m\) die Anzahl der Stichproben ist.

Wahrscheinlichkeitsberechnung#

Die Wahrscheinlichkeit der Kategorie \(t\) im Merkmal \(i\) gegeben Klasse \(c\) wird geschätzt als

\[P(x_i = t \mid y = c \: ;\, \alpha) = \frac{ N_{tic} + \alpha}{N_{c} + \alpha n_i},\]

wobei \(N_{tic} = |\{j \in J \mid x_{ij} = t, y_j = c\}|\) die Anzahl der Male ist, mit denen Kategorie \(t\) in den Stichproben \(x_{i}\) vorkommt, die zur Klasse \(c\) gehören, \(N_{c} = |\{ j \in J\mid y_j = c\}|\) die Anzahl der Stichproben mit Klasse c ist, \(\alpha\) ein Glättungsparameter ist und \(n_i\) die Anzahl der verfügbaren Kategorien des Merkmals \(i\) ist.

CategoricalNB geht davon aus, dass die Stichprobenmatrix \(X\) kodiert ist (z.B. mit Hilfe von OrdinalEncoder), sodass alle Kategorien für jedes Merkmal \(i\) mit Zahlen \(0, ..., n_i - 1\) dargestellt werden, wobei \(n_i\) die Anzahl der verfügbaren Kategorien des Merkmals \(i\) ist.

1.9.6. Out-of-Core Naive Bayes Modell-Fitting#

Naive Bayes-Modelle können verwendet werden, um großskalige Klassifizierungsprobleme zu bewältigen, für die der vollständige Trainingsdatensatz möglicherweise nicht in den Speicher passt. Um diesen Fall zu handhaben, bieten MultinomialNB, BernoulliNB und GaussianNB eine partial_fit-Methode, die inkrementell wie bei anderen Klassifikatoren verwendet werden kann, wie in Out-of-core classification of text documents gezeigt. Alle Naive Bayes-Klassifikatoren unterstützen Stichprobengewichtungen.

Im Gegensatz zur fit-Methode muss beim ersten Aufruf von partial_fit die Liste aller erwarteten Klassenbezeichnungen übergeben werden.

Eine Übersicht über die in scikit-learn verfügbaren Strategien finden Sie auch in der Dokumentation zu Out-of-core learning.

Hinweis

Die Methode partial_fit von Naive Bayes-Modellen führt einen gewissen Rechenaufwand mit sich. Es wird empfohlen, Datenstückgrößen zu verwenden, die so groß wie möglich sind, d.h. wie es der verfügbare Arbeitsspeicher zulässt.