基于前缀投影技术的大规模轨迹预测模型

作     者：乔少杰 韩楠 李天瑞 李荣华 李斌勇 王晓腾 Louis Alberto GUTIERREZ QIAO Shao-Jie;HAN Nan;LI Tian-Rui;LI Rong-Hua;LI Bin-Yong;WANG Xiao-Teng;Louis Alberto GUTIERREZ

作者机构：成都信息工程大学网络空间安全学院四川成都610225 成都信息工程大学管理学院四川成都610103 西南交通大学信息科学与技术学院四川成都611756 深圳大学计算机与软件学院广东深圳518060 Department of Computer ScienceRensselaer Polytechnic InstituteNew YorkUSA 

出 版 物：《软件学报》 (Journal of Software)

年 卷 期：2017年第28卷第11期

页      面：3043-3057页

核心收录：

学科分类：08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 081202[工学-计算机软件与理论] 

基　　金：国家自然科学基金(61772091,61100045,61363037) 教育部人文社会科学研究规划基金(15YJAZH058) 教育部人文社会科学研究青年基金(14YJCZH046) 成都市软科学项目(2015-RK00-00059-ZF) 四川省教育厅资助科研项目(14ZB0458)~~ 

主　　题：轨迹预测 前缀投影 频繁序列模式 轨迹匹配 马尔可夫链 

摘      要：智能手机、车载GPS终端、可穿戴设备产生了海量的轨迹数据,这些数据不仅描述了移动对象的历史轨迹,而且精确地反映出移动对象的运动特点.已有轨迹预测方法的不足在于:不能同时兼具预测的准确性和时效性,有效的轨迹预测受限于路网等局部空间范围,无法处理复杂、大规模位置数据.为了解决上述问题,针对海量移动对象轨迹数据,结合频繁序列模式发现的思想,提出了基于前缀投影技术的轨迹预测模型PPTP(prefix projection based trajectory prediction model),包含两个关键步骤:(1)挖掘频繁轨迹模式,构造投影数据库并递归挖掘频繁前序轨迹模式;(2)轨迹匹配,以不同频繁序列模式作为前缀增量式扩展生成频繁后序轨迹,将大于最小支持度阈值的最长连续轨迹作为结果输出.算法的优势在于:可以通过较短的频繁序列模式,增量式生成长轨迹模式;不会产生无用的候选轨迹,弥补频繁模式挖掘计算代价较高的不足.利用真实大规模轨迹数据进行多角度实验,表明PPTP轨迹预测算法具有较高的预测准确性,相对于1阶马尔可夫链预测算法,其平均预测准确率可以提升39.8%.基于所提出的轨迹预测模型,开发了一个通用的轨迹预测系统,能够可视化输出完整的轨迹路线,为用户路径规划提供辅助决策支持.