一种城市交通流不平衡模式挖掘方法及系统

摘要

本发明公开了一种城市交通流不平衡模式挖掘方法及系统，所述方法包括：首先，建立路网数据与轨迹数据之间的关联模型；进而，提出一种线性扫描统计方法评价交通流不平衡模式的统计显著性；最后，基于模式相似性计算发现流动不平衡模式的动态演化，即频发模式与偶发模式。本发明采用线段扩展方法寻找网络邻域，避免计算点之间的网络距离，从而提高了算法执行效率。本发明提出的线性扫描统计方法对不平衡模式的判别结果受扫描窗口大小的影响较小，因此降低了传统方法人为设定阈值的主观性的影响。将本发明应用于实际交通数据，结合城市功能区与城市设施对不平衡模式的产生原因进行分析，可为城市出行与交通规划提供一定的借鉴。

说明书

技术领域

本发明涉及智能交通领域，更为具体而言，涉及一种城市交通流不平衡模式挖掘方法及系统。

背景技术

科学合理地检测评价城市道路交通状态不均衡度，有助于交通管理者全面了解道路交通运行状况，深入挖掘潜在道路资源，为均衡分配道路资源，诱导交通流合理运行提供数据支撑与决策依据。

交通状态的评估是表征交通流运行拥挤程度，实施交通管理与控制措施的基础。从20世纪80年代至今，城市道路交通状态检测判别技术取得了许多进展，国内外学者提出了大量的表征指标、描述模型与计算方法，如道路服务水平和道路拥挤度/区域交通状态判别模型和区域交通状态时空分层模型等。但是这些指标和模型大多针对单个路段、交叉口或路网交通拥挤程度的检测和判别，而忽视了整个路网交通状态不平衡性、不均衡度的检测和评价。路网交通流的不均衡性，导致不同区域交通拥堵状况迥异，虽然总体交通运行状态相同，但各区域的交通状态差异性较大。因此，为了更好的反映路网交通运行状态，挖掘非拥堵区域的道路资源，更快地疏导拥堵区域交通流，更好地引导城市道路交通资源均衡发展，迫切需要获取城市道路交通状态不均衡度信息，建立城市道路交通状态不均衡度的检测和确定方法。

不平衡交通流指在固定的时间间隔内，流入一个区域的交通流量显著高于或显著低于从该区域流出的交通流量。目前大多数挖掘不平衡交通流模式的方法基于欧式空间的假设，使用自定义阈值确定不平衡交通流的显著性。然而，交通流严格受到道路网络的约束，且很难确定一个合适的阈值来评估不平衡模式的显著性。

发明内容

为了解决现有技术所存在的缺陷，本发明实施方式提供一种城市交通流不平衡模式挖掘方法及系统，能够准确可靠地评估交通流不平衡模式的显著性。

一方面，本发明实施方式提供一种城市交通流不平衡模式挖掘方法，包括：

S1、获取路网数据和轨迹数据；

S2、建立所述路网数据与所述轨迹数据之间的关联模型；

S3、采用线性扫描统计方法评价交通流不平衡模式的统计显著性；

S4、基于模式相似性计算获得所述交通流不平衡模式的动态演化。

相应地，本发明实施例还提供一种城市交通流不平衡模式挖掘方法及系统，包括：

数据获取模块，用于获取路网数据和轨迹数据；

关联模型建立模块，用于建立所述路网数据与所述轨迹数据之间的关联模型；

统计模块，用于采用线性扫描统计方法评价交通流不平衡模式的统计显著性；

计算模块，用于基于模式相似性计算获得所述交通流不平衡模式的动态演化。

本发明的有益效果如下：

本发明提出了城市交通流不平衡模式挖掘方法，弥补了现有技术的不足，有助于全面检测和评价城市道路交通运行状况，结合城市功能区与城市设施对不平衡模式的产生原因进行分析，可为城市出行与交通规划提供一定的借鉴；

