基于時(shí)空相關(guān)性的交通物聯(lián)網(wǎng)缺失數(shù)據(jù)填補(bǔ)算法

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

(1.中鐵城市發(fā)展投資集團(tuán)有限公司，四川成都 610000；2.長(zhǎng)安大學(xué)信息工程學(xué)院，陜西西安 710064)

0 引言

隨著以交通物聯(lián)網(wǎng)為基礎(chǔ)的智慧高速的發(fā)展，通過(guò)全面感知道路基礎(chǔ)設(shè)施、行駛車(chē)輛等交通參與方的數(shù)據(jù)，可有效開(kāi)展面向安全和效率的主動(dòng)智慧管控，為基于車(chē)路協(xié)同的無(wú)人駕駛提供技術(shù)支撐，提升交通運(yùn)輸?shù)陌踩?、高效性和舒適性。

然而在智能感知的過(guò)程中，一方面，由于智能網(wǎng)聯(lián)汽車(chē)的數(shù)量快速增長(zhǎng)，帶來(lái)的海量數(shù)據(jù)傳輸和計(jì)算問(wèn)題更加突出；另一方面，移動(dòng)邊緣計(jì)算的介入，車(chē)載移動(dòng)端和路側(cè)設(shè)備之間數(shù)據(jù)的無(wú)線(xiàn)傳輸占比增加，而由于車(chē)輛的移動(dòng)性和傳輸環(huán)境的時(shí)變性，導(dǎo)致多徑傳輸和多普勒效應(yīng)也愈加突出。上述問(wèn)題會(huì)使數(shù)據(jù)采集時(shí)存在缺失和誤碼的概率提高，然而由于部分業(yè)務(wù)具有嚴(yán)苛的實(shí)時(shí)性要求，不能采用出錯(cuò)重傳機(jī)制，因此，在接收端對(duì)關(guān)鍵數(shù)據(jù)進(jìn)行自主的前向糾錯(cuò)，重建缺失數(shù)據(jù)將是必然選擇。

數(shù)據(jù)缺失主要來(lái)自?xún)煞矫妫阂环矫妫瑐鞲衅鞯墓收蠒?huì)導(dǎo)致不定期的數(shù)據(jù)空白，這種缺失往往持續(xù)時(shí)間較長(zhǎng)，很難用算法進(jìn)行填補(bǔ)重建，不屬于本文研究的范疇。另一方面，由于數(shù)據(jù)傳輸過(guò)程中的信道噪聲，而導(dǎo)致的零星誤碼或缺失，可通過(guò)本文的方法進(jìn)行數(shù)據(jù)填補(bǔ)重建，這是本文的研究?jī)?nèi)容。

當(dāng)前，數(shù)據(jù)重建技術(shù)分為時(shí)域、頻域和空域三大類(lèi)。對(duì)于時(shí)域重建技術(shù)，主要依據(jù)同一傳感數(shù)據(jù)在時(shí)間序列上的相關(guān)性進(jìn)行數(shù)據(jù)填補(bǔ)，文獻(xiàn)[1]從已有數(shù)據(jù)中提取不同類(lèi)型的數(shù)據(jù)基信號(hào)，并利用基于時(shí)間序列的線(xiàn)性關(guān)聯(lián)映射重建缺失數(shù)據(jù)。文獻(xiàn)[2]基于傳感數(shù)據(jù)在一個(gè)嵌套滑動(dòng)窗口內(nèi)的相關(guān)性，提出一種數(shù)據(jù)流缺失恢復(fù)方法。文獻(xiàn)[3]提出一種針對(duì)缺失數(shù)據(jù)的譜分析方法，通過(guò)更新估算因子來(lái)修正時(shí)域重建算法，提高數(shù)據(jù)重建精度。

