Human Mobility Prediction with Calibration for Noisy Trajectories: Comparison
Please note this is a comparison between Version 2 by Peter Tang and Version 1 by min li.

Human mobility prediction is a key task in smart cities to help improve urban management effectiveness. However, it remains challenging due to widespread intractable noises in large-scale mobility data. Based on previous research and ourthe statistical analysis of real large-scale data, wethe researchers observe that there is heterogeneity in the quality of users’ trajectories, that is, the regularity and periodicity of one user's trajectories can be quite different from another. Inspired by this, we the researchers propose a trajectory quality calibration framework for quantifying the quality of each trajectory and promoting high-quality training instances to calibrate the final prediction process. The main module of ourthis approach is a calibration network that evaluates the quality of each user's trajectories by learning their similarity between them. It is designed to be model-independent and can be trained in an unsupervised manner. Finally, the mobility prediction model is trained with the instance-weighting strategy, which integrates quantified quality scores into the parameter updating process of the model. Experiments conducted on two citywide mobility datasets demonstrate the effectiveness of ourthe approach when dealing with massive noisy trajectories in the real world.

  • human mobility
  • spatio-temporal prediction
  • noisy trajectories

1. Introduction

Predicting human mobility on a citywide level is vital to studies and applications in city-related areas, such as urban planning, traffic engineering, and epidemic prevention and control. Though human movements have a high degree of freedom and variation, several remarkable works [1][2][3] have proven that regularity and periodicity dominate the main pattern of human movements and play a critical role in mobility prediction. Therefore, extracting mobility patterns from people’s historical trajectories and predicting their next location has attracted much attention.
Traditional mobility prediction methods are mostly pattern-based. They employ machine learning methods such as matrix factorization to discover movement patterns from successive trajectories and predict the next location based on these formalized pattern representations. In addition, a large number of studies apply variants of Markov models due to their advantage in modeling sequential transitions, including hidden-Markov [4], weighted-Markov [5], attentional-Markov [6], Bayesian nets [7] and some other hybrid models.
In recent years, with the rapid development of deep learning, neural network models have shown promising performance in spatio-temporal sequence modeling such as Recurrent Neural Networks (RNN) [8] and Transformer [9]. Liu et al. [10] propose Spatial Temporal Recurrent Neural Networks (ST-RNN) to model the temporal and spatial context. Based on RNN, DeepMove [11] employs an attention mechanism to extract multi-level periodicity from long historical trajectories. Dang et al. [12] proposed a dual-attentive network to capture the long-range sequential dependency within a trajectory and the correlation between different trajectories. Given trajectory data, existing works usually train a learnable module to predict the next Point of Interest (POI) or corresponding region, aiming to consider the more complex context of spatio-temporal sequences and other related factors (such as social network structure [3] and location semantics [13]) to improve prediction accuracy.
However, the above methods require a large amount of mobility data to train the model to learn the regularity and periodicity of mobility patterns. Unfortunately, most mobility data with large scale and long duration contain noisy data which could reduce the prediction accuracy. Noise trajectories are often generated due to technical deviations from positioning devices and methods. Taking cellular mobility datasets [14] as an example, usually, a user connects to the cell tower closest to them, so the location of the cell tower to which the user is connected is used as an estimate of the user’s location. When there is a load balancing or signal strength change in cell towers [15], even if the user is not moving, the recorded locations switch between two or more cell towers, which is called oscillation [16][17][18]. Two real examples of such oscillations are depicted in Figure 1. With the help of various vehicles, many trips represented by oscillations are theoretically possible [19]. What is more, researchers often lack ground-truth information for validation to identify and clean these noisy trajectories [20].
Figure 1.
Two real examples of oscillations. (a) Cells jump to a far away tower then return back; (b) cells swift between two nearby towers.
Two real examples of oscillations. (a) Cells jump to a far away tower then return back; (b) cells swift between two nearby towers.
Wearchers use heuristic-based approaches[19] to remove significant device noise from the data used in ourthe experiments and roughly consider the average frequency decrease in recording after denoising for each user as the proportion of device noise in the user trajectory.  Figure 2 shows that device noise is prevalent in trajectory data. Most users' trajectories have a small proportion of noise, ranging from 0 to 0.6, and a few users have a large proportion of noise. This distribution indicates heterogeneity in the quality of user trajectories. Therefore, it is crucial to quantify the importance and quality of each user's trajectory in massive noisy mobile data and to reflect this in the prediction process.
Figure 2.
 (
a
) Average time interval of user recordings before and after denoising; (
b
) average frequency decrease in user recording by denoising.

There have been some works that successfully learn with noisy data in dialogue systems for NLP. To evaluate the quality of training dialogues and generate more reasonable conversations, several methods[21][22] concentrate on quantifying the relatedness between queries and replies and train conversation models through an instance-weighting strategy.

