基于自注意力機制與圖自編碼器的路網(wǎng)交通流數(shù)據(jù)修復(fù)模型

張偉斌，張蒲璘，蘇子毅，孫鋒

(1.南京理工大學(xué)，a.電子工程與光電技術(shù)學(xué)院，b.計算機科學(xué)與工程學(xué)院，南京210094；2.山東理工大學(xué)，交通與車輛工程學(xué)院，山東淄博255000)

0 引言

隨著大量傳感器的部署，人們從多種渠道收集到海量的交通數(shù)據(jù)。這些數(shù)據(jù)往往“真假共存”，存在缺失、錯誤、冗余等異常現(xiàn)象。傳感器數(shù)據(jù)是數(shù)據(jù)分類、回歸預(yù)測、交通信號控制優(yōu)化等任務(wù)的基礎(chǔ)，數(shù)據(jù)的缺失會影響后續(xù)的算法性能，因此需要智能交通系統(tǒng)(ITS)盡可能準(zhǔn)確地修復(fù)缺失數(shù)據(jù)，提高數(shù)據(jù)完整度。交通數(shù)據(jù)修復(fù)問題有其固有的特殊性，需要考慮空間路網(wǎng)拓撲結(jié)構(gòu)和數(shù)據(jù)隨時間變化的規(guī)律性和突變性[1]，故針對交通流數(shù)據(jù)修復(fù)問題需要設(shè)計適合交通流特征的模型。

數(shù)據(jù)修復(fù)需要設(shè)計合適的算法從多維數(shù)據(jù)中提取變化規(guī)律，挖掘出數(shù)據(jù)間的相互依賴關(guān)系。傳統(tǒng)數(shù)據(jù)修復(fù)方法存在局限性，對數(shù)據(jù)有較強的前提假設(shè)，如線性[2]，平滑[3]等。近年來深度神經(jīng)網(wǎng)絡(luò)被應(yīng)用于交通流數(shù)據(jù)修復(fù)、預(yù)測等問題，取得了良好的效果。有學(xué)者從時間序列的長短時依賴關(guān)系出發(fā)，利用序列化模型對缺失數(shù)據(jù)進行修復(fù)。Berglund 等[4]提出了雙向循環(huán)神經(jīng)網(wǎng)絡(luò)修復(fù)模型。序列化的模型雖然可以有效學(xué)習(xí)到時間序列的長短時依賴關(guān)系，但通常難以同時捕獲時空關(guān)聯(lián)性。Vaswani 等[5]提出的Transformer 模型在自然語言處理問題上取得較好的效果，Self-Attention機制也隨之應(yīng)用在缺失數(shù)據(jù)填補問題。上述模型雖然可以對道路交通流數(shù)據(jù)進行有效地修復(fù)，但均僅對某條道路進行時間序列分析，無法應(yīng)用于較大范圍的城市路網(wǎng)中。

隨著圖卷積神經(jīng)網(wǎng)絡(luò)的發(fā)展，一些學(xué)者將其應(yīng)用在交通流數(shù)據(jù)預(yù)測中，并取得了良好效果。研究表明，通過GCN將路網(wǎng)信息嵌入到交通流預(yù)測模型中可以提高預(yù)測準(zhǔn)確率。Wang等[6]提出的STGNN(Spatial-temporal Graph Convolutional Networks)模型將路網(wǎng)結(jié)構(gòu)嵌入到模型中，并將S-GNN層加入到GRU(Gated Recurrent Units)的狀態(tài)更新中，明顯提高了模型預(yù)測準(zhǔn)確率。自編碼器作為一種端對端模型在數(shù)據(jù)修復(fù)中也取得良好效果。Zhang等[7]發(fā)現(xiàn)，圖神經(jīng)網(wǎng)絡(luò)會使節(jié)點之間的信息產(chǎn)生較多的共享，導(dǎo)致節(jié)點特征丟失。因此，將GCN直接應(yīng)用于數(shù)據(jù)修復(fù)模型中會降低修復(fù)效果。

