摘要
针对移动对象轨迹预测所面临的"数据稀疏"问题,即有效的历史轨迹空间不能覆盖所有可能的查询轨迹,提出了一种基于迭代网格划分和熵估计的稀疏轨迹预测算法(TPDS-IGP&EE)。首先,对轨迹区域进行迭代网格划分并生成轨迹序列;然后,引入L-Z熵估计计算轨迹序列的熵值,在轨迹熵值的基础上进行轨迹综合形成新的轨迹空间;最后,结合子轨迹综合算法,进行稀疏轨迹预测。实验结果表明,当轨迹完整度达到90%以上,Baseline算法的查询覆盖率只有25%左右;而TPDS-IGP&EE算法几乎不受查询轨迹长度的影响,可以预测几乎100%的查询轨迹;并且TPDS-IGP&EE算法的预测准确率普遍高于Baseline算法4%左右;同时Baseline算法的预测时间非常长,达到100ms,而TPDS-IGP&EE算法的预测时间(10μs)几乎可以忽略不计。TPDS-IGP&EE算法能够有效地进行稀疏环境下的轨迹预测,具有更广的预测范围、更快的预测速度和较高的预测准确率。
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.
出处
《计算机应用》
CSCD
北大核心
2015年第11期3161-3165,共5页
journal of Computer Applications
基金
中央高校基本科研业务费专项资金资助项目(2014XT04)
教育部博士点基金资助项目(20110095110010)
江苏省自然科学基金资助项目(BK20130208)
关键词
轨迹预测
数据稀疏
迭代网格划分
L-Z熵估计
子轨迹综合
trajectory prediction
data sparsity
iterative grid partition
L-Z entropy estimation
sub-trajectory synthesis
