基于改进FCM聚类算法的高速公路交通状态识别

余 庆，胡 尧,2

（1.贵州大学数学与统计学院，贵州 贵阳 550025；2.贵州省公共大数据重点实验室，贵州 贵阳 550025）

0 引言

随着经济的快速发展，我国汽车保有量不断增加，交通拥堵问题不断加剧。交通状态的分类识别能从整体上反映道路的交通状况，有助于交通管理部门制定相应的拥堵缓解措施或为出行者推荐合理的出行路线。同时，准确的交通状态识别和描述对于道路交通的智能化发展及解决道路交通拥堵、提高路网服务水平等至关重要，因此有必要对其进行深入研究。

国内外学者主要基于交通参数[1-2]、图像特征[3]、高空视频[4]等对道路交通状态进行识别。如Ricardo 等[5]结合道路间的空间相关性，基于K-均值（K-Means）聚类算法实现日常交通模式的识别；Bae 等[6]基于交通密度数据，采用Gaussian 混合模型识别高速公路交通状态，并检测交通相位的变化；郭海涛[3]基于交通区域特定的图像特征来识别交通拥堵状态；彭博等[4]基于三维卷积神经网络——深度神经网络方法，采用高空视频数据对道路交通状态进行识别和预测。由于交通状态具有模糊性和不确定性，近年来模糊理论方法在交通状态识别领域得到广泛应用，如陈忠辉等[7]应用模糊C 均值（Fuzzy C-Means,FCM）聚类算法分析历史交通流，并结合随机森林算法预测短时交通状态；陈钊正等[8]基于K-Means 算法和FCM 算法，给出适合高速公路特点的交通状态划分方法和关键参数。

在用聚类分析法进行交通状态识别的过程中，不同分类指标对聚类分析结果的影响程度不同，为提高交通状态识别的有效性，研究人员探索对分类指标进行赋权[9-10]，如王宇俊等[11]对宏观交通参数的权重分配进行多次实验，并通过比较误判率从中选取最优的权重分配方案；于泉等[12]利用单一赋权法和组合赋权法确定交通状态评价指标的权重，并结合K-Means 算法与隶属度函数，将城市交叉口的交通状态划分为畅通、轻微拥挤、拥挤、严重拥挤4 种类别，结果表明组合赋权法的聚类结果比单一赋权法更精确、稳定。

综上，当前交通状态识别研究已取得一些比较有效的成果，但整体上存在以下不足：分类指标偏于单一，对交通状态的描述不够全面、不够准确；缺乏关于不同样本对交通状态识别影响的分析。鉴于此，本文选用多个交通状态分类指标，利用熵权法确定分类指标权重，同时结合样本权重对FCM 算法进行改进，并以美国加州某高速公路交通数据为例对改进FCM 算法的聚类效果和运行效率进行验证[13]。

1 交通状态分类指标

本文选取交通流量、空间占有率、平均速度和路网充裕度作为交通状态分类指标。交通流量、空间占有率、平均速度都是描述道路交通流的基本参数，是交通运行效率评价、交通状态判别、交通安全分析、交通事故鉴定等的重要指标。空间占有率指所有车道在5min内的平均占有率，取值区间为[0,1]。路网充裕度定义为路段i在t时刻的剩余交通流量与饱和交通流量的比值，描述路网资源在空间上的剩余程度，用来反映路网资源在空间上的可利用率，能为交通拥堵疏导提供依据[14]。路网充裕度可根据交通流实时数据计算得到[15]：

式（1）中：ρit为路段i在t时刻的路网充裕度；qimax为通过路段i的饱和交通流量；qit为路段i在t时刻的交通流量；qimax-qit为路段i在t时刻的剩余交通流量。

2 交通状态识别算法

2.1 传统FCM聚类算法

聚类分析是一种无监督的分类方法[16]，能将没有分类标签的数据集分为若干个簇。FCM 聚类算法是一种常用的聚类分析方法，主要用于将多维空间数据分为一定的类别，其基本思路是将聚类问题转化为数学问题，然后利用样本分类的相关方法求解。通常，样本集X={x1,x2,…,xn}可按一定的准则划分为c个模糊集（其中c为预先给定的类别数），然后确定各类别的聚类中心，使目标函数最小化。

交通状态识别的FCM 聚类算法目标函数计算公式[15]为：

