Uncovering individual's mobility patterns from GPS dataset
Date of Issue2014
School of Computer Engineering
Centre for Advanced Information Systems
Human mobility patterns, including issues such as locations of significance, modes of transport, trajectory patterns, location-based activities, are of great importance to a wide range of research areas and location-related applications. Based on the patterns uncovered, various mobility models may be proposed to predict individual's future whereabouts, or to evaluate the protocols for wireless communications, among other applications. In this thesis, I present a study of individual's mobility patterns based on GPS records. The study in this thesis includes inferring the modes of transport, analyzing the predictability of individual's mobility, constructing mobility model, and predicting future locations. Modes of transport, such as walking, biking, driving, or taking a bus, are a basic pattern of individual's mobility. Current studies on inferring the modes of transport apply supervised methods, which include a tedious training process. In this thesis, I present an unsupervised method for inferring the modes of transport, which eliminates the need of manual labeling and training while attaining equal or greater accuracy compared to the best known supervised method. The unsupervised method relies on Kolmogorov-Smirnov Test which offers a theoretical assurance when comparing segments of records. Various probabilistic models and algorithms, such as Markov models, Bayes models, pattern mining methods, have been proposed to predict individual's next moves. The predicting accuracy has been greatly improved because of these efforts. However, little is known whether the predicting accuracy is already approaching the limit and hence further research efforts may yield diminishing returns. Moreover, the predicting accuracy is apparently affected by the scale of the places visited and the time interval concerned. In this thesis, I present a study of the predictability of individual's mobility sequences. The predictability quantifies the potential to foresee the next moves of an individual based on his/her historical records. Using high-resolution GPS data, the scaling effects on predictability are investigated. Given specified spatio-temporal scales, recorded trajectories are encoded into long strings of distinct locations, and several information-theoretic measures of predictability are derived. I show that high predictability is still present at rather high spatial/temporal resolutions. The predictability is found to be independent of the overall mobility area covered, which suggests highly regular mobility behaviors. Moreover, by varying the scales over a wide range, an invariance between the predicting accuracy and spatial resolution is observed which suggests that certain trade-offs between these two are unavoidable. Most known mobility models are incomplete for describing individual's mobility because they fail to reproduce essential characteristics of individual's mobility behaviors. In this thesis, I propose a new Markovian mobility model that fits well the high predictability of individual's mobility and a few other known statistical properties presented in recent studies. The mobility sequences generated from the new model are verified both theoretically and experimentally. I also present several results that validate popular assumptions about mobility sequences. The high predictability of individual's mobility reported in existing literature is based on relatively coarse spatio-temporal resolutions, which is not suitable for the new generation of location-based applications. Also, the high predictability is often dominated by the cases where the individuals stay at a place during most of the time. Therefore, I further investigate methods for predicting individual's locations at high spatio-temporal resolutions. To achieve this purpose, I present a new method to exploit historical traces that exhibit similarity with the current trace. The similarity of the traces is evaluated based on the notion of edit distance. The predicted location at the future point in time is a weighted mean of the results obtained from modified Brownian Bridge models and linear extrapolation. Compared to using either historical records or linear extrapolation method alone, the proposed location prediction method shows lower mean prediction errors.
DRNTU::Engineering::Computer science and engineering::Computing methodologies::Pattern recognition