張量表達下的多模態交通缺失數據補全算法

胡 雪，彭敦陸

(上海理工大學 光電信息與計算機工程學院，上海 200093)

1 引 言

近年來，汽車數量的快速增長導致道路擁擠現象越來越嚴重，對交通管理的智能化迫在眉睫.行車數據是進行智能交通網絡規劃、避免擁堵等應用的基礎，完整的數據有利于提取有價值的交通信息.然而，實際采集的真實數據，由于檢測器故障、通信處理錯誤等各種因素，往往使得來自多源感知設備的交通數據產生丟失的情況，甚至在一些情況下非常普遍[1].同時，高速公路攝像頭(監控視頻、圖像等)、流量檢測器等所采集的多模態交通數據，其編碼方式、語義、標識存在差異，導致了信息無法融合，形成一個個信息孤島.如何高效地實現多模態交通數據缺失值補全具有明顯的現實應用意義.

國內外學者提出了許多交通數據缺失的補全方法.研究人員最初將歷史(最近鄰)歸責方法[2]應用到交通數據補全上.隨后基于主成分分析提出了大量數據補全方法，如貝葉斯主成分分析(BPCA)[3]和概率主成分分析法(PPCA)[4].作為一種能夠綜合表達數據的工具，近年來張量在數據處理領域中快速發展，尤其是在交通數據處理和挖掘領域應用越來越廣.Acar[5]等人提出了用加權優化的CP分解(CP-WOPT) 處理缺失值，通過實驗驗證具有很好的性能.

盡管在單一數據源時具有較好的表現，但這些方法沒有對多模態數據集合進行缺失數據補全的進一步研究.基于此，本文針對交通監控視頻(非結構化數據)與車流量探測數據(結構化數據)，建立了用以描述多模態交通數據的張量模型，同時提出了基于Tucker-Crossover的多模態數據補全算法(Tucker-Crossover based Multimodal Data Imputation Algorithm，TCMD-IA).該方法融合了非結構化與結構化數據，通過張量對不同類型的數據進行統一表達，并改進Tucker分解所得的因子矩陣，將其與另一階上所得的核矩陣進行特征融合，從而進一步提高數據補全的準確性.結合真實的多模態交通數據集實驗，結果證明TCMD-IA對于多模態缺失數據的補全效果優于其他方法，且魯棒性好.

論文其余部分的組織如下：第2部分介紹近年來交通數據缺失值估計的研究結果；第3部分給出本文所用符號的含義、張量理論基礎、多模態交通數據及問題定義；第4部分給出多模態交通數據的表達和本文提出的基于Tucker-Crossover的多模態數據補全算法(TCMD-IA)；第5部分在真實數據集上進行實驗，對所提算法進行有效性驗證；第6部分給出論文的結論.

2 相關工作

過去幾十年中，學者們提出了各種補全算法已經被應用到缺失值補全中.歷史(最近鄰)歸責方法[2]通常用鄰近幾天同一時間、地點的已知數據，通過取平均值等簡單操作進行填補.Qu[3，4]等人提出了BPCA和PPCA，綜合考慮了交通數據的日周期性和區間變化，是解決交通流量數據估計的經典方法，并通過實驗證明了其有效性.Liu[6]等人首次提出了一種基于跡范數最小化的張量補全方法(HaLRTC).他們推廣了矩陣跡范數并定義了張量跟蹤范數，從而將張量補全問題表示為一個凸優化問題.Zhao[7]提出了一種基于分布式減法聚類的數據填充方法，通過利用云計算技術優化聚類算法，根據聚類結果和加權距離進行填充.Han[8]等人提出了一種基于不完備集的雙向聚類的算法，通過雙聚類的完美簇的特性來構造屬性差異矩陣，保存了對象之間的最大相似屬性集，進而以雙聚類的結果對缺失數據進行填補.Li[9]等人使用同類簇的均值對不完備數據進行預填充，通過形成初始完備數據集，進一步對數據集聚類，并運用同類簇的均值修正初始充填值.

