多模式移动对象不确定性轨迹预测模型

乔少杰 韩楠 丁治明 金澈清 孙未未 舒红平

随着无线通信和定位技术的高速发展,人们对持续移动物体所处的空间位置的跟踪能力不断加强,推动相关应用领域的研究不断深入,如智能交通控制、智能导航和军事指挥等.此类应用系统往往基于移动对象数据库构建,其中存储了大量关于移动对象时空位置及运动状态的信息.这些数据通常以轨迹的形式存储,隐藏着关于移动对象大量的行为特征及运动规律.然而,移动对象所处的运动环境往往是动态变化的,不能单纯依赖静态交通网络环境预测其运动行为,需要综合考虑移动速度和方向的动态变化对对象运动行为的影响.如何综合考虑主客观因素,高效准确地查询和预测移动对象不确定性位置成为当前移动数据管理领域的研究热点[1].尤其值得注意的是,在包含较为复杂的轨迹模式场景下，典型运动模式不止一个,一条轨迹可能隶属于多个轨迹模式,称之为多模式.不同类型移动对象运动行为各有差异,相同类型的移动对象由于主客观因素影响,运动模式也不尽相同,因此挖掘多模式移动对象运动行为特征更具实际意义.

多模式移动对象位置预测是一项非常困难和富有挑战意义的课题.1)由于移动对象运动模式复杂多变,且通过定位系统获得的数据流信息量大,具有不确定性,需要更加稳定和具有可伸缩性的挖掘方法进行处理;2)位置预测需要尽可能快地对可能运动轨迹进行评价,延时或滞后将产生无意义的预测结果;3)基于模拟技术的预测方法依赖于大量输入参数,这些参数的设置极大地影响模型的准确性,对于不确定性的轨迹数据进行预测,需要考虑诸多客观因素和领域专家知识;4)如果算法设计不合理,随着移动对象数目的增加,模型的计算代价可能呈指数级增长.下面以移动对象轨迹预测为主要背景,以智能交通系统为例说明问题意义和概貌.

智能交通旨在建立一种在较大范围内,全方位发挥作用的实时、准确和高效的综合运输和管理系统.系统将采集到的各种道路交通及服务信息处理后,传输到运输系统的各种用户(例如驾驶员、居民、警察),出行者可实时选择交通方式和交通路线,交通管理部门可进行自动和合理的交通疏导、控制及事故处理.决策者可知每天哪一时段,具体在哪一区域是机动车出行的高峰期,应该采用何种手段可以使路网上的交通流量处于最佳状态,改善交通拥挤和阻塞状况,最大限度地提高交通的通行能力,提高整个公路运输系统的机动性、安全性和运输效率.可以形式化描述为在一组约束下,确定一组阈值ε和σ,使得

上式(∗)意义为求取当各种车辆总和∑Ti＜ε,且保证不同时段j内交通事故发生率Pj＜σ时,各种车辆的数量Num(Ti),并且在测试数据集上支持度超过Supp,置信度超过Conf.其中,ε表示交通运输能力,σ表示事故发生率门限值.

本文结构如下:第1节对国内外在移动对象不确定性轨迹预测领域的成果进行综述;第2节针对单一运动模式轨迹,挖掘轨迹热点区域并利用频繁模式树准确高效预测移动对象连续位置信息;第3节介绍一个面向复杂运动场景的基于高斯混合回归的多模式轨迹预测模型;第4节验证本文提出的两种针对不同运动模式的轨迹预测算法的性能;第5章总结全文工作并对未来工作进行展望.

1 国内外研究现状

针对移动对象的连续位置预测主要包括过去轨迹的重现及当前和未来轨迹的预测,主要研究集中于轨迹频繁模式挖掘,通过挖掘频繁模式找出典型运动路径.Hu等[2]将连续轨迹视为离散状态点之间转变的过渡,对轨迹离散状态分析的不足之处在于对大量时空数据进行离散化处理代价极高,而且需要计算离散数据点之间的相关性.Parker等[3]设计了移动对象运动目标概率函数可以满足的若干axiom,这些axiom用于精确度量预测轨迹与真实轨迹之间的差异.Song等[4]在Science上发表了预测人类移动性的研究成果,通过测量个体轨迹的信息熵,定量地给出了人类动态运动轨迹具有93%的可预测性,并证明了人类有规律的运动路线与距离无关.Centola[5]在Science上的工作是在原始GPS数据中使用层次型马尔科夫模型抽取重要地点,进而检测用户的行为模式.针对已有轨迹预测算法仅能预测短期内运动路径的不足,Jeung等[6]提出了一种基于路网的移动预测模型,用于准确计算移动对象在交叉路口运动变换模式和在不同路段上的速度信息,但该方法局限于路网中应用.Zhou等[7]利用动态选取的参考轨迹构建预测模型,模型建立之前目标轨迹是已知的,具备先验知识,可以基于少量的历史轨迹构建精准的预测模型.

