CN108320511A - 基于谱聚类的城市道路交通子区划分方法 - Google Patents

Abstract

本发明提供一种基于谱聚类的城市道路交通子区划分方法，建立路网无向图，计算路网密度拉普拉斯矩阵L；根据k个特征值对应的特征向量v₁,…,v_k构建聚类基础矩阵，并实施K均值聚类算法获得k个簇；构成初始的子区；对孤立点随机合并入邻接的子区内，得到当前的子区总数；通过偏差检测识别异常值点，并通过边界调整解决最优的异常点归属问题；通过子区内外的相似度评估以及子区拆分、合并前后的相似度变化分析，对子区方案进行迭代优化，最终获得子区内节点关联度相似性最大、子区间差异性最大的道路交通路网划分方案。该方法根据节点关联度的相似特征高效、稳定地获得交通道路网络划分方案，且最大程度保障子区间的特征差异性与子区内部的特征相似性。

Description

基于谱聚类的城市道路交通子区划分方法

技术领域

本发明涉及一种基于谱聚类的城市道路交通子区划分方法。

背景技术

城市道路交通网络是具有随机特性的复杂网络，将关系紧密的交叉口和路段的集合组成子区域，并针对各子区的特征实施控制、诱导、管理、规划，能够降低道路交通系统复杂性，甚至从宏观层面达到协调优化的效果。在交通信号控制领域，动态的控制子区划分能够提高信号协同控制的稳定性和可靠性；在交通诱导领域，子区的划分为协同诱导效果的发挥提供支撑；在交通规划、交通安全分析等领域，则以静态子区划分为主，考虑土地利用、人口、经济等宏观特征。

目前在区域划分领域，谱图划分理论逐步得到应用。采用这种方法划分得到的小区内部交通流特征具有较高相似性，而各小区之间具有较大的差异性，且在划分空间上具有连续性的优点。目前普遍应用的二分谱聚类的算法，基于Laplacian非零次小特征值及其特征向量聚类得出图形分割结果，没有充分利用包含有用划分信息的其他特征向量，并且在需要分割出多个子图时必须迭代使用，具有信息丢失量大、计算效率低、不稳定的缺陷。

上述问题是在城市道路交通子区划分过程中应当予以考虑并解决的问题。

发明内容

本发明的目的是提供一种基于谱聚类的城市道路交通子区划分方法，通过多重约束条件与相似度的迭代评估，获得子区内相似度最大、子区间差异性最大的最优解，解决现有技术中存在的二分谱聚类的算法，在基于Laplacian非零次小特征值及其特征向量聚类得出图形分割结果时，没有充分利用包含有用划分信息的其他特征向量，并且在需要分割出多个子图时必须迭代使用，而出现的信息丢失量大、计算效率低、不稳定的缺陷的问题。

本发明的技术解决方案是：

一种基于谱聚类的城市道路交通子区划分方法，包括以下步骤：

S1、基于路网交叉口与路段的拓扑结构以及各节点的交通特征数据，建立路网无向图G＝(V,E)，计算路网密度拉普拉斯矩阵L；

S2、计算拉普拉斯矩阵L的除0以外前k个最小的特征值及其特征向量，其中k的初值为2；根据k个特征值对应的特征向量v1,…,vk构建聚类基础矩阵H＝[v1,…,vk]，对矩阵H的行向量实施K均值聚类算法，获得k个簇；运用方差分析检验方法检验k个群组内的交通特征关联度X，若存在显著差异，则进入步骤S3；否则，k＝k+1，重复步骤S2；

S3、由簇内的交叉口以及交叉口间存在的路段构成初始的子区；若存在孤立点，即子区内仅包含一个节点编号，则将该子区随机合并入邻接的子区内，根据合并情况统计当前的子区总数N；

S4、通过偏差检测识别异常值点，并通过边界调整解决最优的异常点归属问题；通过子区内外的相似度评估以及子区拆分、合并前后的相似度变化分析，对子区方案进行迭代优化，最终获得子区内节点关联度相似性最大、子区间差异性最大的道路交通路网划分方案。

进一步地，步骤S4具体为，

