没有合适的资源?快使用搜索试试~ 我知道了~
一种基于高斯混合模型的轨迹预测算法_乔少杰1
需积分: 0 2 下载量 119 浏览量
2022-08-04
15:49:16
上传
评论
收藏 1.05MB PDF 举报
温馨提示
试读
16页
摘要:在智能交通控制系统、军事数字化战场、辅助驾驶系统中,实时、精确、可靠的移动对象不确定性轨迹预测具有极高的应用价值.智能轨迹预测不仅可以提供精准的基于位置的
资源详情
资源评论
资源推荐
软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: [email protected]
Journal of Software,2015,26(5):10481063 [doi: 10.13328/j.cnki.jos.004796] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563
一种基于高斯混合模型的轨迹预测算法
乔少杰
1
,
金
琨
1
,
韩
楠
2
,
唐常杰
3
,
格桑多吉
4
, Louis Alberto GUTIERREZ
5
1
(西南交通大学 信息科学与技术学院,四川 成都 610031)
2
(西南交通大学 生命科学与工程学院,四川 成都 610031)
3
(四川大学 计算机学院,四川 成都 610065)
4
(西藏大学 藏文信息技术研究中心,西藏 拉萨 850000)
5
(Department of Computer Science, Rensselaer Polytechnic Institute, New York, USA)
通讯作者: 韩楠, E-mail: [email protected]
摘 要: 在智能交通控制系统、军事数字化战场、辅助驾驶系统中,实时、精确、可靠的移动对象不确定性轨迹
预测具有极高的应用价值.智能轨迹预测不仅可以提供精准的基于位置的服务,而且可以提前监测和预判交通状况,
进而推荐最佳路线,已经成为移动对象数据库研究的热点,亟需设计准确而高效的位置预测方法.针对现有方法的不
足,提出了基于高斯混合模型的轨迹预测方法 GMTP,主要步骤包括:(1) 针对复杂运动模式利用高斯混合模型建
模;(2) 利用高斯混合模型计算不同运动模式的概率分布,进而将轨迹数据划分为不同分量;(3) 利用高斯过程回归
预测移动对象最可能的运动轨迹.GMTP 是高斯非线性概率统计模型,其优势在于:计算结果不仅是位置预测值,更
是关于移动对象未来所有可能运动轨迹的概率分布,可以利用概率统计分布特性获得某种运动模式(如匀加速运
动)下的位置预测.大量真实轨迹数据集上的实验结果表明:与相同参数设置下的高斯回归预测和卡尔曼滤波预测
法相比,GMTP 的预测准确性平均提高了 22.2%和 23.8%,预测时间平均缩减了 92.7%和 95.9%.
关键词: 移动对象数据库;轨迹预测;高斯混合模型;运动模式
中图法分类号: TP18
中文引用格式: 乔少杰,金琨,韩楠,唐常杰,格桑多吉,Gutierrez LA.一种基于高斯混合模型的轨迹预测算法.软件学报,2015,
26(5):10481063. http://www.jos.org.cn/1000-9825/4796.htm
英文引用格式: Qiao SJ, Jin K, Han N, Tang CJ, Gesangduoji, Gutierrez LA. Trajectory prediction algorithm based on Gaussian
mixture model. Ruan Jian Xue Bao/Journal of Software, 2015,26(5):10481063 (in Chinese). http://www.jos.org.cn/1000-9825/
4796.htm
Trajectory Prediction Algorithm Based on Gaussian Mixture Model
QIAO Shao-Jie
1
, JIN Kun
1
, HAN Nan
2
, TANG Chang-Jie
3
, Gesangduoji
4
, Louis Alberto GUTIERREZ
5
1
(School of Information Science and Technology, Southwest Jiaotong University, Chengdu 610031, China)
2
(School of Life Science and Engineering, Southwest Jiaotong University, Chengdu 610031, China)
3
(College of Computer Science, Sichuan University, Chengdu 610065, China)
4
(Tibetan Information Technology Research Center, Tibet University, Lasa 850000, China)
5
(Department of Computer Science, Rensselaer Polytechnic Institute, New York, USA)
基金项目: 国家自然科学基金(61100045, 61165013); 教育部高等学校博士学科点专项科研基金(20110184120008); 教育部人
文社会科学研究青年基金(14YJCZH046); 中央高校基本科研业务费专项资金(2682013BR023); 科学计算与智能信息处理广西高校
重点实验室开放课题(GXSCIIP201407)
收稿时间: 2014-07-10; 修改时间: 2014-09-29; 定稿时间: 2014-11-25; jos 在线出版时间: 2015-02-02
CNKI 网络优先出版: 2015-02-02 15:24, http://www.cnki.net/kcms/detail/11.2560.TP.20150202.1524.005.html
乔少杰 等:一种基于高斯混合模型的轨迹预测算法
1049
Abstract: For intelligent transportation systems, digital military battlefield and driver assistance systems, it is of great practical value to
predict the trajectories of moving objects with uncertainty in a real-time, accurate and reliable fashion. Intelligent trajectory prediction can
not only provide accurate location-based services, but also monitor and estimate traffic to suggest the best path, and as such becomes an
active research direction. Aiming to overcome the drawbacks of the existing methods, a new trajectory prediction model based on
Gaussian mixture models called GMTP is proposed. The new model contains the following essential phases: (1) modeling the complex
motion patterns based on Gaussian mixture models, (2) calculating the probability distribution of different types of motion patterns by
using Gaussian mixture model in order to partition trajectory data into distinct components, and (3) inferring the most possible trajectories
of moving objects via Gaussian process regression. The GMTP algorithm is naturally a Gaussian nonlinear statistical probability model
and the advantage of the proposed model is that the result is not only a predicted value, but also a whole distribution beyond the future
trajectories, therefore making it possible to infer the location in regard to some motion patterns, e.g., uniformly accelerated motion, by
using statistical probability distribution. Extensive experiments are conducted on real trajectory data sets and the results show that the
prediction accuracy of the GMTP algorithm is improved by 22.2% and 23.8%, and the runtime can be reduced by 92.7% and 95.9% on
average, respectively, when compared to the Gaussian process regression model and Kalman filter prediction algorithm with similar
parameter setting.
Key words: moving objects database; trajectory prediction; Gaussian mixture model; motion pattern
随着无线移动通信设备和无线车载传感器的发展,获取移动对象时空位置的手段更加多样化.在诸多重要
应用领域中,如智能交通系统(ITS)、智能导航、数字化战场、物流配送、移动电子商务等,用户都需要及时查
询和分析各种移动对象的轨迹位置信息,移动对象轨迹位置预测已经逐渐成为移动对象数据管理
[1]
中极为重
要的研究方向.当前,数字化城市的公共交通车辆、出租车以及其他一些车辆都配备 GPS 及车载导航设备,可以
将不同时刻采集到的车辆位置信息连接起来,构成完整的轨迹时间序列,进而挖掘其动态运动模式.对移动对象
的轨迹信息挖掘的目的在于:在短时间内,可以提醒处于拥堵十字路口的驾驶员车辆前行的安全性;在长时间
内,预测可能会发生交通堵塞的区域,及时做出调度,引导交通并提醒驾驶员及时做出路线调整.在一般情况下,
移动对象总是周期性地向中央服务器发送其位置信息,然而在两次定位信息传递时间内,移动对象的具体位置
信息和运动轨迹是无从得知的.此外,移动对象运动环境的多样化也使问题更加复杂.如何对移动对象位置信息
准确预测,成为亟需解决的难点.当前已有一些研究成果,如移动对象的聚类、异常检测以及定位和运动趋势的
预测.其中,对移动对象位置预测技术不断地完善,但由于理论和技术的不成熟,大多数模型不能很好地适应不
断发展的移动计算技术的需要.诸如单一线性回归预测、神经网络预测、Markov 模型位置预测
[2,3]
等传统方法,
因其理论的局限性,未能应用于对实时性、抗干扰性要求较高的移动通信环境中.
1 相关工作
移动对象按照空间分布特性被分为 3 类:(1) 运动道路不受限制,如飞机、轮船、带有传感器的鸽子等;(2) 运
动轨道受限制,如公路行驶的车辆;(3) 运动道路轨迹分散,如移动用户.针对移动对象的位置预测主要分为过去
轨迹的重现、当前和未来轨迹的预测.本文主要研究对象是运动道路轨迹分散的移动对象,同时解决该类移动
对象的未来轨迹预测问题.当前,轨迹预测方法主要集中于轨迹频繁模式挖掘,通过挖掘频繁模式找出典型运动
模式
[4]
.代表性工作由 Morzy 等人
[5]
提出,提出一种结合前缀树 PrefixSpan 和频繁模式挖掘 FP-tree 算法挖掘移
动对象动态运动规则,但是构建前缀树和FP-tree 的时间代价较高.Jeung等人
[6]
提出了一种综合考虑移动对象运
动模式和运动函数的混合预测方法,然而提供的查询预测仅支持短期的查询结果.大多数轨迹预测方法基于轨
迹的地理特性,而 Ying 等人
[7]
结合个体运动轨迹的语义特征和空间位置预测移动对象下一位置信息.这一方法
的不足在于计算每条候选路径的 Semantic Score 时,代价较高.Zheng 等人
[8]
考虑个体的旅行经历和兴趣爱好,
提出了一种 Hypertext Induced Topic Search 模型推测其感兴趣的运动路线,但这一方法主要应用于向用户推荐
可能感兴趣的地点,不能给出一整条完整的运动曲线.本文的研究动机源于Song 等人
[9]
在 Science 上发表的介绍
预测人类移动性的工作,通过测量个体轨迹的信息熵,定量地给出了人类动态运动行为,具有 93%的可预测性.围
绕这一工作,近期,Pan 等人
[10]
提出了基于多变元正态分布的最佳线性预测器,这一方法的不足在于预测会产生
1050
Journal of Software 软件学报 Vol.26, No.5, May 2015
延迟,不能应用于交通流的实时监控.Zhou 等人
[11]
提出了一种称为“semi-lazy”的预测方法,利用动态选取的参考
轨迹构建预测模型,优点是可以基于少量的参考轨迹构建精准的模型.近期,针对受限路网中轨迹预测精度不高
的问题,Qiao 等人
[3]
提出了一种基于隐马尔卡夫模型的轨迹预测算法 HMTP,从海量轨迹数据中提取隐状态和
观察状态,根据不同类型的轨迹,自适应地预测最佳轨迹.与本文的工作不同点在于:本文提出了一种通用的轨
迹预测算法,不仅仅适用于受限路网中移动对象的轨迹预测问题.
大多数轨迹预测问题针对的都是受限路网中移动对象的位置查询和预测
[12]
.Tao 等人
[13]
提出一种基于未
知模型的预测方法,弥补了线性预测的缺陷,将轨迹数据存储在 TPR
*
树中,使用递归函数进行预测.然而,这一方
法忽略了主、客观不确定性因素的影响.Qiao 等人
[14]
充分考虑了影响移动对象位置变化的运动速度、方向和
路况信息,设计了一种基于时间连续贝叶斯网络的连续轨迹序列预测算法.实验证明,这一方法在轨迹预测的准
确性和时效性上均优于朴素预测算法.为了进一步提高预测结果的准确性和时效性,文献[12]提出了一种基于
轨迹时间连续贝叶斯网络的轨迹预测算法 TPMO,考虑了移动速度和方向对移动对象动态运动行为的影响.与
本文工作的不同点在于:本文所提出的预测算法可以解决轨迹离散状态预测准确性较差的问题,并且对于移动
对象轨迹的预测,可以依据概率模型精确度量其预测误差.
从时空轨迹数据中挖掘运动模式的多样性,对移动对象位置预测也是至关重要的.轨迹运动模式建模需要
对状态空间进行离散化分析,Hu等人
[15]
将轨迹模型视为离散状态点之间转变的过渡,离散状态分析方法的不足
在于:需要对大量时空数据进行离散化处理,并且需要分析离散数据点之间的关联.Feng 等人
[16]
基于隐马尔可
夫模型重现移动对象轨迹序列,这一方法无需考虑对象缺失的观察状态信息,但是预测准确率不高.Gaffney 和
Smyth 提出对原始连续轨迹基于原型的聚类方法
[17]
,通过增加高斯噪声,将具有相似轨迹部分的移动对象聚合
在一起,使用最大似然原理实现无监督学习.这是一种比较新颖和实用的轨迹数据分析方法,在本文的后续工作
中,借鉴其利用 EM 算法来确定轨迹聚类的簇个数,并考虑了聚类簇中轨迹点离散空间和时间偏移.轨迹位置预
测中,稳定线性回归如卡尔曼滤波对短时间内(1 步或 2 步)的预测有比较稳定准确的判断
[18]
,而对于长时间(未
来 5 步以上)的预测,仅当处理的轨迹数据是无噪声点的情况才比较有效.高斯过程回归方法对于处理具有噪声
点的数据有着比较好的预测效果,是一种基于非参数的概率性方法,而且所使用的训练数据集规模比较小
[19]
.
Qiao 等人
[20]
对轨迹数据构建双层索引,利用 RoI(region-of-interest)检查算法对轨迹进行划分,构建频繁轨迹模
式树预测移动对象最可能运动模式.针对上述研究的不足,本文提出了基于高斯混合模型(Gaussian mixture
model,简称 GMM)的轨迹建模方法,利用概率模型刻画运动轨迹.其优势在于:可以摆脱轨迹离散状态分析方法
的弊端,并且对于移动对象轨迹的预测,可以依据概率模型精确度量其预测误差.
2 基本概念及模型框架
本节首先给出几个主要概念,然后介绍本文所提出模型的框架及工作原理.
已知移动对象数据库 D,其中存储大量运动对象在不同时间采样点的位置信息,位置点在时间上的有序集
合称为轨迹,用 D={Trj
1
,Trj
2
,...,Trj
n
}表示,轨迹的数量定义为|D|.本文对轨迹作如下定义:
定义 1(轨迹序列). 移动对象原始轨迹序列 Trj={s
1
,s
2
,...,s
d
}表示有序的离散轨迹点{s
i
=(x
i
,y
i
,t
i
)|1≤i≤d}所
构成的序列,其中,t
i
表示时间戳,i[1,d),t
i
<t
i+1
,(x
i
,y
i
)表示移动对象的 2 维空间坐标.
定义 2(轨迹矢量集). 对欧式空间 2 维平面 X 轴和 Y 轴方向进行建模,利用两个方向上的轨迹矢量表示轨
迹数据:
11 22 12 1 2
12
{ , ,..., } {( , ),( , ),...,( , )} {( , ,..., ) ,( , ,..., ) } { , },
n n nT nT
nxyxyxy xxxyyy
D Trj Trj Trj s s s s s s s s s s s s X Y
其中,
i
x
s
=(x
i1
,x
i2
,...,x
id
)
T
表示第 i 条轨迹在 X 方向上的投影矢量集,
i
y
s
=(y
i1
,y
i2
,...,y
id
)
T
表示第 i 条轨迹在 Y 方向上
的投影矢量集,
(,)
ii
x
y
s
s 称为轨迹 Trj
i
的矢量集,{X,Y}称为轨迹数据集 D 上的轨迹矢量集.
定义 3(高斯过程回归,Gaussian processes regression). 对于输入训练数据集
1
{( , )} ( , )
N
iii
Dxy Xy
,其中,
x
i
R
d
为 d 维输入矢量,X=[x
1
,x
2
,…,x
n
]为 dn 维输入矩阵,y
i
R 为相应的输出标量.已知输入数据集合 X,可构成
一个随机变量集合
{f(x
1
),f(x
2
),…,f(x
N
)},且具有联合高斯分布.该高斯过程全部统计数字特征可由均值函数 m(x)
乔少杰 等:一种基于高斯混合模型的轨迹预测算法
1051
和协方差函数 k(x,x)确定,即
f(x)~GP(m(x),k(x,x)) (1)
其中,m(x)=E[f(x)],k(x,x)=E[(f(x)m(x))(f(x)m(x))].本文采用的核函数为标准指数协方差函数,即
2
22
0
2
1
()
((),()) (,) exp
2
ij
xx
Cov f x f x k x x
(2)
其中,
0
为指数权重,θ
1
表示长度规模,
ij
是狄拉克函数.当 i=j 时,函数
ij
=1,否则为 0.
定义 4
(轨迹高斯混合模型). 轨迹高斯混合模型中,每个状态用一个高斯过程函数表示,即,数据是由多个高
斯过程模型线性组合产生的
,用公式(3)、公式(4)来表示轨迹点在二维坐标系下的 GMM 模型.假设数据点(x,y)
是多维运动矢量,其随机生成来自 M 个相互独立的高斯过程线性组合的总体 G={GP
1
,GP
2
,...,GP
M
},且每个高斯
过程对应的权重分为为
1
,
2
,...,
M
,混合而成的总体分布为 G,于是,x 的概率密度函数为
1
(|) (| , )
M
jjj
j
px GPx
(3)
1
(|) (| , )
M
jii
j
py GPy
(4)
其中,GP()表示高斯过程的概率密度函数,M 表示高斯过程数量,
j
为第 j 个高斯过程的权重,且
1
1.
M
j
j
表
示此密度函数中心点,
表示协方差矩阵.参数用集合表示为
={
i
,
i
,
i
},i=1,…,M.
定义 5(预测误差). 轨迹预测时,将测试轨迹数据集输入预测模型得到预测输出轨迹,其中,输入测试轨迹为
部分轨迹点的集合
,预测输出点由图 1 中虚线表示.
Fig.1 An example of predicted trajectories
图 1 预测轨迹示例
采用公式(5)所示的均方根误差 RMSE 来计算预测轨迹点与实际轨迹点的几何空间误差:
22
1
()()
k
ii ii
i
x
xyy
RMSE
k
(5)
其中,(x
i
,y
i
)表示真实位置, (,)
ii
x
y
表示预测位置,k 为预测轨迹点的数量.
本文所提出模型的系统框架如图 2 所示,其工作原理分为 3 个步骤:
(1)
利用 ETL 技术将历史轨迹预处理后转化为轨迹矢量存储于数据库中;
(2)
对不同运动模式轨迹数据进行 GMM 聚类分析,利用最大似然估计 EM 算法求得聚类模型参数,使其
基于历史数据模型概率达到最大化
,获得
M
个聚簇;
(3)
利用最小二乘法和高斯混合回归模型训练得到预测模型 GMTP,根据输入的新轨迹数据预测移动对
象未来最可能的运动轨迹.
本文第 3 节形式化给出移动对象简单和复杂轨迹运动概率模型.第 4 节给出高斯混合模型回归预测理论基
础.第 5 节详细阐述 GMM 轨迹预测模型训练和学习原理.第 6 节介绍基于 GMM 的轨迹预测算法.第 7 节通过
v
v
预测轨迹路线
实际轨迹路线
X
Y
(x
1
,y
1
)
(x
2
,y
2
)
(x
3
,y
3
)
输入历史轨迹点
11
(, )
x
y
22
(, )
x
y
33
(, )
x
y
剩余15页未读,继续阅读
H等等H
- 粉丝: 33
- 资源: 337
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0