随着越来越多不同种类移动对象轨迹数据被收集,近期多模式轨迹预测的工作得到学者的广泛关注,Pan等[8]提出了基于多变元正态分布的线性预测器,应用这一方法预测会产生延迟,不能应用于交通流的实时监控环境中.Qiao等[9]借助隐马尔科夫模型(Hidden Markov model,HMM),设计实现了一种可以自适应调整轨迹预测参数的动态预测算法,根据不同类型轨迹数据预测最佳路线,但是这一模型没有考虑大数据环境下算法的运行时间性能问题.此外,乔少杰等[10]提出了基于隐马尔科夫模型的自适应轨迹预测模型,该算法通过对大数据环境下移动对象海量轨迹利用基于密度的聚类方法进行位置密度分区和高效分段处理,根据输入轨迹自动选取参数组合,避免隐马尔科夫模型中隐状态不连续、状态停留等问题.Ding等[11]近期提出了一种路网匹配的基于轨迹数据库的交通流分析方法,用于预测移动对象位置信息.Xu等[12]提出了用于避免大图上过度二次计算的有效策略,更好地支持动态路网中路径动态规划.为了支持轨迹大数据中个性化多模式运动路径预测,Dai等[13]利用高斯混合模型,描述行驶偏好矢量中随机变量的概率分布，构建带权重的轨迹图，权重反映对象候选路径的可能性，并结合最短路径算法推荐个性化运动轨迹.Tripathy等[14]根据不同对象的历史轨迹特征,构建线性函数,预测移动对象将来可能运动位置,所提方法可以保证较小的预测偏差.Xu等[15]提出一种通用位置表达模型,定义不同对象可能的位置,实现复杂场景不同运动模式下轨迹预测.黄玉龙等[16]提出了一种改进的高斯近似滤波方法,用于再入飞行器的目标跟踪.陈成等[17]提出了一种基于四阶贝塞尔曲线的无人车可行轨迹规划算法,用于在实际道路中行驶的车辆.考虑到高纬度和不确定性对轨迹预测准确性的影响,Monfort等[18]提出了一种逆最优控制方法,用于计算人类活动轨迹出现的概率.

通过对上述移动对象轨迹预测工作进行分析,可以得到如下结论:1)如果针对海量轨迹数据挖掘移动对象频繁轨迹模式,已有算法需要多次扫描数据库,代价很高,需要设计新型频繁模式挖掘算法,提高挖掘的效率和准确性.2)现有轨迹预测算法对具有单一简单模式的移动对象的位置跟踪预测效果较好,对于复杂场景下多模式轨迹预测的研究内容相对较少.

2 基于频繁轨迹模式树的轨迹预测算法

移动对象的运动模式通常比较单一,例如在城市交通道路上匀速运动.针对单一运动模式,本节提出一种基于频繁模式挖掘的轨迹预测算法[19].

2.1 轨迹热点区域挖掘算法

在预测前改进DBSCAN算法对海量GPS轨迹点进行聚类挖掘轨迹热点区域,可以将轨迹点与由信号不稳定等原因产生的噪点区分.轨迹热点区域挖掘算法RoIDiscovery采用密度聚类思想,通过遍历每个轨迹点的邻域生成簇.如果轨迹点p的邻域内包含多于θ个轨迹点,则创建一个新的簇,将p作为该簇的核心对象.然后,递归地遍历核心对象直接密度可达的对象,这个过程中包含簇的合并操作.当没有新的点可以被添加到任何簇时,过程结束.基于密度的轨迹热点区域挖掘算法如算法1所示[19].

算法1.基于密度的轨迹聚类算法

输入.轨迹数据集Tr,聚簇半径ε,最少轨迹点数θ.

输出.聚类后簇集合R={R1,R2,···,Rn}.

1.n=0;

2.foreachp∈Trdo

3.markpas visited;

4.N=getNeighbours(p,ε);

5.ifsize(N)＜ θthen

6.markpas noise;

7.else

8.create a new clusterRk;

9.ExpandCluster(p,N,Rk,ε,θ).

算法1的基本思想为:遍历Tr中所有轨迹点,初始化簇个数(第1行);将轨迹点p标记为已访问(第3行);第4∼9行利用getNeighbours(·)函数计算轨迹点p与其他轨迹点的距离,将距离小于ε的轨迹点存入集合N中,如果size(N)＜θ,则标记p为噪声点,否则以p为核心建立新簇,并调用ExpandCluster(·)函数递归访问N中轨迹点.ExpandCluster(·)基本思想是对N邻域内的所有点进行半径检查,如果大于θ,扩展N的数目,将新节点加入扩展后的簇.当没有新节点可以被添加到任何簇,该过程结束.

