, 林树宽, 杨迪东北大学 计算机科学与工程学院, 辽宁 沈阳 110169
收稿日期：2016-06-16
基金项目：国家自然科学基金资助项目(61272177)。
作者简介：李昇智(1975-), 男, 辽宁桓仁人, 东北大学博士研究生;
乔建忠(1964-), 男, 辽宁兴城人, 东北大学教授, 博士生导师;
林树宽(1966-), 女, 吉林长春人, 东北大学教授。
摘要：随着移动设备和定位技术的广泛应用, 基于位置服务成为研究热点, 位置预测是其重要研究内容.基于GPS轨迹数据, 对位置预测方法进行研究.Markov模型可以较好地表示时序数据, 因此可较好地用于位置建模和预测.在基于Markov建模的位置预测中, 1阶Markov模型存在轨迹信息利用不充分、预测准确率低的问题; 而多阶Markov模型存在状态空间急剧膨胀的问题.针对这些问题, 提出了基于混合多步Markov模型的位置预测方法, 在将原始GPS轨迹转化为区域轨迹的基础上, 对各多步模型进行融合, 提出了基于Adaboost框架的各多步模型影响系数的生成方法, 在保证状态空间不变的情况下提高了预测准确性.真实数据集上的实验验证了所提位置预测方法的有效性.
关键词：位置预测混合多步Markov模型区域轨迹Markov模型的影响系数地图区域划分
Hybrid Multi-step Markov Location Prediction Based on GPS Trajectory Data
LI Sheng-zhi, QIAO Jian-zhong
, LIN Shu-kuan, YANG DiSchool of Computer Science & Engineering, Northeastern University, Shenyang 110169, China
Corresponding author: QIAO Jian-zhong, E-mail: qiaojianzhong@cse.neu.edu.cn
Abstract: Recently, with the wide use of mobile devices and location technology, LBS (location based service) becomes research hotspot. Location prediction is a primary research aspect of LBS. The location prediction based on GPS trajectories was researched. Markov model can represent temporal data well, so it was used in location modeling and prediction. In Markov based location prediction, 1-order Markov model cannot employ trajectory data sufficiently, so the prediction precision is low. The state space of multi-order Markov model will increase rapidly with the order number increasing. For these problems, a novel location prediction method was proposed based on hybrid multi-step Markov model, which transformed the original GPS trajectories into region trajectories. On this basis, all multi-step Markov models were merged. In the course of it, an Adaboost frame based method generating the influence coefficient of each multi-step model was presented. So, the prediction precision was improved, and the state space did not increase. The experiments on real GPS trajectory data show the effectiveness of the location prediction method proposed by the paper.
Key Words: location predictionhybrid multi-step Markov modelregion trajectorythe influence coefficient of Markov modelmap region partitioning
随着移动设备和定位技术的广泛应用, 可以越来越方便地获得位置信息.对位置数据进行数据挖掘并用于基于位置的服务[1-4]越来越受到人们的重视, 位置预测是其重要的研究内容.
在基于GPS轨迹数据的位置预测中, Markov模型可以很好地表示时序数据, 因此可较好地用于位置建模和预测.在基于Markov模型的位置预测中, 1阶Markov模型[5-6]的下一步位置只取决于当前位置, 对轨迹信息的利用不够充分, 因此, 预测准确性不高; 基于多阶Markov模型的位置预测[7-8]可以改进该问题, 可依据近期的多个位置对下一步位置进行预测, 但是, 多阶Markov模型不仅存在阶数难以确定的问题, 还会导致状态空间爆炸式增长.文献[9]针对多阶Markov模型阶数难以确定的问题, 在位置预测中, 提出了对Markov模型的阶数进行自适应调节的方法, 但并没有从根本上解决多阶Markov模型状态空间爆炸增长的问题.文献[10]在位置预测中, 对1阶和2步Markov模型进行融合, 在一定程度上解决了状态空间增长的问题, 但仅限于1阶和2步融合, 限制了其应用.
针对上述问题, 本文提出了基于混合多步Markov模型的位置预测方法, 并提出了基于Adaboost框架[11-12]的多步Markov模型融合方法, 不仅解决了多阶Markov模型状态空间增长的问题, 而且可保持较高的预测准确性.
1 问题定义车载定位系统采集的原始GPS轨迹数据是由若干轨迹点构成的序列, 表示为 <p1, p2, …, pn>, 其中每个轨迹点pi= <longitude, latitude, time>, 表示用户在时刻time位于经纬度坐标(longitude, latitude)处.为使位置预测更具物理意义, 本文的预测对象不是未来可能到达的轨迹点, 而是围绕关键交通枢纽进行地图区域划分, 并将原始由GPS轨迹点构成的轨迹数据转化为由区域构成的序列, 位置预测的对象是未来可能到达的区域.
定义1? (区域)区域是指以关键交通枢纽为中心的地理范围, 表示为多边形Sc=(〈fc〉, 〈f1, f2, …, fn〉), 其中, fc是关键交通枢纽的位置, 〈f1, f2, …, fn〉是环绕fc的多边形的n个顶点.
定义2 (区域轨迹)由用户经过的区域构成的序列称为区域轨迹, 表示为Traj=〈(S1, t1), …, (Si, ti), …, (Sm, tm)〉, 其中Si (m≥i≥1)为区域, ti为用户初次到达区域Si的时间.
定义1中的关键交通枢纽是采用文献[13]中的方法提取的具有一定规模和访问频繁程度的十字路口.围绕关键交通枢纽基于Voronoi图进行区域划分, 可生成区域, 进而可将原始GPS轨迹转化为区域轨迹.为表达方便, 区域轨迹将简单表示为Traj=S1, S2, …, Si, …, Sm.
本文的位置预测基于区域轨迹进行, 根据用户当前的区域轨迹T=S1, S2, …, Sl, 预测用户下一步到达的区域Sl+1.
k步Markov位置预测在建立k步转移概率矩阵的基础上, 计算位置Sl-k+1已知的条件下, 下一步处于各区域的条件概率p(SnextSl-k+1), 并选择其中最大者所对应的区域作为预测结果, 即
 | (1) |