Inspired by these, wthe researchers propose the trajectory quality calibration framework, which automatically estimates the quality of each training trajectory through a pre-trained calibration network and promotes high-quality training instances to calibrate the final prediction process. Several recurrent neural sub-networks with shared weights are used in the proposed calibration network to capture and quantify the consistency of the user's mobility transitions each day. Additionally, the quality score of that user's trajectory is evaluated by measuring the correlation between daily features. Then, in the unsupervised pre-training process of the calibration network through a negative sampling strategy, the quality score will be gradually updated by comparing the relatedness between the original trajectory and the corresponding trajectory injected with random noise. The impact of each training instance on the parameters of the final prediction model can be quantified as a weight value by a normalization process on their quality scores. Finally, the prediction model takes advantage of these normalized weight values to calibrate the training process by an instance-weighting method, which multiplies the weight values to loss functions and gradient descents when updating corresponding parameters.

2. Mobility Prediction

Former studies on human mobility prediction can be generally classified into two categories: pattern-based methods and model-based methods.
The pattern-based methods [23][24][25][26] focus on discovering intrinsic mobility patterns from sequential trajectories and predicting next locations based on these formalized pattern representations. Most works are based on matrix factorization and are often assisted by feature engineering. In addition, embedding techniques can also be regarded as the pattern-mining method, such as POI2Vec [27] and Personalized Ranking Metric Embedding (PRME) [28].
The model-based methods [4][29][30][31] predict the user’s next visit by modeling the statistical relationship of contexts in the trajectories. The Markov model and its variations are common methods in earlier research. They model the probability of a transition matrix between relevant positions based on different data assumptions. The Hidden Semi-Markov Model (HSMM) [32] is designed to remove the constant or geometric distributions of the state durations assumed in the Hidden Markov Model (HMM). Yan et al. [5] propose a weighted Markov model for different user classifications. However, the association between Markov process and mobility dynamics has been questioned [33] in recent years because human mobility may exhibit scale-invariant long-term dependency, which contrasts with the initial Markov assumption [34].
Recently, deep learning techniques have been widely applied to model human mobility. Many works use RNNs to capture long-term dependencies in trajectories. Spatial–Temporal Recurrent Neural Networks (ST-RNN) [10] model temporal and spatial contexts at each time interval. DeepMove [11] employs an attention mechanism to capture periodic features in historical trajectories. The Bidirectional Long Short-Term Memory–Convolutional Neural Network (BiLSTM-CNN) [35] passes the output of RNN to CNN to capture the overall spatial and temporal patterns. Transformer [9] entirely relies on the attention mechanism to model the global dependencies of the sequence and breaks through the limitation that RNN cannot be parallelized. Deep Wide Spatio-Temporal Transformer Network (DWSTTN) [36] uses two attention mechanisms to extract relevant information in time and space, respectively. Graph Convolutional Dual-Attentive Networks (GCDAN) [12] design a dual-attention mechanism within and between trajectories and use graph convolution to extract spatial features in the embedding layer. With the help of sufficient training data sources, neural-based models can parameterize different kinds of mobility transitions instead of fixed hypothetical representations, making it possible to capture more complex regularities and model sequential trajectories more accurately.
However, these proposed models treat every training trajectory equally importantly, regardless of the uneven data quality distribution, which significantly influences mobility prediction accuracy [37].

3. Instance Weighting

Instance weighting is a training strategy that assigns different weight values to training instances when reflecting their influence on the updating process of model parameters. Some recent works have adopted this method for domain adaptation tasks in NLP, especially for dialogue systems. Jiang et al. [38] analyze and characterize the domain adaptation problem from a distributional view and propose a general instance-weighting framework for domain adaptation.
In common domain adaptation tasks, noisy data are identified and easy to distinguish when involving the uneven distribution of data quality. However, the noisy data in training a conversation model for the dialogue system are not that easy to identify, due to their high diversity based on characteristics of human language. Wang et al. [39] adopt the instance-weighting strategy to address the noisy label issue during data processing. Tao et al. [22], Lison et al. [21], and Shang et al. [40] propose relatedness-based evaluation metrics and matching networks to quantify and measure the relationship between queries and replies in conversations. The above problems are similar to the regularity and periodicity between daily mobility transitions in the task. Then, the data quality evaluation results assist the conversation model in focusing on meaningful training dialogues and generating more intelligent answers.
 