2.2 频繁轨迹模式挖掘算法

本节介绍基于频繁轨迹模式树的轨迹预测算法FTP-mining[19],首先给出频繁轨迹模式树定义.

定义 1(频繁轨迹模式树—FTP-tree)[19].FTP-tree由一个标记为空的根节点及一系列由原子路段组成的前缀子树构成,且包含一个头节点表Header table.FTP-tree的数据结构与FP-tree类似,前缀子树上的每一个节点具有三个属性:id,count和pointer,其中id表示原子路段的标识,count表示从根节点到达某一节点的路径被访问次数,pointer表示指向FTP-tree中具有相同id的下一个节点指针.Header table中每一行记录包含两个属性:节点id和头指针(指向FTP-tree中具有某id的第一个节点).基于频繁轨迹模式树的轨迹预测算法FTP-mining如算法2所示[19].

算法2.FTP-mining( FFF, α)

输入.具有根节点t的FTP-treeF,与t对应的轨迹热点路段L,空集合α.

输出.频繁轨迹模式集合R={f1,f2,···,fn}.

1.构建一个空的频繁轨迹模式集合R;

2.if有一条从t出发的路径Qthen

3.构建一条模式q=Q∪α;

4.support_count=min{counti};//counti表示Q中第i个节点被访问的次数;

5.Q.add(q);

6.else

7.for each候选项li∈Ldo

8.构建模式p=li∪α;

9.suppor_tcount=min{counti};

10.构建与p对应的conditional pattern base和conditional FTP-treeF0;

11.ifF0nullthen

12.FTP-mining(F0,p);

13.ifR不变化then

14.R.add(p);

15.输出R中频繁轨迹模式.

算法2的基本思想为:首先生成长度为1的频繁序列集;然后根据长度为1的频繁序列集生成长度为2的频繁序列集;依此类推,产生所有频繁序列模式,与FP-tree[20]类似.FTP-mining与FTP-tree的不同之处在于:1)FTP-tree中的项集表示被移动对象访问的路段,从根节点到叶节点的一条完整的路径表示一条频繁轨迹模式;2)每一条前缀树带有时间戳信息,时间戳表示访问一条路段的时间间隔.基于FTP-tree的轨迹预测算法包含FTP-tree构建和FTP-mining两个步骤,FTP-tree的构建过程与FP-tree的构建相同,不再赘述.FTP-mining算法挖掘频繁轨迹模式的过程不同于FP-tree,其主要目标是找到大于给定门限值的最长的频繁路径,算法2第4∼12行计算生成的最长频繁序列模式没有考虑路段模式组合的情况,第10行中conditional pattern base是具有相同前缀模式的频繁路段项子集合.

在上述两项技术基础上,给出基于FTP-tree的移动对象轨迹预测算法PathPrediction,如算法3所示[19].

算法3.基于FTP-tree的移动对象轨迹预测算法PathPrediction

输入.移动对象数据库D,路网中路段集合S.

输出.预测轨迹集合Tr.

1.R=RoIDiscovery(D,S);

2.foreach RoIrinRdo

3.Tr=FTPTreeGeneration(r);

4.FTP-mining(Tr,α);

5.输出最可能运动轨迹集合Tr.

算法3首先利用RoIDiscovery算法从移动对象数据库D找出热点区域集合R(第1行).然后,对R中的每个轨迹热点区域构建FTP-tree(第2行和第3行),并利用FTP-mining计算出频繁轨迹模式(第4行).最后,输出所有频繁轨迹模式(第5行).

3 基于GPR的复杂多模式轨迹预测模型

本节主要解决复杂场景中包含多种运动模式且很难用单一一种运动模式刻画的复杂运动模式预测问题,首先介绍利用高斯过程回归模型实现单一运动模式预测,进而引出基于高斯混合回归的复杂运动模式预测模型.

3.1 高斯过程回归

一种典型运动模式路径可以由一个高斯过程表示,利用高斯过程回归(Gaussian process regression,GPR)[21]进行预测.下面介绍针对简单运动模式的高斯过程回归模型的理论基础.

对于输入训练数据集其中xi∈Rd为d维输入矢量,yi∈R 为相应输出.对于给定输入数据集合X,可构成一个随机变量集合{f(x1),f(x2),···,f(xN)},且具有联合高斯分布,则该高斯过程(Gaussian process,GP)的全部统计数字特征可由均值函数m(x)和协方差函数k(x,x′) 确定,即

其中,m(x)=E[f(x)],k(x,x′)=E[(f(x)−m(x))×(f(x′)−m(x′))],本文所用核函数为标准指数协方差函数,表示为

