Thanks to the wide diffusion of localization technologies and mobile services based on the positioning of users and devices, the availability of mobility traces is increasing fast in several application domains. Location-based services provided through smartphones are nowadays extremely popular and the vast amounts of data that this trend leads to produce and collect open the door to several opportunities of converting them into better services, economical returns, more sustainable cities, improved living conditions, etc. All this starts from appropriate mobility analysis operations able to extract from raw data usable and useful information. 

 

In mobility analytics one of the fundamental concepts is movement, meaning with that the part of mobility data that describes a transfer from one place where the individual (or the object) was staying, to another one were the user will stop. While it is simple to define a stop in geometrical terms, it is hard to define significant stops, i.e., stops that might have some meaning for the user (e.g., stopping to do some activity before leaving), as opposed to stops that are simply incidental (e.g., due to a small traffic jam). Practitioners in the mobility analytics domain defined several simple strategies to select stops in the mobility data stream each of them apparently capturing well some specific concept or some application-specific idea of stop. 

 

However, most existing solutions suffer from two important limitations: 

The reason of the latter is that, while an overall evaluation might be performed to guide the choice of a global threshold, doing that separately for each individual might be impossible if their number is huge.

 

In this post, we discuss how to overcome the limitations highlighted above, providing a general methodology that inspects the mobility of the individual, and identifies segmentation thresholds that apparently match her mobility features. The process allows to get rid of any input parameter, adapts thresholds to each single individual and, most importantly, is completely automatic, thus applicable to large pools of users

 

Problem Formulation and Proposed Solution

Existing trajectory segmentation methods assume that the same rules and the same parameters should apply to all moving objects. Our objective is to overcome this limitation, making the segmentation process adaptive to the individual and taking into consideration her overall mobility. 

The proposed solution to the individual cut threshold problem consists in fixing the spatial threshold to a global value (i.e. to be used for all users) and then in studying the segmentations that we would obtain by applying different temporal thresholds. When very small values of τ are used, the segmentation obtained will contain a huge number of very short segments, till the extreme case where each point forms its own segment. As the threshold is increased, more and more segments will merge together, since some of the former splitting points will fall below τ. The process is expected to gradually enlarge the trajectory segments by first including simple slowdowns (i.e. not really stop points), then temporary stops (e.g. at traffic lights), and so on.

Our approach consists in (virtually) monitoring such progression, and detect the moment where an anomalous increase in the number of segments is observed, which represents a sort of change of state. We called the procedure as ATS (self-Adaptive Trajectory Segmentation). We experimented the new approach (ATS) described above over a real dataset of GPS vehicle traces. The results commented in the following refer to 2000 users of the area of Rome (Italy), and London (UK). We first analyzed the personal temporal thresholds returned by ATS, then we propose a quantitative and qualitative evaluation of the results for understanding the benefits of the novel method with respect to existing ones. We compare ATS against the trajectory segmentation method with fixed parameters proposed in [1]. 

Figure. Time threshold distributions for trajectories in Rome and London selected by ATS for each user (vertical axis represents value frequencies in log-scale). The peaks show the ideal thresholds to be set to build the trajectories.

Although every user has her own mobility behavior with its own mix of regular and more erratic behaviours [2], we observe two clear peaks in the distributions for both Rome and London. This supports the intuition behind our approach, namely to have a self-adaptive procedure selecting a personalized best temporal threshold for each user. Selecting one single threshold value for all the data might negatively affect the segmentation of some users, partitioning their trajectories either too much or too little.

Though preliminary, the experiments show that it is possible to derive user-adaptive cut thresholds, improving the performances of the segmentation over less flexible solutions. This is an ongoing work, and several improvements are being explored. Among them, the future lines of research will aim to derive thresholds for trajectory segmentation which are not only user-adaptive, but also location-adaptive, thus considering the fact that a stop at different places might require time intervals of different duration to be considered a significant stay – and thus a trajectory cut point. Also, we will study the possibility of exploiting the context around the (moving) user, such as the mobility of other users and the geographical area surrounding the candidate stops.

The paper describing this research has been presented to the workshop “BMDA 2020: Third International Workshop in Big Mobility Data Analytics”.

Written by Agnese Bonavita agnese.bonavita@sns.it
Revised by Luca Pappalardo

References
[1] Luca Pappalardo et al. 2015. Returners and explorers dichotomy in human mobility. Nature communications 6 (2015), 8166.
[2] Roberto Trasarti et al. 2011. Mining mobility user profiles for car pooling. In KDD. ACM, 1190–1198.