任毅龍 ，王建斌 ，付 翔

（1.北京航空航天大學(xué)交通科學(xué)與工程學(xué)院,北京 100191；2.綜合交通大數(shù)據(jù)應(yīng)用技術(shù)國家工程實驗室,北京 100191；3.北京航空航天大學(xué)杭州創(chuàng)新研究院(余杭),浙江 杭州 310023）

1 概 述

豐富的監(jiān)控設(shè)備提供了大量時空尺度的城市路網(wǎng)旅行時間數(shù)據(jù)，然而監(jiān)控設(shè)備故障、信號干擾、惡劣天氣、通信終端宕機等情況常常干擾數(shù)據(jù)采集，造成數(shù)據(jù)缺失問題[1]。旅行時間數(shù)據(jù)的缺失會直接影響路網(wǎng)運行狀態(tài)評估的準確性，因此對缺失旅行時間數(shù)據(jù)進行準確填補十分必要。

目前聚焦缺失交通流數(shù)據(jù)填補的工作和研究主要分為以下幾個部分：傳統(tǒng)模型，統(tǒng)計模型和機器學(xué)習(xí)類模型。傳統(tǒng)模型，主要通過基于歷史或相鄰數(shù)據(jù)的插值法和回歸插值法進行數(shù)據(jù)的填補[2-5]。與傳統(tǒng)方法相比，統(tǒng)計模型由于其較強的可解釋性而被廣泛應(yīng)用于數(shù)據(jù)插補，例如基于貝葉斯主成分分析（BPCA）和概率主成分分析（PPCA）的交通流數(shù)據(jù)填補方法[6-7]。隨著機器學(xué)習(xí)理論的發(fā)展，神經(jīng)網(wǎng)絡(luò)成為交通流填補和建模中常用的方法[8-10]。與神經(jīng)網(wǎng)絡(luò)相比，SVM表現(xiàn)出更好地擬合性能和泛化能力。而廣泛用于數(shù)據(jù)分類和填補的高斯過程模型[11-12]相較于神經(jīng)網(wǎng)絡(luò)和SVM在模型結(jié)構(gòu)上更為簡單，且能效率和精確度更高。

上述方法大多采用時間序列模型將旅行時間以低維度形式輸入，然而交通流數(shù)據(jù)具有天然的高維特征，僅以低維形式存貯不僅浪費了各維度數(shù)據(jù)間的潛在關(guān)聯(lián)，甚至還會破壞交通流數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)[13]。

張量作為一種高維空間的數(shù)據(jù)存儲模型，通過將旅行時間以張量的形式存儲可以保留交通數(shù)據(jù)的原始空間結(jié)構(gòu)與內(nèi)部潛在信息，通過將張量分解再重構(gòu)的張量分解算法可以基于已觀測旅行時間實現(xiàn)對缺失旅行時間的推測，通過挖掘數(shù)據(jù)多維度之間的多重共線性，增強隱形知識發(fā)現(xiàn)過程，在高數(shù)據(jù)缺失率下相較于傳統(tǒng)數(shù)據(jù)填補方法準確性更高[14-17]。Tan等[18]首次引入張量對交通數(shù)據(jù)進行四維建模，提出了一種基于Tucker分解的估算方法（TDI）來估算缺失的流量值。Zhao等[19]提出了一種樸素貝葉斯CP分解方法，可以自然地處理不完整且含噪聲的張量數(shù)據(jù)。Wang等[20]利用三階張量對不同路段不同時段的駕駛員行駛時間進行建模，利用上下文感知張量分解方法估計張量的缺失值。

盡管基于張量分解的交通數(shù)據(jù)補全方法研究眾多，但大多沒有考慮實際交通場景中復(fù)雜的數(shù)據(jù)缺失模式，沒能充分挖掘不同數(shù)據(jù)缺失模式的數(shù)據(jù)結(jié)構(gòu)特征，導(dǎo)致模型在不同缺失模式下表達效果不佳，甚至造成高數(shù)據(jù)缺失率時精度下降，為此，本文將張量數(shù)據(jù)結(jié)構(gòu)與交通場景相關(guān)聯(lián)，挖掘高頻數(shù)據(jù)缺失場景，針對不同缺失場景構(gòu)建張量分解模型，實現(xiàn)缺失數(shù)據(jù)的填充，具體的技術(shù)路線如圖1所示。

