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

来源：软件学报杂志2017年第11期北京时间：

作者：乔少杰,韩楠,李天瑞,李荣华,李斌勇,王晓腾,Louis Alberto GUTIERREZ

单位：乔少杰，成都信息工程大学 网络空间安全学院, 四川 成都 61022511,韩楠，成都信息工程大学 管理学院, 四川 成都 61010302,李天瑞，西南交通大学 信息科学与技术学院, 四川 成都 61175603,李荣华，深圳大学 计算机与软件学院, 广东 深圳 51806004,李斌勇，成都信息工程大学 网络空间安全学院, 四川 成都 61022505,王晓腾，西南交通大学 信息科学与技术学院, 四川 成都 61175606,Louis Alberto GUTIERREZ，Department of Computer Science, Rensselaer Polytechnic Institute, New York, USA07

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

关键词：轨迹预测;前缀投影;频繁序列模式;轨迹匹配;马尔可夫链

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