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. Das Label, das am häufigsten
vorgekommen ist, wird zur Klassifizierung verwendet.
Der DYCOS-Algorithmus nimmt jedoch nicht einfach den Graphen für 
dieses Verfahren, sondern erweitert ihn mit Hilfe der zur Verfügung
stehenden Texte.

Für diese Erweiterung wird zuerst wird Vokabular $W_t$ bestimmt, das 
charakteristisch für eine Knotengruppe ist. Wie das gemacht werden kann
und warum nicht einfach jedes Wort in das Vokabular aufgenommen wird,
wird in Abschnitt~\ref{sec:vokabularbestimmung} erläutert.\\
Nach der Bestimmung des Vokabulars wird für 
jedes Wort im Vokabular ein Wortknoten zum Graphen hinzugefügt. Alle
Knoten, die der Graph zuvor hatte, werden nun \enquote{Strukturknoten}
genannt.
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 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,
          die auch im Vokabular $W_t$ sind,
          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$-Mehrfachsprung
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$-Mehrfachsprung}, 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$\\

        \Procedure{SturkturellerSprung}{Dictionary $d$, Startknoten $v$, Länge $l$}
            \For{$i$ von $1$ bis $l$}
                \State $v \gets v.\Call{Next}{}$
                \ForAll{Label $w$ in v.\Call{GetLabels}{}}
                    \State $d[w] = d[w] + 1$
                \EndFor
            \EndFor
        \EndProcedure
        \\
        \Procedure{InhaltlicherMehrfachsprung}{Dictionary $d$, Startknoten $v$, Länge $l$}
            \For{$i$ von $1$ bis $l$}
                \State $v \gets v.\Call{Next}{}$ \Comment{TODO: Hier muss ein mehrfachsprung beschrieben werden!}
                \ForAll{Label $w$ in v.\Call{GetLabels}{}}
                    \State $d[w] = d[w] + 1$
                \EndFor
            \EndFor
        \EndProcedure
        \\

        \ForAll{Knoten $v$ in $\N_t \setminus \T_t$}
            \State $d \gets $ Dictionary, das für neue Einträge 0 annimmt
            \For{$i$ von $1$ bis $r$}
                \State $sprungTyp \gets \Call{random}{0, 1}$
                \If{$sprungTyp \leq p_S$}
                    \State \Call{SturkturellerSprung}{$v$, $l$}
                \Else
                    \State \Call{InhaltlicherMehrfachsprung}{$v$, $l$}
                \EndIf
            \EndFor

            \If{$d$ ist leer}
                \State $M_H \gets \Call{HäufigsteLabelImGraph}{}$
                \ForAll{$label$ in $M_H$}
                    \State $v.\Call{AddLabel}{label}$
                \EndFor
            \Else
                \State $M_H \gets \Call{max}{d}$
                \ForAll{$label$ in $M_H$}
                    \State $v.\Call{AddLabel}{label}$
                \EndFor
            \EndIf
        \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 Homonymen 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}