基于时空卷积神经网络GL-GCN的交通流异常检测算法

徐红飞 李婧

摘  要：交通流异常检测通常要考虑时间信息、空间信息等信息，这让交通流异常检测变得具有挑战性。文章重点研究由交通事故、或短暂事件引起的非经常性交通异常检查。新提出的算法（GL-GCN）利用交通的时空数据，空间信息采用图卷积网络捕获，时间依赖性采用深度神经网络DeepGLO的方法建模。同时捕捉时空特性并建立预测交通流模型，利用异常分数来判断交通流异常。利用真实的交通流数据，证实了提出的模型具有有效性和优越性。

关键词：交通流;异常检测;深度神经网络;图卷积网络;时空特征

中图分类号：TP39         文献标识码：A 文章编号：2096-4706（2021）02-0070-06

Abstract：Traffic flow anomaly detection usually considers time information，spatial information and others，which makes traffic flow anomaly detection challenging. This paper focuses on the non-recurrent traffic anomaly inspection caused by traffic accidents or short-term events. The new algorithm（GL-GCN）uses the spatiotemporal data of traffic，the spatial information is captured by graph convolution network，and the time dependence is modeled by DeepGLO neural network. This algorithm captures spatiotemporal characteristics at the same time and establishes the traffic flow prediction model，and the traffic flow anomaly is judged by the anomaly score. The model is proved to be effective and superior by using the real traffic flow data.

Keywords：traffic flow;anomaly detection;deep neural network;graph convolutional network;spatiotemporal characteristics

0  引  言

異常检测是数据挖掘的一个重要分支，是发现数据集中异常的现象，在金融、安全、医疗、执法等领域有着广泛的应用。在交通工程领域，几十年来，在道路系统上安装了大量的交通监控设备，但是在这些交通状况数据的中，异常值是不可避免的[1]。通常异常值出现的原因包括两种，一种是由于设备故障等原因产生的错误数据或有效数据，另外一种导致异常值出现的原因可能代表特殊事件的发生，如交通事故或恶劣的天气条件。

交通流异常点或者异常序列在一定时间周期内，交通流数据与长期交通流数据偏离较大[2]。为了提高异常检测精度，一些研究应用了传统的机器学习来建立交通流异常检测模型，例如聚类、k-means、EM（Expectation-Maximization）[3]

等无监督模型和决策树，贝叶斯、支持向量机（support vector machine，SVM）[4]等有监督模型。还有一些学者利用LSTM（Long Short Term Memory networks）[5]、自动编码器[6]等深度神经网络提取交通流时间特征来检测交通流异常。传统的机器学习方法建模时，模型的准确率和有效性取决于数据的分布和大小，面对不同的数据时，适用性并不高。

Philip等人[7]提出了一种核平滑朴素贝叶斯（Kernel Smooth Naive Bayes，KSNB）方法，用于自动确定来自香港的交通数据中的错误数据和异常交通流。作者假定交通流数据遵循核平滑分布，KSNB模型自动确定数据由核分布形成的区域，这些区域以外的数据认为是异常数据。Turochy和Smith[8]提出了一种多变量统计质量控制（Multivariable Statistical Quality Control，MSQC）方法。此方法采用了其他交通流量变量（如平均速度和占用率），而不是使用一个单一的变量表示的流量值，这些变量导致了交通拥堵的情况。Dang等人[9]提出了一种基于KNN的交通异常值检测方法，命名为KNN-F。Ngan等人[10]提出了基于密度的有界LOF（BLOF），这是LOF算法[11]的一个修改版本。Munoz-Organero等人[12]提出了一种基于距离的滑动窗口中心（Sliding Window Center，SWC）算法，以检测由诸如交通信号灯、街道交叉口或环形交叉口的特定交通条件引起的异常驾驶位置。Shi等人[13]提出了一种称为动态空间和时间流（DSTF）的动态时空方法来检测时空流数据中的局部异常。基于分布的改进算法在不同场景的交通流异常检测也有很大的局限性，例如在高速公路和大城市两个场景中，城市道路的节点数量比较庞大，相对速度流比较小。高速公路的干路节点比较少，平均速度比较稳定且比较高。这两种的交通流异常判断需要依靠历史时间的交通流来分析，这就急需考虑时间特征。同时，不同道路的相互影响也是必须要考虑的因素。

