归一化分割算法在路网划分中的敏感度分析

陶黎明， 卢守峰， 江勇东

(长沙理工大学 交通运输工程学院, 湖南 长沙 410114)

针对复杂的交通网络拓扑关系和现实交通荷载分布，路网的子区划分为交通管理与控制提供了思路。通过路网划分来提取系统内部具有强关联性的子区，服务于交通状态的把握和子区信号的控制，从而提高交通运行效率。目前，基于各种理论路网划分方法的研究取得了一些成果，但缺乏对于划分方法本身特性的客观认识，导致对其特性了解不全面和应用不充分。Walinchus[1]提出交通控制子区的概念以来，路网划分的相关研究一直备受关注。其中，对于各种划分方法的应用研究集中在交通信号控制子区[2-3]。在区域交通状态分析方面，Geroliminis[4-5]等人研究了路网平均密度与平均流量相关性，并提出了能反映区域交通网络状态特性的宏观基本图(macroscopic fundamental diagram，简称MFD)概念。利用实测数据创建宏观交通基本图已成为研究的热点。卢守峰[6]等人对利用线圈检测器数据和出租车GPS数据创建的宏观交通基本图进行了研究。Geroliminis[7-8]等人通过对实测数据和模拟数据创建宏观交通基本图进行研究，发现：交通网络中车辆密度的空间分布是影响MFD离散度和形状的关键因素。为了得到更准确的MFD， Ji[9]等人基于路网划分的思路，提出利用归一化分割(Normalized cut，简称为Ncut)方法进行路网划分，将交通网络划分为车辆密度分布均质性较高(即密度方差较小)的子区。

归一化分割属于谱聚类算法的一种，最早应用于图像的分割[10]。该方法通过相似度函数计算权重后建立Laplace矩阵，并通过求解系统特征函数进行划分对象的聚类[11]。在实际应用中，由于不同的相似度函数具有其自身的特性，聚类结果往往会依赖于相似度函数[12]。归一化分割算法应用于路段密度属性划分路网时，其相似函数对路网密度分布的变化不敏感，导致路网在不同密度分布时的划分结果都相同。为创建性能良好的MFD，作者拟对划分路网的归一化分割算法进行研究，对其相似函数利用惩罚系数法进行敏感度分析，为该算法的应用提供参考。

1 归一化分割算法简介

在归一化分割中，先将交通网络作为无向图G，路段作为节点。其中，每个节点i具有对应的密度di属性[9]。建立的邻接矩阵{a(i,j)} (只有0或1 2个值)代表的是每对路段之间的相邻关系。当a(i,j)=1时，表示路段i和j相连，反之亦然。为了保证路网的空间连接，将路段之间的有效值定为1，同时，定义路段i和j之间的权重相似度函数w(i,j)，其表达式为：

(1)

(2)

(3)

其中：Ncut(A,B)的最小化和Nassoc(A,B)的最大化2个目标可以被同时实现。两者遵循的约束为：

Nassoc(A,B)=2-Ncut(A,B)。

(4)

准确求解Ncut是一个多项式非确定性的问题，但可通过求解实值域上的特征值系统，有效逼近离散解。归一化分割的计算思想来自谱方法，其在划分城市交通信号控制网络小区中也得到应用[3]。归一化分割的步骤为：

1) 给定一个从运输网络中建立的无向图，并对连接路段的邻接矩阵设置权重w(i,j)，得到矩阵C，作为2个路段之间相似性的度量。

2) 建立节点权重的Laplace矩阵F(设对角矩阵D，对角线权重为行或列权重的和F=D-C)。

3) 对矩阵系统D-0.5FD-0.5求解特征值，选取第二小特征值，并求取对应特征向量。

4) 从小到大对特征向量进行排序，根据向量是否大于0将路网划分为2部分。

在归一化分割过程中，为了评估和比较不同划分后的聚类情况，引入评价指标[8]：

(5)

式中：K为区域全部子区的数目；NA和NB均为子区内路段的数量。