文獻(xiàn)[1-3]均利用了時(shí)域數(shù)據(jù)的隨機(jī)平穩(wěn)特性，適合數(shù)據(jù)變化不大的靜態(tài)物聯(lián)網(wǎng)領(lǐng)域。例如河道水位檢測(cè)、交通基礎(chǔ)設(shè)施的狀態(tài)檢測(cè)等。但對(duì)于車(chē)速、斷面流量等和交通流密切相關(guān)的實(shí)時(shí)交通元素，數(shù)據(jù)雖然具有廣義隨機(jī)平穩(wěn)特性，但時(shí)域變化劇烈，時(shí)域相干窗口較小，在此窗口內(nèi)采集到的原始有效數(shù)據(jù)較少，提取的特征值往往離散度大，若加大插值窗口又會(huì)導(dǎo)致緩存數(shù)據(jù)過(guò)多，處理時(shí)延長(zhǎng)，且數(shù)據(jù)的時(shí)域關(guān)聯(lián)性呈時(shí)間選擇性衰落，適用性難以保障。

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

隨著以機(jī)器學(xué)習(xí)為代表的人工智能算法的興起，通過(guò)強(qiáng)大的計(jì)算機(jī)算力，在交通大數(shù)據(jù)中提取非線(xiàn)性的時(shí)空屬性特征，搭建多粒度的數(shù)據(jù)格式以及數(shù)學(xué)描述方法，重建缺失數(shù)據(jù)，已成為研究熱點(diǎn)。文獻(xiàn)[7]利用相鄰傳感節(jié)點(diǎn)的小波系數(shù)相關(guān)性，通過(guò)逆小波變換和時(shí)頻回歸模型來(lái)重建缺失數(shù)據(jù)，該方法精度高，但實(shí)現(xiàn)復(fù)雜度偏高。文獻(xiàn)[8]利用逆向傳播(Back Propagation，BP)神經(jīng)網(wǎng)絡(luò)對(duì)單一的交通流量進(jìn)行預(yù)測(cè)，但并不適用于具有非結(jié)構(gòu)化特征的交通物聯(lián)網(wǎng)數(shù)據(jù)。

在公路交通領(lǐng)域，機(jī)電設(shè)備的類(lèi)型適中，空間部署呈線(xiàn)性分布，具有明顯的空間相關(guān)特性，且感知對(duì)象聚焦于交通流、交通事件、氣象等固定類(lèi)型，但數(shù)據(jù)具有一定“定時(shí)漂移”特征，即“此時(shí)此處”的數(shù)據(jù)和“彼時(shí)彼處”的數(shù)據(jù)更具相關(guān)性。因此，本文通過(guò)分析高速公路交通感知數(shù)據(jù)的特性，提出一種基于時(shí)空相關(guān)性的線(xiàn)性插值神經(jīng)網(wǎng)絡(luò)(LIN_BP)數(shù)據(jù)恢復(fù)算法，將時(shí)域和空域特征相結(jié)合來(lái)恢復(fù)缺失數(shù)據(jù)。

1 基于時(shí)域平穩(wěn)性的線(xiàn)性插值預(yù)處理

目前，在公路交通領(lǐng)域中，在靠近傳感器的感知接入層，仍然有較多非智能感知設(shè)備，例如輸出電流信號(hào)的液位計(jì)，電壓信號(hào)的壓力傳感器，這些設(shè)備有些部署無(wú)法進(jìn)行有線(xiàn)傳輸?shù)囊苿?dòng)終端，有些是后裝的感知設(shè)備，不具備有線(xiàn)傳輸條件，無(wú)奈采用無(wú)線(xiàn)傳輸方式。一旦數(shù)據(jù)接入路側(cè)設(shè)備后，就會(huì)采用更加可靠的光纖有線(xiàn)傳輸。因此，本文重點(diǎn)針對(duì)因無(wú)線(xiàn)傳輸導(dǎo)致的數(shù)據(jù)缺失。

由于無(wú)線(xiàn)傳輸環(huán)境的開(kāi)放性和時(shí)變性，數(shù)據(jù)傳輸過(guò)程中經(jīng)常會(huì)受到各種干擾和噪聲的影響，例如車(chē)輛馬達(dá)產(chǎn)生的寬頻干擾脈沖和毛刺噪聲，這些干擾會(huì)導(dǎo)致信號(hào)傳輸出現(xiàn)連續(xù)的誤碼，而常用的卷積碼加交織的信道編碼技術(shù)，僅對(duì)零星的非連續(xù)誤碼有效，因此，有必要對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，將連續(xù)的缺失數(shù)據(jù)或異常數(shù)據(jù)位變?yōu)榱阈堑膯蝹€(gè)孤立缺失數(shù)據(jù)位。

