基于時空卷積神經網絡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—），女，漢族，上海，副教授，碩士研究生導師，博士研究生，主要研究方向：計算機網絡通信算法、智能電網、無線傳感器網絡等。