计算机科学 ›› 2018, Vol. 45 ›› Issue (12): 288-292.doi: 10.11896／j.issn.1002-137X.2018.12.046
李昇智, 乔建忠, 林树宽
LI Sheng-zhi, QIAO Jian-zhong, LIN Shu-kuan
摘要： 随着移动通信技术和车载定位系统的发展和广泛应用,基于位置服务越来越受到人们的关注。位置预测技术是其重要组成部分,并有着广泛的应用。在实际应用中,由于采集点丢失或新用户出现等,GPS轨迹数据往往具有稀疏特性,使得基于单个用户数据的位置预测的准确率较低。针对这种情况,文中提出了基于移动行为相似性和用户聚类的Markov位置预测方法。首先,为使预测的位置具有物理意义,提出了基于Voronoi图的区域划分方法,并基于区域轨迹进行位置预测;其次,提出了同时考虑用户转移特性和用户区域特性的移动行为相似性计算方法;再次,根据移动行为相似性对用户进行聚类,并在聚类的用户组上采用一阶Markov模型进行位置预测,提高了位置预测的准确性。在真实GPS轨迹数据上的实验表明了所提方法的有效性。
中图分类号:
| [1]ZHOU A Y,YANG B,JIN C Q,et al.Location-based services:architecture and progress [J].Chinese Journal of computers,2011,34(7):1155-1171.(in Chinese) 周傲英,杨彬,金澈清,等.基于位置的服务:架构与进展 [J].计算机学报,2011,34(7):1155-1171. [2]BAO J,ZHENG Y,MOKBEL M F.Location-based and prefe-rence-aware recommendation using sparse geo-social networking data[C]∥Proceedings of the 20th International Conference on Advances in Geographic Information Systems.USA:ACM,2012:199-208. [3]LI H F,DONG L H,HAN J F.A Mobile Ordering SchemeBased on LBS[C]∥Proceedings of the 4th International Confe-rence on Emerging Intelligent Data and Web Technologies.China:IEEE,2013:398-401. [4]TAO Y,FALOUTSOS C,PAPADIAS D,et al.Prediction and indexing of moving objects with unknown motion patterns[C]∥Proceedings of the 2004 ACM SIGMOD International Confe-rence on Management of Data.New York:ACM,2004:611-622. [5]AGGAREAL C C,AGRAWAL D.On nearest neighbor indexing of nonlinear trajectories[C]∥Proceedings of the 22th ACM SIGMOD-SIGACT-SIGART Symp.on Principles of Database Systems.New York:ACM,2003:252-259. [6]CHENG X L,XU X L,WANG Z Y,et al.Location Prediction Based On Sequenlial Mining [J].Industrial Control Computer,2013,26(3):70-72.(in Chinese) 程贤亮,徐小良,王中友,等.基于序列挖掘的用户移动位置预测[J].工业控制计算机,2013,26(3):70-72. [7]PEI J,HAN J W,ASL B M,et al.PrefixSpan:Mining SequentialPatterns Efficiently by Prefix Projected Pattern Growth[C]∥Proceedings of the 17th International Conference on Data Engineering.2001:215-224. [8]MORZY M.Prediction of moving object location based on frequent trajectories[C]∥The 21st International Symposium on Computer and Information Sciences(ISCIS’2006).2006:583-592. [9]AGRAWAL R,SRIKANT R.Fast algorithms for mining asso-ciation rules[C]∥Proceedings of the 20th International Confe-rence on Very Large Data Bases.VLDB,1994:487-499. [10]GIDÓFALVI G,DONG F.When and where next:individualmobility prediction[C]∥Proceedings of the First ACM SIGSPATIAL International Workshop on Mobile Geographic Information Systems.ACM,2012:57-64. [11]LV M Q,CHEN L,CHEN G C.Position Prediction Based on Adaptive Multi-Order Markov Model[J].Journal of Computer Research and Development,2010,47(10):1764-1770.(in Chinese) 吕明琪,陈岭,陈根才.基于自适应多阶Markov模型的位置预测[J].计算机研究与发展,2010,47(10):1764-1770. [12]YU X G,LIU Y H,WEI D,et al.Hybrid Markov mode for mobile path prediction[J].Journal on Communications,2006,27 (12):61-69.(in Chinese) 余雪岗,刘衍珩,魏达,等.用于移动路径预测的混合Markov模型[J].通信学报,2006,27(12):61-69. [13]CHEN Z B,SHEN H T,ZHOU X F.Discovering popular routes from trajectories[C]∥Proceedings of the 27th ICDE International Conference on Data Engineering.Germany,IEEE,2011:900-911. [14]DEMIRYUREK U,SHAHABI C.Indexing network voronoidiagrams[C]∥Database Systems for Advanced Applications.Springer Berlin Heidelberg,2012:526-543. [15]CHEN C.The establishment and application of voronoi diagram in computer mapping[J].Acta Geodaetica et Cartographica Sinica,1987,16(3):223-231.(in Chinese) 陈春.泰森多边形的建立及其在计算机制图中的应用[J].测绘学报,1987,16(3):223-231. [16]PAVAN M,PELILLO M.Dominant sets and pairwise clustering[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2007,29(1):167-172. [17]YUAN J,ZHENG Y,XIE X,et al.Driving with knowledge from the physical world[C]∥Proceedings of International Conference on the 17th ACM SIGKDD Knowledge Discovery and Data Mining.USA,ACM,2011:316-324. |
| [1] | 刘嘉琛, 秦小麟, 朱润泽. 基于LSTM-Attention的RFID移动对象位置预测 Prediction of RFID Mobile Object Location Based on LSTM-Attention 计算机科学, 2021, 48(3): 188-195. https://doi.org/10.11896/jsjkx.200600134 |
| [2] | 夏扬波, 杨文忠, 张振宇, 王庆鹏, 石研. 一种移动无线传感器网络的节点位置预测方法 Node Position Prediction Method for Mobile Wireless Sensor Networks 计算机科学, 2018, 45(8): 113-118. https://doi.org/10.11896/j.issn.1002-137X.2018.08.020 |
| [3] | 陈波,张云贺,邱少明,王运明. 基于IRWQS与模糊特征的位置预测算法 Position Prediction Algorithm Based on IRWQS and Fuzzy Features 计算机科学, 2018, 45(6A): 318-322. |
| [4] | 王振朝,侯欢欢,连蕊. WSN中基于位置预测的地理路由算法 Geographic Routing Algorithm Based on Location Prediction in WSN 计算机科学, 2018, 45(5): 59-63. https://doi.org/10.11896/j.issn.1002-137X.2018.05.010 |
| [5] | 佟振明, 刘志鹏. 大型多人在线角色扮演游戏的下一地点预测 Next Place Prediction of Massively Multiplayer Online Role-playing Games 计算机科学, 2018, 45(11A): 453-457. |
| [6] | 薛迪,吴礼发,李华波,洪征. TraDR:一种基于轨迹分解重构的移动社交网络位置预测方法 TraDR:A Destination Prediction Method Based on Trajectory Decomposition and Reconstruction in Geo-social Networks 计算机科学, 2016, 43(3): 93-98. https://doi.org/10.11896/j.issn.1002-137X.2016.03.019 |
| [7] | 郭艳卿,赵锐,孔祥维,付海燕,蒋金平. 基于事件要素加权的新闻摘要提取方法 News-summarization Extraction Method Based on Weighted Event Elements Strategy 计算机科学, 2016, 43(1): 237-241. https://doi.org/10.11896/j.issn.1002-137X.2016.01.051 |
| [8] | 王梦冉,乔少杰,于珊珊. 蜂窝网中基于位置预测的切换算法 Handover Algorithm Based on Location Prediction in Cellular Network 计算机科学, 2014, 41(Z11): 187-190. |
| [9] | . 移动对象位置预测的索引方法 计算机科学, 2006, 33(8): 170-172. |
|
||
首页