mirror of
https://github.com/MartinThoma/LaTeX-examples.git
synced 2025-04-19 11:38:05 +02:00
81 lines
3.7 KiB
TeX
81 lines
3.7 KiB
TeX
Bei der Anwendung des in \cite{aggarwal2011} vorgestellten Algorithmus auf
|
|
reale Datensätze könnten zwei Probleme auftreten, die im Folgenden erläutert
|
|
werden. Außerdem werden Verbesserungen vorgeschlagen, die es allerdings noch zu
|
|
untersuchen gilt.
|
|
|
|
\subsection{Anzahl der Knotenbeschriftungen}
|
|
So, wie der DYCOS-Algorithmus vorgestellt wurde, können nur Graphen bearbeitet
|
|
werden, deren Knoten jeweils höchstens eine Beschriftung haben. In vielen
|
|
Fällen, wie z.~B. Wikipedia mit Kategorien als Knotenbeschriftungen haben
|
|
Knoten jedoch viele Beschriftungen.
|
|
|
|
Auf einen ersten Blick ist diese Schwäche einfach zu beheben, indem man beim
|
|
zählen der Knotenbeschriftungen für jeden Knoten jedes Beschriftung zählt. Dann
|
|
wäre noch die Frage zu klären, mit wie vielen Beschriftungen der betrachtete
|
|
Knoten beschriftet 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.
|
|
|
|
|
|
\subsection{Ü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 $A$
|
|
beschriftet. Zum Zeitpunkt $t=2$ komme ein nicht beschrifteter 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$
|
|
beschriftet.\\
|
|
Zum Zeitpunkt $t=3$ komme ein Knoten $v_3$, der mit $B$ beschriftet ist, und
|
|
die Kante $(v_2, v_3)$ hinzu. \Cref{fig:Formen} visualisiert diesen Vorgang.
|
|
|
|
\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}
|
|
}%
|
|
\caption{Minimalbeispiel für den Einfluss früherer DYCOS-Anwendungen}
|
|
\label{fig:Formen}
|
|
\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
|
|
\SI{50}{\percent}-Wahrscheinlichkeit bestehen, dass dieser mit $B$ beschriftet
|
|
wird. Aber in diesem Beispiel wurde der Knoten schon zum Zeitpunkt $t=2$
|
|
beschriftet. 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 unbeschrifteter 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$ beschriftet wird bei $\frac{2}{3}$.
|
|
Werden die unbeschrifteten Knoten jedoch erst jetzt und alle gemeinsam
|
|
beschriftet, so ist die Wahrscheinlichkeit für $A$ als Beschriftung bei nur $50\%$.
|
|
Bei dem DYCOS-Algorithmus findet also eine Überanpassung an vergangene
|
|
Beschriftungen statt.
|
|
|
|
Das Reklassifizieren von Knoten könnte eine mögliche Lösung für dieses
|
|
Problem sein. Knoten, die durch den DYCOS-Algorithmus beschriftet wurden
|
|
könnten eine Lebenszeit bekommen (TTL, Time to Live). Ist diese
|
|
abgelaufen, wird der DYCOS-Algorithmus erneut auf den Knoten angewendet.
|