Journal of Computer Applications ›› 2015, Vol. 35 ›› Issue (11): 3161-3165.DOI: 10.11772/j.issn.1001-9081.2015.11.3161

• DPCS 2015 Paper • Previous Articles     Next Articles

Sparse trajectory prediction method based on iterative grid partition and entropy estimation

LIU Leijun1, ZHU Meng2, ZHANG Lei1   

  1. 1. College of Computer Science and Technology, China University of Mining and Technology, Xuzhou Jiangsu 221116, China;
    2. Department of Computer Science, Xinyang College of Agriculture and Forestry, Xinyang Henan 464006, China
  • Received:2015-05-13 Revised:2015-07-13 Published:2015-11-13

基于迭代网格划分和熵估计的稀疏轨迹预测

刘磊军1, 朱猛2, 张磊1   

  1. 1. 中国矿业大学 计算机科学与技术学院, 江苏 徐州 221116;
    2. 信阳农林学院 计算机科学系, 河南 信阳 464006
  • 通讯作者: 刘磊军(1991-),男,安徽安庆人,硕士研究生,主要研究方向:移动对象轨迹数据挖掘.
  • 作者简介:朱猛(1977-),男,河南信阳人,讲师,硕士,主要研究方向:智能信息处理; 张磊(1977-),男,江苏徐州人,副教授,博士,CCF会员,主要研究方向:移动对象轨迹数据挖掘.
  • 基金资助:
    中央高校基本科研业务费专项资金资助项目(2014XT04);教育部博士点基金资助项目(20110095110010);江苏省自然科学基金资助项目(BK20130208).

Abstract: Concerning the "data sparsity" problem of moving object's trajectory prediction, i.e., the available historical trajectories are far from enough to cover all possible query trajectories that can obtain predicted destinations, a Trajectory Prediction Algorithm suffer from Data Sparsity based on Iterate Grid Partition and Entropy Estimation (TPDS-IGP&EE) was proposed. Firstly, the moving region of trajectories was iteratively divided into a two-dimensional plane grid graph, and then the original trajectories were mapped to the grid graph so that each trajectory could be represented as a grid sequence. Secondly, an L-Z entropy estimator was used to calculate the entropy value of trajectory sequence, and a new trajectory space was generated by doing trajectory synthesis based on trajectory entropy. At last combining with the Sub-Trajectory Synthesis (SubSyn) algorithm, sparse trajectory prediction was implemented. The experimental results show when trajectory completed percentage increases towards 90%, the coverage of the Baseline algorithm decreases to almost 25%. TPDS-IGP&EE algorithm successfully coped with it as expected with only an unnoticeable drop in coverage, and could constantly answer almost 100% of query trajectories. And TPDS-IGP&EE algorithm's prediction accuracy was generally 4% higher than Baseline algorithm. At the same time, the prediction time of Baseline algorithm to 100 ms was too long, while the prediction time of TPDS-IGP&EE algorithm could be negligible (10 μs). TPDS-IGP&EE algorithm can make an effective prediction for the sparse trajectory, providing much wider predicting range, faster predicting speed and better predicting accuracy.

Key words: trajectory prediction, data sparsity, iterative grid partition, L-Z entropy estimation, sub-trajectory synthesis

摘要: 针对移动对象轨迹预测所面临的"数据稀疏"问题,即有效的历史轨迹空间不能覆盖所有可能的查询轨迹,提出了一种基于迭代网格划分和熵估计的稀疏轨迹预测算法(TPDS-IGP&EE).首先,对轨迹区域进行迭代网格划分并生成轨迹序列;然后,引入L-Z熵估计计算轨迹序列的熵值,在轨迹熵值的基础上进行轨迹综合形成新的轨迹空间;最后,结合子轨迹综合算法,进行稀疏轨迹预测.实验结果表明,当轨迹完整度达到90%以上,Baseline算法的查询覆盖率只有25%左右;而TPDS-IGP&EE算法几乎不受查询轨迹长度的影响,可以预测几乎100%的查询轨迹;并且TPDS-IGP&EE算法的预测准确率普遍高于Baseline算法4%左右;同时Baseline算法的预测时间非常长,达到100 ms,而TPDS-IGP&EE算法的预测时间(10 μs)几乎可以忽略不计.TPDS-IGP&EE算法能够有效地进行稀疏环境下的轨迹预测,具有更广的预测范围、更快的预测速度和较高的预测准确率.

关键词: 轨迹预测, 数据稀疏, 迭代网格划分, L-Z熵估计, 子轨迹综合

CLC Number: