原文传递
基于神经网络的路网最短路径距离高效计算
| 论文题名： | 基于神经网络的路网最短路径距离高效计算 |
| 关键词： | 交通路网;最短路径距离;近似计算;神经网络 |
| 摘要： | 在计算机领域，图（Graph）是一种经典的数据结构，用于描述节点和节点之间的依赖关系。交通路网（路网）就是一种典型的图数据，其上的每条道路可以看做图上的边、两条或者多条道路的交点可以看做图上的顶点。而路网最短路径距离则是指道路网络上任意两点之间的最短路径的长度。计算路网最短路径距离是很多基于位置的服务（LocationBasedServices，LBS）的核心操作。 传统的最短路径距离计算方法，如Dijkstra、Astar等精确方法存在着时间复杂度过大，运行效率过低的问题，在面对海量数据和用户查询时表现欠佳。因此，本文提出基于学习的方法来做路网最短路径的近似计算，通过牺牲一定的计算准确度，换取算法在时间效率和空间效率上的全面提升。 此外，本文提出使用Geohash编码的二进制表示形式作为节点的特征表示，该编码能表征节点在地理空间上的位置信息，和距离预测任务关系密切。和其他嵌入方法相比，具有信息密度高，信息质量高，易于神经网络训练等特点。使用该编码能显著简化模型结构、缩减模型训练成本以及减少使用模型计算最短路径距离的存储和计算的复杂度。具体而言，训练好的模型只需要常数级的存储成本。每个节点的表示也被缩减到9位的Base32字符，即45位0,1编码表示。模型训练完毕后，可以在常数级的时间内返回结果。 其次，Geohash编码作为空间填充曲线Z曲线的一种，存在着一定的突变性。尽管大部分情况下，该编码表示能很好的表示节点在地理空间中的位置信息。但是对于少部分情况，需要邻居节点的信息作为补充，起到一个噪声消除和数据增强的效果。本文实现了图神经网络中的卷积操作来实现该效果，进一步使用注意力机制自适应调节邻居节点的权重信息来增强模型的灵活性。和基于多层感知机实现的方法相比，该方法可以较好的利用图结构中的拓扑信息。 最后，实验中发现模型在不同量级的数据上训练效果差异显著。针对该问题提出使用对数归一化、根号归一化等方法放缩数据到同一尺度，减少归一化后的数据在数值大小上的差异，增强模型的鲁棒性，使得模型在不同量级的数据上均能表现良好。 实验部分论证了本文使用的模型和其他方法相比在时间效率、空间效率以及计算准确度上具有一定的优越性。具体而言，模型在训练完毕后，能在O(1)时间内返回用户查询，模型和节点表示占据O(V)的存储空间。同时，只有少量的精度损失。 |
| 作者： | 何润喆 |
| 专业： | 计算机技术 |
| 导师： | 周晓方 |
| 授予学位： | 硕士 |
| 授予学位单位： | 广州大学 |
| 学位年度： | 2023 |
检索历史
应用推荐
