基于時空相關性的交通物聯網缺失數據填補算法

梁慶，付青坤，田海安，彭志浩

(1.中鐵城市發展投資集團有限公司，四川成都 610000；2.長安大學信息工程學院，陜西西安 710064)

0 引言

隨著以交通物聯網為基礎的智慧高速的發展，通過全面感知道路基礎設施、行駛車輛等交通參與方的數據，可有效開展面向安全和效率的主動智慧管控，為基于車路協同的無人駕駛提供技術支撐，提升交通運輸的安全性、高效性和舒適性。

然而在智能感知的過程中，一方面，由于智能網聯汽車的數量快速增長，帶來的海量數據傳輸和計算問題更加突出；另一方面，移動邊緣計算的介入，車載移動端和路側設備之間數據的無線傳輸占比增加，而由于車輛的移動性和傳輸環境的時變性，導致多徑傳輸和多普勒效應也愈加突出。上述問題會使數據采集時存在缺失和誤碼的概率提高，然而由于部分業務具有嚴苛的實時性要求，不能采用出錯重傳機制，因此，在接收端對關鍵數據進行自主的前向糾錯，重建缺失數據將是必然選擇。

數據缺失主要來自兩方面：一方面，傳感器的故障會導致不定期的數據空白，這種缺失往往持續時間較長，很難用算法進行填補重建，不屬于本文研究的范疇。另一方面，由于數據傳輸過程中的信道噪聲，而導致的零星誤碼或缺失，可通過本文的方法進行數據填補重建，這是本文的研究內容。

當前，數據重建技術分為時域、頻域和空域三大類。對于時域重建技術，主要依據同一傳感數據在時間序列上的相關性進行數據填補，文獻[1]從已有數據中提取不同類型的數據基信號，并利用基于時間序列的線性關聯映射重建缺失數據。文獻[2]基于傳感數據在一個嵌套滑動窗口內的相關性，提出一種數據流缺失恢復方法。文獻[3]提出一種針對缺失數據的譜分析方法，通過更新估算因子來修正時域重建算法，提高數據重建精度。

文獻[1-3]均利用了時域數據的隨機平穩特性，適合數據變化不大的靜態物聯網領域。例如河道水位檢測、交通基礎設施的狀態檢測等。但對于車速、斷面流量等和交通流密切相關的實時交通元素，數據雖然具有廣義隨機平穩特性，但時域變化劇烈，時域相干窗口較小，在此窗口內采集到的原始有效數據較少，提取的特征值往往離散度大，若加大插值窗口又會導致緩存數據過多，處理時延長，且數據的時域關聯性呈時間選擇性衰落，適用性難以保障。

關于數據重建在空域中的研究，主要通過分析多個傳感器在空間部署位置的相關性來提取傳感數據的屬性特征，進而估計缺失數據。文獻[4]提出一種KNN算法，通過在特征空間中尋找與缺失數據屬于同一類的相鄰K個樣本，對其加權平均后估計并重建缺失數據。文獻[5]將邏輯回歸模型與多重插補算法相結合，但該方法僅適用于缺失率較低的情況。文獻[6]則提出一種基于壓縮感知的低秩數據重建算法，利用傳感設備存在的空間相關性和數據的低秩特征，重建缺失數據，然而其低秩特征并不適合多類型混合接入的交通物聯網采集系統。

隨著以機器學習為代表的人工智能算法的興起，通過強大的計算機算力，在交通大數據中提取非線性的時空屬性特征，搭建多粒度的數據格式以及數學描述方法，重建缺失數據，已成為研究熱點。文獻[7]利用相鄰傳感節點的小波系數相關性，通過逆小波變換和時頻回歸模型來重建缺失數據，該方法精度高，但實現復雜度偏高。文獻[8]利用逆向傳播(Back Propagation，BP)神經網絡對單一的交通流量進行預測，但并不適用于具有非結構化特征的交通物聯網數據。

