Abstract
Human mobility is a complex pattern of movements and activities that are based on some underlying semantics of human behavior. In order to construct accurate models of human mobility, this semantic behavior needs to be unearthed from the data sensed as a human being moves around and visits certain classes of locations such as home, work, mall, theater, restaurant etc. The ideal data for understanding the semantics of mobility would constitute timestamped mobility traces with detailed geographic locations with annotations about the type of each location. One way of achieving this is by following a hybrid strategy of participatory sensing (with each person carrying a wireless sensor device) and deploying static sensors at each location of interest – the contacts between the mobile and (annotated) static sensors can be logged at each location, and then collated to form an appropriate mobility traces. For example, a person can connect with his mobile phone over Bluetooth or WiFi to a local hotspot while checking into FourSquare at a restaurant. In the absence of static sensors, a person may manually annotate the places he visits on his device over time. However, most mobility traces consist of network connectivity data from cell phones (e.g., contact with towers) which lack detailed geographic locations and are ambiguous, noisy and unlabeled. Thus, it is important to extract the semantics of mobility that is latent in the available contact traces. To this end, we propose in this paper the concept of Probabilistic Latent Semantic Trajectories (PLST), an unsupervised approach to extract semantically different locations and sequential patterns of mobility from such traces. PLST extracts semantic locations as contextually co-occurring network elements (cell towers and Bluetooth devices) and models the behavior of their sequence. PLST extracts distinct locations with spatial, temporal and semantic coherency and can be used for accurate prediction of the next place a user visits. PLST also analyzes the complexity of mobility traces using information theoretic metrics to study the underlying structure and semantic content in mobility traces. This semantic content can be extracted allowing us to investigate mobility patterns in a completely unsupervised manner.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Blei, D.M., Ng, A.Y., Jordan, M.I.: Latent dirichlet allocation. J. Mach. Learn. Res. 3, 993–1022 (2003)
Brown, P.F., Pietra, V.J.D., Mercer, R.L., Pietra, S.A.D., Lai, J.C.: An estimate of an upper bound for the entropy of english. Comput. Linguist. 18(1), 31–40 (1992)
Buthpitiya, S., Zhang, Y., Dey, A.K., Griss, M.: n-gram geo-trace modeling. In: Lyons, K., Hightower, J., Huang, E.M. (eds.) Pervasive 2011. LNCS, vol. 6696, pp. 97–114. Springer, Heidelberg (2011)
Chang, C.-C., Lin, C.-J.: Libsvm: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology 2, 1–27 (2011), http://www.csie.ntu.edu.tw/~cjlin/libsvm
Coffey, C., Pozdnoukhov, A.: Temporal decomposition and semantic enrichment of mobility flows. In: Proceedings of the 6th ACM SIGSPATIAL International Workshop on Location-Based Social Networks, LBSN 2013, pp. 34–43. ACM, New York (2013)
Cortes, C., Vapnik, V.: Support-vector networks. In: Machine Learning, pp. 273–297 (1995)
Eagle, N., Pentland, A.: Eigenbehaviors: Identifying structure in routine. In: Joint Conference on Pervasive and Ubiquitous Computing (2006)
Eagle, N., Pentland, A.(S.): Reality mining: sensing complex social systems. Personal Ubiquitous Comput. 10(4), 255–268 (2006)
Ebeling, W., Frommel, C.: Entropy and predictability of information carriers. Biosystems 46(1), 47–55 (1998)
Farrahi, K., Gatica-Perez, D.: Discovering routines from large-scale human locations using probabilistic topic models. ACM Trans. Intell. Syst. Technol. 2(1), 3:1–3:27 (2011)
Gambs, S., Killijian, M.-O., del Prado Cortez, M.N.N.: Next place prediction using mobility markov chains. In: First Workshop on Measurement, Privacy, and Mobility, MPM 2012, pp. 3:1–3:6. ACM, New York (2012)
Gao, W., Cao, G.: Fine-grained mobility characterization: Steady and transient state behaviors. In: in Proceedings of Mobihoc (2010)
Gonzalez, M.C., Hidalgo, C.A., Barabasi, A.-L.: Understanding individual human mobility patterns. Nature 453(7196), 779–782 (2008)
Griffiths, T.L., Steyvers, M., Blei, D.M., Tenenbaum, J.B.: Integrating topics and syntax. In: In Advances in Neural Information Processing Systems 17, pp. 537–544. MIT Press (2005)
Griffiths, T.L., Tenenbaum, J.B., Steyvers, M.: Topics in semantic representation. Psychological Review 114 (2007)
Hofmann, T.: Probabilistic latent semantic analysis. In: Uncertainty in Artificial Intelligence, UAI, pp. 289–296 (1999)
Wang, B.P.J.: Periodicity based next place prediction. In: Procedings of Mobile Data Challenge by Nokia Workshop at the Tenth International Conference on Pervasive Computing (2012)
Laurila, J.K., Gatica-Perez, D., Aad, I., Blom, J., Bornet, O., Do, T., Dousse, O., Eberle, J., Miettinen, M.: The mobile data challenge: Big data for mobile computing research. In: Mobile Data Challenge by Nokia Workshop, Newcastle, UK (2012)
Nguyen, L.T., Heng-Tze, C., Pang, W., Senaka, B., Jiang, Z., Ying, Z.: Pnlum: System for prediction of next location for users with mobility. In: Mobile Data Challenge by Nokia Workshop at the Tenth International Conference on Pervasive Computing (2012)
Leguay, J., Lindgren, A., Scott, J., Friedman, T., Crowcroft, J., Hui, P.: CRAWDAD trace set upmc/content/imote (v. 2006-11-17) (November 2006), http://crawdad.cs.dartmouth.edu/upmc/content/imote
Liao, L., Fox, D., Kautz, H.: Extracting places and activities from gps traces using hierarchical conditional random fields. Int. J. Rob. Res. 26(1), 119–134 (2007)
Losada, D., Azzopardi, L.: Assessing multi-variate bernoulli models for information retrieval. ACM Transactions on Information Systems 26(3) (2008)
McDiarmid, A., Irvine, J., Bell, S., Banford, J.: CRAWDAD data set strath/nodobo (v. 2011-03-23) (March 2011), http://crawdad.cs.dartmouth.edu/strath/nodobo
Nahrstedt, K., Vu, L.: CRAWDAD data set uiuc/uim (v. 2012-01-24) (January 2012), http://crawdad.cs.dartmouth.edu/uiuc/uim
Nguyen, T., Phung, D., Gupta, S., Venkatesh, S.: Extraction of latent patterns and contexts from social honest signals using hierarchical dirichlet processes. In: IEEE International Conference on Pervasive Computing and Communications (PerCom), pp. 47–55 (2013)
Parent, C., Spaccapietra, S., Renso, C., Andrienko, G., Andrienko, N., Bogorny, V., Damiani, M.L., Gkoulalas-divanis, A., Macedo, J., Pelekis, N., Theodoridis, Y., Yan, Z.: Semantic trajectories modeling and analysis. ACM Computing Surveys (2012)
Rabiner, L.R.: A tutorial on hidden markov models and selected applications in speech recognition. Proceedings of the IEEE, 257–286 (1989)
Song, C., Qu, Z., Blumm, N., Barabasi, A.: Limits of predictability in human mobility. Science 327(5968), 1018–1021 (2010)
Song, L., Kotz, D., Jain, R., He, X.: Evaluating location predictors with extensive wi-fi mobility data. SIGMOBILE Mob. Comput. Commun. Rev. 7(4), 64–65 (2003)
Srinivasan, V., Natarajan, A., Motani, M.: CRAWDAD data set nus/bluetooth (v. 2007-09-03) (September 2007), http://crawdad.cs.dartmouth.edu/nus/bluetooth
Vincent Etter, E.K., Kafsi, M.: Been there, done that: What your mobility traces reveal about your behavior. In: Mobile Data Challenge by Nokia: Workshop at 10th International Conference on Pervasive Computing (2012)
Ying, J.J.-C., Lee, W.-C., Weng, T.-C., Tseng, V.S.: Semantic trajectory mining for location prediction. In: 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, GIS 2011, pp. 34–43. ACM, New York (2011)
Zheng, Y., Li, Q., Chen, Y., Xie, X., Ma, W.-Y.: Understanding mobility based on gps data. In: 10th International Conference on Ubiquitous Computing, UbiComp 2008, pp. 312–321. ACM, New York (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Deb, B., Basu, P. (2015). Discovering Latent Semantic Structure in Human Mobility Traces. In: Abdelzaher, T., Pereira, N., Tovar, E. (eds) Wireless Sensor Networks. EWSN 2015. Lecture Notes in Computer Science, vol 8965. Springer, Cham. https://doi.org/10.1007/978-3-319-15582-1_6
Download citation
DOI: https://doi.org/10.1007/978-3-319-15582-1_6
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-15581-4
Online ISBN: 978-3-319-15582-1
eBook Packages: Computer ScienceComputer Science (R0)