定义3 ?(混合多步Markov位置预测模型)混合d(d>2)步Markov位置预测模型由d个k步(k=1, 2, …, d)Markov模型融合而成, 如式(2)所示.
 | (2) |
由式(2)可知, 建立混合d步Markov位置预测模型, 只需建立d个N×N的转移概率矩阵, 一方面避免了建立多阶Markov模型的状态空间膨胀问题, 另一方面, 在预测过程中, 充分利用了用户轨迹的多步信息, 通过合理确定各多步模型的影响系数, 可提高位置预测精度.
2 基于混合多步Markov模型的位置预测2.1 k(k=1, 2, …, d)步Markov位置预测模型的建立定义4 ?(1步转移概率矩阵)设区域总数量为N, 1步转移概率矩阵M(1)是一个N×N矩阵, 其中元素Mij(1)(1≤i≤N, 1≤j≤N)为用户在当前位置区域i的条件下经1步转移到区域j的概率pij(1).
定义4中的转移概率pij(1)可通过式(3)计算得到:
 | (3) |
定义5 ?(k步转移概率矩阵) k(k>1)步转移概率矩阵M(k)是一个N×N矩阵, 其中元素Mij(k)(1≤i≤N, 1≤j≤N)为用户在当前位置为区域i的条件下经过k步转移到区域j的概率pij(k).
建立k步Markov模型, 需要建立k步转移概率矩阵.k步转移概率矩阵可通过1步转移概率矩阵计算得出, 如定理1所示.
定理1 ?k(k>1)步转移概率矩阵M(k)可由1步转移概率矩阵M(1)计算得出, 如式(4)所示.
 | (4) |
