基于聚类算法的城市快速路交通状态模式分类

周余军 刘智勇 阮太元

摘要：交通状态模式分类在城市交通控制系统中具有重要的应用价值，本文以车流量、平均速度、时间占有率为特征参数，利用CFSFDP（快速搜索查找密度峰值聚类）算法与FCM（模糊C均值聚类）算法进行组合，给出一种新的交通状态模式分类算法。针对广州市某快速路交通流实测数据进行了仿真，结果表明：组合算法是可行的，且分别比CFSFDP和FCM算法有更高的分类准确率。

关键词：决策图 模糊聚类 交通状态模式 截断距离 密度峰值 快速路

中图分类号：TP391 文献标识码：A 文章编号：1007-9416（2016）07-0117-03

Abstract：The classification of traffic patterns has a great value in urban traffic control system， this essay used the vehicle flow，vehicle speed and time occupy as feature vector， combined CFSFDP（Clustering by Fast Search and Find of Density Peaks） and FCM（Fuzzy C-Means），used the combined algorithm to classify the traffic patterns of a certain freeway in GuangZhou. The result turned out that the combined algorithm is applicable in classifying traffic patterns and it is more accurate than CFSFDP and FCM alternatively.

Key Words：decision graph，FCM，traffic pattern classification，cut-off distance，density peaks，Urban freeway

引言

交通信号控制是解决城市交通拥堵的有效方法之一。随着信息技术和人工智能技术的发展，智能交通信号控制系统的效果已经得到明显改善。然而，现有的智能交通信号控制系统都需要根据交通流状态在线优化配时方案，当路口数规模比较大时，在线优化将会遇到“维数灾”问题，此时系统将无法实时响应交通流的变化，因此会大大影响信号控制效果。

统计表明，从某一个时刻来看：交通流的变化是随机的，但从某一个时间段来看，交通流的变化呈现出明显的规律性，如：上下班高峰期、节假日出行高峰期，其交通量比非高峰时段明显增加。把这些规律性出现的交通现象称之为交通状态模式。如果能够准确分辨出各种交通状态模式，则可离线计算对应的最优配时方案，并存贮在交通信号控制系统中；在实施交通信号控制时，通过检测器所获得的交通状态信息能够匹配已知模式，则可用相应的最优配时方案进行信号控制。这就解决了交通信号控制系统在线优化所遇到的问题。

目前，国内外学者已经提出了一些交通状态模式分类的方法，其中具有代表性的有加州算法标准偏差算法[1]、双指数平滑算法等[2]、相对流量增量相对占有率增量比较检测算法[3]、模糊支持向量机分类方法[4]等等。上述交通状态模式分类算法主要依据路段上交通流基本参数的变化（占有率、流量、速度、饱和度等），并设定相应阈值来判断交通处于何种状态，但是交通流状态的定义具有主观上的模糊性，与每条道路的实际运行环境密切相关，因此相关参数阈值的确定对交通状态模式的分类结果将会产生很大影响。基于此，本文采用FCM进行交通状态模式分类。考虑到模糊聚类算法对初始点的敏感性，引入能确定聚类中心的CFSFDP，将CFSFDP与FCM的进行组合，分别采用这3类算法进行交通状态模式分类。

1 基于聚类算法的交通状态模式分类

1.1 基于CFSFDP的交通状态模式分类

CFSFDP能全局遍历数据点确定聚类中心，CFSFDP确定的聚类中心同时具有以下两个特点[5]：

聚类中心点本身的密度大，且密度大于周围邻居点密度；

聚类中心点与其他密度比它大的数据点之间的距离大。

对于待聚类的交通数据集，其中，代表第个交通数据点的平均车速、时间占有率与流量，定义表示数据点和之间的距离。对于中的任何数据点，为其定义和两个量，分别对应上述特点中的密度与距离。

（1）局部密度：

（1）

其中函数，参数为截断距离，需要事先指定。

（2）距离

设表示为的降序排列下标序：

（2）

定义距离为：

（3）

对于中的每一个数据点，可以计算其对应的，作出对应决策图[5]（为横轴，为纵轴的二维图）选择、都大的数据点作为聚类中心点。

