CN111008223A - 一种基于时空关联规则的区域交通拥堵相关性计算方法 - Google Patents

Abstract

本发明提出了一种基于时空关联规则的区域交通拥堵相关性计算方法，可以给交通管理人员和出行者提供道路情况预警，可以有效避免并缓解交通拥堵的演化与传播。具体实施方案是对路网进行区域划分，并采集区域交通流量与速度数据；使用融合FCM和kmeans++的聚类算法对历史交通数据进行聚类，获得区域的交通状态；进而构建拥堵事务集，并运用时空关联规则算法，根据相关性指标，计算强关联规则中区域间的相关性，从而获得同一时段，具有强相关关系的区域信息。本发明使用的数据易于收集，并通过大数据挖掘的方法，快速便捷地获得拥堵区域关联规律，具有实际的操作价值。

Description

一种基于时空关联规则的区域交通拥堵相关性计算方法

技术领域

本发明涉及智能交通系统技术领域，特别涉及一种基于时空关联规则的区域交通拥堵相关性计算方法。

背景技术

城市交通系统是城市社会经济生活的最重要的基础保障设施之一。2017年年末，中国城镇化率超半数以上，为城市带来了更多的交通需求。与此同时，机动车保有量保持10％以上的增速，全国大部分省会城市与二线城市的机动车保有量均在200万辆以上。大量的人口和车辆聚集在城市内，城市交通系统的运行压力不断上涨，原有的道路设施、规划及交通管理等方面无法及时响应，导致道路拥堵现象频繁，行车速度降低，排队长度增加，交通延误增大，居民的出行时间成本持续增加。同时，拥堵时车辆的低速行驶使得耗油量增加，并伴随噪声污染、尾气污染，给居民的生活带来了诸多问题。

人们的正常社会生活依赖于城市交通系统的正常运行，而城市内部交通也是交通拥堵的常发区域，同时城市道路交通状态存在周期性和时空相关性，某一个路段的交通状况会沿着道路结构蔓延到周围路段，导致周围一定空间范围内路段交通状况改变，掌握拥堵的时空演化规律有利于交通拥堵的治理。挖掘拥堵状态的时空相关性，可以对城市道路的拥堵状态进行预判。交通拥堵时空相关性研究中，部分学者采用统计指标体现相关性，但交通数据具有非平稳和非线性特征，基本的统计学指标应用效果不佳，普适性较差。本申请基于数据挖掘技术关联规则，设计适用于挖掘拥堵时空关联性的时空关联规则算法，挖掘拥堵区域的时空相关性，从而获得在同一时段内，不同区域间拥堵的相关性大小，挖掘到交通拥堵发生的规律性，并给交通管理人员提供拥堵的先验知识。经过数据验证，本发明可以有效计算拥堵区域间的相关性，并且普适性和可行性较强。

发明内容

城市交通拥堵现象频繁发生，增加了居民出行的时间成本，同时降低了出行的体验感。目前针对交通拥堵时空相关性的研究，不能反映拥堵相关性的长期时空关联规律。针对现有技术中存在的缺陷，本发明的目的在于提供一种基于时空关联规则的区域交通拥堵相关性计算方法，可以挖掘拥堵区域间相关性的规律特点，从而可以提前准备拥堵疏导预案，并及时分流拥堵区域车流，避免拥堵传播，进而影响其他区域的交通状态。

为达到以上目的，本发明采取的技术方案是：

一种基于时空关联规则的区域交通拥堵相关性计算方法，包括以下步骤：

步骤1：将研究区域的城市道路区域按1km*1km的方格进行网格区域划分；

步骤2：计算网格区域的平均速度和流量数据；

交通数据由安置在交叉口附近的卡口设备采集，同方向相邻两个卡口设备构成1个路段；首先，统计各网格区域内的路段数量及卡口编码；其次，统计一定时段内通过各路段车辆的平均速度和流量，获得该时段路段的平均速度；最后，将网格区域内所有路段的平均速度进行平均获得网格区域的平均速度，网格内所有路段的流量数据求和获得网格区域的流量数据；时间粒度为15分钟，将每天划分为96个时段，按此方法，获得各网格区域各个时段的速度和流量数据；

