使用LightGBM识别城市道路格网模式

Identifying Grid Pattern of Urban Road Networks Using LightGBM

摘要: 在分析格网模式下城市道路网几何形态及空间分布特点的基础上，运用矩形度、平行度、主方向一致度、质心方向一致度、形状相似度等指标描述道路网眼特征，构建道路网模式识别输入参数组合，然后应用LightGBM方法对道路网眼进行分类，根据输出结果识别道路网格网模式。实验结果表明，该方法可以比较准确地识别城市道路网格网模式。

Abstract: Based on the analysis of the geometric appearance and spatial arrangement characteristics of ur-ban road networks in grid pattern, the features of the road mesh are described by using the indi-cators of rectangularity, parallelism, main direction similarity, centroid direction similarity and shape similarity, formed a combination of parameters for model input of pattern recognition of road networks, then, use LightGBM to classify road mesh and identify the grid pattern of road networks according to the output. The experimental results show that the method can accurately identify the grid pattern of urban road networks.

1. 引言

道路网是城市整体规划布局的骨架，也是地图、地理信息中最基本的地理要素之一，为智能导航、位置服务等应用提供了重要信息 [1] [2]。城市道路网在形成过程中受各种因素的影响，在几何形态上呈现出一定的空间结构模式特征，如线性模式、格网模式、星型模式、环状模式等 [3] [4]。研究识别道路网几何形态空间模式对道路网综合、多尺度路网建模等具有重要意义。

格网模式在城市道路网中较为普遍，对其进行研究识别的也比较多。道路格网模式识别方法按数据几何维度可分为两类。一是基于面状道路网眼的几何形态及空间分布特征的识别方法。如Heinzle等基于道路网眼的质心排列识别格网模式 [5]，该方法仅考虑了道路网眼排列特征，忽略了道路网眼形态对识别结果的影响。Yang等运用区域增长算法对格网模式进行识别 [6]，该方法兼顾了道路网眼的形态与排列特征，但参数整合较为困难。田晶等计算了网眼的矩形度、凹凸度、排列一致度等特征，使用C4.5算法识别道路格网模式 [7]。巩现勇等计算了网眼的矩形状描述子、拐点垂直度、排列一致性、形状相似性等特征，使用关联规则分类算法识别道路格网模式 [8]。另一种是基于线状道路几何与拓扑关系的方法，如何亚坤等提出的利用网络空间向量剖分法识别城市道路网格网模式 [9] 等。

本文以道路网眼作为识别的主体，提出应用LightGBM识别城市道路网格网模式的方法。该方法仅依赖道路网几何数据，以描述道路网眼多边形自身及相邻关系的特征参数作为模型输入量，通过模型样本训练实现对道路网眼的自动分类，从而识别出城市道路网格网模式。

2. LightGBM原理

lightGBM是微软于2017年发布的基于决策树算法的梯度提升框架，是梯度提升决策树算法(Gradient Boosting Decision Tree, GBDT)在工程上的实现 [10]。针对传统GBDT框架在处理高维度、大样本情况时模型运行效率不高的问题，lightGBM采用了基于梯度的单边采样(Gradient-based One-Side Sampling, GOSS)和互斥特征捆绑(Exclusive Feature Bundling, EFB)方法进行了优化，具有准确率高、速度快、内存占用少、可并行化学习等优点。

LightGBM的内核是GBDT算法，该算法是机器学习方法中的一种集成方法，主要思想是迭代训练多个弱的分类回归树基模型，将多个基模型的结果进行线性加和，得到整个模型的最终输出结果，通过该算法，多个弱的基模型被集成为一个强学习器模型 [11]。算法示意图如图1所示。

Figure 1. Diagram of GBDT

图1. 梯度提升决策树示意图

3. 基于LightGBM的道路格网模式识别方法

应用LightGBM方法识别道路格网模式主要有以下三个方面的工作。一是合理选择描述网眼自身及相邻关系的特征参数，这些参数既要便于计算，又要全面准确地反映道路网眼空间特征；二是模型参数的确定及模型训练，设置合理的模型参数，选择合适的训练和测试样本，均可以提高模型识别精度；三是网眼判定阈值的确定，合理的阈值可以降低道路网眼的漏识率，从而比较准确地识别出道路格网模式。该方法的基本流程如图2所示。

Figure 2. Flowchart of street grid pattern recognition based on LightGBM

图2. 基于LightGBM的道路格网模式识别流程