本文針對路網(wǎng)交通流數(shù)據(jù)修復(fù)問題提出一種基于多頭注意力機制和圖卷積網(wǎng)絡(luò)的修復(fù)模型。該模型采用自編碼器結(jié)構(gòu)，其中所提出的時空圖卷積網(wǎng)絡(luò)(Spatial-Temporal Graph Convolutional Networks,STGCN)可以學(xué)習(xí)路網(wǎng)拓撲結(jié)構(gòu)，捕獲數(shù)據(jù)中潛在的時空關(guān)聯(lián)性。與傳統(tǒng)GCN 不同的是，STGCN通過計算道路自注意力和一階相鄰道路注意力值構(gòu)成道路權(quán)重矩陣，代替?zhèn)鹘y(tǒng)GCN 中的鄰接矩陣。STGCN使用LSTM網(wǎng)絡(luò)捕獲數(shù)據(jù)中的時序規(guī)律，將處理后的數(shù)據(jù)代替GCN 中的圖信號加入模型計算。此外，模型加入了Multihead-Attention 層捕獲STGCN 難以利用的數(shù)據(jù)特征，即二階及高階鄰接道路的空間關(guān)聯(lián)性；位于缺失時刻后的數(shù)據(jù)與缺失數(shù)據(jù)的時間關(guān)聯(lián)性，起到對STGCN 層的補充作用。Multihead-Attention 層以殘差鏈的形式加入模型，可以使模型更快收斂。最后使用全連接網(wǎng)絡(luò)輸出修復(fù)結(jié)果。本文方法在實際數(shù)據(jù)集中進行驗證，實驗表明，該模型較一些常用模型取得了更好的修復(fù)效果。

1 問題定義

路網(wǎng)結(jié)構(gòu)可視為一個以雙向道路為節(jié)點的拓撲圖結(jié)構(gòu)。該圖可定義為，其中，V為城市N條雙向路路段的節(jié)點集合，為編號為N的雙向路路段。ε為邊的集合，連接著圖中的N個節(jié)點。這些節(jié)點的連接關(guān)系用一個鄰接矩陣來表示，其中，表示路段vi和vj的連接關(guān)系，i,j為矩陣的行列號，同時也表示道路的編號。如果vi和vj相鄰，則為1，否則為0，由此鄰接矩陣A為對稱矩陣。將交通流數(shù)據(jù)視為在該圖上的時間圖信號序列，如在t時刻道路i交通流數(shù)據(jù)vi,t視為節(jié)點vi在t時刻的信號值，在t時刻城市路網(wǎng)交通流數(shù)據(jù)視為圖信號。假設(shè)節(jié)點的個數(shù)和鄰接關(guān)系不變，城市的交通流數(shù)據(jù)可以表示為圖信號序列，如圖1所示，其中，tn為觀測時刻，為tn時刻城市的交通流數(shù)據(jù)。

圖1 城市路網(wǎng)交通流數(shù)據(jù)的圖信號序列示意圖Fig.1 Schematic diagram of graph signal sequence of urban road network traffic flow data

2 模型構(gòu)建

圖2 為本文模型結(jié)構(gòu)。模型主要包括兩個部分：①STGCN 利用LSTM 網(wǎng)絡(luò)、注意力網(wǎng)絡(luò)、GCN網(wǎng)絡(luò)結(jié)合圖信號和鄰接矩陣，對交通流數(shù)據(jù)的時空關(guān)系進行捕捉和提取，并填補缺失部分；②由Multihead-Attention直接學(xué)習(xí)交通流數(shù)據(jù)中的特征關(guān)系。值得注意的是Multihead-Attention 相比于STGCN，結(jié)構(gòu)更加簡單，可將其視為STGCN 的一條特殊殘差鏈。

圖2 模型結(jié)構(gòu)圖Fig.2 Model structure diagram

2.1 STGCN

路網(wǎng)拓撲圖G(V),ε包含城市路網(wǎng)的道路連接信息。對于這一空間拓撲結(jié)構(gòu)，模型借助Kipf 等[7]提出的GCN 捕獲空間特征，對缺失路段數(shù)據(jù)使用臨近路段數(shù)據(jù)填補。GCN計算過程為

