商强 林赐云,2† 杨兆升,2 邴其春,4 田秀娟 王树兴

(1.吉林大学 交通学院， 吉林 长春 130022； 2.吉林大学 吉林省道路交通重点实验室， 吉林 长春 130022； 3.山东高速公路股份有限公司， 山东 济南 250014； 4.青岛理工大学 汽车与交通学院， 山东 青岛 266520)

基于谱聚类与RS-KNN的城市快速路交通状态判别*

商强1林赐云1,2†杨兆升1,2邴其春1,4田秀娟1王树兴3

(1.吉林大学 交通学院， 吉林 长春 130022； 2.吉林大学 吉林省道路交通重点实验室， 吉林 长春 130022； 3.山东高速公路股份有限公司， 山东 济南 250014； 4.青岛理工大学 汽车与交通学院， 山东 青岛 266520)

为了提高城市快速路交通状态判别的准确性，构建了一种基于谱聚类与随机子空间集成K最近邻(RS-KNN)的交通状态判别模型.以地点交通参数为基础，根据交通流运行特性并结合中国道路服务水平的4个等级，采用谱聚类算法将交通状态划分为4类；然后使用已分类的交通流数据训练RS-KNN模型.通过上海快速路的实测数据完成模型的实验验证和对比分析.实验结果表明，所提出的模型不仅能够提高交通状态判别的精度，而且具有良好的鲁棒性，其判别率比标准KNN模型、BP神经网络模型和SVM模型分别提高7.3%、4.9%和4.5%.

交通工程；交通状态判别；谱聚类；随机子空间；K最近邻

交通状态判别是智能交通系统(ITS)的关键功能之一.实时准确的交通状态判别能够直接用于ITS的多个子系统，例如先进的出行者信息系统(ATIS)和先进的交通管理系统(ATMS)，因此，国内外研究人员提出了许多卓有成效的交通状态判别方法,其中机器学习算法因其优良的性能而受到广泛关注.

聚类分析是一类无监督机器学习算法，能够在没有任何先验知识的情况下实现交通流数据的模式分类.文献[1]将高速公路交通流量、速度和占有率作为分类的特征变量，采用凝聚聚类算法划分交通状态类型；文献[2]以高速公路收费数据为基础，通过模糊C均值(FCM)聚类算法判别交通状态；文献[3]使用SCOOT系统的感应线圈数据，通过FCM聚类算法判别城市道路交通状态；文献[4]在FCM聚类算法的基础上，通过设定不同交通参数的权重，提出参数权重聚类方法用于划分交通状态；文献[5]对比了3种聚类算法在高速公路交通状态分类方面的性能，结果表明K均值聚类算法效果最佳；文献[6]通过K均值聚类算法识别高速公路的交通拥挤，获得了87%的识别率.

人工神经网络(ANN)和支持向量机(SVM)作为典型的监督机器学习算法，已被广泛用于交通状态判别.文献[7]提出基于RBF神经网络的高速公路交通运行状态判别方法；文献[8]采用BP神经网络判别道路交通状态；文献[9]将概率神经网络用于公路交通状态判别；文献[10]提出一种基于优化SVM的快速路交通状态判别方法；文献[11]将模糊SVM用于城市道路交通状态分类；文献[12]将3种核函数的SVM用于城市道路交通状态模式识别，并指出数据归一化的必要性.

近年来，聚类分析与监督学习相结合的方法已被用于交通状态判别，而且具有较好的效果.文献[13]提出了基于K均值聚类和多分类SVM的高速公路交通状态估计方法；文献[14]提出了基于动态数据驱动的地点交通状态估计方法，其基本原理是通过机器学习算法实现交通流数据的聚类和分类.聚类分析为监督学习算法提供了必要的先验信息，而监督学习算法能够保证交通状态判别的实时性.谱聚类是一种基于谱图划分理论的新型聚类算法，相比传统的聚类算法(如K均值聚类算法)，其优点在于计算复杂度低，不受样本空间形状限制等.目前，谱聚类已成功应用于模式识别的多个领域[15].此外，集成学习已成为机器学习领域的一个重要研究方向，许多研究表明集成学习算法在解决众多分类问题上表现出了优越的性能，尤其在提高算法泛化能力方面[16].

