EN中文

地球信息科学学报 >

2022 , Vol. 24 >Issue 2: 339 - 351

DOI: https://doi.org/10.12082/dqxxkx.2022.210392

地球信息科学理论与方法

基于自适应时序剖分与KNN的短时交通流量预测

  • 祁朵 , 1 ,
  • 毛政元 , 1, 2, *
展开
  • 1.福州大学数字中国研究院（福建）,福州 350108
  • 2.福州大学空间数据挖掘与信息共享教育部重点实验室,福州 350108
*毛政元（1964— ）,男,湖南武冈人,教授,博士生导师,主要从事城市变化检测、时空数据分析等研究。 E-mail:

祁 朵（1995— ）,男,安徽阜阳人,硕士生,主要从事智能算法、交通流预测等研究。 E-mail:

收稿日期: 2021-07-14

  要求修回日期: 2021-07-30

  网络出版日期: 2022-04-25

基金资助

国家自然科学基金项目(41471333)

福建省自然科学基金面上项目(2018J01619)

版权

版权所有,未经授权,不得转载、摘编本刊文章,不得使用本刊的版式设计。
收起

Short-term Traffic Flow Prediction based on Adaptive Time Slice and KNN

  • QI Duo , 1 ,
  • MAO Zhengyuan , 1, 2, *
Expand
  • 1. Academy of Digital China, Fuzhou University, Fuzhou 350108, China
  • 2. Key Laboratory of Spatial Data Mining and Information Sharing of Ministry of Education, Fuzhou University, Fuzhou 350108, China
*MAO Zhengyuan, E-mail:

Received date: 2021-07-14

  Request revised date: 2021-07-30

  Online published: 2022-04-25

Supported by

National Natural Science Foundation of China(41471333)

Project of Science and Technology of Fujian Province(2018J01619)

Copyright

Copyright reserved © 2022
Fold

摘要

在智能交通系统中,准确和高效的短时交通流量预测是交通诱导、管理和控制的前提。由于交通流量动态变化中表现出的时变性和非平稳性特征,其预测难度较大,是交通领域中亟待解决的难题。为提高短时交通流量的预测精度,本文设计与实现了基于自适应时序剖分与KNN（A-TS-KNN）的短时交通流量预测算法。① 基于动态时间规整（Dynamic Time Warping,DTW）动态剖分单日时序为不同的交通模式;② 在不同交通模式,采用互信息法求解每个预测时刻时间延迟的最大阈值,构造不同时间延迟的状态向量,生成交通流量历史数据库;③ 采用十次十折交叉验证的方法求解每个时刻不同时间延迟与不同K值的正交误差结果分布,提取误差最小的正交结果,得到自适应时间延迟与K值的参数组合;④ 采用K个最相似的近邻的距离倒数加权值作为预测结果。对比K近邻（K-nearest neighbors, KNN）、支持向量回归（Support vector regression,SVR）、长短期记忆神经网络（Long-short term memory neural network,LSTM）以及门控递归单元神经网络（Gate recurrent unit neural network,GRU）共4种主流预测模型,A-TS-KNN算法预测精度显著提升;将A-TS-KNN算法用于福州市城市路网中其他交叉路口的短时交通流量预测,结果表现出良好的泛化能力。

关键词： 短时交通流量预测; DTW; KNN; 自适应时序剖分; 互信息法; 交叉验证; 自适应时间延迟与K值

本文引用格式

祁朵 , 毛政元 . 基于自适应时序剖分与KNN的短时交通流量预测[J]. 地球信息科学学报, 2022 , 24(2) : 339 -351 . DOI: 10.12082/dqxxkx.2022.210392

Abstract

Short-term traffic flow prediction with high accuracy and efficiency plays an important role in Intelligent Transportation Systems, which is a prerequisite for traffic guidance, management, and control. Due to the time-varying and non-stationary characteristics of the dynamic change of traffic flow, it is difficult to predict traffic flow with high accuracy, which needs to be resolved urgently in the transportation field. In order to improve the accuracy and efficiency of short-term traffic flow prediction, the paper develops a short-term traffic flow predicting algorithm based on adaptive time slice and the improved KNN model (A-TS-KNN), which is then implemented successfully in short-term traffic flow predicting experiments. In the first, the Dynamic Time Warping (DTW) algorithm is used to dynamically slice the daytime sequence of traffic flow into different traffic patterns. Secondly, the mutual information method is used to solve the maximum threshold of the time delays of traffic flow at each time in different traffic patterns. Then the traffic flow state vectors of different time delays is constructed, which generates a history database of traffic flow. Thirdly, the method of ten times ten-fold cross-validation is used to solve the orthogonal error distribution of different time delays and K values of traffic flow at each time. The orthogonal result with the smallest error is selected, and the parameters combination of adaptive time delay and K value are obtained. In the end, the weighted value of the reciprocal Euclidean distance of the K most similar neighbors is used for predicting traffic flow of next time. The forecasting accuracies of the improved A-TS-KNN and other four models including K-Nearest Neighbors (KNN) model, Support Vector Regression (SVR) model, Long-Short Term Memory (LSTM) neural networks, and Gate Recurrent Unit (GRU) neural networks are compared. The experimental results indicate that the improved A-TS-KNN model is more appropriate for short-term traffic flow forecasting than the other models. In addition, the A-TS-KNN algorithm is used for short-term traffic flow predicting at other four different intersections in the urban road network of Fuzhou, which has been shown good generalization ability.