式中：σ為激活函數(shù)；為主對角線對稱矩陣，，A為鄰接矩陣，I為單位陣；?為?的度矩陣，且為節(jié)點i的一階鄰居個數(shù)之和加1，為矩陣?對角線上的值；W為可學(xué)習(xí)參數(shù)；Xin和Xout為圖信號矩陣，分別為矩陣的輸入和輸出。由式(1)可得出對于某個點的信號值是由其自身的信號值和其一階相鄰信號值加權(quán)求和得到，其形式如圖3所示。

圖3 GCN層映射關(guān)系Fig.3 Graph convolutional networks layer mapping

除了空間關(guān)聯(lián)性，交通流數(shù)據(jù)還具有較強的時間關(guān)聯(lián)性，對這一特性的提取和捕獲依賴能夠?qū)r間序列建模的網(wǎng)絡(luò)。LSTM 網(wǎng)絡(luò)作為一種時序網(wǎng)絡(luò)可以對數(shù)據(jù)中的時間關(guān)聯(lián)性進行捕獲和學(xué)習(xí)。基于GCN 和LSTM，提出STGCN 網(wǎng)絡(luò)對交通流數(shù)據(jù)中的時空關(guān)聯(lián)性進行捕獲和提取，并基于提取的時空關(guān)聯(lián)性填補缺失數(shù)據(jù)。網(wǎng)絡(luò)結(jié)構(gòu)如圖4所示。

圖4 STGCN結(jié)構(gòu)圖Fig.4 STGCN structure diagram

STGCN 通過LSTM 對圖信號X預(yù)處理，利用數(shù)據(jù)的時序關(guān)系得到，將其傳入GCN 作為圖信號。值得注意的是，STGCN沒有像GCN直接使用鄰接矩陣，而是通過注意力網(wǎng)絡(luò)對道路的重要性進行估算，并生成一個道路權(quán)重矩陣替代鄰接矩陣。的計算過程為：先使用一層LSTM網(wǎng)絡(luò)對圖信號數(shù)據(jù)進行預(yù)處理，再通過單層注意力網(wǎng)絡(luò)計算道路間重要性系數(shù)eij組成道路權(quán)重矩陣。預(yù)處理的作用為：對交通流數(shù)據(jù)中的時間關(guān)聯(lián)性進行提取，并在缺失部分填補與歷史數(shù)據(jù)有關(guān)的初始值；原始信號的表達力不夠強，通過LSTM對其進行預(yù)處理，轉(zhuǎn)換為表達力更強的數(shù)據(jù)輸入到道路注意力網(wǎng)絡(luò)中，使得道路注意力網(wǎng)絡(luò)更容易地學(xué)習(xí)出道路之間的權(quán)重關(guān)系。

由道路注意力網(wǎng)絡(luò)計算出道路間重要性系數(shù)eij組成道路權(quán)重矩陣的計算過程為

式中：a為注意力函數(shù)；K為道路注意力頭數(shù)；k為注意力編號；eij為道路i與道路j的關(guān)聯(lián)系數(shù)，且eij≥0。

道路注意力網(wǎng)絡(luò)通過計算道路重要性系數(shù)，生成道路權(quán)重矩陣。將和代入式(1)，得到GCN 網(wǎng)絡(luò)的輸出。由于網(wǎng)絡(luò)結(jié)構(gòu)較為復(fù)雜，為加快模型收斂速度，使模型更容易學(xué)習(xí)到梯度下降方法，STGCN加入了殘差鏈結(jié)構(gòu)，將輸入圖信號與輸出相加。計算過程為

式中：σ為激活函數(shù)，實際中，模型選用Relu 作為激活函數(shù)；為由eij組成的道路權(quán)重矩陣，且沿主對角線對稱；為的度矩陣，且為預(yù)處理后的圖信號；X為原始輸入圖信號；W為可學(xué)習(xí)的參數(shù)。

2.2 Multihead-Attention