針對上述問題，本文的主要貢獻如下：

（1）進行張量缺失模式分析與交通場景映射論證，挖掘出兩種高頻數(shù)據(jù)缺失場景：隨機缺失和纖維化缺失。

（2）針對隨機缺失場景，構(gòu)建考慮維度偏置的歷史旅行時間張量，并提出一種考慮時間關(guān)聯(lián)性的旅行時間填補方法，解決高數(shù)據(jù)缺失率下張量結(jié)構(gòu)被破壞而導(dǎo)致精度低的問題。

（3）針對“特定日期特定路段長時間數(shù)據(jù)缺失”高頻纖維化缺失場景，將時空相似路段數(shù)據(jù)融入張量分解模型，規(guī)范張量分解過程中因子矩陣迭代的方向與大小，解決傳統(tǒng)張量分解忽略局部一致性導(dǎo)致的不適用纖維化缺失場景這一問題。

（4）基于實際交通流數(shù)據(jù)對本文所提出的旅行時間填補方法進行驗證分析。

2 張量構(gòu)建與數(shù)據(jù)缺失場景挖掘

2.1 張量理論基礎(chǔ)

張量是一種高維的數(shù)據(jù)存儲模式，通常被認為是低維數(shù)據(jù)的高維擴展。張量分解領(lǐng)域廣泛應(yīng)用的兩種算法為CP分解以及Tucker分解，Tucker因其更靈活的分解結(jié)構(gòu)可以實現(xiàn)更小的模型誤差，因此在本文中選擇Tucker分解作為基礎(chǔ)分解框架。

2.2 數(shù)據(jù)預(yù)處理及旅行時間張量構(gòu)建

交通管理部門在城市關(guān)鍵路段部署卡口監(jiān)控系統(tǒng)，獲得海量的交通數(shù)據(jù)。在使用該數(shù)據(jù)進行建模時，由于采樣頻率、設(shè)備故障等原因往往導(dǎo)致數(shù)據(jù)質(zhì)量問題，需要進行數(shù)據(jù)預(yù)處理：

2.2.1 剔除異常值

計算機視覺技術(shù)的誤差會導(dǎo)致車牌號識別錯誤或無法識別，車輛在變道會導(dǎo)致相同時間節(jié)點記錄同一車輛多條軌跡記錄，以上兩種情況產(chǎn)生的異常數(shù)據(jù)需要剔除。

2.2.2 濾波降噪

由于突發(fā)事件、司機臨時停車等問題導(dǎo)致行程實際旅行時間偏大，本文采用滑動平均濾波法對數(shù)據(jù)中的離群點進行剔除，改善數(shù)據(jù)的連續(xù)性與平滑性，有利于后續(xù)的張量分解計算。

本文采用三維張量形式進行旅行時間張量建模，張量的三個維度分別為：路段、日期、時間窗。旅行時間張量定義為Xr∈RN×M×L，其中N為路網(wǎng)中的路段總數(shù)，M為日期天數(shù)，L為在一天時間內(nèi)選取的時間窗口的數(shù)量，由時間窗口長度決定。張量中的元素xijk代表在車輛在j天k時段內(nèi)通過道路i的平均旅行時間。

2.3 張量數(shù)據(jù)缺失模式與場景挖掘

旅行時間數(shù)據(jù)缺失類型大致分為三類[21-22]：隨機缺失，即缺失的元素隨機散布在數(shù)據(jù)結(jié)構(gòu)上；纖維化缺失，在數(shù)據(jù)結(jié)構(gòu)上表現(xiàn)為缺失的數(shù)據(jù)沿著張量中任意一個維度呈纖維化延伸；系統(tǒng)性缺失，由于服務(wù)器故障等系統(tǒng)性問題導(dǎo)致的數(shù)據(jù)大范圍失真失效，學(xué)者們一般不將這種缺失模式列入研究范圍內(nèi)。