步骤3：将各网格区域的平均速度和流量数据信息标准化；

步骤4：将标准化后的各网格区域的平均速度、流量数据进行聚类，得到各网格区域的交通状态分类，通过使用“kmeans++”与FCM聚类算法对网格区域的交通参数数据集进行划分，产生4种分类，分别为畅通、基本畅通、轻微拥堵、拥堵；所述交通参数数据集包括网格区域的平均速度和流量数据；

步骤5：用“0-1”标记网格区域是否发生拥堵事件，若在某一时段网格区域发生拥堵，则标记为1，否则，标记为0；并提取道路发生拥堵的时间段、发生拥堵的位置信息，位置信息为网格区域的编号信息；

步骤6：构建拥堵事务集T，所述拥堵事务集T中包含多个拥堵项集I，拥堵项集I包含拥堵发生的时间段t、发生拥堵的位置信息、拥堵事件的标记；

步骤7：在拥堵事务集T的基础上，应用时空关联规则，计算规则的支持度和置信度，满足最小支持度和最小置信度的规则为强关联规则；

步骤8：根据时空关联规则算法获得的强关联规则，计算网格区域之间的时空相关性。

在上述技术方案的基础上，步骤2中，各路段车辆的平均速度计算过程如下：

首先，计算第i辆车通过路段R时的平均速度，如公式(1)所示：

其中，

为第i辆车通过路段R时的平均速度；l_R为路段R的长度，路段的长度通过调用百度地图API的方式，输入路段上下游卡口的经纬度信息，即可得到路段上下游卡口间的距离；

为第i辆车通过路段R的时间；

其次，计算所述路段车辆的平均速度，如公式(2)所示：

其中，V_t,R为路段R在t时段的平均速度；t为时段编号，t＝0,1,2,……,95，即为以15min为间隔划分时段，将一天划分为96个时段，采集数据的时间跨度为d天；nvol为路段R在t时段内通过车辆数；

在上述技术方案的基础上，步骤2中，各网格区域的平均速度的计算公式如下：

其中，V_grid,t为网格区域grid在时段t的平均速度；v_t,R为路段R在t时段的平均速度；t为时段编号，t＝0,1,2,……,95；Num为网格区域grid内的路段数；

所述时段t通过卡口m的流量数据的计算公式如下：

其中，vehicle_m,t0为在t₀时段内通过卡口m的车辆数；t_i、t_j表示时段t的开始和结束时刻；q_t,m为时段t通过卡口m的流量；t为时段编号，t＝0,1,2,……,95。

所述网格区域的流量数据的计算公式如下：

其中，Q_grid,t表示网格区域grid在t时段的流量；num表示网格区域grid内的卡口数。

在上述技术方案的基础上，步骤7中，所述的时空关联规则，有以下基本概念：

定义1：

时空关联规则如下所示：

其中P_u和Q_w表示不同的拥堵区域的位置信息，time表示规则发生的时段。式(6)的描述为满足min_sup,min_conf的要求下，X＝[P₁,P₂,…,P_u,time]与Y＝[Q₁,Q₂,…,Q_w,time]存在相关关系。

定义2：

项与项集：记I＝(I₁,I₂,......I_p)为所有项的集合，称为项集(itemsets)，每个I_j(j＝1,2,......p)称为一个项目，根据I包含的项目个数l＝k称I为k-项集，例如，集合{西单拥堵，学院路拥堵，北京南站拥堵}是一个3-项集。

定义3：

事务：拥堵事务数据库D＝{T₁,T₂,......,T_d}，每个事务T_e(e＝1,2,…,d)具有唯一标识TID，每个T_e(e＝1,2,…,d)与I的一个子集相对应。例如：每天的拥堵路段记录为一个事务，多天的拥堵记录组成一个事务数据库，每个事务在数据库中使用TID进行唯一标识，用以标记拥堵发生的日期与位置。

定于4：

支持度：基于经典关联规则的支持度进行变形，计算结合时间、空间属性后的项集在事务集中发生的概率，使得最终规则同时考虑了时间和空间因素。当计算k-项集的支持度大于设定的最小支持度时，即为频繁k-项集，未与最小支持度比较前，均称为候选k-项集。支持度计算公式如下：