本发明在挖掘城市交通流不平衡模式过程中考虑到轨迹数据的特点，添加了道路网络的约束，以网络空间代替欧式空间，可挖掘出欧式空间不平衡模式挖掘方法中会遗漏的模式，使得挖掘结果更加准确可靠；

本发明采用线段扩展方法寻找网络邻域，避免计算点之间的网络距离，从而提高了算法执行效率；

本发明提出的线性扫描统计方法对不平衡模式的判别结果受扫描窗口大小的影响较小，因此降低了传统方法人为设定阈值的主观性的影响；

本发明在挖掘出交通流不平衡模式之后，又基于模式相似性分析交通流不平衡模式的动态演化模式，较已有的不平衡模式挖掘方法又更进一步，可为城市的时空异常探测提供科学指导。

附图说明

图1是本发明实施例提供的城市交通流不平衡模式挖掘方法的流程示意图；

图2是本发明实施例提供的城市交通流不平衡模式挖掘系统的示意图；

图3是本发明实施例提供的以P为窗口中心点，以2Z为窗口大小的线性扫描窗口；

图4是本发明实施例提供的基于密度扩展算法聚类的流程图；

图5（a）是本发明实施例提供的频发模式的示意图，（b）是本发明实施例提供的第一种偶发模式的示意图，（c）是本发明实施例提供的第二种偶发模式的示意图。

具体实施方式

以下结合附图和具体实施方式对本发明的各个方面进行详细阐述。其中，众所周知的模块、单元及其相互之间的连接、链接、通信或操作没有示出或未作详细说明。并且，所描述的特征、架构或功能可在一个或一个以上实施方式中以任何方式组合。本领域技术人员应当理解，下述的各种实施方式只用于举例说明，而非用于限制本发明的保护范围。还可以容易理解，本文所述和附图所示的各实施方式中的模块或单元或步骤可以按各种不同配置进行组合和设计。

图1是根据本发明实施例的一种城市交通流不平衡模式挖掘方法的流程示意图。参照图1，所述方法包括：

S1：获取路网数据和轨迹数据。

S2：建立所述路网数据与所述轨迹数据之间的关联模型。

S3：采用线性扫描统计方法评价交通流不平衡模式的统计显著性。

S4：基于模式相似性计算获得所述交通流不平衡模式的动态演化，即频发模式与偶发模式。

上述步骤S1中的路网数据是从OpenStreetMap获取得到的多级道路矢量数据；轨迹数据是车载GPS每隔一定时间（90秒）采集一次得到的车辆信息数据。本发明需首先从原始GPS数据中提取出所有车辆的起点和终点数据，具体提取方法如下：

将具有同一车辆标识的载客状态下的GPS点识别为同一组轨迹数据，若整个数据集中共有S个不同的车辆ID，则会得到S组轨迹R_i(i=1,2,…,S)；

将上步识别出的每组轨迹数据按照GPS点的采集时间升序排列，从每一组轨迹R_i(i=1,2,…,S)中提取起点和终点的方法为：从R_i的第一个采样点P₁开始，判断R_i中P₁的后一点P₂的采样时间与P₁的采样时间间隔是否大于原始数据的时间分辨率（90秒），若不大于，表示P₁与P₂在同一条载客轨迹上；若大于，表示P₁与P₂不在同一条载客轨迹上，P₁作为一条轨迹的终点，P₂作为另一条轨迹的起点；

对R_i(i=1,2,…,S)中的每一个点执行上述步骤中的操作，最终得到轨迹中所有的起点和终点数据。

上述步骤S2具体包括：

将道路网络中的所有线在线的节点处、相交处打断为直线，每条直线表示网络的边，直线的端点为网络结点，从而构建一个规范的网络结构。

网络中的每条边都有两端点坐标A₁(X₁,Y₁)，A₂(X₂,Y₂)，由两点坐标采用数学方法求出每条直线的直线方程：y=k_i*X+b_i(i=1,2,…,N(N为直线数目))。

