2.3.1 Naive-Bayes-Klassifikation

Basis für die automatische Klassifikation nach dem Naive-Bayes-Verfahren sind zwei zentrale Sätze der Wahrscheinlichkeitsrechnung:

1. Satz von Bayes:

   $$P(X=a_i\vert Y=b)=\frac{P(X=a_i)P(Y=b\vert X=a_i)}{\sum_j P(X=a_j)P(Y=b\vert X=a_j)}$$ (1)

   
   

2. Satz von der totalen Wahrscheinlichkeit:

   $$P(Y=b)=\sum_j P(X=a_j)P(Y=b\vert X=a_j)$$ (2)

   
   

Einsetzen von (2) in (1) und eine Umbenennung von $a_i$ in a ergibt:

$$P(X=a\vert Y=b)=P(X=a) \frac{P(Y=b\vert X=a)}{P(Y=b)}$$ (3)

Zur Vereinfachung und Erhöhung der Lesbarkeit werden Wahrscheinlichkeitsverteilungen $P(X=a_i)$ von Variablen X mit möglichen Ereignissen $a_i$ geschrieben als $p(a_i)$, so daß sich (3) schreibt als:

$$P(a\vert b)=P(a) \frac{P(b\vert a)}{P(b)}$$ (4)

Das Klassifikationsproblem stellt sich im Fall der Naive-Bayes-Klassifikation als die Wahrscheinlichkeit, daß ein Dokument, repräsentiert durch einen Featurevektor $\vec{x}=(x_1, \ldots, x_d)$ im d-dimensionalen Feature-Raum, in die Klasse $c_j$ einzuordnen ist. (Hierbei wird davon ausgegangen, daß jedes Dokument durch einen Featurevektor der Länge d dargestellt werden kann.) Gesucht wird also die bedingte Wahrscheinlichkeit $P(c_j\vert\vec{x})$. Mit (4) ergibt sich somit:

$$P(c_j\vert\vec{x})=P(c_j) \frac{P(\vec{x}\vert c_j)}{P(\vec{x})}$$ (5)

Wenn alle $P(c_j\vert\vec{x})$ bekannt sind, kann ein Dokument mit Featurevektor $\vec{x}$ mit minimierter Fehlererwartung in die Klasse $c_j$ eingeordnet werden, für die $P(c_j\vert\vec{x})$ den größten Wert annimmt (vgl. [Lew98]). Da $P(c_j\vert\vec{x})$ jedoch in der Regel nicht bekannt ist, muß an dieser Stelle auf den Ansatz zurückgegriffen werden, den (5) nahelegt. Hierbei läßt sich $P(c_j)$ bei n Trainingsdokumenten leicht berechnen als

$$P(c_j)=\frac{\vert\textrm{docs in }c_j\vert}{n}$$

Als schwierig stellt sich jedoch die Berechnung von $P(\vec{x}\vert c_j)$ dar, da die Anzahl der möglichen Werte für $\vec{x}$ in der Regel astronomisch hoch ist. Eine übliche Strategie ist es deshalb, anzunehmen, daß $P(\vec{x}\vert c_j)$ für alle $c_j$ geschrieben werden kann als (vgl. [ebd]):

$$P(\vec{x}\vert c_j)=\prod_{i=1}^d P(x_i\vert c_j)$$ (6)

$P(x_i\vert c_j)$ wird hierbei oft abgeschätzt durch

$$P(x_i\vert c_j)=\frac{n_c}{n_j},$$

wobei $n_c$ die Anzahl der Vorkommen des Features $x_i$ in den zu $c_j$ gehörenden Dokumenten und $n_j$ die Anzahl der Features in den zu $c_j$ gehörenden Dokumenten ist. Diese Abschätzung stellt sich jedoch als problematisch heraus, wenn $n_c=0$, da als Folge dessen auch die Abschätzung von $P(\vec{x}\vert c_j)$ nach (6) den Wert 0 annähme. Um diesen Fall zu vermeiden, bietet sich die Verwendung des m-estimate (vgl. [Mit97]) an, das definiert ist als:

$$\frac{n_c+mp}{n_j+m}$$ (7)

Hierbei sind $n_c$ und $n_j$ definiert wie zuvor, p ist die initiale Abschätzung der zu ermittelnden Wahrscheinlichkeit und $m$ eine Konstante, genannt equivalent sample size, die bestimmt, wie stark p relativ zu den trainierten Daten gewichtet wird. Sie heißt deshalb equivalent sample size, weil (7) interpretiert werden kann als Erweiterung der $n_j$ Features in $c_j$ um m virtuelle Features, die p entsprechend verteilt sind [ebd.].

Mit (6) ergibt sich weiterhin folgende Form zur Berechnung von $P(c_j\vert\vec{x})$:

$$P(c_j\vert\vec{x})=P(c_j)\dfrac{\prod_{i=1}^d P(x_i\vert c_j)}{P(\vec{x})}$$ (8)

Einen Klassifikator, der auf der Basis von (8) ein Dokument, das durch einen Featurevektor $\vec{x}$ repräsentiert wird, der Klasse $c_j$ zuordnet, für die $P(c_j\vert\vec{x})$ den höchsten Wert annimmt, nennt man einen Naive-Bayes-Klassifikator (vgl. [Lew98]). Zur Vereinfachung der Berechnung kann außerdem $P(\vec{x})$ vernachlässigt werden, da diese Wahrscheinlichkeit für alle Klassen $c_j$ gleich ist; als Maß für die Klassifikation kann also $P(c_j\vert\vec{x})/P(\vec{x})$ verwendet werden.

,,Naiv(e)`` ist bei diesem Klassifikator die Annahme, die Schritt 6 zugrunde liegt. Dieser Schritt basiert nämlich auf der Annahme, daß das Vorkommen eines Wertes $x_i$ statistisch unabhängig von Vorkommen aller anderen $x_{i'}$ ist (vgl. [Yan99]).