在交通數據分析上，Tan[10]等人提出了多模式關聯張量模型，將交通數據分為鏈路、周、天、小時4個不同模式，構建了四階張量交通數據表達模型.并提出了基于Tucker分解的流量數據注入方法(TDI)，用于處理缺失數據的問題.該方法在保留矩陣模型優點的基礎上，更好地挖掘了交通數據的潛在相關性.Asif[11]等人通過提取大型路網中常見的交通模式來估計缺失值，采用定點連續的近似奇異值分解、正則多進分解、最小二乘和變分貝葉斯主成分分析，提出了多種基于矩陣和張量的交通數據補全方法.Chen[12]等人將貝葉斯概率矩陣分解模型推廣到高階張量，并將其應用于時空交通數據的輸入任務，通過大量實驗探討了不同的數據表示方式對歸責性能的影響.Lin[13]等人提出了一種基于張量分解的張量補全算法，并在算法中引入了時空正則化約束，提高了算法的補全性能，該算法利用該代數框架對交通數據的缺失進行處理效率更高.

目前交通數據的補全研究絕大多數是針對結構化數據，對于多模態交通數據的研究相對較少，而多源的異構數據進行融合處理對于交通數據的利用十分重要.因此，在本項研究中，我們提出了TCMD-IA方法，對結構化和非結構化兩種類型的數據缺失值進行補全.該方法通過構造合適的三階張量來表達包含時空信息的多模態交通數據，結合Tucker分解，對其進行最小二乘法分解所得的因子矩陣與核矩陣進行交叉相乘，融合了不同階之間的潛在相關信息，從而提高對缺失數據的補全效果，通過實驗證明該方法的估計效果優于其他方法，且具有較好的魯棒性.

3 準備工作

本節主要介紹多模態交通數據，并且給出下文所需張量理論基礎、多模態交通數據知識，同時定義了如何對缺失數據進行補全.3.1節給出所需張量理論基礎.3.2節介紹了多模態交通數據.3.3定義了本文所研究的問題.文章用到的符號以及其所代表的含義見表1.

表1 文章中所用符號其含義Table 1 Explanation of words used in paper

3.1 張量理論基礎

矩陣乘積：給定矩陣A∈RI×J和矩陣B∈RJ×K，我們稱C∈RI×K為A和B的乘積，用AB表示，其第(i，k)項如公式(1)所示.當A的列數與B的行數相同時，矩陣乘積才有意義.

(1)

n-Mode展開：對于張量X∈RI1×I2×…×Ir，從指定的第n階上進行切割得到若干數據切片，其中1≤n≤r.將得到的切片以In為行，按順序展開合并成矩陣，我們將這一過程稱為張量的n-Mode展開.本文用Γ(X,n)表示張量在第n階的展開矩陣，如公式(2)所示：

(2)

n階模乘：給定張量X∈RI1×I2×…×Ir和矩陣M∈RIn×J，先將張量X在第n階上進行n-Mode展開，然后將M與展開得到的矩陣相乘得到矩陣乘積，最后將得到的矩陣在第n階上重建張量，表達式如公式(3)所示：

X×nM∈RI1×In-1×J×In+1×…×Ir

(3)

圖1 Tucker分解Fig.1 Tucker decomposition

Tucker：以三階張量X∈RI1×I2×I3為例，如圖1所示，將X分解為一個核張量G∈RL1×L2×L3和3個因子矩陣U1∈RI1×L1，U2∈RI2×L2，U3∈RI3×L3，核張量G包含了不同階之間的潛在相關性，因子矩陣U1，U2，U3可以理解為張量模型在各個階的主成分，他們通常是兩兩正交的，三階張量的Tucker分解表達式如公式(4)所示：

(4)

3.2 多模態交通數據

