Please wait a minute...
浙江大学学报(工学版)
浙江大学学报(工学版)
计算机科学     
移动用户下一地点预测新方法
马春来, 单洪, 李志, 朱立新
解放军电子工程学院,安徽 合肥 230037
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
 全文: PDF(1414 KB)   HTML
摘要：

针对目前移动用户地点预测方法对时间的依赖性较强且在小数据集上表现差的问题,提出一种基于皮特曼尤尔及移动马尔可夫链（PY-MMC）模型的下一步地点预测方法.该方法综合考虑目标用户轨迹的短时效应及幂律分布特征.以用户的时间位置熵为参考,计算可预测性因子.依据该因子对皮特曼尤尔模型及移动马尔可夫链模型输出的概率线性加权,建立PY-MMC模型.利用新模型计算每个下一步候选地点的概率,并取最大者输出,完成下一步地点的预测.以“Geolife”及“Foursquare”数据集为例,采用一步准确率、一步候选准确率及平均准确率3个评估指标进行实验.结果表明：新方法能够有效克服基于MMC模型的预测方法准确率随时间波动较大的不足.同时,该方法解决了基于PY模型的预测方法对子序列长度过度依赖的问题.
Abstract:

A next place prediction method based on PitmanYor model and mobility Markov chain（PYMMC） 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 powerlaw distribution features of users’ trajectories. The predictability factor was calculated with temporal location entropy of users. A PYMMC model was constructed depending on the predictability factor, which was used to weight the output probability from PYMMC 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 onestep accuracy, onestep 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 subsequence.
出版日期: 2016-12-08
:  TP 309  
通讯作者: 单洪，男，教授，博导. ORCID: 0000-0002-9669-0215.     E-mail: hshan222@sina.com
作者简介: 马春来（1989—） 男，博士生，从事网络安全、情报挖掘研究. ORCID: 0000-0002-8432-2052. E-mail: eviiive@163.com
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　

引用本文:

马春来, 单洪, 李志, 朱立新. 移动用户下一地点预测新方法[J]. 浙江大学学报(工学版), 10.3785/j.issn.1008-973X.2016.12.018.

MA Chun lai, SHAN Hong, LI Zhi, ZHU Li xin. New next place prediction method for mobile users. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 10.3785/j.issn.1008-973X.2016.12.018.

链接本文:

http://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2016.12.018    或    http://www.zjujournals.com/eng/CN/Y2016/V50/I12/2371

［1］ 郭迟,刘经南,方媛,等.位置大数据的价值提取与协同挖掘方法［J］.软件学报,2014,25(4): 713-730.
GUO Chi, LIU Jingnan, 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 locationbased social networks: a survey ［J］. GeoInformatica, 2015, 19(3): 525-565.
［5］ MIGUEL P C, FRIGNAL J. Geolocation 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 socialhistorical ties on locationbased 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 nextplace 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 Jiangfan, XIONG Yuhong. 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 Qingwu, LI Qingquan, et al. Extracting hierarchical landmark from checkin 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 locationbased social networking service ［C］ ∥ 2009 Tenth International Conference on Mobile Data Management: Systems, Services and Middleware. Taipei: IEEE, 2009: 357-358.
[1] 蒋煦, 张长胜, 戴大蒙, 阮婧, 慕德俊. Android应用程序隐私数据泄露检测[J]. 浙江大学学报(工学版), 2016, 50(12): 2357-2363.
[2] 万志远, 周波. 支持局部调用图生成的指针分析[J]. 浙江大学学报(工学版), 2015, 49(6): 1031-1040.
[3] 万志远, 周波. 基于静态信息流跟踪的输入验证漏洞检测方法[J]. 浙江大学学报(工学版), 2015, 49(4): 683-691.
[4] 王友卫, 刘元宁, 朱晓冬. 用于图像内容认证的半脆弱水印新算法[J]. J4, 2013, 47(6): 969-976.
[5] 李卓,陈健,蒋晓宁,曾宪庭,潘雪增. 基于多域特征的JPEG图像盲检测算法[J]. J4, 2011, 45(9): 1528-1538.
[6] 马晨华, 王进, 裘炅, 陆国栋. 基于情景约束的工作流柔性访问控制模型[J]. J4, 2010, 44(12): 2297-2308.
[7] 陈珂， 胡天磊， 陈刚. 基于角色的信任证覆盖网络中高效信任链搜索[J]. J4, 2010, 44(12): 2241-2250.
[8] 周天舒, 李劲松, 杨一兵, 陈运奇, 薛万国, 赵军平. 区域医疗系统数据真实性保障流程优化[J]. J4, 2010, 44(8): 1484-1489.
[9] 姜励, 陈健, 平玲娣, 陈小平. 多线程程序的信息抹除和降密安全策略[J]. J4, 2010, 44(5): 854-862.
[10] 付剑晶, 王珂. 基于交叉控制流混淆技术的编译方法[J]. J4, 2010, 44(5): 903-909.
[11] 彭志宇, 李善平, 杨朝晖, 林欣. 信任管理中的匿名授权方法[J]. J4, 2010, 44(5): 897-902.
[12] 余利华, 陈刚, 王伟, 陈柯, 董金祥. 一种基于容器的自组织存储模型[J]. J4, 2010, 44(5): 915-922.
[13] 江颉, 张杰, 陈德人. 基于推理的上下文感知RBAC模型设计和实现[J]. J4, 2009, 43(09): 1609-1614.
[14] 陈珂, 邵峰, 陈刚, 等. XML结构化匹配中的位图过滤加速法[J]. J4, 2009, 43(09): 1549-1556.
[15] 黄勇, 陈小平, 陈文智, 等. 支持动态调节的保密性和完整性统一模型[J]. J4, 2009, 43(8): 1377-1382.