基于Adaboost-Markov模型的移动用户位置预测方法
|
摘要
针对Markov模型在位置预测中存在预测精度不高及匹配稀疏等问题,提出了一种基于Adaboost-Markov模型的移动用户位置预测方法。首先,通过基于转角偏移度与距离偏移量的轨迹划分方法对原始轨迹数据进行预处理,提取出特征点,并采用密度聚类算法将特征点聚类为用户的各个兴趣区域,把原始轨迹数据离散化为由兴趣区域组成的轨迹序列;然后,根据前缀轨迹序列与历史轨迹序列模式树的匹配程度来自适应地确定模型阶数k;最后,采用Adaboost算法根据1～k阶Markov模型的重要程度为其赋予相应的权重系数,组成多阶融合Markov模型,从而实现对移动用户未来兴趣区域的预测。在大规模真实用户轨迹数据集上的实验结果表明,与1阶Markov模型、2阶Markov模型、权重系数平均的多阶融合Markov模型相比, Adaboost-Markov模型的平均预测准确率分别提高了20.83%、11.3%以及5.38%,且具有良好的普适性与多步预测性能。
To solve the problem that Markov model has poor prediction accuracy and sparse matching in location prediction, a mobile user location prediction method based on Adaboost-Markov model was proposed. Firstly, the original trajectory data was preprocessed by a trajectory division method based on angle offset and distance offset to extract feature points, and density clustering algorithm was used to cluster the feature points into interest regions of the user, then the original trajectory data was discretized into a trajectory sequence composed of interest regions. Secondly, according to the matching degree of prefix trajectory sequence and historical trajectory pattern tree, the model order k was adaptively determined. Finally, Adaboost algorithm was used to assign the corresponding weight coefficients according to the importance degree of 1 to k order Markov models to form a multi-order fusion Markov model, realizing the prediction of future interest regions of the mobile user. The experimental results on a large-scale real user trajectory dataset show that the average prediction accuracy of Adaboost-Markov model is improved by 20.83%, 11.3%, and 5.38% respectively compared with the first-order Markov model, the second-order Markov model, and the multi-order fusion Markov model with average weight coefficient, and the proposed model has good universality and multi-step prediction performance.
To solve the problem that Markov model has poor prediction accuracy and sparse matching in location prediction, a mobile user location prediction method based on Adaboost-Markov model was proposed. Firstly, the original trajectory data was preprocessed by a trajectory division method based on angle offset and distance offset to extract feature points, and density clustering algorithm was used to cluster the feature points into interest regions of the user, then the original trajectory data was discretized into a trajectory sequence composed of interest regions. Secondly, according to the matching degree of prefix trajectory sequence and historical trajectory pattern tree, the model order k was adaptively determined. Finally, Adaboost algorithm was used to assign the corresponding weight coefficients according to the importance degree of 1 to k order Markov models to form a multi-order fusion Markov model, realizing the prediction of future interest regions of the mobile user. The experimental results on a large-scale real user trajectory dataset show that the average prediction accuracy of Adaboost-Markov model is improved by 20.83%, 11.3%, and 5.38% respectively compared with the first-order Markov model, the second-order Markov model, and the multi-order fusion Markov model with average weight coefficient, and the proposed model has good universality and multi-step prediction performance.
引文
[1]郭迟,刘经南,方媛,等.位置大数据的价值提取与协同挖掘方法[J].软件学报,2014,25(4):713-730.(GUO C,LIU J N,FANGY,et al.Value extraction and collaborative mining methods for location big data[J].Journal of Software,2014,25(4):713-730.)
[2]WIDHALM P,NITSCHE P,BRANDIE N.Transport mode detection with realistic smartphone sensor data[C]//Proceedings of the21st International Conference on Pattern Recognition.Piscataway,NJ:IEEE,2012:573-576.
[3]SHIH D H,SHIH M H,YEN D C,et al.Personal mobility pattern mining and anomaly detection in the GPS era[J].American Cartographer,2016,43(1):55-67.
[4]GUNDUZ S,YAVANOGLU U,SAGIROGLU S.Predicting next location of twitter users for surveillance[C]//Proceedings of the 12th International Conference on Machine Learning and Applications.Washington,DC:IEEE Computer Society,2013:267-273.
[5]BOGOMOLOV A,LEPRI B,STAIANO J,et al.Once upon a crime:towards crime prediction from demographics and mobile data[C]//ICMI'14:Proceedings of the 16th International Conference on Multimodal Interaction.New York:ACM,2014:427-434.
[6]QIAO S,HAN N,ZHU W,et al.Tra Plan:an effective three-inone trajectory-prediction model in transportation networks[J].IEEETransactions on Intelligent Transportation Systems,2015,16(3):1188-1198.
[7]余雪岗,刘衍珩,魏达,等.用于移动路径预测的混合Markov模型[J].通信学报,2006,27(12):61-69.(YU X G,LIU Y H,WEI D,et al.Hybrid Markov model for mobile path prediction[J].Journal on Communications,2006,27(12):61-69.)
[8]吕明琪,陈岭,陈根才.基于自适应多阶Markov模型的位置预测[J].计算机研究与发展,2010,47(10):1764-1770.(LYU M Q,CHEN L,CHEN G C.Position prediction based on adaptive multiorder Markov model[J].Journal of Computer Research and Development,2010,47(10):1764-1770.)
[9]CHEN M,YU X,LIU Y.Mining moving patterns for predicting next location[J].Information Systems,2015,54:156-168.
[10]宋路杰,孟凡荣,袁冠.基于Markov模型与轨迹相似度的移动对象位置预测算法[J].计算机应用,2016,36(1):39-43.(SONG L J,MENG F R,YUAN G.Moving object location prediction algorithm based on Markov model and trajectory similarity[J].Journal of Computer Applications,2016,36(1):39-43.)
[11]乔少杰,韩楠,李天瑞,等.基于前缀投影技术的大规模轨迹预测模型[J].软件学报,2017,28(11):3043-3057.(QIAO S J,HAN N,LI T R,et al.Large-scale trajectory prediction model based on prefix projection technique[J].Journal of Software,2017,28(11):3043-3057.)
[12]KILLIJIAN M O.Next place prediction using mobility Markov chains[C]//MPM'12:Proceedings of the 1st Workshop on Measurement,Privacy,and Mobility.New York:ACM,2012:Article No.3.
[13]QIAO S J,SHEN D,WANG X,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.
[14]乔少杰,金琨,韩楠,等.一种基于高斯混合模型的轨迹预测算法[J].软件学报,2015,26(5):1048-1063.(QIAO S J,JIN K,HAN N,et al.Trajectory prediction algorithm based on Gaussian mixture model[J].Journal of Software,2015,26(5):1048-1063.)
[15]PATHIRANA P N,SAVKIN A V,JHA S.Robust extended Kalman filter applied to location tracking and trajectory prediction for PCS networks[C]//Proceedings of the 2004 IEEE International Conference on Control Applications.Piscataway,NJ:IEEE,2004,1:63-68.
[16]TRASARTI R,GUIDOTTI R,MONREALE A,et al.My Way:location prediction via mobility profiling[J].Information Systems,2017,64:350-367.
[17]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.New York:ACM,2009:637-646.
[18]YUAN G,ZHAO J,XIA S,et al.Multi-granularity periodic activity discovery for moving objects[J].International Journal of Geographical Information Systems,2016,31(3):435-462.
[19]杨震,王红军,周宇.一种截断距离和聚类中心自适应的聚类算法[J].数据分析与知识发现,2018,2(3):39-48.(YANG Z,WANG H J,ZHOU Y.A clustering algorithm by adaptive cut-off distances and cluster centers[J].Data Analysis and Knowledge Discovery,2018,2(3):39-48.)
[20]李航.统计学习方法[M].北京:清华大学出版社,2012:137-139.(LI H.Statistical Learning Method[M].Beijing:Tsinghua University Press,2012:137-139.)
[21]ZHENG Y,CHEN Y,XIE X,et al.Geo Life2.0:alocation-based social networking service[C]//Proceedings of the 2009 10th International Conference on Mobile Data Management:Systems,Services and Middleware.Washington,DC:IEEE Computer Society,2009:357-358.
[2]WIDHALM P,NITSCHE P,BRANDIE N.Transport mode detection with realistic smartphone sensor data[C]//Proceedings of the21st International Conference on Pattern Recognition.Piscataway,NJ:IEEE,2012:573-576.
[3]SHIH D H,SHIH M H,YEN D C,et al.Personal mobility pattern mining and anomaly detection in the GPS era[J].American Cartographer,2016,43(1):55-67.
[4]GUNDUZ S,YAVANOGLU U,SAGIROGLU S.Predicting next location of twitter users for surveillance[C]//Proceedings of the 12th International Conference on Machine Learning and Applications.Washington,DC:IEEE Computer Society,2013:267-273.
[5]BOGOMOLOV A,LEPRI B,STAIANO J,et al.Once upon a crime:towards crime prediction from demographics and mobile data[C]//ICMI'14:Proceedings of the 16th International Conference on Multimodal Interaction.New York:ACM,2014:427-434.
[6]QIAO S,HAN N,ZHU W,et al.Tra Plan:an effective three-inone trajectory-prediction model in transportation networks[J].IEEETransactions on Intelligent Transportation Systems,2015,16(3):1188-1198.
[7]余雪岗,刘衍珩,魏达,等.用于移动路径预测的混合Markov模型[J].通信学报,2006,27(12):61-69.(YU X G,LIU Y H,WEI D,et al.Hybrid Markov model for mobile path prediction[J].Journal on Communications,2006,27(12):61-69.)
[8]吕明琪,陈岭,陈根才.基于自适应多阶Markov模型的位置预测[J].计算机研究与发展,2010,47(10):1764-1770.(LYU M Q,CHEN L,CHEN G C.Position prediction based on adaptive multiorder Markov model[J].Journal of Computer Research and Development,2010,47(10):1764-1770.)
[9]CHEN M,YU X,LIU Y.Mining moving patterns for predicting next location[J].Information Systems,2015,54:156-168.
[10]宋路杰,孟凡荣,袁冠.基于Markov模型与轨迹相似度的移动对象位置预测算法[J].计算机应用,2016,36(1):39-43.(SONG L J,MENG F R,YUAN G.Moving object location prediction algorithm based on Markov model and trajectory similarity[J].Journal of Computer Applications,2016,36(1):39-43.)
[11]乔少杰,韩楠,李天瑞,等.基于前缀投影技术的大规模轨迹预测模型[J].软件学报,2017,28(11):3043-3057.(QIAO S J,HAN N,LI T R,et al.Large-scale trajectory prediction model based on prefix projection technique[J].Journal of Software,2017,28(11):3043-3057.)
[12]KILLIJIAN M O.Next place prediction using mobility Markov chains[C]//MPM'12:Proceedings of the 1st Workshop on Measurement,Privacy,and Mobility.New York:ACM,2012:Article No.3.
[13]QIAO S J,SHEN D,WANG X,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.
[14]乔少杰,金琨,韩楠,等.一种基于高斯混合模型的轨迹预测算法[J].软件学报,2015,26(5):1048-1063.(QIAO S J,JIN K,HAN N,et al.Trajectory prediction algorithm based on Gaussian mixture model[J].Journal of Software,2015,26(5):1048-1063.)
[15]PATHIRANA P N,SAVKIN A V,JHA S.Robust extended Kalman filter applied to location tracking and trajectory prediction for PCS networks[C]//Proceedings of the 2004 IEEE International Conference on Control Applications.Piscataway,NJ:IEEE,2004,1:63-68.
[16]TRASARTI R,GUIDOTTI R,MONREALE A,et al.My Way:location prediction via mobility profiling[J].Information Systems,2017,64:350-367.
[17]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.New York:ACM,2009:637-646.
[18]YUAN G,ZHAO J,XIA S,et al.Multi-granularity periodic activity discovery for moving objects[J].International Journal of Geographical Information Systems,2016,31(3):435-462.
[19]杨震,王红军,周宇.一种截断距离和聚类中心自适应的聚类算法[J].数据分析与知识发现,2018,2(3):39-48.(YANG Z,WANG H J,ZHOU Y.A clustering algorithm by adaptive cut-off distances and cluster centers[J].Data Analysis and Knowledge Discovery,2018,2(3):39-48.)
[20]李航.统计学习方法[M].北京:清华大学出版社,2012:137-139.(LI H.Statistical Learning Method[M].Beijing:Tsinghua University Press,2012:137-139.)
[21]ZHENG Y,CHEN Y,XIE X,et al.Geo Life2.0:alocation-based social networking service[C]//Proceedings of the 2009 10th International Conference on Mobile Data Management:Systems,Services and Middleware.Washington,DC:IEEE Computer Society,2009:357-358.