Abstract
Few decades ago, understanding human behaviors was considered as a mystery where predicting people’s future was impossible. Many changes have been noticed since that era. Thanks to current advances in location tracking technology and data mining techniques, predicting users’ behaviors has become possible. In this paper we present a new algorithm to online predict users’ next visited locations that not only learns incrementally the users’ habits, but also detects and supports the drifts in their patterns. Our original contribution includes a new algorithm for online association rules mining that supports the concept drift.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
Apriori is an algorithm for frequent item set mining and association rule learning over transactional databases. It proceeds by identifying the frequent individual items in the database and extending them to larger and larger item sets as long as those item sets appear sufficiently often in the database.
MMC is a probabilistic automaton in which states represent points of interest (POIs) of an individual and transitions between states corresponds to a movement from one POI to another one, a transition between POIs is non deterministic but rather that there is a probability distribution over the transitions that corresponds to the probability of moving from one POI to another.
MMM is an intermediate model between individual and generic models. The prediction of the next location is based on a Markov model belonging to a group of individuals with similar mobility behavior. This approach clusters individuals into groups based on their mobility traces and then generates a specific Markov model for each group. The prediction of the next location works by first identifying the group a particular individual belongs to and then inferring the next location based on this group model.
References
Asahara A, Maruyama K, Sato A, Seto K (2011) Pedestrian-movement prediction based on mixed Markov-chain model. ACM Press, Chicago, Illinois, p 25. doi:10.1145/2093973.2093979
Boukhechba M, Bouzouane A, Bouchard B, Charles, GV, Sylvain G (2015) Online recognition of people’s activities from raw GPS data: semantic trajectory data analysis. In: Presented at the 8th ACM international conference on pervasive technologies related to assistive environments
Boukhechba M, Bouzouane A, Bouchard B, Gouin-Vallerand C, Giroux S (2016) Energy optimization for outdoor activity recognition. J Sens 2016:1–15. doi:10.1155/2016/6156914
Ezeife CI, Su Y (2002) Mining incremental association rules with generalized FP-tree. In: Cohen R, Spencer B. (eds) Advances in artificial intelligence. Springer, Berlin, pp 147–160
Gai YL (2012) Research on data mining and apriori algorithm. Adv Mater Res 546–547:497–502. doi:10.4028/www.scientific.net/AMR.546-547.497
Gama J, Medas P, Castillo G, Rodrigues P (2004) Learning with drift detection. In: Bazzan A.L.C., Labidi S (eds) Advances in artificial intelligence—SBIA 2004. Springer, Berlin, pp 286–295
Gama J, Sebastião R, Rodrigues PP (2009) Issues in evaluation of stream learning algorithms. ACM Press. doi:10.1145/1557019.1557060
Gambs S, Killijian M-O, del Prado Cortez MN (2012) Next place prediction using mobility Markov chains. ACM Press, pp 1–6. doi:10.1145/2181196.2181199
Hipp J, Güntzer U, Nakhaeizadeh G (2000) Algorithms for association rule mining—a general survey and comparison. ACM SIGKDD Explor Newsl 2:58–64. doi:10.1145/360402.360421
Kapterev A (2014) Where to go next. In: Presentation secrets. Wiley, Hoboken, pp 265–278
Katsaros D, Nanopoulos A, Karakaya M, Yavas G, Ulusoy Ö, Manolopoulos Y (2003) Clustering mobile trajectories for resource allocation in mobile environments. In: Berthold RM, Lenz H-J, Bradley E, Kruse R, Borgelt C (eds) Advances in intelligent data analysis V. Springer, Berlin, pp 319–329
Li K, Fu Y (2014) Prediction of human activity by discovering temporal sequence patterns. IEEE Trans Pattern Anal Mach Intell 36:1644–1657. doi:10.1109/TPAMI.2013.2297321
Morzy M (2006) Prediction of moving object location based on frequent trajectories. In: Levi A, Savaş E, Yenigün H, Balcısoy S, Saygın Y. (eds) Computer and information sciences—ISCIS. Springer, Berlin, pp 583–592
PhridviRaj MSB, GuruRao CV (2014) Data mining—past, present and future—a typical survey on data streams. Proced Technol 12:255–263. doi:10.1016/j.protcy.2013.12.483
Simmons R, Browning B, Zhang Y, Sadekar V (2006) Learning to predict driver route and destination intent. IEEE, pp 127–132. doi:10.1109/ITSC.2006.1706730
Spaccapietra S, Parent C, Damiani ML, de Macedo JA, Porto F, Vangenot C (2008) A conceptual view on trajectories. Data Knowl Eng 65:126–146. doi:10.1016/j.datak.2007.10.008
Witten IH, Frank E, Hall MA (2017) Data mining: practical machine learning tools and techniques. Morgan Kaufman, 654 p
Zhang X, Germain C, Sebag M, 2010. Adaptively detecting changes in Autonomic Grid Computing. IEEE, pp 387–392. doi:10.1109/GRID.2010.5698017
Zheng Y, Wang L, Zhang R, Xie X, Ma W-Y, 2008. GeoLife: managing and understanding your past life over maps. IEEE, pp. 211–212. doi:10.1109/MDM.2008.20
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Boukhechba, M., Bouzouane, A., Gaboury, S. et al. Prediction of next destinations from irregular patterns. J Ambient Intell Human Comput 9, 1345–1357 (2018). https://doi.org/10.1007/s12652-017-0519-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12652-017-0519-z