杨震 王红军

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

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

中图分类号： TP311

文献标志码：A

文章编号：1001-9081（2019）03-0675-06

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; adaptivelyadaptation

0 引言

随着智能移动终端普及率的提高以及移动空间定位技术的迅猛发展，基于位置的服务（Location Based Service， LBS）得到了广泛应用[1]。目前基于位置的服务主要包含定位查询、路径规划和位置共享等功能，这些功能多集中于为用户提供当前位置的相关服务。为了使服务更具前瞻性，近年来大量国内外学者把目光投向了移动用户的位置预测上[2-3]。移动用户位置预测具有很高的研究价值与广阔的应用前景，其中最直观的应用包括：1）个性化推荐与提醒。根据预测出的用户下一步地点，可以针对用户进行个性化的推荐与提醒，例如系统预测出某个用户的下一步地点为某个酒吧，可以向这位用户推荐这个酒吧的促销活动，以及推荐常去此酒吧的新朋友。2）可疑目标追踪。移动用户位置预测可用于对可疑用户进行追踪定位，例如在网上发表极端言论的用户，通过预测目标用户的未来目的地，可以有效防范危害公共安全的恶性事件发生[4-5]。3）智能化交通。通过车载GPS（Global Positioning System）設备采集的大量轨迹数据可用于预测交通拥堵情况，从而便于司机规划行驶路线以及提高出租车的调度效率[6]。

但是，移动用户位置预测也是一项非常困难且富有挑战性的工作。首先，由于城市内高楼建筑的遮挡以及用户随意开关设备定位功能，容易造成部分重要数据的缺失以及训练数据的不足;其次，移动用户的活动具有不确定性，在不同的时间周期内，同一个用户表现出的移动模式可能大相径庭;再者，用户的轨迹数据同时具有离散型和海量性，研究人员无法直接将原始数据用于位置预测，需要通过轨迹处理算法提取出重要数据，并过滤掉冗余数据以提高预测效率。

现有的研究方法主要通过建立用户的历史移动模式以及轨迹匹配进行位置预测，常用的方法有马尔可夫（Markov）模型[7-12]、隐马尔可夫（Hidden Markov）模型[13]、高斯混合模型[14]以及卡尔曼滤波[15]等。

Markov模型以其良好的时序轨迹数据表示能力而成为应用最为广泛的位置预测模型之一。文献[7]中余雪岗等[7]结合最大期望算法提出了1阶1步与2步相结合的Markov模型，在一定程度上解决了低阶Markov 预测精度差的问题。文献[8]中吕明琪等[8]针对高阶Markov模型中难以确定最优阶数的问题，提出了自适应变阶Markov模型，但其实质与历史模式匹配相同，根据最长匹配序列来确定阶数，仍然存在匹配稀疏率高等问题。文献[9]中Chen等[9]考虑了轨迹中的时间因素，提出了一种时间箱与Markov模型结合的位置预测算法。文献[10]中宋路杰等[10]通过引入轨迹相似度对Markov模型的预测结果进行修正，提高了预测的准确率与稳定性。文献[11]中乔少杰等[11]提出了基于前缀投影数据库的Markov模型，通过设置支持度阈值，将符合条件的前缀轨迹序列放入投影数据库。该方法一定程度上解决了高阶Markov模型中匹配稀疏率高的问题，但是建立投影数据库的时间代价较大。文献[12]中Killijian[12]提出了n-MMC（n-Mobility Markov Chain）模型来预测用户位置，并验证了在n=2时预测效果最好。文献[16]中Trasarti等[16]提出了MyWay方法对移动用户进行位置预测，该方法采用插值修正轨迹，接着通过设定启发式阈值来寻找与待预测轨迹相似的历史轨迹;但是该方法没有对原始轨迹进行预处理，预测出的结果粒度过细，导致计算量太大。文献[17]中Monreale等[17]提出了WhereNext方法进行位置预测，该方法首先通过网格划分将原始轨迹数据离散化，随后采用T模式树挖掘用户的频繁移动模式，从而完成位置预测;但是，采用网格划分方法进行数据预处理必须以用户的各个兴趣区域规模相当为前提，该方法可伸缩性较差，难以适用于大规模轨迹数据中。文献[18]中Yuan等[18]提出了一种移动用户多粒度周期性模型，用于发现个体行为规律，预测用户未来位置;但是，该模型采用有监督的学习方法识别个体行为，计算开销较大。

