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. 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}$ (beschriftete Knoten),\\
                 $\L_t$ (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}}$ \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 initialisiert\\

        \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 0$
            \ForAll{$i \in 1, \dots, |\L_t|$}
                \State $w$.gini $\gets$ $w$.gini + $p[i]^2$
            \EndFor
        \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 aus der Menge aller Dokumente, deren 
Knoten beschriftet sind, mithilfe des in \cite{Vitter} vorgestellten
Algorithmus bestimmt werden.