其中,θ0为指数权重参数,θ1表示长度规模参数,δij是狄拉克函数,当i=j时,函数δij=1,否则为0.

应用高斯过程回归的目的是在训练集输入数据X和输出数据Y之间建立映射关系f(·):Rd→R,继而预测出与新测试输入数据x∗对应最可能的观测输出值f(x∗),求取回归估计函数过程如下.

求解过程:由于输入输出的观测和测量数据经常伴随噪声数据干扰,因此将噪声数据考虑进观测目标值y,建立高斯过程回归一般模型:y=f(x)+ε.其中,ε为独立的高斯白噪声,符合高斯分布,均值为0,方差为σ2,可记为ε∼N(0,σ2).由于噪声ε独立于f(x),所以当f(x)服从高斯分布时,有限观测值联合分布的集合y同样可形成一个高斯过程,即

其中,协方差函数以矩阵方式表达,即

式中,I表示N×N的单位矩阵,C(X,X)表示N×N协方差矩阵,K(X,X)表示N×N的核函数矩阵,元素Kij=k(xi,xj),K(X,X)表示如下:

K(X∗,X)=[k(x∗,x1),k(x∗,x2),...,k(x∗,xn)]表示K(X,X)中某一行,且K(X∗,X∗)=k(x∗,x∗).

由于整个高斯过程模型利用多元高斯分布表达数据,根据贝叶斯原理可知,GP在给定训练集数据Dtrain集合上建立先验函数,然后在测试数据集下转变为后验分布,则训练数据输入数据X的输出向量y和测试数据X∗的输出向量y∗之间的联合高斯密度分布为

为了求取输出向量y∗,需要借助联合高斯密度回归定理.

由此可知,当(y,y∗)T服从联合高斯分布时,条件概率p(y∗|y)是高斯分布,所以得到y∗关于y回归方程及相应方差如下:根据定理1,可以得到关于预测输出数据的条件概率P(y∗|y)和GP回归方程,即

其中,K∗=K(X∗,X),K∗∗=K(X∗,X∗),于是y∗关于y的最佳回归估计方程,即y∗的预测值为

而关于y∗的预测不确定性区间用方差表示为

3.2 基于高斯混合回归的轨迹预测模型

在轨迹包含较为复杂运动模式场景下,需要采用多个高斯过程,利用高斯混合回归模型(Gaussian mixture regression,GMR)[22]进行轨迹预测分析.

3.2.1 训练模型

在具有多种轨迹模式的场景中,一条轨迹可能隶属于多个轨迹模式,准确地刻画一条轨迹需要采用混合模型.例如,对于轨迹S=〈(x1,y1),(x2,y2),···,(xn,yn)〉,本文将其转化为X和Y方向上的n维矢量X=(x1,x2,···,xn)T和Y=(y1,y2,···,yn)T,n表示轨迹的观测点个数,X和Y方向上矢量在所有M个轨迹模式中出现的总概率是由不同运动模式的高斯概率混合而成,表示为

其中,M表示混合轨迹模式的状态数量,wi表示第i个轨迹模式的权重,且和Σx,i分别表示第i个轨迹模式状在X方向上的均值和协方差,参数λ={wi,µi,Σi},i=1,2,···,M.GP(Xn|µx,i,Σx,i)表示轨迹矢量Xn相对第i个运动模式状态的高斯概率函数,定义如下:

其中,µ和Σ表示轨迹高斯过程的典型运动模式在X方向上的均值和协方差矩阵,µ=[E(x1),E(x2),···,E(xd)]T,Σ =(Cij)d×d,Cij=Cov(xi,xj).

于是,对于轨迹训练集S={X,Y},整个轨迹训练集高斯混合模型似然函数为

模型中如何计算复杂运动模式中的参数λ是一个关键步骤,本文通过使轨迹训练模型(即式(14)和式(15))概率达到最大,从已知的训练轨迹矢量集S={X,Y}中学习训练出最佳参数λ,利用概率最大的方式,使用最大似然法估计(Expectationmaximization,EM),选出构成运动模型的概率密度最大的那一组参数,为轨迹回归分析预测时所用.

EM 算法在迭代中改善模型参数估计,在每次迭代中不断地增加模型估计参数λ与观测训练轨迹X方向矢量xi(由若干轨迹点构成)的匹配概率,这里讨论X轴方向,Y轴方向情况类似,即每次迭代使式(14)满足p(X|λk+1)＞p(X|λk),其中k表示迭代的次数.通过不断地学习,获得最佳匹配训练轨迹矢量集X={x1,x2,···,xn}.迭代训练的目的即为找到一组λ,使得p(X|λ)最大,即

