Advanced techniques in trajectory data analysis for anomaly detection and map construction

Abstract

With a large amount of trajectory data generated every day, there is a high demand for developing advanced techniques to discover the underlying information instead of dull and heavy manual work. This thesis focuses on the anomaly detection and map construction from GPS data. Anomaly detection aims to identify trajectories that do not follow common behaviors, and map construction deals with a set of trajectory data to generate a route graph that represents the main movement paths hidden in data. For online anomaly detection, we study the well-known Sequential Hausdorff Nearest-Neighbor Conformal Anomaly Detector (SHNN-CAD) approach, and propose an enhanced version called SHNN-CAD•. For map construction, we present a new, fast and robust three-step framework. Considering the storage limitation and computational cost dealing with large-scale data, we propose a split-and­merge strategy. Besides, we utilize the edge weight to visualize the map and remove the wrong edges.

La gran cantidad de datos de trayectorias generados cada día hace que exista una gran necesidad de desarrollar técnicas avanzadas para descubrir la información subyacente de los datos evitando un trabajo manual aburrido y pesado. Esta tesis se centra en la detección de anomalías y la construcción de mapas a partir de datos GPS. La detección de anomalías identifica trayectorias que no siguen comportamientos habituales; y la construcción de mapas recibe un conjunto de trayectorias y genera un grafo de caminos que representa los principales movimientos escondidos en los datos de entrada. Para detección de anomalías en línea, estudiamos el conocido detector SHNN- CAD y proponemos una versión mejorada llamada SHNN-CAD•. Para construcción de mapas, presentamos una estrategia con tres pasos nueva, rápida y robusta. Considerando datos a gran escala, proponemos una estrategia de división y fusión. También utilizamos el peso de las aristas para visualizar el mapa y eliminar las aristas incorrectas.