Predicting Future Locations with Deep Fuzzy-LSTM Network

doi:10.11947/j.AGCS.2018.20170268

Abstract

Abstract: Current studies on trajectory prediction have two limitations. Spatial division approaches in most existing studies lead to sharp boundary problem of predicting methods. On the other hand, most of traditional predicting models such as Markov could only use a few latest historical locations, making long-term prediction inaccurate. To overcome these limitations,a location prediction method based on deepFuzzy-LSTM Network is proposed. The method employs a long short term memory based network to solve the long-term dependencies problem. By defining the fuzzy-based trajectory and the improved LSTM cell structure, our method solves the sharp boundary problem caused by space partition. It also considers both period and closeness of movement patterns in making prediction. We compare classical NLPMM, Naïve-LSTM and Fuzzy-LSTM methods with a cell signaling dataset consisting of the continuous trajectories of one hundred thousand city residents in 15 workdays. Results show that the proposed Fuzzy-LSTM method gets a precision of 83.98%, 6.95% higher than the NLPMM model and 4.36% higher than Naïve-LSTM model.

Key words: location prediction, fuzzy space partition, long short term memory network (LSTM), data mining, deep learning

CLC Number:

P208

LI Mingxiao, ZHANG Hengcai, QIU Peiyuan, CHENG Shifen, CHEN Jie, LU Feng. Predicting Future Locations with Deep Fuzzy-LSTM Network[J]. Acta Geodaetica et Cartographica Sinica, 2018, 47(12): 1660-1669.

References