實際中每條道路的交通流數(shù)據(jù)不僅會與自身和一階臨近道路相關(guān)，與其他道路也可能存在關(guān)聯(lián)性。然而STGCN僅能對每個道路自身的歷史數(shù)據(jù)和一階相鄰數(shù)據(jù)關(guān)聯(lián)性進行學(xué)習(xí)。除此以外，STGCN 使用的是LSTM 網(wǎng)絡(luò)，只能利用缺失時刻前的歷史數(shù)據(jù)與缺失數(shù)據(jù)的時間關(guān)系。然而在實際問題中，缺失數(shù)據(jù)常常位于數(shù)據(jù)的中間部分，即缺失前后時刻的數(shù)據(jù)都是已知的。對于這些STGCN難以捕獲的特征規(guī)律，模型利用Multihead-Attention 層，通過對整個樣本計算注意力權(quán)值，捕獲和學(xué)習(xí)數(shù)據(jù)中所有道路所有時段之間的關(guān)系。

2.3 位置編碼

由于注意力模塊中不包含輸入數(shù)據(jù)位置信息的計算，因此需要人為生成一些關(guān)于序列中標(biāo)記的相對或絕對位置的信息并加入到輸入數(shù)據(jù)中。受Transformer[5]的啟發(fā)，使用不同頻率的正弦和余弦采樣值作為位置編碼的信息，即

式中：p為輸入數(shù)據(jù)的位置；d為維度；dmodel為輸入的時間維度長度。在修復(fù)問題中，對于一天中的不同采集時刻，計算的位置編碼不同。

2.4 全連接層

在每一個S-GCN 和注意力層后，加入層歸一化和全連接層。層歸一化能增加模型的穩(wěn)定性，全連接層可對提取的特征進行整合，并給出一個響應(yīng)值。因為所用數(shù)據(jù)集中本身存在缺失，將缺失值視為真實值參與訓(xùn)練會降低模型的修復(fù)效果，故只將有檢測數(shù)值的部分代入損失函數(shù)中計算，模型的損失函數(shù)為

式中：y為真實數(shù)據(jù)；?為模型輸出值；N′為批大小，在實驗中取N′=32；為數(shù)據(jù)矩陣中某處是否成功檢測到數(shù)據(jù)，如果存在檢測數(shù)據(jù)，則為1，否則為0。

2.5 模型結(jié)構(gòu)總結(jié)

本文提出的STGCN網(wǎng)絡(luò)能計算道路之間的重要性系數(shù)，并借由GCN結(jié)構(gòu)重組和整合數(shù)據(jù)，以填補缺失數(shù)據(jù)。但是STGCN存在一些難以捕獲的有用信息，如道路與其二階到高階相鄰點的交通流數(shù)據(jù)關(guān)聯(lián)性，缺失數(shù)據(jù)與該路段的歷史數(shù)據(jù)和未來數(shù)據(jù)的關(guān)系。針對這些問題，模型采用Multihead-Attention 網(wǎng)絡(luò)加以補充。此外，模型中每一個STGCN 和Multihead-Attention 后都加入了Layer-Normalization，確保梯度下降能傳播到網(wǎng)絡(luò)的每一層，并添加了全連接層用于信息的整合和提高收斂速度。

3 實驗驗證

3.1 數(shù)據(jù)集

實驗部分所用數(shù)據(jù)集來自某市187 個交叉口的SCATS 運行記錄解析后的真實數(shù)據(jù)，數(shù)據(jù)采集時間間隔為5 min，采集日期為2018年6月1日-8月31日。路網(wǎng)區(qū)域范圍如圖5所示，圖中，白色點位是無法獲取數(shù)據(jù)的交叉口，黑色點位是能夠獲取數(shù)據(jù)的交叉口。

圖5 路網(wǎng)區(qū)域范圍Fig.5 Road network area

以相鄰兩交叉口為一個路段，共得到277個路段，將各路段原始流量數(shù)據(jù)聚合為5 min 步長的等時間間隔數(shù)據(jù)。樣本構(gòu)造方式為在數(shù)據(jù)集上沿著空間和時間兩個維度滑動截取?？臻g上按照道路編號順序滑動截取每60 條道路，空間滑動步長為1。時間上滑動每截取連續(xù)的60個時間點，時間間隔為5 min，時間滑動步長為10。挑選出缺失率低于30%的樣本作為實驗數(shù)據(jù)集，共計324383 個樣本。根據(jù)路網(wǎng)道路信息可得到道路之間的連接關(guān)系并構(gòu)成鄰接矩陣，總道路鄰接矩陣的維度為(277，277)，每個樣本的維度為(60，60)，樣本的鄰接矩陣維度為(60，60)。在實驗數(shù)據(jù)集中隨機選取80%作為訓(xùn)練集，剩余20%作為測試集。實驗中模型使用Adam 優(yōu)化器，學(xué)習(xí)率α=0.005，批大小Batchsize為32。

