基于Spark计算框架的路网核密度估计并行算法

关注
基于Spark计算框架的路网核密度估计并行算法www.shan-machinery.com1.1.  路网约束条件下的核密度估计

平面核密度估计方法以空间上某点为圆心,计算半径为r的圆形范围内事件发生的概率密度。计算公式如下:

$$\lambda \left(s\right) = \mathop {\sum\limits_{i = 1} }\limits^n \frac{1}{{{\rm{ \mathsf{ π} }}{r^2}}}k\left( {\frac{{{d_{is}}}}{r}} \right)$$(1)

式中,λ(s)为位置s处的密度;dis为事件点s之间的欧氏距离;k (·)为核函数(本文中取高斯核函数);r为带宽;n为与s相距r范围内的事件点总数。

路网约束条件下的核密度估计方法是将道路网分解为等长的线性单元(linear pixel,Lixel),以线性单元为最小研究单位,统计距离该线性单元最近的事件点总数,使用最短路网距离代替平面核密度估计方法中的欧氏距离进行计算[7],算法基本步骤如下:

1)将原有的道路网转化为基于路段的线性参考系统,相邻两条道路交叉点之间的线段称为路段,如图 1中的AF。

图  1 路段示意图

Figure 1. Illustration of Road Segment

2)将所有路段按照预设单位长度分为等长的线性单元,如图 1中的l1至l7,不足一个单位长度的也记为一个线性单元。

3)针对每个线性单元,遍历事件点集合,将每个事件点分配给距离其最近的线性单元,统计每个线性单元上的事件点总数。

4)对于每个线性单元,将其带宽范围内的其余线性单元视为邻居,通过如下公式计算其核密度:

$$\lambda \left(s\right) = \mathop {\sum\limits_{i = 1} }\limits^n {c_i}\frac{1}{r}k\left( {\frac{{{d_{is}}}}{r}} \right)$$(2)

式中,dis为线性单元i和线性单元s之间的最短路网距离;ci为线性单元i上的事件点总数。

考虑到每条道路有不同的道路行政等级,如主干道、次干道、县道、乡道等,不同等级道路上的事件造成的影响程度不同,因此将式(2)重新定义为:

$$\lambda \left( s \right) = \mathop {\sum\limits_{i = 1} }\limits^n {w_i}{c_i}\frac{1}{r}k\left( {\frac{{{d_{is}}}}{r}} \right)$$(3)

式中,wi为线性单元i的权重系数。在本文中,权重系数由线性单元所在道路的行政等级确定,主干道权重系数为1.6,次干道权重系数为1.4,县道权重系数为1.2,乡道和其他未明确定义行政等级的道路权重系数为1,权重系数可由用户根据实际应用需求进行自定义。

在基于路网的空间分析中,传统的二维核密度估计方法会产生估计偏差,从而导致错误的聚类结果[9]。因此本文在式(3)的基础上使用Okabe等[9]提出的无偏核函数——等分裂核函数进行密度估计。等分裂核函数如下:

$${K_y}\left( x \right) = \left\{ {\begin{array}{*{20}{l}}{\frac{{k\left( {d\left( {x,y} \right)} \right)}}{{\left( {{n_1} - 1} \right)\left( {{n_2} - 1} \right) \cdots \left( {{n_s} - 1} \right)}},0 \le d\left( {x,y} \right) \le r{\rm{}}}\\{0,{\rm{}}d\left( {x,y} \right) > r}\end{array}} \right.$$(4)

式中,Ky(x)为线性单元ly与线性单元lx之间的等分裂无偏核函数;d(x,y)为线性单元ly与线性单元lx之间的最短路网距离。定义节点的出度为该节点邻接的线性单元数量,如图 1中节点A的出度为3,节点F的出度为4,若ly与lx之间仅仅通过唯一一个节点相连,则该节点的出度为2,如图 1中的节点B、C、D、E。令ni为线性单元ly到线性单元lx之间第i个节点的出度,如图 1中,l1与l7的最短路网距离之间共有A、B、C、D、E、F共6个节点,n1为节点A的出度(即3),n2、n3、n4、n5分别为B、C、D、E的出度(即2),n6为节点F的出度(即4)。

1.2.  Spark并行计算模型

Apache Spark(以下简称Spark)是专为大规模数据处理设计的快速通用的内存计算引擎。Spark中的所有操作在内存充足的情况下均在内存中执行,效率是Hadoop的10倍至100倍[13]。

弹性分布式数据集(resilient distributed dataset,RDD)是Spark中的基本数据抽象,具有自动容错、位置感知调度及可伸缩性等特点。Partition是数据集的基本组成单位,对于单个RDD,每个Partition会被当作一个计算任务进行处理,同时Partition的大小决定了并行计算的粒度。Spark提供了上层应用接口,接受多种数据格式作为输入,内部自动将程序并行化,并负责向集群提交应用和进行一系列的分区、转换、执行等操作,将结果以RDD的方式输出。

1.3.  算法设计

基于Spark计算框架的路网核密度估计并行算法的主要思想为:各个excutor节点加载一部分计算数据,通过Spark的broadcast机制,从driver节点将所有excutor节点都使用到的公用数据进行广播,各个excutor节点并行完成各自计算任务,充分利用多核中央处理器(central processing unit,CPU)的计算性能,最后输出计算结果。本文算法将道路网在几何上抽象为单线进行处理,算法整体流程如图 2所示。

图  2 路网核密度估计并行算法流程图

Figure 2. Flowchart of the Parallel Algorithm for Road Network Kernel Density Estimation

其中,单条道路的数据结构LineInfo如下:

LineInfo{

int id; //道路编号

double weight; //该道路的权重系数

int partitionNum; //分区编号

LineString line; //道路(包含坐标信息)

List < Tuple2 < Integer, Coordinate >> crossPoints; //记录与其他道路的交点

List < LineString > segments; //有序线性单元集合

Map < Integer, List < Tuple2 < Integer, Integer >>> intersections; //路网索引结构

}

算法具体步骤为:

1)将整个路网集合记为S,对S中的每条道路给定唯一编号,记为Li(i=1,2…n),其中唯一编号对应LineInfo中的id。

2)将步骤1)中的路网集合S进行广播,各个excutor节点并行计算任意两条道路之间的交点,并记录相交道路的编号以及交点的坐标信息,该信息记录在LineInfo的crossPoints中。由于一条道路可能与其他多条道路相交,因此采用List存储,二元组Tuple的键为道路编号,值为交点坐标。

3)获取每条道路的起始点、拐点坐标,构建坐标序列,将交点坐标插入到构建好的坐标序列中。

4)以起止点、交点为分割点,将每条道路分为多条路段,再将各路段按照预设的线性单元长度分割为多个线性单元,不足一个线性单元长度的按一个线性单元处理,将分割完成的线性单元按顺序存入segments中。

5)根据步骤2)中记录的交点坐标信息及步骤4)中的线性单元分段信息构建路网拓扑结构,用于标识道路Li的第k段线性单元lik与另一条道路Lj的第t段线性单元ljt之间的邻接关系;在构建路网结构时,对segments中的各个线性单元的首尾节点进行编号,第n个线性单元的首节点编号为n-1,尾节点编号为n;针对每个线性单元,结合crossPoints信息和节点编号信息,即可完成路网拓扑结构intersections的构建;intersections中Map的键为当前LineInfo的节点编号,值为与该节点相交的其他LineInfo集合,二元组Tuple的键为LineInfo的编号,值为segments的节点编号。

6)计算每个事件点与每条道路的距离,选择与事件点距离最短的道路Li,再计算该事件点与Li上每个线性单元的距离,与该事件点距离最短的线性单元的计数值加1,如果最短距离超过阈值范围,则此事件点为无效点,不予考虑。

7)将步骤6)中的结果进行广播,在每个excutor节点中通过广度优先遍历方式并依据式(3)、式(4)计算每条道路Li上各段线性单元的核密度值。其中,广度优先遍历的层数通过带宽与线性单元长度的比值来确定。

https://www.shan-machinery.com