2.4 Feature-Selektion

Eine primäre Schwierigkeit der Klassifikation ist die hohe Dimensionalität des Feature-Raums (vgl. [YP97]). Schon für relativ kleine Mengen von Trainingsdokumenten kann die Anzahl an verschiedenen Features (der die Dimension des Feature-Raums entspricht) 5-stellige oder sogar 6-stellige Werte annehmen. Da die Laufzeit der meisten Algorithmen zur automatischen Klassifikation von dieser Anzahl an Features abhängt, ist es also wünschenswert, die Anzahl an Features zu reduzieren. Dabei sollten jedoch nach Möglichkeit nur Features mit geringem oder keinem Informationsgehalt entfernt werden, während sehr informative Features gehalten werden sollten.

Um eine Reduktion von Features zu erreichen, ist es also notwendig, diese Features bezüglich ihres Informationsgehaltes zu bewerten. Für eine solche Bewertung ist die Betrachtung

• der Häufigkeit von Features,
• der Verteilung dieser Features auf die Trainingsdokumente und
• der Verteilung der verschiedenen Features auf die Klassen

von Bedeutung, wobei letzterem der größte Stellenwert beizumessen ist. So ist zum Beispiel ein Feature, das in den Dokumenten einer Klasse c sehr häufig vorkommt, in den Dokumenten der anderen Klassen jedoch kaum oder gar nicht auftritt, als starker Informationsträger für die Abgrenzung von $c$ gegenüber den übrigen Klassen einzustufen. Im Gegensatz dazu ist ein Feature, das in der gesamten Trainingsbasis sehr oft vorkommt, dabei aber relativ gleichmäßig über die Dokumente der verschiedenen Klassen verteilt ist, als Informationsträger bezüglich der Klassifikation nicht von großem Wert, ebensowenig wie ein Feature, das in der gesamten Dokumentenmenge nur sehr selten vorkommt. Solche Features, die für die Klassifikation von Dokumenten keine bzw. nur schwache Informationsträger sind, werden im folgenden als ,,Quasi-Stopworte`` bezeichnet.

Für die Bewertung von Features bezüglich ihres Informationsgehaltes lassen sich verschiedene Maße verwenden, von denen hier folgende betrachtet werden:

1. (absolute/relative) Häufigkeit
2. Information Gain
3. Mutual Information

Weitere Maße zur Feature-Selektion sind z. B. $\chi^2$ und term strength, die hier jedoch nicht weiter betrachtet werden.

Bei der Berechnung von Information Gain und Mutual Information werden einige Wahrscheinlichkeiten von Klassen und Features verwendet, die an dieser Stelle kurz definiert werden sollen:

• Wahrscheinlichkeit für ein Feature $x_i$:
  $$P(x_i)=\dfrac{\vert\mathrm{docs mit } x_i\vert}{\vert\mathrm{docs gesamt}\vert}$$

  $P(\overline{x_i})$ ist entsprechend $1-P(x_i)$

• Wahrscheinlichkeit einer Klasse $c_j$:
  $$P(c_j)=\dfrac{\vert\mathrm{docs in } c_j\vert}{\vert\mathrm{docs gesamt}\vert}$$

• Wahrscheinlichkeit eines Features $x_i$, falls $c_j$ bereits eingetreten ist:
  $$P(c_j\vert x_i)=\dfrac{\vert\mathrm{docs aus } c_j \mathrm{ mit } x_i\vert}{\vert\mathrm{docs aus } c_j\vert}$$

  $P(c_j\vert\overline{x_i})=1-P(c_j\vert x_i)$

• Wahrscheinlichkeit für eine Klasse $c_j$ und ein Feature $x_i$:
  $$P(x_i \wedge c_j)=\dfrac{\vert\mathrm{docs aus } c_j \mathrm{ mit } x_i\vert}{\vert\mathrm{docs gesamt}\vert}$$

Grundlage für die Berechnung von Information Gain und Mutual Information ist die Information I eines Ereignisses x:

$$I(x)=-\log_2 p(x)$$

Das übliche Maß des Informationsgehaltes einer Zufallsvariablen X mit Ereignissen $x_i$ ist deren (Shannon-)Entropie, die sich über $I(x_i)$ definieren läßt als (vgl. [Sha48]):

$$H(X)=-\sum_{x_i} p(x_i) \; \log_2 p(x_i)$$