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

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.

Sie im Folgenden die Notation wie in Definition~\ref{def:Knotenklassifizierungsproblem}.

Der DYCOS-Algorithmus betrachtet Texte als eine Menge von Wörter, 
die Reihenfolge der Wörter im Text spielt also keine Rolle. Außerdem
werden nicht alle Wörter benutzt, sondern nur solche die auch in 
einem festgelegtem Vokabular vorkommen. Wie dieses Vokabular bestimmt
werden kann, wird in Abschnitt~\ref{sec:vokabularbestimmung} erklärt.

Zusätzlich zu dem Netzwerk verwalltet der DYCOS-Algorithmus für jeden
Knoten eine Liste von Wörtern. Diese Wörter stammen aus den Texten,
die dem Knoten zugeordnet sind.

Für jedes Wort des Vokabulars wird eine Liste von Knoten verwaltet, 
in deren Texten das Wort vorkommt.

Ein $l$-Sprung ist ein ein Random Walk, bei dem $l$
Knoten besucht werden, die nicht verschieden sein müssen. Ein 
$l$-Sprung heißt strukturell, wenn er ausschließlich die Kanten
des Netzwerks für jeden der $l$ Schritte benutzt.

Ein $l$-Sprung heißt inhaltlich, wenn er die Wörter benutzt.

\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}