针对现有方法存在的问题，本文首先采用轨迹划分与密度聚类相结合的方法，将原始轨迹数据离散化为移动用户的各个兴趣区域，接着利用Adaboost算法为多阶融合Markov模型合理确定权重系数，在充分利用历史轨迹序列的基础上，提高了预测准确率，保证了模型的普适性。

1.1 轨迹划分与兴趣点提取

为了实现上述目的，本文提出了一种新的轨迹划分方法，用于提取出轨迹中用户行为变化较大的采样点，并将它们作为特征点，每个特征点作为前一段子轨迹的终点与下一段子轨迹的起点，从而将一条完整轨迹划分为若干条连续子轨迹。

低阶Markov模型具有时间代价小、计算速度快的优点，但是其预测精度不高，如1阶Markov模型，它仅仅利用用户当前所在的兴趣区域来预测下一个兴趣区域，没有充分利用前缀轨迹序列中所包含的信息。而高阶Markov模型通常拥有更高的预测精度，但是随之而来的是空间状态膨胀与匹配稀疏问题，并且有研究[8]指出，随着阶数提高带来的预测性能增长有一个极限。若Markov模型阶数设定过高，如3阶及以上Markov模型，它同时利用用户当前所在的兴趣区域与前缀轨迹序列中的多个兴趣区域来预测下一个兴趣区域，在与用户的历史轨迹序列进行匹配时，可能会导致匹配失败或是仅仅匹配出极少数的历史轨迹序列，即匹配稀疏，这样反而会导致模型的预测性能降低。如图2所示，以某位用户的历史轨迹序列模式树为例，假设采用三阶Markov模型，前缀轨迹序列为C2 → C4 → C5，并基于此移动模式树预测用户的下一兴趣区域。但是，在此模式树中并没有以C2 → C4 → C5为前缀序列的历史轨迹，三阶Markov模型无法作出预测。针对此问题，文献[8]提出了的自适应多阶Markov模型能够在前缀序列与移动历史模式树匹配失败时自动降阶，直到匹配成功。然而，当Markov模型的阶数较高时，即使在用户的历史轨迹序列模式树中找到以C2 → C4 → C5为前缀的序列，也极有可能存在匹配数量过少、稀疏率高等问题，从而导致预测效果不佳。

2 Adaboost-Markov建模

1阶Markov模型仅仅利用了用户当前所在的兴趣区域，对历史轨迹序列的利用率不高;而高阶Markov模型由于存在匹配困难、稀疏率高的问题，同样存在无法充分利用历史轨迹序列的问题。因此，将低阶模型与高阶模型相结合是一种可行的方法。那么，合理地确定各阶模型对最终预测结果的影响系数，则是保证预测性能良好的重要前提。从宏观上看，高阶Markov模型通常具有更高的预测精度，在组合模型中应该具有更大的“话语权”。为了确定各阶模型的具体影响系数，本文提出了基于Adaboost-Markov模型的移动用户位置预测方法。Adaboost算法作为一种代表性的提升方法，可以通过改变训练数据的概率分布以及弱分类器的权重系数，组合多个弱分类器，生成一个强分类器[17]。本文自适应确定模型阶数k，将1阶至k阶Markov模型作为k个弱预測器，通过Adaboost算法改变用户轨迹数据的概率分布与各阶Markov模型的权重系数，最终生成一个多阶融合Markov模型用于预测用户位置。

阶数k由用户前缀轨迹序列与历史轨迹序列的最大匹配阶长所决定。以图3为例，用户原始轨迹数据经过预处理后建立了历史轨迹序列库，参与匹配的前缀轨迹序列长度通常有两种方法确定：一是前缀轨迹序列与历史轨迹序列的最大匹配长度，但是当前缀轨迹序列过长时，采用这种方法会导致时间代价过高。二是人为指定参与匹配的前缀轨迹序列长度，由用户确定参与匹配的前缀轨迹序列元素个数并输入相应长度的待预测前缀轨迹序列，若能在历史轨迹序列库中找到与前缀轨迹序列相同的序列，则匹配成功，并将此时前缀轨迹序列的元素个数设为模型阶数k;否则，此次匹配失败，则自动降阶，去掉前缀轨迹序列中距离当前最远的一个元素，并继续在历史轨迹序列库中寻求匹配，重复以上步骤，直至匹配成功。