在公路交通領域，機電設備的類型適中，空間部署呈線性分布，具有明顯的空間相關特性，且感知對象聚焦于交通流、交通事件、氣象等固定類型，但數據具有一定“定時漂移”特征，即“此時此處”的數據和“彼時彼處”的數據更具相關性。因此，本文通過分析高速公路交通感知數據的特性，提出一種基于時空相關性的線性插值神經網絡(LIN_BP)數據恢復算法，將時域和空域特征相結合來恢復缺失數據。

1 基于時域平穩性的線性插值預處理

目前，在公路交通領域中，在靠近傳感器的感知接入層，仍然有較多非智能感知設備，例如輸出電流信號的液位計，電壓信號的壓力傳感器，這些設備有些部署無法進行有線傳輸的移動終端，有些是后裝的感知設備，不具備有線傳輸條件，無奈采用無線傳輸方式。一旦數據接入路側設備后，就會采用更加可靠的光纖有線傳輸。因此，本文重點針對因無線傳輸導致的數據缺失。

由于無線傳輸環境的開放性和時變性，數據傳輸過程中經常會受到各種干擾和噪聲的影響，例如車輛馬達產生的寬頻干擾脈沖和毛刺噪聲，這些干擾會導致信號傳輸出現連續的誤碼，而常用的卷積碼加交織的信道編碼技術，僅對零星的非連續誤碼有效，因此，有必要對數據進行預處理，將連續的缺失數據或異常數據位變為零星的單個孤立缺失數據位。

對于多數輸出模擬信號的傳感器，在連續時間內采集到的非電量數值非常相近甚至相同。因此，可利用感知數據的時間相關性，構建線性函數來粗略估算缺失數據。該方法優勢在于復雜度低，適合對時延敏感的實時性業務。

線性插值的基本原理是：假設ti時刻的數據xi缺失，在其附近的tp和tq時刻的傳感器數值為xp和xq，經過線性插值后的估計值為

插值窗口尺寸M的選擇至關重要，若取值太小，缺失數據點占比過高，容易受到周圍噪聲和毛刺的影響，影響插值的精度。若取值太大，計算復雜度升高，導致產生較大的處理時延。一般的經驗原則是，在插值窗口內，缺失數據點占比不超10%，且與待重建信號的中心頻率成反比，頻率越高，說明數據變化越快，時域相干窗口應越小。通過選擇合適的窗口大小，對多個缺失數據進行預處理后，得到初步數據重建結果。

在上述方法中，只是針對一個傳感器在時域的時間相關性，同時由于選擇窗口尺寸K時的兩難顧慮，實際效果并不理想。因此，還應兼顧傳感器在空間位置的相關性，進行時空二維聯合處理。

2 基于時空相關性的交通感知數據分析

在交通物聯網中，對同一物理量的檢測通常采用多點布設傳感器的方式，例如在一段公路上多個門架設備對車速，車流量的連續檢測。這些傳感器在同一時刻對各自負責的區域進行信號采集，由于部署在公路沿線的傳感器位置存在空間相關性，數據也會呈現一定的相關性。若某個傳感器出現故障或受到強干擾，導致采集數據缺失，可通過相同時間不同點位的其他傳感數據來估計缺失值。

但這種相關性由于受到路面質量、交通流、交通信號控制等多方面的影響，交通流特征和環境參數并不是線性變化，很難用簡單的線性解析數學模型來刻畫，因此，需引入非線性的預測和分析手段。BP神經網絡是一種智能算法，通過相當數量的訓練找出模式與類別之間的內在聯系，以隱性方式學習和存儲輸入-輸出模式之間的非線性映射關系，因此，本文綜合利用感知數據在時間和空間的相關性，建立基于BP神經網絡的數據重建模型，最后得到缺失數據的估計值。

這里的時空相關性表現為兩個方面：

1)時域相關性。同一傳感器在相鄰時刻（相干時間內）采集到的數據之間存在的時間相關性，超出相干時間，數據之間的關聯性明顯下降。

