后缀自动机在轨迹模式挖掘与预测中的应用

“基于后缀自动机的轨迹模式挖掘方法，结合序列分析与马尔可夫模型，提出一种变阶马尔可夫模型，用于移动对象的轨迹预测。该方法利用历史轨迹数据训练，构建后缀自动机模型，动态预测位置信息，具有高精度和低时间空间开销。” 本文是关于移动对象轨迹预测的研究，采用了基于后缀自动机的变阶马尔可夫模型。在智能交通系统中，对移动对象（如车辆、行人）的轨迹预测至关重要，这有助于优化交通管理、提高交通安全和效率。传统的预测方法，如定阶马尔可夫模型，通常假设未来状态只依赖于有限的过去状态，但这种假设在处理复杂轨迹模式时可能不足。 变阶马尔可夫模型（Variable-order Markov Model, VMM）是对此的一种改进，它允许模型阶数随上下文变化，从而更准确地捕捉轨迹模式的动态性。后缀自动机（Suffix Automaton）在此中起到了关键作用，它是一种高效的字符串搜索和模式匹配工具，可以有效地处理和存储大量的历史轨迹数据。 该研究中，首先通过学习和分析移动对象的历史轨迹数据，计算出轨迹序列的上下文概率特征。然后，这些特征被用来构建后缀自动机模型，这个模型能够捕获序列中的模式并进行预测。当结合当前的实际轨迹数据时，模型能够动态自适应地预测未来的移动路径，而不是像固定阶马尔可夫模型那样，随着阶数的增加预测精度下降。 实验结果证明，所提出的变阶马尔可夫模型结合后缀自动机的方法，在轨迹预测的准确性上优于固定阶模型，平均精度保持在约81.3%，表现出良好的预测性能。此外，该方法的时间和空间复杂度仅为线性，这意味着它可以有效地处理大规模数据，并支持在线学习，这对于实时的交通管理系统来说非常有利。 该研究得到了国家自然科学基金、福建省科技项目等多个科研基金的支持，由不同高校的研究人员合作完成，涵盖了数据挖掘、智能交通和海量数据处理等多领域知识。这种方法的创新性和实用性对于推动交通领域的智能决策和数据分析有着重要的意义。