基于張量奇異值理論的交通數據重構方法

摘 要： 由于探測器和通信設備的故障，交通數據的缺失是不可避免的，這種缺失給智能交通系統（ITS）帶來了不利的影響。針對此問題，運用張量平均秩的概念，對張量核范數進行最小化，從而構建了新的低秩張量補全模型，并且在此基礎上，基于張量奇異值分解（T-SVD）和閾值分解（TSVT）理論，分別使用坐標梯度下降法（CGD）和交替乘子法（ADMM）對模型進行求解，提出兩個張量補全算法LRTC-CGD和LRTC-TSVT。在公開的真實時空交通數據集上進行實驗。結果表明，LRTC-CGD和LRTC-TSVT算法在不同的缺失場景和缺失率條件下，補全精度要優于現行的其他補全算法，并且在數據極端缺失情況下（70%～80%），補全的效果更加穩定。

關鍵詞： 交通數據； 低秩張量補全； 張量奇異值分解； 閾值分解

中圖分類號： TP274.2"" 文獻標志碼： A

文章編號： 1001-3695（2022）05-027-1449-05

doi：10.19734/j.issn.1001-3695.2021.10.0429

Data reconstruction method based on tensor singular value theory

Wu Jiangnan， Zhang Hongmei， Zhao Yongmei， Zeng Hang

（Equipment Management amp; Unmanned Aerial Vehicle Engineering College， Air Force Engineering University， Xi’an 710051， China）

Abstract： Due to the failure of detectors and communication equipment，the lack of traffic data is inevitable，and this kind of lack has an adverse impact on intelligent transportation systems（ITS）.To solve this problem，this paper used the concept of tensor average rank to minimize the tensor kernel norm，thereby constructed a new low-rank tensor completion model.And on this basis，based on tensor singular value decomposition（T-SVD） and threshold decomposition（TSVT） theories，it respectively used coordinate gradient descent（CGD） and alternating multiplier method（ADMM） to solve the model，and proposed two tensor completion algorithms LRTC-CGD and LRTC-TSVT.Experiments on the real spatio-temporal traffic data set show that the LRTC-CGD and LRTC-TSVT algorithms have better completion accuracy than other existing completion algorithms under different missing scenarios and missing rates.And in the case of extreme data missing（70%～80%），the effect of completion is more stable.

Key words： traffic data； low-rank tensor completion； tensor singular value decomposition； threshold decomposition

隨著現代傳感技術、通信技術、計算機技術與信息技術的不斷快速發展，智能交通系統（intelligent transport system，ITS）被廣泛運用于道路交通的管理和控制［1，2］。而交通信息采集系統作為ITS的重要組成部分，它通過傳感器來獲取全面、豐富、實時的交通信息，時空交通數據的記錄來自不同地點帶有時間標記的交通狀態（如流量和速度等）。但由于探測器和通信故障，時空交通數據的缺失是不可避免的，現實中采集得到的數據往往出現大量的缺失［3，4］，這種缺失給智能交通系統帶來了不利的影響。例如，交通控制系統需要足夠的交通流數據（即交通量、占用率和流速）來生成適當的交通管理策略，在交通預測區域，如果存在缺失數據，預測性能也會急劇下降［5，6］。因此，智能交通系統中的數據缺失問題及其影響的研究引起了交通學界的廣泛關注。

1 相關工作

面對交通數據的缺失問題，國內外學者開始進行數據補全，最早的數據補全方法是基于向量的。常見基于向量的數據補全方法有歷史鄰近補全方法[7]、基于線性/樣條回歸的補全方法[8，9]、自回歸綜合移動平均（ARIMA）模型［10，11］。但隨著研究發現，交通數據并不是完全線性的數據，并且基于向量的方法不能夠很好地利用交通數據的時空信息。因此，有學者提出用基于矩陣的方法對交通數據進行補全，隨后，文獻［12，13］提出了貝葉斯主成分分析（BPCA）和概率主成分分析（PPCA）。實驗也證明，基于矩陣的補全方法比基于向量的補全方法精確性更高。