Key words： short-term traffic flow prediction; DTW; KNN; adaptive time slice; mutual information method; cross validation; adaptive time delay and K value

1 引言

随着交通拥堵日益严重,用于提升交通系统性能的智能交通系统（Intelligent Transportation Systerms,ITS）受到了越来越多的关注,短时交通流量预测是其中涉及的关键技术,旨在根据特定位置当前交通流量和历史序列数据预测其下一时刻（如 5 min或10 min）的交通流量。缺乏良好交通预测能力的ITS只能被动地提供服务,由于交通流量时间序列的时变性与非平稳性特征,通过准确、高效的预测避免数据收集和交通策略实施间存在的时滞是解决该问题最具挑战性的任务[1]。
城市路网包括路段与路口2个子类。相较于路段上的交通流,交叉路口受交通信号灯控制的影响,其交通流的时变性特征更为突出[2]。非平稳性特征主要反映在2个方面,包括空间非平稳性和时间非平稳性。空间非平稳性意味着样本数据分布的不同局部区域是变化的[3]。例如,在城市路网中,不同类型道路的交通模式存在显著的差异[4],不同城市更是如此。时间非平稳性主要体现于 2个方面：① 在不同的时间区域,即便相同的道路也具有不同的变化模式[5],如早晚高峰的流量变化模式完全不同;② 由于时空自相关的影响,路段当前时刻的交通模式与邻近历史时间间隔的交通模式极为相似[6]。
为解决上述问题,许多技术相继被应用于短时交通流量预测领域,相关文献中已经提出的预测模型包括基于统计方法的参数模型和基于机器学习的非参数模型[7]。参数模型可进一步细分为差分自回归移动平均（ARIMA）、卡尔曼滤波、线性回归等子类。此类模型假设同一地点的交通流量在时间序列上呈线性关系,忽略了其中普遍存在的时变性、非平稳性等特征;此外,加入新数据需要重新计算模型参数,模型时间复杂度高、效率低。因此,运用此类模型预测交通流量的局限性越来越明显。非参数模型主要包括SVR[8]、KNN[7]、神经网络[9]（含深度学习）。此类模型是基于数据驱动的回归预测方法,能够处理交通流量发生不确定性变化的问题,预测过程中无需建立自变量与因变量之间的函数关系,而是根据已有数据的输入输出关系决定预测结果,观测到的新数据可以随时加入模型的数据库作为预测的样本数据,具有良好的可移植性和较高的预测精度[10]。
非参数模型中的KNN具有处理非线性问题的能力,通过改进KNN算法能够捕捉交通流量变化过程中的时变性与非平稳特征,已被广泛应用于短时交通流量预测研究中。如Davis等[11]首先将KNN算法引入交通流预测领域,验证了基于模式识别领域的KNN算法无需理解数据的内部规律,适用于处理具有非线性的交通流数据;Yu等[12]比较不同状态向量的预测精度,证明了模型预测精度依赖于时间延迟的选取;梁艳平等[7]考虑到时空自相关的影响,为每个预测时刻选取变化的K值,进一步提高了预测精度;Ryu等[13]采用基于信息论的方法求解全局时间延迟,生成较为合理的状态向量,得到了满意的预测结果;程诗奋等[14]采用聚类算法划分一天为不同时间区间,分别针对不同时间区间采用预测算法,一定程度提高了预测精度。上述文献倾向于学习一个用于所有任务的全局度量,难以捕捉交通流表现出的时变性和非平稳性特征;根据交通流表现出的日周期性划分每天为不同时间区间具有一定合理性,但相同路段同一交通模式会出现滞后或提前,不同路段更是如此,采用全局固定的时间区间划分策略无法反应细粒度的时间非平稳变化特征。如何准确地将每天的交通流划分为不同时间区间仍是短时交通流量预测中一个尚未解决的难题[15]。
基于KNN回归算法的短时交通流量预测现有研究成果仍存在以下2个方面的局限性：① 算法方面：未考虑时间延迟与K值的正交作用导致错误地捕捉交通模式的时变性特征;② 交通模式方面：未准确地划分不同交通模式的时间区间,导致刻画交通模式非平稳性特征不合理。综上,本文提出一种A-TS-KNN的短时交通流量预测方法,通过动态剖分单日时序为不同交通模式,针对不同交通模式为不同预测时刻制定合理的时间延迟与K值的参数组合,并以最相似的K个近邻的距离倒数加权值作为预测结果,试图克服KNN算法方面的局限性和动态剖分交通流本身表现出的不同模式特征提高短时交通流量预测的精度。

