2017, Vol. 38
随着移动设备和定位技术的广泛应用, 可以越来越方便地获得位置信息.对位置数据进行数据挖掘并用于基于位置的服务[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) |
k步转移概率矩阵的定义及建立过程将在2.1节介绍, 其规模相当于1阶Markov模型, 但是, k步Markov位置预测只用到了预测区域Sl+1前面第k个区域Sl-k+1的位置信息, 轨迹信息利用不充分.为了充分利用轨迹位置信息, 提高预测准确率, 本文提出了基于混合多步Markov模型的位置预测方法.
定义3 (混合多步Markov位置预测模型)混合d(d>2)步Markov位置预测模型由d个k步(k=1, 2, …, d)Markov模型融合而成, 如式(2)所示.
|
(2) |
其中：p(Snext|Sl-k+1)是由k步(k=1, 2, …, d)Markov模型得出的转移概率; ak为每个k步模型在混合多步Markov模型中的影响系数.
由式(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) |
其中：nij是用户的历史轨迹中从区域i经1步转移到区域j的轨迹数目；ni是用户的历史轨迹中从区域i出发向所有区域转移的计数总和.二者均可以从用户的历史轨迹数据中统计得出.
定义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) |
其中:wik是与k步Markov模型对应的样本i的权重, 初始时设置为1/n; Ek是k步Markov模型的加权预测误差, 其计算如式(6)所示.
|
(6) |
其中,
|
基于上述预测误差ek, 可计算k步Markov模型的影响系数ak:若ek≥1/2, 则在混合多步Markov模型中舍弃该k步Markov模型, 即令ak=0, 也就是说, 在混合多步Markov模型中, 对于每个k步Markov模型, 其预测误差ek < 1/2;对于ek < 1/2的k步模型, 其影响系数的计算如式(7)所示.预测误差ek越大, 影响系数ak越小, 反之亦然.
|
(7) |
除了按照每个k步Markov模型的预测误差计算其影响系数, Adaboost框架在混合多步Markov模型的建立过程中还体现为:与k步Markov模型相对应的每个轨迹样本的权重wik也根据其预测准确度进行调整.在计算(k+1)步Markov模型的影响系数之前, 增加被错误预测样本的权重wik+1以调整训练集的样本分布, 使得被错误预测的样本在下一次训练中受到重视, 从而不断提升预测能力.对于每个预测错误的轨迹样本i, 按照式(8)增大其权重wik+1, 即
|
(8) |
在式(8)中, 对于每个预测错误的轨迹样本i, 由ek < 1/2知, wik+1>wik.
基于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) |
其中:N和n分别为区域的数量和预测轨迹的数量; pij为第i条轨迹当前位置的下一步区域为j的概率; 
图 1给出了1阶Markov, 2阶Markov和本文提出的混合多步Markov位置预测模型准确性的比较.从图 1可以看出, 1阶模型和2阶模型的预测准确率随轨迹长度的增加变化并不明显.当预测轨迹长度较小时, 本文的位置预测方法准确率低于1阶模型和2阶模型, 随着轨迹长度的增加, 本文方法的预测准确率不断提高, 超过了1阶模型和2阶模型.这是因为, 随着轨迹长度的增加, 轨迹信息更加充分, 更能体现出混合多步Markov位置预测模型的优势.
|
图 1 三种方法的预测准确率比较 Fig.1 Precision comparison of the three methods |
图 2比较了混合多步Markov模型中采用均等系数和基于Adaboost框架的影响系数生成方法对预测准确率的影响.可以看出, 本文提出的基于Adaboost框架的影响系数生成方法非常有效, 无论k值怎样变化, 位置预测的准确率均高于“均等系数”方法, 因为采用均等系数限制了混合多步Markov模型中各个多步模型对位置准确性的影响.
|
图 2 两种影响系数确定方法的比较 Fig.2 Comparison of the two methods generating the influence coefficients |
本文面向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. |