近年來，由于對先前研究的考量和交通數據量的增大，基于矩陣的方法也不能夠覆蓋足夠多的時空信息，而且在缺失率較大和非隨機缺失的情況下，基于矩陣的方法無法處理。為了彌補以上的不足，Tan等人［14］將張量模式引入到交通數據的補全中，提出了基于Tucker分解的TDI算法，之后基于張量的補全方法在交通數據領域開始被應用。Liu等人［15］最先提出了張量跡范數的概念，用最小化多重TNN的方式來代替張量的秩最小化問題，并構造了經典的HaLRTC算法，而Zhang等人［16］提出了基于張量奇異值分解的T-SVD算法。近年來，Battaglino等人［17］將經典的CP分解模型用最小二乘法求解（TF_ALS），王薇等人［18］提出了基于3Ｄ形函數的數據修復方法，陸文琦等人［19］提出了一種基于自適應秩Tucker分解的插補方法（ARTDI），都獲得了不錯的效果。在文獻［15］的基礎上，Shang等人［20］運用p-shrinke的方式來代替張量的跡范數，提出了IpST算法。Chen等人［21］對HaLRTC的求解進行了優化，并加入了截斷核范數的思想（LRTC-TNN）。陳小波等人［22］提出了基于圖正則化和 Schatten-p 范數的交通數據恢復方法（SPGR）。而隨后Chen等人［23］又提出了一種新的張量補全思想，根據貝葉斯準則和經典的CP分解模型提出了一種貝葉斯高斯CP分解（BGCP）模型和貝葉斯時間因子分解［24］（BTTF）模型。

基于張量的方法將交通數據構造成多路矩陣，以準確捕獲交通數據的底層多模式結構。但現有的張量補全框架（LRTC）在對張量進行恢復時都需要將張量展開為矩陣進行補全計算，在一定程度上減小了張量的模式關聯性，而基于貝葉斯準則的張量補全算法補全效果穩定但精度提升不高，這又與使用張量進行補全的思想相違背。

針對上述問題，提出兩種不同的交通數據補全算法并進行了相關實驗：

a）運用張量的平均秩和核范數最小化，建立一個新的低秩張量補全模型，并分別用坐標梯度下降法（CGD）和交替乘子法（ADMM）對模型進行求解，提出兩個運用于交通數據恢復的張量補全算法LRTC-CGD和LRTC-TSVT；b）在公開的真實時空交通數據集上進行補全實驗，在不同的缺失率（20%～80%）和缺失條件（隨機缺失和非隨機缺失）下，通過同樣條件下采用LRTC-CGD和LRTC-TSVT與基線算法的補全精度進行對比，展現了該算法的優越性。

2）對比方案 在隨機缺失和非隨機缺失場景兩個不同的缺失場景下進行實驗。隨機缺失（RM）場景下，觀測值的缺失是隨機的且無目的的。非隨機缺失場景下，NM場景更具挑戰性，因為數據是以相關的方式損壞的。在兩種缺失場景下，分別設置G、S與P的缺失率為20%～80%，通過實驗來對比不同場景與不同缺失率下算法的補全精度來分析算法的性能，結果如圖2～7所示（見電子版）。RMSE與MAPE的值越小，證明算法的補全精度越高。如圖2～4所示。

3）實驗結果分析 在時空交通數據隨機缺失場景下（RM），從RMSE和MAPE的對比來看，LRTC-CGD與LRTC-TSVT的插補精度相近。在G與S數據集中，LRTC-CGD與LRTC-TSVT的補全精度要始終明顯高于其他基線算法，且隨著缺失率的增大，精度優勢相對減小。在P數據集中，在缺失率較小的情況下（20%～40%），LRTC-CGD與LRTC-TSVT的插補精度仍是最高的，且隨著缺失率的增加（50%～80%），RMSE的優勢相對減小，但MAPE的優勢卻更加明顯。整體來看，在隨機缺失場景下，缺失率設置為（20%～80%），LRTC-CGD與LRTC-TSVT的插補性能都是最優的，如圖5～7所示。

在時空交通數據的非隨機缺失場景下（NM），從RMSE和MAPE的對比來看，在G數據集中，低缺失率的情況下（20%～50%），LRTC-CGD與LRTC-TSVT的插補精度與基線算法相比并不明顯，而在極端缺失場景（60%～80%），LRTC-CGD與LRTC-TSVT的插補精度要明顯高于現有的其他基線算法。在S數據集中，在低缺失率的情況下，LRTC-CGD與LRTC-TSVT的插補精度與基線模型相比并無太大優勢，但隨著缺失率的增加，LRTC-CGD與LRTC-TSVT算法的優勢得到顯現，且在極端缺失的場景下（60%～80%），LRTC-CGD與LRTC-TSVT的插補精度要明顯優于其他算法。在P數據集中，低缺失率的情況下（20%～60%），LRTC-CGD與LRTC-TSVT算法的性能是最差的，但在極端缺失情況下（60%～80%），LRTC-CGD與LRTC-TSVT的插補精度是最高的，基線算法出現了失真情況。整體來看，在非隨機缺失場景下，缺失率設置為（20%～60%）時，LRTC-CGD與LRTC-TSVT的插補性能并不理想，缺失率設置為（70%～80%）時，LRTC-CGD與LRTC-TSVT的插補性能是最優的。