S41、若i≤N，则根据子区交叉口或路段交通特征关联度X，检测初始划分方案内各子区内关联度偏差，若存在异常值点，则转入S42，否则转入S43；其中i为子区编号，初值为1；若i＞N，结束本流程；

S42、根据路网拓扑识别子区i的相邻子区集I＝{i1,i2…ip}，其中ip为相邻子区的编号，p为相邻子区个数，p∈[1,N-1]；检测异常值点映射的节点或路段是否位于子区i边界，若是，则将异常点映射的节点或路段划入相邻区域，求解使得成立的边界调整方案，Var(X)为子区内关联度X方差，q为参与边界调整的子区数，q∈[2,p]；若异常值点映射的节点或路段不在子区边界上，则将异常值点作为子区内的特殊点标记，不参与后续的处理；

S43、判断该子区i是否为初次划分，若是，进入步骤S44；否则，进入步骤S46；

S44、计算子区内除去特殊标记点以外的点间关联度X的相似度NS(X_i)；

S45、若NS(X_i)≥1，检测子区i内的交叉口数是否低于阈值NT；若成立则将子区i与相邻子区合并，求解成立的合并方案，其中X_c'为合并后的i原相邻子区的内部关联度，i＝i+1，回S41；若i内的交叉口数不低于阈值NT，则回S1；

若NS(X_i)＜1，i＝i+1，回S41；

S46、计算子区内除去特殊标记点以外的点间关联度X的相似度NS(X_i)，若NS(X_i)≥1，则恢复i区划分前的方案；否则，检测子区i内的交叉口数是否低于阈值NT；

若成立则将子区i与相邻子区合并，求解成立的合并方案，进S47；否则，直接进S47；

S47、计算子区i与路网内其他子区的组间相似度并比较在子区i从原区域划分出来前，其归属区域与其他子区的组间相似度的变化趋势，若降低，则i＝i+1，回S41；否则，恢复i区划分前的方案。

进一步地，步骤S41中，关联度偏差检测方式为：若则将xi作为子区内的离群点；其中，u为xi均值，sd为标准差。

进一步地，步骤S44、S46中，计算子区内除去特殊标记点以外的点间关联度X的相似度其中，ip为相邻子区的编号，ui、为子区i、ip内关联度X数据均值，Var(Xi)、Var(Xip)分别为子区i、ip内关联度X方差。

本发明的有益效果是：该种基于谱聚类的城市道路交通子区划分方法，是一种高效稳定的谱聚类交通子区划分方法，能够减少子区划分迭代过程，同时设置子区划分优化调整机制，构建组内差异评价模型，区域划分时兼顾子区内部特征相似性以及子区间的特征差异性，通过组内数据统计以及多回合的组内差异评价，以多重分割或合并的手段优化子区划分方案，最终真正达到子区内交通流特征相似性最大、子区间差异性最大的划分效果。本发明根据节点关联度的相似特征高效、稳定地获得交通道路网络划分方案，且最大程度保障子区间的特征差异性与子区内部的特征相似性。

附图说明

图1是本发明实施例基于谱聚类的城市道路交通子区划分方法的流程示意图。

图2是实施例中路网拓扑结构的示意图。

图3是实施例中分区方案及对应的子区交通安全等级的示意图。

具体实施方式

下面结合附图详细说明本发明的优选实施例。

实施例

一种基于谱聚类的城市道路交通子区划分方法，包括以下步骤：

S1、基于路网交叉口与路段的拓扑结构以及各节点的交通特征数据，建立路网无向图G＝(V,E)，计算路网密度拉普拉斯矩阵L。

S2、计算拉普拉斯矩阵L的除0以外前k个最小的特征值及其特征向量，其中k的初值为2；根据k个特征值对应的特征向量v1,…,vk构建聚类基础矩阵H＝[v1,…,vk]，对矩阵H的行向量实施K均值聚类算法，获得k个簇；

运用方差分析检验方法检验k个群组内的交通特征关联度X，检验水准通常为0.05，若存在显著差异，则进入步骤S3；否则，k＝k+1，重复步骤S2。

