考虑空间结构特征的大规模路网时空交通状态表达与分析方法

摘要

本发明提供一种结合路网空间结构对大规模路网交通状态进行精简及时空特征挖掘的分析方法，首先建立大规模路网高维度交通状态表达矩阵，并结合图论相关思想建立空间结构表达矩阵，然后通过改进的NMF算法结合上述路网空间结构信息对路网交通状态进行精简，最后针对低维度的精简空间，深入挖掘路网交通状态的时空特征，并进行可视化表达。本发明提出的方法具有新颖，高效，解释性强等优点，不但可以在低维度空间中反映出整个路网交通状态的变化特征，还可对精简后路网交通状态进行深入的时间演化分析和空间结构分析，为大规模路网的交通状态的表达和时空特征挖掘提供了一种有效的方法。

说明书

技术领域

本发明涉及大规模路网交通状态表达及交通状态时空特征挖掘领域。

背景技术

城市道路交通拥堵问题已经严重影响到社会经济活动和人们的日常生活，准确把握城市道路交通状态的时空变化特征是交通管理者优化交通管控方案和改造道路设施以缓解拥堵的重要基础。以往大多数对城市道路交通状态的研究集中在单一路口或某些路段，采用仿真数据、感应线圈数据、车牌识别数据等通过微观仿真、统计模型构建以及数据驱动的相关算法，从微观中观层面对交叉口、快速路或主干道进行交通状态分析，这些研究方式虽具有精确性和高效性，但未深入涉及大规模城市路网交通状态的复杂性，无法把握其时空特征，不利于对整个城市交通状况的宏观管控。近年来，随着通讯技术的快速发展，利用车载GPS设备以一定的时间间隔返回交通流参数的浮动车数据，在时间空间维度覆盖范围都很广，对于从宏观层面把握城市路网交通状态具有很强的适用性，为路网层级的研究提供了很好的数据支持，也逐渐成为大规模路网研究中主要且广泛应用的数据源。但由于城市路网的交通状态始终随着时间在空间上不断变化，呈现出高度的动态、随机、复杂性，获得的交通流时空数据具有多源、多维、海量、多尺度、多时相等性质，同时也为大规模路网的交通状态分析带来了新的挑战。

针对上述海量高维的大规模路网交通数据分析问题，部分研究利用数据驱动的方法，在保留路网足够多的信息的基础上，对路网交通状态高维数据进行精简，以便在低维空间中挖掘交通状态的时空演化特征。然而，目前对精简空间的分析侧重于路网交通状态的表达、在低维空间中对拥堵特征的识别，以及交通状态的时间演化规律，很少能结合路网的空间结构对精简过程进行优化，致使在一定程度上缺乏利用精简空间对路网交通状态的空间结构特征解读的能力。

发明内容

本发明的目的是为了解决上述现有方法的不足，在考虑到路网空间信息的同时对高维度的交通状态数据进行精简，提供了一种可以结合路网空间结构对大规模路网交通状态进行表达及时空特征挖掘的分析方法，相应分析结果对交通管理者进行宏观调控具有一定的指导作用。

为达到上述目的，本发明采用了以下技术方案：

一种结合路网空间结构对大规模路网交通状态进行精简及时空特征挖掘的分析方法，包括下列步骤：

1)大规模路网全局交通状态的表达。

通过浮动车返回数据，建立路网全局交通状态的表达矩阵。

2)构建路网空间结构表达模型。

考虑目标路段所属道路等级的上下游相接路段对其交通状态的影响，构建空间结构模型。

3)路网全局交通状态的精简。

利用上述空间结构模型优化NMF非负矩阵分解算法，对路网全局交通状态进行精简。

4)时空特征挖掘。

基于上述精简的路网全局交通状态，在低维空间中进行聚类分析及可视化，挖掘大规模路网交通状态的时间演化规律和空间结构特征。

本发明的优点在于：

(1)从宏观角度出发，将大规模路网看作一个整体进行分析，相比于以往通过对单个交叉口或某一路段的分析上升到大规模路网的研究，弥补了其无法把握路网时空变化特征复杂性及内在关联性的缺点。

(2)克服了大规模路网交通状态数据量大、维数高对分析手段的限制，基于改进的NMF算法对全局交通状态进行低维展示，在保证保留足够时空信息的同时，降低了计算分析的难度、成本和复杂性。