3 实验分析

本文仿真实验环境为Windows10 64 位操作系统，Intel Core i7-6700HQ 2.60GHz CPU，8GB内存，硬盘1TB。本实验中所采用的轨迹数据集来自于微软亚洲研究院的Geolife项目[18]，该数据集包含182名用户从2007年4月至2012年8月的轨迹采样点，共有17621条轨迹，总距离为1292951km，总持续时间为50176h;并且，91.5%的轨迹以每1～5s或每5～10m记录一次，能够真实反映出用户的生活习惯及行为模式。

为验证模型的有效性，本文对4种模型进行对比实验：1阶Markov模型、2阶Markov模型、权重系数平均的多阶融合Markov模型以及本文提出的Adaboost-Markov模型。其中，权重系数平均的多阶融合Markov模型与Adaboost-Markov模型的区别在于，前者为1～k阶Markov模型赋予相同的权重系数，而后者采用Adaboost算法根据各阶模型的预测误差调整对应的权重系数。从Geolife轨迹数据集中随机抽取90%用于训练上述模型，剩下10%的轨迹数据用于检测预测性能。

为了方便量化表示算法的性能优势，本文采用如下性能评价指标。

定义9 预测准确率（Prediction Accuracy）。已知待预测轨迹序列T与由某个模型预测出的轨迹序列P，预测准确率定义为：

首先，为验证使用Adaboost算法进行权重系数分配的合理性，比较了不同前缀轨迹序列元素个数下Adaboost-Markov模型、权重系数均等的多阶融合Markov模型与普通Markov模型的预测准确率。

如图4所示，横轴表示前缀轨迹序列元素的个数，纵轴表示预测准确率。对于普通Markov模型来说，前缀元素个数即等同于模型阶数，而Adaboost-Markov模型与权重系数平均的多阶融合Markov模型采用了自适应确定模型阶数k的匹配方法。因此，随着前缀元素个数的增多，普通Markov模型的预测准确率首先呈现出提升的趋势，在2阶时达到最大值，随后由于阶数的增多，匹配稀疏率逐渐增高，从而导致预测准确率逐渐降低。Adaboost-Markov模型则有效克服了这一不足，其预测准确率首先随着前缀元素数量的增加而提高，在前缀元素数量为3时基本趋近于最大值，随后预测准确率一直稳定在最大值附近。因此，在接下来的仿真实验中，Adaboost-Markov模型与权重系数平均的多阶融合Markov模型均将前缀轨迹序列长度设为3。并且，从图4中可以看出，通过Adaboost算法确定的模型权重系数是合理有效的，无论给定的待预测序列中前缀元素的数量怎样变化，Adaboost-Markov模型的预测准确率均高于权重系数平均的多阶融合Markov模型。

接着，利用上述4种模型进行单步预测，即预测用户的下一个兴趣区域，图5和图6分别展示了4种模型在小规模轨迹数据集及大规模轨迹数据集上的预测效果，横轴代表轨迹序列长度，即用于预测的历史轨迹序列库中的元素个数，纵轴表示预测准确率。

从图5、6中观察可以发现，本文提出的Adaboost-Markov模型对用户下一步兴趣区域预测的准确率明显高于1阶Markov模型、2阶Markov模型以及权重系数平均的多阶融合Markov模型：在小规模轨迹数据集的实验中，与1阶Markov模型、2阶Markov模型以及权重系数平均的多阶融合Markov模型相比，Adaboost-Markov模型的平均预测准确率分别提高了39.73%、18.3%以及9.12%;在大规模轨迹数据集的实验中，与1阶Markov模型、2阶Markov模型以及权重系数平均的多阶融合Markov模型相比，Adaboost-Markov模型的平均预测准确率分别提高了20.83%、11.3%以及5.38%。随着轨迹长度的增加，各模型预测准确率的增长也趋于稳定，因此在大规模轨迹数据集的实验中，各模型的准确率曲线相对平缓。1阶Markov模型和2阶Markov模型由于对前缀轨迹序列的利用不够充分，所以其预测准确率的上升空间不大;而权重系数平均的多阶融合Markov模型与Adaboost-Markov模型的预测准确率均明显高于1、2阶Markov模型，这是因为权重系数平均的多阶融合Markov模型与Adaboost-Markov模型的前缀轨迹序列长度被设为3，當历史轨迹序列库满足匹配条件时，上述模型同时利用了1～3阶Markov模型的前缀轨迹序列，充分利用了轨迹序列中所包含的移动模式信息，在历史轨迹序列库不符合匹配条件时，亦可自适应降低前缀轨迹序列长度，相比于定阶Markov模型具有更好的灵活性。权重系数平均的多阶融合Markov模型虽然融合了各阶Markov模型且较为充分利用了前缀轨迹序列，但是其没有考虑到各阶Markov模型的重要性差异问题，因此结合了Adaboost算法为各阶模型合理分配权重系数的Adaboost-Markov模型具有更高的预测准确率。

