LaTeX-examples/documents/DYCOS/DYCOS-Algorithmus.tex

\subsection{Überblick}
DYCOS (\underline{DY}namic \underline{C}lassification 
algorithm with c\underline{O}ntent and \underline{S}tructure) ist ein 
Knotenklassifizierungsalgorithmus, der Ursprünglich in \cite{aggarwal2011} vorgestellt 
wurde. Er klassifiziert Knoten, indem mehrfach Random Walks startend
bei dem zu klassifizierenden Knoten gemacht werden und die Labels
der besuchten Knoten gezählt werden. Der DYCOS-Algorithmus nimmt 
jedoch nicht einfach den Graphen für dieses Verfahren, sondern
eine Erweiterung.

Für diese Erweiterung wird zuerst wird Vokabular $W_t$ bestimmt, das 
charakteristisch für eine Knotengruppe ist. Wie das gemacht werden kann, wird in 
Abschnitt~\ref{sec:vokabularbestimmung} erläutert. Dann wird für 
jedes Wort im Vokabular ein Wortknoten zum Graphen hinzugefügt.
Ein Strukturknoten $v$ wird genau dann mit einem Wortknoten $w \in W_t$
verbunden, wenn $w$ in einem Text von $v$ vorkommt.

\begin{figure}[htp]
    \centering
    \input{figures/graph-content-and-structure.tex}
    \caption{Erweiterter Graph}
    \label{fig:erweiterter-graph}
\end{figure}

Der DYCOS-Algorithmus betrachtet die Texte, die zu einem Knoten 
zugeornet sind, als eine
Multimenge von Wörtern. Das heißt, zum einen wird nicht auf die
Reihenfolge der Wörter geachtet, zum anderen wird bei Texten
eines Knotens nicht zwischen verschiedenen Texten unterschieden.
Jedoch wird die Anzahl der vorkommen jedes Wortes berücksichtigt.

\subsection{Datenstrukturen}
Zusätzlich zu dem gerichteten Graphen $G_t = (V_t, E_t, V_{L,t})$ 
verwaltet der DYCOS-Algorithmus zwei weitere Datenstrukturen:
\begin{itemize}
    \item Für jeden Knoten $v \in V_t$ werden die vorkommenden Wörter
          und deren Anzahl gespeichert. Das könnte z.~B. über ein 
          assoziatives Array geschehen. Wörter, die nicht in 
          Texten von $v$ vorkommen, sind nicht im Array. Für
          alle vorkommenden Wörter ist der gespeicherte Wert zum 
          Schlüssel \enquote{Wort} die Anzahl der Vorkommen von 
          \enquote{Wort} in den Texten von $v$.
    \item Für jedes Wort des Vokabulars $W_t$ wird eine Liste von 
          Knoten verwaltet, in deren Texten das Wort vorkommt.
\end{itemize}

\subsection{Algorithmen}
Bevor der Algorithmus formal beschrieben wird, wird eine Definition
des strukturellen $l$-Sprungs benötigt:
\begin{definition}
    Sei $G_{E,t} = (V_t, E_{S,t} \cup E_{W,t}, V_{L,t}, W_{t})$ der
    um die Wortknoten $W_{t}$ erweiterte Graph.

    Dann heißt ein Random Walk der Länge $l$ in diesem Graphen
    ein \textbf{struktureller $l$-Sprung}, wenn für den Random Walk
    nur Kanten aus $E_{S,t}$ benutzt werden.
\end{definition}

Der strukturelle $l$-Sprung ist also ein Random Walk der Länge $l$
im Graph $G_t$. Im Gegensatz dazu benötigt der inhaltliche $l$-Multisprung
tatsächlich die Grapherweiterung:

\begin{definition}
    Sei $G_t = (V_t, E_{S,t} \cup E_{W,t}, V_{L,t}, W_{t})$ der
    um die Wortknoten $W_{t}$ erweiterte Graph.

    Dann heißt ein Random Walk der Länge $l$ in diesem Graphen
    ein \textbf{inhaltlicher $l$-Multisprung}, wenn für den Random Walk
    in jedem der $l$ Schritte, startend von einem Knoten $v \in V_t$
    eine Kante zu einem Wortknoten und von dem Wortknoten wieder 
    zu einem Strukturknoten genommen wird.
\end{definition}

\begin{algorithm}[H]
    \begin{algorithmic}
        \Require \\$\G_t = (\N_t, \A_t, \T_t)$ (Netzwerk),\\
                 $r$ (Anzahl der Random Walks),\\
                 $l$ (Länge eines Random Walks),\\
                 $p_s$ (Wahrscheinlichkeit eines strukturellen Sprungs)
        \Ensure  Klassifikation von $\N_t \setminus \T_t$\\

        \ForAll{Knoten $v$ in $\N_t \setminus \T_t$}
            \For{$i$ von $1$ bis $l$}
                \State $sprungTyp \gets \Call{random}{0.0, 1.0}$
                \If{$sprungTyp \leq p_s$}
                    \State Strukturellen $l$-Sprung ausführen
                \Else
                    \State Inhaltlichen $l$-Sprung ausführen
                \EndIf
            \EndFor
        \EndFor
        \State \Return Labels für $\N_t \setminus \T_t$
    \end{algorithmic}
\caption{DYCOS-Algorithmus}
\label{alg:DYCOS}
\end{algorithm}

\subsection{Inhaltliche Mehrfachsprünge}
Es ist nicht sinnvoll, direkt von einem strukturellem Knoten 
$v \in \N_t$ zu einem mit $v$ verbundenen Wortknoten $w$ zu springen
und von diesem wieder zu einem verbundenem strutkurellem Knoten 
$v' \in \N_t$. Würde man dies machen, wäre zu befürchten, dass
aufgrund von Polysemen die Qualität der Klassifizierung verringert
wird. So hat \enquote{Brücke} im Deutschen viele Bedeutungen.
Gemeint sein können z.~B. das Bauwerk, das Entwurfsmuster der
objektorientierten Programmierung oder ein Teil des Gehirns.

Deshalb wird für jeden Knoten $v$, von dem aus man einen inhaltlichen
Mehrfachsprung machen will folgendes vorgehen gewählt:
\begin{enumerate}
    \item Gehe alle in $v$ startenden Random Walks der Länge 2 durch
          und erstelle eine Liste $L$, der erreichbaren Knoten $v'$. Speichere
          außerdem, durch wie viele Pfade diese Knoten $v'$ jeweils erreichbar sind.
    \item Betrachte im folgenden nur die Top-$q$ Knoten, wobei $q \in \mathbb{N}$
          eine zu wählende Konstante des Algorithmus ist.
    \item Wähle mit Wahrscheinlichkeit $\frac{\Call{Anzahl}{v'}}{\sum_{w \in L} \Call{Anzahl}{v'}}$
          den Knoten $v'$ als Ziel des Mehrfachsprungs.
\end{enumerate}

\input{Vokabularbestimmung}