2 基于自适应时序剖分与KNN的算法框架

2.1 基于A-TS-KNN的非参数回归

KNN算法是一种基于模式识别理论的回归预测算法,即利用模式匹配的思想从历史数据库中匹配与当前状态最相似的K个数据,将其用于预测下一时刻的交通流量[11]。A-TS-KNN算法的短时交通流量预测流程如图1所示,基本思想是在KNN算法的基础之上,通过动态剖分每天的交通模式为不同时间区间,针对不同时间区间为不同预测时刻制定时间延迟和K值的参数组合以提高短时交通流量预测的精度。
图1 基于A-TS-KNN算法的短时交通流量预测流程

Fig. 1 Short-term traffic flow prediction process based on A-TS-KNN algorithm

2.2 基于DTW的单日交通模式动态剖分算法

同一路段一天中不同时间区间的交通流（如凌晨和早高峰）存在显著性差异[5],这是影响预测模型的一个主要因素[16],其日交通流曲线表现出极强的周期性,但不同日期同一交通模式并非严格对齐,例如周一早高峰区间为7:00—10:00,周二早高峰区间可能出现于7:20—10:10,这就导致高峰区间出现位移现象。若仍采用全局固定的时间区间划分策略,会导致错误地刻画非平稳性特征,影响预测精度[14]。鉴于此,引入DTW算法[17],通过模板匹配,动态剖分单日时序为不同交通模式的时间区间。
考虑2个随机变量{ x 1, x 2, x 3, …, x m}与{ y 1, y 2, y 3, …, y n}组成的时间序列X和Y,m与n不相等,构建 m × n距离矩阵。DTW定义如式（1）所示。
DTW ( X , Y ) = min ∑ k = 1 K w k K
式中：K表示对不同长度的规整路径进行补偿; w k表示矩阵中搜索路径第k个单元。选择一个路径使得累加距离最小。累积距离定义如式（2）所示。
γ ( i , j ) = d ( q i , c j ) + min γ ( i - 1 , j - 1 ) , γ ( i - 1 , j ) , γ ( i , j - 1 )
式中： d ( q i , c j )为当前格点距离, min γ ( i - 1 , j - 1 ) , γ ( i - 1 , j ) , γ ( i , j - 1 )为达到该点的最小的邻近元素的累计距离之和。
基于DTW的单日交通模式动态剖分伪代码如算法1所示。

算法1 基于DTW的单日交通模式动态剖分算法
输入：日交通流量序列 F ← f i n,模板交通流量序列 D ← d n,时间延迟参数 M ← r , l
输出：日交通流量模式区间分隔点 P ← p n - 1 FunctionSEG _ TRAFFIC _ MODEL ( F , D , M )
Step 1 for d n inD :
Step 2 for f i n inF :
forrinM :
forlinM :
Step 2.1 //计算测试序列与模板序列间DTW
cal culateDTW ( F i n , d n )
Step 2.2 //获取DTW相似度最小值对应时间序列
get ind ex _ of _ Min ( f i n )
Step 2.3 //获取该序列交通模式起始和结束时刻
get p i , p i + 1

2.3 MI算法求解时间延迟的最大阈值

