一种基于马尔可夫模型的稀疏轨迹终点预测算法

摘要

随着移动设备的普及与定位技术的成熟,涌现出了各种基于地理位置的应用软件不断涌现.为了使这类应用软件给用户提供精准的基于地理位置的服务,实时、准确、可靠地预测移动对象的不确定性轨迹显得尤为重要.目前大多数传统的轨迹终点预测方法都是通过计算轨迹之间的相似度来预测给定轨迹的终点,这种算法的弊端是没有充分考虑轨迹数据时间序列之间的前后联系,导致预测结果偏差较大.理论证明,马尔可夫模型对处理时间序列数据具有较好的效果.因此,针对轨迹终点预测的问题,提出了一种基于马尔可夫模型的预测算法.同时,针对样本运动空间提出一种新的划分网格策略——K-d tree网格划分.实验结果表明,相比于传统方法,运用马尔可夫模型预测轨迹终点的算法的精度有明显提高,预测时间会大大缩短.%With the popularity of mobile devices and the maturity of location technologies,a variety of location-based applications emerge.In order to make such applications provide users with accurate location-based services,timely,accurately,reliably forecast uncertainty track of moving objects is particularly important.Currently,most traditional methods predict the destination of a given trajectory by calculating the similarity between two trajectories,and this algorithm does not fully consider the drawbacks of backward and forward linkages between trajectory time series,resulting in a larger prediction error.Theory demonstrates that the Markov model to deal with time series data have very good effect.Therefore,we proposed a sparse trajectory destination prediction algorithm based on Markov model.Meanwhile we investigated a new partitioning strategies for the sample motion space——grid partitioning based on K-d tree.The experimental results show that compared with traditional methods,using Markov model to predict the destination of the trajectory will significantly improve the accuracy of the algorithm,and the predicted time will be shortened.