Novel Algorithms for Trajectory Segmentation based on Interpolation-based Change Detection Strategies

Abstract

An enormous number of mobility datasets for tracking animals, vehicles, vessels, individuals and moving objects are currently available, and this number continues to grow. Mobility data has diverse applications, including for transportation, marine navigation, tourism, and animal behaviour analysis. Processing such data requires reasonable pre-processing and cleaning efforts, owing to its velocity. Splitting the traces of mobility data movements into semantically related trajectory points is an essential task for trajectory mining pre-processing, called Trajectory Segmentation. Generating enriched graph representations, preserving the privacy of mobility data, and facilitating trajectory-tagging tasks are three critical reasons for the importance of this pre-processing task. Available solutions for trajectory segmentation utilize background knowledge more than just the movement captured knowledge and are specific to a particular domain. They do not provide a domain-independent solution that uses only the movement tracks.

We propose two TS methods that apply to two different types of trajectory applications: 1) when we only have access to geolocation and timestamp, but its point or segment feature is not accessible, and 2) when a dataset with at least a point feature is available.

Sliding Window Segmentation (SWS) splits trajectories into segments using behaviour change detection. We evaluated SWS on three datasets (fishing, hurricanes, and Geolife) by comparing it against four available solutions (SPD, GRASP-UTS, CBSMoT, and WKMeans). SWS discovered statistically significant higher-quality segments (higher harmonic mean) than SPD, GRASP-UTS, and WKMeans. The number of identified segments, amount of memory, and CPU consumption of algorithms, and v-measure indicated that SWS found more high-quality segments than CBSMoT. SWS cannot produce segments for a dataset with a low frequency of capturing.

Wise Sliding Window Segmentation (WSII) identifies the potential partitioning position using labelled data, a binary classifier, and a majority vote decision-making mechanism. It can be applied in a trajectory-tagging platform to assist in annotating trajectories. It boosted harmonic means on hurricanes and Geolife datasets compared to five other algorithms; however, WSII does not perform well on the fishing dataset. The dataset attributes and the nature of the movement are two major contributing factors (e.g. low frequency of sampling decreases the quality of segmentation).