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

摘要

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

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1 研究背景和意义

1.2 研究现状及存在的问题

1.3 本文研究内容和方法

1.4 本文组织结构

第二章 相关概念及技术

2.1 相关概念

2.2 相关技术概述

2.3 本章小结

第三章 基于变阶马尔科夫模型的位置预测方法

3.1 引言

3.2 相关技术及存在的问题

3.3 整体处理框架

3.4 基于多级聚类算法的物理位置提取方法

3.5 基于VOMM的位置预测方法

3.6 实验设计

3.7 本章小结

第四章 基于Voronoi图的位置预测方法

4.1 引言

4.2 整体处理框架

4.3 基于Voronoi图的语义轨迹挖掘

4.4 基于统计模型的位置预测方法

4.5 实验设计

4.6 本章小结

第五章 总结与展望

5.1 本文工作总结

5.2 今后工作展望

致谢

参考文献

附录