基于LSTM的移动对象位置预测算法
|
摘要
移动对象位置预测是基于位置服务的重要组成部分。现有的移动对象位置预测算法有基于马尔可夫链的算法、基于隐马尔可夫模型的算法、基于神经网络的算法等,然而这些算法都无法解决移动对象轨迹数据中位置过多带来的维数灾难问题。为了解决这一问题,提出了位置分布式表示模型(location distributed representation model,LDRM)。该模型将难以处理的表示位置的高维one-hot向量降维成包含移动对象运动模式的低维位置嵌入向量。随后,将该模型与基于长短期记忆网络(long short-term memory,LSTM)的位置预测算法结合为LDRM-LSTM移动对象位置预测算法。真实数据集上的实验表明,与现有算法相比LDRM-LSTM算法在预测准确性上有较大的提升。
Location prediction of moving object is an important part in location based service. Existing location prediction algorithms of moving object include Markov chain, hidden Markov model, neural network, etc. However,existing algorithms cannot solve the problem of dimensionality disaster caused by too many positions of the moving object.s trajectory data. In order to overcome this problem, this paper proposes a location distributed representation model(LDRM). The model reduces the dimension of one-hot vector which represents each location to a low dimension location embedding vector which concludes the moving object. s moving pattern. After that, LDRM is combined with location prediction algorithm based on long short-term memory(LSTM) neural network to get an overall algorithm called LDRM-LSTM. Experiment results on real dataset show that, there has been a major improvement of the LDRM-LSTM algorithm compared with the existing ones, in terms of prediction accuracy.
Location prediction of moving object is an important part in location based service. Existing location prediction algorithms of moving object include Markov chain, hidden Markov model, neural network, etc. However,existing algorithms cannot solve the problem of dimensionality disaster caused by too many positions of the moving object.s trajectory data. In order to overcome this problem, this paper proposes a location distributed representation model(LDRM). The model reduces the dimension of one-hot vector which represents each location to a low dimension location embedding vector which concludes the moving object. s moving pattern. After that, LDRM is combined with location prediction algorithm based on long short-term memory(LSTM) neural network to get an overall algorithm called LDRM-LSTM. Experiment results on real dataset show that, there has been a major improvement of the LDRM-LSTM algorithm compared with the existing ones, in terms of prediction accuracy.
引文
[1]Bao J,Zheng Y,Mokbel M F.Location-based and preferenceaware recommendation using sparse geo-social networking data[C]//Proceedings of the 20th International Conference on Advances in Geographic Information Systems,Redondo Beach,Nov 7-9,2012.New York:ACM,2012:199-208.
[2]Bao J,He T F,Ruan S J,et al.Planning bike lanes based on sharing-bikes.trajectories[C]//Proceedings of the 23rd ACMSIGKDD International Conference on Knowledge Discovery and Data Mining,Halifax,Aug 13-17,2017.New York:ACM,2017:1377-1386.
[3]Feng Z N,Zhu Y M.A survey on trajectory data mining:techniques and applications[J].IEEE Access,2017,4:2056-2067.
[4]Giannotti F,Nanni M,Pinelli F,et al.Trajectory pattern mining[C]//Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,San Jose,Aug 12-15,2007.New York:ACM,2007:330-339.
[5]Killijian M O.Next place prediction using mobility Markov chains[C]//Proceedings of the Workshop on Measurement,Privacy,and Mobility,Helsinki,Augu 13-17,2012.New York:ACM,2012:3.
[6]Krumm J.A Markov model for driver turn prediction[C]//Proceedings of the Society of Automotive Engineers World Congress,Detroit,Apr 14-17,2008.Warrendale:SAE World Congress,2016:1-7.
[7]Morzy M.Prediction of moving object location based on frequent trajectories[C]//LNCS 4263:Proceedings of the21st International Symposium on Computer and Information Sciences,Istanbul,Nov 1-3,2006.Berlin,Heidelberg:Springer,2006:583-592.
[8]Liu Q,Wu S,Wang L,et al.Predicting the next location:a recurrent model with spatial and temporal contexts[C]//Proceedings of the 30th AAAI Conference on Artificial Intelligence,Phoenix,Feb 12-17,2016.Menlo Park:AAAI,2016:194-200.
[9]Bengio Y,Simard P Y,Frasconi P.Learning long-term dependencies with gradient descent is difficult[J].IEEETransactions on Neural Networks,1994,5(2):157-166.
[10]Hochreiter S,Schmidhuber J.Long short-term memory[J].Neural Computation,1997,9(8):1735-1780.
[11]Koren Y,Bell R M,Volinsky C.Matrix factorization techniques for recommender systems[J].IEEE Computer,2009,42(8):30-37.
[12]Xiong L,Chen X,Huang T K,et al.Temporal collaborative filtering with Bayesian probabilistic tensor factorization[C]//Proceedings of the SIAM International Conference on Data Mining,Columbus,Apr 29-May 1,2010.Philadelphia:SIAM,2010:211-222.
[13]Monreale A,Pinelli F,Trasarti R,et al.Where Next:a location predictor on trajectory pattern mining[C]//Proceedings of the15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,Paris,Jun 28-Jul 1,2009.New York:ACM,2009:637-646.
[14]Ying J J C,Lee W C,Weng T C,et al.Semantic trajectory mining for location prediction[C]//Proceedings of the 19th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems,Chicago,Nov 1-4.New York:ACM,2011:34-43.
[15]Morzy M.Mining frequent trajectories of moving objects for location prediction[C]//LNCS 4571:Proceedings of the5th International Conference on Machine Learning and Data Mining in Pattern Recognition,Leipzig,Jul 18-20,2007.Berlin,Heidelberg:Springer,2007:667-680.
[16]Pei J,Han J W,Mortazaviasl B,et al.PrefixSpan:mining sequential patterns efficiently by prefix-projected pattern growth[C]//Proceedings of the International Conference on Data Engineering,Heidelberg,Apr 2-6,2001.Washington:IEEE Computer Society,2001:215.
[17]Rendle S,Freudenthaler C,Schmidt-Thieme L.Factorizing personalized Markov chains for next-basket recommendation[C]//Proceedings of the 19th International Conference on World Wide Web,Raleigh,Apr 26-30,2010.New York:ACM,2010:811-820.
[18]Mathew W,Raposo R,Martins B.Predicting future locations with hidden Markov models[C]//Proceedings of the ACMConference on Ubiquitous Computing,Pittsburgh,Sep 5-8,2012.New York:ACM,2012:911-918.
[19]Al-Molegi A,Jabreel M,Ghaleb B.STF-RNN:space time features-based recurrent neural network for predicting people next location[C]//Proceedings of the IEEE Symposium Series on Computational Intelligence,Athens,Dec 6-9,2016.Piscataway:IEEE,2016:1-7.
[20]Sutskever I,Vinyals O,Le Q V.Sequence to sequence learning with neural networks[C]//Proceedings of the Annual Conference on Neural Information Processing Systems,Montreal,Dec8-13,2014.Red Hook:Curran Associates,2014:3104-3112.
[21]Palangi H,Deng L,Shen Y L,et al.Deep sentence embedding using long short-term memory networks:analysis and application to information retrieval[J].IEEE/ACM Transactions on Audio,Speech and Language Processing,2016,24(4):694-707.
[22]Visin F,Kastner K,Cho K,et al.ReNet:a recurrent neural network based alternative to convolutional networks[J].arXiv:1505.00393,2015.
[23]Malhotra P,Ramakrishnan A,Anand G,et al.LSTM-based encoder-decoder for multi-sensor anomaly detection[J].ar Xiv:1607.00148,2016.
[24]Wu F,Fu K,Wang Y,et al.A spatial-temporal-semantic neural network algorithm for location prediction on moving objects[J].Algorithms,2017,10(2):37.
[25]Jin A,Cheng C Q,Song S H,et al.Regional query of area data based on geohash[J].Geography and Geo-Information Science,2013,29(5):31-35.
[26]Gers F A,Schmidhuber J,Cummins F.Learning to forget:continual prediction with LSTM[J].Neural Computation,2000,12(10):2451-2471.
[27]Qiao S J,Li T R,Han N,et al.Self-adaptive trajectory prediction model for moving objects in big data environment[J].Journal of Software,2015,26(11):2869-2883.
[28]Chen T Q,Guestrin C.XGBoost:a scalable tree boosting system[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,San Francisco,Aug 13-17,2016.New York:ACM,2016:785-794.
[25]金安,程承旗,宋树华,等.基于Geohash的面数据区域查询[J].地理与地理信息科学,2013,29(5):31-35.
[27]乔少杰,李天瑞,韩楠,等.大数据环境下移动对象自适应轨迹预测模型[J].软件学报,2015,26(11):2869-2883.
[2]Bao J,He T F,Ruan S J,et al.Planning bike lanes based on sharing-bikes.trajectories[C]//Proceedings of the 23rd ACMSIGKDD International Conference on Knowledge Discovery and Data Mining,Halifax,Aug 13-17,2017.New York:ACM,2017:1377-1386.
[3]Feng Z N,Zhu Y M.A survey on trajectory data mining:techniques and applications[J].IEEE Access,2017,4:2056-2067.
[4]Giannotti F,Nanni M,Pinelli F,et al.Trajectory pattern mining[C]//Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,San Jose,Aug 12-15,2007.New York:ACM,2007:330-339.
[5]Killijian M O.Next place prediction using mobility Markov chains[C]//Proceedings of the Workshop on Measurement,Privacy,and Mobility,Helsinki,Augu 13-17,2012.New York:ACM,2012:3.
[6]Krumm J.A Markov model for driver turn prediction[C]//Proceedings of the Society of Automotive Engineers World Congress,Detroit,Apr 14-17,2008.Warrendale:SAE World Congress,2016:1-7.
[7]Morzy M.Prediction of moving object location based on frequent trajectories[C]//LNCS 4263:Proceedings of the21st International Symposium on Computer and Information Sciences,Istanbul,Nov 1-3,2006.Berlin,Heidelberg:Springer,2006:583-592.
[8]Liu Q,Wu S,Wang L,et al.Predicting the next location:a recurrent model with spatial and temporal contexts[C]//Proceedings of the 30th AAAI Conference on Artificial Intelligence,Phoenix,Feb 12-17,2016.Menlo Park:AAAI,2016:194-200.
[9]Bengio Y,Simard P Y,Frasconi P.Learning long-term dependencies with gradient descent is difficult[J].IEEETransactions on Neural Networks,1994,5(2):157-166.
[10]Hochreiter S,Schmidhuber J.Long short-term memory[J].Neural Computation,1997,9(8):1735-1780.
[11]Koren Y,Bell R M,Volinsky C.Matrix factorization techniques for recommender systems[J].IEEE Computer,2009,42(8):30-37.
[12]Xiong L,Chen X,Huang T K,et al.Temporal collaborative filtering with Bayesian probabilistic tensor factorization[C]//Proceedings of the SIAM International Conference on Data Mining,Columbus,Apr 29-May 1,2010.Philadelphia:SIAM,2010:211-222.
[13]Monreale A,Pinelli F,Trasarti R,et al.Where Next:a location predictor on trajectory pattern mining[C]//Proceedings of the15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,Paris,Jun 28-Jul 1,2009.New York:ACM,2009:637-646.
[14]Ying J J C,Lee W C,Weng T C,et al.Semantic trajectory mining for location prediction[C]//Proceedings of the 19th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems,Chicago,Nov 1-4.New York:ACM,2011:34-43.
[15]Morzy M.Mining frequent trajectories of moving objects for location prediction[C]//LNCS 4571:Proceedings of the5th International Conference on Machine Learning and Data Mining in Pattern Recognition,Leipzig,Jul 18-20,2007.Berlin,Heidelberg:Springer,2007:667-680.
[16]Pei J,Han J W,Mortazaviasl B,et al.PrefixSpan:mining sequential patterns efficiently by prefix-projected pattern growth[C]//Proceedings of the International Conference on Data Engineering,Heidelberg,Apr 2-6,2001.Washington:IEEE Computer Society,2001:215.
[17]Rendle S,Freudenthaler C,Schmidt-Thieme L.Factorizing personalized Markov chains for next-basket recommendation[C]//Proceedings of the 19th International Conference on World Wide Web,Raleigh,Apr 26-30,2010.New York:ACM,2010:811-820.
[18]Mathew W,Raposo R,Martins B.Predicting future locations with hidden Markov models[C]//Proceedings of the ACMConference on Ubiquitous Computing,Pittsburgh,Sep 5-8,2012.New York:ACM,2012:911-918.
[19]Al-Molegi A,Jabreel M,Ghaleb B.STF-RNN:space time features-based recurrent neural network for predicting people next location[C]//Proceedings of the IEEE Symposium Series on Computational Intelligence,Athens,Dec 6-9,2016.Piscataway:IEEE,2016:1-7.
[20]Sutskever I,Vinyals O,Le Q V.Sequence to sequence learning with neural networks[C]//Proceedings of the Annual Conference on Neural Information Processing Systems,Montreal,Dec8-13,2014.Red Hook:Curran Associates,2014:3104-3112.
[21]Palangi H,Deng L,Shen Y L,et al.Deep sentence embedding using long short-term memory networks:analysis and application to information retrieval[J].IEEE/ACM Transactions on Audio,Speech and Language Processing,2016,24(4):694-707.
[22]Visin F,Kastner K,Cho K,et al.ReNet:a recurrent neural network based alternative to convolutional networks[J].arXiv:1505.00393,2015.
[23]Malhotra P,Ramakrishnan A,Anand G,et al.LSTM-based encoder-decoder for multi-sensor anomaly detection[J].ar Xiv:1607.00148,2016.
[24]Wu F,Fu K,Wang Y,et al.A spatial-temporal-semantic neural network algorithm for location prediction on moving objects[J].Algorithms,2017,10(2):37.
[25]Jin A,Cheng C Q,Song S H,et al.Regional query of area data based on geohash[J].Geography and Geo-Information Science,2013,29(5):31-35.
[26]Gers F A,Schmidhuber J,Cummins F.Learning to forget:continual prediction with LSTM[J].Neural Computation,2000,12(10):2451-2471.
[27]Qiao S J,Li T R,Han N,et al.Self-adaptive trajectory prediction model for moving objects in big data environment[J].Journal of Software,2015,26(11):2869-2883.
[28]Chen T Q,Guestrin C.XGBoost:a scalable tree boosting system[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,San Francisco,Aug 13-17,2016.New York:ACM,2016:785-794.
[25]金安,程承旗,宋树华,等.基于Geohash的面数据区域查询[J].地理与地理信息科学,2013,29(5):31-35.
[27]乔少杰,李天瑞,韩楠,等.大数据环境下移动对象自适应轨迹预测模型[J].软件学报,2015,26(11):2869-2883.