式（2）～式（3）中：F(U,V)为目标函数；U为隶属度矩阵；V为聚类中心矩阵；c为聚类数；n为样本数；d为分类指标数；uij∈U为第i个样本对第j个交通状态类别的隶属度；∂为加权指数，表示模糊度；xim为第i个样本在第m个分类指标下的取值；vjm∈V为第m个分类指标在第j个交通状态类别下的聚类中心。

在目标函数中引入拉格朗日乘子，并求偏导，令其等于0，从而得到参数的迭代解[15]：

式（4）中：vhm为第m个分类指标在第h个交通状态类别下的聚类中心。

2.2 改进的FCM聚类算法

聚类过程中，聚类中心周围的样本数据往往分布不均匀，各数据对聚类结果的贡献可能存在较大差异，同时每个分类指标对聚类的影响也有所不同。传统的FCM 聚类方法将所有指标和样本对聚类结果的影响都视为同等重要，可能会导致算法无法取得较好的聚类效果。本文采用信息熵[17-18]对每个分类指标赋予不同的权重，同时采用样本加权的方法克服样本分布不均匀对聚类的影响，从而加快聚类的收敛速度。

2.2.1 熵权法

熵权法可以对样本数据携带的信息进行量化，通过引入权重使聚类结果更加客观真实。应用熵权法对分类指标赋权时，指标的熵权越大，说明其对聚类结果的影响越大，反之对聚类结果的影响越小。熵权法的计算步骤如下。

（1）归一化处理。为避免不同指标之间的量纲不同，首先采用极差法对数据进行归一化处理[12]：

式（6）中：yim为第i个样本在第m个分类指标下的归一化值；xi为第i个样本。

（2）计算熵值。利用归一化处理所得数据，计算第m个分类指标的熵值Em[12]：

（3）计算每个交通状态分类指标的权重大小。利用熵值确定第m个分类指标的权重wm[12]：

2.2.2 样本加权

为减小甚至消除噪声和离群数据对聚类结果的影响，通常对这两种数据赋予较小的权重。对于给出的数据样本，其权重计算公式[18]为：

式（9）中：ti为第i个样本的权重；为改 进FCM 算法中第i个样本对第j个交通状态类别的隶属度；为第i个样本与第j个类别中心的加权距离。

显然，样本权重的大小与样本到各聚类中心的距离有关，故将样本权重计算也纳入算法迭代过程。不过其缺点是权重对聚类中心较敏感，聚类中心越精确，权重计算就越合理，如果聚类中心偏离真实中心，得到的样本权重则会存在偏差。K-Means 聚类算法是一种经典的聚类算法，能简单、快速地对数据进行类别划分，故本文首先应用K-Means 聚类算法选取初始聚类中心，以避免样本权重偏差。

2.2.3 改进FCM聚类算法的迭代解

将通过信息熵和样本权重改进后的FCM 算法的目标函数定义为：

同样可以得到隶属度和聚类中心的迭代解，分别为：

式（10）～式（12）中：F′(U′,V′)为改进FCM 算法的目标函数；U′为改进FCM 算法的隶属度矩阵；V′为改进FCM 算法的聚类中心矩阵；表示第i个样本与第h个类别中心的加权距离；∈V′为改进FCM 算法中第m个分类指标在第j个交通状态类别下的聚类中心；其他变量意义同前。

可见，改进后的FCM 聚类算法综合考虑了聚类过程中每个样本点的不同贡献和每个特征的不同重要性。

2.3 交通状态识别流程

将改进后的FCM 算法应用于高速公路交通状态识别，具体流程如图1所示。

图1 交通状态识别流程图

3 高速公路交通状态识别

为验证改进FCM 算法的聚类效果，本文选取美国加州高速公路交通数据集[13]实现交通状态识别。该数据为每30s 实时采集一次，由加州运输局性能测量系统（Performance Measurement Sys⁃tem,PeMS）聚合成间隔为5min 的连续数据，包含交通流量、空间占有率、平均速度等监测数据，适用于交通数据分析与状态识别及不同方法的比较。本文选取数据采集点VDS 311974,VDS 312139 及VDS 319129 的10 个工作日（2020年7月6日0:00—2020年7月10日23:55和2020年7月13日0:00—2020年7月17日23:55）的高速公路数据。对交通参数（包括每5min交通流量、空间占有率、平均速度和路网充裕度）进行可视化，如图2～图5所示，其中路网充裕度由式（1）计算得到。由图可知，同一采集点的交通数据在一天内会发生多次变化且每日变化规律大致相同，其中交通流量和空间占有率曲线走势相同，平均速度和路网充裕度曲线则朝相反方向变化。此外，VDS 311974 和VDS 312139 数据集在各分类指标下的变化范围相差不大，而VDS 319129数据集的交通流量指标变化幅度较小，其最大流量仅为前两个数据集的1/3。可见，不同采集点的交通数据可能表现出不同的变化规律，该数据适用于交通状态分类识别。

