基于位置相似性与Markov 模型的移动轨迹预测算法∗

李佳泽 高全力 郭 帅 胡发丽 李庆敏

（西安工程大学计算机科学学院 西安 710048）

1 引言

随着通信技术与互联网基础设施的快速发展，海量移动轨迹数据的获取成为了现实［1］。与此同时，无人驾驶、智能车联网等新应用的出现也催生了用户对位置信息获取与分析的需求［2］。移动用户的轨迹数据不仅包含着移动用户的行为轨迹模式，而且还记录了用户的实时动态［3］。通过分析潜在规律和相关有用信息，就能提供给用户智能化、精确化的路线推荐［4］。因此，移动轨迹预测具有很高的研究价值［5］。

现有方法主要是Markov 模型和频繁序列模式等。频繁序列模式是利用关联规则找出历史轨迹中的频繁轨迹序列［6］。该方法对历史轨迹利用率很高，但耗费的时间较长［7］。Markov模型以其对时间序列数据处理的良好能力成为了应用广泛的预测模型之一［8］。但是由于对历史轨迹信息的利用不足，所以预测的精度不高［9］。冯然等［10］提出了基于二阶马尔可夫链的预测模型，时间复杂度较高。宋路杰等［11］引入相似度对Markov 模型候选结果集合进行修正。高建等［12］提出高斯混合-时间序列模型来预测用户位置。李昇智等［13］提出了混合多步Markov 模型，将多阶Markov 模型进行融合。程媛等［14］提出了基于非参数估计方法来构建概率密度函数，提高了轨迹的匹配程度。

上述的方法大多直接利用轨迹数据进行预测，对轨迹数据中的信息考虑不充分导致准确率不高。因此，本文提出了基于位置相似性与Markov模型（Location Similarity and Markov Model，LSMM）的轨迹预测算法，该方法是将位置相似性因素与Markov模型相结合，筛选出满足位置相似的历史轨迹序列集合；然后由轨迹相似的序列建立转移概率矩阵，通过Markov 模型对用户未来时间内的位置区域进行预测。

2 数据模型定义及说明

2.1 轨迹数据预处理

移动轨迹是一组时序序列，由一系列的轨迹采样点构成，表示为{p1,p2,…,pn}(1 ≤i≤n)。由于轨迹采样点的粒度过于细密，想要挖掘出其中的轨迹模式就需要进一步的处理，所以本文借鉴文献［15］中的迭代网格划分算法。对轨迹数据的样本空间进行层次划分，形成轨迹点的初始聚类，进而提取出具有一定规模的区域集合，实现轨迹的序列化。

定义1 轨迹序列：轨迹序列是由用户的轨迹穿过的区域组成的序列。表示为

2.2 Markov模型

马尔可夫过程假设未来的状态只和当前的状态有关，而和过去的状态无关［16］。也就是说用户的下一个位置仅和当前的地理位置相关。

定义2 马尔可夫链：马尔可夫链是一组状态空间内具备马尔可夫性质的随机过程［17］。若随机过程X={Xn:n>0} ，并且存在有限个状态I={i0,i2,…,in}，若：

则X={Xn:n>0}被称为马尔可夫链。其中Xn=in表示X 处于n 时刻的状态为in，Xn-1=in-1表示X 处于n-1时刻的状态为in-1。

定义3 转移概率：pij=P(Xn=j|Xn-1=i) 。转移概率pi，j表示在当前n-1 时刻的状态为i，下一时刻状态转化为j的概率［18］。若用户经过的区域数量为n，那么转移概率矩阵P 就是个n×n 的矩阵。其中pi，j表示从区域Si转移到区域Sj的概率。其转移概率表达式为

3 基于Markov 模型和位置相似性的预测算法

为了解决Markov 模型对历史轨迹信息利用率低的问题，本文提出了基于欧式距离的位置相似性算法。该算法通过计算当前轨迹与历史轨迹之间的欧式距离之和来判断轨迹间的相似程度，并结合Markov模型完成轨迹预测。

考虑到历史信息中距离当前轨迹较近的序列对结果影响比较大，所以在进行相似度判断之前找出与用户当前访问区域相同的历史轨迹序列，然后计算历史轨迹序列与当前轨迹的欧式距离，找出符合满足阈值的历史轨迹序列。