由于篇幅限制,求解使p(X|λ)达到最大的参数λ值的过程参见文献[23].

3.2.2 预测模型

在上一节的基础上,本节给出基于GMR的轨迹预测模型.已知训练数据集为S=(x,y),其中输入数据为x,输出数据为y.测试数据集S∗=(x∗,y∗), 输入测试数据为x∗, 预测输出y∗, 那么[y,y∗]T的联合概率密度函数遵从如下的GMR模型.

其中并且满足每个高斯成分GP(·|µi,Σi) 可由式(9)计算出,联合概率密度函数表示为

其中,除此之外,边缘密度py和条件密度py∗|y可由式(17)和式(18)求得,y的边缘密度函数为

条件密度函数为

其中混合权重

因此,y∗关于y的回归函数(y∗预测值)为

对应的方差为

式(22)称作高斯混合回归模型,基于GMR的轨迹预测算法思路即利用式(20)对预测数据概率密度函数建模,应用EM算法估计相应参数,依据正态分布数据的条件分布(参见定理1)得到m个高斯分量回归函数,利用式(22)将总体回归函数加权混合实现对整体数据的回归预测分析.

4 实验及算法性能分析

4.1 基于FTP-tree的轨迹预测算法性能分析

为了验证基于FTP-tree的轨迹预测算法预测准确性和时间性能,对Naive算法(没有采用轨迹热点区域挖掘RoIDiscovery算法,仅应用FTP-mining算法),PutMode算法[24](基于时间连续贝叶斯网络的轨迹预测算法)和PathPrediction算法(集成轨迹热点区域挖掘和FTP-mining算法)进行对比实验.实验数据集使用New York,Kansas和Chengdu真实矢量地图.New York,Kansas和Chengdu地图分别由435186×563287,348693×437998和23514×25672个像素构成,合成的轨迹数据通过修改Brinkhoff轨迹生成器[25]生成.为了进一步证明算法的真实有效性,实验使用微软亚洲研究院GeoLife数据集[26],由182个用户5年间1129天GPS轨迹数据组成,包含17621条轨迹.

4.1.1 轨迹预测准确性对比

实验利用预测命中率评价算法的有效性[19].

定义2(预测命中).已知一条轨迹序列S={s1,s2,···,sk},根据S得到的预测轨迹序列为Tp={p1,p2,···,pk},dist(p,q) 表示时空点p和q之间的欧氏距离,θ是一个给定的距离门限值,dist(si,pi)≤θ表明一次轨迹预测命中,预测命中定义为

定义3(预测命中率).已知一条轨迹序列S和预测得到的轨迹序列Tp,预测命中率定义为

其中,|Tp|表示组成Tp轨迹点的数量.

图1和图2给出了不同算法随轨迹数量增加的轨迹预测准确率.其中,横轴表示轨迹数量,纵轴表示预测准确率.实验结果表明,融合轨迹热点区域挖掘和基于FTP-tree的频繁轨迹模式挖掘方法PathPrediction的预测精度在Chengdu数据集上平均高出PutMode算法8.0个百分点,高出Naive预测算法29.2个百分点,在GeoLife真实数据集上平均高出PutMode算法5.5个百分点,高出Naive预测算法28.9个百分点.原因在于PathPrediction算法对经过聚类后的轨迹热点区域进行频繁轨迹模式的挖掘,轨迹热点区域是由经过噪声处理后的轨迹点组成的,因此预测的准确性更高.此外,构建的频繁轨迹模式树FTP-tree综合考虑了真实路网中的轨迹运动规则,因此预测的结果与移动对象真实运动情况更加吻合,而PutMode算法融合了轨迹聚类和时间连续贝叶斯网络,相比于没有进行轨迹热点挖掘的Naive算法准确性要高.

图1 Chengdu数据集下不同算法预测准确率比较Fig.1 Prediction accuracy comparison of different algorithms under Chengdu datasets

图2 GeoLife数据集下不同算法预测准确率比较Fig.2 Prediction accuracy comparison of different algorithms under GeoLife datasets

4.1.2 轨迹预测时间性能对比

为了验证本文提出的基于FTP-tree的轨迹预测算法的时间性能,本节实验在不同的电子地图(New York,Kansas和Chengdu)上生成轨迹数据集,观察PathPrediction算法的预测时间,结果如图3所示.可以发现,不同电子地图上,随着生成轨迹数量的增加,PathPrediction算法的运行时间均近似呈线性增长,证明了算法的可伸缩性.

图3 PathPrediction算法在不同数据集下预测时间比较Fig.3 Prediction time of PathPrediction algorithm under different datasets