CFSFDP对于参数的取值设定了大致范围，但具体的取值对于本文研究的交通状态模式分类没有定论；式（1）中也看出参数的取值很大程度上影响着决策图中聚类中心点的分布，进而影响最终的分类效果，为确保CFSFDP能较好地运用到交通状态模式分类，本文对参数的选取进行改进。

参数选取的改进：CFSFDP对于的取值会使得每个数据点的平均邻居个数约为数据点总数的1%～2%，但这只是针对一般分类情况；对于交通状态模式分类，如何找到较好的进而有效地找到各交通状态模式中心点尚未明确，所以本文提出一种寻找较优的改进，使得CFSFDP能够获得较准确的聚类中心。改进具体步骤为：

第一步：设定的取值范围为（为交通数据点中每两点间最大的距离），采用启发式的学习方法，以指定的步长在中对进行取值。经过反复实验，将步长取为0.1。

第二步：在当前取值下，使用式（1）、（3）计算每个交通数据点的和，作出决策图找出当前的聚类中心点，并构造聚类中心点矩阵。

第三步：判断前后两次迭代获得的聚类中心点个数是否相同，如果不同，则回到第一步继续迭代。

第四步：由式（4）计算前后两次迭代获得的聚类中心点矩阵的距离。设当次迭代所构造的聚类中心点矩阵为。如果前后中心点矩阵间距离小于某个阈值，则表明当前为较优截断距离，停止迭代。否则回到第一步继续迭代。

（4）

式（4）中，为最终聚类个数，为特征参数个数，本文中取。

本文通过改进找到4个聚类中心，分别对应自由流、稳定流、拥挤流、堵塞流四种交通状态模式。找到4类交通状态模式聚类中心点后，根据欧式距离最短原则，对交通数据样本点逐一遍历，判断样本点离哪个中心点的欧式距离最短，则归为相应的交通状态模式类。

1.2 基于FCM的交通状态模式分类

FCM是一种基于目标函数的分类算法，通过求解带约束条件的目标函数将聚类问题转换成非线性规划问题，之后通过迭代优化得到满意的聚类结果[6]。待求解的FCM目标函数为：

（5）

式（5）中，，为待分类的交通数据集，其中，代表第个交通数据点的平均车速、时间占有率与流量；表示聚类中心矩阵；为最终输出的隶属度矩阵，为隶属度矩阵中第行第列的隶属度；为第个聚类中心与第个样本间的欧式距离；为加权指数，令；设定聚类中心数为4，即。

求解带约束条件的目标函数，通常是引入拉格朗日系数构造新函数进行求解：

（6）

对式（6）求偏导，进一步求得：

（7）

（8）

式（7）、（8）即为目标函数式（5）取得极小值的必要条件。通过反复迭代式（7）、（8）就可以得到最终的和。

采用FCM进行交通状态模式分类步骤为：

第一步：设定聚类中心点个数、迭代次数阈值、初始化聚类中心，设置计数器。

第二步：计算模糊隶属度矩阵。

第三步：更新模糊聚类中心。第四步：判断如果，则算法迭代停止，最终输出聚类中心和隶属度矩阵；否则，，重新回到第二步求隶属度矩阵，继续迭代。

迭代完成，得到隶属度矩阵与四个交通状态模式中心，通过隶属度矩阵完成未分类交通数据点的分类得到四类交通状态模式数据集。

1.3 基于组合算法的交通状态模式分类

FCM的初始聚类中心点是随机选择的，在算法迭代过程中有可能使目标函数陷入局部最优，导致FCM过早迭代完成使得分类效果不佳；CFSFDP能较准确的找到聚类中心点，但分类过程是遵循欧式距离最短原则，如果要分类的交通数据点离几个交通状态模式中心点的距离都一致时，则容易发生错分从而影响分类总体结果。基于此，本文采用CFSFDP与FCM组合的算法。组合算法在分类过程中能找到较准确的聚类中心，将找到的聚类中心代入FCM作为其初始聚类中心点，然后迭代找到最优聚类中心，从而输出最优聚类结果。