(3)创新性的将路网空间结构信息建模到NMF算法中进行优化，解决了目前针对大规模路网交通状态研究的主流算法，缺乏在精简空间的基础上对空间结构特征进行解读的能力的局限性。

(4)相比传统的分析方法，本发明对大规模路网交通状态的时空特征分析结合了路段的道路等级，对路网拥堵的研究具有一定的针对性，在实现对路网时空交通状态进行深入解读的同时，不但有利于交通管理者对大规模路网进行宏观调控，还有利于进行精确的拥堵治理。

附图说明

图1为本发明的方法流程示意图；

具体实施方式

下面结合附图和实施例对本发明做进一步说明。

本发明是一种结合路网空间结构对大规模路网交通状态进行精简及时空特征挖掘的分析方法，流程如图1所示，包括以下几个步骤：

1.大规模路网交通状态的表达。

本发明选取北京市三环内大规模路网为例进行说明，该路网共包含14990个路段，研究整个路网一个工作日(201*年6月1日)交通状态的时空变化特征。

利用装有GPS设备的浮动车以2分钟为间隔返回的每个路段的速度数据作为输入。对于每个路段i，用V_it表示其在时间戳t代表的2分钟内的平均速度。为了更准确的表征交通状态，将路段i在时段t内的实际平均速度V_it与自由流速度V_fi的比值记为F_it，并定义为路段畅行指数，值越接近于1表示路段越畅通，值越小则表示拥堵情况越严重，公式如下：

由此，网络层面的交通状态即可定义为由m个路段，n个时间戳的交通状态构成的一个高维向量。由F_it表示路段i在t时段的交通状态，则路网的全局交通状态可定义为如下所示的m×n高阶矩阵X。

根据前文，北京市三环内路网的全局交通状态则可定义为由14990个路段、720个时间序列(2分钟为间隔)组成的14990×720阶矩阵，将其作为改进NMF算法的输入矩阵之一。

2.构建路网空间结构表达模型

路网的全局交通状态由每个路段交通状态的时空组合表示，每个路段的交通状态在空间上存在一定的关联性，一个指定路段的交通状态会受其上下游相接路段交通状态的影响，不同道路等级路段之间又存在一定的差异。为了在把握路网整体交通状态的同时充分考虑空间结构对其产生的重要影响，本发明结合了图论中的相关思想构建路网的空间结构模型。

在数学领域，图论中的图定义为由若干给定的点及点之间的连接线所构成的图形，通常用来描述某些事物之间的内在联系或某种特定关系。针对于大规模路网的空间结构建模，本具体实施方式中将每个路段作为图论中的节点，那么节点之间的连接线则代表着相连接路段之间的空间结构关系，利用图论中的邻接矩阵概念来表达路网之间的空间结构。

在图论和计算机科学中，邻接矩阵作为表达图中结构的方式，只存在1和0两个值，代表着图中节点连接与否，且主对角线均为0，对于简单无向图又为对称阵。那么在大规模路网中，对于一个给定的路段，假设其交通状态只和与其隶属同一道路等级的上下游路段相关，将其赋值为1，其余均设置为0，即可得到路网空间结构的一个简单表达矩阵，该矩阵为主对角元素均为0的对称方阵，且为稀疏矩阵。那么对于包含m个路段的路网，其空间结构的表达矩阵则记为A_m×m，路段i和j的空间结构关系用A_ij表示，其表达式为：

对于北京市三环路网，道路等级主要分为四个部分，二三环快速路、主干路、辅路及次干路、支路，首先将每个路段所属道路等级进行匹配，然后提取出相邻路段，得到包含路网空间结构的m阶方阵A_m×m，作为改进NMF算法的另一输入矩阵。

3.路网全局交通状态的精简。

在此部分，本具体实施方式基于上述空间结构信息对NMF算法进行改进，利用改进的NMF算法对大规模路网的全局交通状态进行精简。所述NMF算法，即非负矩阵分解算法，作为一种半监督学习算法，其核心思想是将一个目标矩阵X分解成两个非负子矩阵W和H。即给定一个由n个样本及每个样本的m维特征向量构成的m×n阶非负矩阵X，将其作为输入，然后通过迭代过程地不断计算，将输入矩阵分解为m*s阶和s*n阶的两个非负矩阵W和H，使其最大化地近似输入矩阵X，即：