4）實驗總結 在隨機缺失場景下，缺失率設置為20%～80%，LRTC-CGD與LRTC-TSVT的插補精度一直是最高的，且總體表現得非常明顯。在非隨機缺失場景，當缺失率為（20%～60%）的情況下，LRTC-CGD與LRTC-TSVT的插補精度要略低于基線算法，當缺失率為（70%～80%）的極端缺失情況下，LRTC-CGD與LRTC-TSVT的補全精度最高，且補全效果非常穩定，沒有出現失真情況。因此，LRTC-CGD與LRTC-TSVT的優勢在于隨機缺失場景與非隨機缺失的極端缺失場景下，相較于傳統的基線算法，LRTC-CGD與LRTC-TSVT的計算都是在張量模式上進行，不需要將張量展開為矩陣進行計算，能夠比傳統的基線算法更充分利用交通數據內部的相關性信息，提高了補全的精度和在極端條件下補全的穩定性。

5 結束語

基于張量的交通數據補全算法能夠比基于矩陣的方法更加充分地利用模式關聯性，提高時空交通數據的補全精度。但現有的張量補全算法通過將張量展開成模式矩陣來對張量的核范數最小化，在一定程度上打破了多通道間固有的相關性和依賴性，可能會導致關鍵信息的丟失。為了解決這個問題，運用張量平均秩與核范數的概念，在張量的模式上對其核范數最小化，引入了新的低秩張量補全模型，并且用坐標梯度下降法和ADMM框架，設計了LRTC-CGD和LTRC-TSVT兩個算法，在張量的模式上進行補全，不需要再進行模式展開，在現有的公開交通數據集上進行實驗。實驗結果表明，在不同的缺失場景和缺失率情況下，兩種算法在性能上要明顯優于現有的其他補全算法，尤其是在極端缺失的情況下。

參考文獻：

［1］Zhang Degan，Tang Yameng，Cui Yuya，et al.Novel reliable routing method for engineering of Internet of Vehicles based on graph theory［J］.Engineering Computation，2019，36（1）：226-247.

［2］Goulart J.Traffic data imputation via tensor completion based on soft thresholding of Tucker core［J］.Transportation Research Part C：Emerging Technologies，2017，85：348-362.

［3］Tan Huachun，Wu Yuankai，Shen Bin，et al.Short-term traffic prediction based on dynamic tensor completion［J］.IEEE Trans on Intelligent Transportation Systems，2016，17（8）：2123-2133.

［4］Zhang Degan，Zhang Ting，Zhang Jie.A kind of effective data aggregating method based on compressive sensing for wireless sensor network［J］.EURASIP Journal on Wireless Communications and Networking，2018，2018（159）：article No.159.

［5］Chen Chenyi，Yin Wang，Li Li，et al.The retrieval of intra-day trend and its influence on traffic prediction［J］.Transportation Research Part C：Emerging Technologies，2012，22：103-118.

［6］Karlaftis M G，Vlahogianni E I.Statistical methods versus neural networks in transportation research：differences，similarities and some insights［J］.Transportation Research Part C：Emerging Technologies，2011，19（3）：387-399.

［7］Ni Daiheng，John D，Guin A，et al.Multiple imputation scheme for overcoming the missing values and variability issues in ITS data［J］.Journal of Transportation Engineering，2005，131（12）：931-938.

［8］Chen J，Shao J.Nearest neighbor imputation for survey data［J］.Journal of Official Statistics，2000，16（2）：113-131.

［9］Allison P D.Missing data［M］.Thousand Oaks，CA：SAGE Publications Inc.，2001.

［10］Zhong Ming，Lingras P，Sharma S，et al.Estimation of missing traffic counts using factor，genetic，neural，and regression techniques［J］.Transportation Research Part C：Emerging Technologies，2004，12：139-166.

［11］Zhong Ming，Sharma A，Lingras P，et al.Genetically designed models for accurate imputation of missing traffic counts［J］.Transportation Research Record：Journal of the Transportation Research Board，2004，1879（1）：71-79.

［12］Qu Li，Zhang Yi，Hu Jianming，et al.A BPCA based missing value imputing method for traffic flow volume data［C］//Proc of IEEE Intelligent Vehicles Symposium.Piscataway，NJ：IEEE Press，2008：985-990.

［13］Qu Li，Li Li，Zhang Yi，et al.PPCA-based missing data imputation for traffic flow volume：a systematical approach［J］.IEEE Trans on Intelligent Transportation Systems，2009，10（3）：512-522.

