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 stark 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, 15,20}$ auf die Klassifikationsgüte
untersucht und festgestellt, dass die Klassifikationsgüte mit größerem $m$
sinkt, sie also für $m=5$ für den DBLP-Datensatz am höchsten ist. Für den
CORA-Datensatz wurde mit $m \in \set{3,4,5,6}$ getestet und kein signifikanter
Unterschied festgestellt.

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ößtmöglichen Ungleichverteilung.

Sei nun $n_i(w)$ die Häufigkeit des Wortes $w$ in allen Texten mit der $i$-ten
Knotenbeschriftung.
\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. In \cref{alg4:l6} wird
eine Teilmenge $S_t \subseteq V_{L,t}$ zum Generieren des Vokabulars gewählt.
In \cref{alg4:l8} wird ein Array $cLabelWords$ erstellt, das $(|\L_t|+1)$
Felder hat. Die Elemente dieser Felder sind jeweils assoziative Arrays, deren
Schlüssel Wörter und deren Werte natürliche Zahlen sind. Die ersten $|\L_t|$
Elemente von $cLabelWords$ dienen dem Zählen der Häufigkeit der Wörter von
Texten aus $S_t$, wobei für jede Beschriftung die Häufigkeit einzeln gezählt
wird. Das letzte Element aus $cLabelWords$ zählt die Summe der Wörter. Diese
Datenstruktur wird in \cref{alg4:l10} bis \ref{alg4:l12} gefüllt.

In \cref{alg4:l17} bis \ref{alg4:l19} wird die relative Häufigkeit der Wörter
bzgl. der Beschriftungen bestimmt. Daraus wird in \cref{alg4:l20} bis
\ref{alg4:l22} der Gini-Koeffizient berechnet. Schließlich werden in
\cref{alg4:l23} bis \ref{alg4:l24} die Top-$q$ Wörter mit den
höchsten Gini-Koeffizienten zurückgegeben.

\begin{algorithm}[ht]
    \begin{algorithmic}[1]
        \Require \\
                 $V_{L,t}$ (beschriftete Knoten),\\
                 $\L_t$ (Menge der Beschriftungen),\\
                 $f:V_{L,t} \rightarrow \L_t$ (Beschriftungsfunktion),\\
                 $m$ (Gewünschte Vokabulargröße)
        \Ensure  $\M_t$ (Vokabular)\\
        \State $S_t \gets \Call{Sample}{V_{L,t}}$\label{alg4:l6} \Comment{Wähle $S_t \subseteq V_{L,t}$ aus}
        \State $\M_t \gets \emptyset$ \Comment{Menge aller Wörter}
        \State $cLabelWords \gets$ Array aus $(|\L_t|+1)$ assoziativen Arrays\label{alg4:l8}
        \ForAll{$v \in S_t$} \label{alg4:l10}
            \State $i \gets \Call{getLabel}{v}$
            \State \Comment{$w$ ist das Wort, $c$ ist die Häufigkeit}
            \ForAll{$(w, c) \in \Call{getTextAsMultiset}{v}$}
                \State $cLabelWords[i][w] \gets cLabelWords[i][w] + c$
                \State $cLabelWords[|\L_t|][w] \gets cLabelWords[i][|\L_t|] + c$
                \State $\M_t = \M_t \cup \Set{w}$
            \EndFor
        \EndFor\label{alg4:l12}
		\\
        \ForAll{Wort $w \in \M_t$}
            \State $p \gets $ Array aus $|\L_t|$ Zahlen in $[0, 1]$\label{alg4:l17}
            \ForAll{Label $i \in \L_t$}
                \State $p[i] \gets \frac{cLabelWords[i][w]}{cLabelWords[i][|\L_t|]}$
            \EndFor\label{alg4:l19}

            \State $w$.gini $\gets 0$ \label{alg4:l20}
            \ForAll{$i \in 1, \dots, |\L_t|$}
                \State $w$.gini $\gets$ $w$.gini + $p[i]^2$
            \EndFor\label{alg4:l22}
        \EndFor

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

Die Menge $S_t$ kann aus der Menge aller Dokumente, deren Knoten beschriftet
sind, mithilfe des in \cite{Vitter} vorgestellten Algorithmus bestimmt werden.