基于交通指数聚类的路网区域动态划分

侯军军， 龙佰超， 王洪钰， 肖建力

（上海理工大学 光电信息与计算机工程学院，上海 200093）

现有的交通状态预报方法通常以较小空间尺度的路段作为研究对象。例如，高德地图和百度地图显示的交通状态就是以路段的不同颜色来表示。然而，在某些情形下，大空间尺度的路网交通状态预报往往更为重要，特别是对宏观路网区域交通状态的预报。例如，假设需要选择一个交通状态良好的区域举办一场演唱会，选择徐家汇还是人民广场区域，此时，需要对区域的交通状态进行评价。然而，对区域交通状态进行评价，首先必须产生路网区域。因此，本文主要关注路网区域划分方法的研究。

早期的城市路网区域划分主要根据行政区域及土地性质等因素来进行[1]。该方法主要用于研究区域的演变及其空间格局的变化，其特点是将乡镇街道的变化等因素融入路网区域划分的研究中。近年来，路网交通状态的预报对路网区域划分的目标提出了更高的要求，需要进行路网区域划分后得到的区域尽量能够反映本区域的交通特性，如果仍然基于之前的思路进行划分，显然已无法满足现代路网区域划分的要求[2]。国内外学者对此展开了深入的研究。

目前，国内学者对城市路网区域划分的研究，大体上可以分为两种思路：一种是以路网内交叉口的交通特性作为划分标准，将交通特性相近的交叉路口划分为同一个交通区域，这种路网划分方法称为聚类分析方法[3]；第二种是考虑交通路网中所有路段的交叉口，再通过已经规定好的搜索规则，对符合搜索规则的交叉口路段统一考虑后划入同一个区域，这种路网划分方法称为遍历搜寻法[4]。Moore等[5]提出两步划分法，将路网划分分成两步：初次划分时依据交叉路口的流量大小以及信号控制参数作为划分的标准，通过聚类分析完成初次的区域划分；然后加入最大绿波带优化模型，并以信号配时优化为目标，在初次划分的结果上对路网区域实现二次划分。Geroliminis等[6]提出了宏观基本图的概念，通过应用示例数据区交通流进行数据分析，发现城市路网中均存在“回滞环”的现象，即宏观基本图客观存在且具有不随时间变化的共性，这为城市路网区域划分提供了新的研究思路。

总体来看，现有的路网区域划分方法的研究还是不够成熟，不能够适应现代路网区域划分的要求。为此，本文提出了基于交通指数聚类的路网区域动态划分方法。为验证城市路网区域划分方法的性能，采用基于k-means++聚类算法[7]的路网区域划分方法进行区域划分，并与其他聚类方法进行对比。结果表明，本文提出的路网区域划分方法的精度要优于其他对比方法，且具有良好的稳定性。

1 城市路网区域动态划分方法

图1呈现了基于聚类的路网区域划分方法的流程，其具体步骤为：第一步，对整个城市区域进行网格划分，路网中的路段被网格切分成不同的子路段，每个子路段都从属于某个特定的网格；第二步，计算每个网格的交通指数；第三步，对每个网格提取特征，建立样本特征矩阵；第四步，对样本特征矩阵进行聚类，得到初始聚类标签；第五步，对奇异网格的标签进行修正，得到网格的最终标签，同时对面积过小的区域进行合并；最后，将具有相同标签的网格组成一个路网区域，对城市路网区域划分的结果进行可视化，得到最终的划分结果。

图1 路网区域动态划分方法流程Fig.1 Flowchart of the dynamic division method of traffic road network area

1.1 地图网格划分

本文提出的路网区域动态划分方法，其主要思路是先将整个路网区域划分成相同大小的网格，然后对网格进行聚类，从而得到路网区域。要实现这一想法，首先需要对整个城市区域进行网格划分。先选定整个城市的路网区域，该区域为一个矩形区域。然后，将其划分为N×N的网格，其中，N为矩形区域的长或宽的等分数且N为正整数。在本文的研究中，将整个上海区域划分成50×50的网格。自然地，一条长的路段会被网格切分成不同的子路段，每个子路段将从属于一个唯一的网格。得到网格后，在接下来的小节中将为每个网格计算交通指数。

1.2 网格交通指数计算

