Strukturelle Analyse Web-basierter Dokument

Die Untersuchung von Strukturen ist aus der Sicht vieler Wissenschaftsbereiche ein aktuelles Forschungsthema. Dabei ist die Strukturanalyse einerseits in anwendungsorientierten Disziplinen und andererseits in theorieorientierten Forschungsbereichen von zentraler Bedeutung:

Die Anwendung von klassischen Data Mining-Konzepten (Han & Kamber 2001) auf web-basierte Daten, wie z.B. die Cluster analyse, wird als Web Mining (Chakrabarti 2002) bezeichnet. Ein Teilbereich des Web Mining, der in dieser Arbeit besonders im Vordergrund steht, ist das Web Structure Mining, welches die Aufdeckung und die Erforschung struktureller Aspekte web-basierter Hypertexte zum Hauptziel hat. Ausgehend von einer kurzen Darstellung der Grundlagen von Hypertext und Hypermedia in Kapitel (2.1) hat das vorliegende Kapitel (2) das Ziel, eine verstandliche Einfuhrung von Data Mining-Konzepten im Hinblick auf die Anwendung im Web Mining zu geben. Das Teilgebiet Web Structure Mining wird dabei besonders hervorgehoben, insbesondere graphentheoretische Methoden zur strukturellen Analyse von Hypertexten.

Obwohl sich die vorliegende Arbeit auf die struktur- und graphbasierte Analyse hypertextueller Dokumente konzentriert, wurden umfangreiche Teilarbeiten auch zur inhaltsbasierten Kategorisierung durchgeführt. Insbesondere erhält man dadurch ein besseres Verst↭dnis für die Abgrenzung, sowie für die Möglichkeiten und Grenzen der beiden Teilbereiche. Im klassischen Sinne ist der wissenschaftliche Beitrag dieses Kapitels daher auch ein „Negativergebnis“. Wie im Verlauf des Kapitels klar wird, wurden dazu sowohl mathematisch-theoretische Arbeit en als auch softwaretechnische Entwicklungen und darauf aufbauende Experimente durchgeführt. Ausgehend von einer Motivation der Problemstellung in Kapitel (3.1) wird in Kapitel (3.2) die web-basierte Extraktion und die Konstruktion des verwendeten Testkorpus T_C detailliert dargestellt. Da das eigentliche Kategorisierungsexperiment auf der Basis eines maschinellen Lernverfahrens durchgeführt wurde, erfolgt dessen Motivation in Kapitel (3.3). In Kapitel (3.4) wird das Experiment mathematisch-theoretisch charakterisiert. Mit der Interpretation der Evaluierungsergebnisse und einem Fazit schliefit dieses Kapitel ab.

Die Anwendung und die Entwicklung graphentheoretischer Methoden nehmen in dieser Arbeit einen großen Raum ein. Deshalb wird in diesem Kapitel in der gebotenen Kürze ein Überblick über die Graphentheorie und deren Anwendungsgebiete gegeben, um die in dieser Arbeit entwickelten Methoden fachlich einordnen zu können. Ausgehend von der Definition graphentheoretischer Begriffe, wird in diesem Kapitel weiterhin der Ähnlichkeits-Begriff hinsichtlich strukturierter Objekte erklärt. In Vorbereitung auf die Motivation und die Entwicklung des Graphähnlichkeitsmodells in Kapitel (5), erfolgt in Kapitel (4.1.2) eine ausführliche Diskussion bekannter Methoden zur Bestimmung der strukturellen Ähnlichkeit von Graphen. Kapitel (4.3) beschäftigt sich mit Graph Mining-Konzepten und bekannten Methoden zur Ähnlichkeitsbestimmung web-basierter Dokument-strukturen.

Die Bestimmung der strukturellen Ähnlichkeit von Graphen stellt ein herausforderndes Problem dar. Besonders bei ähnlichkeitsbasierten Graphanalysen auf großen Datenbeständen, wobei die Graphen von höherer Ordnung sind, ist die Konstruktion von effizienten und aussagekräftigen Ähnlichkeitsmaßen schwer. Im vorliegenden Kapitel (5) wird nun die Motivation und mathematische Modellierung einer neuen Methode zur effizienten Bestimmung der strukturellen Ähnlichkeit hierarchisierter und gerichteter Graphen angegeben. Sie ist auf Grund ihrer Konzeption für das web-basierte Graphmatching hinsichtlich Massendaten geeignet. Zum einen besteht das Hauptziel dieses neuen Ansatzes in der Umgehung von graphentheoretischen Modellen, die auf Isomorphie- oder Untergraphisomor-phiebeziehungen aufbauen. Zum anderen wird die Entwicklung eines unüberwachten und parametrischen Verfahrens angestrebt, welches die strukturelle Ähnlichkeit auf der Basis ganzheitlicher Graphvergleiche bestimmt. Kapitel (5.1) stellt zunächst die grundlegende Motivation aus anwendungsorientierter und mathematischer Sicht dar. Ausgehend von weiterführenden graphentheoretischen Begriffen und Konstruktionen, die in den Kapiteln (5.2), (5.3) definiert werden, diskutiert Kapitel (5.4) den zentralen Lösungsansatz. Da das neue Verfahren auf einem Algorithmus basiert, welcher auf dynamischer Programmierung beruht, werden die erforderlichen Hilfsmittel in Kapitel (5.5) eingeführt. Mit der eigentlichen Konstruktion der Graphähnlichkeitsmaße in Kapitel (5.6) und einem experimentellen Teil in Kapitel (5.8) schließt das Kapitel (5) ab.

In Kapitel (5.8.1) wurde auf Basis der Website-Strukturen die Fragestellung untersucht, ob das Graphähnlichkeitsmaß d₃ mit Hilfe eines agglomerativen Clusteringverfahrens in der Lage ist, homogene und aussagekräftige Cluster zu bilden. Da jedoch die Ähnlichkeitswertverteilungen der aus dem WWW extrahierten Website-Strukturen unbekannt sind, kann die Interpretation von Clustering-Experimenten problematisch sein. Daher wird im Folgenden auf der Grundlage bekannter Ähnlichkeitswertverteilungen die über Kapitel (5.8.1) hinausgehende Problemstellung betrachtet, ob mit Hilfe von d₃ strukturelle Beziehungen zwischen vorgegebenen Graphmengen detektiert werden können.

Kapitel (7) fasst die Ergebnisse dieser Arbeit zusammen. Darüber hinaus werden in Form eines Ausblicks Bereiche angegeben, in denen das Hauptergebnis der Arbeit, das Graphähnlichkeitsmodell für hierarchisierte und gerichtete Graphen, über die Kapitel (5.8.1), (5.8.2), (6) hinaus zukünftig Anwendung finden kann. Abschließend werden weiterführende Fragestellungen und Ansatzpunkte für zukünftige Untersuchungen aufgezeigt.