E-Book, Deutsch, 171 Seiten, eBook
Dehmer Strukturelle Analyse Web-basierter Dokumente
2006
ISBN: 978-3-8350-9135-1
Verlag: Deutscher Universitätsverlag
Format: PDF
Kopierschutz: 1 - PDF Watermark
E-Book, Deutsch, 171 Seiten, eBook
Reihe: Multimedia und Telekooperation
ISBN: 978-3-8350-9135-1
Verlag: Deutscher Universitätsverlag
Format: PDF
Kopierschutz: 1 - PDF Watermark
Matthias Dehmer rückt das Web Structure Mining, insbesondere die strukturelle Analyse Web-basierter Hypertexte auf Grundlage gerichteter Graphen, in den Mittelpunkt seiner Untersuchung. Der Autor stellt ein graphentheoretisches Modell zur Bestimmung der strukturellen Ähnlichkeit einer Klasse von gerichteten Graphen vor. Auf Basis des angesprochenen Modells führt er Experimente mit bestehenden Hypertexten durch und beschreibt neuartige Anwendungen im Web Structure Mining und in anderen Gebieten.
Dr. Matthias Dehmer arbeitet in der Informatik im Bereich der Strukturklassifikation und der Analyse von graphbasierten Netzwerken. In der Mathematik ist er in der diskreten Mathematik (Schwerpunkt Graphentheorie) und in der angewandten Funktionentheorie (Schwerpunkt Nullstellenlokalisierung) tätig.
Zielgruppe
Research
Autoren/Hrsg.
Weitere Infos & Material
1;Vorwort;6
2;Zusammenfassung;8
3;Inhaltsverzeichnis;10
4;Kapitel 1 Einleitung;13
4.1;1.1 Motivation der Arbeit;13
4.2;1.2 Zielsetzung der Arbeit;15
4.3;1.3 Aufbau der Arbeit;17
4.4;1.4 Wissenschaftlicher Beitrag der Arbeit;19
5;Kapitel 2 Strukturelle Aspekte hypertextueller Einheiten;23
5.1;2.1 Hypertext und Hypermedia;23
5.2;2.2 Problemstellungen des Web Mining;26
5.3;2.3 Existierende graphentheoretische Analysemethoden von Hypertextstrukturen;32
5.4;2.4 Existierende Clusteringverfahren zur Analyse hypertextueller Daten;43
5.5;2.5 Modellbildung: Polymorphie und funktionale Äquivalenz;55
5.6;2.6 Konkreter Modellierungsansatz auf der Basis von GXL;57
5.7;2.7 Zusammenfassende Bewertung und Fazit;59
6;Kapitel 3 Grenzen der inhaltsbasierten Kategorisierung von Hypertextstrukturen;63
6.1;3.1 Motivation;63
6.2;3.2 Das Testkorpus und die Extraktion web-basierter Hypertexte;66
6.3;3.3 Motivation des maschinellen Lernverfahrens;68
6.4;3.4 Das Kategorisierungsexperiment;71
6.5;3.5 Interpretation der Evaluierungsergebnisse;74
6.6;3.6 Fazit;76
7;Kapitel 4 Graphentheorie und strukturelle Ähnlichkeit: Bekannte Methoden;79
7.1;4.1 Erforderliche Grundlagen;79
7.2;4.2 Strukturelle Ähnlichkeit von Graphen;87
7.3;4.3 Graph Mining und weitere graphorientierte Ähnlichkeitsmaße;92
7.4;4.4 Zusammenfassende Bewertung;101
8;Kapitel 5 Graphbasierte Analyse und Retrieval: Neuer Ansatz;105
8.1;5.1 Motivation;106
8.2;5.2 Gradsequenzen von Graphen;110
8.3;5.3 Hierarchisierte und gerichtete Graphen;114
8.4;5.4 Zentraler Lösungsansatz;117
8.5;5.5 Berechnungsgrundlagen;120
8.6;5.6 Strukturelle Ähnlichkeit hierarchisierter und gerichteter Graphen;125
8.7;5.7 Ergebnisse;134
8.8;5.8 Experimentelle Ergebnisse;136
9;Kapitel 6 Exkurs: Strukturvorhersage;151
9.1;6.1 Erkennung struktureller Beziehungen zwischen Graphmengen;151
9.2;6.2 Ergebnisse;154
9.3;6.3 Fazit;156
10;Kapitel 7 Zusammenfassung und Ausblick;157
10.1;7.1 Zusammenfassung der Ergebnisse;157
10.2;7.2 Ausblick;160
10.3;7.3 Weiterführende Fragestellungen;163
11;Literaturverzeichnis;165
Strukturelle Aspekte hypertextueller Einheiten.- Grenzen der inhaltsbasierten Kategorisierung von Hypertextstrukturen.- Graphentheorie und strukturelle Ähnlichkeit: Bekannte Methoden.- Graphbasierte Analyse und Retrieval: Neuer Ansatz.- Exkurs: Strukturvorhersage.- Zusammenfassung und Ausblick.
Einleitung (S. 1)
1.1 Motivation der Arbeit
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:
,In der Linguistik wird intensiv die Struktur von Sprache, z.B. die syntaktische Sprachstruktur (Bar-Hillel 1964, Chomsky 1976) untersucht.
,Die soziologische Forschung betrachtet z.B. Kommunikationsstrukturen (Bavelas 1950) und soziale Netzwerke (Harary 1959, 1974, Scott 2001).
,In der Biologie und in der Biochemie spielen z.B. fraktale biologische Strukturen (Sernetz 2001) eine größte Rolle.
,Die Elektrotechnik untersucht Strukturen von Stromverzweigungen, elektrischer Netzwerke und Platinen.
Aus diesen Beispielen geht zunächst nicht hervor, mit welchen Methoden und Formalismen die jeweiligen Strukturen modelliert werden. Da in dieser Arbeit relationale Strukturen in Form von Graphen als Repräsentation komplexer Dokumentstrukturen eine wesentliche Rolle spielen, ist speziell das letzte Beispiel der obigen Aufzählung interessant.
KIRCHOFF (Kirchhoff 1847) publizierte im Bereich der Elektrizitätslehre bereits 1847 eine wichtige Arbeit bezogen auf die Theorie der Stromverzweigungen, die einen Grundstein der modernen Graphentheorie legte. Daran schlossen sich richtungsweisende Beiträge , von CALEY (Caley 1875), PETERSEN (Petersen 1891) und SYLVESTER (Sylvester 1878) an, die ihre Wurzeln ebenfalls in der Graphentheorie besitzen.
Heute ist die Beschreibung von Strukturen ohne graphbasierte Modelle in vielen Wissenschafts- und Lebensbereichen nicht mehr vorstellbar, wobei Graphen in der Informatik, z.B. für die Darstellung von Rechnernetzen, breite Anwendung , finden.
Die vorliegende Arbeit ist thematisch in einem Teilbereich des Web Mining (Chakrabarti 2002, Kosala &, Blockeel 2000)- dem Web Structure Mining (Kosala &, Blockeel 2000)- angesiedelt, weil sie strukturelle Modellierungsaspekte webbasierter , Dokumentstrukturen untersucht.
Da der Umgang mit Computern allgegenwärtig ist und die Menge an Dokumenten im Web bekanntlich exponentiell zunimmt, sind Hilfsmittel zur schnellen Erfassung, Klassifizierung und Auffindung von Dokumenten von zentraler Bedeutung. Längst wurde klar, dass Inhalt und Struktur vernetzter Dokumente hierbei relevant sind. Die vorliegende Arbeit konzentriert sich auf Strukturaspekte web-basierter Dokumente, welche in jüngerer Zeit immer stärker ins Blickfeld rücken.
Es existieren formale Ansätze (dInverno et al. 1997, Fronk 2003, Lange 1990, Mehler 2001), die strukturelle Aspekte hypertextueller Dokumente beschreiben. Die ersten bekannten Arbeiten, die insbesondere die strukturelle Analyse von Hypertexten auf der Basis graphentheoretischer Methoden fokussierten, stammen von (Botafogo &, Shneiderman 1991, Botafogo et al. 1992, Botafogo 1993).
Dabei wurden bekannte Konzepte , der Graphentheorie verwendet, um Maßzahlen- so genannte Indizes (Dehmer 2005, Mehler 2004) - für die Beschreibung struktureller Hypertextausprägungen zu entwickeln. Beispielsweise definierten BOTAFOGO et al. (Botafogo et al. 1992) als einen typischen Vertreter das bekannte Maß Compactness , welches den Grad der Vernetztheit einer Hypertextstruktur beschreibt.
Die Aussagekraft solcher Maße ist jedoch sehr eingeschränkt, da die zu beschreibende Ausprägung auf eine einzige Maßzahl abgebildet wird. Damit folgt weiter, dass solche Maße nicht eindeutig interpretierbar sind.
Unmittelbar daraus resultiert ein Problem, welches sich bislang negativ auf die Analyse hypertextueller Dokumente auswirkte (Dehmer 2005): Wegen der nicht eindeutigen Interpretierbarkeit und der damit verbundenden mangelnden Aussagekraft dieser Maße, ist eine Gruppierungähnlicher Strukturen nicht möglich, mit dem Ziel, ähnliche Funktionen oder sogar Qualitätsmerkmale abzuleiten.
