英语原文共 10 页，剩余内容已隐藏，支付完成后下载完整资料
基于子轨迹理解的用户目的地预测：
一种基于深度学习的方法
Abstract
对于许多基于位置的服务，目的地预测是一个很重要的问题。存在的方法通常应用概率模型通过子轨迹去预测目的地，但是它们的准确率由于数据稀疏的问题，在细粒度预测上并不能让人满意。本文提出了精心设计的一种深度学习模型TALL，用来预测目的地。它不仅利用了双向LSTM网络对序列建模的优点，也通过注意力机制将更多的注意力放在那些又强关联性的位置。而且提出了多粒度学习能力融合的层次模型进一步提高预测准确性。在北京和成都的大量真实数据集的实验最终证明，我们提出的模型在不考虑外部特征的优于现有的方法。
Introduction
广泛使用的智能手机与车内导航系统已经成为了生活中的一部分，这些系统引导普及了GPC服务，使定位技术高速发展。我们越来越受益于各种的基于位置的服务，这些服务影响着我们的生活。目的地预测被用来预测一个子轨迹已经给定的轨迹目的地，这项技术变得越来越重要。大量的LBSs需要准确的目的地预测来提供有效可用的服务，例如推荐景点，发送针对性的广告，自动设置导航系统的目的地等等。
Figure 1:说明图例
在今日随着大量可用的用户轨迹，目的地预测准确率可以通过理解用户移动模式来实现。经典的方法一般采用轨迹搜索，搜索在数据库中可以覆盖给定子轨迹的轨迹。通过聚合这些轨迹的前k个目的地被选为最终预测目的地。可是，我们经常在数据中找不到或者很少有轨迹可以覆盖给定的子轨迹。目前位置，许多统计学的方法通常分解原始轨迹成基于网格的轨迹，并在空间网格粒度上预测目的地。基本思想是通过贝叶斯推理框架计算可能路径的概率，通过贝叶斯轨迹推到出目的地概率。但是有限的学习能力使得这些模型在大多数情况下只能支持粗粒度的预测。
例子1：在Figure 1 (a)中，有4条历史轨迹。t1={l1,l2,l6,l7,l11,l12}, t2={l1,l2,l6,l10,l11,l7,l8},t3={l5,l9,l10,l11,l15}. 和l4={l9,l10,l14,l15,l16}。每个li代表路网的一个交叉点，相连的线为路段。如果一个给定的子轨迹{l5,l9}，它匹配历史轨迹t3的前段部分，因为我们可以把l15作为它的目的地。可是，如果给定的子轨迹是{l1,l5,l6,l10}，轨迹搜索将会无返回结果，因为在Figure 1 (a)中没有轨迹可以覆盖它。现在，假定整个区域被分为4个空间网格，表示为n1,n2,n3,n4在Figure 1 (b)，所以子轨迹{l1,l5,l6,l10}将会转变为{n1,n4}。我们可以预测n3为用户最优可能到达的区域，因为大多是轨迹通过n1和n4,最后停在n3。可是当空间区域不够小的时候，这样的精度并不能令人满意。在现实中，LBS系统实际上需要改进模型，在精细力度上提供准确的目的地预测，从而保证个性化广告和景点推荐的质量。
现在，我们面临几个新的技术挑战。首先，它可能导致数据的稀疏性。在细粒度时，每个空间网格会更小。因此一个轨迹对应一个长序列网格，从而导致了数据的稀疏性，阻碍了传统统计推理模型的有效性。其次，有用的迁移模式可能会出现在不同的空间粒度中，而不是只用一个进行预测。一个更复杂的模型需要来学习不同粒度的隐藏特征和模式，并将它们合理的融合在一起。另外，在不同的天气条件，节假日情况下，人们的移动模式可能会有很大的差异，因此在训练是应该考虑外部特征来提高准确性。
近些年，在各种神经网络中，RNN网络已在时间序列数据的分析上得到了广泛的应用。研究证明LSTM网络在变长时间序列数据的建模方面有很好的性能，例如机器翻译，图像标注，语音识别等。因为目的地预测也依赖时间序列建模，它对于我们的问题，也认为是一个很好的机会。然而，标准的LSTM模型不足以支持精确细粒度预测，特别是当考虑学习各种细粒度的特征和模式，因此需要一个更具体的模型。此外，强烈的相关性可能会被忽略，如果位置序列轨迹互相远离，一些重要的位置与目的地有很强的关联性，需要被给予更多的关注。
针对上述的问题，本文提出了一个新的深度学习模型，用来预测细粒度的TALL模型。在这个模型中，双向LSTM被用来作轨迹的建模，所以轨迹前后的潜在特征都被学习，外部特征可以很容易的被融合来反应上下文感知移动模式。在注意力机制的帮助下，该模型可以识别和强调功能，与目的地有很强的相关性。不管他们在轨迹中的位置，来避免LSTM网络的缺陷。通过结合双向LSTM与注意力机制，该模型在解决细粒度下的数据稀疏问题又明显的有事。此外，我们还进一步整合多粒度知识来提高准确性，提出了分层次的深度学习模型来合并不同空间粒度中学习到的移动模式。
总之，我们在这篇文章中做了一下贡献：
- 我们提出了一个深度学习模型，结合了双向LSTM模型和注意力机制。这个方法不仅可以学习轨迹前后位置的潜在特征，融合外部特征来反应上下文感知移动模式，而且可以识别和强化跟目的地相关性强的特征。
- 我们进一步采用了多层级的深度学习模型来学习不同粒度下的有意义的移动模式，合理的融合模式，通过增强学习能力来提升预测结果的准确度。
- 模型考虑了假日时间和天气条件因素，通过一个可学习的参数矩阵将结果与这些信息自适应的融合，从而获得更准确的预测结果。
- 我们对北京和成都的真实轨迹数据集进行了大量实验，评估这些解决方案的有效性和效率。实验结果证明了我们模型的优点。
本文的其余部分组织如下。第二章节正式顶底了我们的问题。第三章节推导了一个基线算法，第四章节提出了注意力LSTM模型和多粒度融合框架来预测轨迹目的地。第五章节给出了大量的实验结果，证明我们提出的解决方案的性能。第六章节与第七章节讨论了相关工作与总结论文。
Problem Statement
这一章节介绍了一些初步的工作，并对本文所关注的问题进行了正式的说明。
原始轨迹是全球定位系统手机的一系列采样点。每个采样点都由两个经度和纬度组成坐标。Figure 2 (a)显示了轨迹T在地理空间上的投影。但是很显然，预测最终目的地准确的坐标是不现实的。同样，我们这里采用了基于网格的轨迹表示。
Figure 2：轨迹网格显示
地理空间被分为一组gtimes;g的网格，如Figure 2所示。在相同网格内的所有位置都被考虑为是同一个对象。每个网格边长相同为1，相邻网格步长为1，因此轨迹可以定义为：
定义1：一个轨迹T={T1,T2,hellip;hellip;,Ti,Ti 1,hellip;hellip;,Td}(1lt;=ilt;=d)是一个网格单元序列，获取用户的移动轨迹，每一个轨迹点Ti是一个至少包涵一个采样点的网格。我们使用Td代表轨迹T的目的地。
在文中剩下的部分，所有的轨迹都以网格来表示。显然，任何两个连续的轨迹点TI和Ti 1必须位于相邻的网格单元。
案例2：给定Figure 2中的原始轨迹，我们可以推导出序列{n5,n1,hellip;,n15,n14}作为其在网格表示中的对应序列。显然，我们可以看到T1=n5,T2=n1和Td=n14。T序列的目的地T是n14。
定义2（前缀轨迹）：给定轨迹T，子轨迹TP={Tp1，。。。，Tpc}作为轨迹T的前缀。如果其满足下列两个条件：（1）TP的序列与T开始于相同单元格（2）TP序列完全被包含在序列T中。子轨迹TP的最后一个点表示为TPc，是用户的当前位置。
案例3：在Figure 2 (b)，TP={n5,n1,n2,n6,n7}是T的子轨迹，该轨迹开始于n5并且TP完全被T包含。
假设TP是被观察的子轨迹，n7是当前位置。为了向用户推荐有用的位置感知信息，首先LBS系统需要估计轨迹T的最后目的地Td。下一步，我们将形式化论文的问题。
问题定义。给定一个轨迹数据集D，前缀轨迹TP，我们将返回前K个基于一些预测模型有最大概率为目的地Td的单元格。
Baseline Algorithm
在本章节，我们将介绍Sub-Trajectory Synthesis算法来解决目的地的预测问题。该方法遵守一般的贝叶斯推理框架，同时菜啊用了贝叶斯规则作为预测工具。贝叶斯规则包含先验概率与后验概率，该算法主要针对后验概率P(Tp|disin;nj),因为先验概率P(disin;nj)很容易得到。
在训练阶段，该算法应用了马尔可夫模型完成概率的准备工作，计算出概率P(Tp|disin;nj)。这些重要的概率被存储于两个二维空间个g2times;g2概率矩阵：一个转移矩阵M和一个总转移矩阵MT。在概率矩阵M的每个元素pij表示ni转换到临近nj的轨迹概率。算法生成M，通过内部的不同路径来计算两个不临近的单元格的转移概率，例如：ni与nk。因为这里有许多可能的路径从ni到nk，算法限制路径在一个典型的步长值内， ni与nk的总转移概率可以被得到，保存在MT。
在预测阶段，当一个轨迹的前缀TP是给定的，目的地Tp将被在线上被分析与回复。该算法引入了一个路径概率，将一个轨迹的前缀看作是相邻单元的合成。这是一个人通过特定路径从一个地方旅行到另一个地方的概率。在我们得到原始矩阵MT和路径概率P(TP)，用户从起始单元格到当前单元的后验概率通过TP在目的地nj为条件可以得到。因此，每一个单元nj是目的地轨迹的前提条件Tp在贝叶斯规则中可以计算。当用户发出一个查询，这些单元格根据他们目的地概率P(disin;nj |Tp),排序前K个元素返回最可能的目的地。
Discussion.然而，传统的马尔可夫模型方法在细粒度预测上存在缺陷。首先，每个轨迹对应一个更长的序列，数据稀疏性问题变得更加重要。另外，在马尔可夫模型中每个状态完全依赖于前一个状态，所以下一个轨迹点的预测只考虑前一个轨迹点，而沪铝了其他所有通过位置的相关性。这严重的限制了Sub-Trajectory Synthesis算法的精度，特别是在细粒度预测方面。因此我我们提出了更有效的模型来提高精度。
Solutions
在这个章节，我们介绍了两种设计好的方法来达到精确预测用户目的地。第4.1章节描述了注意力机制与LSTM网络模型。而且，在4.2章节介绍了通过探索和合并不同空间粒度的一个多层级的卓越学习能力的模型。
4.1 Trajectory based Attentional LSTM Learning model
Overview.对我们的目的地预测问题，直接使用LSTM网络可能不太令人满意
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[240527]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