針對交通流量的缺失特點設(shè)計3種缺失模式：塊狀缺失，時間條狀缺失和空間條狀缺失。

(1)連續(xù)路段上的連續(xù)時間缺失

如圖6(a)所示，數(shù)據(jù)在連續(xù)的檢測線圈上發(fā)生時間上的連續(xù)缺失，造成的原因可能是路側(cè)控制處理單元的數(shù)據(jù)傳送到監(jiān)控分中心的過程中發(fā)生丟失。

(2)特定時間上在采集設(shè)備上的連續(xù)缺失

如圖6(b)所示，某些時刻的數(shù)據(jù)未采集，造成的原因可能是通信或者系統(tǒng)故障。

(3)特定采集設(shè)備在時間上的連續(xù)缺失

如圖6(c)所示，某些采集線圈數(shù)據(jù)未收集，造成的原因可能是單個線圈損壞導(dǎo)致該路段數(shù)據(jù)未采集，或是某些路口未安裝檢測設(shè)備。

而二進制粒子群算法[6]，速度更新公式不變，含義有所變化。狀態(tài)空間中的每一個粒子的位置xid值為0或1，選擇哪個則取決于vid的大小，即速度為位置取值的概率。分兩種情況：① vid較大，xid較大概率取1，較小概率取0；② vid較小，xid較大概率取0，較小概率取1。

圖6 缺失模式展示Fig.6 Missing pattern

3.2 數(shù)據(jù)實驗

為驗證所提模型的有效性，選取4個基準(zhǔn)模型(HA，KNN，AE，M-RNN)進行數(shù)據(jù)實驗對比。

3.2.1 基準(zhǔn)模型

仿真實驗里神經(jīng)網(wǎng)絡(luò)模型均通過TensorFlow神經(jīng)網(wǎng)絡(luò)計算庫搭建。各種基準(zhǔn)模型的介紹如下：

(1)歷史平均(Historical average,HA)

滑動歷史平均模型使用歷史交通流量的時間平均值作為填補值，進行數(shù)據(jù)修復(fù)。

(2)K-最近鄰(K-nearest neighbor,KNN)

使用插值函數(shù)利用鄰近k長度向量插補缺失值。在實際部署過程中，k值設(shè)置為3。

通過構(gòu)建包含3 個全連接層的自編碼器達到對輸入數(shù)據(jù)重構(gòu)的目的。每個全連接層的神經(jīng)元個數(shù)為60，激活函數(shù)使用Sigmoid，并使用Adam優(yōu)化算法反向傳播。

(4)雙向循環(huán)神經(jīng)網(wǎng)絡(luò)[8](Multi-directional Recurrent Neural,M-RNN)

M-RNN 由包括60 個神經(jīng)元的雙向LSTM 組成，使用Adam梯度下降算法進行網(wǎng)絡(luò)訓(xùn)練。

3.2.2 評價指標(biāo)

為比較不同修復(fù)模型的性能，采用MAE 和RMSE 評價修復(fù)數(shù)據(jù)和缺失處真實數(shù)據(jù)之間的偏差。

平均絕對誤差(MAE)表示兩矩陣平均絕對誤差，公式為

平均根方誤差(RMSE)表示兩矩陣根均方誤差，公式為

式中：Yb為缺失處真實數(shù)據(jù)；為缺失處真實數(shù)據(jù)；B為批大小Batchsize，實驗中為32。

3.2.3 實驗結(jié)果

根據(jù)上述模型和生成的修復(fù)數(shù)據(jù)，對各個模型的實驗結(jié)果進行分析。表1～表3 為不同修復(fù)算法在3種缺失場景，以及不同數(shù)據(jù)缺失率情況下的修復(fù)表現(xiàn)。在絕大多數(shù)情況下，基于SA-GAE(Self-Attention Graph Auto-Encoder)的方法獲得最佳的修復(fù)精度。

表1 場景1下的數(shù)據(jù)修復(fù)表現(xiàn)Table 1 Data imputation performance under scenario 1