2)空域相關性。相鄰傳感器（相干距離內）在同一時刻采集到的數據之間存在的空間相關性，超出相干距離規定的空間范圍，數據之間的關聯性明顯下降。

圖1為高速公路微波檢測器的區間車流量的時空檢測數據。橫坐標表示采樣時刻，也就是以該時刻為終點，過去一段時間內統計得到的車流量。縱坐標是檢測點位，對應不同的空間位置，不同的幾何外形表示不同的ABCDE傳感器。觀察矩陣圖中數據發現，A檢測點在時刻1 的數據(93)，與B 點在時刻2 的數據(94)相關度更高。也就是說，沿對角線上的數據關聯程度明顯高于水平線和垂直線上的關聯度。原因在于，不同傳感器的部署位置不同，檢測數據具有一定“定時漂移”特征，即“此時此處”的數據和“彼時彼處”的數據更相關，類似“綠波帶”的交通流“流動”特性。

圖1 時空二維車流量數據矩陣

圖2是同一路段內相鄰5個檢測點的車流量變化曲線，圖中每一條折線對應一個檢測點。這也是從另一個角度描述數據的時空關聯性。對比圖1 和圖2，圖1中對角線的斜率，圖2中兩條折線的平移間隔，都反映了該路段的平均車速。

圖2 相鄰檢測點車流量變化曲線

圖3 是檢測點車流量隨時域統計窗口變化的曲線。可以看出，若統計窗口較小，此時段內通過的車流量不穩定，隨機性更強，兩個檢測點檢測到的車流量數據相差較大，但隨著窗口的增大，數據趨于穩定，兩個檢測點的車流量數據差距越來越小，逐漸趨于相等。例如，在一天的統計窗口內，若兩個檢測點之間沒有進出閘道，那么觀察到的車流量幾乎相同，此時的時域關聯性對填補數據沒有幫助。

需要注意的是，數據的相關性不僅與車流量統計窗口大小有關，還與傳感器的布設間隔有關。圖4是在采樣時間間隔固定的條件下，不同的檢測點采集的車流量隨采樣距離變化的曲線。

圖4 基于距離的車流量變化曲線圖

從圖4可以看出，傳感器布設間隔越大，車流量的相關性越小，當兩個傳感器的距離在2km 以上時，A點和B 點的車流量并沒有明顯的正相關。這是因為交通流量自身的彌散效應，隨著檢測點距離的增加，兩處檢測數據的關聯程度會更低。

3 基于時空相關性的數據填補算法

由于數據之間不僅存在時間上的相關性，在空間上也存在一定的相關性，若使用單一的時域線性插值，對缺失多個數據或缺失較長時間的情況下填充效果不理想，且影響時空關聯的因素涵蓋傳感器間隔、車輛速度、采樣頻率等，很難用線性模型表示，為此，本文引入非線性的BP 神經網絡，其網絡結構如圖5所示。BP神經網絡包括輸入層、隱含層和輸出層[9]。同一層各個神經元無連接，層與層之間神經元全連接，右下角特寫部分是單一神經元內部的計算操作。正向傳播是從輸入層神經元到隱含層再到輸出層逐層計算[10]，若輸出層未得到期望的輸出，則使用梯度下降法沿連接線反向傳播誤差，逐層更新權重ω和偏差b，直至目標函數的誤差滿足要求，訓練完成。神經網絡的傳播都是線性矩陣運算,為了解決線性模型所不能解決的問題，需要在隱藏層中加入非線性的激活函數f。

圖5 BP神經網絡結構圖

BP網絡的核心是以相鄰若干節點（空域）和相鄰時刻（時域）的已知數據作為網絡輸入，以缺失數據的預估結果作為輸出，通過一定量的樣本學習訓練，將診斷知識隱性存儲于網絡的拓撲結構和連接權值ω和b中，形成從已知數據值到缺失數據預估值之間的非線性映射關系。