图2 交通流量时序图

图3 空间占有率时序图

图4 平均速度时序图

图5 路网充裕度时序图

根据文献[8]中的分类级别，将高速公路道路交通状态分为7个等级，即畅通、较畅通、平稳、较平稳、较拥挤、拥挤及阻塞。表1 列出了采集点VDS 311974 的聚类中心及各类交通状态的样本数。可以看出，就样本数而言，属于畅通的最多，其次是较拥挤和较平稳，属于阻塞的最少。

表1 FCM聚类中心（VDS 311974）

为验证改进后FCM 算法的聚类效果，现用其进行高速公路交通状态识别。首先采用熵权法计算交通状态分类指标的权重。各分类指标在不同数据集下的信息熵权重如表2 所示。可以看出，在不同数据集中，同一指标对应的熵权不同；3个数据集中，空间占有率的熵权最大，平均速度的熵权最小，这表明在本文所选数据中，空间占有率对聚类结果的影响最大，而平均速度对聚类结果的影响最小。

表2 分类指标熵权值

接着，计算不同数据集的交通状态分类样本数及占比，如表3所示。可以看出，3个数据集中属于畅通状态的样本数最多，占比分别为21.15%,21.25%和24.93%；其次是较拥挤状态。此外，前两个数据集中属于阻塞状态的样本数最少，占比分别为5.94%和9.26%，而第3个数据集中属于拥挤状态的样本数最少，占比为4.03%。这进一步表明不同道路的划分情况有所不同，应根据道路的实际情况来划分交通状态等级。

表3 交通状态分类样本数及占比

最后，比较传统FCM 算法与改进后FCM 算法的目标函数值、迭代次数及运行时间，所得结果如表4 所示。可以看出，所有数据集中改进FCM 算法的目标函数值都明显小于传统FCM 算法的目标函数值，3 个数据集的目标函数值分别减小了75%,74.95%和75.38%，符合目标函数值越小，聚类效果越好的思想。此外，所有数据集中改进后的FCM 算法迭代次数更少，运行时间更短。可见，改进后的FCM 算法在聚类效果和运行效率方面均优于传统FCM聚类算法。

表4 传统FCM算法与改进FCM算法结果比较

应用改进FCM 算法计算数据集在不同交通状态下各分类指标具体的取值范围。数据采集点VDS 311974 的数据分布情况如表5 所示。可以看出，若采用单个分类指标来识别高速公路交通状态，则不能为交通状态的识别提供有效信息（如同样的平均速度可能处于不同的交通状态）；当采用多个指标划分交通状态时，同一指标对应不同交通状态的取值范围具有明显差异。比较各交通状态对应的指标取值范围可以看出，畅通状态和较畅通状态对应的交通流量和空间占有率较低，平均速度和路网充裕度较高；平稳状态和较平稳状态对应的4 个指标均处于中值；较拥挤状态、拥挤状态和阻塞状态对应的交通流量和空间占有率较高，平均速度和路网充裕度较低。此外，分析得出数据采集点VDS 319129的交通流量明显低于另外两个采集点，但改进后的FCM 聚类法仍能清楚地划分该数据集所对应的交通状态。可见，该算法在识别交通状态时，能根据道路的实际情况调整聚类结果，从而更加准确、全面地识别交通状态。

表5 不同交通状态下分类指标的取值范围（数据采集点VDS 311974）

4 结语

本文针对传统FCM 算法未考虑各指标重要性和各样本贡献度不同的缺陷，采用信息熵确定分类指标权重，同时对每个样本赋予不同的加权系数，然后选用交通流量、空间占有率、平均速度和路网充裕度4 个分类指标来识别高速公路的交通状态，并比较了传统FCM 算法和改进FCM 算法的目标函数值、迭代次数及运行时间。结果表明：改进后的FCM 算法因综合考虑了不同指标和样本对聚类结果的影响，其聚类效果优于传统FCM 算法，且迭代次数较少，运行时间更短。值得注意的是，本文仅针对高速公路交通数据进行状态划分，而城市道路情况更加复杂，因此未来还需考虑道路的实际情况来实现对城市道路交通状态的高效识别。