Paul Baumann
ABSTRACT
Several algorithms to predict the next place visited by a user have been proposed in the literature. The accuracy of these algorithms -- measured as the ratio of the number of correct predictions and the number of all computed predictions -- is typically very high. In this paper, we show that this good performance is due to the high predictability intrinsic in human mobility. We also show that most algorithms fail to correctly predict transitions, i.e. situations in which users move between different places. To this end, we analyze the performance of 18 prediction algorithms focusing on their ability to predict transitions. We run our analysis on a data set of mobility traces of 37 users collected over a period of 1.5 years. Our results show that even algorithms achieving an overall high accuracy are unable to reliably predict the next location of the user if this is different from the current one. Building upon our analysis we then present a novel next-place prediction algorithm that can both achieve high overall accuracy and reliably predict transitions. Our approach combines all the 18 algorithms considered in our analysis and achieves its good performance at the cost of a higher computational and memory overhead.
- D. Ashbrook and T. Starner. Using GPS to Learn Significant Locations and Predict Movement Across Multiple Users. Personal and Ubiquitous Computing, 7(5):275--286, Oct. 2003. Google Scholar
Digital Library
- Y. Chon, H. Shin, E. Talipov, and H. Cha. Evaluating Mobility Models for Temporal Prediction with High-granularity Mobility Data. In 10th Intl. Conf. on Pervasive Computing and Communications (PerCom'12). IEEE, Mar. 2012.Google Scholar
- A. Dey, K. Wac, and D. Ferreira. Getting Closer: An Empirical Investigation of the Proximity of Users to their Smart Phones. In 13th Intl. Conf. on Ubiquitous Computing (UbiComp'11). ACM, Sept. 2011. Google ScholarDigital Library
- M. D. Domenico, A. Lima, and M. Musolesi. Interdependence and Predictability of Human Mobility and Social Interactions. In Nokia Mobile Data Challenge Workshop in Conjunction with 10th Intl. Conf. on Pervasive Computing (Pervasive'12). Springer, June 2012.Google Scholar
- O. Dousse, J. Eberle, and M. Mertens. Place Learning via Direct WiFi Fingerprint Clustering. In 13th Intl. Conf. on Mobile Data Management (MDM'12). IEEE, July 2012. Google ScholarDigital Library
- J. Hightower, S. Consolvo, and A. LaMarca. Learning and Recognizing the Places We Go. In 7th Intl. Conf. on Ubiquitous Computing (UbiComp'05). Springer, Sept. 2005. Google ScholarDigital Library
- J. H. Kang, W. Welbourne, B. Stewart, and G. Borriello. Extracting Places from Traces of Locations. Mobile Computing and Communications Review, 9(3):58, July 2005. Google ScholarDigital Library
- D. H. Kim, J. Hightower, R. Govindan, and D. Estrin. Discovering Semantically Meaningful Places from Pervasive RF-Beacons. In 11th Intl. Conf. on Ubiquitous Computing (UbiComp'09). ACM, Sept. 2009. Google ScholarDigital Library
- M. Kim, D. Kotz, and S. Kim. Extracting a Mobility Model from Real User Traces. In 25th Intl. Conf. on Computer Communications (INFOCOM'06). IEEE, Apr. 2006.Google ScholarCross Ref
- J. Krumm and A. J. B. Brush. Learning Time-based Presence Probabilities. In 9th Intl. Conf. on Pervasive Computing (Pervasive'11). Springer, June 2011. Google ScholarDigital Library
- J. Krumm and E. Horvitz. Predestination: Inferring Destinations from Partial Trajectories. In 8th Intl. Conf. on Ubiquitous Computing (UbiComp'06). ACM and Springer, Sept. 2006. Google ScholarDigital Library
- J. Laurila, D. Gatica-Perez, and I. Aad. The Mobile Data Challenge: Big Data for Mobile Computing Research. In 10th Intl. Conf. on Pervasive Computing (Pervasive'12). Springer, June 2012.Google Scholar
- M. Lin, W.-J. Hsu, and Z. Q. Lee. Predictability of Individuals' Mobility with High-resolution Positioning Data. In 14th Intl. Conf. on Ubiquitous Computing (UbiComp'12). ACM, Sept. 2012. Google ScholarDigital Library
- J. McInerney, S. Stein, A. Rogers, and N. Jennings. Exploring Periods of Low Predictability in Daily Life Mobility. In 10th Intl. Conf. on Pervasive Computing (Pervasive'12). Springer, June 2012.Google Scholar
- R. Montoliu, J. Blom, and D. Gatica-Perez. Discovering Places of Interest in Everyday Life from Smartphone Data. Multimedia Tools and Applications, 62:179--207, Jan. 2013.Google ScholarCross Ref
- A. J. Nicholson and B. D. Noble. BreadCrumbs: Forecasting Mobile Connectivity. In 14th Intl. Conf. on Mobile Computing and Networking (MobiCom'08). ACM, Sept. 2008. Google ScholarDigital Library
- P. Baumann and S. Santini. On the Use of Instantaneous Entropy to Measure the Momentary Predictability of Human Mobility. In 14th IEEE Workshop on Signal Processing Advances in Wireless Communications (SPAWC'13). IEEE, June 2013.Google ScholarCross Ref
- S. Patel, J. Kientz, G. Hayes, S. Bhat, and G. Abowd. Farther Than You May Think: An Empirical Investigation of the Proximity of Users to their Mobile Phones. In 8th Intl. Conf. on Ubiquitous Computing (UbiComp'06). ACM and Springer, Sept. 2006. Google ScholarDigital Library
- S. Scellato, M. Musolesi, C. Mascolo, V. Latora, and A. T. Campbell. NextPlace: A Spatio-temporal Prediction Framework for Pervasive Systems. In 9th Intl. Conf. on Pervasive Computing (Pervasive'11). Springer, June 2011. Google ScholarDigital Library
- J. Scott, A. Brush, and J. Krumm. PreHeat: Controlling Home Heating Using Occupancy Prediction. In 13th Intl. Conf. on Ubiquitous Computing (UbiComp'11). ACM, Sept. 2011. Google ScholarDigital Library
- C. Song, Z. Qu, N. Blumm, and A.-L. Barabási. Limits of Predictability in Human Mobility. Science (New York, N.Y.), 327(5968):1018--21, Feb. 2010.Google ScholarCross Ref
- C. Song, Z. Qu, N. Blumm, and A.-L. Barabási. Supplementaring Online Material on Limits of Predictability in Human Mobility. Science (New York, N.Y.), 327(5968):1--21, Mar. 2010.L. Song and U. Deshpande. Predictability of WLAN Mobility and its Effects on Bandwidth Provisioning. In 25th Intl. Conf. on Computer Communications (INFOCOM '06). IEEE, 2006.Google Scholar
- L. Song, D. Kotz, R. Jain, and X. He. Evaluating Location Predictors with Extensive WiFi Mobility Data. Mobile Computing and Communications Review, 7(4):64--65, Oct. 2003. Google ScholarDigital Library
- I. Witten, E. Frank, and M. Hall. Data Mining: Practical Machine Learning Tools and Techniques. Morgan Kaufmann, 3rd edition, 2011. Google ScholarDigital Library
- Y. Ye, Y. Zheng, Y. Chen, J. Feng, and X. Xie. Mining Individual Life Pattern Based on Location History. In 10th Intl. Conf. on Mobile Data Management: Systems, Services and Middleware (MDM'09). IEEE, May 2009. Google ScholarDigital Library
Index Terms
- The influence of temporal and spatial features on the performance of next-place prediction algorithms
Recommendations
Comparing Sequential and Temporal Patterns from Human Mobility Data for Next-Place Prediction
UMAP '18: Adjunct Publication of the 26th Conference on User Modeling, Adaptation and PersonalizationIn the domain of human behavior prediction, next-place prediction is an active research field. While prior work has applied sequential and temporal patterns for next-place prediction, no work has yet studied the prediction performance of combining ...
Next Place Prediction: A Systematic Literature Review
PredictGIS 2018: Proceedings of the 2nd ACM SIGSPATIAL Workshop on Prediction of Human MobilityIn this systematic literature review an overview of the recent developments in the field of Next Place Prediction is given. Next Place Prediction in this work refers to the prediction of where an individual human will go to next, based on continuous ...
Human Mobility Prediction Challenge: Next Location Prediction using Spatiotemporal BERT
HuMob-Challenge '23: Proceedings of the 1st International Workshop on the Human Mobility Prediction ChallengeUnderstanding, modeling, and predicting human mobility patterns in urban areas has become a crucial task from the perspectives of traffic modeling, disaster risk management, urban planning, and more. HuMob Challenge 2023 aims to predict future ...
Comments