Parameterfreies hierarchisches Graph-Clustering-Verfahren zur Interpretation raumbezogener Daten

Die Notwendigkeit der automatischen Interpretation und Analyse von räumlichen Daten wird heutzutage immer wichtiger, da eine stetige Zunahme der digitalen räumlichen Daten zu verzeichnen ist. Dies betrifft auf der einen Seite Rasterdaten wie auch auf der anderen Seite Vektordaten, welche überwiegend auf unterschiedlichen Landschaftsmodellen basieren. Differenzen zwischen diesen Landschaftsmodellen bestehen u.a. in den Objektarten, dem Grad der Generalisierung oder der geometrischen Genauigkeit der gespeicherten Landschaftsobjekte. Die interaktive Prozessierung und Analyse von großen Datenbeständen ist sehr zeitaufwendig und teuer. Speziell die manuelle Analyse räumlicher Daten zum Zwecke der Datenrevision wird in Zukunft das Limit der technischen Umsetzbarkeit erreichen, da moderne Anforderungen an die Laufendhaltung der Daten zu immer kürzeren Aktualisierungszyklen führen. Die automatische Interpretation digitaler Landschaftsmodelle setzt die Integration von Methoden des räumlichen Data Mining bzw. Knowledge Discovery in raumbezogenen Daten innerhalb von Geographischen Informationssystemen (GIS) voraus. Zunächst beschreiben wir einen Ansatz zur Generierung von 3D-Gebäuden, welche als Hypothese aus Katasterkarten abgleitet werden. Diese Vorgehensweise stellt ein Beispiel für die DLM-Interpretation auf der Grundlage eines spezifischen Modells dar und kann zur schnellen Generierung von groben 3D-Stadtmodellen oder als Vorabinformation zur bildgestützten 3D-Gebäuderekonstruktion verwendet werden. Des weiteren stellen wir detailliert einen Ansatz zur Ableitung von ATKIS-Daten aus ALK-Daten vor, welcher ein Beispiel für die DLM-Interpretation basierend auf einem generischen Modell der DLM-Basiselemente darstellt und zur automatischen Laufendhaltung der Daten dient. Beide Ansätze führen direkt zum grundsätzlichen Problem der Gruppierung von räumlichen Objekten, welches generell unter dem Begriff des Clusterns zusammengefasst wird. Man unterscheidet zwei Arten von Clusterverfahren: überwachte und unüberwachte Methoden. Unüberwachte Cluster- oder Lernverfahren können für den dritten genannten Fall der DLM-Interpretation verwendet werden und sind gut geeignet für die Modellgeneralisierung und die kartographische Generalisierung von DLM-Daten, falls die Methoden in der Lage sind, Cluster mit beliebiger Form zu erkennen. Die bisher existierenden Verfahren benötigen jedoch zumeist verschiedenste Kenntnisse als Voraussetzung, wie z.B. die Verteilungsfunktion der Daten oder Schrankenwerte für Ähnlichkeitsmessungen bzw. Abbruchkriterien. Zudem finden viele Clusterverfahren nur Gruppierungen mit konvexer Form und erkennen keine Löcher (z.B. Maximum-Likelihood-Methoden). Der Hauptteil dieser Arbeit widmet sich einem neu entwickelten, unüberwachten Clusterverfahren zur automatischen Interpretation von raumbezogenen Daten. Das Verfahren heißt Hierarchisches Parameterfreies Graph-CLustering (HPGCL) und dient zur Erkennung von Clustern beliebiger Form. Es benötigt weder Parameter wie z.B. Schrankenwerte noch Annahmen über die Verteilung der Daten oder die Anzahl der Cluster. Die Neuartigkeit des HPGCL-Algorithmus besteht auf der einen Seite in der Anwendung der Hierarchie von Nachbarschaftsgraphen zur Definition der Nachbarschaft eines Einzelobjekts oder eines Objektclusters in allgemeiner Art und Weise, sowie auf der anderen Seite in der Definition eines Entscheidungskriteriums zur Ähnlichkeitsbestimmung von Clustern, welches medianbasiert ist und ohne Angabe von Schwellwerten auskommt. Der Nächste-Nachbar-Graph, der Minimal Spannende Baum, der Relative Nachbarschaftsgraph, der Gabriel-Graph und die Delaunay-Triangulation kommen im HPGCL-Algorithmus zum Einsatz. Es wird aufgezeigt, dass die hierarchische Beziehung dieser Nachbarschaftsgraphen in einem natürlichen Generalisierungsprozess im Sinne einer grob-zu-fein-Segmentierung eines Datensatzes genutzt werden kann. Als weiterer Aspekt des HPGCL-Algorithmus kann die Tatsache genannt werden, dass im allgemeinen eine begrenzte Anzahl von Clustern größer eins gefunden wird. Im Gegensatz dazu benötigen andere hierarchische Clusterverfahren generell die Minimalanzahl der zu findenden Cluster als Parameter, da ohne Abbruchkriterium sonst alle Objekte des Datensatzes in einem einzigen großen Cluster vereinigt werden. Die Arbeit untersucht detailliert den Einfluss eines einzelnen Nachbarschaftsgraphen in der Hierarchie auf das Ergebnis des Clusterings, und es wird die Verwendbarkeit des HPGCL-Algorithmus auf der Grundlage von verschiedenen Datensatztypen evaluiert. Anhand zweier Datensätze werden die Ergebnisse des HPGCL-Verfahrens mit den Resultaten eines durch Testpersonen durchgeführten manuellen Clusterings verglichen.

Author dc:creator

• Anders, Karl-Heinrich

Advisor dc:contributor.advisor

• Fritsch, Dieter (Prof. Dr.-Ing.)

Statement dc:rights

• info:eu-repo/semantics/openAccess

Language dc:language.iso

de

Identifier URI

http://elib.uni-stuttgart.de/handle/11682/3705
http://dx.doi.org/10.18419/opus-3688

Dc Identifier Other

114821089

OAI identifier oai:identifier

oai:elib.uni-stuttgart.de:11682/3705