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 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$ dienem 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 eine Teilmenge $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}\Comment{Gehe jeden Text Wort für Wort durch}
            \State $i \gets \Call{getLabel}{v}$
            \ForAll{$(word, haeufigkeit) \in \Call{getTextAsMultiset}{v}$}
                \State $cLabelWords[i][word] \gets cLabelWords[i][word] + haeufigkeit$
                \State $cLabelWords[|\L_t|][word] \gets cLabelWords[i][|\L_t|] + haeufigkeit$
                \State $\M_t = \M_t \cup \Set{word}$
            \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.