生活中，交通數據的完整性對于進一步數據分析、智能交通的優化等具有十分重要的作用，如圖2所示.隨著技術的發展，我們收集交通數據的方法也越來越多，道路監控數據、流量檢測、GPS定位等設備都收集了成千上萬的數據.這些數據由于來源的不同，導致了他們的編碼方式、語義的差異，構成了信息孤島.但來自于不同平臺的異構數據，往往存在著相關性.例如對于同一路口的監控錄像和車流量對于該路段的實時車況有著很高的價值，同時經過該路段的GPS數據對于我們交通規劃也有很大的幫助.因此，將不同類型的交通數據通過特定的方法，本文采用張量進行融合后，將原本無法交互的信息進行統一映射，便于后續進一步挖掘交通信息的相關性，提高交通數據的利用率，這一過程對于智能交通規劃、擁塞避免、智慧城市有著很大的意義.

圖2 多模態交通數據Fig.2 Multimodal traffic data

數據融合技術已在多傳感器環境中廣泛應用，目的是通過使用多源數據來獲得較高的可靠性.但由于各種傳感器的特點以及數據類型的差異，以更小的代價獲取更高質量的信息并不是一件簡單的事情.在過去的十幾年中，學者們對數據融合做了較多的研究，主要包括信息融合的方法、結構、層次以及信息的表示和轉換.但對于多模態交通數據的融合目前的研究本不是很多.本文針對非結構化(道路監控視頻)和結構化(車流量)兩大類交通數據，進行張量建模，并對其所包含的缺失數據進行補全.

3.3 問題定義

結合上文提出的多模態交通數據張量模型，我們分別用P，W∈RI1×I2×I3表示完整數據和缺失權重張量.便于分析，我們將P分成實驗數據和檢驗數據兩部分.實驗數據(即缺失數據)用于驗證缺失值估計的誤差，用Wi1,i2,i3=0表示.已知數據用用Wi1,i2,i3=1表示，所有已知數據的集合用Ω表示，如公式(5)所示：

(5)

我們可以根據P，W得到包含缺失的實驗數據集A，表達如公式(6)所示：

Ai1,i2,i3=Pi1,i2,i3Wi1,i2,i3

(6)

多模態交通數據張量化后，估計缺失數據可以視為一個張量補全問題，其目標是通過張量分解對缺失值進行估計，并且使估計值盡可能地接近真實值.用X表示填充后的數據集，那么，我們可以用公式(7)來表示目標函數：

min|P-X|，s.t.PΩ=XΩ

(7)

4 TCMD-IA

4.1 多模態交通數據的表達

結合交通數據，本文針對兩種不同類型的數據進行缺失值估計：1) 非結構化數據，主要包含道路監控視頻；2) 結構化數據，主要針對車流量檢測數據.交通監控視頻主要包括視頻幀、分辨率、色彩空間等特征.其中分辨率由像素寬和高組成，色彩空間可用RGB表示.又可利用灰度值將三維RGB轉化為一維灰度值.轉化公式如公式(8)所示：

Gray=0.299Red+0.587Green+0.114Blue

(8)

因此，視頻數據可用三階張量T∈RIWI×IHI×IFR表示，其中IWI表示水平像素點，IHI表示垂直像素點，IFR表示視頻幀數，對應的數據為該像素點的灰度值.

車流量檢測數據通過道路檢測設備采集，每間隔一段時間收集通過車輛數目，可根據不同時間間隔分成不同的時間片數據.根據文獻[14]中提出車流量信息以天和周為時間切割單位時具有一定的循環性和相關性，因此本文構造F∈RITI×IDA×IWE來表達車流量數據，其中ITI表示一天中測試車流量次數，IDA表示按天為單位劃分，IWE表示按周為單位劃分，對應的每個單元數據為車流量.

得到上述兩種不同類型的交通數據張量模型后，我們觀察可知，視頻數據的水平和垂直像素維數是固定的，幀數可隨著監控時長增加.同時，車流量數據劃分之后，每天的測試次數與每周的天數是固定的，測試的周數是可增加的.即T,F第一、二階上的維度是不變的，第三階的維度會隨著時間的增加而變大.基于此，我們將上述兩種不同類型數據映射到同一張量P中，在第一階上取T,F維度之和，對其進行疊加映射.在第二階上取T,F對應維度的較大值，較小張量的對應缺失數據置空.第三階的維數取決于時間長短.得到融合了結構化與非結構化數據統一表達張量P.