在此映射過程中，輸入層神經元個數取決于輸入數據的時空選擇區域，其中，空域對應相鄰感知節點的數量，時域對應第2節提到的插值窗口。時空選擇區域對算法的性能影響重大，選擇區域太小，時空關聯窗口小，恢復的數據準確性較低；而選擇的區域太大，輸入的神經元節點過多，訓練時間長，影響數據填補的實時性。

因此本文選取3～8 個。采用計算速度更快的ReLU 激活函數，用Adam 算法優化模型，減小損失函數，當訓練選取的樣本數batch_size 選擇32 且學習率設定為0.001 時模型的誤差最小。本場景中，輸出層輸出是一個估計值，故神經元個數為1。由于傳感器沿公路線型布局，結構簡單，為了提高算法的收斂速度，本文選取一層隱含層，隱含層神經元個數為輸出層的兩倍。

假設在某高速公路上，每隔1km有一個微波車輛檢測器，實時檢測交通流量、平均車速、車型及車道占用率等交通數據，如圖6所示，一般意義的數據xi,j中，下標i表示時間，下標j表示空間傳感器的編號。圖6中，淺灰色背景的數據為輸入數據，可采用“十字”“對角線”“環形“三種策略，對應的輸入數據點數量分別為4、6、8。深灰色背景的B2為缺失數據。

圖6 輸入數據選擇示意圖（輸入個數為4，6，8)

推廣到一般情況，為了將時空二維數據輸入到BP網絡中，需經過并串轉換后變為一維數據，暫時忽略其時空特性。示意圖如圖7所示，此處只列出連續5個傳感器(A,B,C,D,E)的數據。其中，為i時刻所有檢測點的數據的集合向量。并串轉換后的一維數據集合為X={x1,x2,x3,…,xK}，其中K=(M+1)N。根據第2節的時空特性分析，輸入檢測點的數量（圖6矩陣的行數）、插值窗口（圖6矩陣的列數）和選擇策略共同決定輸入神經元的個數。

圖7 并串轉換示意圖

在輸入圖5所示的BP網絡時，輸入數據集為XK={x1,x2,x3,…,xK}，輸出為待估計數值，對應原始數值為yk，理想情況下=yk。為了訓練模型，將多個樣本數據集分為訓練集和測試集，其中訓練集為T={XK,yk}。

BP網絡的優化流程如下：

1)初始化BP網絡。對網絡層里的所有權值和偏置進行(0,1)范圍內隨機初始化，設置最大迭代次數epoch和最小誤差值eps；

2)輸入訓練集T={XK,yk}；其中yk是實際標記的缺失值，XK是以yk為中心，從時空二維拓展獲得的一系列已知訓練數據；

3)根據圖5的BP網絡模型正向計算輸出值；

5)將誤差ek反向傳播到隱含層神經元，計算誤差對每個神經元的偏導數，據此調整連接權重ω和偏置b；

6)重復步驟2 至6 訓練樣本數據集，直到誤差ek的結果小于最小誤差值eps或者訓練達到epoch為止。

在上述訓練過程中，輸入的數據集{x1,x2,x3,…,xK}實際為時空二維數據，其中每一個數據對應第j個檢測點在第i個時刻的檢測數據xi,j。

在實際場景中，由于環境因素的作用，數據缺失點的個數和位置是隨機的。在第1節基于時域相關性的線性插值模型中，只針對同一個傳感器，但允許存在連續幾個缺失數據，需要動態調整插值窗口的大小。而第2節的基于空間相關性的BP算法，盡管輸入數據涵蓋不同時刻、不同位置的傳感數據，但出于計算復雜度和實時性的考慮，假設只有一個缺失點（輸出節點數為1)。因此，在不確定缺失數據個數的情況下進行視情處理，可在算法復雜度和填補準確度間取得平衡，具體流程如圖8所示。

圖8 算法整體流程圖

首先對訓練集中的缺失數據個數n進行判斷。當只有一個缺失數據時，直接使用BP 網絡模型進行預估。當缺失多個數據(n＞1)時，需通過LIN模型進行數據估計并得到n-1 個估計值，將訓練恢復所得結果與已知數據輸入一起輸入到BP網絡模型中進行預估，整個算法流程中，只需要一個BP 模型進行數據估計。