對(duì)于多數(shù)輸出模擬信號(hào)的傳感器，在連續(xù)時(shí)間內(nèi)采集到的非電量數(shù)值非常相近甚至相同。因此，可利用感知數(shù)據(jù)的時(shí)間相關(guān)性，構(gòu)建線(xiàn)性函數(shù)來(lái)粗略估算缺失數(shù)據(jù)。該方法優(yōu)勢(shì)在于復(fù)雜度低，適合對(duì)時(shí)延敏感的實(shí)時(shí)性業(yè)務(wù)。

線(xiàn)性插值的基本原理是：假設(shè)ti時(shí)刻的數(shù)據(jù)xi缺失，在其附近的tp和tq時(shí)刻的傳感器數(shù)值為xp和xq，經(jīng)過(guò)線(xiàn)性插值后的估計(jì)值為

插值窗口尺寸M的選擇至關(guān)重要，若取值太小，缺失數(shù)據(jù)點(diǎn)占比過(guò)高，容易受到周?chē)肼暫兔痰挠绊?，影響插值的精度。若取值太大，?jì)算復(fù)雜度升高，導(dǎo)致產(chǎn)生較大的處理時(shí)延。一般的經(jīng)驗(yàn)原則是，在插值窗口內(nèi)，缺失數(shù)據(jù)點(diǎn)占比不超10%，且與待重建信號(hào)的中心頻率成反比，頻率越高，說(shuō)明數(shù)據(jù)變化越快，時(shí)域相干窗口應(yīng)越小。通過(guò)選擇合適的窗口大小，對(duì)多個(gè)缺失數(shù)據(jù)進(jìn)行預(yù)處理后，得到初步數(shù)據(jù)重建結(jié)果。

在上述方法中，只是針對(duì)一個(gè)傳感器在時(shí)域的時(shí)間相關(guān)性，同時(shí)由于選擇窗口尺寸K時(shí)的兩難顧慮，實(shí)際效果并不理想。因此，還應(yīng)兼顧傳感器在空間位置的相關(guān)性，進(jìn)行時(shí)空二維聯(lián)合處理。

2 基于時(shí)空相關(guān)性的交通感知數(shù)據(jù)分析

在交通物聯(lián)網(wǎng)中，對(duì)同一物理量的檢測(cè)通常采用多點(diǎn)布設(shè)傳感器的方式，例如在一段公路上多個(gè)門(mén)架設(shè)備對(duì)車(chē)速，車(chē)流量的連續(xù)檢測(cè)。這些傳感器在同一時(shí)刻對(duì)各自負(fù)責(zé)的區(qū)域進(jìn)行信號(hào)采集，由于部署在公路沿線(xiàn)的傳感器位置存在空間相關(guān)性，數(shù)據(jù)也會(huì)呈現(xiàn)一定的相關(guān)性。若某個(gè)傳感器出現(xiàn)故障或受到強(qiáng)干擾，導(dǎo)致采集數(shù)據(jù)缺失，可通過(guò)相同時(shí)間不同點(diǎn)位的其他傳感數(shù)據(jù)來(lái)估計(jì)缺失值。

但這種相關(guān)性由于受到路面質(zhì)量、交通流、交通信號(hào)控制等多方面的影響，交通流特征和環(huán)境參數(shù)并不是線(xiàn)性變化，很難用簡(jiǎn)單的線(xiàn)性解析數(shù)學(xué)模型來(lái)刻畫(huà)，因此，需引入非線(xiàn)性的預(yù)測(cè)和分析手段。BP神經(jīng)網(wǎng)絡(luò)是一種智能算法，通過(guò)相當(dāng)數(shù)量的訓(xùn)練找出模式與類(lèi)別之間的內(nèi)在聯(lián)系，以隱性方式學(xué)習(xí)和存儲(chǔ)輸入-輸出模式之間的非線(xiàn)性映射關(guān)系，因此，本文綜合利用感知數(shù)據(jù)在時(shí)間和空間的相關(guān)性，建立基于BP神經(jīng)網(wǎng)絡(luò)的數(shù)據(jù)重建模型，最后得到缺失數(shù)據(jù)的估計(jì)值。