交通畅通指数[8]被定义为在给定时间段内，城市路网或区域的总体畅通程度的相对数，它是一个无量纲的量。交通畅通指数的区间为[0，100]，数值大小与畅通程度成正比，即数值越大表示状态越畅通，数值越小则越拥堵[9]。本文将交通畅通指数简称为交通指数。

一个路网区域的交通指数可由式（1）计算得到，即

式中：TFI表示一个网格的交通指数；i代表当前路网区域中的第i条子路段；r代表当前区域属于第r种路网；t代表当前时间属于第t个时间段；vi为路段实际交通流速度；vfr为不同路网下的路段的自由流车速，根据路网为快速路、地面主干道、次干道、支路以及高速公路取不同的值；li为路段i的里程长度；ki为路段的车道数；wt为时间权重系数，按高峰时段和平峰时段取不同的权重；wr为路网权重系数，根据路网属于快速路、地面主干道、地面次干道、地面支路、高速公路取不同的权重。

1.3 网格特征提取

为了后续对网格进行聚类，必须先对每个网格进行特征提取。可以由网格连续一段时间内的交通指数以及网格的坐标来构造该网格的特征向量。例如，取一个小时内网格的交通指数，由于指数的计算周期是10 min/次，即一共取6组交通指数加入到网格的特征向量中。对于第i个网格，其特征向量可以表示为

式中：fi表示第i个网格的特征向量；（x,y）表示第i个网格的坐标；TFIi,1表示第i个网格的第1个计算周期的交通指数，其余的5个交通指数以此类推。

对所有网格均作类似处理，可以得到由所有网格的特征向量组成的样本特征矩阵。由于本文中路网划分是按照50×50来进行划分的，即一共有2 500个网格。于是，样本特征矩阵可表示为

可以将样本特征矩阵F表示为列向量的形式，即有

1.4 样本特征矩阵聚类

a. 初始聚类。

得到样本特征矩阵后，需要对其进行聚类，从而产生初始的聚类标签。一些常见的聚类算法都可以用来执行聚类任务，例如，k-means聚类算法[10]、k-means++聚类算法、Birch聚类算法[11]和AGNES聚类算法[12]等。本文采用k-means++聚类算法进行样本特征矩阵的聚类。

在k-means++聚类算法中，数据点与聚类中心之间的最近距离用D(x)表示，其中µo(o=1,2,···,n)表示n个聚类中心点，D(x)的具体计算公式[13]如下：G={g1,g2,···,gk}，则聚类中心的数学表达式可以表示为[13]

k-means++聚类算法在聚类中心点的选取过程中引入了概率的思想：将每一个被选中的样本数据点概率与距其最近的已选中心点的距离相互联系，这样距离越大被选中的概率就越大。选取好k-means++聚类中心点后，还需要对选定的聚类中心点进行不断更新，直到聚类中心点不再发生变化。假定类别数为k，则聚类中心G可以表示为

式中：gk表示第k类样本簇的中心点；|Gk|表示第k类样本簇的样本总数；Ak表示第k类样本簇的样本集合；xi表示第k类样本簇的第i个样本。kmeans++聚类算法的具体步骤如下：

步骤1从输入的样本特征数据F={x1,x2,···,xn}中随机选择一个数据点作为第一个聚类中心点µ1；

步骤2对于数据点xi，计算数据点与第一个聚类中心点的最近距离；

步骤3选择新的数据点作为新的聚类中心点，其中选取的原则为D（x）中距离较大的点，其被选为聚类中心点的概率较大；

步骤4重复上述步骤2和步骤3，选出k个聚类中心点，然后对其更新，直到满足所有条件，输出聚类标签。

通过k-means++聚类算法对样本特征矩阵进行初始的聚类后，可以得到网格的聚类标签。图1（b）为网格数为10、类别数为6的带有聚类标签的可视化效果图，数字代表每个小网格的聚类标签。注意，该图只是一个示意图，为给读者一个直观的展示。

b. 奇异网格标签的修正。

通过初始聚类得到聚类标签，然后对具有相同类别标签的网格着上同一种颜色，得到初始聚类的可视化结果图，如图1（c）所示。为了更清楚地观察到初始聚类可视化结果图中存在的奇异网格，对图1（c）进行局部放大，结果如图1（d）所示。对其中存在的部分奇异网格用红色方框标识出来。所谓奇异网格是指其标签（即颜色）与周围邻域内网格的绝大多数标签存在明显差异的网格。奇异网格的标签可能是错误的，因此，需要采用正确的方法对奇异网格的标签进行修正。