表1為陜西省巖灣閘道至寶雞南閘道路段某日的車流量檢測部分數據。其中縱坐標為不同的檢測點，橫坐標為不同的檢測時刻，圖中深灰色和淺灰色數據均為缺失數據。第一階段選擇合適的插值窗口得到邊緣缺失點的數據（表中淺灰色部分的2個數據）；第二階段將已知數據和第一階段得到的數據（標深灰的數據）輸入到BP模型中，對最后剩余的深灰色點位進行數據預估。

表1 車流量統計表

4 實驗與分析

本文使用多個檢測點的交通流量真實數據集進行試驗。其中數據集的80%作為訓練樣本，20%作為測試樣本。由于該數據集本身的統計窗口較大，實驗時選取的感知數據的時間統計窗口取值在5min 到25min之間，在空間維度上，選擇以待重建數據的節點為中心，周圍3～8 之間的鄰居節點。將本文提出的LIN_BP 算法分別與LIN，BP 及KNN 算法[4]進行對比，采用均方誤差(Mean Square Error，MSE)衡量算法的填充精度：

其中，yn是真實非缺失數據值為由模型計算得到的估計值。在不同統計窗口下，各算法的均方誤差對比結果如圖9所示，隨著統計窗口的增大，LIN模型和KNN 模型的誤差顯著增大；而LIN_BP 模型的誤差變化并不明顯。由于KNN 算法建模的依據僅僅是感知數據的空間相關性，只考慮同一時刻內兩個相鄰傳感器的采樣數據，沒有考慮車流量的“時移特性”，以及不同統計窗口的影響。而LIN_BP模型同時考慮時域插值窗口和空間相鄰節點兩種特征的影響，根據缺失數據個數動態調整插值窗口，因此，時域統計窗口對LIN_BP 模型的影響很小，最終預估結果的準確度更高。

圖9 時域統計窗口對算法估計誤差的影響

從圖10 中可以看出，LIN 算法的估計誤差最大，KNN 算法的誤差隨著節點數的增加逐漸變大，BP 算法和本文提出的LIN_BP 算法的誤差較小且較為穩定。由于LIN 算法單純利用時間相關性進行數據重建，面對突發性較強的交通物聯網進行數據估計的準確度較低；而KNN 算法僅考慮空間相關性，當相鄰節點較少時，估計出的數據值比較準確。但隨著鄰近節點的增多，數據的空間相關性變得更為復雜，基于該模型進行估計的誤差變大；BP算法的誤差較小，付出的代價是算法的復雜度高，時延較長。而LIN_BP 模型同時兼顧感知數據的時空相關性，數據重建的效果誤差更小，和單純的BP模型相比，算法復雜度更低。

圖10 節點數對算法估計誤差的影響

綜上所述，本文針對實際場景中的交通數據具有時空二維相關性的特點，提出了一種基于時空相關性的LIN_BP 模型，既考慮同一時刻相鄰位置的傳感器的空間相關性，也考慮了同一個傳感器采集數據的時間相關性，從兩方面出發對缺失數據進行預估，在擴大了算法適用范圍的同時，提高了數據填補的準確性。

5 結論

本文通過分析交通物聯網中傳感器數據的特征，提出基于時空相關性的LIN_BP 模型來填充缺失數據。該算法模型同時考慮時間和空間兩維度的影響，根據缺失數據個數的不同進行分情況處理，當缺失個數較多時先利用LIN模型進行估計，將結果結合原始數據輸入BP模型從而得到最終的預估結果。本文以MSE作為算法性能評價的標準，在真實數據集對本文中提出的模型和幾種常用缺失值填補模型進行實驗，得出以下結論：相較于基于單一屬性的填充算法，本文提出的線性插值與BP神經網絡結合的算法能克服由于數據不平穩，統計窗口大而產生的誤差，從而使填補精度更高。實驗結果表明，本算法的誤差小于經典KNN算法。