暂无图片
暂无图片
暂无图片
暂无图片
暂无图片
首页 / KDD 2022 | MetaPTP: 面向个性化空间轨迹预测的自适应元优化模型

KDD 2022 | MetaPTP: 面向个性化空间轨迹预测的自适应元优化模型

时空实验室 2022-09-19
677
轨迹预测在许多提供准确有效位置的应用程序中至关重要。但解决冷启动情况仍然是个挑战。本次为大家介绍国际顶级数据挖掘会议ACM KDD 2022上的论文：《MetaPTP: An Adaptive Meta-optimized Model for Personalized Spatial Trajectory Prediction》。
一、背景
随着GPS设备的广泛使用，人们的位置被记录下来，积累了无数的轨迹。轨迹预测，旨在预测一条轨迹的未来位置，例如下一个基站、功能区或路段。在许多基于位置的应用程序中提供准确有效的服务至关重要，例如移动通信中的资源管理、城市规划和交通管理。
现有的轨迹预测模型，比如HMM、RNN，需要以海量历史数据为条件预测个人频繁路线。但由于轨迹稀疏问题，可能会遇到冷启动路径或用户，这类空间轨迹预测模型的性能会大大降低。虽然元学习模型可以缓解冷启动问题，但由于传统的元学习模型中所有任务学习⼀个全局共享的初始网络，这样相同的初始化可能会忽略个人旅行偏好并混合不相关的移动模式，从而导致次优结果，无法很好地适应每个用户。因此，使用少量数据发现序列模式和用户偏好变得非常具有挑战性。
该篇论文提出一种个性化空间轨迹预测的自适应元优化模型MetaPTP。首先，MetaPTP采用基于软聚类的方法在更细的粒度上指导网络初始化，使共享知识能够在具有相似旅游偏好的用户之间更好地传递。其次，对于模型微调，MetaPTP采用了更有效的轨迹采样方法，生成有意义的支持集，考虑用户偏好和空间轨迹相似性，为个性化模型适配提供任务相关信息。此外，还设计权重生成器，可以自适应地为支持集中的每个轨迹分配合适的权重，以避免对具有不同用户偏好和空间分布的轨迹使用相同的权重微调初始网络时出现次优结果。
二、基础模型（PTP）
MetaPTP以模型PTP为轨迹预测的基础模型，选择STLSTM对轨迹序列和时空信息进行建模。
  1.  轨迹建模