图1（d）展示了中心网格的四连通和八连通区域内的奇异网格。可以看到奇异网格与四连通和八连通区域内绝大多数网格的颜色明显不同。为便于后续论述，先给出四连通与八连通区域的基本概念。

根据数字图像处理[14]中的相关理论，四连通区域是指处于中心网格上、下、左、右，紧邻的4个网格区域，如图2（a）所示。共有4个方向，所以称为四连通区域，又称四邻域。假设中心网格p的坐标为（x,y），则四连通数学含义可定义为

同理，八连通区域，是指在中心网格的上、下、左、右、左上、右上、左下、右下，是紧邻的网格和斜向相邻的网格区域组成的全体，共8个方向，所以称之为八连通区域或八邻域，如图2（b）所示。假设中心网格p的坐标为（x,y），则八连通数学含义可定义为

图2 奇异网格示意图Fig.2 Examples of singular grids

本文提出一种基于八连通多数投票的奇异网格标签修正方法，其具体步骤如下：

步骤1输入初始聚类标签；

步骤2判断在中心网格的八连通区域中是否存在奇异网格，如果存在奇异网格，则将奇异网格聚类标签修正为八邻域内数目最多的标签，同时中心网格右移一个网格，直到所有奇异网格的聚类标签都得到修正，否则重复步骤1和步骤2；

步骤3输出修正后的聚类标签。

经过基于八连通多数投票的奇异网格标签修正后，即可得到初始的路网区域划分，观察各个区域，一旦发现某个区域的面积过小，且其颜色与周围面积较大区域的颜色相近，则将该区域进行合并。

1.5 产生路网区域

对于上述步骤得到的区域，还需要用轮廓线进行标识，具体方法为：通过比较各网格的聚类标签来画出城市路网区域的轮廓线。首先确定轮廓线起点，接下来如果两个聚类标签不相同就在两个聚类标签中间画一条直线，相同则不作处理，依次迭代下去，直到将所有聚类簇的轮廓线都画出来为止。最终得到城市路网区域划分结果，如图1（f）所示。

2 相关实验

2.1 数据来源

本文实验部分的GPS数据来源于上海市交通信息中心，时间为2012年2月1日，一天24 h的GPS数据。

2.2 交通指数颜色映射

为了后续验证路网区域划分方法的精度，将网格的交通指数映射为不同的颜色，颜色映射的规则为：将交通指数由0到100分别映射为深红到深绿色，颜色会随着交通指数数值由小到大呈现出不断渐变的过程[15-16]。其中，某些缺少交通指数的网格则用白色表示，效果图如图3所示。

图3 交通指数颜色映射图Fig.3 Map generated by mapping the traffic indexes into the color space

2.3 聚类算法精度评价指标

将城市路网区域划分结果图1（f）叠加到图3中得到图4。在图4中红色线段所框出来的区域中，组成区域的网格主要由两部分组成，主基色网格以及辅基色网格。所谓主基色网格是指一个区域内颜色接近且网格数目占绝大多数的网格，辅基色网格则是指区域内除了主基色网格之外的其他颜色网格。一般而言，辅基色网格的颜色与主基色网格颜色不同，且其网格数量占该区域的少数。区域面积则可由该区域内的网格总数来表示，也即主基色网格数量和辅基色网格数量的总和。

图4 路网区域及区域中的主基色网格和辅基色网格Fig. 4 Traffic road network areas and the major color grids and minor color grids in these areas

为了评价不同城市路网区域划分方法的精度，创新性地提出了一个衡量某个区域划分精度的指标P，其计算公式为

式中：P表示当前区域的划分精度，P值越小表示划分精度越好，P值越大表示划分精度越不理想；H表示路网区域中的主基色网格数量；hi为第i种辅基色网格的数目，n为辅基色颜色的总数，表示路网区域中辅基色网格总数；S表示当前区域的面积大小，即当前区域内网格的总数。

为了衡量整个路网划分的精度，可以计算P的平均值Pave，即有

式中：N表示城市路网中的区域总数；Pk表示第k个区域的划分精度；Pave指标用来衡量整个城市路网划分的平均精度。

2.4 实验验证

实验部分根据如下思路进行组织：实验1分别对不同的路网区域划分方法的精度进行定性和定量分析，实验2对不同的路网区域划分方法的稳定性进行验证。

