Semantische Netze haben sich als eines der erfolgreichsten Konzepte für die Darstellung und Verarbeitung von Wissen in dem Kontext der automatischen Wissensverarbeitung erwiesen. Während die textuelle Repräsentation eines semantischen Netzes sich sehr gut für die automatische Verarbeitung eignet, unterstützt die visuelle Darstellung in Form einer Grafik das Verständnis eines menschlichen Betrachters.
Einzelne Wissenselemente und die Beziehungen zwischen ihnen werden als Knoten und Kanten eines verallgemeinerten Graphen abgebildet, so dass sich das Zeichnen eines semantischen Netzes auf das Zeichnen von Graphen zurückführen lässt. Bei dem rechnergestützten Zeichnen von Graphen besteht die Aufgabe darin, zu einem gegebenen Graphen (als Menge von Knoten und Kanten) die Positionen der Knoten, Kanten und Beschriftungen so zu ermitteln, dass die Darstellung ästhetischen Anforderungen genügt.
Zur Unterstützung der praktischen Arbeit mit semantischen Netzen wurden in dem Lehrgebiet Praktische Informatik VII der FernUniversität in Hagen bereits mehrere Anwendungen entwickelt, die Module für die grafische Darstellung von semantischen Netzen mit einschließen. Trotz der umfassenden Möglichkeiten dieser Anwendungen bestehen noch Lücken in der Berücksichtigung aller Darstellungsmittel von semantischen Netzen, beispielsweise bei mehrstelligen Funktionen. Insbesondere die Platzierung von Beschriftungen zeigt deutlichen Optimierungsbedarf, damit durch weniger Überschneidungen die Beschriftungen besser lesbar werden (s. Abbildung 1). Auch hinsichtlich der Berechnung der Darstellung von großen Netzen mit mehreren Hundert Knoten ist eine deutliche Verbesserung der Qualität wünschenswert und möglich.
Inhaltsverzeichnis
1 Einleitung
1.1 Motivation
1.2 Ziele
1.3 Vorgehen
2 Semantische Netze
2.1 Grundlagen der Wissensrepräsentation
2.2 Darstellungsmittel semantischer Netze
2.2.1 Einfache semantische Netze
2.2.2 Erweiterte semantische Netze
2.2.3 Mehrschichtige erweiterte semantische Netze
2.3 Funktionen und Relationen
2.3.1 Zweistellige Relationen
2.3.2 Reflexive Relationen
2.3.3 Einstellige Funktionen
2.3.4 Mehrstellige Funktionen
3 Graphen zeichnen
3.1 Grundlagen
3.1.1 Kräftebasierte Methoden
3.1.2 Energiebasierte Methoden
3.1.3 Andere Methoden
3.2 Beschriftung von Graphen
3.3 Qualitätskriterien
3.4 Lauftzeitkomplexität
4 Graphendarstellung für MultiNet
4.1 Bisherige Funktionalität
4.1.1 MWR
4.1.2 RETE
4.1.3 Vergleich von MWR-Layout und RETE_view
4.2 Erweiterung der Darstellungsmittel
5 Konzeption
5.1 Layout
5.2 Beschriftungen
5.2.1 Kantenbeschriftungen
5.2.2 Knotenbeschriftungen
5.3 Ausgabeformat
5.4 Statistikmodul
6 Technische Realisierung
6.1 Vorgaben
6.2 Design der Anwendung
6.3 Klassenstruktur
7 Evaluierung
7.1 Qualität
7.2 Laufzeiten
8 Ergebnisse
8.1 Fazit
8.2 Ausblick
Zielsetzung & Themen
Ziel dieser Arbeit ist die Verbesserung des automatischen Zeichnens von mehrschichtigen erweiterten semantischen Netzen (MultiNet). Die Forschungsfrage konzentriert sich darauf, wie durch Optimierung bestehender Algorithmen ein ästhetisch ansprechendes Layout und eine überschneidungsfreie Platzierung von Beschriftungen in großen Netzen realisiert werden kann, um die visuelle Wissensrepräsentation und Lesbarkeit maßgeblich zu steigern.
- Analyse und Vergleich gängiger Algorithmen zum automatischen Zeichnen von Graphen.
- Entwicklung eines verbesserten Layout-Modells auf Basis der Spring-Embedder-Methode.
- Konzeption effizienter Strategien für die Platzierung von Knoten- und Kantenbeschriftungen.
- Technische Realisierung und Integration eines Statistikmoduls zur objektiven Qualitätsbewertung.
- Evaluierung der Leistungsfähigkeit und Laufzeitoptimierung für große semantische Netzstrukturen.
Auszug aus dem Buch
3.1.1 Kräftebasierte Methoden
Viele Methoden für das Erstellen eines Graphen-Layouts basieren auf Analogien zu physikalischen Systemen. Wegen dieser Beziehung zu der uns umgebenden physikalischen Welt erscheinen die Ergebnisse intuitiv gut nachvollziehbar. Zudem ist die ästhetische Darstellung für Graphen mit unter 50 Knoten akzeptabel.
Im Allgemeinen besteht eine solche Layout-Methode aus zwei Komponenten: einem Modell und einem Algorithmus. Das Modell repräsentiert physikalische Objekte und die Interaktionen (bzw. Kräfte) zwischen ihnen, was in einem Graphen G=(V, E) als Knoten und Kanten abgebildet wird. Der Algorithmus ist eine Berechnungsvorschrift, die einen Gleichgewichtszustand zwischen den Kräften des Modells herzustellen versucht. Dabei wird davon ausgegangen, dass ein Zustand des Systems mit minimaler Gesamtenergie ein adäquates Layout liefert und daher erstrebenswert ist.
Wie das adäquate Layout genau aussieht, hängt entscheidend von der Ausprägung des Modells ab. Der Algorithmus dient lediglich dazu, die Eigenschaften des Modells umzusetzen bzw. zu optimieren.
Für eine ästhetisches Gestaltung des Layouts werden zwei Rahmenkriterien mitgegeben, über die ein allgemeiner Konsens besteht: 1. die Knoten sollen gleichmäßig auf der Zeichenfläche verteilt sein und 2. durch eine Kante verbundene Knoten sollen nah beieinander liegen.
Äquivalente physikalische Phänomene existieren für beide Kriterien. Eine gleichmäßige Verteilung der Knoten auf der Fläche entspricht abstoßenden Kräften zwischen den Knoten, wie sie in magnetischen oder elektrischen Feldern vorkommen. Das zweite Kriterium findet seine Umsetzung in Form von Federn, die im Modell als Kanten zwischen den Knoten eingesetzt werden. Federn besitzen mehrere Eigenschaften, die der Modellierung zugute kommen: sie besitzen ein konstante natürliche Länge, für die im Modell der gewünschte ideale Knotenabstand eingesetzt werden kann. Ferner besitzen Federn Kräfte, die sie bei einer Verformung auf ihre natürliche Länge zurückbringen wollen. Dies gilt sowohl für die Dehnung als auch für die Stauchung einer Feder, und zwar umso mehr, je stärker ihre Länge von ihrer natürlichen Länge abweicht. Die Modellierung mit elektrischen Kräften und Federn geht auf Eades zurück und ist heute unter dem Namen „Spring Embedder“ bekannt.
Zusammenfassung der Kapitel
1 Einleitung: Beschreibt die Motivation für die visuelle Darstellung semantischer Netze, definiert die Ziele der Arbeit und erläutert das Vorgehen.
2 Semantische Netze: Führt in die Grundlagen der Wissensrepräsentation ein und erläutert die Syntax und Semantik mehrschichtiger erweiterter semantischer Netze.
3 Graphen zeichnen: Diskutiert graphentheoretische Ansätze für das Layout von Graphen, einschließlich kraft- und energiebasierter Methoden sowie Fragen der Beschriftung.
4 Graphendarstellung für MultiNet: Analysiert bestehende Anwendungen (MWR, RETE) für die Arbeit mit MultiNet und identifiziert Verbesserungspotenziale.
5 Konzeption: Präsentiert den Entwurf des verbesserten Layout-Algorithmus sowie Strategien zur Beschriftung und das Speicherformat für Layout-Informationen.
6 Technische Realisierung: Beschreibt die technische Umsetzung der Konzepte in Form einer Java-Applet-Erweiterung und die Klassenstruktur der Anwendung.
7 Evaluierung: Bewertet die Qualität und Laufzeit des entwickelten Layout-Algorithmus anhand definierter Kriterien und vergleicht ihn mit den Ausgangssystemen.
8 Ergebnisse: Fasst die Errungenschaften der Arbeit zusammen und gibt einen Ausblick auf zukünftige Erweiterungsmöglichkeiten.
Schlüsselwörter
Semantische Netze, MultiNet, Graphenlayout, Spring-Embedder-Algorithmus, Wissensrepräsentation, Graphentheorie, Beschriftung, Knoten, Kanten, Java-Applet, Qualitätskriterien, Wissensverarbeitung, Informatik, Layout-Algorithmus, Kraftsimulation.
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit beschäftigt sich mit der Optimierung der grafischen Darstellung von mehrschichtigen erweiterten semantischen Netzen (MultiNet), um deren Lesbarkeit und ästhetische Qualität bei großen Datenmengen zu verbessern.
Welche zentralen Themenfelder werden behandelt?
Zentrale Themen sind Wissensrepräsentation, Algorithmen zum Zeichnen von Graphen, Optimierung der Beschriftungsplatzierung und die interaktive Darstellung innerhalb von Softwareanwendungen.
Was ist das primäre Ziel der Forschungsarbeit?
Das primäre Ziel ist der Entwurf und die Implementierung eines Layout-Algorithmus, der auch bei großen Netzwerken eine überschneidungsfreie und visuell klare Darstellung ermöglicht.
Welche wissenschaftlichen Methoden werden verwendet?
Es werden kräftebasierte Methoden der Graphenzeichnung (physikalische Analogien) eingesetzt, mit spezifischen Anpassungen für die Besonderheiten semantischer Netze wie Mehrfachkanten und komplexe Beschriftungsmodelle.
Was wird im Hauptteil der Arbeit behandelt?
Der Hauptteil umfasst die theoretischen Grundlagen semantischer Netze, die Analyse bestehender Algorithmen, die Konzeption einer verbesserten Layout- und Beschriftungsstrategie sowie deren technische Realisierung.
Welche Schlüsselwörter charakterisieren die Arbeit?
Die Arbeit lässt sich am besten mit Begriffen wie semantische Netze, MultiNet, Spring-Embedder-Algorithmus, Graphenlayout und Wissensrepräsentation beschreiben.
Wie unterscheidet sich der neue Ansatz vom MWR-Layout?
Im Gegensatz zum MWR-Layout, das auf festen Abständen basiert, verwendet der neue Ansatz physikalische Kräfte, um eine dynamische und weniger fehleranfällige Anordnung der Knoten zu erreichen.
Was wurde durch das Statistikmodul ermöglicht?
Das Statistikmodul ermöglicht eine objektive, prozentuale Qualitätsbewertung des berechneten Graphenlayouts auf Basis messbarer Faktoren wie Kanten- und Beschriftungsüberschneidungen.
Warum spielt die Komplexität der Beschriftung eine wichtige Rolle?
Da die optimale Platzierung von Beschriftungen ein NP-vollständiges Problem darstellt, war es notwendig, einen effizienten, heuristischen Algorithmus mit Linearzeit-Komplexität für interaktive Anwendungen zu entwickeln.
- Citation du texte
- Fabian Aiteanu (Auteur), 2006, Entwurf und Implementierung eines Layout-Algorithmus für mehrschichtige erweiterte semantische Netze, Munich, GRIN Verlag, https://www.grin.com/document/65936