为了提高快速路交通状态判别的准确性，文中构建了一种基于谱聚类(SC)与随机子空间集成K最近邻(RS-KNN)的快速路交通状态判别模型(SC-RS-KNN).首先介绍谱聚类与RS-KNN的基本原理,然后构建了SC-RS-KNN交通状态判别模型，最后对模型性能进行实例验证和对比分析.

1 谱聚类

谱聚类(SC)包括两个不同阶段：①使用数据集构造亲和图；②通过亲和图的最优分割，聚类数据点.亲和图是一个无向图G(Z,E,W)，其中Z=(z1,z2,…,zn)，表示顶点，E表示边，W为相应的亲和矩阵.ei,j为顶点zi与zj之间的边，所对应的非负权重为wi,j，表示样本xi和xj之间的亲和度.因此，亲和图可用亲和矩阵W=[wi,j]表示.通过高斯相似度函数求解wi,j为

(1)

步骤1 构建K最近邻亲和图，其权重邻接矩阵记作W.

步骤2 计算Laplacian矩阵L，标准化Laplacian矩阵Lsym=D1/2LD1/2.

步骤3 计算矩阵Lsym的前k个特征向量值u1,u2,…,uk.将u1,u2,…,uk作为列，构造矩阵U∈Rn×k.

步骤5 将矩阵T的每一行向量yi∈Rk(i=1,2,…，n)作为一个数据点，通过K均值算法对yi进行聚类得到C1,C2,…，Ck.

2 RS-KNN

集成多个弱分类器，实现强分类器的功能.集成学习不仅能够提高算法的鲁棒性，而且适用于不平衡数据的分类.集成学习包括两个主要问题：一是集成算法的选择；二是弱分类器的选择.常用的集成算法包括AdaBoost、Bagging和随机子空间等.文中采用随机子空间算法集成K最近邻分类器.

2.1 K最近邻

K最近邻是一种简单有效的非参数分类方法，不仅容易实现，而且直接适用于多分类问题.KNN算法基本步骤如下：

步骤1 找出与待分类对象d最接近的K个训练样本，称为待分类对象的K个“最近邻”.欧氏距离是度量“最近邻”的常用标准.待分类对象的特征序列X1=(x11,x12，…，x1n)和训练样本的特征序列X2=(x21,x22，…，x2n)之间的欧式距离为

(2)

步骤2 分别计算待分类对象d属于每一类的权重W，d属于类Cj的权重为

(3)

其中，sim(dj,d)为待分类对象d与第i个最近邻训练样本di之间的相似度，

(4)

步骤3 将待分类对象划分到权重最大一类.

2.2 随机子空间

随机子空间(RS)是一种基于样本特征空间抽样的集成学习算法，其基本原理是从训练样本的特征空间中随机抽样，构建新的训练集，并训练基分类器(文中采用KNN作为基分类器)，通过一定规则(文中采用多数投票规则)融合多个基分类器的分类结果，得到最终分类结果.RS算法能够有效降低样本维度，减小分类器之间的相关性，从而提高整体分类效果.RS算法可总结为以下3个步骤：

步骤2 每个新的数据集Fi训练固定学习算法，得到训练好的基分类器hi，i=1,2,…，G.

步骤3 通过给定的决策规则，合成基分类器h1,h2,…，hG，得到最终集成的分类器.

3 SC-RS-KNN模型

SC-RS-KNN模型的流程主要包括4个步骤：

步骤1 选择用于交通状态判别的特征变量.根据文献[18]的建议，选择交通流量、速度、占有率、占有率与流量的比值和占有率与速度的比值作为特征变量，因为这些变量在不同交通状态下具有较大差异.