将k-means++聚类算法与k-means聚类算法、AGNES聚类算法以及Birch聚类算法4种方法对比验证。k-means聚类算法流程如下：首先设置聚类的类别数k，然后从样本数据中随机选取k个样本作为初始的聚类中心，通过计算聚类中心与样本数据点之间的距离，把每个数据点分配到距离它最近的聚类中心；再将同一类别的所有样本数据特征取平均值，并将平均后所得的数据点作为新的聚类中心；最后，重复上述步骤直到聚类中心满足终止条件，输出聚类标签。AGNES聚类算法采取自下而上的聚类思想。首先将样本数据作为一个聚类簇，然后根据一定的相似性度量将这些聚类簇逐渐合并成一个大的聚类簇，直到达到初始设定的类别数为止。Birch聚类算法引入聚类特征和聚类特征树两个新的概念来概括对聚类的描述。其中，聚类特征树概括了聚类中的有用信息，占用的空间比原来的数据集要小，这节约了内存空间，提升了Birch算法在大型数据集上的聚类速度[17-20]。

a.方法精度验证。

分别选取以下4个时间段：04:00—04:20、17:40—18:00、08:00—08:20、00:40—01:00，通过定性分析和定量计算验证基于k-means++聚类算法的路网区域划分方法的精度。

定性分析，以图5（a）～（d）的结果，基于kmeans++聚类算法的路网区域划分方法的精度，对其展开定性分析。通过观察图5（a）～（d）发现各个路网区域中网格的颜色一致性较强，这表明路网区域划分的精度较高。

图5 k-means++聚类算法的精度验证Fig.5 Accuracy verification of k-means++ clustering algorithm

定量分析，通过对城市路网的各区域分别计算精度性能评价指标P，然后计算P的均值Pave来评价路网区域划分方法的精度，Pave值越小精度越高。选取的交通指数时间段为17:40—18:00。图6（a）～（d）分别为基于k-means++，k-means，AGNES，Birch聚类算法的路网区域划分方法的划分结果，由图6（a）～（d）分别计算各方法划分结果的Pave值，并总结于表1中。由表1可知，基于k-means++聚类算法的路网区域划分方法精度最高。

表1 不同方法的Pave值Tab.1 Pave values of different methods

图6 不同聚类算法对比图Fig. 6 Comparison of different clustering algorithms

b. 方法稳定性验证。

如图7（a）～（i）所示，对基于k-means++聚类算法的路网区域划分方法在不同时间段上的稳定性进行验证，选取的9个时间段分别是：12:00—12:20、13:00—13:20、14:00—14:20、15:00—15:20、16:00—16:20、17:00—17:20、18:00—18:20、19:00—19:20和20:00—20:20。纵观整个路网区域，划分结果会随着不同时间段的交通指数发生一定的变化。但是，总体上同一区域的划分结果不会发生太大的空间区域变化。实验结果证实了基于k-means++聚类算法的路网区域划分方法其稳定性较为良好。

图7 k-means++聚类算法稳定性验证Fig.7 Stability verification of k-means++ clustering algorithm

分别在9个不同时间段的路网区域划分结果图中选取5个空间地理位置接近的区域，通过观察这5个区域在不同时间段上形状的变化，来定性分析算法的稳定性。如图7（a）～（i）所示，选取的区域为：区域No.1、区域No.2、区域No.3、区域No.4和区域No.5，采用不同颜色的轮廓线对5个区域进行标注。通过对比9个时间段上的城市路网区域划分的结果，发现在不同的时间段上，5个区域面积大小、划分区域的路网拓扑结构没有发生较大变化。这从局部细节上反映了基于kmeans++聚类算法的路网区域划分方法的稳定性较为良好。

3 结论

提出了一种基于交通指数聚类的路网区域动态划分方法，该方法能够对城市路网区域实现动态划分，并具有良好的划分精度和稳定性。本文创新性地提出了衡量不同城市路网区域划分方法的精度衡量指标，使对路网区域划分方法的精度进行定量分析成为可能。通过将基于k-means++聚类算法的路网区域划分方法与其他3种方法进行实验对比，实验结果表明，基于k-means++聚类算法的路网区域划分方法相比于其他3种方法具有更好的划分精度和稳定性。在今后的研究中，可以将性能更加优越的聚类算法引入到城市路网区域划分中，进一步提高路网区域划分的性能。