這里的時(shí)空相關(guān)性表現(xiàn)為兩個(gè)方面：

1)時(shí)域相關(guān)性。同一傳感器在相鄰時(shí)刻（相干時(shí)間內(nèi)）采集到的數(shù)據(jù)之間存在的時(shí)間相關(guān)性，超出相干時(shí)間，數(shù)據(jù)之間的關(guān)聯(lián)性明顯下降。

2)空域相關(guān)性。相鄰傳感器（相干距離內(nèi)）在同一時(shí)刻采集到的數(shù)據(jù)之間存在的空間相關(guān)性，超出相干距離規(guī)定的空間范圍，數(shù)據(jù)之間的關(guān)聯(lián)性明顯下降。

圖1為高速公路微波檢測(cè)器的區(qū)間車(chē)流量的時(shí)空檢測(cè)數(shù)據(jù)。橫坐標(biāo)表示采樣時(shí)刻，也就是以該時(shí)刻為終點(diǎn)，過(guò)去一段時(shí)間內(nèi)統(tǒng)計(jì)得到的車(chē)流量。縱坐標(biāo)是檢測(cè)點(diǎn)位，對(duì)應(yīng)不同的空間位置，不同的幾何外形表示不同的ABCDE傳感器。觀察矩陣圖中數(shù)據(jù)發(fā)現(xiàn)，A檢測(cè)點(diǎn)在時(shí)刻1 的數(shù)據(jù)(93)，與B 點(diǎn)在時(shí)刻2 的數(shù)據(jù)(94)相關(guān)度更高。也就是說(shuō)，沿對(duì)角線(xiàn)上的數(shù)據(jù)關(guān)聯(lián)程度明顯高于水平線(xiàn)和垂直線(xiàn)上的關(guān)聯(lián)度。原因在于，不同傳感器的部署位置不同，檢測(cè)數(shù)據(jù)具有一定“定時(shí)漂移”特征，即“此時(shí)此處”的數(shù)據(jù)和“彼時(shí)彼處”的數(shù)據(jù)更相關(guān)，類(lèi)似“綠波帶”的交通流“流動(dòng)”特性。

圖1 時(shí)空二維車(chē)流量數(shù)據(jù)矩陣

圖2是同一路段內(nèi)相鄰5個(gè)檢測(cè)點(diǎn)的車(chē)流量變化曲線(xiàn)，圖中每一條折線(xiàn)對(duì)應(yīng)一個(gè)檢測(cè)點(diǎn)。這也是從另一個(gè)角度描述數(shù)據(jù)的時(shí)空關(guān)聯(lián)性。對(duì)比圖1 和圖2，圖1中對(duì)角線(xiàn)的斜率，圖2中兩條折線(xiàn)的平移間隔，都反映了該路段的平均車(chē)速。

圖2 相鄰檢測(cè)點(diǎn)車(chē)流量變化曲線(xiàn)

圖3 是檢測(cè)點(diǎn)車(chē)流量隨時(shí)域統(tǒng)計(jì)窗口變化的曲線(xiàn)?？梢钥闯?，若統(tǒng)計(jì)窗口較小，此時(shí)段內(nèi)通過(guò)的車(chē)流量不穩(wěn)定，隨機(jī)性更強(qiáng)，兩個(gè)檢測(cè)點(diǎn)檢測(cè)到的車(chē)流量數(shù)據(jù)相差較大，但隨著窗口的增大，數(shù)據(jù)趨于穩(wěn)定，兩個(gè)檢測(cè)點(diǎn)的車(chē)流量數(shù)據(jù)差距越來(lái)越小，逐漸趨于相等。例如，在一天的統(tǒng)計(jì)窗口內(nèi)，若兩個(gè)檢測(cè)點(diǎn)之間沒(méi)有進(jìn)出閘道，那么觀察到的車(chē)流量幾乎相同，此時(shí)的時(shí)域關(guān)聯(lián)性對(duì)填補(bǔ)數(shù)據(jù)沒(méi)有幫助。

