(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211183127.2 (22)申请日 2022.09.27 (71)申请人 沈阳航空航天大 学 地址 110136 辽宁省沈阳市道义经济开发 区道义南大街37号 (72)发明人 李佳佳　王明申　赵颖　李雷　 (74)专利代理 机构 沈阳维特专利商标事务所 (普通合伙) 21229 专利代理师 李娜 (51)Int.Cl. G06F 16/2453(2019.01) G06F 16/22(2019.01) G06F 16/29(2019.01) G06F 16/9537(2019.01) (54)发明名称 一种基于轨迹表示学习的相似度查询优化 方法 (57)摘要 本发明公开了一种基于轨迹表示学习的相 似度查询优化方法， 本发明的轨迹相似度查询是 将轨迹表 示成向量， 在向量空间利用两个向量之 间的欧氏距离找到离查询轨迹距离最近的轨迹。 本发明提出了一种基于路网分区的轨迹表示学 习模型PT2vec， PT2vec考虑了轨迹的空间特征和 底层路网的拓扑约束将轨迹嵌入到低维向量空 间， 设计一个基于空间和拓扑信息的损失函数， 加快模型的训练， 提高模型准确度， 并有效的解 决了大规模轨迹相似度计算时间过大的问题。 同 时为了减小轨迹查询 空间， 提高查询效率， 使用 PT‑GTree索引对查询数据库中的轨 迹进行剪枝。 权利要求书2页 说明书6页 附图3页 CN 115544070 A 2022.12.30 CN 115544070 A 1.基于路网划分的轨 迹表示学习和相似度查询方法， 其特 征在于， 包括如下步骤： S1:对路网进行分区， 并对每 个分区及边界边按顺序排 号赋予标签单词， 构建词汇 表； S2:获取多条原始轨迹， 基于上述词汇表， 对原始轨迹进行路网匹配， 将匹配后的轨迹 序列转换为词序列； S3:根据分区结果构建PT ‑GTree， 将步骤S2中匹配后的轨迹存储到PT ‑GTree最小公共 祖先节点中， 针对轨迹相似性查询， 利用PT ‑GTree对查询数据库进 行剪枝， 确定查询候选轨 迹集； S4:构建基于GRU的编码器 ‑解码器模型， 使用步骤S2中的词序列作 为输入， 经过编码器 将其编码为低 维的潜在向量v， 然后通过解码器解码出一个输出序列y， 同时设计一种基于 空间和拓扑信息的损失函数对该模型进行训练； S5:利用训练好的编码器 ‑解码器模型将步骤S3中确定的候选轨迹嵌入到低维向量空 间， 将候选轨迹都表示成向量的形式， 使用两个轨迹 向量之间的欧氏距离来表示轨迹的相 似程度， 距离越小轨 迹越相似。 2.按照权利要求1所述的基于路网划分的轨迹表示学习和相似度查询方法， 其特征在 于： 步骤S1中， 利用多层划分算法对路网进行划分， 具体的， 对路网的顶点和边 缘进行粗 化来减少网络规模； 使用Kernighan ‑Lin网络划 分算法对粗化的路网图上进行划 分形成多个子图； 通过设 定两个参数m和n进行划分， 其中m为每 个子图中路网节点的个数； n 为划分子图的数量； 对子图进行解粗， 生成原始网络的最终分区， 对最终分区和边界边按顺序编号赋予标 签， 每个标签对应相应的单词， 这些 单词组成词汇 表。 3.按照权利要求1所述的基于路网划分的轨迹表示学习和相似度查询方法， 其特征在 于： 基于PT‑GTree索引的轨 迹相似度查询剪枝方法如下： 利用步骤S2中的分区结果构建PT ‑GTree， 找到所有原始轨迹经过的所有叶子节点， 找 到所有叶子节点的最小公共祖 先节点， 并将原 始轨迹存储到相应的树节点中； 给定一条待查询轨迹， 首先找到待查询轨迹经过的所有叶子节点， 再根据这些叶子节 点找到待查询轨迹的最小公共祖先节点， 将最小公共祖先节点和其孩子节点中存储的原始 轨迹作为候选集。 4.按照权利要求1所述的基于路网划分的轨迹表示学习和相似度查询方法， 其特征在 于： 损失函数如下 所示 其中， W是将ht从隐藏状态空间投射到单词列表空间的投影矩阵， Wu表示它的第u行,D (u,yt)表示单词之间最短的路网距离， λ是一个距离尺度参数， TK(yt)表示接近yt的K个单 词， T(yt)表示拓扑 结构上直接与目标 单词相连的单词。权　利　要　求　书 1/2 页 2 CN 115544070 A 25.按照权利要求1所述的基于路网划分的轨迹表示学习和相似度查询方法， 其特征在 于： 步骤S5中， 将词序列输入到改进后模型的编码器， 通过嵌入和3层GRU网络的计算单元 将轨迹序列编码为 一个低维的潜在向量v； 解码器依此计算每个位置上的输出序列的条件概率； 具体的， 在某一位置上， 解码器将 该位置之前的输出序列和潜在向量转换为隐藏状态， 该隐藏状态保留了词 序列和输出序列 的序列信息， 然后通过隐藏状态预测该位置的输出， 最后得到输出序列y， 利用损失函数计 算输出序列y和目标序列之间的损失， 模型根据损失来调整参数， 使模型 更加准确。权　利　要　求　书 2/2 页 3 CN 115544070 A 3