3.1. 道路网眼特征参数计算

道路网眼是道路网纵横交错形成的最小闭合区块 [12]，在格网模式的道路网中，网眼具有如下特征：在几何形态上，网眼形状通常接近于矩形，且相邻之间往往具有类似的尺寸；在空间分布上，网眼具有一致的排列。本文通过矩形度 [13] 、平行度 [14] 描述网眼自身形态特征，通过主方向一致度、质心方向一致度、形状相似度 [6] 描述相邻网眼在空间排列和形态尺寸上的相互关系。

1) 矩形度(Rectangularity)，描述道路网眼形状与矩形的相似程度 [13]。计算公式如式(1)所示。

$\text{Rectangularity}=\frac{Area}{mbrArea}$ (1)

式中，Area为网眼多边形面积，mbrArea为网眼多边形最小外接矩形面积。

2) 平行度(Parallelism)，描述格网模式下组成网眼的两组道路的平行程度。计算公式如式(2)所示。

$\text{Parallelism}=\frac{Perimeter\left(mbr\right)}{Perimeter}$ (2)

式中，Perimeter(mbr)为网眼按面积量算的最小外接矩形周长，Perimeter为网眼多边形周长。

3) 主方向一致度(Main Direction Similarity, MDS)，描述相邻网眼主方向接近于平行或垂直的程度(网眼主方向定义为网眼最小外接矩形长边按顺时针方向偏离正北方向的角度，以十进制度为单位，取值范围为[0,180))。计算公式如式(3)所示。

$\text{MDS}=\frac{\left|\left|\left|Orient\left(A\right)-Orient\left(B\right)\right|-90\right|-45\right|}{45}$ (3)

式中，Orient(X)为网眼多边形X的主方向，式中已做归一化处理，取值范围为[0,1]。

4) 质心方向一致度(Centroid Direction Similarity, CDS)，描述相邻网眼质心连线方向与主方向接近于平行或垂直的程度(质心连线方向定义为网眼质心连线以逆时针方向偏离正东方向的角度，当偏离角度大于180度时则减去180度，取值范围为[0,180))。计算如公式(4)、(5)所示。

$\text{CDR}=\frac{\left|\alpha -Orient\left(A\right)\right|+\left|\alpha -Orient\left(B\right)\right|}{2}$ (4)

$\text{CDS}=\frac{\left|\left|\left|CDR-90\right|-45\right|-22.5\right|}{22.5}$ (5)

式中，α代表质心连线方向，Orient(X)为网眼多边形X的主方向。公式(4)为计算式，公式(5)为归一化处理公式，取值范围为[0,1]。

5) 形状相似度(Shape Similarity, SS)，描述相邻网眼质心重合时交集面积与并集面积的比值，示意图如图3所示。计算公式如式(6)所示。

Figure 3. Diagram of shape similarity

图3. 形状相似性示意图

$SS=\frac{Area\left(A\cap B\right)}{Area\left(A\cup B\right)}$ (6)

式中，A、B分别代表经移动后质心重叠的相邻网眼多边形。

以上5个指标描述了网眼自身形态及相邻网眼的相互关系特征，以这些指标为基础，计算道路网眼及一阶邻居网眼 [15] (即与该网眼相邻的所有网眼)的特征指标的最大值、平均值等统计量，构建道路格网模式识别的网眼参数组合作为模型的输入量，能够比较全面地反映网眼自身形态、相互关系及空间上下文环境，进而提高网眼识别率。详细参数解释如表1所示。

Table 1. The mesh parameter combination of road grid pattern recognition

表1. 道路格网模式识别网眼参数组合

注：表中邻接特指多边形以边相接的情况，不包括以点相接。

3.2. 模型参数确定方法

合理设置模型参数有利于提高LightGBM对网眼的识别精度。本文中，判断道路网眼是否为具有格网模式特征属于二分类问题，故将训练目标“objective”参数设定为“binary”；由于GOSS方法可以在训练时更关注从未被训练过的数据，减少了模型训练所需的数据量并兼顾了模型的准确度，将其设为提升方法“Boosting”的参数值；考虑到道路格网模式有时作为道路局部区域的模式特征出现，而AUC (Area Under the Curve) [16] 是样本数据分布不平衡时评价模型性能比较好的指标，将其设为模型性能评价指标“Metric”的参数值。

