PostgreSQL机器学习插件MADlib实践-All Pairs Shortest Path篇

      MADlib是一个可以在数据库中使用的机器学习库，可以非常方便的加载到数据库中，其主要目的是扩展数据库的分析能力，它提供了一整套的机器学习、图、分析和统计方法来对结构化和非结构化数据进行分析，支持PostgreSQL、Greenplum数据库。MADlib 是伯克利大学的一个开源软件项目，2015年7月MADlib成为Apache软件基金会的孵化项目，其最新版本为MADlib1.17，支持PostgreSQL11、PostgreSQL12、Greenplum 6 ，官网地址：http://madlib.apache.org/。

图1 MADlib官网截图

       All Pairs Shortest Path，是MADlib中图相关机器学习算法中的一种，用来查找给定图中每个节点对之间的最短路径，城市道路网络也是一种图，可以通过这个算法来计算城市道路网络中两个任意节点的最短路径。本文利用惠州市部分道路线数据来制作图数据集，通过这个图数据集来实践All Pairs Shortest Path算法。惠州市部分道路线如图2所示。

图2 惠州市部分道路线数据

根据上图所示的道路线数据制作得到的图数据集，如图3所示

图3 惠州市部分道路线数据制作的图数据集

        在PostgreSQL数据库中通过MADlib这个机器学习插件提供的All Pairs Shortest Path计算函数（graph_apsp，graph_apsp_get_path）能计算出图3中任意两个蓝色点的最短路径。graph_apsp这个函数用来计算所用节点对的最短路径，图数据集中节点越多计算量越大（最大计算量为：V ^ 2 * E，其中V是节点数，E是道路线数量）。graph_apsp的使用方法如图4所示，结果如图5所示。graph_apsp_get_path这个函数用来计算源节点到指定目标节点的最短路径，graph_apsp_get_path的使用方法如图6所示，结果图7所示

图4 graph_apsp的使用方法

图5 graph_apsp计算结果截图

图5中src表示源节点的id，dest表示目标节点的id，weight表示从源节点到目标节点的最短路径的总权重，parent表示从源节点到目标节点的最短路径经过的中间节点。如果没有中间节点，则等于目标节点的id。

图6 graph_apsp_get_path的使用方法

图7 源节点801057到目标节点25735797的最短路径（图中红线）结果图

总结

        All Pairs Shortest Path，是MADlib中图相关机器学习算法中的一种，用来查找给定图中每个节点对之间的最短路径，本文利用惠州市部分道路线制作的图数据集，来实践这个机器学习算法，实践过程中依次计算得到了道路网络中所有节点对的最短路径、指定源节点到目标节点的最短路径，整个实践过程达到目的。计算图数据集中所有节点对的最短路径是一个很耗时的过程，这个过程消耗的时间会随着图数据量的增大而依次增大，但是这个计算完成后，计算指定源节点到目标节点的最短路径会变得很简单，这在实际应用中是一个亮点，因为，计算所有节点对的最短路径这个耗时操作可以在服务端先完成，在应用端请求计算指定源节点到目标节点的最短路径时，能快速响应。