步骤2 划分交通状态类型.首先需要确定交通状态类型的数目.目前交通状态分类数目没有统一标准，文中根据中国道路服务水平的4个等级，采用谱聚类算法，将交通状态特征变量数据分为4类，分别对应4种交通状态类型：顺畅、平稳、拥挤和拥堵.聚类前需要对特征变量数据进行归一化处理，归一化公式如下：

(5)

步骤3 构造训练集.使用已分类的交通状态特征变量数据构造训练集.训练集的输入为5个交通状态特征变量，训练集的输出为相应的交通状态，设定标签1、2、3、4分别对应顺畅状态、平稳状态、拥挤状态、拥堵状态.

步骤4 训练RS-KNN模型.通过随机子空间方法提取原训练集的多个特征子空间，使用特征子空间训练KNN分类器，并通过多数投票规则合成各KNN分类器的结果，输出最终的交通状态类型.

4 实例分析

4.1 数据来源

实验数据来源于上海南北高架快速路，快速路设置有24个检测断面，断面的每条车道分别设有线圈检测器，检测器的统计间隔为5 min，采集连续5个工作日的交通流数据，包括交通流量、速度和占有率.

文中随机选取一个检测断面数据进行分析.为了获取道路断面的交通状态，根据式(6)将车道的交通流数据合成断面的交通流数据：

(6)

其中，qi、vi和oi分别表示断面i的流量、速度和占有率，j表示断面的车道编号，n表示断面车道数.

4.2 基于谱聚类的交通状态划分

通过谱聚类算法，将交通流数据分为4种交通状态：顺畅、平稳、拥挤和拥堵.各交通状态下，交通参数的平均值如表1所示.由表可知，不同交通状态的交通参数值具有较大差异，符合交通流在不同状态下的运行特征.

表1 各交通状态的交通参数均值

Table 1 Mean values of traffic parameters in different traffic states

交通状态每5分钟流量/辆速度/(km·h-1)占有率/%顺畅8473.51.9平稳32764.77.7拥挤50653.415.3拥堵53227.133.0

交通流数据的分类结果如图1所示.从图1可以看出，通过交通流数据的聚类，得到4个聚类簇，分别对应顺畅、平稳、拥挤和拥堵4种交通状态.簇与簇之间的界限明显，说明聚类效果良好.顺畅交通状态下，占有率低，车与车之间的干扰很小，车辆几乎可以自由行驶，速度快，因而该状态的交通参数数据点比较分散.平稳交通状态下，占有率有所升高，车与车之间干扰增加，开始出现跟驰现象，交通流连续性增强，交通运行平稳，交通流量与速度大致成线性关系，交通流量随速度的降低而增加.拥挤状态下，占有率进一步升高，车辆之间的干扰加剧，速度的下降加快，随之交通流量的增加缓慢，直至不再增加，甚至减小.拥堵状态下，车与车之间严重干扰，速度大幅度下降，交通流量减小，占有率急剧升高，交通运行极不稳定，数据的离散度较大.因此，通过谱聚类划分的交通状态符合交通流在不同阶段的运行特性.

图2为每一天的交通状态类型.

图2 每天交通状态划分结果Fig.2 Classification results for traffic state of each day

由图2可见，每一天的交通状态不尽相同，但也具有一定的相似性.每天大约0:00～5:00，交通梯型的变化，从顺畅逐渐变为拥堵(标签为4)，出现早高峰；随后交通状态不断波动，大约19:00后，交通状态开始变为平稳(标签为2)，在接近0:00时，交通状态变为顺畅.交通状态的划分结果符合交通流一天的变化规律，进一步说明了基于谱聚类划分交通状态的有效性.

4.3 RS-KNN的训练

使用前4天数据构建训练集，训练RS-KNN模型.为了避免模型的过度学习，模型的训练采用五折交叉验证方法.