由定理1知, k(k>1)步Markov模型的状态空间与1阶Markov模型相同, 并未发生变化.建立起k(k=1, 2, …, d, d>2)步转移概率矩阵M(k), 就可在已知当前轨迹T=S1, S2, …, Sl的情况下, 得到混合d步Markov位置预测模型(定义4)中的d个到达下个位置Snext的概率, 为建立混合d步Markov位置预测模型奠定了基础.
2.2 混合多步Markov位置预测模型的建立2.1节通过建立k(k=1, 2, …, d)步转移概率矩阵, 已经建立了d个k步Markov模型.而每个k步模型对下一个位置的预测能力是有限的, 因此, 如何对d个k步Markov模型进行融合, 即如何合理确定定义4中各k步模型的影响系数, 是保证位置预测准确性的关键.
确定混合多步Markov模型中的影响系数, 一种常规的思路是采用均等系数, 即式(4)中所有k(k=1, 2, …, d)步Markov模型对于混合d步Markov模型的影响系数是相同的, 均设定为
为此, 本文提出了基于Adaboost框架[11-12]的多步Markov模型融合方法, 用以确定混合多步Markov模型中的影响系数.
如定义4所述, 混合d(d>2)步Markov位置预测模型由d个k步(k=1, 2, …, d)Markov模型融合而成, 对于每个k步Markov模型, 其影响系数ak根据其预测误差确定, 预测误差越大, 影响系数越小.对于具有n个轨迹数据的训练样本, k步Markov模型的预测误差ek计算如式(5)所示.
 | (5) |
 | (6) |
 |
 | (7) |
 | (8) |
基于Adaboost框架建立混合多步Markov位置预测模型的具体过程如算法1所示.
算法1 ?混合d(d>2)步Markov位置预测模型的建立
输入:大小为n的轨迹样本集Traj[]
输出:混合d步Markov位置预测模型
1) 分别建立k(k=1, 2, …, d)步转移概率矩阵;
2) 将样本集中每个样本的权重初始化为1/n;
3) for k=1, …, d do
4) ??利用k步转移概率矩阵计算k步预测值;
5) ??按照式(5)计算k步模型的预测误差ek;
6) ?? if ek≥0.5 then ak=0;
7) ?? else按照式(7)计算k步模型的影响系数ak;
8) ?? for每个轨迹样本i∈Traj[]do
9) ???? if (i被k步模型预测错误) then
10) ??????按式(8)对样本i的权重进行修正;
11)将{a1, a2, …ad}归一化;
12)按照定义3生成混合d步Markov模型;
13) return
3 实验分析本文实验环境为Intel(R) Core(TM2) Duo CPU E8500 @3.16 GHz, 内存4 GB, 硬盘500 GB.实验程序用Java编写, 在Windows XP系统下运行.实验数据为北京市10 357辆出租车的真实GPS数据.
实验将本文提出的混合多步Markov位置预测模型与1阶和2阶Markov模型的预测效果进行比较.在此过程中, 用以衡量预测效果的指标—预测准确率，定义如式(9)所示.
 | (9) |
图 1给出了1阶Markov, 2阶Markov和本文提出的混合多步Markov位置预测模型准确性的比较.从图 1可以看出, 1阶模型和2阶模型的预测准确率随轨迹长度的增加变化并不明显.当预测轨迹长度较小时, 本文的位置预测方法准确率低于1阶模型和2阶模型, 随着轨迹长度的增加, 本文方法的预测准确率不断提高, 超过了1阶模型和2阶模型.这是因为, 随着轨迹长度的增加, 轨迹信息更加充分, 更能体现出混合多步Markov位置预测模型的优势.
图 1(Fig. 1)
 | 图 1 三种方法的预测准确率比较Fig.1 Precision comparison of the three methods |
图 2比较了混合多步Markov模型中采用均等系数和基于Adaboost框架的影响系数生成方法对预测准确率的影响.可以看出, 本文提出的基于Adaboost框架的影响系数生成方法非常有效, 无论k值怎样变化, 位置预测的准确率均高于“均等系数”方法, 因为采用均等系数限制了混合多步Markov模型中各个多步模型对位置准确性的影响.
图 2(Fig. 2)
 | 图 2 两种影响系数确定方法的比较Fig.2 Comparison of the two methods generating the influence coefficients |
