Abstract: To solve the problem that Markov model has poor prediction accuracy and sparse matching in location prediction, a mobile user location prediction method based on Adaboost-Markov model was proposed. Firstly, the original trajectory data was preprocessed by a trajectory division method based on angle offset and distance offset to extract feature points, and density clustering algorithm was used to cluster the feature points into interest regions of the user, then the original trajectory data was discretized into a trajectory sequence composed of interest regions. Secondly, according to the matching degree of prefix trajectory sequence and historical trajectory pattern tree, the model order k was adaptively determined. Finally, Adaboost algorithm was used to assign the corresponding weight coefficients according to the importance degree of 1 to k order Markov models to form a multi-order fusion Markov model, realizing the prediction of future interest regions of the mobile user. The experimental results on a large-scale real user trajectory dataset show that the average prediction accuracy of Adaboost-Markov model is improved by 20.83%, 11.3%, and 5.38% respectively compared with the first-order Markov model, the second-order Markov model, and the multi-order fusion Markov model with average weight coefficient, and the proposed model has good universality and multi-step prediction performance.

Key words: location prediction, region of interest, Adaboost algorithm, multi-order fusion Markov model, weight coefficient, adaptation

摘要： 针对Markov模型在位置预测中存在预测精度不高及匹配稀疏等问题，提出了一种基于Adaboost-Markov模型的移动用户位置预测方法。首先，通过基于转角偏移度与距离偏移量的轨迹划分方法对原始轨迹数据进行预处理，提取出特征点，并采用密度聚类算法将特征点聚类为用户的各个兴趣区域，把原始轨迹数据离散化为由兴趣区域组成的轨迹序列；然后，根据前缀轨迹序列与历史轨迹序列模式树的匹配程度来自适应地确定模型阶数k；最后，采用Adaboost算法根据1~k阶Markov模型的重要程度为其赋予相应的权重系数，组成多阶融合Markov模型，从而实现对移动用户未来兴趣区域的预测。在大规模真实用户轨迹数据集上的实验结果表明，与1阶Markov模型、2阶Markov模型、权重系数平均的多阶融合Markov模型相比，Adaboost-Markov模型的平均预测准确率分别提高了20.83%、11.3%以及5.38%，且具有良好的普适性与多步预测性能。

关键词: 位置预测, 兴趣区域, Adaboost算法, 多阶融合Markov模型, 权重系数, 自适应