PostgreSQL机器学习插件MADlib实践 Breadth-First Search篇

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

图1 MADlib官网截图

       Breadth-First Search，是MADlib中图相关机器学习算法中的一种，用于在给定图中以广度优先的方式搜索或遍历该图来查找可从源顶点到达的所有节点。城市道路网络也是一种图，可以通过这个算法来计算城市道路网络中每个节点在城市道路网络中能到达哪些节点，从而可计算每个道路节点的交通通达性，理论上城市道路网络中心的节点其交通通达性是最优的。本文利用惠州市部分道路线数据来制作图数据集，通过这个图数据集来实践 Breadth-First Search算法。惠州市部分道路线如图2所示。

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

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

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

       在PostgreSQL数据库中通过MADlib这个机器学习插件提供的 Breadth-First Search计算函数（graph_bfs）能计算出图3中任意蓝色点的能到达的所有蓝色点。graph_bfs函数是广度优先搜索算法在关系数据库中进行适当修改后的SQL实现。graph_bfs的使用方法如图4所示，结果如图5所示。

图4 graph_bfs的使用方法

图5 graph_bfs计算结果截图

      图5中id表示除起始道路节点外，起始道路节点可以到达的所有道路节点的id值，dist表示距离，以边为单位，是起始道路节点到达此节点经过几条边，parent表示到达当前道路节点经过的上一个道路节点的id值。

       根据图5的计算结果，可以得到起始道路节点能到达的所有道路节点及其所对应的边，进而可通过图形展示起始道路节点的交通通达性，如图6所示，图中绿色圆点为起始道路节点，离起始道路节点越近的边颜色越深，边宽度越大。

图6 起始道路节点（绿色圆点）的交通通达性图示

总结

      Breadth-First Search，是MADlib中图相关机器学习算法中的一种，用于在给定图中以广度优先的方式搜索或遍历该图来查找可从源顶点到达的所有节点。本文利用惠州市部分道路线数据制作图的数据集，来实践这个算法，利用这个算法的结果，可以得到起始道路节点能到达的所有道路节点及其所对应的边，通过计算这些边的长度总和，可以得到起始道路节点交通通达性的量化值，也可以计算包含这些边的最小面几何，这个最小面几何就是起始道路节点的通达范围。