表2 場景2下的數(shù)據(jù)修復(fù)表現(xiàn)Table 2 Data imputation performance under scenario 2

表3 場景3下的數(shù)據(jù)修復(fù)表現(xiàn)Table 3 Data imputation performance under scenario 3

HA 和統(tǒng)計學(xué)模型KNN 方法沒有考慮交通數(shù)據(jù)的突變性及路網(wǎng)拓撲圖結(jié)構(gòu)關(guān)系，不能對交通數(shù)據(jù)的時間關(guān)聯(lián)性加以利用，產(chǎn)生的修復(fù)值可靠性不強，與缺失部分的真實值關(guān)聯(lián)度較低，因此修復(fù)結(jié)果不佳。

自編碼器方法能夠?qū)?shù)據(jù)中的關(guān)聯(lián)性進行學(xué)習(xí)和捕獲，取得了一定的修復(fù)效果，但是缺少對交通流數(shù)據(jù)特性的針對性設(shè)計，并且無法學(xué)習(xí)空間路網(wǎng)拓撲圖結(jié)構(gòu)，故修復(fù)效果難以進一步的提高。M-RNN 由于可對時間序列建模，在缺失模式1，2下取得了不錯的效果；但是在缺失模式3 下，由于其無法利用空間路網(wǎng)拓撲圖結(jié)構(gòu)，不能捕獲缺失道路與其臨近道路數(shù)據(jù)之間的關(guān)系，難以有效修復(fù)缺失數(shù)據(jù)。

本文提出的SA-GAE 模型不僅可以對數(shù)據(jù)中的時空關(guān)聯(lián)性進行學(xué)習(xí)，還能利用空間路網(wǎng)拓撲圖結(jié)構(gòu)進一步提高修復(fù)效果。通過ST-GCN 網(wǎng)絡(luò)捕獲路網(wǎng)數(shù)據(jù)中蘊含的時間規(guī)律，并利用拓撲圖結(jié)構(gòu)學(xué)習(xí)一階相鄰道路數(shù)據(jù)中的空間關(guān)聯(lián)性。對于STGCN難以捕獲的殘余關(guān)聯(lián)性，本文使用Multihead-Attention 進行學(xué)習(xí)并以殘差鏈的形式加入到網(wǎng)絡(luò)中，最終達到精確修復(fù)缺失數(shù)據(jù)的目的，在多種缺失模式下取得最優(yōu)效果。以圖7為修復(fù)示例，其為SA-GAE 模型在缺失模式2 下，缺失率為50%時的修復(fù)結(jié)果，其中第1行為輸入的缺失數(shù)據(jù)，第2行為模型輸出的修復(fù)結(jié)果，第3行為對應(yīng)的真實完整數(shù)據(jù)。通過式(9)和式(10)對圖7中缺失部分的修復(fù)值與真實值計算誤差，MAE 為29.81，RMSE 為44.16。與自編碼器相比，相同缺失率下MAE 下降了30.70，RMSE 下降了42.10；與M-RNN 相比，MAE下降了4.21，RMSE下降了3.67。

圖7 SA-GAE修復(fù)結(jié)果示意圖Fig.7 Schematic diagram of SA-GAE repair results

4 結(jié)論

本文針對路網(wǎng)交通流數(shù)據(jù)修復(fù)問題，提出一種基于多頭注意力機制和圖卷積網(wǎng)絡(luò)的數(shù)據(jù)修復(fù)模型SA-GAE。與其他修復(fù)模型相比，該模型可以學(xué)習(xí)城市路網(wǎng)拓撲結(jié)構(gòu)，捕獲交通流數(shù)據(jù)中的時空規(guī)律，并基于捕獲到的時空規(guī)律對缺失數(shù)據(jù)進行有效修復(fù)。并且，該模型能夠應(yīng)用于復(fù)雜城市路網(wǎng)結(jié)構(gòu)多種缺失情景下的數(shù)據(jù)修復(fù)問題。真實城市路網(wǎng)交通流數(shù)據(jù)實驗結(jié)果表明，該模型相比常用的修復(fù)模型在多種缺失率和缺失場景下均取得了較好的修復(fù)效果。