本文將對纖維化缺失進行實際的場景化分析，如圖2所示缺失數(shù)據(jù)沿著不同的維度延伸對應(yīng)的缺失場景分別為“特定路段、特定日期長時間數(shù)據(jù)缺失”、“特定路段在每天固定的時間段數(shù)據(jù)缺失”、“在特定日期特定時間路網(wǎng)內(nèi)所有路段數(shù)據(jù)均缺失”?！疤囟范翁囟ㄈ掌陂L時間數(shù)據(jù)缺失”場景在實際生活中時常發(fā)生（例如卡口監(jiān)測設(shè)備長時間故障導(dǎo)致的數(shù)據(jù)缺失），故本文針對該場景的旅行時間數(shù)據(jù)填補問題為例進行重點分析。

3 考慮數(shù)據(jù)缺失模式的旅行時間填補方法研究

3.1 隨機缺失場景的旅行時間填補方法

本節(jié)基于交通數(shù)據(jù)的時間關(guān)聯(lián)性，通過歷史張量與原始張量合并建模，完善數(shù)據(jù)結(jié)構(gòu)，解決隨機缺失高缺失率場景下旅行時間填補精度低的問題。

3.1.1 考慮維度偏置的歷史旅行時間張量構(gòu)建方法

本小節(jié)通過構(gòu)建歷史旅行時間張量Xh來彌補原始張量Xr中的空缺。歷史旅行時間張量Xh的各維度數(shù)據(jù)均與原始張量Xr相同，歷史張量中元素Xh(i，j，k)代表車輛在相同工作日j的第k個時間窗通過第i條路段的旅行時間平均值。

原始張量三個維度上的旅行時間相較于歷史平均值可能存在偏差[23]。本小節(jié)提出一種自適應(yīng)標定不同維度歷史旅行時間偏差的方法，通過梯度下降的方式迭代求解修正系數(shù)，以保證歷史數(shù)據(jù)可以最大程度表征當(dāng)前的數(shù)據(jù)狀況。歷史張量修正值計算方式如下式所示：

3.1.2 考慮時間關(guān)聯(lián)性的旅行時間填補方法建模

本文基于Tucker分解框架提出了考慮歷史數(shù)據(jù)特征的改進張量分解模型，在分解過程中融入歷史張量約束項，規(guī)范因式迭代的方向，模型的目標函數(shù)如所下式所示：

目標函數(shù)以分解結(jié)果與原張量的差最小為導(dǎo)向，主體分為三部分：‖Xr-G×1U×2V×3W‖2表示的是旅行時間原始張量Xr與估計旅行時間張量的差值的范數(shù)；其中×k為張量與矩陣的k模態(tài)積遠算符，表示的是旅行時間歷史張量與估計旅行時間張量的差值的范數(shù)，用以彌補因原始數(shù)據(jù)缺失導(dǎo)致的數(shù)據(jù)稀疏性問題；‖G‖2+‖U‖2+‖V‖2+‖W‖2為正則項，用于防止分解過程過擬合；λ1，λ2為公式中各項的權(quán)重系數(shù)。

目標函數(shù)（3）的求解是一個非線性凸優(yōu)化問題，無法直接求解，所以本文使用隨機梯度下降的方法求解目標方程，得到各個變量的更新公式如下，其中令，可得：

式（4）為核張量G的更新方法，式（5）～（7）為因子矩陣U，V，W的更新方法，在算法迭代終止后，可以得到各因子矩陣的最終值，此時可以通過張量重構(gòu)的方式計算最終的推斷旅行時間張量，計算方式如下式所示：

在重構(gòu)推斷旅行時間張量過程中，會導(dǎo)致原始張量中未缺失路段的數(shù)據(jù)也相應(yīng)改變，因此需要將推斷旅行時間張量中這部分數(shù)據(jù)調(diào)整為原始數(shù)據(jù)，調(diào)整公式如下所示：

原始張量中未缺失路段的數(shù)據(jù)集合為φ={(i，j，k)|Xijk≠ 0}，缺失路段數(shù)據(jù)集合為={(i，j，k)|Xijk=0}。

3.2 纖維化缺失下旅行時間填補方法

本節(jié)通過對時空特征相似路段數(shù)據(jù)進行挖掘并融入張量分解算法，解決傳統(tǒng)張量分解忽略局部一致性導(dǎo)致的不適用纖維化缺失場景這一問題，以提高算法的準確性。

3.2.1 基于K-means算法的空間相似性挖掘

本小節(jié)采用基于劃分的聚類方法根據(jù)道路長度等物理屬性對道路進行聚類，并通過輪廓系數(shù)指標評價聚類效果的優(yōu)異，輪廓系數(shù)越大，表示簇內(nèi)實例之間緊湊，簇間距離大，聚類效果越好。輪廓系數(shù)計算公式如下式所示：

