| Computer Technology |
|
|
|
|
| New next place prediction method for mobile users |
| MA Chun lai, SHAN Hong, LI Zhi, ZHU Li xin |
| Electronic Engineering Institute of PLA, Hefei 230037, China |
|
|
|
Abstract A next place prediction method based on PitmanYor model and mobility Markov chain（PYMMC） model was proposed to solve the problems that mobile users’ next place prediction method depended on time heavily and the performance was poor on small dataset. The method considered both short effect and powerlaw distribution features of users’ trajectories. The predictability factor was calculated with temporal location entropy of users. A PYMMC model was constructed depending on the predictability factor, which was used to weight the output probability from PYMMC model. The maximum probability of each candidate next place was calculated with the new model. Geolife and Foursquare dataset were used in experiment, which was evaluated with onestep accuracy, onestep accuracy of candidate places and average accuracy. Experimental results show that the new method can improve stability of MMC model, and solve the problem that accuracy rate of PY model based method excessively relied on the length of subsequence.
|
|
Published: 08 December 2016
|
|
|
移动用户下一地点预测新方法
针对目前移动用户地点预测方法对时间的依赖性较强且在小数据集上表现差的问题,提出一种基于皮特曼尤尔及移动马尔可夫链（PY-MMC）模型的下一步地点预测方法.该方法综合考虑目标用户轨迹的短时效应及幂律分布特征.以用户的时间位置熵为参考,计算可预测性因子.依据该因子对皮特曼尤尔模型及移动马尔可夫链模型输出的概率线性加权,建立PY-MMC模型.利用新模型计算每个下一步候选地点的概率,并取最大者输出,完成下一步地点的预测.以“Geolife”及“Foursquare”数据集为例,采用一步准确率、一步候选准确率及平均准确率3个评估指标进行实验.结果表明：新方法能够有效克服基于MMC模型的预测方法准确率随时间波动较大的不足.同时,该方法解决了基于PY模型的预测方法对子序列长度过度依赖的问题.
|
|
| ［1］ 郭迟,刘经南,方媛,等.位置大数据的价值提取与协同挖掘方法［J］.软件学报,2014,25(4): 713-730.
GUO Chi, LIU Jingnan, FANG Yuan, et al. Value extraction and collaborative mining methods for location big data ［J］. Ruan Jian Xue Bao/Journal of Software, 2014, 25(4):713-730.
［2］ KRUMM J. Inference attacks on location tracks \[J\]. IEEE Pervasive Computing, 2007,4480: 127-143.
［3］ LU X, WETTER E, BHARTI N, et al. Approaching the limit of predictability in human mobility ［J］. Scientific Reports, 2013, 3（10）: 19.
［4］ BAO J, ZHENG Y, WILKIE D, et al. Recommendations in locationbased social networks: a survey ［J］. GeoInformatica, 2015, 19(3): 525-565.
［5］ MIGUEL P C, FRIGNAL J. Geolocation inference attacks: from modeling to privacy risk assessment ［C］∥ 2014 Tenth European Dependable Computing Conference (EDCC). Tyne: IEEE, 2014: 222-225.
［6］ GUNDUZ S, YAVANOGLU U, SAGIROGLU S. Predicting next location of twitter users for surveillance ［C］∥ 2013 12th International Conference on Machine Learning and Applications (ICMLA). Miami: IEEE, 2013: 267-273.
［7］ BOGOMOLOV A, LEPRI B, STAIANO J, et al. Once upon a crime: towards crime prediction from demographics and mobile data ［C］∥ Proceedings of the 16th International Conference on Multimodal Interaction. Istanbul: ACM, 2014: 110.
［8］ GAO H, TANG J, LIU H. Exploring socialhistorical ties on locationbased social networks ［C］ ∥ The 6th International AAAI Conference on Weblogs and Social Media. Dublin: AAAI, 2012: 18.
［9］ CHO E, MYERS S A, LESKOVEC J. Friendship and mobility: user movement in location-based social networks ［C］ ∥ Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Diego: ACM, 2011: 19.
［10］ CHEN M, YU X, LIU Y. Mining moving patterns for predicting next location［J］. Information Systems, 2015, 54: 156-168.
［11］ GAMBS S, KILLIJIAN M, MIGUEL P C. De anonymization attack on geolocated data ［J］. Journal of Computer and System Sciences, 2014, 80(8): 1597-1614.
［12］ DASH M, KEE K K, GOMES J B, et al. Next place prediction by understanding mobility patterns ［C］∥ 2015 IEEE International Conference on Pervasive Computing and Communication Workshops. St.Louis: IEEE,2015: 469-474.
［13］ BAUMANN P, KLEIMINGER W, SANTINI S. The influence of temporal and spatial features on the performance of nextplace prediction algorithms ［C］∥ Proceedings of the 2013 ACM International Joint Conference On Pervasive And Ubiquitous Computing.Zurich: ACM, 2013: 110.
［14］ 丰江帆,熊雨虹.一种基于个人位置信息的重要地点识别方法［J］.小型微型计算机系统,2013,34(3): 503-507.
FENG Jiangfan, XIONG Yuhong. An important place identification algorithm based on personal GPS location ［J］. Journal of Chinese Computer Systems, 2013, 34(3): 503507.
［15］ 王明,胡庆武,李清泉,等.基于位置签到数据的城市分层地标提取［J］.计算机学报.2016,39(2): 405-413.
WANG Ming, HU Qingwu, LI Qingquan, et al. Extracting hierarchical landmark from checkin data ［J］. Chinese Journal of Computers, 2016, 39(2):405-413.
［16］ CLAUSET A, SHALIZI C R, NEWMAN M E. Power-law distributions in empirical data ［J］. SIAM Review, 2009, 51(4): 661-703.
［17］ RODRIGUEZ A, LAIO A. Clustering by fast search and find of density peaks ［J］. Science, 2014, 344(6191): 1492-1496.
［18］ TEH Y W. A hierarchical Bayesian language model based on Pitman-Yor processes ［C］∥ Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the Association for Computational Linguistics. Stroudsburg: ACM, 2006: 985-992.
［19］ SONG C, QU Z, BLUMM N, et al. Limits of predictability in human mobility ［J］. Science, 2010, 327(5968): 1018-1021.
［20］ ZHENG Y, CHEN Y, XIE X, et al. Geolife2.0: A locationbased social networking service ［C］ ∥ 2009 Tenth International Conference on Mobile Data Management: Systems, Services and Middleware. Taipei: IEEE, 2009: 357-358. |
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|