References

  1. Song, C.; Qu, Z.; Blumm, N.; Barabási, A.L. Limits of predictability in human mobility. Science 2010, 327, 1018–1021.
  2. Lu, X.; Wetter, E.; Bharti, N.; Tatem, A.J.; Bengtsson, L. Approaching the limit of predictability in human mobility. Sci. Rep. 2013, 3, 2923.
  3. Cho, E.; Myers, S.A.; Leskovec, J. Friendship and mobility: User movement in location-based social networks. In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Diego, CA, USA, 21–24 August 2011; pp. 1082–1090.
  4. Mathew, W.; Raposo, R.; Martins, B. Predicting future locations with hidden Markov models. In Proceedings of the 2012 ACM Conference on Ubiquitous Computing, Pittsburgh, PA, USA, 5–8 September 2012; pp. 911–918.
  5. Yan, M.; Li, S.; Chan, C.A.; Shen, Y.; Yu, Y. Mobility Prediction Using a Weighted Markov Model Based on Mobile User Classification. Sensors 2021, 21, 1740.
  6. Wang, H.; Li, Y.; Jin, D.; Han, Z. Attentional Markov Model for Human Mobility Prediction. IEEE J. Sel. Areas Commun. 2021, 39, 2213–2225.
  7. Ma, Z.; Rana, P.K.; Taghia, J.; Flierl, M.; Leijon, A. Bayesian estimation of Dirichlet mixture model with variational inference. Pattern Recognit. 2014, 47, 3143–3157.
  8. Lipton, Z.C.; Berkowitz, J.; Elkan, C. A critical review of recurrent neural networks for sequence learning. arXiv, 2015; arXiv:1506.00019.
  9. Vaswani, A.; Shazeer, N.; Parmar, N.; Uszkoreit, J.; Jones, L.; Gomez, A.N.; Kaiser, Ł.; Polosukhin, I. Attention is all you need. In Proceedings of the 31st Conference on Neural Information Processing Systems (NIPS 2017), Long Beach, CA, USA, 4–9 December 2017.
  10. Liu, Q.; Wu, S.; Wang, L.; Tan, T. Predicting the next location: A recurrent model with spatial and temporal contexts. In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, Phoenix, AZ, USA, 12–17 February 2016.
  11. Feng, J.; Li, Y.; Zhang, C.; Sun, F.; Meng, F.; Guo, A.; Jin, D. Deepmove: Predicting human mobility with attentional recurrent networks. In Proceedings of the 2018 World Wide Web Conference, Lyon, France, 23–27 April 2018; pp. 1459–1468.
  12. Dang, W.; Wang, H.; Pan, S.; Zhang, P.; Zhou, C.; Chen, X.; Wang, J. Predicting Human Mobility via Graph Convolutional Dual-attentive Networks. In Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining, Houston, Texas, USA, 21–25 February 2022; pp. 192–200.
  13. Wang, H.; Yu, Q.; Liu, Y.; Jin, D.; Li, Y. Spatio-Temporal Urban Knowledge Graph Enabled Mobility Prediction. Proc. ACM Interact. Mob. Wearable Ubiquitous Technol. 2021, 5, 1–24.
  14. Jang, H.S.; Baek, J.H. Mobility Management Scheme with Mobility Prediction in Wireless Communication Networks. Appl. Sci. 2022, 12, 1252.
  15. Qi, L.; Qiao, Y.; Abdesslem, F.B.; Ma, Z.; Yang, J. Oscillation resolution for massive cell phone traffic data. In Proceedings of the First Workshop on Mobile Data, Porto, Portugal, 13–16 June 2016; pp. 25–30.
  16. Bayir, M.A.; Demirbas, M.; Eagle, N. Mobility profiler: A framework for discovering mobility profiles of cell phone users. Pervasive Mob. Comput. 2010, 6, 435–454.
  17. Calabrese, F.; Di Lorenzo, G.; Liu, L.; Ratti, C. Estimating origin-destination flows using mobile phone location data. In Proceedings of the IEEE Pervasive Computing, Seattle, WA, USA, 21–25 March 2011; pp. 36–44.
  18. Wu, W.; Wang, Y.; Gomes, J.B.; Anh, D.T.; Antonatos, S.; Xue, M.; Yang, P.; Yap, G.E.; Li, X.; Krishnaswamy, S.; et al. Oscillation resolution for mobile phone cellular tower data to enable mobility modelling. In Proceedings of the 2014 IEEE 15th International Conference on Mobile Data Management, Brisbane, QLD, Australia, 15–18 July 2014; Volume 1, pp. 321–328.
  19. Wang, F.; Chen, C. On data processing required to derive mobility patterns from passively-generated mobile phone data. Transp. Res. Part C Emerg. Technol. 2018, 87, 58–74.
  20. Xu, Y.; Li, X.; Shaw, S.L.; Lu, F.; Yin, L.; Chen, B.Y. Effects of Data Preprocessing Methods on Addressing Location Uncertainty in Mobile Signaling Data. Ann. Am. Assoc. Geogr. 2021, 111, 515–539.
  21. Feng, S.; Cong, G.; An, B.; Chee, Y.M. Poi2vec: Geographical latent representation for predicting future visitors. In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, San Francisco, CA, USA, 4–9 February 2017.
  22. Monreale, A.; Pinelli, F.; Trasarti, R.; Giannotti, F. Wherenext: A location predictor on trajectory pattern mining. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Paris, France, 28 June–1 July 2009; pp. 637–646.
  23. Giannotti, F.; Nanni, M.; Pinelli, F.; Pedreschi, D. Trajectory pattern mining. In Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Nanjing, China, 22–25 May 2007; pp. 330–339.
  24. Peng, C.; Jin, X.; Wong, K.C.; Shi, M.; Liò, P. Collective human mobility pattern from taxi trips in urban area. PLoS ONE 2012, 7, e34487.
  25. Noulas, A.; Scellato, S.; Lathia, N.; Mascolo, C. Mining user mobility features for next place prediction in location-based services. In Proceedings of the 2012 IEEE 12th International Conference on Data Mining, Brussels, Belgium, 10–13 December 2012; pp. 1038–1043.
  26. Feng, S.; Li, X.; Zeng, Y.; Cong, G.; Chee, Y.M.; Yuan, Q. Personalized ranking metric embedding for next new poi recommendation. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, Buenos Aires, Argentina, 25–31 July 2015.
  27. Gambs, S.; Killijian, M.O.; del Prado Cortez, M.N. Next place prediction using mobility markov chains. In Proceedings of the First Workshop on Measurement, Privacy, and Mobility, Bern, Switzerland, 10–12 April 2012; pp. 1–6.
  28. Chen, M.; Liu, Y.; Yu, X. Nlpmm: A next location predictor with markov modeling. In Proceedings of the Pacific-Asia Conference on Knowledge Discovery and Data Mining. Springer, Tainan, Taiwan, 13–16 May 2014; pp. 186–197.
  29. Amirrudin, N.A.; Ariffin, S.H.; Malik, N.A.; Ghazali, N.E. User’s mobility history-based mobility prediction in LTE femtocells network. In Proceedings of the 2013 IEEE International RF and Microwave Conference (RFM), Penang, Malaysia, 9–11 December 2013; pp. 105–110.
  30. Yu, S.Z.; Kobayashi, H. A hidden semi-Markov model with missing data and multiple observation sequences for mobility tracking. Signal Process. 2003, 83, 235–250.
  31. Kulkarni, V.; Garbinato, B. 20 Years of Mobility Modeling & Prediction: Trends, Shortcomings & Perspectives. In Proceedings of the 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, Chicago, IL, USA, 5–8 November 2019; pp. 492–495.
  32. Kulkarni, V.; Mahalunkar, A.; Garbinato, B.; Kelleher, J.D. Examining the limits of predictability of human mobility. Entropy 2019, 21, 432.
  33. Bao, Y.; Huang, Z.; Li, L.; Wang, Y.; Liu, Y. A BiLSTM-CNN model for predicting users’ next locations based on geotagged social media. Int. J. Geogr. Inf. Sci. 2021, 35, 639–660.
  34. Abideen, Z.U.; Sun, H.; Yang, Z.; Ahmad, R.Z.; Iftekhar, A.; Ali, A. Deep wide spatial-temporal based transformer networks modeling for the next destination according to the taxi driver behavior prediction. Appl. Sci. 2020, 11, 17.
  35. Zhang, H.; Dai, L. Mobility prediction: A survey on state-of-the-art schemes and future applications. IEEE Access 2018, 7, 802–822.
  36. Jiang, J.; Zhai, C. Instance weighting for domain adaptation in NLP. In Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics, Prague, Czech Republic, 23–30 June 2007; pp. 264–271.
  37. Wang, R.; Utiyama, M.; Liu, L.; Chen, K.; Sumita, E. Instance weighting for neural machine translation domain adaptation. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, Copenhagen, Denmark, 7–11 September 2017; pp. 1482–1488.
  38. Tao, C.; Mou, L.; Zhao, D.; Yan, R. Ruber: An unsupervised method for automatic evaluation of open-domain dialog systems. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, New Orleans, LA, USA, 2–7 February 2018.
  39. Lison, P.; Bibauw, S. Not all dialogues are created equal: Instance weighting for neural conversational models. arXiv, 2017; arXiv:1704.08966.
  40. Shang, M.; Fu, Z.; Peng, N.; Feng, Y.; Zhao, D.; Yan, R. Learning to Converse with Noisy Data: Generation with Calibration. In Proceedings of the International Joint Conferences on Artificial Intelligence, Stockholm, Sweden, 13–19 July 2018; pp. 4338–4344.
More