RS-KNN模型需要确定的参数包括子空间的个数和每个子空间的特征维数，其中子空间个数即为KNN分类器的个数.不同的子空间个数和子空间维数的RS-KNN模型交通状态的分类正确率如图3所示.由图可知，随着子空间维数的增加，交通状态分类正确率升高,因此子空间维数取4.在理论上，随着子空间个数的增加，即集成的分类器越多，模型的分类正确率越高.然而，集成的分类器越多，计算效率越低.从图3的4维子空间曲线来看，当集成30个KNN分类器之后，随着集成分类器数目的增加，模型的交通状态分类正确率保持不变(均为93.3%).综上，子空间维数取4，子空间个数取30.

图3 模型参数与分类正确率的关系

Fig.3 Relationships between model parameters and classification accuracy

4.4 模型性能分析

采用第5天数据测试RS-KNN模型的交通状态判别效果.为了更好地分析RS-KNN模型的性能,将标准K最近邻模型、反向传播神经网络模型(BPNN)[8]和支持向量机模型[10]作为对比模型.其中，KNN模型需要确定邻近点的个数，设置邻近点个数范围是1-30，经过测试发现，邻近点个数为10时模型分类效果最优.BPNN模型需要确定隐层神经元个数，文中根据文献[8]所示方法，得出最佳隐层神经元数为8.SVM模型选用RBF核函数，按照文献[10]所示方法，得到优化的RBF核函数参数为2.2，惩罚系数为10.5.

各模型交通状态判别结果的混淆矩阵如图4所示.混淆矩阵能够提供模型判别结果的具体信息.以RS-KNN模型的混淆矩阵(见图4(a))为例，矩阵主对角线的方格表示模型正确判别交通状态，例如最左上角的方格表示有73个顺畅交通状态能够正确识别，占所有交通状态个数的比例为25.3%(73/288).最右下角方格表示模型对所有交通状态的总体判别率为96.9%，误判率为3.1%.非主对角线方格表示交通状态误判的具体情况，例如第1行、第2列的方格表示模型将平稳状态(标签为2)误判为顺畅状态(标签为1)，误判次数为2，占判别总数的0.7%(2/288).混淆矩阵下方灰色方格表示对每一类交通状态的判别率(上面)和误判率(下面)，例如第4行、第1列灰色方格表示顺畅状态的判别率为98.6%，误判率为1.4%.右侧灰色方格表示模型判别为某一类交通状态时的结果中，正确判别为该类交通状态的次数占判别为该类交通状态总次数的比例(上面)以及误判次数所占比例(下面).例如第1行、第4列的灰色方格表示在判别为顺畅交通状态的结果(共计73+2个)中，97.3%(73/75)是正确的，2.7%(2/75)是错误的.

由图4可知，在拥堵状态判别方面，RS-KNN模型与SVM模型的判别率相等(均为97.1%)，除此之外，RS-KNN模型对各交通状态的判别率均高于其他模型.在总体判别率方面，RS-KNN模型比KNN模型、BPNN模型和SVM模型分别提高了7.3%、4.9%和4.5%.在交通状态的误判方面，RS-KNN模型误判的交通状态与目标交通状态只相差一个类型，而其他模型均出现相差两个交通状态类型的误判情况，即出现较为严重的误判，说明RS-KNN在交通状态判别上具有更好的稳定性.综上，RS-KNN模型不仅能够进一步提高交通状态判别的精度，而且具有较好的鲁棒性.

图4 模型的混淆矩阵Fig.4 Confusion matrixes of models

5 结语

文中结合无监督学习算法和监督学习算法的优势，构建了一种基于谱聚类和RS-KNN的交通状态判别模型(SC-RS-KNN).首先通过谱聚类算法将交通状态特征变量数据划分为4类，分别对应4种交通状态；然后使用已分类的特征变量数据构造训练集，训练RS-KNN模型并优化模型参数；最后通过实测数据，对模型性能进行比较和分析.结果表明，SC-RS-KNN模型性能良好，不仅交通状态的判别率较高，而且误判的严重程度较低.在进一步研究中，将使用不同道路的交通数据验证和分析模型性能.此外，采用更加智能的模型优化方法(如群体智慧算法和进化算法)也是未来研究的方向.

