基于历史轨迹的位置预测方法的研究.pdf

硕士学位论文





题目: 基于历史轨迹的位置预测方法研究


研究生杨洁
专业计算机应用技术
指导教师徐建教授


完成日期 2015 年 3 月


万方数据
杭州电子科技大学硕士学位论文






基于历史轨迹的位置预测方法研究





研究生: 杨洁
指导教师: 徐建教授

2015 年 3 月

万方数据
Dissertation Submitted to Hangzhou Dianzi University
for the Degree of Master









The Research on Technologies of
Predicting Next Location Based on
Historical Trajectory













Candidate: Jie Yang
Supervisor: Prof. Xu Jian



March, 2015


万方数据
杭州电子科技大学
学位论文原创性声明和使用授权说明

原创性声明

本人郑重声明: 所呈交的学位论文,是本人在导师的指导下,独立进行研究工
作所取得的成果。除文中已经注明引用的内容外,本论文不含任何其他个人或集体已
经发表或撰写过的作品或成果。对本文的研究做出重要贡献的个人和集体,均已在文
中以明确方式标明。
申请学位论文与资料若有不实之处,本人承担一切相关责任。

论文作者签名: 日期: 年月日

学位论文使用授权说明

本人完全了解杭州电子科技大学关于保留和使用学位论文的规定,即:研究生
在校攻读学位期间论文工作的知识产权单位属杭州电子科技大学。本人保证毕业离校
后,发表论文或使用论文工作成果时署名单位仍然为杭州电子科技大学。学校有权保
留送交论文的复印件,允许查阅和借阅论文;学校可以公布论文的全部或部分内容,
可以允许采用影印、缩印或其它复制手段保存论文。(保密论文在解密后遵守此规定)



论文作者签名: 日期: 年月日

指导教师签名: 日期: 年月日



万方数据
杭州电子科技大学硕士学位论文
摘要
位置预测一般可以分为两个子问题,即从历史轨迹中发现有意义的位置和利
用处理后的轨迹数据预测用户的下一个位置。本文针对传统的位置预测技术存在
的缺点,分别研究了上述两个问题。考虑到人们出行时是基于遍布城市的交通道
路网络的事实,本文又研究了路网环境下针对大规模轨迹数据的位置预测问题,
并提出了高效的方法。本文主要工作如下:
首先,提出了一种基于一致性相关关系进行扩展的停留位置发现方法。从历
史轨迹中发现有意义的位置,关键在于停留位置的提取。停留位置是那些人们花
了一段时间进行一些活动的地点。本文通过分析现有的停留位置提取方法,发现
他们存在以下问题:1)提取出的结果过于粗糙,往往丢失了大量可能的结果;2)
不适合处理低采样率轨迹。针对以上缺点,本文首先定义了一致性权值,来量化
停留位置密度大,轨迹点速度小的特征。然后提出了基于一致性权值进行扩展的
算法,该算法从某个轨迹点开始根据一致性权值向外扩展,这类似于 DBSCAN
聚类算法。
然后,提出了一种具有较小空间复杂度、能解决零频率问题的位置预测方法。
基于矩阵实现的传统位置预测模型,存在空间复杂度高和零频率问题。针对传统
预测模型中存在的这些问题,本文通过训练变阶马尔科夫模型来预测位置。变阶
马尔科夫模型分别采用字典树和逃逸机制来解决上述两个问题。
最后,提出了一种基于 Voronoi 图、能够处理大规模轨迹数据的预测方法。
路网环境错综复杂,路口和路段众多,数据量十分之大。基于多级聚类算法的方
法能有效挖掘出语义轨迹,但是运行时间消耗非常大,而且这种方法没有利用起
路网信息。由此,本文提出基于 Voronoi 图的位置预测方法来处理路网环境下针
对大规模轨迹数据的位置预测问题。该方法首先在 Voronoi 图分割地图的基础上,
将轨迹转化为用 Voronoi 图单元区域表示的语义轨迹,然后通过训练统计模型来
预测位置。
综上,本文通过对现有研究的总结,对停留位置提取方法,预测模型,针对
大规模轨迹数据的预测算法展开了研究。实验结果