Parameterfreies hierarchisches Graph-Clustering-Verfahren zur Interpretation raumbezogener Daten

Abstract

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.

Nowadays, the necessity of automatic interpretation and analysis of spatial data is getting more and more important, because the amount of digital spatial data continuously increases. On the one hand, there are raster data sets, on the other hand vector data that are predominantly based on different landscape models. Differences between these landscape models are, e.g., the object type, the degree of generalization or the geometric accuracy of the captured landscape objects. The pure interactive processing and analysis of large spatial databases is very time-consuming and expensive. Especially the manual analysis of spatial data for the purpose of data revision will reach the limit of technical feasibility in the near future, because modern requirements on the up-to-dateness of data lead to ever shorter update cycles.

The automatic interpretation of digital landscape models needs the integration of methods of the field of spatial data mining or knowledge discovery in spatial databases into geographical information systems (GIS), which is the focus of this thesis. In general, the automatic interpretation of a digital landscape model (DLM) can be divided into the interpretation based on a specific model of the DLM, the interpretation based on a generic model of the basic elements of the DLM and the unsupervised interpretation of the DLM.

First, an approach for the generation of 3D building hypotheses from a cadastral map is described which is an example for the DLM interpretation based on a specific model. This approach can be used for the fast generation of approximate 3D city models or as pre-information for an image based 3D building reconstruction. Secondly, an approach for the automatic derivation of ATKIS data from ALK data will be described in detail, which is an example for the DLM interpretation based on a generic model of the basic DLM elements for the purpose of automatic data revision. Both approaches lead directly to the basic problem of grouping spatial objects, which can be seen as a general clustering problem. Clustering methods can be divided into supervised and unsupervised methods. Unsupervised clustering or learning methods can be used for the third case of DLM interpretation. Especially unsupervised clustering methods are well suited for the model generalization and the cartographic generalization of DLM data if these methods can recognize clusters of arbitrary shape. There are a lot of different clustering approaches, but most of them need certain prerequisites, like the distribution function of the data or thresholds for similarity tests and terminating conditions. In many cases, clustering methods can only find clusters with a convex shape and without holes (e.g. maximum-likelihood).

The main contribution of this thesis is a new unsupervised clustering method called Hierarchical Parameter-free Graph CLustering (HPGCL) for the automatic interpretation of spatial data. The HPGCL algorithm can find clusters of arbitrary shape and needs neither parameters like thresholds nor an assumption about the distribution of the data or number of clusters. The novelty of the HPGCL algorithm lies on the one hand in the application of the hierarchy of neighbourhood graphs (also called proximity graphs) to define the neighbourhood of a single object and object clusters in a natural and common way and on the other hand in the definition of a median based, threshold free decision criteria for the similarity of clusters. In the HPGCL algorithm the Nearest-Neighbour-Graph, the Minimum-Spanning-Tree, the Relative-Neighbourhood-Graph, the Gabriel-Graph and the Delaunay-Triangulation are used. It will be shown that the hierarchical relationship of these proximity graphs can be used for a natural generalization process in the sense of a coarse-to-fine segmentation of a data set. One additional feature of the HPGCL algorithm is that in general a limiting number of clusters greater than one will be found. In contrast, general hierarchical cluster algorithms require the minimal number of clusters as a parameter, otherwise they will always group all objects of a data set in one big cluster. The influence of the single proximity graphs of the hierarchy on the clustering result is investigated in detail. The usability of the HPGCL algorithm is evaluated on different types of data sets and for two data sets the results of the HPGCL algorithm are compared with manual clustering results.