基于历史轨迹的位置预测方法的分析.pdf

硕士学位论文题目:基于历史轨迹的位置预测方法研究研究生杨洁专业计算机应用技术指导教师徐建教授完成日期2015年3月万方数据杭州电子科技大学硕士学位论文基于历史轨迹的位置预测方法研究研究生:杨洁指导教师:徐建教授2015年3月万方数据Dissertation Submitted to Hangzhou Dianzi Universityfor the Degree of MasterThe Research on Technologies of Predicting Next Location Based on Historical TrajectoryCandidate: Jie YangSupervisor: Prof. XuJianMarch, 2015万方数据杭州电子科技大学学位论文原创性声明和使用授权说明原创性声明本人郑重声明:所呈交的学位论文,是本人在导师的指导下,独立进行研究工作所取得的成果。除文中已经注明引用的内容外,本论文不含任何其他个人或集体已经发表或撰写过的作品或成果。对本文的研究做出重要贡献的个人和集体,均已在文中以明确方式标明。申请学位论文与资料若有不实之处,本人承担一切相关责任。论文作者签名:日期:年月日学位论文使用授权说明本人完全了解杭州电子科技大学关于保留和使用学位论文的规定,即:研究生在校攻读学位期间论文工作的知识产权单位属杭州电子科技大学。本人保证毕业离校后,发表论文或使用论文工作成果时署名单位仍然为杭州电子科技大学。学校有权保留送交论文的复印件,允许查阅和借阅论文;学校可以公布论文的全部或部分内容,可以允许采用影印、缩印或其它复制手段保存论文。(保密论文在解密后遵守此规定)论文作者签名:日期:年月日指导教师签名:日期:年月日万方数据杭州电子科技大学硕士学位论文I摘要位置预测一般可以分为两个子问题,即从历史轨迹中发现有意义的位置和利用处理后的轨迹数据预测用户的下一个位置。本文针对传统的位置预测技术存在的缺点,分别研究了上述两个问题。考虑到人们出行时是基于遍布城市的交通道路网络的事实,本文又研究了路网环境下针对大规模轨迹数据的位置预测问题,并提出了高效的方法。本文主要工作如下:首先,提出了一种基于一致性相关关系进行扩展的停留位置发现方法。从历史轨迹中发现有意义的位置,关键在于停留位置的提取。停留位置是那些人们花了一段时间进行一些活动的地点。本文通过分析现有的停留位置提取方法,发现他们存在以下问题:1)提取出的结果过于粗糙,往往丢失了大量可能的结果;2)不适合处理低采样率轨迹。针对以上缺点,本文首先定义了一致性权值,来量化停留位置密度大,轨迹点速度小的特征。然后提出了基于一致性权值进行扩展的算法,该算法从某个轨迹点开始根据一致性权值向外扩展,这类似于DBSCAN聚类算法。然后,提出了一种具有较小空间复杂度、能解决零频率问题的位置预测方法。基于矩阵实现的传统位置预测模型,存在空间复杂度高和零频率问题。针对传统预测模型中存在的这些问题,本文通过训练变阶马尔科夫模型来预测位置。变阶马尔科夫模型分别采用字典树和逃逸机制来解决上述两个问题。最后,提出了一种基于Voronoi图、能够处理大规模轨迹数据的预测方法。路网环境错综复杂,路口和路段众多,数据量十分之大。基于多级聚类算法的方法能有效挖掘出语义轨迹,但是运行时间消耗非常大,而且这种方法没有利用起路网信息。由此,本文提出基于Voronoi图的位置预测方法来处理路网环境下针对大规模轨迹数据的位置预测问题。该方法首先在Voronoi图分割地图的基础上,将轨迹转化为用Voronoi图单元区域表示的语义轨迹,然后通过训练统计模型来预测位置。综上,本文通过对现有研究的总结,对停留位置提取方法,预测模型,针对大规模轨迹数据的预测算法展开了研究。实验结果表明本文提出的停留位置提取方法效果优异,基于VOMM的位置预测方法在大大降低空间需求的同时提高了预测精度,而基于Voronoi图的方法能快速处理路网环境下的位置预测问题。本文的研究有助于在线的实时LBS服务技术的发展。关键词:位置预测,轨迹挖掘,GPS轨迹分析,数据挖掘,轨迹数据库万方数据杭州电子科技大学硕士学位论文IIABSTRACTPredicting users’future location can be divided into two sub-problems, . obtaining significant places from history trajectories and predicting locations based on statistical models. This paper presents new approaches to deal with b