此外，评估簇A内的路段聚类情况的计算公式为：

(6)

NSNK(A,B)=min{NSK(A,M)|M∈

Neighbor(A)}。

(7)

其中：Neighbor(A)为空间上与集群A相邻的子区。在该指标中，NSK(A,A)表示的是集群内的相似度，NSK(A,B)表示的是不同集群之间的相似度。如果2个集群在空间上不相邻，即使它们的路段车道密度很接近，也会被成功分区，因此，只要测量该子区与其相邻子区之间的相似度。又由于A可能有多个相邻子区，因此选择与A最相似的一个进行对比计算。整体分区的评价利用全部子区NSK(A)的平均值ANSK来评估。

(8)

式中：C为划分的子区集合；K为子区的数量。

ANSK越小，表明划分越理想。NSK评估度量可以等价地用集群中的路段车道密度方差和平均密度来表示，其计算式为：

NSK(A,B) =var(A)+var(B)+

(uA-uB)2。

(9)

式中：uA为子区A的路段平均密度；uB为子区B的路段平均密度。

同时，可以得到：

(10)

在式(10)中，相邻不同子区的平均密度差越大，评价的子区内部方差越小，则NSK越小，表明该子区划分效果越好。由于一个具有较小方差和NSK的集群可能伴随着一个具有较大方差和NSK的相邻子区，因此，整区划分的评价用NSK的平均值来评估。也可以使用集群的总方差来评估整区划分的质量，其计算式为：

(11)

归一化分割算法的优势有：①归一化分割是基于图论的分割算法，图像的线条和色彩与路网的路段荷载具有相同的关系特征；②该分割方法可以避免划分出大小迥异的路段集群，同时，可以产生节点规格相近的子区；③它可以实现感知性的编组，即利用图形最主要、最明显的成分对全局进行分割提取；④可保证划分的路段集群在空间上紧凑连续；⑤该分割算法在路网划分中可以有效实现。

2 敏感度分析

2.1 惩罚系数量级对划分结果的影响

为了研究归一化分割对于路网密度变化的敏感性，本研究基于浙江绍兴柯桥城区道路的车牌照数据进行了路网划分试验。由CUPRITE模型[13]计算得到路段密度，其单位为辆/m。该模型在道路上、下游车辆数据统计上已得到深入验证，并被广泛应用。初始路网和一次初始划分的结果如图1所示。

图1 初始路网和一次划分结果Fig. 1 Initial road network and first division result

初始路网由39个交叉口和62条路段构成，区域面积约7.36 km2。将1 d中6∶10-21∶50的时段取10 min为间隔，提取了94个时间间隔，并基于密度方差最大的第70个时段(17∶40-17∶50)路网密度进行了一次分割。对所有时间段进行划分后，发现94次划分结果完全相同。但1 d中的不同时段，路网的道路密度方差是有明显变化的，如图2所示。

图2 路网密度方差与时间的变化Fig. 2 The change of network density with time

对归一化分割中的相似度函数添加了惩罚系数α，将相邻路段相似度权重w(i,j)设计为 exp(-α(di-dj)2),并通过调整其数量级，对划分结果进行了研究。最初划分中的密度单位取辆/m，(di-dj)2的数量级为10-4。通过依次调整α，将α设为100～104，当α=103，即α(di-dj)2的数量级为10-1时，划分结果出现了变化,如图3所示。

图3中，横坐标代表94个时间段，纵坐标为路段编号，白色和黑色表示对应编号隶属于的不同子区。比较不同α数量级下的划分效果，可以发现：当相似度函数的量级过小时，其对路网密度的分布不敏感，划分结果固定。同时，当路网划分结果出现变化时，密度方差较大的早、晚高峰时段子区的临界路段波动很大，划分效果对密度分布变化的敏感度加强。表明：归一化分割的划分效果对权重指数的数量级存在依赖。为了进一步对比不同α量级下相似函数对密度分布的敏感性，验证其指数对数量级的依赖，同样，基于第70个时段下的路网密度，进行了具体划分并计算了相应评价指标。不同α数量级下的路网具体划分如图4所示。