式中frq(I(o',t))——时段t、位置为o'的拥堵项集I的支持度计数；N[t]——时段t发生的事务数；o'——拥堵区域的位置信息。

定义5：

置信度：基于定义4获得的支持度，计算时空关联规则的置信度，计算公式如下：

其中

o'和o”表示两个不同的位置信息。

定义6：

相关性指标：提升度可以衡量规则间的相关性，但提升度会受到零和事务的影响，零和事务即不包含规则中任意一项的事务；且提升度在临界值1附近呈不对称，故采用“Kulc+IR”指标，根据指标大小，评价规则前件X与后件Y之间的相关性。Kulc趋向于1，则表示规则的前后件之间呈正相关，即前件的发生会促进后件的发生；IR趋向于0，表示规则为平衡状态，前件影响后件，同时后件也影响前件。

Kulc＝0.5×(conf(X,Y)+conf(Y,X)) (9)

在上述方法的基本概念的基础上，其中步骤7所述时空关联规则的具体设计包含以下步骤：

Step1：根据定义4分时段统计候选1-项集的支持度；由设定的最小支持度筛选获得不同时段的频繁1-项集；计算得到的支持度与最小支持度进行比较，若大于，则为频繁项集；

Step2：获得不同时段的频繁k-1(k≥2)项集后，在相同的时间段内执行连接步，形成候选k-项集；

连接步：主要是为了生成频繁k-项集，记为L_k，输入为频繁k-1项集L_k-1，记L_a，其中a＝1,2,…k-1，则L_a是L_k-1中的第a项；L_k-1中的所有子集之间相互连接，产生候选k-1项集，记为C_k；L_k-1中的任意两个元素L_i和L_j均可以执行上述连接操作；

Step3：对候选k-项集根据Apriori性质进行剪枝，形成频繁k-项集；

剪枝步：C_k是频繁k-项集L_k的超集，即C_k的成员可能不全是频繁的，因此，先删除不可能为频繁k-项集的项有利于减少计算成本，如果一个候选k-项集的k-1项集不在L_k-1中，则该候选k-项集也不可能成为频繁项集，从而可从C_k删中除，为剪枝过程；

Step4：重复Step2和Step3，直到不能产生新的频繁候选集或是产生的候选集不满足设定的最小支持度，则完成了所有时空频繁k-项集的搜索工作；

Step5：执行完Step4后，根据定义5分别计算各时段频繁k-项集的置信度，满足最小置信度要求的规则构成了强关联规则集合。根据定义6的相关性指标，计算相关性大小，用以评价规则前件X与规则后件Y之间的相关性，当Kulc趋向于1，则表示规则前件X与规则后件Y之间呈正相关，即前件的发生会促进后件的发生；当IR趋向于0，表示规则为平衡状态，前件影响后件，同时后件也影响前件。

本发明的有益效果：

本发明利用历史交通数据集进行聚类，确定拥堵状态，给交通数据标记拥堵状态。综合考虑拥堵发生的时间和地点后，构建拥堵时空数据集，对拥堵时空数据集应用时空关联规则，挖掘出同一时段具有强相关关系的区域。本发明可以通过某一时段某一区域发生拥堵判断出与之相关的其他区域也会为拥堵状态，并显示具体的概率，可以提前设定拥堵预警方案且及时疏散去往拥堵区域的车辆。本发明使用的数据易于收集，并通过大数据挖掘的方法，快速便捷地获得拥堵规律，具有实际的操作价值。

附图说明

本发明有如下附图：

图1本发明的基于时空关联规则的区域交通拥堵相关性计算方法的总体流程图。

图2本发明的城市道路网格区域划分示意图。

具体实施方式

以下结合附图对本发明作进一步详细说明。

如图1～2所示，本发明所述的一种基于时空关联规则的交通拥堵时空相关性计算方法，包括以下步骤：

步骤1：将研究区域的城市道路区域按1km*1km的方格进行网格区域划分；

步骤2：计算网格区域的平均速度和流量数据；

首先，相邻两个同方向的卡口构成一个路段，统计一定时段通过该路段车辆的平均速度，获得该时段路段的平均速度；其次，统计网格中路段的个数，网格区域的平均速度即为所有路段车速的平均，网格区域的流量为所有路段车流量之和。计算第i辆车通过路段R时的平均速度计算公式如下：

其中，

为第i辆车通过路段R时的平均速度；l_R为路段R的长度，路段的长度通过调用百度地图API的方式，输入路段上下游卡口的经纬度信息，即可得到路段上下游卡口间的距离；

为第i辆车通过路段R的时间。

所述路段车辆的平均速度计算公式如下：

其中，V_t,R为路段R在时段t的平均速度；t为时段编号，t＝0,1,2,……,95，即为以15min为间隔划分时段，将一天划分为96个时段，采集数据的时间跨度为d天；nvol为路段R在t时段内通过车辆数；

各网格区域的平均速度的计算公式如下：

其中，V_grid,t为网格grid在时段t的平均速度；v_t,R为R路段在t时段的平均速度；t为时段编号，t＝0,1,2,……,95；Num为网格区域grid内的路段数。

通过所述时段t通过卡口m的车流量的计算公式如下：

其中，vehicle_m,t0为在t₀时间通过卡口m的车辆；t_i、t_j表示时段t的开始和结束时刻；q_t,m为时段t通过卡口m的流量；t为时段编号，t＝0,1,2,……,95。

所述网格区域的流量数据的计算公式如下：

其中，Q_grid,t表示网格grid在t时段的平均流量；num表示网格区域grid内的卡口数。

步骤3：将各网格区域的平均速度、流量数据信息标准化。

步骤4：将标准化后的各网格区域的平均速度、流量数据进行聚类，得到各网格区域的交通状态分类，通过使用融合“kmeans++”与FCM的聚类算法对网格区域的交通参数数据集进行划分，产生4种分类，分别为畅通、基本畅通、轻微拥堵、拥堵。所述交通参数数据集包括网格区域的平均速度和流量数据。

步骤5：用“0-1”标记网格区域是否发生拥堵事件，若在某一时段网格区域发生拥堵，则标记为1，否则，标记为0；并提取道路发生拥堵的时间段，发生拥堵的位置信息，位置信息即网格区域的编号信息。

步骤6：构建拥堵事务集T，所述拥堵事务集T中包含多个拥堵项集I，拥堵项集I包含拥堵发生的时间段t、发生拥堵的位置信息、拥堵事件的标记。

拥堵项集表样如下表所示：

TID	TF	特征值	Location_I
				1	t<sub>1</sub>	v<sub>1</sub>	o<sub>1</sub>
2	t<sub>2</sub>	v<sub>1</sub>	o<sub>2</sub>
				……	……	……	……
p	t<sub>f</sub>	v<sub>1</sub>	o<sub>n</sub>

表中，所有TF具有相同的时间步长，特征值为四种交通状态，v₁为拥堵状态，O_n为拥堵发生的空间信息。

步骤7：在拥堵事务集T的基础上，应用时空关联规则，计算规则的支持度和置信度，满足最小支持度和最小置信度的规则为强关联规则。具体设计包含以下步骤：

Step1：分时段统计候选1-项集的支持度。由设定的最小支持度筛选获得不同时段的频繁1-项集。计算得到的支持度与最小支持度进行比较，若大于，则为频繁项集；支持度公式如下所示：

其中，frq(I(o',t))为时段t、位置为o'的拥堵项集I的支持度计数；N[t]为时段t发生的事务数；o'为拥堵区域的位置信息。

Step2：获得不同时段的频繁k-1(k≥2)项集后，在相同的时间段内执行连接步，形成候选k-项集。

连接步：主要是为了生成频繁k-项集，记为L_k。输入为频繁k-1项集L_k-1，记L_a，其中a＝1,2,…k-1，则L_a是L_k-1中的第a项。L_k-1中的所有子集之间相互连接，产生候选k-1项集，记为C_k。L_k-1中的任意两个元素L_i和L_j均可以执行上述连接操作。

Step3：对候选k-项集根据Apriori性质进行剪枝，形成频繁k-项集。

剪枝步：C_k是频繁k-项集L_k的超集，即C_k的成员可能不全是频繁的，因此，先删除不可能为频繁k-项集的项有利于减少计算成本。如果一个候选k-项集的k-1项集不在L_k-1中，则该候选k-项集也不可能成为频繁项集，从而将其从C_k中删除，为剪枝过程。

Step4：重复Step2和Step3，直到不能产生新的频繁候选集或是产生的候选集不满足设定的最小支持度，则完成了所有时空频繁k-项集的搜索工作。

Step5：执行完Step4后，分别计算各时段频繁k-项集的置信度，满足最小置信度要求的规则构成了强关联规则集合。置信度公式如下所示：

其中，

时空关联规则如下所示：

其中P_u和Q_w表示不同的拥堵区域的位置信息，time表示规则发生的时段。满足最小支持度、最小置信度min_sup,min_conf的要求下，X＝[P₁,P₂,…,P_u,time]与Y＝[Q₁,Q₂,…,Q_w,time]存在相关关系。

步骤8：根据步骤7获得的强关联规则，计算网格区域之间的时空相关性，公式如下所示：

Kulc＝0.5×(conf(X,Y)+conf(Y,X)) (9)

采用“Kulc+IR”指标，根据指标大小，评价规则前件X与后件Y之间的相关性。Kulc趋向于1，则表示规则的前后件之间呈正相关，即前件的发生会促进后件的发生；IR趋向于0，表示规则为平衡状态，前件影响后件，同时后件也影响前件。

由步骤8的相关性指标可知，强关联规则包含具有强相关性的区域。因此，实现了通过交通数据挖掘拥堵区域间的相关性。

本说明书中未作详细描述的内容属于本领域专业技术人员公知的现有技术。

Claims (9)

1.一种基于时空关联规则的区域交通拥堵相关性计算方法，其特征在于，包括以下步骤：

步骤1：将研究区域的城市道路区域按1km*1km的方格进行网格区域划分；

步骤2：计算网格区域的交通数据，所述交通数据包括平均速度和流量数据；

步骤3：将各网格区域的平均速度和流量数据信息标准化；

步骤4：将标准化后的各网格区域的平均速度、流量数据进行聚类，得到各网格区域的交通状态分类，通过使用“kmeans++”与FCM聚类算法对网格区域的交通参数数据集进行划分，产生4种分类，分别为畅通、基本畅通、轻微拥堵、拥堵；所述交通参数数据集包括网格区域的平均速度和流量数据；

步骤5：用“0-1”标记网格区域是否发生拥堵事件，若在某一时段网格区域发生拥堵，则标记为1，否则，标记为0；并提取道路发生拥堵的时段、发生拥堵的位置信息，位置信息为网格区域的编号信息；

步骤6：构建拥堵事务集T，所述拥堵事务集T中包含多个拥堵项集I，拥堵项集I包含以下信息：拥堵发生的时段、拥堵发生的位置信息、拥堵事件的标记；

步骤7：在拥堵事务集T的基础上，应用时空关联规则，计算规则的支持度和置信度，满足最小支持度和最小置信度的规则为强关联规则；

步骤8：根据时空关联规则获得的强关联规则，计算网格区域之间的时空相关性。

2.如权利要求1所述的基于时空关联规则的区域交通拥堵相关性计算方法，其特征在于，步骤2中，所述交通数据由安置在交叉口附近的卡口设备采集，同方向相邻两个卡口设备构成1个路段；

首先，统计各网格区域内的路段数量及卡口编码；其次，统计一定时段内通过各路段车辆的平均速度和车流量，获得该时段路段的平均速度；最后，将网格区域内所有路段的平均速度进行平均获得网格区域的平均速度，网格区域内所有路段的流量数据求和获得网格区域的流量数据。

3.如权利要求2所述的基于时空关联规则的区域交通拥堵相关性计算方法，其特征在于，统计通过各路段车辆的平均速度和车流量的时间粒度为15分钟，将每天划分为96个时段。

4.如权利要求3所述的基于时空关联规则的区域交通拥堵相关性计算方法，其特征在于，各路段车辆的平均速度计算过程如下：

首先，计算第i辆车通过路段R时的平均速度，如公式(1)所示：

其中，

为第i辆车通过路段R时的平均速度；l_R为路段R的长度；

为第i辆车通过路段R的时间；

其次，计算路段R车辆的平均速度，如公式(2)所示：

其中，V_t,R为路段R在t时段的平均速度；t为时段编号，t＝0,1,2,……,95；nvol为路段R在t时段内通过车辆数。

5.如权利要求4所述的基于时空关联规则的区域交通拥堵相关性计算方法，其特征在于，各网格区域的平均速度的计算公式如下：

其中，V_grid,t为网格区域grid在时段t的平均速度；v_t,R为路段R在t时段的平均速度；t为时段编号，t＝0,1,2,……,95；Num为网格区域grid内的路段数；

所述时段t通过卡口m的流量数据的计算公式如下：

其中，vehicle_m,t0为在t₀时段内通过卡口m的车辆数；t_i、t_j分别表示时段t的开始和结束时刻；q_t,m为时段t通过卡口m的流量；t为时段编号，t＝0,1,2,……,95；

所述网格区域的流量数据的计算公式如下：

其中，Q_grid,t表示网格区域grid在t时段的流量；num表示网格区域grid内的卡口数。

6.如权利要求1所述的基于时空关联规则的区域交通拥堵相关性计算方法，其特征在于，步骤7中，所述时空关联规则的具体设计包含以下步骤：

Step1：分时段统计候选1-项集的支持度；由设定的最小支持度筛选获得不同时段的频繁1-项集；计算得到的支持度与最小支持度进行比较，若大于，则为频繁项集；所述支持度的计算公式如下所示：

其中，frq(I(o',t))为时段t、位置为o'的拥堵项集I的支持度计数；N[t]为时段t发生的事务数；o'为拥堵区域的位置信息；

Step2：获得不同时段的频繁k-1项集后，在相同的时间段内执行连接步，形成候选k-项集；其中k≥2；

Step3：对候选k-项集根据Apriori性质进行剪枝，形成频繁k-项集；

Step4：重复Step2和Step3，直到不能产生新的频繁项集和候选项集或是产生的候选项集不满足设定的最小支持度，则完成了所有时空频繁k-项集的搜索工作；

Step5：执行完Step4后，计算各时段频繁k-项集的置信度，满足最小支持度和最小置信度要求的规则构成了强关联规则集合；所述置信度公式如下所示：

其中，

o'和o”表示两个不同的位置信息。

7.如权利要求6所述的基于时空关联规则的区域交通拥堵相关性计算方法，其特征在于，Step2中，所述连接步用于生成频繁k-项集，记为L_k，输入为频繁k-1项集L_k-1，记L_a，其中a＝1,2,…k-1，则L_a是L_k-1中的第a项；L_k-1中的所有子集之间相互连接，产生候选k-1项集，记为C_k；L_k-1中的任意两个元素均执行上述连接操作。

8.如权利要求7所述的基于时空关联规则的区域交通拥堵相关性计算方法，其特征在于，Step3中根据Apriori性质进行剪枝的过程为：C_k是频繁k-项集L_k的超集，先删除不可能为频繁k-项集的项，如果一个候选k-项集的k-1项集不在L_k-1中，则该候选k-项集就不可能成为频繁项集，则将其从C_k中删除。

9.如权利要求8所述的基于时空关联规则的区域交通拥堵相关性计算方法，其特征在于，根据强关联规则，计算网格区域之间的时空相关性的计算过程为：

采用“Kulc+IR”相关性指标，计算公式如下：

Kulc＝0.5×(conf(X,Y)+conf(Y,X)) (9)

其中，X＝[P₁,P₂,…,P_u,time]，Y＝[Q₁,Q₂,…,Q_w,time]，P_u和Q_w表示不同的拥堵区域的位置信息，time表示规则发生的时段；

计算相关性大小，用以评价规则前件X与规则后件Y之间的相关性，当Kulc趋向于1，则表示规则前件X与规则后件Y之间呈正相关，规则前件的发生会促进规则后件的发生；当IR趋向于0，表示规则为平衡状态，规则前件影响规则后件，同时规则后件也影响规则前件。

Images