Thumbnail

Pixel-based Visual Data Mining in Large Geo-Spatial Point Sets

M. Sips

2005
Dissertation

In vielen Data Mining Szenarios wird es zunehmend wichtiger, Beziehungen und Muster zu explorieren, die durch große geographiebezogene Datenmengen beschrieben werden. Interessante Beispiele sind Kreditkartentransaktionen, bei denen sowohl die Adresse des Verkäufers als auch des Kunden gesichert werden, oder Telefongespräche, bei denen die Adressen und die Koordinaten (Standorte) des Anrufers und des Angerufenen protokolliert werden. Auch in der Demographie und anderen amtlichen Veröffentlichungen werden neben den statistischen Werten auch Adressen und geographische Verzeichnisse verwendet. Diese geographischen Datenbanken werden durch eine Menge von Tupeln, bestehend aus einem Längengrad und einem Breitengrad, sowie einer Menge von statistischen Werten beschrieben. Jedes Tupel repräsentiert eine geographische Position, welcher ein oder mehrere statistische Werte, entsprechend den Messergebnissen bzw. der statistischen Erhebungen für einen geographischen Standort, zugeordnet werden. Eine sehr einfache und weit verbreitete Visualisierungstechnik sind DotMaps, bei denen einfach Punkte an den einzelnen Standorten gezeichnet werden. Ein großes Problem dieser Technik ist das überschreiben von bereits gesetzten Punkten, da geographische Daten sehr unregelmäßig in der realen Welt verteilt sind. Dieses Problem führt dazu, dass lokale Muster durch unerwünschtes Überschreiben von bereits gesetzten Pixel in dichten Regionen (zum Beispiel Ballungszentren) miteinander vermischt werden, während dünn besiedelte Regionen im Gegensatz dazu virtuell leer sind. Diese Situation führt zu neuen Herausforderungen in Hinblick auf die Skalierbarkeit neuer Visualisierungstechniken. Der Hauptbeitrag der vorliegenden Dissertation zur aktuellen Forschung im Bereich geographischer Datenbanken besteht darin, dass haben wir einen neuen Ansatz, PixelMap genannt, zur visuellen Analyse von großen geographischen Datenbanken entwickelt haben. Unser PixelMap-Ansatz kombiniert dabei Clustering-Techniken mit einer neuen pixelbasierenden Visualisierungstechnik. Die Kombination der beiden unterschiedlichen Techniken ermöglicht einerseits eine effiziente Verzerrung der Karte basierend auf einer Approximation der 2-dimensionalen Kernel-Density auf den beiden geographischen Dimensionen, so dass die 3-dimensionalen Punktwolken besser auf die Karte abgebildet werden können, und andererseits eine effiziente Neupositionierung der Datenpunkte. Unser PixelMap-Ansatz besitzt dabei gegenüber einfachen Visualisierungstechniken die folgenden Vorteile: • Kein Überschreiben bereits gesetzter Punkte. • Die Datenpunke werden lokal so platziert, so dass lokale geographische Cluster sichtbar sind. • Die absoluten/relativen Positionierungsfehler werden minimiert, so dass auch die Cluster an den Standorten entstehen, an denen es auch in der realen Welt das Phänomen auftritt. Der Hauptbeitrag der vorliegenden Dissertation besteht darin, dass zwei neuartige Algorithmen zur Berechnung von PixelMap Visualisierungen entwickelt wurden sind. Der erste Algorithmus heißt Fast-PixelMap und er zweite HistoScale-PixelMap. Der Vorteil beider Algorithmen liegt in der effizienten Approximation der 2 Kernel Density Funktionen, basieren aber auf verschieden Ansätzen. Beide Algorithmen sind erfolgreich implementiert. Die Ergebnisse sind im Vergleich zu einer Multi-Objective Optimierung ähnlich, die benötigte Rechenzeit ist im Vergleich um Größenordnungen kleiner. In einem visuellen generieren die vorgestellten Verfahren ästhetisch bessere Visualisierungen. Welcher der beiden Algorithmen zu bevorzugen ist, hängt von der Zielsetzung ab. Die Anwendung beider Algorithmen wird anhand von zahlreichen Beispielen im Kapitel Applications gezeigt.

Materials
Related Publication
thumbnail
IEEE EMBS Visual Information Expert Workshop (VIEW 06), Paris, France, April 24-25, 2006
thumbnail
Workshop on Visualization, Analytics & Spatial Decision Support at the GIScience conference, September 20, 2006, Muenster, Germany, 2006
Title