为了进一步验证PathPrediction的时间性能,随着移动对象数量增加,观察算法1∼3的运行时间,实验数据集为Chengdu地图生成的轨迹数据集和GeoLife真实轨迹数据集,结果如图4和图5所示.

图4 Chengdu数据集下不同算法预测时间比较Fig.4 Prediction time comparison of different algorithms under Chengdu datasets

通过图4和图5可以发现,PathPrediction算法在所有情况下预测时间均小于PutMode算法,略高于Naive算法.原因在于Naive算法没有应用轨迹热点区域挖掘算法,因此预测时间要小于PathPrediction算法.而PutMode算法需要训练时间连续贝叶斯网络并构建转换强度矩阵,该过程非常耗时,时间远远高于本文提出的频繁轨迹模式挖掘算法FTP-mining.此外,可以发现Naive和PathPrediction算法运行时间接近,说明本文提出的轨迹热点区域挖掘算法时间随着轨迹数量的增加不会发生巨大变化.

图5 GeoLife数据集下不同算法预测时间比较Fig.5 Prediction time comparison of different algorithms under GeoLife datasets

4.2 基于高斯混合回归的轨迹预测算法性能分析

为了验证本文提出的面向多模式移动对象轨迹预测算法的性能,设计实现了基于高斯混合回归的轨迹预测算法GMRTP,基于卡尔曼滤波的预测算法Kalman,基于隐马尔科夫模型(Hidden Markov model,HMM)的轨迹预测算法HMTP[9].其中,Kalman filter[27]是一种应用普遍的回归预测方法,与本文提出的预测算法的可比性较高.HMTP算法基于HMM模型提取隐状态和观察状态,预测效果较好,通过与其比较,可以充分证明本文算法的性能优势.

本节比较上述三种算法的准确性和时间性能.实验数据来源于MIT停车场行驶车辆数据1http://www.ee.cuhk.edu.hk/xgwang/MITtrajsingle.html,收集了40453条真实轨迹.

4.2.1 高斯过程分量的选取

GMRTP算法中高斯过程分量个数M的选取很重要,如果选择的过程分量过少,算法不能充分地对数据建模,进而对测试轨迹进行准确的预测;选择的过程分量太多,则会增加轨迹预测时间代价.本节实验观察在不同高斯过程分量个数下,不同轨迹输入长度(即已知轨迹点个数)对预测误差的影响.

定义4(预测误差).轨迹预测是将测试轨迹数据集输入预测模型得到预测输出轨迹,其中输入测试轨迹为部分轨迹点的集合,采用均方根误差(Root mean squared error,RMSE)计算预测轨迹点与实际轨迹点的误差.

其中,(xi,yi)表示真实位置,表示预测位置,k为预测轨迹点的数量.

实验中每条观测轨迹由60个轨迹点构成,已知输入轨迹点长度分别取10,30,50,对应预测的未来轨迹点数目分别是50,30,10,实验结果如图6所示.

图6 不同高斯过程分量下轨迹预测误差比较Fig.6 Prediction error comparison with distinct Gaussian regression components

从图6可以看出:1)在不同高斯过程分量下,当观测的历史轨迹输入点个数越多时(例如observable length=50),算法预测误差越低.因为预测模型有了更多的历史轨迹数据点信息,包含更多的运动模式,预测误差降低.2)GP混合分量个数从1增加到5时,其预测误差变化较大.当高斯过程分量达到5时,预测误差收敛.值得注意的是,不同轨迹数据集其运动模式个数不同,因此需要通过实验探寻最佳的高斯过程分量个数.本节后面实验内容中GMRTP中高斯过程分量个数均设置为5.

4.2.2 预测准确性分析

本节观察三种预测算法在训练轨迹数量为39000条、不同测试集数据规模为100∼1000条轨迹下的预测准确性.用预测命中率评价算法的准确性,用预测误差(RMSE)评价算法的预测精度,实验结果取每种测试集下所有轨迹预测结果的平均值,如图7和图8所示.

从图7可以看出,相比于其他两种算法,随着测试轨迹数量的增加,GMRTP预测误差最小,一直保持在40m上下波动,相对较长的真实轨迹,预测精度较高且比较稳定.分析实验结果发现,HMTP预测的平均误差比GMRTP平均高出5.5m,GMRTP相比Kalman算法,预测误差平均减少18.6m.原因在于HMTP和Kalman轨迹预测算法对于处理较为简单运动模式的轨迹预测精度较好,而实验中采用的数据集中轨迹模式较为复杂且种类繁多,因此预测误差最大.而基于GMR的模型通用性较好,可以针对不同的多模式轨迹利用高斯过程回归预测.

图7 不同算法预测误差比较Fig.7 Prediction bias comparison of different algorithms

图8 不同算法预测准确率比较Fig.8 Prediction accuracy comparison of different algorithms