随着神经网络的快速发展，深度神经网络具有很强的特征捕捉能力，更多学者开始使用深度学习来进行交通流异常检测。Wen等人[14]使用LVQ（Learning Vector Quantization）神经网络来检测城市主干路中的异常。利用LVQ神经网络聚合上下游的占有率、平均速度等等来检测异常。Hsu[15]提出了VRNN模型（Variational Recurrent Neural Network）来估计交通流时间序列的拥堵检测方法，同时利用了图卷积神经网络[16]（Graph Convolutional Network，GCN）模型来提取空间上的特征，两者结合来检测异常。

在传统的交通流异常检测模型当中，通常是提取时间、速度、车辆占有率等一些特征。这些特征并不能反映空间上交通的拓扑结构，这样可能对交通流的数据分析不准确，并且导致下游的任务产生比较大的误差。近几年，随着图卷积神经网络的发展，该技术在知识图谱分析、交通流预测中的运用越来越广。越来越多的时空卷积模型在交通流预测和交通流异常检测中被提出。在交通流预测模型中，大多数的预测结果稳定性并不高，一方面由于数据的不稳定性，另一方是由于面在时间特征捕捉时通常使用RNN和GRU等常用的模型，而这些算法在数据节点比较少时有比较好的结果，反之，在交通流比较长时表现的比较差。交通流异常检测模型中，如VRNN模型中，预测和异常检测的任务相对独立，并不能有效地完成端到端的学习任务，异常检测的准确度需要上游预测的有效性，不能完全适用于其他交通流数据集中。

在本文中，我们提出了一种基于深度学习的交通流异常检测的模型，采用端到端的方法联合捕捉交通流的时空特征来构造异常检测方法。其中，一方面利用图卷积神经网络学习交通道路之间的拓扑结构（空间），另一方面，利用深度神经网络DeepGLO[17]学习交通流的时间序列特征。使用两者共同建立交通流预测模型，然后根据预测值和真实值偏差设置异常分数，端到端地构建最终交通流异常检测模型。

1  交通流异常检测

1.1  GCN

GCN[16]可以有效地捕捉数据的空间特征，通过聚合数据节点特征来进行分类预测等任务。GCN算法首先给定一张有向图G=（V，E，W），其中V为有限集合，|V|=n个节点，E为所有边的集合，W∈?n×n为图G的权重矩阵。向量x∈?n为图节点上的输入信息，xi为第i节点信息。我们可以得到拉普拉斯矩阵L=D-W，其对应的分解为L=UΛUT，其中D为度矩阵（对角矩阵），对角线上元素依次为各个顶点的度且Dii= 。输入信号x的傅立叶变换为，逆变换为。因此，信号x经gθ滤波为：

其中，gθ（Λ）=diag（θ1λ1，…，θnλn），λ为拉普拉斯矩阵的特征值，θ∈?n为傅立叶系数的向量。为了使滤波器在空间中局部化和降低其计算复杂度，并利用切比雪夫多项式展开得到：

其中，gw（L）为基于w∈?K参数化的拉普拉斯矩阵的学习滤波器。，为k阶切比雪夫多项式。

1.2  问题定义

问题的描述和定义：

我们将道路网定义为G=（V，E，W），其中V为一个顶点集合，每个顶点对应于一个路段，E为一组边缘，每条边连接在网络中的两个路段之间，W为G的邻接矩阵，W矩阵中只包含0，1。如果两段道路之间有直接连接，那么Wi，j=1，否则Wi，j=0。在时间间隔t中，路段i的平均交通速度用vi（t）∈?n×T表示。

1.3  预测任务

通过GCN算法的模型预测交通流速度：

其中，n为历史交通数据的长度，l为预测数据长度。

交通流预测的好坏通常使用一个度量来衡量，这个度量在预测值和实际值之间进行计算。其中一个流行的度量是归一化绝对偏差度量：

其中 ∈?n×τ和vi（t）分别为第i条道路t时刻的预测值和真实值，n为道路的条数，τ为预测窗口的大小。式（4）中这个度量有时被称为WAPE（Weighted Absolute Percent Error）。式（5）度量被称为均方误差（Mean Square Error，MSE）MSE和WAPE都是预测好坏评价标准。预测速度的目标是最小化Loss（，vi（t））。

1.4  异常检测任务

通过将某条道路的当前交通流与历史交通流，临近时间交通流进行比较，得出该道路的车流异常值。时间序列的异常检测方法有很多，常见方法有基于密度的模型（Extreme Low Density Model）、深度神经网络自编码器[6]（Auto Encoder）、K-sigma模型、特定异常分数等等。

2  GL-GCN