4.2 基于Tucker-Crossover的多模態數據補全算法

上節我們已經將兩種不同類型的交通數據統一映射到張量空間中，本節我們將重點介紹Tucker-Crossover模型，并將其應用到多模態張量表達下的交通數據補全上，并提出基于Tucker-Crossover的多模態交通數據補全算法(TCMD-IA).該方法利用了最小二乘法Tucker分解，計算三階張量模型的核張量和各階的因子矩陣.并提取核矩陣與另一階的因子矩陣進行交叉相乘，將各階的潛在相關性融合到因子矩陣中，使其更具有特征性，增加了缺失數據補全的準確性.

結合前文定義的P和W，構造包含缺失的多模態交通數據集A∈RI1×I2×I3，通過最小二乘法的Tucker選取合適的初始核張量B∈RL1×L2×L3.將張量進行n-Mode展開后與初始因子矩陣相乘，計算該次迭代的特征值與特征向量，排序后選取前n個特征值所對應特征向量作為因子矩陣組成.迭代至收斂，可以得到最終的核張量B和因子矩陣Ut，即算法1中的Ft.

Ft∈RIt×Lt，wheret=1,2,3

(9)

核張量B表達了各階上數據之間的潛在相關性，因子矩陣則代表著各階的主要特征.針對不同的數據，核張量不同.為了進一步利用各階之間的潛在相關性，本文定義了核張量在第t階的特征矩陣為核矩陣Ct.

Ct∈RLt×Lt，wheret=1,2,3

(10)

為了更好地利用各階之間的潛在相關性，我們將因子矩陣Ft與下一階的核矩陣Ct進行交叉相乘，得到特征矩陣Rt，最后結合Tucker進行張量的重建，得到的X為補全缺失值后的完整數據集.該操作再次利用不同階之間的潛在相關性，將階之間的特征融合到特征矩陣中，從而提高了算法對于數據補全的準確性.

Rt=FtCk，where k=(t+1)mod 3

(11)

X=B×1R1×2R2×3R3

(12)

TCMD-IA的偽代碼如算法1所示.算法第1行通過缺失權重張量W構造了包含缺失的實驗數據集A，如公式(6)所示.第2-12行為最小二乘法的Tucker分解，通過迭代將實驗數據集分解成核張量B和因子矩陣Ft兩部分.第13-18行構造了核矩陣Ct，將因子矩陣與下一階的核矩陣進行信息融合，計算特征矩陣Rt.第19行重建完整張量，X可視為補全后的數據集.第20-22行，通過不同的評價指標對缺失值補全效果進行估計.

算法1.基于Tucker-Crossover的多模態交通數據補全算法

輸入：包含完整數據和缺失權重張量P,W∈RI1×I2×I3和最大迭代次數maxIterate

輸出：補全評價指標Δ

1. A←(P,W);

#通過最小二乘法Tucker分解構建核張量與因子矩陣

2. InitialU;

3. For iterate i in 1:maxIterate do

4. For order n in 1:3 do

5. U=ttm(A，U，-n);

6.U{n}=nvecs(U，n);

7. End For

8. C=ttm(U，U，n);

9. End For

10. Ttensor=ttensor(C，U);

11.N=ndims(C);#計算核張量各階維數

12. B=Ttensor.C;

13. For order t in 1:3 do

14.Ft=C.Ttensor.Ut#因子矩陣

15.Ct=Ft(1:N{t},:);#核矩陣

16. k=(t+1) mod 3;

17.Rt=FtCk;#特征矩陣

18. End For

19. X=B×1R1×2R2×3R3;#重構張量

20. For missing item in A do

21. Δ=Eval(P，X);

22. End for

5 實驗分析

5.1 數據來源

