ABSTRACT
The pervasiveness of mobile devices and location based services is leading to an increasing volume of mobility data.This side eect provides the opportunity for innovative methods that analyse the behaviors of movements. In this paper we propose WhereNext, which is a method aimed at predicting with a certain level of accuracy the next location of a moving object. The prediction uses previously extracted movement patterns named Trajectory Patterns, which are a concise representation of behaviors of moving objects as sequences of regions frequently visited with a typical travel time. A decision tree, named T-pattern Tree, is built and evaluated with a formal training and test process. The tree is learned from the Trajectory Patterns that hold a certain area and it may be used as a predictor of the next location of a new trajectory finding the best matching path in the tree. Three dierent best matching methods to classify a new moving object are proposed and their impact on the quality of prediction is studied extensively. Using Trajectory Patterns as predictive rules has the following implications: (I) the learning depends on the movement of all available objects in a certain area instead of on the individual history of an object; (II) the prediction tree intrinsically contains the spatio-temporal properties that have emerged from the data and this allows us to define matching methods that striclty depend on the properties of such movements. In addition, we propose a set of other measures, that evaluate a priori the predictive power of a set of Trajectory Patterns. This measures were tuned on a real life case study. Finally, an exhaustive set of experiments and results on the real dataset are presented.
Supplemental Material
- H. Cheng, X. Yan, J. Han, and C.-W. Hsu. Discriminative frequent pattern analysis for effective classification. ICDE 2007: 716--725.Google Scholar
- F. Giannotti, M. Nanni, and D. Pedreschi. Efficient mining of temporally annotated sequences. SIAM, 2006.Google Scholar
- F. Giannotti, M. Nanni, F. Pinelli, and D. Pedreschi. Trajectory pattern mining. KDD 2007: 330--339. Google ScholarDigital Library
- F. Giannotti, D. Pedreschi, and et al. Geopkdd: Geographic privacy-aware knowledge discovery and delivery (european project), 2008.Google Scholar
- H. Jeung, Q. Liu, H. T. Shen, and X. Zhou. A hybrid prediction model for moving objects. ICDE 2008: 70--79. Google ScholarDigital Library
- K. Kianmehr and R. Alhajj. Effective classification by integrating support vector machine and association rule mining. IDEAL 2006: 920--927. Google ScholarDigital Library
- B. Liu, W. Hsu, and Y. Ma. Integrating classification and association rule mining. KDD 1998: 80--86.Google Scholar
- M. Morzy. Prediction of moving object location based on frequent trajectories. ISCIS, volume 4263 of LNCS, pages 583--592. Springer, 2006.Google Scholar
- M. Morzy. Mining frequent trajectories of moving objects for location prediction. MLDM, volume 4571 of LNCS, pages 667--680. Springer, 2007. Google ScholarDigital Library
- M. Nanni, B. Kuijpers, C. Korner, M. May, and D. Pedreschi. Spatiotemporal data mining. In F. Giannotti and D. Pedreschi, editors, Mobility, Data Mining, and Privacy: Geographic Knoweledge Discovery. Springer-Verlag, 2008.Google Scholar
- R. Ortale, E. Ritacco, N. Pelekis, R. Trasarti, G. Costa, F. Giannotti, G. Manco, and C. Renso. Daedalus: A knowledge discovery analysis framework for movement data. SEBD, 2008.Google Scholar
- B. Xu and O. Wolfson. Time-series prediction with applications to traffic and moving objects databases. MobiDE, pages 56--60. ACM, 2003. Google ScholarDigital Library
- G. Yavas, D. Katsaros, O. Ulusoy, and Y. Manolopoulos. A data mining approach for location prediction in mobile environments. D.K.E., 54(2):121--146, 2005. Google ScholarDigital Library
Index Terms
- WhereNext: a location predictor on trajectory pattern mining
Recommendations
Trajectory pattern mining
KDD '07: Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data miningThe increasing pervasiveness of location-acquisition technologies (GPS, GSM networks, etc.) is leading to the collection of large spatio-temporal datasets and to the opportunity of discovering usable knowledge about movement behaviour, which fosters ...
Exploring Spatial-Temporal Trajectory Model for Location Prediction
MDM '11: Proceedings of the 2011 IEEE 12th International Conference on Mobile Data Management - Volume 01Location prediction has attracted a significant amount of research effort. Given an object's recent movements and a future time, the goal of location prediction is to predict the location of this object at the future time specified. Prior works have ...
Hotspot district trajectory prediction
WAIM'10: Proceedings of the 2010 international conference on Web-age information managementTrajectory prediction (TP) of moving objects has grown rapidly to be a new exciting paradigm. However, existing prediction algorithms mainly employ kinematical models to approximate real world routes and always ignore spatial and temporal distance. In ...
Comments