在本部分将介绍我们提出的异常检测方法，本文中，交通流异常检测可分为两部分，第一部分（时空模块）基于历史交通流数据预测未来某段时间内的交通数据，第二部分是利用预测的交通数据信息与真实交通数据信息的偏差设置异常分数，最后通过对异常分数分布建模，使用高斯尾部概率来确定某条道路和某段时间的交通流异常。我们将交通流属性中的交通速度作为本次异常检测的对象。步骤分为两步：

第一步：先利用历史交通流数据导入时空卷积模块预测后面一段时间的交通流，得到预测值

第二步：异常分数设定，通过异常分数判断交通流是否异常。

如图1所示，我们的异常检测框架由两个模块组成：一个如图2所示的时空卷积块和一个异常检测模块。时空模块由GCN模块和时间卷积模块组成。其中，A为邻接矩形，X为交通流的速度值。我们可以充分利用交通数据中隐藏的空间相关性和时间相关性来完成我们的预测并异常检测任务。

2.1  预测模块

在预测模型中，常见的方法是采用基于RNN的模型，该模型在每个时刻上进行一次迭代，可以很好地捕捉时间依賴性性，建立时序模型，被广泛应用于深度神经网络中。但由于其卷积核大小的限制，不能很好地抓取长时的依赖信息，容易出现梯度爆炸等问题。因此，我们在时间卷积模块中添加时间卷积网络[18]（Temporal Convolutional Network，TCN）的改进版本DeepGLO来捕捉交通流的动态时间特征。TCN具有稳定的梯度、灵活的感受视野和内存需求小的优点，常用于语音识别，文本翻译等工作。DeepGLO可以捕捉局部和全局的时间特征，具有很强的灵活性。在本文任务中，我们对于DeepGLO的模型进行了改进。其中，将原始的DeepGLO中TCN的层数修改为双层，这样可以同时考虑长时和短时的依赖信息，同时，在增加层数和神经元的同时，为了更好地迭代和模型的稳定性，在模型中增加了残差网络。

在预测模块中，我们分别定义图卷积神经网络GCN和DeepGLO为G（·|Θg）和D（·|Θd），Θg为GCN网络神经元权重参数，Θd为DeepGLO网络神经元权重参数。那么整个预测任务输出为：

其中l为预测窗口大小，即预测速度窗口的大小。是一个超参数，在实验中可以设置。

那么整个预测任务的损失函数可以选择式（4）。

2.2  异常检测模块

在异常检测模块中，异常分数的设置为：

（1）先计算原始异常分数，在t时刻的异常分数为：

其中，π（v（t-1））为基于历史交通流数据预测值稀疏二进制编码，a（v（t））为真实数据的稀疏二进制编码。

（2）计算异常可能性：

3  实验

3.1  实验数据

为了评估我们提出的交通流异常检测模型：我们在METR-LA和PEMS-BAY两个数据集上进行实验，实验数据的信息如表1所示。METR-LA在洛杉矶县高速公路上的207个传感器上记录了四个月的统计数据。PEMS-BAY包含旧金山六个月内有关325传感器的传输速度信息。在数据预处理当中，我们采用了与DCRNN[19]（Diffusion Convolutional Recurrent Neural Network）模型相同的数据预处理过程。传感器的读数被汇总到5分钟的窗口中。道路的拓扑结构即节点的邻接矩阵由道路网络距离和带阈值的高斯核构造。Z-Score标准化后应用于输入。

3.2  基准模型

为了体现该模型预测的优越性，我们在实验中和几种常见的基准模型做了对比：

（1）ARIMA[20]（Autoregressive Integrated Moving Average）：卡尔曼滤波的自回归积分滑动平均模型;

（2）SVR[21]（support vector regression）：是SVM对回归问题的一种运用模型;

（3）WaveNet[22]：处理时间序列的卷积神经网络模型;

（4）DCRNN[19]：扩散卷积递归神经网络模型;

（5）STGCN[23]（Spatio-Temporal Graph Convolutional Networks）：时空图卷积网络，将图卷积与一维卷积相结合的模型。

为了更好地衡量交通流异常检测的优越性，和传统的几种异常检测方法在该数据集的实验结果进行对比：

（1）孤立森林算法[24]（Isolation Forest）：一种可以根据数据密度分布的无监督学习模型。

（2）高斯混合模型[25]（Gaussian Mixed Model，GMM）算法：一种与K均值类似的无监督聚类模型。

（3）自编码神经网络：利用编码解码之间的重构的误差来确定异常的神经网络模型。

3.3  实验结果

如表2和表3所示，通过实验比较了两个数据集使用提出的新算法GL-GCN和其他基准算法的表现，分别记录了预测15 min，30 min和60 min的交通速度时衡量误差的MAE、均方根误差（Root Mean Square Error，RMSE）。