步骤S1提取出的每个起点O_j(j=1,2,…,M)和终点D_k(k=1,2,…,M)（M为起点或终点的数目）都有其相应的坐标，判断一个轨迹点P(x,y)所属的直线的方法为：将P点的x坐标分别代入每条直线方程得到y_i(i=1,2,…,N)，找出y_i与P点的y坐标差值最小的直线即为P点所属的直线。以此方法可判断所有的起点和终点所属的直线。

判段起点和终点所属的直线之后需建立道路网络和轨迹点之间的存储关系。本发明分别建立了路网数据的存储结构表和轨迹数据的存储结构表。其中路网数据的存储结构表（表1）的每条记录表示一条网络边，包括边的ID标识，边的长度，起结点ID，起结点所连接的其它所有边的ID，尾结点ID，尾结点所连接的其它所有边的ID，边上所有的轨迹点的ID；轨迹数据的存储结构表（表2）的每条记录表示一个点，包括点的ID标识，点所属的类别（起点或终点），点所在的边的ID，点距离其所在边的起结点的距离。

表1. 路网的存储形式

IDLengthStart-nodeEdges linked to start-nodeEnd-nodeEdges linked to end-nodePoints1L₁n₁E₁n₂E₂S₁2L₂n₃E₃n₄E₄S₂……………………………………NL_Nn_(2N-1)E_2N-1n_(2N)E_2NS_N

表2. 点的存储形式

IDCategoryEdge IDDistance to Start-node1Oe₁l₁2Oe₂l₂……………………MDE_ML_M

建立了路网数据与轨迹数据之间的关联模型之后，在下一步骤S3中搜索一定范围内点的路网邻域时可先快速搜索一定范围内的网络线段，根据关联关系对应到线段上的起点和终点，无需繁琐地计算点之间的网络距离。

在建立了路网数据和交通轨迹数据之间的关联模型之后，便可以进行线性扫描统计，扫描统计的第一步应首先确定扫描统计的零假设和备择假设以及扫描统计的统计量。扫描统计中根据统计目的的不同零假设和备择假设有不同的定义，本发明使用扫描统计的目的是得到窗口内两种类型的点的数目存在显著差异，因此将零假设定义为：

（1）

将备择假设定义为：

（2）

其中，在公式（1）和（2）中，p_O表示扫描窗口内起点O的数目占窗口内总点数的比例；q_O表示扫描窗口外起点O的数目占窗口外总点数的比例；p_D表示窗口内终点D的数目占窗口内总点数的比例；q_D表示窗口外终点D的数目占窗口外总点数的比例，则有。

扫描统计中定义统计量的目的是为了确定扫描窗口内外数据的分布情况，对于扫描统计中的每一个窗口，都有一个统计值。本发明将测试统计值的计算公式定义如下：

（3）

其中，Z表示一个扫描窗口，C表示数据集中起点和终点的总数，表示数据集中起点所占的比例，表示数据集中终点所占的比例，表示窗口内点的数目，表示窗口Z内起点所占的比例，表示窗口Z内终点所占的比例。

S3的第二步即为线性空间扫描统计的具体过程，首先应以点数据集中的每个点为窗口中心点构建网络中的线性扫描窗口，统计窗口内外的点数，并计算窗口的测试统计量。以图3为例描述寻找线性扫描窗口内的所有点的具体过程，图3中P为窗口中心点，2Z为窗口大小，P点所在边为E1，两端结点为N1和N7，边E2两端结点为N1和N2，边E3两端结点为N1和N3，边E4两端结点为N1和N4，边E5两端结点为N4和N5，边E6两端结点为N4和N6，寻找窗口内的点的具体过程为：

1. 从P点开始，判断P与N7的距离，大于Z则终止此方向的遍历；

2. 判断P与N1的距离，小于Z则继续该方向的遍历，寻找N1连接的所有未被遍历的边E2，E3，E4，分别判断边E2，E3，E4的另一端结点N2，N3，N4与P的最短网络距离是否大于Z；