采用组合算法进行交通状态模式分类步骤为：

第一步：设定的取值范围为，采用启发式的学习方法，以0.1为步长在中对进行取值。

第二步：在当前取值下，计算每个交通数据点的和，作出决策图找出当前聚类中心点，并构造聚类中心点矩阵；并判断前后两次迭代获得的聚类中心点个数是否相同，如果不同，则回到第一步继续迭代。

第三步：计算前后两次迭代获得的聚类中心点矩阵的距离，如果前后中心点矩阵间距离小于某个阈值，停止迭代，输出聚类中心数c及聚类中心点矩阵。否则回到第一步继续迭代。

第四步：设定FCM聚类中心点个数为c、初始化聚类中心点矩阵为、迭代次数阈值，设置计数器。

第五步：计算模糊隶属度矩阵。

第六步：更新模糊聚类中心。

第七步：判断如果，则算法迭代停止，最终输出聚类中心和隶属度矩阵；否则，，重新回到第五步求隶属度矩阵，继续迭代。

迭代完成，得到隶属度矩阵与四个交通状态模式中心，通过隶属度矩阵完成未分类交通数据点的分类得到四类交通状态模式数据集。

2 仿真结果分析

本文采用的数据为广州市某快速路完整一周的交通流数据，车辆检测器类型为地感线圈，车辆类型都相应的折算成标准小客车类型，采集参数为流量、时间占有率、平均速度，每5分钟作为一个样本数据，总共样本数据2017个。表1为三种算法分别对交通状态模式分类后的各类交通状态模式的分类准确率，准确率定义是，对于某一类交通状态模式，分类正确的交通样本数与某一类交通状态模式样本总数比值，计算公式为：

（9）

式中，为分类准确率，为分类正确的交通样本数，为某类交通状态模式样本总数。

由表1得知组合算法比CFSFDP有更高的准确率，CFSFDP的分类过程是遵循欧式距离最短原则，待分类的交通数据点离几个交通状态模式中心点的距离都一致时，容易发生错分，而组合算法采用隶属度最大原则进行分类，会考虑整体交通样本点计算隶属度矩阵，从而得到各交通样本点较理想的分类；同时从表1中可得知组合算法比FCM准确率高，这两种算法虽然都采用隶属度最大原则进行分类，但由推导公式（7）、公式（8）得知隶属度矩阵的计算与聚类中心点的选择有很大关系，更合理的聚类中心点会计算出更合理的隶属度矩阵，因此组合算法的分类效果优于FCM。

3 结语

本文在FCM和CFSFDP的基础上，通过准确选取聚类中心点，用模糊均值聚类算法将历史交通流数据进行分类，并利用Matlab软件进行仿真，结果表明：所采用的组合算法在交通状态模式分类上是可行的，且分别比FCM和CFSFDP具有更高的准确率。需要指出的是，本文所给出的算法对该快速路是有效的，对其他快速路或交通路段进行交通状态模式分类是否有效则需进一步研究。

参考文献

[1]姜桂艳.道路交通状态判别技术与应用[M].北京：人民交通出版社，2004.

[2] Huang Y， Kang Y， Zhao S. Urban Regional Road Network Traffic State Identifying Method[C]// Intelligent Computation Technology and Automation （ICICTA）， 2012 Fifth International Conference on. IEEE， 2012：530-533.

[3]庄斌，杨晓光，李克平.道路交通拥挤事件判别准则与检测算法[J].中国公路学报，2006，19（3）：82-86.

[4]李清泉，高德荃，杨必胜. 基于模糊支持向量机的城市道路交通状态分类[J].吉林大学学报：工学版，2009，吉林大学学报（工学版），2009，39（增刊2）：131-0134（S2）：131-134.

[5]Alex Rodriguez and Alessandro Laio. Clustering by fast search and find of density peaks.Science 344，1492（2014）；DOI：10.1126/science.1242072.

[6]Bezdek J C. Pattern Recognition with Fuzzy Objective Function Algorithms[M]. New York Plenum Press，1981.