轨迹采用网格进行表示，将整个地理空间划分为m个网格（m­1×m2），每个网格单元表示一个地理区域，所有位置在同一个网格单元被视为同一个对象。给定用户行进的部分轨迹T­1­­={l­1,l2,…,lc}，采用查找层将轨迹序列中每个访问单元格的one-hot向量转换成相应的密集向量ej，则轨迹可以表示为 T­1­­={e­1,e2,…,ec}。再选择STLSTM通过将连续访问点之间的时空间隔融合到LSTM的现有门中，同时对轨迹的序列信息和时空信息进行建模。计算轨迹中第j个点的隐藏状态hj = STLSTM(hj-1, ej, sj-1, qj-1)，其中sj-1, qj-1分别表示lj-1和l­j的相对时间间隔和地理距离。
2. 用户移动偏好建模
用su=(w(g1),w(g2),…,w(gm))表示用户u轨迹的空间分布，其中w(gj)表示对应网络单元格的比重。采用TF_IDF权重策略，计算每一个用户的空间分配：
其中tf(gj)表示单元格g­j在该用户历史轨迹中的频率， Ngj,τu表示单元格g­j在轨迹中的次数， |Tu |表示g­j在所有单元格在轨迹Tu中出现的总次数；idf(gj)表示单元格g­j对于用户u的分辨能力，|U|是所有用户的个数， |Ugj|是轨迹中包含gj的用户总数。
为了从空间分布su进一步了解用户的移动偏好pu，使用两个全连接层和激活函数sigmoid将用户的空间分布su转换为低维表示向量pu
3. 轨迹预测
模型由连接层、全连接网络和预测层组成，结合轨迹序列信息和用户移动偏好来完成预测任务。首先，连接层将STLSTM的输出hc­和用户移动偏好pu组合成一个新向量，即zT=[hc,pu ]。然后，利用全连接网络将zT转换为更小且更具表达性的向量。最后，在将转后的向量输入预测层以预测未来访问轨迹中的单元格：
其中pT表示网格单元的概率分布；FCN是由两个全连接网络组成的全连接网络层；是预测层，将由FCN获得的向量映射到参数θpre的概率分布；是预测结果。
在基础模型PTP中，应用交叉熵作为损失函数：
其中yT,j是实际点的one-hot向量。
三、元优化模型
元优化模型中的自适应元优化框架，支持具有个性化的初始化，并能有效适应个性化轨迹的少样本的情况。该框架由四部分组成：任务聚类，集群感知参数存储，本地更新和全局更新。
1. 任务聚类
采用聚类的方法，根据空间分布将具有相似旅行偏好的用户分组到同一个聚类中，以更好地在相似用户之间传递共享知识。为了模糊用户的鲁棒性，采用软聚类的聚类方式；同时，软聚类可以保证可区分性，使得模型能够以端到端方式被训练。
将用户移动偏好pu线性用公式qT = Wq ∙ pu + bq线性投影到查询向量qT上，其中Wq和bq是学习参数。然后，再计算查询向量qT和每个聚类中心的相似度，其中 <qk, ck>是查询向量qT和聚类中心的余弦相似度，K是聚类的数量。值得注意的是，所有集群的聚类中心在训练前是随机初始化，并在训练期间不断更新。
2. 集群感知参数存储
每个集群都有一个集群感知参数内存，为每个任务提供个性化的初始化，通过它共享知识可以在具有相似旅行偏好的用户之间转移。
MP是参数存储器，存储预测层参数，以实现在具有相似旅行偏好的用户之间共享知识以及在初始化步骤中提供个性化的网络参数。从MP中读取网络参数bT：bT = (sT)T ⋅MP，bT是个性化偏差项。因此，轨迹可以在广义的基础上学习每个集群中的共享知识，得到个性化的预测层参数θpre：θpre = ϕpre - τbT，其中ϕpre是预测层的全局参数，参数τ控制个性化比率，即控制bT被考虑的占比。最后，再更新MP: ，其中学习后支持集上预测层的参数，𝛾控制MP的更新率，即添加多少新信息。
3. 本地更新
在局部更新期间，论文利用有效的轨迹采样方法来生成有意义的支持集和自适应权重生成器为支持集中的轨迹分配合理的权重，使模型可以结合用户和跟踪相关知识有效的模型适应。
支持集生成
为了结合用户相关知识进行微调，我们应该使用用户自己的数据来捕获用户移动偏好。
首先，查询轨迹子序列T1,c-1与查询用户有高度相似的偏好以及与查询轨迹有高度相似的序列模式，所以应被包含在支持集中；此外，选取部分最相关的个人数据参与微调，以减少计算成本提高效率。因此，选取高度相似的子轨迹T1,c以及M1个最相似的轨迹进行微调，其中相似度利用与T1,c的最长公共子序列（LCSS）进行评估获得：
然而，我们不仅需要考虑轨迹相似，还需考虑用户偏好的相似。所以，选取M2个最相关的轨迹进行微调，相关度用来衡量，其中是余弦相似度。
基于此，支持集包含了查询轨迹子序列，空间相似轨迹，用户移动偏好这三个因素。
权重生成
为了给不同的轨迹合理分配权重，应该充分考虑支持集中轨迹之间的相关性，即高度空间相似的轨迹和高度用户偏好相似的轨迹应有较高的权重。因此，结合利用STLSTM得到的轨迹表示和用户偏好表示得到。然后，通过余弦相似度计算轨迹之间的相关性，再利用全连接层获得权重。
本地更新过程
本地更新过程旨在利用有意义的支持集微调初始网络以适应每个任务。
首先，本地网络参数θ*来源于全局共享初始参数ϕ*（从中读取）。然后重新更新本地网络中的权重并使得损失函数最小。
4. 全局更新
采样一步的梯度下降法更新全局参数ϕ*，并满足每个训练轨迹的查询集的损失总和最小：
四、实验
实验采用两个真实数据集：2016年5月1日到2016年5月8日的北京出租s车轨迹数据，以及2013年7月1日至2013年12月31日的Porto轨迹数据。在北京数据集中，选取115.8135101°E 到 117.2543064°E 、 39.1323612°N 至 40.4178621°N范围，并在 47645 辆出租车中随机选择 20 万条轨迹。在波尔图数据集中，选取轨迹在 8.500014°W 到 8.699967°W 和 41.000148°N 到41.299362°N范围，并随机选择433辆出租车的10万条轨迹。对于每个数据集，论文选择 70% 的轨迹用于训练，10% 用于验证，剩下的 20% 用于测试。