图3 不同α数量级下的路段子区分布Fig. 3 The distribution maps of the road section under different orders of magnitude alpha

从图4中可以看出，不同α数量级下的划分结果均不同。同时，计算得到划分子区的评价指标见表1。

图4 不同α数量级下的路网具体划分Fig. 4 Specific division diagrams of road network with different orders of magnitude alpha

惩罚系数车辆密度平均值/(辆·m-1)方差/(辆2·m-2)子区相似度路段数/条总方差/(辆2·m-2)相似度平均值100,101,102 (子区1)0.039 1 3.25×10-40.928 9 330.020 320.936 5 100,101,102 (子区2)0.032 4 3.31×10-40.944 0 29--103 (子区1)0.039 2 3.35×10-40.958 2 320.020 290.935 6 103 (子区2)0.032 5 3.19×10-40.913 0 30--104 (子区1)0.038 9 3.02×10-40.754 2 480.019 160.793 0 104 (子区2)0.026 0 3.33×10-40.831 7 14--

从表1中可以看出，当划分结果出现变化后，随着α数量级的增加，子区内路段的密度、方差、总方差及相似度平均值均降低了。划分效果的优化表明：归一化分割的相似函数对路网中路段密度的分布敏感度提高了，验证了其划分结果对相似度函数的指数量级存在依赖。这对于归一化分割算法在不同应用中具有实际参考价值。

2.2 相似函数图像分析

为了分析权重对相似函数图形的影响，α取100,103,105和107, 分别绘制了函数exp(-αx2)的图像，如图5所示。

从图5中可以看出，归一化分割算法的相似度函数在初始α=100时，其函数在变量较小时斜率绝对值过小，对于变量的变化不敏感，导致其在划分应用中对于不同密度分布情况结果相同。但随着惩罚系数量级的增加，函数图像逐渐变窄变陡，变量对应的斜率绝对值变大，对不同变量的感知力增强，使得不同密度方差下的子区划分产生了差异。当α=107时，函数图像仅在0附近很小的区间有值，其他均趋于0。这与实际试验中利用Matlab求解矩阵系统特征向量时出现无效值错误相吻合。因此，在应用归一化分割算法时，其划分结果对相似函数的指数量级存在着依赖。量级过小，会导致其对划分对象属性变化不敏感；量级过大，会带来求解困难。经试验验证，在MFD创建的路网划分应用中，其相似度函数的指数-α(di-dj)2的整体量级控制在100到101比较合适，即惩罚系数α取104～105。

图5 exp(-αx2)函数图像Fig. 5 The image of exp(-αx2)function

2.3 宏观交通基本图分析

考虑到归一化分割算法在MFD创建中应用的有效性[9]，对其划分的第70个时段的路网子区进行了宏观基本图的分析。路网划分前、后MFD的对比如图6所示。

图6 α取104时，划分前、后MFD的对比Fig. 6 The MFD contrast of the network before and after the partition

从图6中可以看出，归一化分割后各子区的最大流量是不同的。该结论为精细化分析交通路网运行状况和交通管控措施提供了依据。

3 结论

由于归一化分割算法可以将路网划分为密度分布均质性更高的子区，提高宏观基本图的准确性，但划分敏感度在相似度函数的指数量级上存在依赖。因此，本研究通过惩罚系数法，对归一化分割算法进行了不同指数量级下的敏感度分析，通过比较划分后子区路网的评价指标，验证了数量级会对划分结果产生重要影响。同时，对不同指数量级产生敏感度变化影响的原因进行了函数曲线分析，表明了其产生影响的原因。基于归一化分割算法在实际路网划分应用中的有效性，以及其相似函数的敏感度特点，提出：在实际应用中，应根据划分目标和划分对象的属性，合理控制其相似函数的指数量级。