为了更为全面地比较4种模型的预测性能，随机选用了Geolife项目中8名用户的轨迹数据集。从图7中可以看出，虽然四种模型在不同数据集上的预测准确率存在一定范围的波动，但是整体上的预测性能排名与之前的实验结果并无二致，与1阶Markov模型、2阶Markov模型以及权重系数平均的多阶融合Markov模型相比，Adaboost-Markov模型的平均预测准确率分别提高了23.14%、15.44%以及7.06%。可见本文提出的Adaboost-Markov模型具有良好的普适性，在不同数据集上的预测准确率均好于另外3种模型。

在位置预测中，多步预测能力也是反映模型好坏的关键之一。多步预测即预测出用户在n步之后所处的兴趣区域。实验结果如图8所示，从图8中可以看出，随着预测步长的增加，各模型预测准确率的下降幅度均较为明显，但是Adaboost-Markov模型在各步长的预测准确率均优于另外三种模型。原因在于，在进行n步预测对比实验时，1、2阶Markov模型采用n步转移概率预测之后的兴趣区域，相比于Adaboost-Markov模型的自适应可变长序列的预测方式，1、2阶Markov模型仅仅考虑了固定长度的轨迹序列，对于数据的适应性不佳。

4 结语

本文针对Markov模型进行位置预测时存在预测准确率低与匹配稀疏等不足，采用轨迹划分与密度聚类相结合的方法作为轨迹数据预处理手段，提出了Adaboost算法与多阶融合Markov模型相结合的预测方法，充分利用了历史轨迹序列，提高了预测准确率。真实用户轨迹数据集上的实验证明了本文方法在一定程度上解决了低阶Markov模型预测准确率低以及高阶Markov模型匹配稀疏率高等问题，具有较高的预测准确率以及良好的普适性。未来工作中，还将对上述模型进一步优化，更深入地研究轨迹数据的时空特性与群体特性，将天气、时间（工作日与休息日）以及用户相关的社交数据等因素考虑在内，以期进一步提高模型的预测准确率。

参考文献 （References）

[1] 郭迟，刘经南，方媛，等.位置大数据的价值提取与协同挖掘方法[J].软件学报，2014，25（4）：713-730.（GUO C， LIU J N， FANG Y， et al. Value extraction and collaborative mining methods for location big data [J]. Journal of Software， 2014， 25（4）：713-730.）

[2] WIDHALM P， NITSCHE P， BRANDIE N. Transport mode detection with realistic smartphone sensor data [C]// Proceedings of the 21st International Conference on Pattern Recognition. Piscataway， NJ： IEEE， 2012： 573-576.

[3] SHIH D H， SHIH M H， YEN D C， et al. Personal mobility pattern mining and anomaly detection in the GPS era [J]. American Cartographer， 2016， 43（1）： 55-67.

[4] GUNDUZ S， YAVANOGLU U， SAGIROGLU S. Predicting next location of twitter users for surveillance [C]// Proceedings of the 12th International Conference on Machine Learning and Applications. Washington， DC： IEEE Computer Society， 2013： 267-273.

[5] BOGOMOLOV A， LEPRI B， STAIANO J， et al. Once upon a crime： towards crime prediction from demographics and mobile data [C]// ICMI '14： Proceedings of the 16th International Conference on Multimodal Interaction. New York： ACM， 2014： 427-434.