X_m×n≈W_m×s·H_s×n

通过该矩阵分解，输入矩阵X中每个样本的m维特征向量可近似为矩阵H相应列中分量加权后的矩阵W中s列的线性组合，即x≈Wh。通常，变量s要取一个极小于n和m两者的值，使得矩阵H代表着输入数据的一个精简化的低维表示，以便进一步的数据分析。

对应在本发明中，输入矩阵即对应着路网的全局交通状态X，其维数等于路段的数目m，将时间序列作为n个样本，每个样本的特征向量由路段代表的m维列向量组成，通过改进的NMF算法，得到由n个s维特征向量构成的子矩阵H，则H即代表着路网全局交通状态的一个低维表示形式。为了实现这一目标，首先需要定义损失函数，来定量计算矩阵X和两个子矩阵的近似程度。使用欧几里德距离来定义两个非负矩阵A、B之间的相似性:

在此基础上，本发明结合路网的空间结构给出了自定义损失函数C的计算公式：

其中，W为m*s阶参数矩阵，H为s*n目标矩阵，A为第二步定义的路网空间结构表示矩阵，λ为调节参数，范围在0到1之间。公式分为两个部分：第一部分为非负矩阵分解的损失计算，值越小，表明目标矩阵包含的路网交通状态信息与输入矩阵越相似；第二部分为参数矩阵的修正损失计算，通过将空间结构矩阵与参数矩阵相乘，相当于将每个路段的空间结构信息作为权重，对其参数矩阵的特征向量进行加权，目的是在保留相邻路段的交通状态特征对其影响的情况对参数矩阵进行修正。值越小，则表明参数矩阵的修正度越高。

但不能直接利用矩阵A对参数矩阵进行修正。原因有二：1.由于矩阵A的主对角元素为0，参数矩阵W与空间结构矩阵A相乘会忽略路段本身的性质。2.使用矩阵A进行简单相乘来修正W会加大特征向量的规模，脱离参数矩阵W中原始数据值的范围，计算欧几里得距离误差很大。所以需要对空间结构矩阵A进行标准化，标准化过程如下：

1.使用单位矩阵I对空间结构矩阵A进行修正，即：

2.引入图论中的度矩阵D对A进行标准化，度矩阵为对角矩阵，在图论中定义为每个节点的连接边数目，即邻接矩阵的行元素之和。本发明中，对角矩阵的主对角元素即为修正后的空间结构矩阵的行元素之和,通过的标准化过程将每一行和列的元素之和归为1。

这样，上述自定义损失函数的求解过程即为求最小化问题：

s.t.W≥0，H≥0

为了找到上述优化问题的最优解，并在计算过程中保证非负，训练过程中使用乘法更新规则，公式如下：

基于上述更新规则，在使损失函数最小的情况下，找到一组既考虑了路网空间结构信息，又对原始矩阵有较高表达性的参数矩阵W和目标矩阵H，其中H即代表着精简后的路网全局交通状态，其维度相对于原始数据有了极大的降低，更有利于处理与分析。

4.时空特征挖掘。

基于上述精简的路网全局交通状态，采用K-means算法进行聚类分析，挖掘大规模路网交通状态的时间演化规律和空间结构特征。下面结合北京市三环路网作说明：

基于上述算法过程，将得到s*720阶的目标矩阵H，代表着北京三环内路网交通状态的一个低维表示，保留了以2分钟为间隔的时间戳信息。由于s为用户设定参数，为了便于展开对精简后交通状态的分析和可视化，将主要围绕三维空间对其所包含的路网交通状态信息进行分析。在三维空间中，输入数据往往依据交通状态在时间层面或空间层面的不同性质呈现出集聚或分簇的现象，为深入挖掘其中隐含的路网交通状态的时空特征，将H作为K-means聚类算法的输入，得到在时间层面具有相似交通状态的几个聚类，结合在三维空间的可视化即可表达路网交通状态的时间演化特征。

在时间演化分析的基础上，得到每个道路等级的交通状态的拥堵时段，然后对拥堵时段中的拥堵路段结合Arcgis进行可视化表达，并对比分析不同道路等级拥堵状态的空间结构分布，确定大规模路网的瓶颈路段，为交通管理者优化交通管控方案和改造道路设施以缓解拥堵提供一定的理论依据。