[1] XIA J,CHEN M.A nested clustering technique for freeway operating condition classification [J].Computer-Aided Civil and Infrastructure Engineering,2007,22(6):430- 437.

[2] 杨庆芳,马明辉,梁士栋,等.基于收费数据的高速公路交通状态判别方法 [J].华南理工大学学报(自然科学版),2014,42(12):51- 57. YANG Qing-fang,MA Ming-hui,LIANG Shi-dong,et al.Freeway traffic state identification based on toll data [J].Journal of South China University of Technology(Natural ScienceEdition),2014,42(12):51- 57.

[3] 姜桂艳,郭海锋,吴超腾.基于感应线圈数据的城市道路交通状态判别方法 [J].吉林大学学报(工学版),2008,38(S1):37- 42. JIANG Gui-yan,GUO Hai-feng,WU Chao-teng.Identification method of urban road traffic conditions based on inductive coil data [J].Journal of Jilin University(Engineering and Technology Edition),2008,38(S1):37- 42.

[4] 张亮亮,贾元华,牛忠海,等.交通状态划分的参数权重聚类方法研究 [J].交通运输系统工程与信息,2014,14(6):147- 151. ZHANG Liang-liang,JIA Yuan-hua,NIU Zhong-hai,et al.Traffic state classification based on parameter weighting and clustering method [J].Journal of Transportation Systems Engineering and Information Technology,2014,14(6):147- 151.

[5] AZIMI M,ZHANG Y.Categorizing freeway flow conditions by using clustering methods [J].Transportation Research Record:Journal of the Transportation Research Board,2010,2010(2173):105- 114.

[6] MONTAZERI-GH M,FOTOUHI A.Traffic condition re-cognition using thek-means clustering method [J].Scientia Iranica,2011,18(4):930- 937.

[7] 李晓斌,徐建闽.基于 RBF 神经网络的高速公路交通状况判别 [J].计算机仿真,2011,28(2):350- 353. LI Xiao-bin,XU Jian-min.Discriminating for traffic situation of highway based on RBF neural network [J].Computer Simulation,2011,28(2):350- 353.

[8] 巫威眺,靳文舟,林培群.基于BP神经网络的道路交通状态判别方法研究 [J].交通信息与安全,2011,29(4):71- 74. WU Wei-tiao,JIN Wen-zhou,LIN Pei-qun.The method of traffic state identification based on BP neural network [J].Journal of Transportation Information and Safety,2011,29(4):71- 74.

[9] NIU S,LIU H.Probabilistic neural networks for the identification of traffic state [C]∥Proceedings of the 14th International IEEE Conference on Intelligent Transportation Systems(ITSC).Washington DC:IEEE,2011:754- 759.

[10] 董春娇,邵春福,熊志华.基于优化SVM的城市快速路网交通流状态判别 [J].北京交通大学学报,2011,35(6):13- 16. DONG Chun-jiao,SHAO Chun-fu,XIONG Zhi-hua.Identification of traffic states with optimized SVM method on urban expressway network [J].Journal of Beijing Jiaotong University,2011,35(6):13- 16.

[11] 李清泉,高德荃,杨必胜.基于模糊支持向量机的城市道路交通状态分类 [J].吉林大学学报(工学版),2009,39(S2):131- 134. LI Qing-quan,GAO De-quan,YANG Bi-sheng.Urban road traffic status classification based on fuzzy support vector machines [J].Journal of Jilin University(Engineering and Technology Edition),2009,39(S2):131- 134.[12] 于荣,王国祥,郑继媛,等.基于支持向量机的城市道路交通状态模式识别研究 [J].交通运输系统工程与信息,2013(1):130- 136. YU Rong,WANG Guo-xiang,ZHENG Ji-yuan,et al.Urban road traffic condition pattern recognition based on support vector machine [J].Journal of Transportation Systems Engineering and Information Technology,2013(1):130- 136.

