###
Journal of Software:2017.28(11):3043-3057

基于前缀投影技术的大规模轨迹预测模型
乔少杰,韩楠,李天瑞,李荣华,李斌勇,王晓腾,LouisAlbertoGUTIERREZ
(成都信息工程大学 网络空间安全学院, 四川 成都 610225;成都信息工程大学 管理学院, 四川 成都 610103;西南交通大学 信息科学与技术学院, 四川 成都 611756;深圳大学 计算机与软件学院, 广东 深圳 518060;Department of Computer Science, Rensselaer Polytechnic Institute, New York, USA)
Large-Scale Trajectory Prediction Model Based on Prefix Projection Technique
QIAO Shao-Jie,HAN Nan,LI Tian-Rui,LI Rong-Hua,LI Bin-Yong,WANG Xiao-Teng,Louis Alberto GUTIERREZ
(School of Cybersecurity, Chengdu University of Information Technology, Chengdu 610225, China;School of Management, Chengdu University of Information Technology, Chengdu 610103, China;School of Information Science and Technology, Southwest Jiaotong University, Chengdu 611756, China;College of Computer Science and Software Engineering, Shenzhen University, Shenzhen 518060, China;Department of Computer Science, Rensselaer Polytechnic Institute, New York, USA)
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 1106   Download 1191
Received:April 07, 2017    Revised:June 16, 2017
> 中文摘要: 智能手机、车载GPS终端、可穿戴设备产生了海量的轨迹数据,这些数据不仅描述了移动对象的历史轨迹,而且精确地反映出移动对象的运动特点.已有轨迹预测方法的不足在于:不能同时兼具预测的准确性和时效性,有效的轨迹预测受限于路网等局部空间范围,无法处理复杂、大规模位置数据.为了解决上述问题,针对海量移动对象轨迹数据,结合频繁序列模式发现的思想,提出了基于前缀投影技术的轨迹预测模型PPTP(prefix projection based trajectory prediction model),包含两个关键步骤:(1)挖掘频繁轨迹模式,构造投影数据库并递归挖掘频繁前序轨迹模式;(2)轨迹匹配,以不同频繁序列模式作为前缀增量式扩展生成频繁后序轨迹,将大于最小支持度阈值的最长连续轨迹作为结果输出.算法的优势在于:可以通过较短的频繁序列模式,增量式生成长轨迹模式;不会产生无用的候选轨迹,弥补频繁模式挖掘计算代价较高的不足.利用真实大规模轨迹数据进行多角度实验,表明PPTP轨迹预测算法具有较高的预测准确性,相对于1阶马尔可夫链预测算法,其平均预测准确率可以提升39.8%.基于所提出的轨迹预测模型,开发了一个通用的轨迹预测系统,能够可视化输出完整的轨迹路线,为用户路径规划提供辅助决策支持.
Abstract:Smart phones, GPS equipped vehicles and wearable devices can generate a large number of trajectory data. These data can not only describe the historical trajectory of moving objects, but also accurately reflect the characteristics of moving objects. The existing trajectory prediction approaches have the following drawbacks:both prediction accuracy and efficiency cannot be guaranteed together, effective trajectory prediction is limited to road-network constrained local spatial areas, and complex and large-scale location data are difficult to process. Aiming to cope with the aforementioned problems, a prefix projection based trajectory prediction model targeting massive trajectory data of moving objects is proposed by employing the basic idea of frequent sequential patterns discovery. The new model, called PPTP (prefix projection based trajectory prediction model), includes two essential steps:(1) Discovering frequent trajectory patterns by creating projected databases and iteratively mining frequent prefix trajectory patterns from projected databases; (2) Trajectory matching by incrementally extending the postfix trajectory based on each frequent sequential pattern and outputting the longest continuous trajectory that is greater than the threshold of minimum support count. The advantages of the proposed algorithm are that it can generate long-term trajectory patterns via short frequent sequential patterns in an incremental manner, and it will not generate useless candidate trajectory sequences in order to overcome the drawback of time-intensive in discovering frequent sequential patterns. Extensive experiments are conducted on real large-scale trajectory data from multiple aspects, and the results show that PPTP algorithm has very high trajectory prediction accuracy when comparing to 1st-order Markov chain prediction algorithm and the average improvement of accuracy can reach to 39.8%. A generic trajectory prediction system is developed based on the proposed trajectory prediction model, and the complete prediction trajectories are visualized in order to provide assistance for users in path planning.
文章编号:     中图分类号:    文献标志码:
基金项目:国家自然科学基金(61772091,61100045,61363037);教育部人文社会科学研究规划基金(15YJAZH058);教育部人文社会科学研究青年基金(14YJCZH046);成都市软科学项目(2015-RK00-00059-ZF);四川省教育厅资助科研项目(14ZB0458) 国家自然科学基金(61772091,61100045,61363037);教育部人文社会科学研究规划基金(15YJAZH058);教育部人文社会科学研究青年基金(14YJCZH046);成都市软科学项目(2015-RK00-00059-ZF);四川省教育厅资助科研项目(14ZB0458)
Foundation items:National Natural Science Foundation of China (61772091, 61100045, 61363037); Planning Foundation for Humanities and Social Sciences of the Ministry of Education of China (15YJAZH058); Youth Foundation for Humanities and Social Sciences of the Ministry of Education of China (14YJCZH046); Soft Science Foundation of Chengdu (2015-RK00-00059-ZF); Foundation of Educational Commission of Sichuan Province (14ZB0458)
Reference text:

乔少杰,韩楠,李天瑞,李荣华,李斌勇,王晓腾,Louis Alberto GUTIERREZ.基于前缀投影技术的大规模轨迹预测模型.软件学报,2017,28(11):3043-3057

QIAO Shao-Jie,HAN Nan,LI Tian-Rui,LI Rong-Hua,LI Bin-Yong,WANG Xiao-Teng,Louis Alberto GUTIERREZ.Large-Scale Trajectory Prediction Model Based on Prefix Projection Technique.Journal of Software,2017,28(11):3043-3057