[1] ZHENG Yu. Trajectory Data Mining:An Overview[J]. ACM Transactions on Intelligent Systems and Technology (TIST), 2015, 6(3):29.
[2] 陆锋, 刘康, 陈洁. 大数据时代的人类移动性研究[J]. 地球信息科学学报, 2014, 16(5):665-672. LU Feng, LIU Kang, CHEN Jie. Research on Human Mobility in Big Data Era[J]. Journal of Geo-Information Science, 2014, 16(5):665-672.
[3] FORMENTIN S, BIANCHESSI A G, SAVARESI S M. On the Prediction of Future Vehicle Locations in Free-floating Car Sharing Systems[C]//2015 IEEE Intelligent Vehicles Symposium. Seoul, South Korea:IEEE, 2015:1006-1011.
[4] CHEN Meng, LIU Yang, YU Xiaohui. NLPMM:A Next Location Predictor with Markov Modeling[C]//Pacific-Asia Conference on Knowledge Discovery and Data Mining. Cham:Springer, 2014:186-197.
[5] QIAO Shaojie, SHEN Dayong, WANG Xiaoteng, et al. A Self-adaptive Parameter Selection Trajectory Prediction Approach via Hidden Markov Models[J]. IEEE Transactions on Intelligent Transportation Systems, 2015, 16(1):284-296.
[6] WIEST J, HÖFFKEN M, KREβEL U, et al. Probabilistic Trajectory Prediction with Gaussian Mixture Models[C]//2012 IEEE Intelligent Vehicles Symposium. Alcala de Henares, Spain:IEEE, 2012:141-146.
[7] CHAPUIS B, MORO A, KULKARNI V, et al. Capturing Complex Behaviour for Predicting Distant Future Trajectories[C]//Proceedings of the 5th ACM SIGSPATIAL International Workshop on Mobile Geographic Information Systems. Burlingame, California:ACM, 2016:64-73.
[8] MUNTEAN C I, NARDINI F M, SILVESTRI F, et al. On Learning Prediction Models for Tourists Paths[J]. ACM Transactions on Intelligent Systems and Technology (TIST), 2015, 7(1):8.
[9] 乔少杰, 金琨, 韩楠, 等. 一种基于高斯混合模型的轨迹预测算法[J]. 软件学报, 2015, 26(5):1048-1063. QIAO Shaojie, JIN Kun, HAN Nan, et al. Trajectory Prediction Algorithm Based on Gaussian Mixture Model[J]. Journal of Software, 2015, 26(5):1048-1063.
[10] PREVOST C G, DESBIENS A, GAGNON E. Extended Kalman Filter for State Estimation and Trajectory Prediction of a Moving Object Detected by an Unmanned Aerial Vehicle[C]//2007 American Control Conference. New York:IEEE, 2007:1805-1810.
[11] JEUNG H, LIU Qing, SHEN Hengtao, et al. A Hybrid Prediction Model for Moving Objects[C]//Proceedings of the IEEE 24th International Conference on Data Engineering. Cancun, Mexico:IEEE, 2008:70-79.
[12] MONREALE A, PINELLI F, TRASARTI R, et al. Wherenext:A Location Predictor on Trajectory Pattern Mining[C]//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Paris, France:ACM, 2009:637-646.
[13] YING J J C, LEE W C, TSENG V S. Mining Geographic-Temporal-semantic Patterns in Trajectories for Location Prediction[J]. ACM Transactions on Intelligent Systems and Technology (TIST), 2013, 5(1):2.
[14] OZER M, KELES I, TOROSLU H, et al. Predicting the Location and Time of Mobile Phone Users by Using Sequential Pattern Mining Techniques[J]. The Computer Journal, 2016, 59(6):908-922.
[15] CHEN Meng, LIU Yang, YU Xiaohui. Predicting Next Locations with Object Clustering and Trajectory Clustering[C]//Pacific-Asia Conference on Knowledge Discovery and Data Mining. Cham:Springer, 2015:344-356.
[16] CHAPUIS B, MORO A, KULKARNI V, et al. Capturing Complex Behaviour for Predicting Distant Future Trajectories[C]//Proceedings of the 5th ACM SIGSPATIAL International Workshop on Mobile Geographic Information Systems. Burlingame, California:ACM, 2016:64-73.
[17] QIAO Shaojie, TANG Changjie, JIN Huidong, et al. Putmode:Prediction of Uncertain Trajectories in Moving Objects Databases[J]. Applied Intelligence, 2010, 33(3):370-386.
[18] SHAH R, ROMIJNDERS R. Applying Deep Learning to Basketball Trajectories[J]. arXiv preprint arXiv:1608.03793, 2016.
[19] MATHEW W, RAPOSO R, MARTINS B. Predicting Future Locations with Hidden Markov Models[C]//Proceedings of the 2012 ACM Conference on Ubiquitous Computing. Pittsburgh, Pennsylvania:ACM, 2012:911-918.
[20] 李万高, 赵雪梅, 孙德厂. 基于改进贝叶斯方法的轨迹预测算法研究[J]. 计算机应用, 2013, 33(7):1960-1963. LI Wangao, ZHAO Xuemei, SUN Dechang. Prediction of Trajectory Based on Modified Bayesian Inference[J]. Journal of Computer Applications, 2013, 33(7):1960-1963.
[21] CHUNG J, PAEK O, LEE J, et al. Temporal Pattern Mining of Moving Objects for Location-based Service[C]//Proceedings of the 13th International Conference on Database and Expert Systems Applications. Berlin/Heidelberg:Springer, 2002:331-340.
[22] 向隆刚, 邵晓天. 载体轨迹停留信息提取的核密度法及其可视化[J]. 测绘学报, 2016, 45(9):1122-1131. DOI:10.11947/j.AGCS.2016.20150347. XIANG Longgang, SHAO Xiaotian. Visualization and Extraction of Trajectory Stops Based on Kernel-density[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(9):1122-1131. DOI:10.11947/j.AGCS.2016.20150347.
[23] LI Zhenhui. Spatiotemporal Pattern Mining:Algorithms and Applications[M]//AGGARWAL C, HAN Jiawei. Frequent Pattern Mining. Cham:Springer, 2014:283-306.
[24] GERS F A, SCHMIDHUBER J, CUMMINS F. Learning to Forget:Continual Prediction with LSTM[J]. Neural Computation, 2000, 12(10):2451-2471.
[25] SHI Xingjian, CHEN Zhourong, WANG Hao, et al. Convolutional LSTM Network:A Machine Learning Approach for Precipitation Nowcasting[C]//Proceedings of the 28th International Conference on Neural Information Processing Systems. Montreal, Canada:MIT Press, 2015:802-810.
[26] SUTSKEVER I, MARTENS J, HINTON G. Generating Text with Recurrent Neural Networks[C]//Proceedings of the 28th International Conference on Machine Learning (ICML-11). Bellevue, Washington:Omnipress, 2011:1017-1024.
[27] SONG Chaoming, QU Zehui, BLUMM N, et al. Limits of Predictability in Human Mobility[J]. Science, 2010, 327(5968):1018-1021.
[28] 鲁仕维, 方志祥, 萧世伦, 等. 城市群体移动模式研究中空间尺度影响的定量分析[J]. 武汉大学学报(信息科学版), 2016, 41(9):1199-1204. LU Shiwei, FANG Zhixiang, XIAO Shilun, et al. Quantitative Analysis of the Effects of Spatial Scales on Intra-urban Human Mobility[J]. Geomatics and Information Science of Wuhan University, 2016, 41(9):1199-1204.
[29] VIEGAS J M, MARTINEZ L M, SILVA E A. Effects of the Modifiable Areal Unit Problem on the Delineation of Traffic Analysis Zones[J]. Environment and Planning B:Planning and Design, 2009, 36(4):625-643.
[30] GIANNOTTI F, NANNI M, PEDRESCHI D, et al. Unveiling the Complexity of Human Mobility by Querying and Mining Massive Trajectory Data[J]. The VLDB Journal, 2011, 20(5):695-719.
[31] XU Yang, SHAW S L, ZHAO Ziliang, et al. Another Tale of Two Cities:Understanding Human Activity Space Using Actively Tracked Cellphone Location Data[J]. Annals of the American Association of Geographers, 2016, 106(2). DOI:10.1080/00045608.2015.1120147.
[32] FANG Zhixiang, YANG Xiping, XU Yang, et al. Spatiotemporal Model for Assessing the Stability of Urban Human Convergence and Divergence Patterns[J]. International Journal of Geographical Information Science, 2017:1-23. DOI:10.1080/13658816.2017.1346256.