本发明公开了一种基于归一化谱聚类算法的城市快速路交通状态估计方法，包括以下步骤：(1)对获取的城市快速路GPS数据进行预处理；(2)选定城市快速路交通运行状态的参数数据；(3)利用归一化谱聚类算法对交通流特征参数进行聚类划分并输出聚类结果确定交通估计状态；(4)利用轮廓系数SC对归一化谱聚类算法效果进行评价。本发明基于归一化谱聚类算法，通过引入新的速度离散概念和归一化拉普拉斯矩阵，能更加准确地对城市快速路交通状态进行精准估计，并在估计之后采用轮廓系数SC对整个估计结果进行效果评价，更完成整个估计过程。
1.基于归一化谱聚类算法的城市快速路交通状态估计方法，其特征在于：该方法包括以下步骤：(1)获取城市快速路GPS数据并进行预处理：包括去除冗余数据，GPS数据时间排序，地图匹配，数据选取处理；
(2)进行交通参数选定：计算目标路段的平均速度，速度离散度，作为交通状态估计的表征参数；
(3)将表征参数平均速度和速度离散度作为二维数据点，利用归一化谱聚类算法对数据点进行聚类分析；
(4)运用轮廓系数对聚类效果即交通状态估计效果进行评价，比较每个聚类簇中轮廓系数均值的最大值即得到最终的聚类评价效果；
步骤(2)中，按照以下公式计算某一时间段内的速度离散度：其中，Vdt表示t时间内的车速离散度；n表示t时间内的目标车辆数；vi表示车速； 表示t时间内的平均速度；σ1表示t时间内的速度标准差；
步骤(3)中，利用归一化谱聚类算法对选取的表征参数进行聚类划分，步骤如下：(3‑1)定义谱聚类算法和交通状态估计之间的关系：定义数据集S＝(G,E)，其中 表示相关点，即数据点，E是点与点之间的边，用于描述两个数据点之间的相关关系，用相似度wij表示边的权重；
(3‑2)确定图论划分准则为多路NCUT切图：将目标数据集划分为k个集合，使得子簇间的相似度最小，子簇内的相似度最大；构造目标函数如下：其中， 表示集合Ai与其补集 之间的关系，具体表示为Ai与其补集 之间的相似度 vol(Ai)表示隶属集合Ai的所有数据点的权重之和；
(3‑3)使用n维空间中的欧几里得距离和高斯核函数定义数据点间的相似度wij，其公式如下：wij＝wji；
其中，w(Xi,Xj)表示第i,j个数据点Xi,Xj之间的相似度， σ2是高斯核函数的核；
(3‑4)使用全连接法构建邻接矩阵W，wij是矩阵W中的元素：(3‑5)定义每一个数据点和与它相联的所有边的相似度之和di，公式如下：(3‑6)构建对角矩阵D，公式如下：
(3‑7)构建归一化拉普拉斯矩阵Lsym，公式如下：‑1/2 ‑1/2 ‑1/2 ‑1/2Lsym＝D LD ＝E‑D WD
其中，L＝D‑W，E表示单位向量；对于Lsym，0是其最小的特征向量且对应的特征值是D2
(3‑8)计算矩阵Lsym的特征向量和对应的特征值，按照特征值从小到大的顺序选择k个最小特征值和其对应的特征向量；k个特征向量构成矩阵U；
(3‑9)对矩阵U的每一行进行归一化处理得到矩阵N，表示如下：其中，Nij是矩阵N中的元素，uij是矩阵U中的元素；
(3‑10)将行向量ni∈N作为K‑means算法的聚类中心，利用K‑means算法进行聚类，获得聚类结果C1,C2,…,Ck，其中每一种聚类结果包含的数据点集合表示为A1,A2,...,Ak；
步骤(4)中，运用轮廓系数SC对归一化谱聚类算法效果进行评价，具体步骤如下：(4‑1)计算聚类之后每个簇内数据点的轮廓系数，具体公式如下：m m
其中，Si表示第i个簇内第m个数据点的轮廓系数，‑1
(4‑2)计算每个簇内轮廓系数Si的均值 并比较k个簇中轮廓系数均值的最大值即得到最终的聚类评价效果SC：其中 表示第k个簇内所有数据点的轮廓系数的均值。
基于归一化谱聚类算法的城市快速路交通状态估计方法
技术领域
[0001] 本发明涉及智能交通状态估计领域，尤其涉及一种基于归一化谱聚类算法的城市快速路交通状态估计方法。
背景技术
[0002] 城市快速路是城市的快速交通走廊，设置中央分割带减少对向车流干扰，全部或部分采用立体交叉与控制出入，使得进入快速路的车辆能够安全、快速、高效地行驶。城市快速路巨大的服务潜力也对其自身的服务能力提出了更高的要求，对城市快速路交通状态的精准估计可以为道路管理人员和旅行者提供更有效和精确的信息，进行交通管控和路线优化，减少旅行者交通出行时间成本、提升城市综合交通运行效率。
[0003] 交通状态即指交通流的总体运行状况，交通状态与交通流参数之间是一种映射关系，随着交通状态的不断变化，交通流特征参数也随之变化，对于不同的交通流参数特征，也对应不同的道路交通状态。在大部分的研究中，往往采用平均速度，流量，占有率等参数，借助这些参数衡量交通状态的近似范围。在实际道路条件下，平均速度衡量的是整个路段的整体情况，但是交通流中车辆之间的速度都存在差异，便产生车速的离散现象，尤其是差异较为明显时这种现象就更加显著，研究中使用车速离散度进行描述。由车速离散现象引发的加速、减速以及超车和变道行为，显著地改变了整个交通状态，使交通流从稳定趋向紊乱。所以将车速离散度作为交通状态表征参数能更全面地反应交通状态和交通参数之间的关系，也能精准对交通状态进行估计。
发明内容
[0004] 发明目的：针对宏观交通流参数难以精确反映单个车辆对交通运行的作用，从而影响整个交通状态估计结果准确性的问题，本发明提出一种基于归一化谱聚类算法的城市快速路交通状态估计方法，实现对交通状态更精确的估计。
[0005] 技术方案：为实现本发明的目的，本发明所采用的技术方案是：一种基于归一化谱聚类算法的城市快速路交通状态估计方法，包括以下步骤：
[0006] (1)获取城市快速路GPS数据并进行预处理：包括去除冗余数据，GPS数据时间排序，地图匹配，数据选取处理；
[0007] (2)进行交通参数选定：计算目标路段的平均速度，速度离散度，作为交通状态估计的表征参数；
[0008] (3)将表征参数平均速度和速度离散度作为二维数据点，利用归一化谱聚类算法对数据点进行聚类分析；
[0009] (4)运用轮廓系数对聚类效果即交通状态估计效果进行评价，比较每个聚类簇中轮廓系数均值的最大值即得到最终的聚类评价效果。
[0010] 进一步的，所述步骤(2)中，按照以下公式计算某一时间段内的速度离散度：
[0011]
[0012] 其中，Vdt表示t时间内的车速离散度；n表示t时间内的目标车辆数；vi表示车速；表示t时间内的平均速度；σ1表示t时间内的速度标准差。
[0013] 进一步的，所述步骤(3)中，利用归一化谱聚类算法对选取的表征参数进行聚类划分，步骤如下：
[0014] (1)定义谱聚类算法和交通状态估计之间的关系：
[0015] 定义数据集S＝(G,E)，其中 表示相关点，即数据点，E是点与点之间的边，用于描述两个数据点之间的相关关系，用相似度wij表示边的权重；
[0016] (2)确定图论划分准则为多路NCUT切图：
[0017] 将目标数据集划分为k个集合，使得子簇间的相似度最小，子簇内的相似度最大；构造目标函数如下：
[0018]
[0019] 其中， 表示集合Ai与其补集 之间的关系，具体表示为Ai与其补集 之间的相似度 vol(Ai)表示隶属集合Ai的所有数据点的权重之和；
[0020]
[0021] 其中，n表示集合Ai的数据点数；
[0022] (3)使用n维空间中的欧几里得距离和高斯核函数定义数据点间的相似度wij，其公式如下：
[0023]
[0024] 其中，w(Xi,Xj)表示第i,j个数据点Xi,Xj之间的相似度， σ2是高斯核函数的核；
[0025] (4)使用全连接法构建邻接矩阵W，wij是矩阵W中的元素：
[0026]
[0027] (5)定义每一个数据点和与它相联的所有边的相似度之和di，公式如下：
[0028]
[0029]
[0030] (6)构建对角矩阵D，公式如下：
[0031]
[0032] (7)构建归一化拉普拉斯矩阵Lsym，公式如下：
[0033] Lsym＝D‑1/2LD‑1/2＝E‑D‑1/2WD‑1/2
[0034] 其中，L＝D‑W，E表示单位向量；对于Lsym，0是其最小的特征向量且对应的特征值是‑1/2D E；
[0035] (8)计算矩阵Lsym的特征向量和对应的特征值，按照特征值从小到大的顺序选择k个最小特征值和其对应的特征向量；k个特征向量构成矩阵U；
[0036] (9)对矩阵U的每一行进行归一化处理得到矩阵N，表示如下：
[0037]
[0038] 其中，Nij是矩阵N中的元素，uij是矩阵U中的元素；
[0039] (10)将行向量ni∈N作为K‑means算法的聚类中心，利用K‑means算法进行聚类，获得聚类结果C1,C2,…,Ck，其中每一种聚类结果包含的数据点集合表示为A1,A2,...,Ak。
[0040] 进一步的，所述步骤(4)中，运用轮廓系数SC对归一化谱聚类算法效果进行评价，具体步骤如下：
[0041] (1)计算聚类之后每个簇内数据点的轮廓系数，具体公式如下：
[0042]
[0043] 其中，Sim表示第i个簇内第m个数据点的轮廓系数，‑1
[0044]
[0045]m
[0046] (2)计算每个簇内轮廓系数Si的均值 并比较k个簇中轮廓系数均值的最大值即得到最终的聚类评价效果SC：
[0047]
[0048] 其中 表示第k个簇内所有数据点的轮廓系数的均值。
[0049] 有益效果：与现有技术相比，本发明的技术方案具有以下有益的技术效果：
[0050] 在大部分的研究中，往往采用平均速度，流量，占有率等宏观参数衡量交通状态的近似范围，本发明将速度离散度引入考虑范围能从单个车辆的角度表征微观情况对整体的反应，也是对宏观交通参数的补充，更合理地表达不同层次的参数对状态的作用，从而精确地完成交通状态估计；谱聚类算法是近些年机器学习领域的热门研究问题，归一化谱聚类能收敛于全局最优解和实现简单的同时能提供不同于非规划谱聚类的特征向量，实现更好的估计效果。
[0051] 本发明的基于归一化谱聚类算法的城市快速路交通状态估计方法，将以实际的出租车GPS检测到交通数据作为基础数据，以定义的速度离散度和平均速度作为表征参数，根据交通状态划分原则，即每种交通状态下速度和离散度的相似程度，利用归一化谱聚类算法实现不同交通状态之间表征参数差异最大，相同交通状态中表征参数最相近，最终实现城市快速路交通状态更加精确的估计。
附图说明
[0052] 图1是本发明方法流程图；
[0053] 图2是GPS数据处理流程图；
[0054] 图3是归一化谱聚类算法图。
具体实施方式
[0055] 下面结合附图和实施例对本发明的技术方案作进一步的说明。
[0056] 本发明所述的基于归一化谱聚类算法的城市快速路交通状态估计方法，采用了定义的速度离散度和归一化谱聚类方法，用于克服宏观交通流参数难以精确反映单个车辆对交通运行的作用，从而影响整个交通状态估计结果准确性的问题，以及对非归一化谱聚类算法的改进问题，具体流程如图1所示，包括以下步骤：
[0057] (1)获取城市快速路GPS数据并进行预处理：包括去除冗余数据，GPS数据时间排序，地图匹配，数据选取处理；本实施例数据处理流程如图2；
[0058] (2)进行交通参数选定：计算目标路段的平均速度，速度离散度，作为交通状态估计的表征参数；
[0059] (3)将表征参数平均速度和速度离散度作为二维数据点，利用归一化谱聚类算法对数据点进行聚类分析；
[0060] (4)运用轮廓系数对聚类效果即交通状态估计效果进行评价，比较每个聚类簇中轮廓系数均值的最大值即得到最终的聚类评价效果。
[0061] 所述步骤(2)中，按照以下公式计算某一时间段内的速度离散度：
[0062]
[0063] 其中，Vdt表示t时间内的车速离散度；n表示t时间内的目标车辆数；vi表示车速；表示t时间内的平均速度；σ1表示t时间内的速度标准差。
[0064] 所述步骤(3)中，利用归一化谱聚类算法对选取的表征参数进行聚类划分，算法流程如图3所示，步骤如下：
[0065] (1)定义谱聚类算法和交通状态估计之间的关系：
[0066] 定义数据集S＝(G,E)，其中 表示相关点，即数据点，E是点与点之间的边，用于描述两个数据点之间的相关关系，用相似度wij表示边的权重；
[0067] (2)确定图论划分准则为多路NCUT切图：
[0068] 将目标数据集划分为k个集合，使得子簇间的相似度最小，子簇内的相似度最大；构造目标函数如下：
[0069]
[0070] 其中， 表示集合Ai与其补集 之间的关系，具体表示为Ai与其补集 之间的相似度 vol(Ai)表示隶属集合Ai的所有数据点的权重之和；
[0071]
[0072] 其中，n表示集合Ai的数据点数；
[0073] (3)使用n维空间中的欧几里得距离和高斯核函数定义数据点间的相似度wij，其公式如下：
[0074]
[0075] 其中，w(Xi,Xj)表示第i,j个数据点Xi,Xj之间的相似度， σ2是高斯核函数的核；
[0076] (4)使用全连接法构建邻接矩阵W，wij是矩阵W中的元素：
[0077]
[0078] (5)定义每一个数据点和与它相联的所有边的相似度之和di，公式如下：
[0079]
[0080]
[0081] (6)构建对角矩阵D，公式如下：
[0082]
[0083] (7)构建归一化拉普拉斯矩阵Lsym，公式如下：
[0084] Lsym＝D‑1/2LD‑1/2＝E‑D‑1/2WD‑1/2
[0085] 其中，L＝D‑W，E表示单位向量；对于Lsym，0是其最小的特征向量且对应的特征值是‑1/2D E；
[0086] (8)计算矩阵Lsym的特征向量和对应的特征值，按照特征值从小到大的顺序选择k个最小特征值和其对应的特征向量；k个特征向量构成矩阵U；
[0087] (9)对矩阵U的每一行进行归一化处理得到矩阵N，表示如下：
[0088]
[0089] 其中，Nij是矩阵N中的元素，uij是矩阵U中的元素；
[0090] (10)将行向量ni∈N作为K‑means算法的聚类中心，利用K‑means算法进行聚类，获得聚类结果C1,C2,…,Ck，其中每一种聚类结果包含的数据点集合表示为A1,A2,...,Ak。
[0091] 所述步骤(4)中，运用轮廓系数SC对归一化谱聚类算法效果进行评价，具体步骤如下：
[0092] (1)计算聚类之后每个簇内数据点的轮廓系数，具体公式如下：
[0093]
[0094] 其中，Sim表示第i个簇内第m个数据点的轮廓系数，‑1
[0095]
[0096]
[0097] (2)计算每个簇内轮廓系数Sim的均值 并比较k个簇中轮廓系数均值的最大值即得到最终的聚类评价效果SC：
[0098]
[0099] 其中 表示第k个簇内所有数据点的轮廓系数的均值。
