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

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

Large-Scale Trajectory Prediction Model Based on Prefix Projection Technique

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.