其他参数如控制模型调整幅度的learning_rate (学习率)，控制分类回归树形态的num_leaves (一棵树上的叶节点数)、max_depth (树的最大深度)、min_data_in_leaf (叶节点上的最少数据量)等，其取值组合对模型精度和效率有一定的影响，难以人工确定。本文采用贝叶斯优化 [17] 的方法对这些参数自动调整，从而找到合适的模型参数取值组合。本文确定的最终模型参数如下：

params = {

'objective': 'binary',

' boosting_type' : 'goss ',

'learning_rate': 0.12,

'num_leaves': 21,

'max_depth': 8,

'metric': {'l2', 'auc'},

'min_data_in_leaf': 10,

'subsample': 0.82,

'feature_fraction': 0.79,

}

3.3. 样本选取与模型训练

用于模型训练所选取的样本区域应该具有代表性，既要有一定数量的格网模式网眼，又要保证区域内网眼特征在形态和空间分布上的多样性。样本数据需进行如下处理：首先进行拓扑处理生成道路网眼多边形；然后根据3.1中确定的网眼参数组合计算参数值；最后对每一个网眼进行人工判定并添加标签，属于格网模式的设为1，否则为0。经过以上处理的样本数据才能输入模型进行训练。

本文采用五折验证策略 [18] 用于模型训练以防止过拟合(即模型在训练数据上表现好但在测试数据上表现差)，即将所有训练数据等分为五份，每次取其中四份用于训练模型，另一份用于测试模型，最后取五次评测中平均误差最小的作为最终训练好的预测模型。

3.4. 模型结果分类

将研究区非样本区域的道路网眼数据输入训练好的模型，得到的预测值为(0,1)范围内的小数，代表的是该道路网眼为格网模式网眼的概率。比较不同概率阈值设定下的识别结果，选择合适的概率作为阈值，即可对模型结果进行分类，从而识别出道路格网模式。本文经实验发现，对于属于典型道路格网模式的城市，阈值取0.2左右即可满足要求，对于道路格网模式作为局部特征出现的模式，需要取稍高的阈值以保证准确率。

4. 实验与分析

本文采用美国旧金山城区道路网数据作为道路格网模式识别的研究区。该区域内共有路段16,236条，生成道路网眼7496个，用于模型训练输入的样本区域有路段592条，网眼222个，呈格网模式的网眼112个。研究区域如图4所示，右侧小图为从研究区域红色框截取的样本区域，样本图中蓝色部分为格网模式的网眼，红色部分为非格网模式的网眼。

Figure 4. The street network of San Francisco and sample selection

图4. 旧金山道路网及样本选择

训练模型时判断道路网眼是否属于格网模式的各特征参数重要性如图5所示，可以看出，应用LightGBM方法识别道路网眼是否属于格网模式主要依赖的是形状相似度，其次是道路网眼本身的平行度和与其相邻网眼的矩形度，道路网眼的排列特征对结果也有一定的影响。

Figure 5. The importance statistics table of feature parameters input into LightGBM

图5. LightGBM输入特征参数重要性统计表

从实验结果可以看出，大部分格网模式的网眼被识别出来，包括一些属于格网模式但特征不够典型的网眼也被识别出来。图6为阈值取0.2时的识别效果，总的来看，LightGBM方法能够比较好的识别格网模式的道路网眼。实验中也有一些依据格式塔原则 [19] 的整体性判断应属于格网模式的网眼没有被识别出来，主要是由于这些网眼的形状、尺寸、面积与周围道路网眼不一致而导致的漏识别。

Figure 6. The road street pattern recognition result of San Francisco

图6. 旧金山道路格网模式识别结果

5. 结束语

本文通过分析格网模式下道路网眼的几何形态和空间分布特征，使用矩形度、平行度、主方向一致度、质心方向一致度、形状相似度等指标构建道路网眼特征参数组合作为模型输入值，将LightGBM应用于格网模式道路网眼的识别，经实验验证，该方法可以比较准确地识别出城市道路网格网模式。但由于城市道路网的多样性，一些属于格网模式但几何形态复杂的网眼还难以被识别出来。深入研究道路网眼的其他特征信息，并融合LightGBM和其他模式识别算法将能进一步提升道路格网模式识别的精度和效率。

基金项目

国家重点研发计划(2017YFB0503601、2017YFB0503502)；国家自然科学基金(41671448)；四川省重点研发计划(19ZDYF0839)。

NOTES

^*通讯作者。