基于KNN算法的短时交通流量预测中,构造状态向量S是进行模式匹配的基础[4],也是KNN算法回归预测的核心问题之一,其定义如式（3）所示。
S = [ s t - d , … , s t - 2 , s t - 1 , s t , s t + 1 ]
式中： s t + 1表示预测下一时刻的交通流量; s t与 s t - d表示当前时刻与向前延迟d个时刻的交通流量。如何合理地制定时间延迟d的选取方案决定了KNN算法能否正确地捕捉交通流量动态的时变性特征。针对2.2节动态剖分的不同交通模式时间区间,分别采用互信息法[13]（Mutual Information Method,MI） 求解每个预测时刻最大时间延迟d,生成不同时间延迟构建的状态向量。
引用2.2节时间序列X和Y,在此m等于n,互信息（MI）定义如式（4）所示。
I ( X ; Y ) = ∑ ∑ p ( x , y ) lo g 2 p ( x , y ) p ( x ) p ( y )
式中：互信息是衡量一个时间序列与另一时间序列相关性的信息量。2个时间序列之间相关性越强,二者之间的MI值越大;相反,如果这2个时间序列在统计上是独立的,那么MI值为0。故可将其用于在无先验知识的情况下度量本文中的2个时间序列之间的时间自相关性。
定义[X, Y] = [ V ( t ) , V ( t - d ) ],X、Y分别代表时间序列 V ( t ) , V ( t - d ),则 I ( X , Y )可用以d为自变量的函数关系式表达,记作 I ( d )。 I ( d )的大小代表了在时间序列 V ( t )确定的情况下,时间序列 V ( t - d )确定性的大小。 I ( d )数值越大表示 V ( t - d )与 V ( t )相关性越强; I ( d )为0,表示 V ( t )与 V ( t - d )完全独立;重构状态向量时标准化MI值,以0.9、0.8作为MI值的最小阈值（在求解MI过程中,不同时刻历史交通流量与其邻近历史时刻的历史交通流量MI值出现在区间[0.7, 1））。

2.4 选取距离度量准则

KNN预测算法的关键是找到与当前交通 模式最相似的K个近邻数据。基于KNN算法的短时交通流量预测中,欧氏距离应用最为广泛。为赋予与当前交通模式最相似的近邻更大的权重,采用 2.3节所述MI值为权重作为实验的距离度量指标,如式（5）、式（6）所示。
w j = I - 1 ( X i j , Y ) ∑ i = 1 n I - 1 ( X i j , Y )
d X i j , Y = w j ( x i - y i ) 2
式（5）中： w j为权值, I - 1 ( X i j , Y )是第j个状态向量与当前状态向量互信息的倒数,MI值越大, w j越小;式（6）中： w j越小, X i j与Y距离越接近, X i j与Y的相似性越强。

2.5 选取自适应时间延迟与K值

如何确定时间延迟与K值（从训练数据集选取的近邻个数）是KNN算法的2个核心问题。全局最优时间延迟和K值均无法合理地捕捉交通模式动态的时变性特征,从而导致预测结果发生过拟合或欠拟合。本文通过2.2节动态剖分单日的时序为不同交通模式,针对不同交通模式,分别为每个预测时刻选取自适应时间延迟与自适应K值的参数组合。
在不同交通模式,为每个预测时刻初始化时间延迟2,时间延迟的最大阈值为d（2.3节求解的时间延迟的最大阈值）,构造时间延迟在[2,d]区间上的状态向量,并生成历史数据库（训练数据集）。K值过小会造成过拟合,K值过大会导致预测结果欠拟合,基于此,为每个预测时刻的不同状态向量分配[2, 13]区间上不同的K值,采用十次十折交叉验证的方法进行短时交通流量预测,得到正交预测结果误差,选取误差最小值对应的时间延迟与K值作为自适应时间延迟与K值。误差衡量指标采用平均绝对误差（MAE）。十折交叉验证的原理如图2所示。
图2 十折交叉验证原理

注：V表示整个训练数据集。

Fig. 2 Principle of ten-fold cross-validation

2.6 选取预测算法

经上述匹配机制得到的K个近邻将用于预测下一时刻的交通流量。如何将K个近邻的特点与预测算法结合起来,并有针对性地利用这K个近邻是预测算法解决的根本问题。本文采用带有权重的欧氏距离预测算法,如式（7）、式（8）所示。
a i = q i - 1 ∑ i = 1 k q i - 1
s ˆ t + 1 = ∑ 1 k a i s ˆ t + 1 i
式中： q i表示第i个邻居与当前状态向量之间的距离; a i表示距离倒数加权值; s ˆ t + 1 i表示第i个近邻的下一时刻交通流量。

2.7 精度评价指标

引入平均绝对误差（MAE）、均方根误差（RMSE）、平均绝对百分比误差（MAPE）、均等系数（EC） 4种精度评价指标和算法运行时间对比分析A-TS-KNN算法与KNN、SVR、LSTM以及GRU的预测性能。MAE反映与真实值之间的差异,RMSE反映拟合曲线离散的程度,2种评价指标数值越小,说明预测精度越高;MAPE为0表示完美模型,MAPE大于1表示劣质模型;EC值越大,说明预测结果与真实值的拟合程度越高;算法运行的时间越小,其效率越高。4种误差评价指标如式（9）—式（12）所示。
MAE = 1 n ∑ i = 1 n y ˆ i - y i
RMSE = 1 n ∑ i = 1 n y ˆ i - y i 2
MAPE = 100 % n ∑ i = 1 n y ˆ i - y i y i
EC = 1 - ∑ i = 1 n y ˆ i - y i 2 ∑ i = 1 n y ˆ i 2 + ∑ i = 1 n y i 2
式中： y ˆ i表示预测值;yi代表真实值;n为预测时刻的数量。

3 实验数据及实验过程分析

3.1 数据源

实验采用福州市主城区五四路东大路交叉路口及其邻近4个路口（图3）的交通流量数据,数据通过微波传感器每5 min采集一次,采集时间为2017年10月9日至2018年2月2日。其中,2017年10月9日至2018年2月2日期间工作日的交通流量原始数据经缺失值恢复、异常值修复等预处理工作后运用于本文各节实验。算法均通过Python编程语言,在Pycharm开发环境下编程实现。
图3 实验路口分布

Fig. 3 Distribution of experimental intersections

3.2 基于DTW的单日交通模式动态剖分结果分析

提取2017年10月9日至2018年1月26日期间的工作日交通流量数据（3.4节用于构造训练数据集）,采用2.2节所述方法得到不同交通模式的动态剖分时间区间（表1）,划分10种不同交通模式,其中划分结果的节点处于动态状态。
表1 动态剖分时序结果

Tab.1 Results of dynamic slice of time

模式名称 模式类型 模式时间区间
a 缓慢下降模式 [00:00, 03:00)
b 畅通平稳模式 [03:00, 06:00)
c 迅速增长模式 [06:00, 07:30)
d 早高峰模式 [07:30, 11:00)
e 次高峰模式 [11:00, 13:00)
f 平稳下降模式 [13:00, 14:00)
g 平稳增长模式 [14:00, 17:00)
h 晚高峰模式 [17:00, 19:20)
i 畅通平稳模式 [19:20, 21:40)
j 畅通稳降模式 [21:40, 23:59)
综上所述,交通流存在时间非平稳性特征,这种非平稳性表现在不同时间段交通模式存在差异性,以此为出发点,对本文实验路口数据的单日交通流量进行动态时间区间剖分。动态剖分结果如图4所示。00:00—03:00,交通流呈现出稳定地下降模式; 03:00—06:00,交通流呈现出稳定趋势,未见明显上涨与下降;这与人们出行需求具有一致性;06:00—07:30,交通流呈现出迅速增长,此段时间,道路承载能力富余,人们出行需求大大增加,导致交通流迅速增长;07：30—11：00,道路承载能力达到一定限度,使得交通流呈现出相对稳定的运动模式;11:00—13:00,交通流有降低趋势,与高峰时段的交通模式具有相似性,但其反映的出行需求与早高峰区间截然不同,早高峰时段主要由于刚性的出行需求所致,因此与早高峰时段划分开;13:00—14:00,由于道路出行需求减弱,交通流呈现出一定降低趋势;14:00—17:00,交通流表现出稳定的趋势;17:00—19:20是晚高峰时段,相比早高峰时段未出现迅速增长的过渡阶段,原因在于此时段开始前道路承载能力已达到一定限度,无法保证车辆迅速通过该检测点,相比早高峰时段晚高峰交通流量有所下滑,表明该时段更易出现拥堵;19:20—21:40,相较晚高峰时段交通流有所增加,原因有：① 结合图3可知,选用路口为主城区繁忙路口,人们出行需求较大,且福州市人口分布密集;② 道路承载能力有所提升,单位时间通过该监测点的车辆增加;21:40—23:59,人们出行需求小于道路承载能力,呈现出稳定下降。通过动态划分上述10种不同交通模式,分别刻画不同交通模式的非平稳性特征。
图4 动态剖分时序结果

注：图中不同颜色的线条代表不同日期。

Fig. 4 Results of dynamic slice of time

3.3 时间延迟最大阈值分析

针对2.2节动态剖分单日交通流量为不同交通模式的时间区间,采用2.3节所述MI算法求解每个时刻时间延迟的最大阈值。以迅速增长模式时段预测第89、90时刻为例（图5）,第89时刻（图5（a））时间延迟的最大阈值为8,第90时刻（图5（b））时间延迟最大阈值为9,其余286个预测时刻均重复采用此方法得到图6各个预测时刻时间延迟的最大阈值取值分布（蓝色柱）。时间延迟阈值大多分布在5左右,与文献[13]不谋而合,表明同一时刻历史交通流量与其邻近历史时刻的历史交通流量的时间自相关程度逐渐减弱,与邻近5个时刻左右的历史交通流量呈现最大相关程度。
图5 MI算法求解时间延迟的最大阈值

Fig. 5 MI algorithm solves the maximum threshold of time delay

图6 不同预测时刻时间延迟最大阈值取值

注：绿色柱和红色柱分别代表第89、第90时刻最大时间延迟数。

Fig. 6 Maximum threshold value of time delay at different predicted moments

3.4 构造训练数据集

提取2017年10月9日至2018年1月26日期间工作日交通流量数据,针对3.2节动态剖分结果,在不同交通模式为不同预测时刻构造[2, d]区间上的（d-2）种不同时间延迟的状态向量作为其训练数据集（d表示3.3节求解的时间延迟的最大阈值）。

3.5 选取自适应时间延迟与K值

通过2.2节动态剖分的不同交通模式,采用3.3节求解最大时间延迟,以2.5节所述原则为依据,运用于3.4节的训练数据集,求解自适应时间延迟和K值的参数组合。同样以预测第89、90时刻为例,自适应时间延迟与k值正交结果误差分布如图7、图8。
图7 第89时刻参数正交误差分布

注：图中对应格子的颜色越深表示误差越小。

Fig. 7 Orthogonal error distribution of parameters at time 89

图8 第90时刻参数正交误差分布

注：图中对应格子的颜色越深表示误差越小。

Fig. 8 Orthogonal error distribution of parameters at time 90

由图7、图8可知,第89、90时刻选取参数组合分别为[K=2, d=2]、[K=2, d=7],d表示时间延迟。不同预测时刻选取相同参数组合,预测精度存在明显差异,表明由于交通流存在时变性特征,为每个预测时刻选取自适应时间延迟与自适应K值的合理性。每个预测时刻自适应时间延迟与k值的分布如图9所示（d为时间延迟）。时间延迟与K值的取值更多分布在3和2左右,一方面由于动态地剖分单日交通模式为不同时间区间,在同一时间区间参数的选取具有相似性;另一方面,由于时间自相关的影响,即当前时刻与其邻近历史时刻的交通流量的自相关性存在由强减弱的过程。
图9 自适应时间延迟与K值选取

Fig. 9 Adaptive time delay and K value selection

4 结果和分析

设计了3组预测实验,分别为：A-TS-KNN算法参数分析及比较实验;A-TS-KNN算法与当下主流算法的比较实验;A-TS-KNN算法的可移植性实验。实验测试数据集均采用2018年1月29日至2018年2月2日5个工作日的交通流量数据。

4.1 A-TS -KNN算法参数分析及比较实验

本节采用KNN算法、AK-KNN算法、AD-KNN算法、TS-KNN算法和A-TS-KNN算法进行短时交通流量预测,其中,KNN为基础算法,AD-KNN和AK-KNN为单考虑自适应时间延迟或K值的预测算法（未剖分时间区间）,TS-KNN算法为手动提取交通模式后未考虑节点动态变化的全局固定划分时段的预测算法。
实验采用动态时序剖分和交叉验证的思想得到预测误差对比表（表2）,AD-KNN、TS-KNN和A-TS-KNN共3种预测算法的EC值均大于0.9,相较于KNN和AK-KNN预测算法更为可靠;从AK-KNN、AD-KNN、TS-KNN和A-TS-KNN算法的预测误差（MAE、RMSE和MAPE）比较来看,时间延迟与K值对预测结果均有影响,表明基于交叉验证思路针对每个预测时刻训练生成的时间延迟与K值具有自适应性,可以捕捉到交通流量动态变化过程中的时变性特征;经手动提取不同交通模式的全局固定时段（未考虑节点动态变化）的预测精度显著提升,表明通过刻画交通流非平稳性特征有利于提高预测精度;A-TS-KNN算法在全局固定时段划分的基础上预测精度进一步提升,其优势在于动态地捕捉交通流量非平稳性特征,较手动生成全局固定的节点,结果更加准确,过程更加便捷,验证了基于DTW算法动态刻画交通模式的时间非平稳性特征具有自适应性。在KNN算法基础上A-TS-KNN算法预测精度（MAE、RMSE、MAPE、EC）分别提升了12.01、13.54、5.45%和0.06。
表2 预测结果误差表

Tab. 2 Errors table of prediction results

算法 MAE RMSE MAPE/% EC
KNN 24.70 33.75 10.97 0.88
AK-KNN 19.88 29.63 8.88 0.89
AD-KNN 18.10 26.31 8.00 0.91
TS-KNN 13.12 20.62 5.85 0.93
A-TS-KNN 12.69 20.21 5.52 0.94

4.2 A-TS-KNN算法与其他主流算法的比较实验

本节选取4种当下主流的预测算法,分别为KNN、SVR、LSTM和GRU作为对比实验,旨在突出A-TS-KNN算法的优越性。4种对比算法的训练数据集一致（4.1节KNN基础算法的训练数据集）,且参数设置为最佳状态。得到预测误差结果对比图（图10）。
图10 不同算法预测结果性能对比

Fig. 10 Performance comparision of prediction results of different algorithms

SVR参数设置：核函数设置为“poly”,惩罚因子设置为“1e3”,核系数设置为0.1;LSTM参数设置：隐藏层数设置为4,单层神经元数为128,1个Dense层,优化器为rmsprop,epochs为200,batch_size为6,损失函数为mse;GRU参数设置：隐藏层数设置为4,单层神经元数为128优化器为SGD,epochs为100,batch_size为6,损失函数为mse。
据图10预测性能评价指标可知,SVR预测精度最低,因其适用于处理小样本训练数据集;LSTM和GRU预测精度均低于基础KNN预测算法,一方面,KNN算法所匹配的历史数据具有完备性;另一方面,LSTM和GRU只有在数据量达到一定规模时才会表现出比传统机器学习更优越的预测性能[18]。A-TS-KNN算法预测精度显著高于其他算法,关键原因在于通过动态刻画交通模式的非平稳性特征,在不同交通模式,为不同时刻制定了与预测密切相关的时间延迟和K值的选取方案,以此抓取交通流时变性特征。在模型运行时间上可以看出,基础KNN算法运行时间最慢,因其要遍历整个历史数据集;A-TS-KNN算法得益于对不同交通模式的剖分提取处理,只需对该模式下的历史数据遍历即可,计算时间缩短至基础KNN的十分之一,在提高预测精度的同时,优化了模型的运行时间。GRU的更新门相当于LSTM的输入门和遗忘门,缺少一个通道,使得运行效率高于LSTM。
为更直观地比较各类方法,可视化2018年1月29日的预测结果。图11为全天交通流量的可视化结果,图12为早高峰时段交通流量的可视化结果,图13为晚高峰时段交通流量的可视化结果。
图11 不同预测算法可视化结果

Fig. 11 Visualization results of different prediction algorithms

图12 早高峰时段不同预测算法可视化结果

Fig. 12 Visualization results of different prediction algorithms during morning peak hours

图13 晚高峰时段不同预测算法可视化结果

Fig. 13 Visualization results of different prediction algorithms during night peak hours

如图11所示,真实交通流量变化过程中表现出极强的时变性、非平稳性特征。预测算法SVR、LSTM以及GRU均能够拟合出真实交通流量序列的大致走势,但拟合曲线过于平滑;A-TS-KNN算法拟合曲线比前三者更佳,优势在于能够捕捉交通流的时变性和非平稳性特征。图12和图13更加细粒度地展示了各类方法的预测结果,早高峰时段A-TS-KNN算法拟合结果较完美,相较晚高峰时段预测结果更佳。一方面,早高峰时段人们出行的刚性需求相对稳定;另一方面,晚高峰期间人们出行需求存在不确定性,影响因素较多。

4.3 A-TS-KNN算法的可移植性实验

为验证A-TS-KNN算法的泛化能力,设置4组可移植性实验采用2.2节方法动态剖分不同路口的时间区间和3.5节求解的参数组合进行短时交通流量预测。选取福州市五四路东大路邻近的 4个不同交叉路口（图3）作为实验区域,4个交叉路口均采用2017年10月9日—2018年1月26日工作日的交通流量作为实验的训练数据集,采用2018年1月29日—2018年2月2日的交通流量作为实验的测试数据集。预测结果误差如图14所示。 路口1：湖东-井大路;路口2：八一七-东街路; 路口3：鼓屏-湖东路;路口4：六一-东大路。
图14 不同路口预测结果误差

Fig. 14 Errors of prediction results at different intersections

据图14可知,4个交叉路口预测结果的EC值均大于0.9,说明A-TS-KNN算法拟合结果良好,具有一定泛化能力,能够一定程度上克服交通流空间上的非平稳性特征获得满意的预测结果;由于不同交叉路口间存在空间上的的异质性[19],预测精度（MAE、MAPE、RMSE、EC）呈现出不一致性。

5 结论与讨论

5.1 结论

非参数回归预测短时交通流量仅在历史数据库的支持下就能够适应其时变性和非平稳性特征,预测效果明显优于同类成果中的参数模型。针对KNN算法应用于短时交通流量预测的局限性,通过动态剖分单日交通流为不同模式以刻画交通流非平稳性特征,并针对不同交通模式为每个预测时刻制定有效的时间延迟和K值选取方案以克服交通流时变性的影响,二者优化了KNN算法的匹配精度和运行效率。研究表明,A-TS-KNN比基础KNN算法的预测结果误差MAE降低了12.01。与主流算法对比,A-TS-KNN算法的预测精度显著高于KNN、SVR、LSTM和GRU;在运行效率方面,A-TS-KNN算法运行时间是基础KNN的十分之一。将A-TS-KNN算法应用于随机选定的其他不同的4个交叉路口,也得到了满意的预测结果,表明A-TS-KNN算法具有良好的泛化性能。

5.2 讨论

A-TS-KNN算法针对下午高峰时段的预测仍存在一定的局限性,如何全面考虑该时段交通流影响因子提升其预测精度是后续研究努力的方向;由于交叉路口的数据有限,A-TS-KNN算法是否适合用于空间上更远的交叉路口,仍有待验证。

参考文献

原文顺序 | 文献年度倒序 | 文中引用次数倒序
[1]
Li W, Wang J X, Fan R, et al. Short-term traffic state prediction from latent structures: Accuracy vs. efficiency[J]. Transportation Research Part C: Emerging Technologies, 2020, 111:72-90. DOI: 10.1016/j.trc.2019.12.007

DOI

[2]
Coogan S, Flores C, Varaiya P. Traffic predictive control from low-rank structure[J]. Transportation Research Part B: Methodological, 2017, 97:1-22. DOI: 10.1016/j.trb.2016.11.013

DOI

[3]
Wu S S, Wang Z Y, Du Z H, et al. Geographically and temporally neural network weighted regression for modeling spatiotemporal non-stationary relationships[J]. International Journal of Geographical Information Science, 2021, 35(3):582-608. DOI: 10.1080/13658816.2020.1775836

DOI

[4]
Cai P L, Wang Y P, Lu G Q, et al. A spatiotemporal correlative k-nearest neighbor model for short-term traffic multistep forecasting[J]. Transportation Research Part C: Emerging Technologies, 2016, 62:21-34. DOI: 10.1016/j.trc.2015.11.002

DOI

[5]
Toshniwal D, Chaturvedi N, Parida M, et al. Application of clustering algorithms for spatio-temporal analysis of urban traffic data[J]. Transportation Research Procedia, 2020, 48:1046-1059. DOI: 10.1016/j.trpro.2020.08.132

DOI

[6]
Deng M, Yang W T, Liu Q L, et al. Heterogeneous space-time artificial neural networks for space-time series prediction[J]. Transactions in GIS, 2018, 22(1):183-201. DOI: 10.1111/tgis.12302

DOI

[7]
梁艳平, 毛政元, 邹为彬, 等. 基于相似数据聚合与变K值KNN的短时交通流量预测[J]. 地球信息科学学报, 2018, 20(10):1403-1411.

DOI

[ Liang Y P, Mao Z Y, Zou W B, et al. Short-term traffic flow prediction based on similar data aggregation and KNN with varying K-value[J]. Journal of Geo-Information Science, 2018, 20(10):1403-1411. ] DOI: 10.12082/dqxxkx.2018.180281

DOI

[8]
姚卫红, 方仁孝, 张旭东. 基于混合人工鱼群优化SVR的交通流量预测[J]. 大连理工大学学报, 2015, 55(6):632-637.

[ Yao W H, Fang R X, Zhang X D. Traffic flow forecasting based on optimized SVR with hybrid artificial fish swarm algorithm[J]. Journal of Dalian University of Technology, 2015, 55(6):632-637. ] DOI: 10.7511/dllgxb201506011

DOI

[9]
Yu H Y, Wu Z H, Wang S Q, et al. Spatiotemporal recurrent convolutional networks for traffic prediction in transportation networks[J]. Sensors (Basel, Switzerland), 2017, 17(7):1501. DOI: 10.3390/s17071501

DOI

[10]
李明晓, 张恒才, 仇培元, 等. 一种基于模糊长短期神经网络的移动对象轨迹预测算法[J]. 测绘学报, 2018, 47(12):1660-1669.

[ Li M X, Zhang H C, Qiu P Y, et al. Predicting future locations with deep fuzzy-LSTM network[J]. Acta Geodaetica et Cartographica Sinica, 2018, 47(12):1660-1669. ] DOI: CNKI:SUN:CHXB.0.2018-12-012

DOI

[11]
Davis G A, Nihan N L. Nonparametric regression and short-term freeway traffic forecasting[J]. Journal of Transportation Engineering, 1991, 117(2):178-188. DOI: 10.1061/(ASCE)0733-947X(1991)117:2(178)

DOI

[12]
Yu B, Song X L, Guan F, et al. K-nearest neighbor model for multiple-time-step prediction of short-term traffic condition[J]. Journal of Transportation Engineering, 2016, 142(6):04016018. DOI: 10.1061/(ASCE)TE.1943-5436.0000816

DOI

[13]
Ryu U, Wang J A, Kim T, et al. Construction of traffic state vector using mutual information for short-term traffic flow prediction[J]. Transportation Research Part C: Emerging Technologies, 2018, 96:55-71. DOI: 10.1016/j.trc.2018.09.015

DOI

[14]
Cheng S F, Lu F, Peng P. Short-term traffic forecasting by mining the non-stationarity of spatiotemporal patterns[J]. IEEE Transactions on Intelligent Transportation Systems, 2020, 99:1-19. DOI: 10.1109/tits.2020.2991781

DOI

[15]
Cheng S F, Lu F, Peng P, et al. A spatiotemporal multi-view-based learning method for short-term traffic forecasting[J]. ISPRS International Journal of Geo-information, 2018, 7(6):218. DOI: 10.3390/ijgi7060218

DOI

[16]
Stathopoulos A, Karlaftis M G. A multivariate state space approach for urban traffic flow modeling and prediction[J]. Transportation Research Part C, 2003, 11(2):121-135. DOI: 10.1016/S0968-090X(03)00004-4

DOI

[17]
Rakthanmanon T, Campana B, Mueen A, et al. Searching and mining trillions of time series subsequences under dynamic time warping[J]. KDD: Proceedings International Conference on Knowledge Discovery & Data Mining, 2012, 2012:262-270. DOI: 10.1145/2339530.2339576

DOI

[18]
Chalapathy R, Chawla S. Deep learning for anomaly detection: A Survey[J]. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2019.

[19]
Cheng S F, Lu F, Peng P, et al. Short-term traffic forecasting: An adaptive ST-KNN model that considers spatial heterogeneity[J]. Computers, Environment and Urban Systems, 2018, 71:186-198. DOI: 10.1016/j.compenvurbsys.2018.05.009

DOI

Options
文章导航

/

〈 〉