3. N2，N3与P的最短网络距离大于Z，则不再进行N2，N3方向的遍历；

4. N4与P的最短网络距离小于Z，则继续寻找N4连接的所有边，重复2-4，直到遍历终止。

最后得到图3中红线部分的网络边，图中网络边的终端P1，P2，P3，P4，P5到P的距离均为Z。由S2建立的网络数据和轨迹点数据之间的关联模型，在得到窗口内的边之后可以快速得到窗口内的边上的点，进而计算得到窗口的统计量。由于路网数据边的数目远远小于轨迹数据点的数目，且网络中边的长度已知，本发明中这种寻找线性扫描窗口内的点的方法只遍历了网络中的边，且避免了计算点之间的网络距离，大大提高了算法的执行效率。

在实际运用中，将起点和终点数据按照数据采集时间划分到不同的M个时间切片上（T₁,T₂,…,T_M），以每小时时间间隔为一个时间切片，以下以一个时间切片上的起点和终点为例进行聚类过程介绍，将一个时间切片上的所有的N个点与路网建立空间关联模型，输入一个参数2Z作为线性扫描窗口的大小，数据集中每个点都对应一个2Z大小的线性扫描窗口（Z₁,Z₂,…,Z_N），计算每个窗口的统计值。

将得到的窗口的统计值进行蒙特卡罗假设测试，判断统计值的显著性。将网络的边上以间隔d取点，作为候选点集，从候选点集中随机抽取与起点数目相同的点作为生成模拟起点，随机抽取与终点数目相同的点作为生成的模拟终点，将模拟起点和模拟终点一起作为模拟数据集。进行蒙特卡罗假设测试R次，分别计算数据集中的每个点在给定窗口内对于每次假设测试产生的随机数据集的似然估计值的对数（j=1,2,...,R），与真实数据集对应窗口的统计值进行比较，进而得出数据集中每个点的p值：

（4）

其中，i表示起点和终点数据集中的每个点，R表示蒙特卡罗假设测试的次数，I(*)是一个判断函数，如果满足条件则取1，如果不满足条件则取0。

