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

来源：计算机应用杂志2015年第11期北京时间：

作者：刘磊军, 朱猛, 张磊

单位：1. 中国矿业大学 计算机科学与技术学院, 江苏 徐州 221116;2. 信阳农林学院 计算机科学系, 河南 信阳 464006

摘要：针对移动对象轨迹预测所面临的"数据稀疏"问题,即有效的历史轨迹空间不能覆盖所有可能的查询轨迹,提出了一种基于迭代网格划分和熵估计的稀疏轨迹预测算法(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熵估计,子轨迹综合

基金资助：中央高校基本科研业务费专项资金资助项目(2014XT04);教育部博士点基金资助项目(20110095110010);江苏省自然科学基金资助项目(BK20130208).