需要注意的是，數(shù)據(jù)的相關(guān)性不僅與車(chē)流量統(tǒng)計(jì)窗口大小有關(guān)，還與傳感器的布設(shè)間隔有關(guān)。圖4是在采樣時(shí)間間隔固定的條件下，不同的檢測(cè)點(diǎn)采集的車(chē)流量隨采樣距離變化的曲線(xiàn)。

圖4 基于距離的車(chē)流量變化曲線(xiàn)圖

從圖4可以看出，傳感器布設(shè)間隔越大，車(chē)流量的相關(guān)性越小，當(dāng)兩個(gè)傳感器的距離在2km 以上時(shí)，A點(diǎn)和B 點(diǎn)的車(chē)流量并沒(méi)有明顯的正相關(guān)。這是因?yàn)榻煌髁孔陨淼膹浬⑿?yīng)，隨著檢測(cè)點(diǎn)距離的增加，兩處檢測(cè)數(shù)據(jù)的關(guān)聯(lián)程度會(huì)更低。

3 基于時(shí)空相關(guān)性的數(shù)據(jù)填補(bǔ)算法

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

圖5 BP神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)圖

BP網(wǎng)絡(luò)的核心是以相鄰若干節(jié)點(diǎn)（空域）和相鄰時(shí)刻（時(shí)域）的已知數(shù)據(jù)作為網(wǎng)絡(luò)輸入，以缺失數(shù)據(jù)的預(yù)估結(jié)果作為輸出，通過(guò)一定量的樣本學(xué)習(xí)訓(xùn)練，將診斷知識(shí)隱性存儲(chǔ)于網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和連接權(quán)值ω和b中，形成從已知數(shù)據(jù)值到缺失數(shù)據(jù)預(yù)估值之間的非線(xiàn)性映射關(guān)系。

在此映射過(guò)程中，輸入層神經(jīng)元個(gè)數(shù)取決于輸入數(shù)據(jù)的時(shí)空選擇區(qū)域，其中，空域?qū)?yīng)相鄰感知節(jié)點(diǎn)的數(shù)量，時(shí)域?qū)?yīng)第2節(jié)提到的插值窗口。時(shí)空選擇區(qū)域?qū)λ惴ǖ男阅苡绊懼卮?，選擇區(qū)域太小，時(shí)空關(guān)聯(lián)窗口小，恢復(fù)的數(shù)據(jù)準(zhǔn)確性較低；而選擇的區(qū)域太大，輸入的神經(jīng)元節(jié)點(diǎn)過(guò)多，訓(xùn)練時(shí)間長(zhǎng)，影響數(shù)據(jù)填補(bǔ)的實(shí)時(shí)性。

因此本文選取3～8 個(gè)。采用計(jì)算速度更快的ReLU 激活函數(shù)，用Adam 算法優(yōu)化模型，減小損失函數(shù)，當(dāng)訓(xùn)練選取的樣本數(shù)batch_size 選擇32 且學(xué)習(xí)率設(shè)定為0.001 時(shí)模型的誤差最小。本場(chǎng)景中，輸出層輸出是一個(gè)估計(jì)值，故神經(jīng)元個(gè)數(shù)為1。由于傳感器沿公路線(xiàn)型布局，結(jié)構(gòu)簡(jiǎn)單，為了提高算法的收斂速度，本文選取一層隱含層，隱含層神經(jīng)元個(gè)數(shù)為輸出層的兩倍。