[13] DENG C,WANG F,SHI H,et al.Real-time freeway traffic state estimation based on cluster analysis and multiclass support vector machine [C]∥ Proceedings of International Workshop on Intelligent Systems and Applications(ISA).Wuhan:IEEE,2009:1- 4.

[14] ANTONIOU C,KOUTSOPOULOS H N,YANNIS G.Dynamic data-driven local traffic state estimation and prediction [J].Transportation Research Part C:Emerging Technologies,2013,34:89- 107.

[15] LIU D,WANG J,WANG H.Short-term wind speed forecasting based on spectral clustering and optimised echo state networks [J].Renewable Energy,2015,78:599- 608.

[16] GUO H,LI Y,LI Y,et al.PSO-adaboost-KNN ensemble learning algorithm for multi-class imbalanced data classification [J].Engineering Applications of Artificial Intelligence,2016,49:176- 193.

[17] VON LUXBURG U.A tutorial on spectral clustering [J].Statistics and Computing,2007,17(4):395- 416.

[18] 邴其春,龚勃文,杨兆升,等.基于投影寻踪动态聚类的快速路交通状态判别 [J].西南交通大学学报,2015,50(6):1164- 1169. BING Qi-chun,GONG Bo-wen,YANG Zhao-sheng,et al.Traffic state identification for urban expressway based on projection pursuit dynamic cluster model [J].Journal of Southwest Jiaotong University,2015,50(6):1164- 1169.

Traffic State Identification for Urban Expressway Based on Spectral Clustering and RS-KNN

SHANG Qiang1LIN Ci-yun1,2YANG Zhao-sheng1,2BING Qi-chun1,4TIAN Xiu-juan1WANG Shu-xing3

(1.College of Transportation,Jilin University,Changchun 130022, Jilin, China;2.Jilin Province Key Laboratory of Road Traffic, Jilin University, Changchun 130022, Jilin, China;3.Shandong High-Speed Group Co., Ltd., Jinan 250014, Shandong, China;4.College of Automobile and Transportation, Qingdao Technological University, Qingdao 266520, Shandong, China)

In order to improve the accuracy of traffic state identification for urban expressway,a traffic state identification model based on spectral clustering and RS-KNN (Random Subspace Ensemble K-Nearest Neighbors) is developed. In the investigation,first,on the basis of spot traffic parameters data and according to the operation cha-racteristics of traffic flow,the traffic state is divided into four categories with the consideration of the four levels of service for Chinese roads. Then,the classified traffic flow data are used to train the RS-KNN model.Finally,by using the real data of an expressway in Shanghai,China,an experimental verification and a comparative analysis for the proposed model are carried out. Experimental results demonstrate that the proposed model not only improves the accuracy of traffic state identification but also possesses good robustness;and that the identification rate of the proposed model is 7.3%,4.9% and 4.5% higher than that of the standard KNN model,the BP neural network and the SVM model,respectively.

traffic engineering;traffic state identification;spectral clustering;random subspace;K-nearest neighbor

2016- 10- 08

国家科技支撑计划项目(2014BAG03B03)；国家自然科学基金资助项目(51408257,51308248)；山东省省管企业科技创新项目(20122150251- 1) Foundation items: Supported by the National Key Technology Research and Development Program of the Ministry of Science and Technology of China(2014BAG03B03) and the National Natural Science Foundation of China(51408257,51308248)

商强(1987-)，男，博士生，主要从事智能交通系统关键理论与技术研究.E-mail:shangqiang14@mails.jlu.edu.cn

† 通信作者: 林赐云(1980-)，男，博士，副教授，主要从事智能交通系统关键理论与技术研究.E-mail:linciyun@jlu.edu.cn

1000- 565X(2017)06- 0052- 07

U 491

10.3969/j.issn.1000-565X.2017.06.009