Exploring movement using similarity analysis

Abstract

Bewegung ist ein (lebens)notwendiger Aspekt von fast allen Organismen und vieler räumlich-zeitlicher Prozesse. Daher ist es äusserst wichtig, das Konzept Bewegung zu verstehen und unser Wissen über Bewegungsmuster zu erweitern. In letzter Zeit haben Fortschritte diverser Ortungstechnologien uns den Zugang zu immens grossen Mengen von Bewegungsdaten eröffnet. Dieser Schatz von Daten stellt Forschende aber auch vor die Herausforderung, neue explorative Werkzeuge und Methoden der Erkenntnisgewinnung (Knowledge Discovery) zu entwickeln, um nützliche Informationen extrahieren, interessante Muster entdecken und dynamisches Verhalten von beweglichen Objekten (z.B. Menschen, Fahrzeuge, Schiffe, Tiere) oder von Prozessen (z.B. Hurrikane, Ölteppiche) analysieren zu können. Unter den Verfahren der Knowledge Discovery ist die Analyse von Ähnlichkeiten im Bewegungsverhalten mehrerer Objekte von grossem und wachsendem Interesse. Das Wissen über solche Bewegungsähnlichkeiten nützt der Vorhersage, der Modellierung und der Simulation von gemeinschaftlichem Verhalten dynamischer Phänomene und Objekte. Die vorliegende Dissertation zielt darauf ab, einen Beitrag zu den exploratorischen Ansätzen der Geographischen Informationswissenschaft zu leisten, so dass diese neues Wissen über Bewegungsmuster und über Ähnlichkeiten zwischen den Bewegungsverhalten unterschiedlicher Objekte erarbeiten kann. Das spezifische Ziel der Arbeit ist die Entwicklung von Konzepten und Methoden, um Bewegungsparameter wie zum Beispiel Geschwindigkeit, Beschleunigung oder Richtung bei der Analyse von Bewegungen miteinzubeziehen. Daher ist der Begriff der Bewegungsähnlichkeit in dieser Dissertation als die Ähnlichkeit von zeitabhängigen Variationen in den genannten Bewegungsparametern von bewegten Objekten definiert. Im Hinblick auf Bewegung als Untersuchungsgegenstand folgt die vorliegende Untersuchung einem dreiteiligen Forschungsprozess. Dieser besteht aus der Entwicklung von (a) einem konzeptionellen Rahmen, (b) Merkmalsextraktions- und Segmentierungsmethoden und (c) Techniken zur Beurteilung von Bewegungsähnlichkeit. Die Untersuchung benutzt dafür einen iterativen Forschungsprozess, der quantitative Ansätze aus der Geographischen Informationswissenschaft mit Ansätzen der Knowledge Discovery kombiniert, um aus Bewegungsrohdaten Informationen auf einem hohen konzeptionellen Niveau ableiten zu können. Der Kern des Forschungsvorhabens wird in vier wissenschaftlichen Artikeln präsentiert. Forschungsartikel 1 stellt einen konzeptionellen Rahmen zur Bewegungsanalyse und eine umfassende Klassifikation von Bewegungsmustern vor. Forschungsartikel 2 führt einen Segmentierungsansatz ein, der es erlaubt Bewegungsmerkmale aus Trajektorien bewegter Objekte zu extrahieren. Der Segmentierungsprozess kann als Werkzeug zur Reduktion der Dimensionalität des Problems verstanden werden. Er vereinfacht die Struktur von Bewegungsdaten und ermöglicht dadurch die Knowledge Discovery. Forschungsartikel 3 schlägt einen neuen Ansatz zur Beurteilung von Bewegungsähnlichkeit vor, der auf dem Segmentierungsansatz aufbaut. Schliesslich erweitert Forschungsartikel 4 die Dimensionalität des Ansatzes in Richtung der Detektion von relativen Bewegungsmustern. Zusätzlich zeigt die vorliegende Dissertation durch eine Serie von Experimenten, dass die entworfene Methodik zusammen mit Data-Mining-Techniken angewendet werden kann, um Knowledge Discovery in verschiedenartigen Bewegungsdaten (zum Beispiel aus den Gebieten der Verkehrsanalyse oder der Meteorologie) erfolgreich zu unterstützen. Die Resultate dieser Dissertation tragen daher zur Knowledge Discovery in Bewegungsdaten mit Fokus auf die Extraktion oder Gruppierung ähnlichen Bewegungsverhaltens mehrerer dynamischer Objekte bei.


Movement is a vital aspect of almost all organisms and many spatio-temporal processes. Hence it is crucial to understand movement and gain knowledge about its patterns. Recent advances in positioning technologies provide an increasing access to massive repositories of movement data and hence challenges arise to develop new exploratory tools and knowledge discovery techniques in order to extract meaningful information, discover interesting patterns, and explore the dynamic behavior of moving objects (humans, vehicles, vessels, animals) or processes (hurricanes, oil spills). Among knowledge discovery techniques, the exploration of similarities in the movement of multiple objects is a key emerging interest. Learning about movement similarities can be beneficial in the prediction, modeling and simulation of collective behavior of dynamic phenomena. This thesis intends to contribute to GIScience’s exploratory capacity to discover insights about patterns of movement as well as existing similarities between movement behaviors of different objects. Specifically, the aim is to develop concepts and methods for incorporating movement parameters such as speed, acceleration, or direction in the study and analysis of movement. Hence in this thesis, movement similarity is defined as the resemblance in the variations of movement parameters of objects over time. This study, with a perspective on movement, undertakes a three-stage research process including the development of (a) a conceptual framework, (b) feature extraction and segmentation methods, and (c) similarity assessment techniques. The overall study involves an iterative research process integrating quantitative techniques from GIScience and knowledge discovery approaches in order to extract high-level information from low-level, raw movement data. The core of the research process is presented in four scientific papers. Research Paper 1 proposes a conceptual framework for movement as well as a comprehensive classification of movement patterns. Research Paper 2 presents a segmentation technique in order to extract movement features from trajectories of moving objects. The segmentation process can be seen as a dimension reduction technique to simplify the structure of the movement data in order to facilitate knowledge discovery. Research Paper 3 proposes a novel similarity assessment approach relying on the segmentation technique. Finally, Research Paper 4 extends the dimensionality of the main approach towards the detection of relative movement patterns Furthermore, through a set of experiments this thesis shows that the proposed methods can be successfully applied in conjunction with data mining techniques in order to support knowledge discovery from various movement datasets in real-world applications (e.g. transportation, meteorology). Consequently, the out- comes of this thesis can contribute to knowledge discovery from movement data where the interest is to extract or group similar behaviors of dynamic objects.