从实验结果可以看出，我们提出的新模型在METR-LA的表现比基准模型ARIMA，SVR和WaveNet要出色，对应的MAE和MAPE在三个时间段预测的损失都明显较小。相对于其他的时空网络模型，我们提出的GL-GCN在预测15 min和30 min的表现都比较相互接近，但是在预测后面60 min交通流速度的MAE和MAPE分别为3.51和7.52，比其他两个基准模型更有优势，预测损失平均降低了2.87%。在数据集PEMS-BAY两个误差相对比较小，比前面常规的基准模型更加优异，在预测60 min交通速度，STGCN的误差值比较大，而本文提出的模型的MAE和RMSE的误差都最小，分别为3.51和7.32，预测损失平均降低了3.56%。为了更直接地比較GL-GCN在交通流上预测的优越性，图3所示为GL-GCN和STGCN两个模型在PEMS-BAY数据集上的预测结果，可以从图上看出，GL-GCN比STGCN预测的结果更加符合交通流随时间的变化趋势，表现更加稳定。我们认为造成这种情况的原因是，我们的模型比其他模型的网络结构更有鲁棒性，有效更好地结合交通流周期规律和道路之间拓扑结构来预测交通速度。

由于此公共交通流数据集没有异常标签，人工标注需要大量的人力物力，此次实验与几个在无监督异常算法来对比如图4，图5，图6，图7。通过实验对比发现，孤立森林和GMM算法的异常值检测结果比较相似，对最大值和最小值都比较敏感，但是有些在200时刻的有些速度也列入异常值范围，同时，在交通流数据上，速度接近70 km/h时也不能列入异常值范围。自编码神经网络在该数据上表现比前面两个基准模型更好，但是200时刻和500时刻附件的大部分速度也标记为异常值。GL-GCN模型结合时空卷积在该数据集上表现具有很强的优势和良好的性能，对一些突变点更加敏感。

4  结  论

针对交通流数据异常检测问题，本文提出了一个全新的基于时空卷积神经网络GL-GCN模型。该方法可以同时有效提取交通流的时间和空间特征，在两个公开数据集上与其他几个基准模型相比，确定了模型的优越性。在预测和异常检测两个实验对比上，GL-GCN相较于其他模型具有更好的稳定性和准确性。本文提出的GL-GCN具有以下几个贡献：

（1）将整个交通流异常检测任务分为预测和无监督异常检测两个模块，并实现了端到端的学习;

（2）本文的GL-GCN相对于其他模型更好地耦合时间和空间信息，让模型表现得更加稳定和有效;

（3）該模型可以捕捉交通流长时数据的依赖性，有效捕捉时间特征。

在未来工作中，如何将时空数据和在线学习结合起来，可以实时有效地检测交通流异常。

参考文献：

[1] 陈珂，邹权.融入时间关联因子曲线拟合的交通流异常挖掘方法 [J].计算机工程与设计，2013，34（7）：2561-2565.

[2] 黎维，陶蔚，周星宇，等.时空序列预测方法综述 [J].计算机应用研究，2020，37（10）：2881-2888.

[3] WU X D，KUMAR V，QUINLAN J R. Top 10 algorithms in data mining [J].Knowledge and Information Systems，2018，14：1-37.

[4] GIANNAKERIS P，KALTSA V，AVGERINAKIS K. Speed Estimation and Abnormality Detection from Surveillance Cameras [C]//2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops （CVPRW）.Salt Lake City：IEEE，2018：93-936.

[5] HOCHREITER S，SCHMIDHUBER J. Long Short-Term Memory [J].Neural Computation，1997，9（8）：1735-1780.

[6] KING D P，WELLING M. Auto-Encoding Variational Bayes [J/OL].arXiv：1312.6114v10 [stat.ML].（2014-05-01）.https：//arxiv.org/abs/1312.6114v10.

[7] PHILIP L，WANG L L，NGAN H Y T. Outlier Detection In Large-scale Traffic Data By Naitve Bayes Method and Gaussian Mixture Model Method [C]//Electronic Imaging，Intelligent Robotics and Industrial Applications using Computer Vision 2017.Society for Imaging Science and Technology，2017：73-78.

[8] TUROCHY R E，SMITH B L. Applying quality control to traffic condition monitoring [C]//ITSC2000. 2000 IEEE Intelligent Transportation Systems. Proceedings（Cat.No.00TH8493）.Dearborn，IEEE，2000：15-20.