S3、由簇内的交叉口以及交叉口间存在的路段构成初始的子区；若存在孤立点，即子区内仅包含一个节点编号，则将该子区随机合并入邻接的子区内，根据合并情况统计当前的子区总数N。

S4、通过偏差检测识别异常值点，并通过边界调整解决最优的异常点归属问题；通过子区内外的相似度评估以及子区拆分、合并前后的相似度变化分析，对子区方案进行迭代优化，最终获得子区内节点关联度相似性最大、子区间差异性最大的道路交通路网划分方案。

S41、若i≤N，则根据子区交叉口或路段交通特征关联度X，检测初始划分方案内各子区内关联度偏差，若存在异常值点，则转入S42，否则转入S43；其中i为子区编号，初值为1；若i＞N，结束本流程。

步骤S41中，关联度偏差检测方式为：若则将xi作为子区内的离群点；其中，u为xi均值，sd为标准差。

S42、根据路网拓扑识别子区i的相邻子区集I＝{i₁,i₂…i_p}，其中i_p为相邻子区的编号，p为相邻子区个数，p∈[1,N-1]；检测异常值点映射的节点或路段是否位于子区i边界，若是，则将异常点映射的节点或路段划入相邻区域，求解使得成立的边界调整方案；并计算边界调整后的Var(X)为子区内关联度X方差，q为参与边界调整的子区数，q∈[2,p]；若异常值点映射的节点或路段不在子区边界上，则将异常值点作为子区内的特殊点标记，不参与后续的组内相似度评估。

S43、判断该子区i是否为初次划分，若是，进S44；否则，进S46。

S44、计算子区内除去特殊标记点以外的点间关联度X的相似度其中u为子区内X数据均值，其他参数如上所示。

S45、若NS(X_i)≥1，检测子区i内的交叉口数是否低于阈值NT。

若成立则将子区i与相邻子区合并，求解成立的合并方案，其中X_c'为合并后的i原相邻子区的内部关联度，i＝i+1，回S41；若i内的交叉口数不低于阈值NT，则回S1；

若NS(X_i)＜1，i＝i+1，回S41；

S46、计算NS(X_i)，若NS(X_i)≥1，则恢复i区划分前的方案；否则，检测子区i内的交叉口数是否低于阈值NT；

若成立则将子区i与相邻子区合并，求解成立的合并方案，

进S47；否则，直接进S47。

S47、计算子区i与路网内其他子区的组间相似度并比较在子区i从原区域划分出来前，其归属区域与其他子区的组间相似度的变化趋势，若降低，则i＝i+1，回S41；否则，恢复i区划分前的方案。

某城市的中心城区路网作为划分区域，路网拓扑结构如图2所示，该区域范围内包含99个交叉口并对其编号。从各路段布设的微波车检器获取交通流数据。

实施例中以路段交通密度作为交叉口间的关联度X，子区划分的目的用于道路交通宏观安全分析。构建无向图G，计算对应的路网密度拉普拉斯矩阵L，由于拉普拉斯矩阵中所有的行和列和都为0，因此得到路网密度拉普拉斯矩阵L对角线上的元素λ_ii即为矩阵的度，路网密度拉普拉斯矩阵L如下表1所示：

表1实施例的路网密度拉普拉斯矩阵L

按上述流程得到的子区划分方案，同时采用另两种现有常用的子区划分方法，获得了另外两种子区划分方案：一种划分方案为CT划分，即按街道进行子区划分，划分出44个子区域(现有方案2)；另一种划分方法为TAZ划分，即采用交通规划中的交通小区作为划分方案，将目标区域划分为205个子区域(现有方案3)。

在三套子区划分方案基础上，收集道路交通事故数据、土地利用性质及道路等级等空间信息，具体变量如下表2所示：

表2实施例方法与现有方案2、现有方案3

基于上述数据，构建空间层次贝叶斯模型用于分析城市宏观道路交通安全特性，区域内的交通安全等级如图3所示。

对三种子区划分方案的模型性能进行评价分析，统计评价指标如下表3所示：

表3实施例方法与现有方案2、现有方案3的统计评价指标

