一种聚类隐马尔可夫模型的时空轨迹预测算法
|
摘要
随着"互联网+"的高速发展,大数据的不断产生,人们对时空轨迹的数据分析也越来越多.本文针对海量的用户轨迹数据进行研究,提出一种基于分区域的隐马尔可夫模型用以解决时空轨迹序列的预测问题.该模型首先通过聚类将一片区域内的时空序列分成多个小区域,每个小区域内再通过聚类确定多个隐状态和发射序列,然后针对每个小区域进行隐马尔可夫模型的训练得出最终模型.预测时通过已知的时空序列,找到对应的区域模型,通过维特比算法计算出最佳隐状态序列,再结合转移矩阵做出下一个轨迹点的预测.实验表明,该模型具有较高的学习速度,且预测精度较高.
With the rapid development of"Internet plus"and continuous generation of large data,the spatio-temporal trajectory data analysis is also more and more. Aiming at massive user trajectory data,a hidden Markov model based on subarea is proposed to solve the prediction problem of spatio-temporal trajectory. Firstly,the spatio-temporal sequence in a region will be divided into multiple small regions by clustering. In each small domain,multiple hidden states and emission sequences are determined by clustering. Then,the hidden Markov model is trained for each small domain to get the final model. In the prediction,we find the corresponding region model through the known space-time sequence,calculate the best hidden state sequence through Vitby algorithm,and combine the transfer matrix to make the prediction of the next trajectory. The experiment shows that the model has high learning speed and high prediction precision.
With the rapid development of"Internet plus"and continuous generation of large data,the spatio-temporal trajectory data analysis is also more and more. Aiming at massive user trajectory data,a hidden Markov model based on subarea is proposed to solve the prediction problem of spatio-temporal trajectory. Firstly,the spatio-temporal sequence in a region will be divided into multiple small regions by clustering. In each small domain,multiple hidden states and emission sequences are determined by clustering. Then,the hidden Markov model is trained for each small domain to get the final model. In the prediction,we find the corresponding region model through the known space-time sequence,calculate the best hidden state sequence through Vitby algorithm,and combine the transfer matrix to make the prediction of the next trajectory. The experiment shows that the model has high learning speed and high prediction precision.
引文
[1] Niedermayer J,Emrich T,Renz M,et al. Probabilistic nearest neighbor queries on uncertain moving object trajectories[J]. Proceedings of the Vldb Endow ment,2013,7(3):205-216.
[2]Monreale A,Pinelli F,Trasarti R,et al. WhereNext:a location predictor on trajectory pattern mining[C]. ACM SIGKDD International Conference on Know ledge Discovery and Data M ining,Paris,France,ACM,2009:637-646.
[3]Yang Jie,Xu Jian,Xu Ming,et al. Predicting next location using a variable order M arkov model[C]. ACM Sigspatial International Workshop on Geostreaming,ACM,2014:37-42.
[4]Nodari A,Nurminen J,Siekkinen M. Energy-efficient position tracking via trajectory modeling[C]. International Workshop on M obility in the Evolving Internet Architecture,ACM,2015:33-38.
[5]Chen S,Xu J,Joachims T. Multi-space probabilistic sequence modeling[C]. ACM SIGKDD International Conference on Know ledge Discovery and Data M ining,ACM,2013:865-873.
[6]Chen M,Liu Y,Yu X. NLPMM:a next location predictor with M arkov modeling[M]. Advances in Know ledge Discovery and Data M ining,Springer International Publishing,2014:186-197.
[7]Figueiredo F,Ribeiro B,Almeida J M,et al. TribeFlow:mining&predicting user trajectories[C]. International Conference on World Wide Web,International World Wide Web Conferences Steering Committee,2016:695-706.
[8]Feng S,Li X,Zeng Y,et al. Personalized ranking metric embedding for next new POI recommendation[C]. International Conference on Artificial Intelligence,AAAI Press,2015:2069-2075.
[9] Zheng Yu,Zhang Li-zhu,Xie Xing,et al. Mining interesting locations and travel sequences from GPS trajectories[J]. Proceedings of the 18th International Conference on World Wide Web,M adrid,Spain,2009:791-800.
[10]Jeung H,Liu Q,Shen H T,et al. A Hybrid prediction model for moving objects[C]. IEEE,International Conference on Data Engineering,IEEE,2008:70-79.
[11] Morzy,Mikoaj. Prediction of moving object location based on frequent trajectories[C]. Computer and Information Sciences-Iscis,International Symposium,Istanbul,Turkey,November 1-3,2006,Proceedings,DBLP,2006:583-592.
[12]Morzy M. Mining frequent trajectories of moving objects for location prediction[C]. International Conference on Machine Learning and Data Mining in Pattern Recognition,Springer-Verlag,2007:667-680.
[13]Chaney A J B,Blei D M,Eliassi-Rad T. A probabilistic model for using social netw orks in personalized item recommendation[C].ACM Conference on Recommender Systems,ACM,2015:43-50.
[14]Song Hai-tao,Wei Da-wei,Tang Guang-ming,et al. Anomaly detection of single user behaviors based on pattern mining[J]. Journal of Chinese Computer Systems,2016,37(2):221-226.
[15]Pei Jian,Peng Dun-lu. LCSS-based computing similarity between trajectories for vehicles[J]. Journal of Chinese Computer Systems,2016,37(6):1197-1202.
[14]宋海涛,韦大伟,汤光明,等.基于模式挖掘的用户行为异常检测算法[J].小型微型计算机系统,2016,37(2):221-226.
[15]裴剑,彭敦陆.一种基于LCSS的相似车辆轨迹查找方法[J].小型微型计算机系统,2016,37(6):1197-1202.
[2]Monreale A,Pinelli F,Trasarti R,et al. WhereNext:a location predictor on trajectory pattern mining[C]. ACM SIGKDD International Conference on Know ledge Discovery and Data M ining,Paris,France,ACM,2009:637-646.
[3]Yang Jie,Xu Jian,Xu Ming,et al. Predicting next location using a variable order M arkov model[C]. ACM Sigspatial International Workshop on Geostreaming,ACM,2014:37-42.
[4]Nodari A,Nurminen J,Siekkinen M. Energy-efficient position tracking via trajectory modeling[C]. International Workshop on M obility in the Evolving Internet Architecture,ACM,2015:33-38.
[5]Chen S,Xu J,Joachims T. Multi-space probabilistic sequence modeling[C]. ACM SIGKDD International Conference on Know ledge Discovery and Data M ining,ACM,2013:865-873.
[6]Chen M,Liu Y,Yu X. NLPMM:a next location predictor with M arkov modeling[M]. Advances in Know ledge Discovery and Data M ining,Springer International Publishing,2014:186-197.
[7]Figueiredo F,Ribeiro B,Almeida J M,et al. TribeFlow:mining&predicting user trajectories[C]. International Conference on World Wide Web,International World Wide Web Conferences Steering Committee,2016:695-706.
[8]Feng S,Li X,Zeng Y,et al. Personalized ranking metric embedding for next new POI recommendation[C]. International Conference on Artificial Intelligence,AAAI Press,2015:2069-2075.
[9] Zheng Yu,Zhang Li-zhu,Xie Xing,et al. Mining interesting locations and travel sequences from GPS trajectories[J]. Proceedings of the 18th International Conference on World Wide Web,M adrid,Spain,2009:791-800.
[10]Jeung H,Liu Q,Shen H T,et al. A Hybrid prediction model for moving objects[C]. IEEE,International Conference on Data Engineering,IEEE,2008:70-79.
[11] Morzy,Mikoaj. Prediction of moving object location based on frequent trajectories[C]. Computer and Information Sciences-Iscis,International Symposium,Istanbul,Turkey,November 1-3,2006,Proceedings,DBLP,2006:583-592.
[12]Morzy M. Mining frequent trajectories of moving objects for location prediction[C]. International Conference on Machine Learning and Data Mining in Pattern Recognition,Springer-Verlag,2007:667-680.
[13]Chaney A J B,Blei D M,Eliassi-Rad T. A probabilistic model for using social netw orks in personalized item recommendation[C].ACM Conference on Recommender Systems,ACM,2015:43-50.
[14]Song Hai-tao,Wei Da-wei,Tang Guang-ming,et al. Anomaly detection of single user behaviors based on pattern mining[J]. Journal of Chinese Computer Systems,2016,37(2):221-226.
[15]Pei Jian,Peng Dun-lu. LCSS-based computing similarity between trajectories for vehicles[J]. Journal of Chinese Computer Systems,2016,37(6):1197-1202.
[14]宋海涛,韦大伟,汤光明,等.基于模式挖掘的用户行为异常检测算法[J].小型微型计算机系统,2016,37(2):221-226.
[15]裴剑,彭敦陆.一种基于LCSS的相似车辆轨迹查找方法[J].小型微型计算机系统,2016,37(6):1197-1202.