若历史轨迹集合为SH={H1,H2,…,Ha}(1 ≤k≤a)，则满足与当前轨迹位置区域相同的历史轨迹集合为H={H1,H2,…,Hβ}(1 ≤k≤β,β≤α) 。当前轨迹P={P1,P2,…,Pn}(1 ≤i≤n) ，历史轨迹为Hk={Hk1,Hk2,…,Hkn}(k1 ≤ki≤kn)，kn 是历史序列Hk中区域的个数，数量与当前轨迹P 中的个数n 相同，保证当前轨迹序列与历史轨迹序列的长度相等。那么当前轨迹P 和历史轨迹序列Hk中位置对应的第i 个区域的欧式距离D(P1,Hk1)的计算方法如下：

其中：Ploni和Plati表示Pi的经纬度坐标，Hionki和Hlatki表示Hki的经纬度坐标。

轨迹序列P 与历史轨迹序列Hk的轨迹序列距离L(P,Hk)计算方法如下：

接着计算当前轨迹P 与历史轨迹序列集合中轨迹序列距离L(P,Hk)的平均值μ。其表达式为

对于满足L(P,Hk)≤μ的历史轨迹序列，计算他们与当前轨迹P 的相似度。轨迹相似度是用来衡量当前轨迹P 与历史轨迹序列Hk对应区域之间距离的离散程度，也就是计算轨迹之间距离的方差S(P,Hk)，其表达式为

对于S(P,Hk)小于相似度阈值δ的历史轨迹序列，将该轨迹序列加入相似度集合M 中，根据相似度集合M 建立Markov 转移概率矩阵，通过转移概率矩阵的迭代计算可得出用户下一步处于各区域的条件概率集合，其中条件概率最大的所对应的区域为预测结果。若预测区域为Pn+1，则

式中：Pnext为条件概率集合对应的区域；Pn为当前所在区域位置。

4 实验及分析

本文的实验环境是CPU 为Intel（R）Core（TM）i5-8300H的笔记本，内存为8GB，硬盘为500G的固态硬盘。实验数据采用Geolife项目数据集［20］，该数据集不仅记录了182 位用户外出活动的真实行为和轨迹，还记录了很多用户日常生活中的信息，包括家庭住址或者工作单位等地理位置信息，能够真实反映用户轨迹模式。

为了测试LSMM 算法的性能和对预测准确率的提升情况，本文将选取1 阶Markov 模型和2 阶Markov 模型与之进行对比分析。实验评价指标为预测准确率PredictionA，其定义为

其中：n为轨迹序列的长度；Ti和Hi分别为预测区域和真实区域。

1）图1 给出了本文提出的LSMM 模型与1 阶、2阶Markov 模型在不同轨迹长度下的预测准确率的比较。可以看出，1 阶模型和2 阶Markov 模型的预测准确率并没有随着轨迹序列长度的增加而大幅度提高，在序列长度较小的时候，LSMM 模型由于历史信息利用不足而与Markov 模型的准确率差距不大。而随轨迹长度增加，LSMM 模型预测的准确率不断提高，超过了1阶模型和2阶Markov模型。

图1 三种方法的预测准确率比较

2）图2 给出了两种模型在不同阶数下的预测准确率比较，对Markov 模型来说，模型阶数的增加，预测准确率呈上升趋势，但阶数过高会出现数据稀疏问题，即在历史轨迹集合中找不到与当前轨迹匹配的序列，导致预测精度不断降低。而LSMM模型则很大程度上优化了Markov 模型，通过历史信息的充分利用，降低了预测稀疏率的影响，提高了预测精度。

图2 不同阶数下两种方法的预测准确率的比较

3）图3 给出了不同规模的轨迹数据集下的三种模型的准确率的比较。随着数据规模的不断增加，三种模型的预测准确率都在增加，但是由于1阶Markov 模型的对信息利用不够充分，所以其准确率的上升空间小，而2阶Markov模型虽然利用了历史轨迹信息来提升模型的精度，但是对相似的轨迹利用率仍然不足。从图上看，LSMM 模型无论是小规模数据集还是大规模数据集，表现都优于其他两种算法。

图3 不同规模轨迹数据集下的预测准确率对比

5 结语

本文提出了一种基于位置相似性与Markov 模型的移动轨迹预测算法。该算法首先对轨迹数据利用位置相似性因素进行筛选，作为Markov 模型的数据基础，然后建立状态转移概率矩阵实现对未来区域的预测。实验表明，该方法对比Markov 模型来说，充分利用了历史轨迹信息，提高了预测的准确度和稳定性。未来工作中，还将在本文的基础上，深入研究轨迹数据的时空特性实现轨迹的序列化，进一步提高模型的准确度。