假設(shè)在某高速公路上，每隔1km有一個(gè)微波車(chē)輛檢測(cè)器，實(shí)時(shí)檢測(cè)交通流量、平均車(chē)速、車(chē)型及車(chē)道占用率等交通數(shù)據(jù)，如圖6所示，一般意義的數(shù)據(jù)xi,j中，下標(biāo)i表示時(shí)間，下標(biāo)j表示空間傳感器的編號(hào)。圖6中，淺灰色背景的數(shù)據(jù)為輸入數(shù)據(jù)，可采用“十字”“對(duì)角線(xiàn)”“環(huán)形“三種策略，對(duì)應(yīng)的輸入數(shù)據(jù)點(diǎn)數(shù)量分別為4、6、8。深灰色背景的B2為缺失數(shù)據(jù)。

圖6 輸入數(shù)據(jù)選擇示意圖（輸入個(gè)數(shù)為4，6，8)

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

圖7 并串轉(zhuǎn)換示意圖

在輸入圖5所示的BP網(wǎng)絡(luò)時(shí)，輸入數(shù)據(jù)集為XK={x1,x2,x3,…,xK}，輸出為待估計(jì)數(shù)值，對(duì)應(yīng)原始數(shù)值為yk，理想情況下=yk。為了訓(xùn)練模型，將多個(gè)樣本數(shù)據(jù)集分為訓(xùn)練集和測(cè)試集，其中訓(xùn)練集為T(mén)={XK,yk}。

BP網(wǎng)絡(luò)的優(yōu)化流程如下：

1)初始化BP網(wǎng)絡(luò)。對(duì)網(wǎng)絡(luò)層里的所有權(quán)值和偏置進(jìn)行(0,1)范圍內(nèi)隨機(jī)初始化，設(shè)置最大迭代次數(shù)epoch和最小誤差值eps；

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

3)根據(jù)圖5的BP網(wǎng)絡(luò)模型正向計(jì)算輸出值；

5)將誤差ek反向傳播到隱含層神經(jīng)元，計(jì)算誤差對(duì)每個(gè)神經(jīng)元的偏導(dǎo)數(shù)，據(jù)此調(diào)整連接權(quán)重ω和偏置b；

6)重復(fù)步驟2 至6 訓(xùn)練樣本數(shù)據(jù)集，直到誤差ek的結(jié)果小于最小誤差值eps或者訓(xùn)練達(dá)到epoch為止。

在上述訓(xùn)練過(guò)程中，輸入的數(shù)據(jù)集{x1,x2,x3,…,xK}實(shí)際為時(shí)空二維數(shù)據(jù)，其中每一個(gè)數(shù)據(jù)對(duì)應(yīng)第j個(gè)檢測(cè)點(diǎn)在第i個(gè)時(shí)刻的檢測(cè)數(shù)據(jù)xi,j。

在實(shí)際場(chǎng)景中，由于環(huán)境因素的作用，數(shù)據(jù)缺失點(diǎn)的個(gè)數(shù)和位置是隨機(jī)的。在第1節(jié)基于時(shí)域相關(guān)性的線(xiàn)性插值模型中，只針對(duì)同一個(gè)傳感器，但允許存在連續(xù)幾個(gè)缺失數(shù)據(jù)，需要?jiǎng)討B(tài)調(diào)整插值窗口的大小。而第2節(jié)的基于空間相關(guān)性的BP算法，盡管輸入數(shù)據(jù)涵蓋不同時(shí)刻、不同位置的傳感數(shù)據(jù)，但出于計(jì)算復(fù)雜度和實(shí)時(shí)性的考慮，假設(shè)只有一個(gè)缺失點(diǎn)（輸出節(jié)點(diǎn)數(shù)為1)。因此，在不確定缺失數(shù)據(jù)個(gè)數(shù)的情況下進(jìn)行視情處理，可在算法復(fù)雜度和填補(bǔ)準(zhǔn)確度間取得平衡，具體流程如圖8所示。

圖8 算法整體流程圖

首先對(duì)訓(xùn)練集中的缺失數(shù)據(jù)個(gè)數(shù)n進(jìn)行判斷。當(dāng)只有一個(gè)缺失數(shù)據(jù)時(shí)，直接使用BP 網(wǎng)絡(luò)模型進(jìn)行預(yù)估。當(dāng)缺失多個(gè)數(shù)據(jù)(n＞1)時(shí)，需通過(guò)LIN模型進(jìn)行數(shù)據(jù)估計(jì)并得到n-1 個(gè)估計(jì)值，將訓(xùn)練恢復(fù)所得結(jié)果與已知數(shù)據(jù)輸入一起輸入到BP網(wǎng)絡(luò)模型中進(jìn)行預(yù)估，整個(gè)算法流程中，只需要一個(gè)BP 模型進(jìn)行數(shù)據(jù)估計(jì)。

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