實驗道路監控視頻與車流量數據采集于上海市楊浦區某路段.車流量數據選取的時間節點為2019年9月1日-2019年9月30日，每天的13點-21點，以1分鐘為單位采集通過車輛數，共14，400條數據.道路監控視頻像素656*656，共650幀.

5.2 評價指標

(13)

(14)

錯誤率(Error Ratio，ER)用來度量估計后張量項的恢復誤差，其表達式如公式(15)所示，值域為[0，1]，值越接近0表示數據補全的效果越接近真實值.

(15)

5.3 實驗結果與分析

實驗1.核張量大小對實驗結果影響

實驗通過設置核張量在各個階上維數的不同，探究了核張量大小對缺失數據估計的影響.本節根據核張量各階維數的比例，選取了[50～300，50～200，50～70]的取值范圍，通過隨機組合共設置了12組不同大小的核張量來探究核張量對缺失數據估計效果的影響，如表2所示.圖3給出不同核張量大小對缺失數據的補全效果RMSE折線對比圖.從圖中可以看出，C1-C4的RMSE較大，保持在112.3左右.隨著第二階維數的增加，C5-C8的RMSE下降至110附近.C9-C12四組的RMSE相對較小，且C10所包含的數據最少.因此，在后續實驗中，我們選取C10所對應的核張量大小，即[200，200，50].

表2 核張量表Table 2 Core tensor Table

圖3 核張量對補全效果影響Fig.3 Effects of core tensor on completion

實驗2.與其他缺失值填充方法的比較

圖4 不同補全方法效果對比圖Fig.4 Comparison of different completion methods

實驗設定P[：，：，90：100]為缺失數據，其余數據為已知數據，結果如圖4所示.RMSE子圖中，最大期望法的誤差最小，TCMD-IA僅次于最大期望法，且與前者差距較小，平均值法的誤差最大.R-square子圖中，TCMD-IA的得分最大，擬合效果最好，最大期望值得分最小.ER子圖中，TCMD-IA的錯誤率最小，平均值法最大.綜合3種評價指標，我們可知T-CURE與TCMD-IA兩種基于張量的方法，相比于傳統方法對于缺失值處理的整體效果更佳，進一步驗證了前文給出的張量在數據處理領域的表現.TCMD-IA通過Tucker分解所得的各階特征矩陣和不同階之間的相關性，更好地利用了已知數據，從而提高了數據補全的準確性，整體效果均優于T-CURE.

實驗3.不同缺失率下的數據補全效果

實驗通過選取了不同的缺失率(Missing Ratio，MR)來進一步衡量TCMD-IA對于多模態交通數據的補全效果.缺失率從10%-80%，每增加10%計算數據估計的RMSE、R-square和ER值，實驗結果如表3所示.從表中可知，隨著缺失率不斷增加，TCMD-IA的補全效果在3種評價指標下均表現優秀，其RMSE穩定在23左右，R-square維持在0.7，ER恒定在0.3，具有較高的魯棒性.這表明TCMD-IA在對數據補全的過程中，通過采用Tucker分解，對已知數據的比例要求并不是十分嚴格，僅需要少量已知數據即可進行高質量數據估計，因此更適合于缺失率較大的情況.

表3 不同缺失率下的數據補全實驗結果Table 3 Experimental results of data completion under different miss rates

6 結 論

多模態交通數據的表達有利于數據的統一處理，同時，交通數據的補全可以幫助我們更好地挖掘數據的相關性和潛在價值，進一步為智能交通網絡規劃、避免擁堵等應用提供可靠數據.本文所提的模型將結構化與非結構化數據通過張量方法進行融合表達，并在此基礎上提出了基于Tucker-Crossover的多模態數據補全算法(TCMD-IA).該方法通過Tucker分解，將因子矩陣與另一階分解所得核矩陣交叉相乘，更好地融合了階與階的特征，進一步利用了不同階的潛在相關性，從而提高算法的補全效果.在真實數據集上實驗表明，文本所提算法具有更好地補全效果和魯棒性.下一步工作將繼續考慮更多不同類型的數據進行融合，提高缺失數據統一補全的效果.