基于概率后缀树的移动对象轨迹预测  

Prediction of moving object trajectory based on probabilistic suffix tree

作　　者：王兴[1,2] 蒋新华[1,3] 林劼[2] 熊金波[2] 

机构地区：[1]中南大学信息科学与工程学院,长沙410075 [2]福建师范大学软件学院,福州350108 [3]福建工程学院下一代互联网应用技术研究中心,福州350108

出　　处：《计算机应用》2013年第11期3119-3122,3133,共5页journal of Computer Applications

基　　金：福建省重大专项(2011HZ0002-1);国家自然科学基金资助项目(61101139);福建省科技计划重点项目(2011H0002);福建省交通科技计划项目(201122)

摘　　要：在移动对象轨迹预测中,针对低阶马尔可夫模型预测准确率不高、高阶模型状态空间膨胀的问题,提出一种基于概率后缀树(PST)的动态自适应变长马尔可夫模型预测方法。首先依时间先后将移动对象的轨迹路径序列化;然后根据移动对象的历史轨迹数据进行学习训练,计算序列上下文的概率特征,建立路径序列的概率后缀树模型,结合当前实际轨迹数据,动态自适应预测将来的位置信息。实验结果表明,该模型在二阶时取得最高的预测精度,随着阶数的增加,预测精度保持在82%左右,能取得较好的预测效果;同时空间复杂度呈指数级减少,大大节省了存储空间。该方法充分利用历史轨迹数据和当前轨迹信息预测未来轨迹,能够提供更加灵活、高效的基于位置服务。In the prediction of moving object trajectory, concerning the low accuracy rate of low order Markov model and the expansion of state space in high order model, a dynamic adaptive Probabilistic Suffix Tree （PST） prediction method based on variable length Markov model was proposed. Firstly, moving object＇s trajectory path was serialized according to the time; then the probability characteristic of sequence context was trained anti calculated from the historical trajectory data of moving objects, the probabilistic suffix tree model based path sequence was constructed, combined with the actual trajectory data, thus the future trajectory information could be predicted dynamically and adaptively. The experimental results show that the highest prediction accuracy was obtained in second order model, with the order of the model increasing, the prediction accuracy was maintained at about 82% and better prediction results were achieved. In the meantime, space complexity was decreased exponentially and storage space was reduced greatly. The proposed method made full use of historical data and current trajectory information to predict the future trajectory, and provided a more flexible and efficient location-based

关 键 词：变长马尔可夫模型 概率后缀树 历史轨迹 轨迹预测 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]