4 结论本文面向GPS轨迹数据, 对基于Markov模型的位置预测方法进行研究.在对原始GPS轨迹数据进行处理, 将其转换为区域轨迹的基础上, 针对1阶Markov位置建模和预测中存在的轨迹信息利用不充分、预测准确率低的问题, 以及多阶Markov位置预测模型存在的状态空间急剧膨胀的问题, 提出了混合多步Markov位置建模与预测方法, 解决了状态空间膨胀的问题; 同时, 在建模过程中, 提出了基于Adaboost框架的多步Markov模型的影响系数生成方法, 提高了预测准确性.
参考文献
| [1] | 周傲英, 杨彬, 金澈清, 等. 基于位置的服务:架构与进展[J].计算机学报, 2011, 34(7): 1155–1171. ( Zhou Ao-ying, Yang Bin, Jin Che-qing, et al. Location-based services:architecture and progress[J].Chinese Journal of Computers, 2011, 34(7): 1155–1171.) |
| [2] | Li Y, Yiu M L. Route-saver:leveraging route APIs for accurate and efficient query processing at location-based services[J].IEEE Transactions on Knowledge and Data Engineering, 2015, 27(1): 235–249.DOI:10.1109/TKDE.2014.2324597 |
| [3] | Jung S, Mo H. A spatial indexing scheme for location based service queries in a single wireless broadcast channel[J].Journal of Information Science and Engineering, 2014, 30(6): 1945–1963. |
| [4] | Shin H, Chon Y, Kim Y, et al. A participatory service platform for indoor location-based services[J].IEEE Pervasive Computing, 2015, 14(1): 62–69.DOI:10.1109/MPRV.2015.1 |
| [5] | Chen M, Liu Y, Yu X H.NLPMM:a next location predictor with Markov modeling[C]// Advances in Knowledge Discovery and Data Mining:18th Pacific-Asia Conference.Tainan, 2014:186-197. |
| [6] | Gidofalvi G, Dong F.When and where next:individual mobility prediction[C]// Proceedings of the First ACM SIGSPATIAL International Workshop on Mobile Geographic Information Systems.Redondo Beach, 2012:57-64. |
| [7] | Krumm J. A Markov model for driver turn prediction[J].Proceedings of Society of Automotive Engineers World Congress, 2008, 22(1): 1–25. |
| [8] | Ashbrook D, Starner T. Using GPS to learn significant locations and predict movement across multiple users[J].Personal and Ubiquitous Computing, 2003, 7(5): 275–286.DOI:10.1007/s00779-003-0240-0 |
| [9] | 吕明琪, 陈岭, 陈根才. 基于自适应多阶Markov模型的位置预测[J].计算机研究与发展, 2010, 47(10): 1764–1770. ( Lyu Ming-qi, Chen Ling, Chen Gen-cai. Position prediction based on adaptive multi-order Markov model[J].Journal of Computer Research and Development, 2010, 47(10): 1764–1770.) |
| [10] | 余雪岗, 刘衍珩, 魏达, 等. 用于移动路径预测的混合Markov模型[J].通信学报, 2006, 27(12): 61–69. ( Yu Xue-gang, Liu Yan-heng, Wei Da, et al. Hybrid Markov model for mobile path prediction[J].Journal on Communications, 2006, 27(12): 61–69.DOI:10.3321/j.issn:1000-436X.2006.12.012) |
| [11] | Freund Y, Schapire R E. A decision-theoretic generalization of on-line learning and an application to boosting[J].Journal of Computer and System Sciences, 1997, 55(1): 119–139.DOI:10.1006/jcss.1997.1504 |
| [12] | Schapire R E.A brief introduction to boosting[C]// Proceedings of the 16th International Joint Conference on Artificial Intelligence.Stockholm, 1999:1401-1406. |
| [13] | Chen Z B, Shen H T, Zhou X F.Discovering popular routes from trajectories[C]// Proceedings of the 27th ICDE International Conference on Data Engineering.Hannover, 2011:900-911. |
