LaTeX-examples/documents/DYCOS/SchwaechenVerbesserungen.tex

Der in \cite{aggarwal2011} vorgestellte Algorithmus hat einige Probleme,
die im Folgenden erläutert werden. Außerdem werden Verbesserungen
vorgeschlagen, die es allerdings noch zu untersuchen gilt.

\subsection{Schwächen von DYCOS}
\subsubsection{Anzahl der Labels}
So, wie der DYCOS-Algorithmus vorgestellt wurde, können nur Graphen bearbeitet werden, 
deren Knoten höchstens ein Label haben. In vielen Fällen, wie z.~B. 
Wikipedia mit Kategorien als Labels haben Knoten jedoch viele Labels.

Auf einen ersten Blick ist diese Schwäche einfach zu beheben, indem 
man beim zählen der Labels für jeden Knoten jedes Label zählt. Dann
wäre noch die Frage zu klären, mit wie vielen Labels der betrachtete
Knoten gelabelt werden soll.

Jedoch ist z.~B. bei Wikipedia-Artikeln auf den Knoten eine 
Hierarchie definiert. So ist die Kategorie \enquote{Klassifikationsverfahren}
eine Unterkategorie von \enquote{Klassifikation}. Bei dem Kategorisieren
von Artikeln sind möglichst spezifische Kategorien vorzuziehen, also
kann man nicht einfach bei dem Auftreten der Kategorie \enquote{Klassifikationsverfahren}
sowohl für diese Kategorie als auch für die Kategorie \enquote{Klassifikation}
zählen.


\subsubsection{Überanpassung und Reklassifizierung}
Aggarwal und Li beschreiben in \cite{aggarwal2011} nicht, auf welche
Knoten der Klassifizierungsalgorithmus angewendet werden soll. Jedoch
ist die Reihenfolge der Klassifizierung relevant. Dazu folgendes 
Minimalbeispiel:

Gegeben sei ein dynamischer Graph ohne textuelle Inhalte. Zum Zeitpunkt
$t=1$ habe dieser Graph genau einen Knoten $v_1$ und $v_1$  sei
mit dem Label $A$ beschriftet. Zum Zeitpunkt $t=2$ komme ein nicht-gelabelter
Knoten $v_2$ sowie die Kante $(v_2, v_1)$ hinzu.\\
Nun wird der DYCOS-Algorithmus auf diesen Knoten angewendet und
$v_2$ mit $A$ gelabelt.\\
Zum Zeitpunkt $t=3$ komme ein Knoten $v_3$, der mit $B$ gelabelt ist,
und die Kante $(v_2, v_3)$ hinzu.

\begin{figure}[ht]
    \centering
    \subfloat[$t=1$]{
        \input{figures/graph-t1.tex}
        \label{fig:graph-t1}
    }%
    \subfloat[$t=2$]{
        \input{figures/graph-t2.tex}
        \label{fig:graph-t2}
    }

    \subfloat[$t=3$]{
        \input{figures/graph-t3.tex}
        \label{fig:graph-t3}
    }%
    \subfloat[$t=4$]{
        \input{figures/graph-t4.tex}
        \label{fig:graph-t4}
    }%
    \label{Formen}
    \caption{Minimalbeispiel für den Einfluss früherer DYCOS-Anwendungen}
\end{figure}

Würde man nun den DYCOS-Algorithmus erst jetzt, also anstelle von
Zeitpunkt $t=2$ zum Zeitpunkt $t=3$ auf den Knoten $v_2$ anwenden, so
würde eine $50\%$-Wahrscheinlichkeit bestehen, dass dieser mit $B$ 
gelabelt wird. Aber in diesem Beispiel wurde der Knoten schon
zum Zeitpunkt $t=2$ gelabelt. Obwohl es in diesem kleinem Beispiel
noch keine Rolle spielt, wird das Problem klar, wenn man weitere
Knoten einfügt:

Wird zum Zeitpunkt $t=4$ ein ungelabelter Knoten $v_4$ und die Kanten
$(v_1, v_4)$, $(v_2, v_4)$, $(v_3, v_4)$ hinzugefügt, so ist die 
Wahrscheinlichkeit, dass $v_4$ mit $A$ gelabelt wird bei $\frac{2}{3}$.
Werden die als ungelabelten Knoten jedoch erst jetzt und alle gemeinsam
gelabelt, so ist die Wahrscheinlichkeit für $A$ als Label bei nur $50\%$.
Bei dem DYCOS-Algorithmus findet also eine Überanpassung an vergangene
Labels statt.

Das Reklassifizieren von Knoten könnte eine mögliche Lösung für dieses
Problem sein. Knoten, die durch den DYCOS-Algorithmus gelabelt wurden
könnten eine Lebenszeit bekommen (TTL, Time to Live). Ist diese 
abgelaufen, wird der DYCOS-Algorithmus erneut auf den Knoten angewendet.

\subsection{Schwächen des Papers}
In \cite{aggarwal2011} wurde eine experimentelle Analyse mithilfe 
des DBLP-Datensatzes\footnote{http://dblp.uni-trier.de/} und des
CORA-Datensatzes\footnote{\href{http://people.cs.umass.edu/~mccallum/data/cora-classify.tar.gz}{http://people.cs.umass.edu/~mccallum/data/cora-classify.tar.gz}} durchgeführt.
Die Ergebnisse dieser Analyse können aus folgenden Gründen
nicht überprüft werden:
\begin{itemize}
    \item Der Parameter $a \in \mathbb{N}$, der die Anzahl der ausgehenden Kanten
          aller Wortknoten beschränkt, wird erst mit der Experimentellen
          Analyse auf S.~362 eingeführt.
          Es ist nicht klar, wie entschieden wird welche Kanten
          gespeichert werden und welche nicht.
    \item Für die Analyse der CORA-Datensatzes analysiert.
          Dieser beinhaltet Forschungsarbeiten, wobei die 
          Forschungsgebiete die in einen Baum mit 73 Blättern 
          eingeordnet wurden. Aus diesen 73 Blättern wurden 5 Klassen
          extrahiert und der Graph, der keine Zeitpunkte beinhaltet,
          künstlich in 10 Graphen mit Zeitpunkten unterteilt. Wie
          jedoch diese Unterteilung genau durchgeführt wurde kann nicht
          nachvollzogen werden.
    \item Der auf S. 360 in \enquote{Algorithm 1} vorgestellte
          Pseudocode soll den DYCOS-Algorithmus darstellen. Allerdings
          werden die bereits klassifizierten Knoten $\T_t$ neu klassifiziert
          und mit $\theta$ die Klassifikationsgüte gemessen.
\end{itemize}