《基于自编码器的旅行同伴挖掘》
本文是旅行类在职毕业论文范文与编码器相关在职毕业论文范文.
摘 要：随着移动设备的广泛应用,当今的位置跟踪系统不断产生大量的轨迹数据.同时,许多应用亟需具备从移动物体的轨迹数据中挖掘出一起旅行的物体（旅行同伴）的能力,如智慧交通系统和智慧营销.现有算法或是基于模式挖掘方法,按照特定模式匹配旅行同伴：或是基于表征学习方法,学习相似轨迹的相似表征.前一种方法受限于点对匹配的问题,后一种方法往往忽略轨迹之间的时间相近性.为了改善这些问题,提出了一个基于自编码器的深度表征学习模型Mean-Attn（Mean-Attention）,用于发现旅行同伴.Mean-Attn分别使用低维稠密向量表征和位置编码技术,将空间和时间信息同时注入轨迹的嵌入表征中;此外,还利用Sort-Tile-Recursive（sTR）算法、均值运算和全局注意力机制,鼓励轨迹向邻近的轨迹学习;从编码器获得轨迹表征后,利用DBSCAN（Density-Based Spatial Clustering of Applications with Noise）对表征进行聚类,从而找到旅行同伴.实验结果表明,Mean-Attn在寻找旅行同伴方面的表现要优于传统的数据挖掘算法和最新的深度学习算法.
关键词：旅伴同伴;自编码器;时空信息;STR算法;注意力机制
中图分类号：TP391 文献标志码：A DOI：10.3969/j.issn.1000-5641.202091003
0引言
挖掘结伴同行的移动物体（旅行同伴）在许多实际应用中是一个非常有价值的问题.例如,在智慧交通系统中,交通流的优化需要依赖道路传感器监控车流量.如果传感器能够发现大量汽车正沿同一路径行进,交通管制人员则可以及时管控和调整车辆行进路线,以减轻可能发生的交通拥堵.再如,在移动广告中,有研究证明,在同一时间出现在同一地点的消费者,通常会表现出共同的消费偏好.因而,发现一起行走的消费者群体,并向他们发放同一产品类别的优惠券,有可能会增加广告的营销效益.寻找旅行同伴在其他方面也有着广泛应用,包括机场安防、动物迁徙监测和公共游行管理等.
旅行同伴可以从物体的轨迹中挖掘.物体的轨迹是指按时间顺序排列的一系列位置点,而旅行同伴的轨迹在空间和时间上都比较接近,即在相近的时间内互相有大量彼此靠近的位置点.现有的旅行同伴挖掘方法可以大致分為两类：一类是基于模式挖掘的方法;另一类是基于表示学习的方法.基于模式挖掘的方法,通常首先依据专家经验来定义和旅行同伴有关的轨迹模式,即相似的轨迹,然后开发相应的算法从轨迹数据集中挖掘预定义的模式.这类算法中,轨迹的相似性计算通常基于点对之间的欧氏距离,因此要求待检验的轨迹按照时间戳对齐.但是,实际应用中的轨迹通常包含许多缺失的位置点,必须通过插值补齐后才能有效对齐,因而在挖掘过程中会引入大量的测量误差.另外,基于表示学习的方法不需要定义模式或逐点比较,而是使用机器/深度学习模型来学习轨迹的嵌入表征,然后将这些表征进行聚类,从而挖掘出相似的轨迹.现有的轨迹表征模型,一般需要一定的特征工程,或者需要特定的标签以进行有监督学习.在实践中,特征工程通常依赖于问题的定义并且很耗时,会给数据挖掘带来额外的开销;而轨迹标签信息通常很难收集,并且在使用时经常存在问题.除此以外,现有模型更多关注的是轨迹之间空间接近性上的特征,而忽略了轨迹之间时间接近性上的特征.因而,这样挖掘出的轨迹虽然形状相似,但并不一定对应一起旅行的同伴.
为了解决上述问题,本文开发了一种基于自编码器的无监督模型MEAN-Attn.该模型可以直接从原始轨迹中学习表征,输入的原始轨迹不需要按照时间戳对齐,即允许具有不同数量的位置点,也即轨迹长度可以不同.模型学习到的表征同时包含了原始轨迹的空间和时间特征,从而允许通过聚类轨迹表征的方式来发现旅行同伴.Mean-Attn的灵感来源于文本摘 要模型MeanSum.MeanSum模型可以用于对主题相似的文本进行摘 要式总结.基于此,本文首先使用STR算法对原始轨迹进行分组.STR算法最初用于对空间数据进行分组,以支持R树的批量构建.利用STR分组,可以使同一组内的轨迹具有一定的时空接近性.随后,从每组轨迹中抽取小的批次输入基于注意力的自编码器中.这背后的想法是鼓励时空上更近的轨迹能互相学习到更多相似的表征,同时在轨迹嵌入的时候,本文使用了位置编码技术,将轨迹的时间信息注入模型的输入表征中.然后,对每组轨迹学到的表征做均值计算,并使用一个一编码器结构对表征均值进行重编码.模型的损失函数分为两部分：一部分是轨迹的重构损失,用以控制轨迹学习自身的特征;另一部分是前述重编码表征和相应批次中其他轨迹表征的相似性,用以引导批次中的轨迹互相学习对方的特征.由于在编码时使用了注意力机制,并且使用均值计算来聚合一个批次的编码,因此本文将模型称为Mean-Attn自编码器.当模型训练完毕,就可以使用它的编码器对轨迹进行编码,然后使用聚类算法,如DBSCAN,对编码得到的表征进行聚类.最后,在聚类后同一个簇中的表征所对应的轨迹中,同时具有时间和空间上的相似性的可视为旅行同伴.
1相关工作介绍
1、1基于点对匹配的同伴挖掘
在过去的10年中,寻找旅行同伴的问题在数据挖掘领域已经有了非常广泛的研究.一些具有代表性的研究主要是Flock、Convoy、Swarm和Gathering.本文重点阐述与本文要解决的问题更相关的Convoy和Swarm这两个工作.Flock、Gathering与Convoy、Swarm这两个工作类似,但是定义旅行同伴模式的方法不同.Convoy被定义为一组至少包含m个移动物体的集合,且要求集合中中的移动物体需要在至少k个连续时间点内都是密度连通的：首先,通过在每个时间点执行聚类算法,发现密度联通的簇后,找出那些在连续的时间点内能够至少维护n个簇的对象;然后把这些对象加入Convoy候选集;最后,对于候选集中的每个对象,对其中的所有簇相交以测试所有的簇是否至少包含m个相同的轨迹.为了缓解计算复杂度过高的问题,Jeung等建议,首先根据简化的轨迹挖掘Convoy候选集,然后在微调步中确定每个候选集是否确实合格.另一个类似的工作是Swarm,它通过将旅行同伴定义为在至少k个可能不连续的时间点内具有密度连通特性的移动物体.这个定义放松了Convoy对旅行同伴的约束,即k个时间点可以不连续.这项工作的目的是发现所有封闭的群体,即群体中的轨迹集或者时间点都不能被扩大.由于候选的封闭Swarm数量过高,因此Li等提出了利用两种剪枝策略来缩小模式的搜索空间.
1.2基于表征学习的轨迹相似度计算
近年来,轨迹的表征学习引起了很多关注.因为它几乎不需要特征工程,并且不依赖于基于点对的相似度计算,一旦表征被学习到,就可以非常高效地将表征用于其他任务.与本文工作最相关的研究包括轨迹聚类和基于表征学习的轨迹相似度计算.Yao等使用序列到序列的自编码器来学习轨迹表征,并用于轨迹聚类任务：首先提取轨迹特征,例如速度和转弯速率等;然后将其转换为能描述相应对象移动模式的特征序列;最后,将特征序列输入自编码器模型,以学习固定长度的轨迹表征.随后,Li等提出了一种基于循环神经网络（Recurrent Neural Network,RNN）的模型来学习用于相似度计算的轨迹表征.该模型不需要特征提取,直接从原始轨迹中学习表征.但是,该模型的训练是有监督学习,需要对每条原始轨迹进行下采样,以构建训练对.值得一提的是,这两个工作都只关注寻找具有相似形状的轨迹,因此它们所发现的相似轨迹,有可能是时间上间隔很远的轨迹,因此不能被直接用来发现旅行同伴.另外,Zhang等的模型将额外的语义信息（例如环境约束和轨迹活动）注入到模型中,以获得更精确的轨迹表征.尽管如此,到目前为止还没有发现一个现有模型可以同时学习轨迹之间的时间相似性和空间相似性.
2Mean-Attn模型
2、1轨迹点的嵌入表征
首先,对于给定的轨迹数据集,将整个空间划分为大小相同的正方形单元.然后使用低维稠密表征技术对所有单元的嵌入表征进行预训练,使得空间上接近的单元具有更相似的嵌入表征.对于轨迹中的每个点,使用该点所在单元格的表征作为其表征,那么每条轨迹就可以表示为它所有点的表征的序列.
其次,为了捕获轨迹的时间特征,使用位置编码技术将时间信息注入轨迹的每个点的表征中.位置编码原先被用于Tranormer模型中用来捕获文本中各个单词之间的位置信息.由于已经将轨迹表示成了一个标识序列,因此可以使用相同的机制来给每个标识加入时间信息.位置编码PE（Positional Encoding）的计算方法为（本文用PpE表示）
2、2Mean-Attn自编码器
为了鼓励每条轨迹更多地向时空接近的轨迹学习,首先根据轨迹的时空接近性将它们粗略地划分为不同的组,然后将每个组独立地输入到自编码器中.这里使用STR算法对轨迹进行分组.STR算法最初用于将空间接近的对象打包为最小边界矩形MBR（Minimum Bounding Rectangle）,并用来构建R树索引的批量加载.由于每个轨迹都可以视为三维空间（t,x,y）中的一个对象,其中t是时间维度,x和y代表两个空间维度,因此可借用STR的思想粗略地对轨迹进行分组.被分到同一个MBR的轨迹在时间上和空间上都更为接近,因此更有可能是旅行同伴.随后从每个MBR中单独抽取轨迹,组成小批次送入模型,相比原来开放式地抽取轨迹组成一个批次,小批次的处理更有可能包含旅行同伴,从而有更多的机会学习到彼此相似的特征.
整个模型由两个共享参数的自编码器构建,如图1所示.左侧的编码器和构成了第一个自编码器,用于重构每条输入的轨迹.编码器和均采用LSTM（Long Short-Term Memory）网络.在模型右侧是一个一编码器结构.首先,对左侧的编码器输出的一个小批次的轨迹表征进行均值运算,得到一个小批次的平均编码,后将其送入右侧的,将输出的中间轨迹再次输到右侧的编码器中,以获得重编码的轨迹平均表征;然后,计算左侧编码器输出的每条轨迹的编码与右侧编码器输出的平均轨迹的重编码之间的相似性,用以控制轨迹在自我编码的同时,尽量学习与其邻近轨迹的特征.为了既保证轨迹的自我重构,又保证从邻近轨迹学到相似的表征,左右两侧的两个编码器和分别需要共享相同的结构和参数.
在两个LSTM编码器上,本文还使用全局注意力机制来汇总每个步骤的隐藏状态,以形成最终的输出编码.该编码考虑了整个轨迹的全局信息,实验证明能够提高编码的表征能力.具体来说,首先初始化与轨迹点维度相等的全局注意力向量a,用来计算轨迹中每个轨迹点的注意力得分,相应公式为其中,Hti表示在左侧模块中编码器生成的针对ti轨迹的注意力聚合编码,Ht'代表由右侧的编码器生成的平均轨迹重编码.通过同时最小化重构损失和相似性损失,迫使编码器产生的编码,既保持轨迹自身的独特特征,也能从同一组中的邻居轨迹那里学到相似的特征.这样,相似的编码所对应的轨迹,同时在时间和空间上具有相似性.
3实验结果
3、1实验数据和评估指标
本文在与亚洲某机场的合作研究中,获得了一个真实的乘客机场轨迹数据集.该数据集包含14 605个轨迹,约有719 507个位置点,每个轨迹包含20至120个点.本文使用此数据集来训练模型,挖掘一起行走的乘客.
将Mean-Attn与简单的LSTM自编码器（LSTM-AE）、两个经典的模式挖掘算法Convoy和Swarm,以及两个机器学习模型T2Vec（Trajectory to Vector）和BFEA（Behior Feature ExtractionAlgorithm）进行比较.对于基于模式挖掘的两个算法Convoy和Swarm,本文比较它们抽取的簇数（旅行同伴的组数）,且先学习轨迹表征,然后对表征聚类得到的簇数进行比较.为了遵循算法的要求,本文在数据集中进行线性插值,针对每条轨迹,每10s为一个时间步,在轨迹点缺失时生成一个插值点.对于T2Vec和BFEA,修改模型的输入,将位置编码添加到其原始嵌入中,以便和本文的模型进行公平比较.本文使用DBSCAN对学习到的编码进行聚类,并比较各个算法的聚类性能.
在评估轨迹表征聚类效果时,本文采用Dis-Bouldin Index、Silhouette Coefficient以及WeightedAverage Entropy（加权平均熵）这3个指标来衡量.Dis-Bouldin Index首先根据每个簇的直径找到最相似的簇,然后计算这些簇的平均相似度,因此较小的值通常表示着较好的聚类性能.SilhouetteCoefficient是衡量每个对象与相同簇内的其他对象相比于簇外的对象是否更相似的一种度量;较高的Silhouette Coefficient值表示每个对象与相同簇内的对象相似度较高,而与簇外对象的相似度较低,因此表明聚类效果更好.Dis-Bouldin Index和Silhouette Coefficient是进行聚类评估的内部指标.除此之外,本文还计算所有簇的加权平均熵并将其作为外部指标.簇的熵是聚类对象的最大似然估计,当簇中的对象的类别较为一致时,簇的熵较小.加权平均熵是所有簇的熵的加权总和,其中每个簇的权重是簇的大小除以对象总数.更好的轨迹表征应使得簇的加权平均熵较小.尽管无法得到轨迹的类别标签,但如果几名乘客是旅行同伴,那么他们更有可能乘坐同一航班.基于此假设,本文将每个轨迹的最后位置点,与10 min后的第一个航班相关联,并将该航班用作进行熵计算的轨迹标签.对于所有这些实验,本文丢弃大小为1的簇,即被视为单独移动的轨跡.
该文结论,此文是一篇关于编码器方面的大学硕士和本科毕业论文范文,可作为旅行相关论文开题报告写作参考和职称论文写作文献资料.
旅行引用文献:
[1] 旅行论文范文 关于旅行方面在职毕业论文范文2万字
[2] 旅行论文范文 关于旅行相关在职毕业论文范文2000字
[3] 旅行论文范文 旅行类硕士论文范文2500字