从图8可以看出,相比HMTP和Kalman算法,GMRTP算法的预测准确率平均提高9.9%和21.2%,且GMRTP比较稳定,准确率维持在90%上下波动.

4.2.3 预测时间性能分析

本节实验观察上述三种算法随着移动对象数量增加的预测时间代价,结果如图9所示.

从图9可以看出,GMRTP的预测时间最少,相比HMTP和Kalman算法,平均减少49.3%和11.3%.原因在于Kalman算法对每条轨迹中下一个位置预测都要将前一个位置信息代入回归分析,当预测的轨迹数量增加时,预测时间近似呈线性增长.而GMRTP预测时利用高斯过程刻画的轨迹仅需一次性预测即可,因此当预测轨迹数量增加时,只要没有增加较多的轨迹运动模式,预测时间并不会产生较大的增加和波动.而HMTP算法预测最为耗时,因为其在训练模型时需对轨迹进行分段处理,并利用HMM模型提取隐状态和观察状态,代价较高.

图9 不同算法预测时间性能比较Fig.9 Prediction time comparison among different algorithms

4.2.4 单一运动模式轨迹预测准确性对比

为了进一步证明基于高斯过程回归的轨迹预测算法GMRTP的通用性,本节比较在单一运动模式下,GMRTP和PathPrediction的预测准确性,实验采用GeoLife数据集,结果如图10所示.其中,横轴表示轨迹的数量,纵轴表示预测准确性.

图10 单一运动模式轨迹预测准确率比较Fig.10 Prediction accuracy comparison beyond single-motion-pattern trajectories

从图10可以看出,GMRTP算法对具有单一运动模式的轨迹进行预测时仍然具有很高的准确性,当移动对象数量大于2000时,预测准确率在90%以上;且随着移动对象数量增加,GMRTP均优于本文提出的基于频繁模式树的单一模式轨迹预测算法PathPrediction.原因在于GMRTP对轨迹数据利用概率密度函数建模,依据符合正态分布数据的条件分布得到回归函数完成回归预测,能够准确地反应移动对象真实运动行为.

5 总结与展望

多模式移动对象不确定性轨迹预测是移动对象数据库领域新提出的充满挑战性的研究课题,针对当前部分轨迹预测算法精度不高,复杂多模式轨迹预测准确性不高、预测实时性不能保证、预测轨迹长度较短的不足,本文提出一种基于轨迹频繁模式树的轨迹预测方法,充分考虑真实路网中的轨迹运动规则,预测结果准确性较高.为了对复杂多模式移动对象位置进行预测,提出了基于高斯过程回归的多模式轨迹预测模型,算法运行过程中无需设置大量参数,可以通过数据自身利用概率统计分布获得各种运动模式下的位置信息.

未来工作包括:1)对频繁模式树FTP-tree挖掘频繁项集进一步优化,提高算法的挖掘效率;2)与国内交通部门合作将所提模型应用于卡口摄像头采集到的交通数据,辅助跟踪和定位机动车辆和行人(主要针对未装备GPS定位系统的交通工具);3)为了保证预测的准确性,充分考虑影响对象运动行为的主客观因素.

References

1 Meng X F,Ding Z M,Xu J J.Moving Objects Management:Models,Techniques and Applications.Berlin:Springer-Verlag,2014.117−131

2 Hu W M,Xiao X J,Fu Z Y,Xie D,Tan T N,Maybank S.A system for learning statistical motion patterns.IEEE Transactions on Pattern Analysis and Machine Intelligence,2006,28(9):1450−1464

3 Parker A,Subrahmanian V S,Grant J.Fast and accurate prediction of the destination of moving objects.In:Proceedings of the 3rd International Conference on Scalable Uncertainty Management.Berlin,Germany:Springer,2009.180−192

4 Song C M,Qu Z H,Blumm N,Barabási A L.Limits of predictability in human mobility.Science,2010,327(5968):1018−1021

5 Centola D.The spread of behavior in an online social network experiment.Science,2010,329(5996):1194−1197

6 Jeung H,Yiu M L,Zhou X F,Jensen C S.Path prediction and predictive range querying in road network databases.The VLDB Journal,2010,19(4):585−602

7 Zhou J B,Tung A K H,Wu W,Ng W S.A “semi-lazy”approach to probabilistic path prediction in dynamic environments.In:Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM,2013.748−756

8 Pan T L,Sumalee A,Zhong R X,Indra-payoong N.Shortterm traffic state prediction based on temporal-spatial correlation.IEEE Transactions on Intelligent Transportation Systems,2013,14(3):1242−1254