对于数据集中的N个点所对应的窗口都计算了p值，此时应考虑多重测试的问题，本发明采用基于线性的两步自适应程序来纠正多重测试问题，按照p值对数据集中的N个点进行升序排列(，然后从开始找出第一个满足下式的：

（5）

这里α表示显著性水平，如果窗口的p值比小，则拒绝零假设，接受备择假设。

在纠正了多重测试的错误发生率之后，可以得到一个校正后的显著性水平α_adj，即从开始找出的第一个满足（5）式的。在所有扫描窗口中，p值小于α_adj的窗口即为包含的两种类型的点显著不平衡的扫描窗口，p值小于α_adj的扫描窗口的中心点可被视为混合核心点。两种类型的混合核心点可被定义为：

Core_O>D：在一个不平衡扫描窗口内，起点数目多于终点数目；

Core_O<D：在一个不平衡扫描窗口内，起点数目少于终点数目。

在识别了两种类型的混合核心点之后，可以通过密度扩展算法将两种类型的混合核心点分别聚类得到两种类型的簇H_OL_D和L_OH_D：

H_OL_D：由混合核心点Core_O>D聚类得到，为交通流出量大于流入量的簇；

L_OH_D：由混合核心点Core_O<D聚类得到，为交通流出量小于流入量的簇。

图4以形成H_OL_D类型的簇为例对密度扩展算法的具体步骤进行介绍，形成L_OH_D类型的簇的方法与此相同：

1. 首先随机选择一个未分类的Core_O>D点m，并为其分配ID号1；

2. 从Core_O>D中寻找距离点m的路网距离小于或等于Z的所有未分类的点，并为其分配与点m相同的ID号1；

3. 继续寻找距离上一步找到的所有点的路网距离小于或等于Z的所有未分类的点，并为其分配与点m相同的ID号1；

4. 重复上一步，直到在Core_O>D中找不到未分类的混合核心点；

5. ID号加1；

6. 重复上述步骤，直到在Core_O>D中没有未分类的混合核心点。

本发明通过S3获取到较显著的交通流不平衡模式后，又分析了这种交通流不平衡模式的动态演化，将演化模式定义为频发模式与偶发模式。频发模式定义为在连续研究时间段内，每个时间切片上都发生的模式（图5(a)），表示如下：

（6）

其中， N表示时间切片的总数，n表示第n个时间切片，k表示每个时间切片上的第k个频发模式簇，m表示不同时间切片上的簇间可认为在同一位置的距离阈值。

本发明将偶发模式分为第一种偶发模式和第二种偶发模式，将第一种偶发模式定义为在连续研究时间段内，只有一个时间切片上没有发生，其余时间切片上都发生的模式（图5(b)），表示如下：

（7）

第二种偶发模式定义为在连续研究时间段内，只有一个时间切片上发生，其余时间切片上都没有发生的模式（图5(c)），表示如下：

（8）

其中，在式（7）和（8）中，N表示时间切片的总数，n表示第n个时间切片，d表示第d个时间切片，k表示每个时间切片上的第k个频发模式簇，m表示不同时间切片上的簇间可认为在同一位置的距离阈值。

采用空间聚类分析中的平均链接法度量簇间距离，交通流不平衡模式的动态演化的分析步骤如下：

1. 分别找出每个时间切片上的所有H_OL_D(L_OH_D)簇到其余所有时间切片上的距离最短的H_OL_D(L_OH_D)簇及相应的距离；

2. 对于任意一个时间切片Ti上的H_OL_D(L_OH_D)簇，到其余所有时间切片上的距离最短的H_OL_D(L_OH_D)簇的距离都小于给定距离阈值的为H_OL_D(L_OH_D)频发模式，簇所在位置为交通流不平衡模式的频发位置；

3. 对于任意一个时间切片T_i上的H_OL_D(L_OH_D)簇，到其余所有时间切片上的距离最短的H_OL_D(L_OH_D)簇的距离只有一个时间切片大于给定距离阈值的为H_OL_D(L_OH_D)第一种偶发模式，簇所在位置为交通流不平衡模式的第一种偶发位置；

4. 对于任意一个时间切片T_i上的H_OL_D(L_OH_D)簇，到其余所有时间切片上的距离最短的H_OL_D(L_OH_D)簇的距离都大于给定距离阈值的为H_OL_D(L_OH_D)第二种偶发模式簇，簇所在位置为交通流不平衡模式的第二种偶发位置。

图2是根据本发明实施例的一种城市交通流不平衡模式挖掘系统的示意图，所述城市交通流不平衡模式挖掘系统用于城市交通流不平衡模式挖掘，参照图2，该系统包括数据获取模块201、关联模型建立模块202、统计模块203、计算模块204。下面分别进行说明。

数据获取模块201，用于获取路网数据和轨迹数据。

关联模型建立模块202，用于建立所述路网数据与所述轨迹数据之间的关联模型。具体地，还用于采用线段扩展方法寻找网络邻域，避免计算点之间的网络距离，从而可以提高算法执行效率。

统计模块203，用于采用线性扫描统计方法评价交通流不平衡模式的统计显著性。

计算模块204，用于基于模式相似性计算获得所述交通流不平衡模式的动态演化，即频发模式与偶发模式。

基于本发明，可以实现城市交通流不平衡模式的挖掘，有助于全面检测和评价城市道路交通运行状况，结合城市功能区与城市设施对不平衡模式的产生原因进行分析，可为城市出行与交通规划提供一定的借鉴。

本发明说明书中使用的术语和措辞仅仅为了举例说明，并不意味构成限定。本领域技术人员应当理解，在不脱离所公开的实施方式的基本原理的前提下，对上述实施方式中的各细节可进行各种变化。因此，本发明的范围只由权利要求确定，在权利要求中，除非另有说明，所有的术语应按最宽泛合理的意思进行理解。