[9] DANG T T，NGAN H Y T，LIU W. Distance-based k-nearest neighbors outlier detection method in large-scale traffic data [C]//2015 IEEE International Conference on Digital Signal Processing（DSP）.Singapore ：IEEE，2015：507-510.

[10] MA M X，NGAN H Y T，LIU W. Density-based Outlier Detection by Local Outlier Factor on Largescale Traffic Data [C]//Electronic Imaging，Image Processing：Machine Vision Applications IX.San Francisco：Society for Imaging Science and Technology：2016：1-4.

[11] MARKUS M，BREUNIG M M，KRIEGEL H P，et al. LOF：Identifying Density-Based Local Outliers [C]//Proceedings of the 2000 ACM SIGMOD international conference on management of data.Dallas：Association for Computing Machinery，2000：93-97.

[12] MUNOZ-ORGANERO M，RUIZ-BLAQUEZ R，S?NCHEZ-FERN?NDEZ L. Automatic detection of traffic lights，street crossings and urban roundabouts combining outlier detection and deep learning classification techniques based on GPS traces while driving [J].Computers，Environment and Urban Systems，2018，68：1-8.

[13] SHI Y，DENG M，YANG X X，et al. Detecting anomalies in spatio-temporal flow data by constructing dynamic neighbourhoods [J].Computers，Environment and Urban Systems，2018，67：80-96.

[14] WEN H Y，LUO J. Traffic Incident Detection for Urban Arterial Road Based on Data Fusion and Learning Vector Quantization [C]//First International Conference on Transportation Information and Safety（ICTIS）.Wuhan：American Society of Civil Engineers，2011.

[15] HSU D. Anomaly Detection on Graph Time Series [J/OL].arXiv：1708.02975v2 [cs.LG].（2017-11-01）.https：//arxiv.org/abs/1708.02975v2.

[16] DEFFERRARD M，BRESSON X，VANDERGHEYNST P.Convolutional neural networks on graphs with fast localized spectral filtering [C]//NIPS16：Proceedings of the 30th International Conference on Neural Information Processing Systems.Red Hook：Curran Associates Inc.，2016：3844-3852.

[17] SEN R，YU H F，DHILLON I.Think Globally，Act Locally：A Deep Neural Network Approach to High-Dimensional Time Series Forecasting [J/OL].arXiv：1905.03806v2 [stat.ML].（2019-10-27）.https：//arxiv.org/abs/1905.03806v2.

[18] BAI S J，KOLTER Z，KOLTUN V. An Empirical Evaluation of Generic Convolutional and Recurrent Networks for Sequence Modeling [J/OL].arXiv：1803.01271v2 [cs.LG].（2018-04-19）.https：//arxiv.org/abs/1803.01271v2.

[19] LI Y G，YU R，SHAHABI C，et al. Diffusion Convolutional Recurrent Neural Network：Data-Driven Traffic Forecasting [J/OL].arXiv：1707.01926v3 [cs.LG].（2018-01-22）https：//arxiv.org/abs/1707.01926v3.

[20] AHMED M S，COOK A R. Analysis of freeway traffic time series data by using Box-Jenkins techniques [J].Transportation Research Record Journal of the Transportation Research Board，1979，773（722）：1-9.

[21] SMOLA A J，SCH?LKOPF B. A tutorial on support vector regression [J].Statistics and Computing，2004，14：199-222.

[22] OORD A V D，DIELEMAN S，ZEN H，et al. WaveNet：A Generative Model for Raw Audio [J/OL].arXiv：1609.03499v2 [cs.SD].（2016-08-19）.https：//arxiv.org/abs/1609.03499v2.

[23] YU B，YIN H T，ZHU Z X.Spatio-Temporal Graph Convolutional Networks：A Deep Learning Framework for Traffic Forecasting [J/OL].arXiv：1709.04875v4 [cs.LG].（2018-07-12）.https：//arxiv.org/abs/1709.04875v4.

[24] LIU F T，TING K M，ZHOU Z H. Isolation Forest [C]//2008 Eighth IEEE International Conference on Data Mining.Pisa：IEEE，2008：413-422.

[25] KHANSARI-ZADEH S M，BILLARD A. Learning Stable Nonlinear Dynamical Systems With Gaussian Mixture Models [J].IEEE，2011，27（5）：943-957.

作者简介：徐红飞（1995—），男，汉族，江苏宿迁人，硕士研究生在读，主要研究方向：大数據挖掘，智能运维等;李婧（1980—），女，汉族，上海，副教授，硕士研究生导师，博士研究生，主要研究方向：计算机网络通信算法、智能电网、无线传感器网络等。