9 Qiao S J,Shen D Y,Wang X T,Han N,Zhu W.A selfadaptive parameter selection trajectory prediction approach via hidden Markov models.IEEE Transactions on Intelligent Transportation Systems,2015,16(1):284−296

10 Qiao Shao-Jie,Li Tian-Rui,Han Nan,Gao Yun-Jun,Yuan Chang-An,Wang Xiao-Teng,Tang Chang-Jie.Self-adaptive trajectory prediction model for moving objects in big data environment.Journal of Software,2015,26(11):2869−2883(乔少杰,李天瑞,韩楠,高云君,元昌安,王晓腾,唐常杰.大数据环境下移动对象自适应轨迹预测模型.软件学报,2015,26(11):2869−2883)

11 Ding Z M,Yang B,Güting R H,Li Y G.Network-matched trajectory-based moving-object database:models and applications.IEEE Transactions on Intelligent Transportation Systems,2015,16(4):1918−1928

12 Xu J J,Gao Y J,Liu C F,Zhao L,Ding Z M.Efficient route search on hierarchical dynamic road networks.Distributed and Parallel Databases,2015,33(2):227−252

13 Dai J,Yang B,Guo C J,Ding Z M.Personalized route recommendation using big trajectory data.In:Proceedings of the 31st IEEE International Conference on Data Engineering.Seoul,South Korea:IEEE Computer Society,2015.543−554

14 Tripathy S,Howard C J.Multiple trajectory tracking.Scholarpedia,2012,7(4):Article No.11287

15 Xu J Q,Güting R H.A generic data model for moving objects.Geoinformatica,2013,17(1):125−172

16 Huang Yu-Long,Zhang Yong-Gang,Li Ning,Zhao Lin.An improved Gaussian approximate filtering method.Acta Automatica Sinica,2016,42(3):385−401(黄玉龙,张勇刚,李宁,赵琳.一种改进的高斯近似滤波方法.自动化学报,2016,42(3):385−401)

17 Chen Cheng,He Yu-Qing,Bu Chun-Guang,Han Jian-Da.Feasible trajectory generation for autonomous vehicles based on quartic Bézier curve.Acta Automatica Sinica,2015,41(3):486−496(陈成,何玉庆,卜春光,韩建达.基于四阶贝塞尔曲线的无人车可行轨迹规划.自动化学报,2015,41(3):486−496)

18 Monfort M,Liu A Q,Ziebart B D.Intent prediction and trajectory forecasting via predictive inverse linear-quadratic regulation.In:Proceedings of the 29th AAAI Conference on Arti ficial Intelligence.Austin,Texas,USA:AAAI,2015.3672−3678

19 Qiao S J,Han N,Zhu W,Gutierrez L A.TraPlan:an effective three-in-one trajectory-prediction model in transportation networks.IEEE Transactions on Intelligent Transportation Systems,2015,16(3):1188−1198

20 Han J W,Pei J,Yin Y W,Mao R Y.Mining frequent patterns without candidate generation:a frequent-pattern tree approach.Data Mining and Knowledge Discovery,2004,8(1):53−87

21 Rasmussen C E,Williams C K I.Gaussian Processes for Machine Learning(Adaptive Computation and Machine Learning).Cambridge,USA:The MIT Press,2005.12−22

22 Yu Jian-Bo,Lu Xiao-Lei,Zong Wei-Zhou.Wafer defect detection and recognition based on local and nonlocal linear discriminant analysis and dynamic ensemble of Gaussian mixture models.Acta Automatica Sinica,2016,42(1):47−59(余建波,卢笑蕾,宗卫周.基于局部与非局部线性判别分析和高斯混合模型动态集成的晶圆表面缺陷探测与识别.自动化学报,2016,42(1):47−59)

23 Dellaert F.The Expectation Maximization Algorithm,Technical Report GIT-GVU-02-20,Colleage of Computing,Georgia Institute of Technology,USA,2002.

24 Qiao S J,Tang C J,Jin H D,Long T,Dai S C,Ku Y C,Chau M.PutMode:prediction of uncertain trajectories in moving objects databases.Applied Intelligence,2010,33(3):370−386

25 BrinkhoffT.A framework for generating network-based moving objects.GeoInformatica,2002,6(2):153−180

26 Zheng Y,Xie X,Ma W Y.Geolife:a collaborative social networking service among user,location and trajectory.IEEE Data(base)Engineering Bulletin,2010,33(2):32−40

27 Deng Hu-Bin,Zhang Lei,Wu Ying,Zhou Jie,Liu Feng.Research on track estimation based on Kalman filtering algorithm.Transducer and Microsystem Technologies,2012,31(5):4−7(邓胡滨,张磊,吴颖,周洁,刘枫.基于卡尔曼滤波算法的轨迹估计研究.传感器与微系统,2012,31(5):4−7)