论文部分内容阅读
近年来，随着通信和位置感知技术的发展，基于位置的服务(Location Based Service，LBS)需求不断增加。位置预测是LBS的研究内容之一，在广告服务、位置导航等领域具有重要的应用。已有的位置预测方法多通过建立Markov位置预测模型和频繁轨迹挖掘来实现，尽管此类模型和方法可以较好地适用于GPS轨迹数据，可以有效地用于位置预测，但却存在模型阶数不好确定，轨迹挖掘过程只涉及轨迹数据本身体现的时间及空间特征，没有进一步挖掘轨迹数据所隐含的语义，从而导致位置预测性能差等问题。针对这些问题，本文基于GPS轨迹数据，从两方面对位置预测方法进行研究，一是针对基于Markov模型的位置预测方法存在的诸多问题加以改进;二是在考虑轨迹的时间及空间特征的同时，加入语义特征，研究基于多个轨迹特征的位置预测方法。
本文主要贡献如下:
(1)针对已有方法中存在的问题，提出了一种基于交通枢纽和Voronoi图的形成区域的方法，将地图分割为以交通枢纽为中心的更具物理意义的区域，为后续的模型构建以及预测提供了数据支持，增强了位置预测的实用性;
(2)在基于用户移动特征相似性的聚类过程中，针对轨迹数据的特点，提出了同时考虑用户的区域访问特征和区域变化特征，基于区域向量和位置转移概率矩阵的用户移动特征相似性度量和计算方法，在此基础上，通过聚类建立用户类簇，解决了基于单一用户数据建立模型存在的数据稀疏问题，同时，由于在聚类过程中考虑了用户的区域访问特征和区域变化特征，有助于提高位置预测的性能;
(3)针对已有的Markov位置预测模型中的问题，提出了一种多步融合的Markov位置预测模型，解决了1阶Markov模型对于轨迹信息利用不充分、预测性能差，以及多阶Markov模型状态空间急剧增长的问题。在建立多步融合Markov位置预测模型的过程中，为了提高各模型融合的效果，提出了基于Adaboost框架和差分进化算法的模型融合权重生成与优化方法;
(4)在建立用户类簇和多步融合的Markov位置预测模型的基础上，提出了基于移动特征相似性聚类的多步融合Markov位置预测方法。通过为聚类产生的用户类簇建立多步融合的Markov模型，并为当前用户轨迹选定符合其移动特征的用户类簇模型，解决了单一用户数据稀疏问题和状态空间增长问题，在不增加Markov状态空间的同时，提高了位置预测的准确率;
(5)在基于多个轨迹特征的位置预测中，针对轨迹数据的特点，改进了最长公共子序列求解方法，提出了基于轨迹语义及时间特征的语义序列相似性度量与计算方法，并基于此，进一步提出了基于聚类评价指标自适应确定相似度阈值的语义序列类簇生成方法，改善了聚类的效果。通过生成语义序列类簇，不仅解决了数据稀疏问题，而且解决了不能预测新的行为语义的问题;
(6)为了提高位置预测准确率，通过轨迹聚类以及为每个类簇建立语义树结构，充分利用轨迹的时间特征和所蕴含的语义特征，提出了语义模型构建方法。在此基础上，结合考虑轨迹空间特征的空间模型，提出了基于空间、时间及语义多个轨迹特征的位置预测方法，通过计算每个区域成为输出结果的语义概率和位置概率，进而计算其成为输出结果的综合概率，提高了位置预测的性能。
真实数据集上的实验和分析验证了本文所提出的位置预测方法的可行性和有效性。
本文主要贡献如下:
(1)针对已有方法中存在的问题，提出了一种基于交通枢纽和Voronoi图的形成区域的方法，将地图分割为以交通枢纽为中心的更具物理意义的区域，为后续的模型构建以及预测提供了数据支持，增强了位置预测的实用性;
(2)在基于用户移动特征相似性的聚类过程中，针对轨迹数据的特点，提出了同时考虑用户的区域访问特征和区域变化特征，基于区域向量和位置转移概率矩阵的用户移动特征相似性度量和计算方法，在此基础上，通过聚类建立用户类簇，解决了基于单一用户数据建立模型存在的数据稀疏问题，同时，由于在聚类过程中考虑了用户的区域访问特征和区域变化特征，有助于提高位置预测的性能;
(3)针对已有的Markov位置预测模型中的问题，提出了一种多步融合的Markov位置预测模型，解决了1阶Markov模型对于轨迹信息利用不充分、预测性能差，以及多阶Markov模型状态空间急剧增长的问题。在建立多步融合Markov位置预测模型的过程中，为了提高各模型融合的效果，提出了基于Adaboost框架和差分进化算法的模型融合权重生成与优化方法;
(4)在建立用户类簇和多步融合的Markov位置预测模型的基础上，提出了基于移动特征相似性聚类的多步融合Markov位置预测方法。通过为聚类产生的用户类簇建立多步融合的Markov模型，并为当前用户轨迹选定符合其移动特征的用户类簇模型，解决了单一用户数据稀疏问题和状态空间增长问题，在不增加Markov状态空间的同时，提高了位置预测的准确率;
(5)在基于多个轨迹特征的位置预测中，针对轨迹数据的特点，改进了最长公共子序列求解方法，提出了基于轨迹语义及时间特征的语义序列相似性度量与计算方法，并基于此，进一步提出了基于聚类评价指标自适应确定相似度阈值的语义序列类簇生成方法，改善了聚类的效果。通过生成语义序列类簇，不仅解决了数据稀疏问题，而且解决了不能预测新的行为语义的问题;
(6)为了提高位置预测准确率，通过轨迹聚类以及为每个类簇建立语义树结构，充分利用轨迹的时间特征和所蕴含的语义特征，提出了语义模型构建方法。在此基础上，结合考虑轨迹空间特征的空间模型，提出了基于空间、时间及语义多个轨迹特征的位置预测方法，通过计算每个区域成为输出结果的语义概率和位置概率，进而计算其成为输出结果的综合概率，提高了位置预测的性能。
真实数据集上的实验和分析验证了本文所提出的位置预测方法的可行性和有效性。