式中a(i)為向量i到同一簇內(nèi)其他點不相似程度的平均值，b(i)為向量i到其他簇的平均不相似程度的最小值。

3.2.2 基于改進LCSS算法的時間相似性挖掘

本小節(jié)提出一種自適應(yīng)的閾值設(shè)定方法，通過設(shè)定相似比例，利用兩條路段交通量的平均值近似表征路段的交通狀況，其與相似比例的乘積代替?zhèn)鹘y(tǒng)LCSS方法中的固定閾值，這種處理方式可以使算法中相似閾值隨交通狀態(tài)動態(tài)變化，當(dāng)兩個比較點的路段流量差小于動態(tài)閾值時，則認為二者相似。改進LCSS算法如下式所示：

式中A與B分別代表兩條路段的交通流量序列，長度分別為n與m，at與bi分別代表A與B中的序列點，兩個比較點間的流量差用dist(at，bi)表示，計算方式如下式所示：

相似閾值θ的選擇是模型精度與所挖掘相似路段數(shù)量的博弈過程，若選取閾值過小，則極有可能出現(xiàn)模型無可行解的情況，在本文中選取θ=0.2。

基于上述公式，最長公共子序列的相似度公式如下式所示：

通過計算同一簇類的其他路段與數(shù)據(jù)缺失路段間的交通流時序向量軌跡相似度DLCSS，選取其中軌跡相似度最大的路段為最終的相似路段。

3.2.3 考慮時空相似度的旅行時間填補方法建模

為了發(fā)揮相似路段的靶向作用，增強對缺失數(shù)據(jù)的隱形知識以及局部一致性的發(fā)現(xiàn)過程，設(shè)計Tucker分解目標函數(shù)如下式所示：

目標函數(shù)以分解后結(jié)果與原張量的差最小為導(dǎo)向，‖Xr-G×1U×2V×3W‖2表示的是旅行時間張量Xr與估計旅行時間張量的差值的范數(shù)，其中×k為張量與矩陣的k模態(tài)積運算符，k=1，2，3；F為相似路段的交通流量序列，用其表征相似路段的時空特征，T為系數(shù)矩陣，‖F(xiàn)-WT‖2用來保證分解后的時間因子矩陣與相似路段的交通流量序列結(jié)果相近，通過這種方式控制分解過程中極大程度保留了缺失路段的時空特征。

目標函數(shù)（14）的求解是一個非線性凸優(yōu)化問題，使用隨機梯度下降的方法求解目標方程，得到各個變量的更新如式（15）～（19）所示，其中令δ=Xr-G×1U×2V×3W；可得：

式（15）為核張量G的更新方法，式（16）～（18）為因子矩陣U，V，W的更新方法，式（19）為系數(shù)矩陣T的更新方法，并通過式（8）和式（9）計算得到最終的推斷旅行時間數(shù)據(jù)。

4 實例驗證及分析

本章節(jié)使用瑞安市卡口數(shù)據(jù)及所構(gòu)建的旅行時間張量，驗證旅行時間填補方法的有效性。

4.1 數(shù)據(jù)處理

本文選取浙江省瑞安市一個局部路網(wǎng)作為數(shù)據(jù)采集區(qū)域，區(qū)域內(nèi)卡口數(shù)據(jù)采集設(shè)備共35個，共計覆蓋路網(wǎng)內(nèi)108個路段，如圖3所示（圖中白色圓點代表卡口檢測系統(tǒng)安裝位置）?？跀?shù)據(jù)采集自2016年 5月 16日 00：00：00至 2016年 6月 5日 23：59：59，共計21天的交通流數(shù)據(jù)。當(dāng)車輛依次通過不同卡口時，卡口會記錄下過車時間，通過過車時間的差值即可以計算出車輛這段道路的旅行時間。

在數(shù)據(jù)預(yù)處理基礎(chǔ)上，以30 min為時間窗長度構(gòu)建旅行時間張量，張量中元素總計108864個，表示為 Xr∈ R108×21×48。

4.2 隨機缺失填補方法效果分析