综合分析信息偏差准则DIC、平均绝对偏差MAD、平均绝对百分误差MAPE、标准差SD、均方百分比误差MSPE各指标，可以发现实施例方法获得的分区方案的性能最佳。

Claims (4)

1.一种基于谱聚类的城市道路交通子区划分方法，包括以下步骤：

S1、基于路网交叉口与路段的拓扑结构以及各节点的交通特征数据，建立路网无向图G＝(V,E)，计算路网密度拉普拉斯矩阵L；

S2、计算拉普拉斯矩阵L的除0以外前k个最小的特征值及其特征向量，其中k的初值为2；根据k个特征值对应的特征向量v₁,…,v_k构建聚类基础矩阵H＝[v₁,…,v_k]，对矩阵H的行向量实施K均值聚类算法，获得k个簇；运用方差分析检验方法检验k个群组内的交通特征关联度X，若存在显著差异，则进入步骤S3；否则，k＝k+1，重复步骤S2；

S3、由簇内的交叉口以及交叉口间存在的路段构成初始的子区；若存在孤立点，即子区内仅包含一个节点编号，则将该子区随机合并入邻接的子区内，根据合并情况统计当前的子区总数N；

其特征在于：

S4、通过偏差检测识别异常值点，并通过边界调整解决最优的异常点归属问题；通过子区内外的相似度评估以及子区拆分、合并前后的相似度变化分析，对子区方案进行迭代优化，最终获得子区内节点关联度相似性最大、子区间差异性最大的道路交通路网划分方案。

2.如权利要求1所述的基于谱聚类的城市道路交通子区划分方法，其特征在于：步骤S4具体为，

S41、若i≤N，则根据子区交叉口或路段交通特征关联度X，检测初始划分方案内各子区内关联度偏差，若存在异常值点，则转入S42，否则转入S43；其中i为子区编号，初值为1；若i＞N，结束本流程；

S42、根据路网拓扑识别子区i的相邻子区集I＝{i₁,i₂…i_p}，其中i_p为相邻子区的编号，p为相邻子区个数，p∈[1,N-1]；检测异常值点映射的节点或路段是否位于子区i边界，若是，则将异常点映射的节点或路段划入相邻区域，求解使得成立的边界调整方案，Var(X)为子区内关联度X方差，q为参与边界调整的子区数，q∈[2,p]；若异常值点映射的节点或路段不在子区边界上，则将异常值点作为子区内的特殊点标记，不参与后续的处理；

S43、判断该子区i是否为初次划分，若是，进入步骤S44；否则，进入步骤S46；

S44、计算子区内除去特殊标记点以外的点间关联度X的相似度NS(X_i)；

S45、若NS(X_i)≥1，检测子区i内的交叉口数是否低于阈值NT；若成立则将子区i与相邻子区合并，求解成立的合并方案，其中X_c'为合并后的i原相邻子区的内部关联度，i＝i+1，回S41；若i内的交叉口数不低于阈值NT，则回S1；

若NS(X_i)＜1，i＝i+1，回S41；

S46、计算子区内除去特殊标记点以外的点间关联度X的相似度NS(X_i)，若NS(X_i)≥1，则恢复i区划分前的方案；否则，检测子区i内的交叉口数是否低于阈值NT；

若成立则将子区i与相邻子区合并，求解成立的合并方案，进S47；否则，直接进S47；

S47、计算子区i与路网内其他子区的组间相似度并比较在子区i从原区域划分出来前后，其归属区域与其他子区的组间相似度的变化趋势，若降低，则i＝i+1，回S41；否则，恢复i区划分前的方案。

3.如权利要求2所述的基于谱聚类的城市道路交通子区划分方法，其特征在于：步骤S41中，关联度偏差检测方式为：若则将x_i作为子区内的离群点；其中，u为x_i均值，sd为标准差。

4.如权利要求1所述的基于谱聚类的城市道路交通子区划分方法，其特征在于：步骤S44、S46中，计算子区内除去特殊标记点以外的点间关联度X的相似度其中，i_p为相邻子区的编号，u_i、为子区i、i_p内关联度X数据均值，Var(X_i)、Var(X_ip)分别为子区i、i_p内关联度X方差。