LaTeX-examples/documents/DYCOS/Vokabularbestimmung.tex

\subsection{Vokabularbestimmung}\label{sec:vokabularbestimmung}
Da die größe des Vokabulars die Datenmenge signifikant beeinflusst,
liegt es in unserem Interesse so wenig Wörter wie möglich ins
Vokabular aufzunehmen. Insbesondere sind Wörter nicht von Interesse,
die in fast allen Texten vorkommen, wie im Deutschen z.~B.
\enquote{und}, \enquote{mit} und die Pronomen. Es ist wünschenswert
Wörter zu wählen, die die Texte möglichst start voneinander Unterscheiden.
Der DYCOS-Algorithmus wählt die Top-$m$ dieser Wörter als Vokabular,
wobei $m \in \mathbb{N}$ eine Festzulegende Konstante ist. In \cite[S. 365]{aggarwal2011}
wird der Einfluss von $m \in \Set{5,10, 20}$ auf die Klassifikationsgüte
untersucht und festegestellt, dass für $m \in \Set{5,10}$ die Klassifikationsgüte 
sehr ähnlich ist.

Nun kann man manuell eine Liste von zu beachtenden Wörtern erstellen
oder mit Hilfe des Gini-Koeffizienten automatisch ein Vokabular erstellen.
Der Gini-Koeffizient ist ein statistisches Maß, das die Ungleichverteilung
bewertet. Er ist immer im Intervall $[0,1]$, wobei $0$ einer 
Gleichverteilung entspricht und $1$ der größt möglichen Ungleichverteilung.

Sei nun $n_i(w)$ die Häufigkeit des Wortes $w$ in allen Texten mit 
dem $i$-ten Label.
\begin{align}
    p_i(w) &:= \frac{n_i(w)}{\sum_{j=1}^{|\L_t|} n_j(w)} &\text{(Relative Häufigkeit des Wortes $w$)}\\
    G(w)   &:= \sum_{j=1}^{|\L_t|} p_j(w)^2              &\text{(Gini-Koeffizient von $w$)}
\end{align}
In diesem Fall ist $G(w)=0$ nicht möglich, da zur Vokabularbestimmung
nur Wörter betrachtet werden, die auch vorkommen.

Ein Vorschlag, wie die Vokabularbestimmung implementiert werden kann,
ist als Pseudocode mit \cref{alg:vokabularbestimmung}
gegeben. Dieser Algorithmus benötigt neben dem Speicher für den
Graphen, die Texte sowie die $m$ Vokabeln noch $\mathcal{O}(|\text{Verschiedene Wörter in } S_t| \cdot (|\L_t| + 1))$
Speicher. Die Average-Case Zeitkomplexität beträgt 
$\mathcal{O}(|\text{Wörter in } S_t|)$, wobei dazu die Vereinigung
von Mengen $M,N$ in $\mathcal{O}(\min{|M|, |N|})$ sein muss.

\begin{algorithm}
    \begin{algorithmic}[1]
        \Require \\
                 $V_{L,t}$ (Knoten mit Labels),\\
                 $\L_t$ (Labels),\\
                 $f:V_{L,t} \rightarrow \L_t$ (Label-Funktion),\\
                 $m$ (Gewünschte Vokabulargröße)
        \Ensure  $\M_t$ (Vokabular)\\

        \State $S_t \gets \Call{Sample}{V_{L,t}}$ \Comment{Wähle eine Teilmenge $S_t \subseteq V_{L,t}$ aus}
        \State $\M_t \gets \bigcup_{v \in S_t} \Call{getTextAsSet}{v}$ \Comment{Menge aller Wörter}
        \State $cLabelWords \gets (|\L_t|+1) \times |\M_t|$-Array, mit 0en initialisert\\

        \ForAll{$v \in V_{L,t}$} \Comment{Gehe jeden Text Wort für Wort durch}
            \State $i \gets \Call{getLabel}{v}$
            \ForAll{$(word, occurences) \in \Call{getTextAsMultiset}{v}$}
                \State $cLabelWords[i][word] \gets cLabelWords[i][word] + occurences$
                \State $cLabelWords[i][|\L_t|] \gets cLabelWords[i][|\L_t|] + occurences$
            \EndFor
        \EndFor
        \\
        \ForAll{Wort $w \in \M_t$}
            \State $p \gets $ Array aus $|\L_t|$ Zahlen in $[0, 1]$
            \ForAll{Label $i \in \L_t$}
                \State $p[i] \gets \frac{cLabelWords[i][w]}{cLabelWords[i][|\L_t|]}$
            \EndFor
            \State $w$.gini $\gets$ \Call{sum}{{\sc map}({\sc square}, $p$)}
        \EndFor

        \State $\M_t \gets \Call{SortDescendingByGini}{\M_t}$
        \State \Return $\Call{Top}{\M_t, m}$
    \end{algorithmic}
\caption{Vokabularbestimmung}
\label{alg:vokabularbestimmung}
\end{algorithm}

Die Menge $S_t$ kann durch Aus der Menge aller Dokumenten, deren 
Knoten gelabelt sind, mithile des in \cite{Vitter} vorgestellten
Algorithmus bestimmt werden.