随着全球定位技术和移动通信技术的快速发展,移动对象产生的轨迹数据规模呈爆炸式增长,对大量的轨迹数据进行存储、处理后进一步挖掘应用的需求越来越多。移动对象的轨迹预测已经成为当前轨迹数据挖掘的研究热点,通过移动对象轨迹预测,对于缓解交通压力、基于位置的应用和服务、用户隐私保护等方面有着重要的意义。本文围绕稀疏轨迹预测方法进行研究,主要工作如下:(1)基于迭代网格划分和熵估计的稀疏轨迹预测方法目前移动对象的轨迹预测方法主要是基于历史轨迹空间的轨迹预测,但是这类方法面临“数据稀疏”问题,即有效的历史轨迹空间不能覆盖所有可能的查询轨迹。为了解决上述问题,本文提出一种基于迭代网格划分和熵估计的稀疏轨迹预测方法(TPDS-SIGP&EE)。首先对轨迹所在区域进行迭代网格划分,并将离散的GPS轨迹点映射到网格图中生成轨迹序列;其次,采用L-Z熵估计计算轨迹序列的熵值,在熵值排序的基础上选择熵值较低的轨迹进行划分形成子轨迹,重新组合子轨迹形成新的轨迹空间,以解决轨迹数据的稀疏问题,同时,使得新的轨迹空间更加可信,且将其规模控制在一定范围内;最后在新的轨迹空间下使用基于马尔可夫模型和贝叶斯推理的子轨迹综合方法进行稀疏轨迹预测。采用微软亚洲研究院T-Drive数据对算法进行测试,实验结果表明,TPDS-SIGP&EE能够有效地进行稀疏环境下的轨迹预测,并且与同类算法相比,该算法的轨迹空间大幅缩小,预测速度快,而预测准确性却有所提高。(2)基于多种熵估计的稀疏轨迹预测方法考虑时间因素对轨迹预测的影响,并引入多种熵估计评价轨迹整体、不同时间段、不同位置上和位置转移的规律性来加强预测准确性,提出了一种基于多种熵估计的稀疏轨迹预测算法(STP-ME)。首先,对轨迹区域进行迭代网格划分并生成带时间标签的轨迹序列;然后使用L-Z熵评估计算完整轨迹序列的L-Z熵值,并引入转移熵作为轨迹划分的依据,在轨迹L-Z熵值和转移熵的基础上进行轨迹划分得到新的轨迹空间;最后结合度量位置受欢迎程度的位置熵和时间段内活跃程度的时间熵,使用带时间维度的二阶马尔可夫模型(2-TMM)进行稀疏轨迹预测。实验表明,在2-TMM的基础上使用多种熵估计可以提高轨迹预测的准确性;当轨迹完整度达到90%以上,Baseline算法的查询覆盖率只有25%左右;而STP-ME算法几乎不受查询轨迹长度的影响,可以预测几乎100%的查询轨迹;并且STP-ME算法的预测准确率最高,分别高于Baseline算法、SubSyn算法和2-MM算法8%、4%和3%左右;同时Baseline算法的预测时间非常长,达到100ms,而STP-ME算法的预测时间(10ms)几乎可以忽略不计。STP-ME算法能够有效地进行稀疏环境下的轨迹预测,具有更广的预测范围,更快的预测速度和较高的预测准确率。