基于后缀自动机的轨迹模式挖掘方法

Mining method for trajectory pattern based on suffix automaton

基于交通路网研究移动对象轨迹预测,将序列分析方法和马尔可夫统计模型结合,提出了一种基于后缀自动机的变阶马尔可夫模型挖掘方法。该方法根据移动对象的历史轨迹数据进行学习训练,计算轨迹序列上下文的概率特征,建立序列的后缀自动机模型,结合当前实际轨迹数据,动态自适应预测将来的位置信息。实验结果表明:相比固定阶马尔可夫模型,随着阶数的增加(L≥2),固定阶马尔可夫模型预测的精度逐步降低,而该方法能动态自适应,精度保持在81.3%左右,取得较好的预测效果;同时,该方法只需线性的时间和空间开销,大大降低了存储空间和时间,能实现大规模数据的在线学习。

This paper researched the prediction for moving object＇ s trajectory based on the traffic network, and propOsed a variable order Markov model mining method based on suffix automaton by combining the sequence analysis method and Markov model. It trained the model and calculated the probabilistic characteristics of sequence context from the historical trajectory da- ta of moving objects, and constructed the suffix automaton model based path sequence, predicted the future trajectory position information dynamically and adaptively according to actual trajectory data. Experimental results show that this method can dy- namically adapt with the increase of order （L ≥ 2 ） and its accuracy remains at about 81.3 % while the prediction accuracy de- creases gradually using fixed order markov model. It acquires good prediction effect. Meanwhile, it needs only linear time and space cost , greatly reduces the storage space and time, and can realize large-scale data learning online.