1. 性能比较
为了评估模型的有效性，将采用的基础模型 PTP 与最先进的轨迹预测模型（DestPD、Flashback、DeepMove、STLSTM、HST-LSTM）进行比较。其次，将模型 MetaPTP 与同样处理冷启动问题模型（即基于迁移学习的模型 PTP-FT 和基于元学习的模型 MAML）进行比较；同时， PTP-FT、MAML 和 MetaPTP 采用相同的基本模型 PTP。
通过下表可以看出，对于基础模型而言， PTP 比所有现有其他方法准确度都要高。因为STLSTM采用了很好的方法来融合时空序列信息；同时还基于用户空间分布进一步建立用户移动偏好来改进指标。因此，论文认为 PTP 是最好的元学习基础模型。对于元学习策略而言，PTP-FT和MAML比基础模型要好，这说明迁移学习和元学习确实可以缓解冷启动问题。而MAML比PTP-FT的准确度要高，说明了元学习相较于迁移学习具有优势。最后，MetaPTP相较于MAML有进一步提高，说明了论文模型的优越性。
2.消融分析
MetaPTP-I：删除了基于软聚类的初始化方法，并为所有任务采用相同的初始网络。
MetaPTP-US：仅使用查询轨迹子序列作为微调的支持集，不使用用户历史轨迹（用户偏好）和空间相似轨迹。
MetaPTP-U：仅使用查询轨迹子序列以及空间相似轨迹作为支持集进行微调。
MetaPTP-S：仅使用查询轨迹子序列和用户的历史数据（用户偏好）作为支持集进行微调。
MetaPTP-W：移除了自适应权重生成器，并且对支持集中的所有轨迹使用相同的权重。
从上表中可以看出，MetaPTP-I、MetaPTP-US、MetaPTP-W的性能均比MetaPTP差，MetaPTP-S和MetaPTP-U优于MetaPTP-US。由此可得，MetaPTP达到最佳性能，而且说明了基于软聚类的初始化方法，使用查询轨迹子序列、空间相似轨迹、用户的历史数据（用户偏好）作为支持集进行微调，以及自适应权重生成器的重要性。
五、总结
该论文提出了一种自适应元优化模型MetaPTP，以解决由于数据系数而造成的冷启动问题。采用基于软聚类的方法在更细粒度级别上引导初始化，从而驱动共享知识在具有相似旅行偏好的用户之间转移，以解决所有用户使用相同初始化的缺陷；此外，引入了一种有效的轨迹采样方法生成有意义的支持集，以便模型可以结合用户和轨迹相关性实现个性化适应；同时，设计了一个自适应权重生成器来分配一个支持组中每个轨迹的合理权重，以实现有效模型适配。
-End-

本文作者

吴怡

重庆大学计算机科学与技术（卓越）专业在读大三学生，重庆大学CUST团队成员，主要研究方向：时空数据管理与挖掘。

重大时空团队（CUST，Chongqing University Spatio-Temporal Lab）发挥企业和高校的优势，深入探索时空数据收集、存储、管理、挖掘、可视化相关技术，并积极推进学术成果在产业界的落地！年度有2~3名研究生名额，欢迎计算机、GIS等相关专业的学生报考！
聚类自适应空间向量预测模型序列模式
文章转载自时空实验室，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

评论