［14］Tan Huachun，Feng Guangdong，Feng Jianshuai，et al.A tensor-based method for missing traffic data completion［J］.Transportation Research Part C：Emerging Technologies，2013，28：15-27.

［15］Liu Ji，Musialski P，Wonka P，et al.Tensor completion for estimating missing values in visual data［J］.IEEE Trans on Pattern Analysis and Machine Intelligence，2013，35（1）：208-220.

［16］Zhang Zemin，Aeron S.Exact tensor completion using t-SVD［J］.IEEE Trans on Signal Processing，2017，65（6）：1511-1526.

［17］Battaglino C，Ballard G，Kolda T G.A practical randomized CP tensor decomposition［J］.SIAM Journal on Matrix Analysis and Applications，2017，39（2）：876-901.

［18］王薇，程澤陽，劉夢依，等.基于時空相關性的交通流故障數據修復方法［J］.浙江大學學報：工學版，2017，51（9）：1727-1734. （Wang Wei，Cheng Zeyang，Liu Mengyi，et al.Traffic flow fault data restoration method based on spatio-temporal correlation［J］.Journal of Zhejiang University：Engineering Science，2017，51（9）：1727-1734.）

［19］陸文琦，周天，谷遠利，等.基于張量分解理論的車道級交通流數據修復算法［J］.吉林大學學報：工學版，2021，51（5）：1708-1715. （Lu Wenqi，Zhou Tian，Gu Yuanli，et al.Lane level traffic flow data repair algorithm based on tensor decomposition theory［J］.Journal of Jilin University：Engineering and Technology Edition，2021，51（5）：1708-1715.）

［20］Shang Kun，Li Yufan，Huang Zhenghai.Iterative p-shrinkage thresholding algorithm for low Tucker rank tensor recovery［J］.Information Sciences，2019，482：374-391.

［21］Chen Xinyu，Yang Jinming，Sun Lijun.A nonconvex low-rank tensor completion model for spatio-temporal traffic data imputation［J］.Transportation Research Part C：Emerging Technologies，2020，117：102673.

［22］陳小波，梁書榮，柯佳，等.基于圖正則化和Schatten-p范數的交通數據恢復方法［J/OL］.西南交通大學報.［2021-11-22］.http：//kns.cnki.net/kcms/detail/51.1277.U.20210913.1343.004.html. （Chen Xiaobo，Liang Shurong，Ke Jia，et al.Traffic data reco-very method based on graph regularization and Schatten-p norm［J/OL］.Journal of Southwest Jiaotong University.［2021-11-22］.http：//kns.cnki.net/kcms/detail/51.1277.U.20210913.1343.004.html.）

［23］Chen Xinyu，He Zhaocheng，Sun Lijun.A Bayesian tensor decomposition approach for spatiotemporal traffic data imputation［J］.Transportation Research Part C：Emerging Technologies，2019，98：73-84.

［24］Chen Xinyu，Sun Lijun.Bayesian temporal factorization for multidimensional time series prediction［J/OL］.IEEE Trans on Pattern Analysis and Machine Intelligence.（2021-03-17）.https：//doi.org/10.1109/TPAMI.2021.3066551.

［25］Lu Canyi，Feng Jiashi，Chen Yudong，et al.Tensor robust principal component analysis with a new tensor nuclear norm［J］.IEEE Trans on Pattern Analysis and Machine Intelligence，2020，42（4）：925-938.

［26］Zhang Zemin，Ely G，Aeron S，et al.Novel methods for multilinear data completion and de-noising based on tensor-SVD［C］//Proc of IEEE Conference on Computer Vision and Pattern Recognition.Piscataway，NJ：IEEE Press，2014：3842-3849.

［27］Tripathi R，Mohan B，Rajawat K.Adaptive low-rank matrix completion［J］.IEEE Trans on Signal Processing，2017，65（14）：3603-3616.

［28］Boyd S，Parikh N，Chu E，et al.Distributed optimization and statistical learning via the alternating direction method of multipliers［M］.［S.l.］：Now Foundations and Trends，2010：128.

［29］Cui Zhiyong，Ke Ruimin，Pu Ziyuan，et al.Deep bidirectional and unidirectional LSTM recurrent neural network for network-wide traffic speed prediction［EB/OL］.（2019-11-23）.https：//arxiv.org/abs/1801.02143.

［30］Zhang Yin，Roughan M，Willinger W，et al.Spatio-temporal compressive sensing and Internet traffic matrices［C］//Proc of ACM SIGCOMM Conference on Data Communication.New York：ACM Press，2009：267-278.