表1 車(chē)流量統(tǒng)計(jì)表

4 實(shí)驗(yàn)與分析

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

其中，yn是真實(shí)非缺失數(shù)據(jù)值為由模型計(jì)算得到的估計(jì)值。在不同統(tǒng)計(jì)窗口下，各算法的均方誤差對(duì)比結(jié)果如圖9所示，隨著統(tǒng)計(jì)窗口的增大，LIN模型和KNN 模型的誤差顯著增大；而LIN_BP 模型的誤差變化并不明顯。由于KNN 算法建模的依據(jù)僅僅是感知數(shù)據(jù)的空間相關(guān)性，只考慮同一時(shí)刻內(nèi)兩個(gè)相鄰傳感器的采樣數(shù)據(jù)，沒(méi)有考慮車(chē)流量的“時(shí)移特性”，以及不同統(tǒng)計(jì)窗口的影響。而LIN_BP模型同時(shí)考慮時(shí)域插值窗口和空間相鄰節(jié)點(diǎn)兩種特征的影響，根據(jù)缺失數(shù)據(jù)個(gè)數(shù)動(dòng)態(tài)調(diào)整插值窗口，因此，時(shí)域統(tǒng)計(jì)窗口對(duì)LIN_BP 模型的影響很小，最終預(yù)估結(jié)果的準(zhǔn)確度更高。

圖9 時(shí)域統(tǒng)計(jì)窗口對(duì)算法估計(jì)誤差的影響

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

圖10 節(jié)點(diǎn)數(shù)對(duì)算法估計(jì)誤差的影響

綜上所述，本文針對(duì)實(shí)際場(chǎng)景中的交通數(shù)據(jù)具有時(shí)空二維相關(guān)性的特點(diǎn)，提出了一種基于時(shí)空相關(guān)性的LIN_BP 模型，既考慮同一時(shí)刻相鄰位置的傳感器的空間相關(guān)性，也考慮了同一個(gè)傳感器采集數(shù)據(jù)的時(shí)間相關(guān)性，從兩方面出發(fā)對(duì)缺失數(shù)據(jù)進(jìn)行預(yù)估，在擴(kuò)大了算法適用范圍的同時(shí)，提高了數(shù)據(jù)填補(bǔ)的準(zhǔn)確性。

5 結(jié)論

本文通過(guò)分析交通物聯(lián)網(wǎng)中傳感器數(shù)據(jù)的特征，提出基于時(shí)空相關(guān)性的LIN_BP 模型來(lái)填充缺失數(shù)據(jù)。該算法模型同時(shí)考慮時(shí)間和空間兩維度的影響，根據(jù)缺失數(shù)據(jù)個(gè)數(shù)的不同進(jìn)行分情況處理，當(dāng)缺失個(gè)數(shù)較多時(shí)先利用LIN模型進(jìn)行估計(jì)，將結(jié)果結(jié)合原始數(shù)據(jù)輸入BP模型從而得到最終的預(yù)估結(jié)果。本文以MSE作為算法性能評(píng)價(jià)的標(biāo)準(zhǔn)，在真實(shí)數(shù)據(jù)集對(duì)本文中提出的模型和幾種常用缺失值填補(bǔ)模型進(jìn)行實(shí)驗(yàn)，得出以下結(jié)論：相較于基于單一屬性的填充算法，本文提出的線(xiàn)性插值與BP神經(jīng)網(wǎng)絡(luò)結(jié)合的算法能克服由于數(shù)據(jù)不平穩(wěn)，統(tǒng)計(jì)窗口大而產(chǎn)生的誤差，從而使填補(bǔ)精度更高。實(shí)驗(yàn)結(jié)果表明，本算法的誤差小于經(jīng)典KNN算法。