[6] QIAO S， HAN N， ZHU W， et al. TraPlan： an effective three-in-one trajectory-prediction model in transportation networks [J]. IEEE Transactions on Intelligent Transportation Systems， 2015， 16（3）： 1188-1198.

[7] 余雪岗，刘衍珩，魏达，等.用于移动路径预测的混合Markov模型[J].通信学报，2006，27（12）：61-69. （YU X G， LIU Y H， WEI D， et al. Hybrid Markov model for mobile path prediction [J]. Journal on Communications， 2006， 27（12）： 61-69.）

[8] 呂明琪，陈岭，陈根才.基于自适应多阶Markov模型的位置预测[J].计算机研究与发展，2010，47（10）：1764-1770.（LYU M Q， CHEN L， CHEN G C. Position prediction based on adaptive multi-order Markov model [J]. Journal of Computer Research and Development， 2010， 47（10）： 1764-1770.）

[9] CHEN M， YU X， LIU Y. Mining moving patterns for predicting next location [J]. Information Systems， 2015， 54： 156-168.

[10] 宋路杰，孟凡荣，袁冠.基于Markov模型与轨迹相似度的移动对象位置预测算法[J].计算机应用，2016，36（1）：39-43.（SONG L J， MENG F R， YUAN G. Moving object location prediction algorithm based on Markov model and trajectory similarity [J]. Journal of Computer Applications， 2016， 36（1）： 39-43.）

[11] 乔少杰，韩楠，李天瑞，等.基于前缀投影技术的大规模轨迹预测模型[J].软件学报，2017，28（11）：3043-3057.（QIAO S J， HAN N， LI T R， et al. Large-scale trajectory prediction model based on prefix projection technique [J]. Journal of Software， 2017， 28（11）： 3043-3057.）

[12] KILLIJIAN M O. Next place prediction using mobility Markov chains [C]// MPM '12： Proceedings of the 1st Workshop on Measurement， Privacy， and Mobility. New York： ACM， 2012： Article No. 3.

[13] QIAO S J， SHEN D， WANG X， et al. A self-adaptive parameter selection trajectory prediction approach via hidden Markov models [J]. IEEE Transactions on Intelligent Transportation Systems， 2015， 16（1）： 284-296.

[14] 喬少杰，金琨，韩楠，等.一种基于高斯混合模型的轨迹预测算法[J].软件学报，2015，26（5）：1048-1063.（QIAO S J， JIN K， HAN N， et al. Trajectory prediction algorithm based on Gaussian mixture model [J]. Journal of Software， 2015，26（5）：1048-1063.）

[15] PATHIRANA P N， SAVKIN A V， JHA S. Robust extended Kalman filter applied to location tracking and trajectory prediction for PCS networks [C]// Proceedings of the 2004 IEEE International Conference on Control Applications. Piscataway， NJ： IEEE， 2004， 1： 63-68.

[16] TRASARTI R， GUIDOTTI R， MONREALE A， et al. MyWay： location prediction via mobility profiling [J]. Information Systems， 2017， 64： 350-367.

[17] MONREALE A， PINELLI F， TRASARTI R， et al. WhereNext： a location predictor on trajectory pattern mining [C]// Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2009： 637-646.

[18] YUAN G， ZHAO J， XIA S， et al. Multi-granularity periodic activity discovery for moving objects [J]. International Journal of Geographical Information Systems， 2016， 31（3）： 435-462.

[19] 杨震，王红军，周宇.一种截断距离和聚类中心自适应的聚类算法[J].数据分析与知识发现，2018，2（3）：39-48.（YANG Z， WANG H J， ZHOU Y. A clustering algorithm by adaptive cut-off distances and cluster centers [J]. Data Analysis and Knowledge Discovery， 2018， 2（3）： 39-48.）

[20] 李航.统计学习方法[M].北京：清华大学出版社， 2012：137-139.（LI H. Statistical Learning Method [M]. Beijing： Tsinghua University Press， 2012： 137-139.）

[21] ZHENG Y， CHEN Y， XIE X， et al. GeoLife2.0： alocation-based social networking service [C]// Proceedings of the 2009 10th International Conference on Mobile Data Management： Systems， Services and Middleware. Washington， DC： IEEE Computer Society， 2009： 357-358.