距离 vs 复杂性：大数据帮你导航_大数据培训-CDA数据分析师官网

热线电话：13121318867

距离 vs 复杂性：大数据帮你导航_大数据培训

2015-03-05

距离 vs 复杂性：大数据帮你导航_大数据培训

传统的路径规划算法一般基于最短旅行距离或时间来进行优化。然而空间认知学方面的大量研究已表明，人们在选择路径时，其他的一些因素往往发挥着重要的作用。例如在实际中，当本地人为外地游客指路时，常常舍弃那些难走、难认的道路，而选择给出那些容易走（例如较少转弯）的简单路径，即便距离并非最短。

在空间数据库的研究中，道路网络上最近邻的查找（如“离此处最近的邮局“）是一个重要的研究问题，因为它是各种基于位置服务的基石。在给定出发点和多个可能的候选目的地的情况下，当路径选择的标准从旅行距离变为通行复杂度时，“最易到达邻”的新概念可视为最近邻的自然延伸。它的查找对于在陌生的城市环境中旅行的人们大有帮助。

电子科技大学，大数据研究中心，数据挖掘与推理研究所邵杰教授和澳大利亚墨尔本大学的合作者一起，通过融合空间认知学的方法来分析空间簇集的效应和地标物的效应，从而对通行复杂度这一因素加以建模，实现了对道路网络上最易到达邻的高效查询处理。通过对墨尔本市道路网络数据（包括市中心密集网格状区域，以及市郊稀疏道路区域）上的超过1000万条的大量路径测试实验发现，最简单路径的旅行距离平均只比最短路径增长15.8%，93.2%的最简单路径比相应的最短路径增长的距离小于50%。近期在ACMInternational Conference on Information and Knowledge Management上发表的文章进一步用真实用户研究的方式验证了最易到达邻的实际使用效果：83.3%的受访用户表示，偏向于选择去到最易到达邻，而非选择实际旅行距离最短的最近邻作为他们的目的地。此外，在墨尔本市道路网络上随机选取出发点的大规模的实验结果表明，与最近邻相比最易到达邻的距离平均虽然增长16.2%，但通行复杂度仅为最近邻的42.3%。该研究还展示了导航系统如何同时兼顾旅行距离以及通行复杂度，为旅行者提供更佳的路径建议。