為了模擬數(shù)據(jù)在不同缺失率下的數(shù)據(jù)表現(xiàn)，構(gòu)造一個與原始張量Xr相同結(jié)構(gòu)的0-1分布張量B∈R108×21×48，張量中的元素只為0或1，通過設(shè)定張量B中0元素的分布概率控制完備張量X0（未發(fā)生數(shù)據(jù)缺失）的數(shù)據(jù)缺失概率，從而計算得到實驗需要的不同缺失率下的原始張量Xr，計算方式如下式所示：

4.2.1 隨機缺失填補方法精度分析

本文中選取數(shù)據(jù)缺失率從10%～40%的場景，各個模型在不同缺失率下的精度指標表現(xiàn)如表1所示。

表1 隨機化缺失下不同模型RMSE誤差/s

圖4表示不同模型精度指標的點線圖。

整體來看，在低缺失率下幾種模型的效果大致相當(dāng)，在較高的數(shù)據(jù)缺失率下本文所提出的模型填補效果更為顯著，精度提升明顯，這是由于在高數(shù)據(jù)缺失率下，融合歷史數(shù)據(jù)張量可以更好的輔助隱形特征挖掘過程。且隨著數(shù)據(jù)缺失率的提高，傳統(tǒng)模型的誤差大多在30%數(shù)據(jù)缺失率處存在拐點，在此處模型誤差明顯的提高，而本文所提出的模型曲線增長相對平穩(wěn)，對于數(shù)據(jù)缺失率的魯棒性更優(yōu)。這個實驗結(jié)果論證了前文的觀點，張量分解模型可以通過挖掘交通數(shù)據(jù)多維度的隱式特征實現(xiàn)高精度的數(shù)據(jù)填補。

4.2.2 隨機缺失填補方法敏感度分析

本小節(jié)通過選取不同時間窗長度不同缺失條件進行模型敏感度分析，分析結(jié)果如表2所示。隨著標定時間窗長度的減小，本文模型的擬合精度逐漸降低。針對同一數(shù)據(jù)缺失率而言，模型精度存在先增長后降低的趨勢。

表2 不同時間窗下模型RMSE誤差/s

4.3 纖維化缺失填補方法效果分析

4.3.1 纖維化缺失填補方法精度分析

由圖5可以看出，本文所提出方法的散點大致緊密分布在y=x這條直線上，數(shù)值在[0，250]區(qū)間皆有不錯的擬合效果，相較于其他模型方法有著更高的填補精度。

4.3.2 纖維化缺失填補方法魯棒性分析

為驗證所提出模型的魯棒性，依次模擬原始張量在10%，20%，30%，40%纖維化缺失條件下的數(shù)據(jù)情況進行實例驗證，結(jié)果如圖6～9所示。

紅色線表示車輛通過“缺失的纖維化張量結(jié)構(gòu)”所對應(yīng)的路段在該日各個時段的實際平均旅行時間，藍色線表示模型所推斷的平均旅行時間?？傮w而言，本文所提出的模型在受到數(shù)據(jù)缺失的擾動下，仍能保持較好的擬合效果，尤其是在10%～30%的數(shù)據(jù)缺失場景下。

5 結(jié) 論

本文通過將張量數(shù)據(jù)缺失結(jié)構(gòu)與實際交通場景映射，挖掘出隨機缺失和纖維化缺失兩種場景。針對隨機缺失場景，構(gòu)建歷史旅行時間張量及其修正方法，并將歷史數(shù)據(jù)修正結(jié)果融入張量分解框架，提出一種考慮時間關(guān)聯(lián)性的旅行時間填補方法，解決了高數(shù)據(jù)缺失率下張量數(shù)據(jù)結(jié)構(gòu)被破壞而導(dǎo)致模型精度低的問題。針對纖維化缺失高頻場景，提出了挖掘與缺失路段時空特征相似路段的方法，在張量分解目標函數(shù)內(nèi)融合相似路段的時空特征，規(guī)范張量分解中的因子矩陣迭代的方向與大小，使模型收斂方向逼近纖維化缺失數(shù)據(jù)。實例結(jié)果表明，本文的模型方法精度更高，且受原始數(shù)據(jù)缺失率影響較小，模型魯棒性強。

在未來的研究中，將深入探究纖維化缺失下更精確、科學(xué)的時空相似路段挖掘方法，期望得到精度更高的旅行時間填補結(jié)果。