基于圖正則化和Schatten-p范數最小化的交通數據恢復

陳小波，梁書榮，柯 佳，陳 玲，胡 煜

（1.江蘇大學汽車工程研究院，江蘇 鎮江 212013；2.江蘇大學管理學院，江蘇 鎮江 212013）

準確、完整的交通數據是實現交通大數據分析與挖掘的基礎.然而，實際交通環境中，由于檢測器故障、惡劣天氣、通信中斷等原因，采集的交通數據通常存在缺失值.例如，北京交通流數據檢測設備采集的數據中每天約有10%的數據缺失[1].傳統的機器學習算法，如支持向量機、神經網絡等無法處理不完整數據，嚴重地影響交通預測與分析智能算法的性能.因此，數據缺失問題已成為交通大數據分析的關鍵挑戰之一.

近年來，如何對交通數據中的缺失值進行準確恢復受到國內外學者的廣泛關注.由于路網的拓撲結構、人們出行行為的規律性和周期性等，同一路網中不同位置的檢測器在不同檢測時間所記錄的數據具有較強的時空相關性，因此，充分挖掘交通數據內在的時空相關性是實現缺失數據準確恢復的關鍵.目前，交通數據缺失值恢復的主要方法可分為三類：基于預測的方法、基于插值的方法和基于統計學習的方法.基于預測的方法是利用歷史數據的特性將缺失值作為預測的目標進行恢復；例如，Henrickson等[2]針對交通數據中的連續缺失現象，提出一種預測均值匹配多重恢復方法，即使是全天數據缺失，也能取得良好的效果；但這類方法基于歷史數據建模，忽略了缺失值之后的數據所提供的信息，導致對信息利用不充分，同時，當數據變化波動較大時，恢復數據的準確性將顯著降低.基于插值的方法是利用缺失值前后鄰近的數據或者缺失值所在的鄰近檢測器數據取加權平均作為缺失值的恢復值；孫玲等[3]通過研究缺失值與觀測值的相關性，對不同相關性的數據給予不同的權重，通過加權平均作為插補值；基于插值的方法計算簡單，但要求缺失數據前后的相似性較高，并且當缺失值周圍數據也存在缺失時，這類方法將會出現較大誤差.基于統計學習的方法通過引入機器學習理論與算法[4-5]建模交通數據的時空關系，實現缺失值恢復；李林超等[6]提出一種基于多源數據融合的異質交通流數據修復方法，通過自編碼器提取高維多源交通流數據的時空特征，并采用隨機森林估計數據中的缺失值；這類方法主要是建立符合數據分布的模型，并不斷調整模型參數，使之實現對數據的最優擬合，進而實現缺失值的恢復.

低秩矩陣補全（low-rank matrix completion，LRMC）、低秩張量補全（low-rank tensor completion，LRTC）算法被成功應用于交通數據缺失值恢復[7].由于交通數據的時空相關性，交通數據矩陣具有低秩結構，通過矩陣秩最小化實現對缺失數據矩陣的恢復.Chen等[8]將交通量數據表示為張量形式，并利用貝葉斯張量分解理論交替優化缺失值和概率模型參數.Li等[7]對4種LRTC和4種預測模型進行了研究，表明提高缺失值恢復精度可以改善交通預測模型的性能.基于LRMC的缺失值恢復方法取得了較好的效果，然而，最小化秩函數是一個NP （nondeterministic polynomial）難的非凸優化問題，難以在多項式時間內求解.一些方法將秩函數凸松弛為矩陣核范數進行求解，最小化核范數是一個凸優化問題，具有全局最優解.然而，凸松弛問題的最優解可能會偏離原問題的最優解.同時，大多數基于LRMC的恢復方法只利用了數據矩陣的全局時空相關性，而沒有充分利用數據的局部結構特性.

基于上述分析，本文提出一種基于圖正則化和Schatten-p范數（Schatten-pnorm and graph regularization，SPGR）的交通數據缺失值恢復方法.首先，應用已有的數據缺失值恢復方法對缺失值進行初步估計，基于此，建立刻畫交通數據局部近鄰結構的圖模型以反映不同樣本之間的相似度；依據交通數據的低秩結構這一全局先驗信息，應用Schatten-p范數逼近矩陣的秩函數，提出融合圖正則化和Schattenp范數最小化的缺失值恢復模型.然后，基于交替方向乘子法（alternating direction method of multipliers，ADMM）框架設計優化算法，實現對模型的有效求解.最后，通過在真實路網交通流量與速度數據上的實驗對比分析驗證該方法的有效性.

1 問題描述

將交通數據（如交通流量、速度）表示為變量矩陣X=(X1,X2,···,Xi,···,XN)∈RM×N.N為樣本總數；M為檢測器一天采集的交通數據個數，即一個樣本中的數據量；Xi=(xi(1),xi(2),···,xi(q),···,xi(Q))T，xi(q)為第i個樣本中第q個時刻的交通數據.設 ?表示X中已知元素的下標集合，即X?為觀測值集合，表示X中缺失元素的下標集合，因此，交通數據恢復問題就是根據觀測值集合X?準確估計缺失值集合.

2 基于SPGR的交通數據缺失值恢復算法

2.1 算法框架

本文提出的基于圖正則化和Schatten-p范數最小化的交通數據缺失值恢復算法，算法流程如圖1所示，具體包括以下步驟：

圖1 交通數據恢復算法框架Fig.1 Diagram of traffic data imputation algorithm

步驟1應用已有的數據缺失值恢復方法（如LRMC）得到缺失值的初始估計，其中，當xi(q)已知時，(q)=xi(q).

步驟2根據初始估計的結果，計算任意兩個樣本之間的距離，表示為矩陣D=(dij)∈RN×N，其中，dij為第i個樣本與第j個樣本間的距離，j=1,2,···,N，通過加權歐幾里得公式[9]計算，如式（1）所示.

式中：θq為兩樣本在第q個時刻的差值權重；θ?q為 θq的歸一化值；α為相對小的正數，本文取0.1.

步驟3對樣本Xi，根據距離矩陣D選出與之最接近的K個樣本，表示為集合Ne(i).然后構造鄰接矩陣（權矩陣）S=(sij)∈RN×N.

步驟4基于X與S，建立SPGR模型并求解，得到最終恢復值Y=(Y1,Y2,···,YN).

2.2 SPGR模型

如前所述，交通數據具有較強的時空相關性，因此，交通數據矩陣具有低秩結構[1]，可將缺失值恢復問題轉化為矩陣秩最小化問題，如式（5）所示.

式中：A∈RM×N為觀測值矩陣；P?(?)為 ? 的投影運算，如式（6）所示.

然而，由于秩函數是非凸且不連續，所以式（5）是一個NP難問題，難以求解.為解決這一問題，用矩陣的Schatten-p（0

式中：∥X∥sp為X的Schatten-p范數；σt為X的第t個奇異值.

當p= 1 時，Schatten-1范數即為核范數.當p越趨近于0時，X的Schatten-p范數越接近秩函數.當p= 0 時，式（7）就是X的秩函數.總的來說，與核范數相比，Schatten-p范數對秩函數的逼近能力更強，可以更精確刻畫數據的低秩結構.因此，本文構建基于Schatten-p范數最小化的缺失值恢復模型，如式（8）所示.

式中：∥?∥F為矩陣的F范數.

同時，鄰近的數據樣本具有相似的特征，為更好利用這種信息，在進行恢復時，將所有鄰域樣本之間的距離限制在適當的范圍內，以防止被恢復樣本與鄰域樣本的差異過大.基于上述分析，提出圖正則化來刻畫這種局部鄰近結構：

式中：L=E?S，為圖的拉普拉斯矩陣；E為對角元素是的對角矩陣.

結合式（8）、（9），SPGR的目標函數為

式中：λ>0為控制圖正則化項的權重常數.

2.3 基于ADMM的優化算法

本文采用交替方向乘子法（ADMM）框架尋求式（10）的最優解[10].首先，引入輔助變量W和Z，將式（10）轉化為式（11）所示等價問題.

構造式（11）的增廣拉格朗日函數為

式中：U、V為拉格朗日乘子；μ1>0，μ2>0，為懲罰系數.

增廣拉格朗日函數融合了罰函數法與拉格朗日乘子法的優點，依據ADMM框架對優化變量進行迭代求解.一個變量進行優化時，固定其他變量，通過變量交替近似求解，實現算法結果的優化.

1）固定變量Z和X，

式中：l為ADMM算法中的迭代次數；Wl、Zl、Xl、Ul、Vl分別為W、Z、X、U、V迭代l次后對應的數值.

式（13）的最優解通過迭代算法[11]求出.

2）固定變量W和X，

式（14）中對Z求導，并將導數設為0，得到

3）固定變量W和Z，

式（16）中對X求導，并將導數設為0，得到

式（17）為Sylvester方程，對于方程AX+XB=C，其解表示為X=s(A,B,C)

[12]，s(?)為Sylvester方程的求解運算.因此，

4）更新乘子Ul+ 1和Vl+ 1，

變量W、Z和X按照上述規則迭代更新，直到算法收斂，收斂條件 ε為

式中：r為很小的正數，本文取 1×10?5.

當 ε

綜上，求解式（11）的優化算法流程如圖2所示.

圖2 ADMM流程Fig.2 Flow chart of ADMM

3 實驗驗證

3.1 交通數據與實驗方案

為了評估SPGR方法的數據恢復性能，在真實的交通流量和交通速度數據上進行實驗分析.交通流量數據來自美國俄勒岡州波特蘭市交通信息中心，從I205和I84州際公路構成的路網中選擇40個只有極少缺失數據的檢測站采集數據.由于工作日的交通流量數據與周末和節假日的數據存在較大差異，因此，選取2015年中連續30個工作日的交通流數據進行研究.傳感器采樣間隔為15 min，最終獲取30 × 40 = 1200個樣本，構造為96 × 1200的數據矩陣.此外，交通速度數據集為中國廣州兩個月（2016年8月1日至2016年9月30日共61 d）內以10 min為間隔的7個路段（主要包括城市快速路和干線）的速度信息.因此，得到7 × 61 = 421個樣本，構造為144 × 421數據矩陣.圖3展示了8個傳感器在同一天的交通數據變化情況.

圖3 同一天中不同傳感器交通流和交通速度的變化情況Fig.3 Changes in traffic flow and speed from different sensors over the same day

反映交通數據缺失值的復雜分布，模擬3種常見的數據缺失模式：1）完全隨機缺失（missing completely at random，MCAR），缺失值獨立于其他缺失數據或已知數據，表現為一組隨機分布的孤立點；2）隨機缺失（missing at random，MAR），交通數據表現為連續缺失的現象，即缺失值的恢復依賴于相鄰的缺失值；3）混合缺失（mixture of MCAR and MAR，MIXED），MAR與MCAR的混合比例各為0.5.圖4為不同缺失模式的示例，圖中每行表示一個流量樣本，每列表示一個變量，黑色表示缺失值.

圖4 數據缺失模式模擬示例Fig.4 Simulation examples of data missing modes

為綜合比較不同數據恢復方法的有效性，將提出的SPGR模型、去除圖正則化的SP模型（Schattenp范數最小化，λ=0）與3種缺失值恢復方法：LRMC、概率主成分分析（probabilistic principal component analysis，PPCA）、局部最小二乘（local least squares，LLS）進行比較[1,13-14].這3種對比方法涵蓋了數據缺失值恢復的主流技術，包括低秩矩陣補全、概率模型和回歸模型.

實驗中，按照缺失模式和缺失比例模擬缺失值.其中，缺失率 δ 定義為缺失數據數量與總數據量之比，以0.1為步長將 δ 從0.1增加到0.5，研究不同缺失率對恢復性能的影響.為衡量不同算法的恢復性能，采用缺失項的恢復值與真實值之間的均方根誤差（RMSE，eRMSE）和平均絕對百分比誤差（MAPE，eMAPE）表示，分別為

式中：C為缺失值的總數目；和分別為真實值和恢復值.

RMSE和MAPE越小，算法的恢復性能越好.為準確評估5種缺失值恢復方法在兩種交通數據上的性能，減少隨機性對實驗結果的影響，每種實驗均重復5次，取實驗結果的誤差平均值作為評價缺失值恢復方法性能的依據.

3.2 實驗結果分析

表1～ 3分別列出了不同算法在MCAR、MAR和MIXED模式下的恢復誤差，根據實驗結果，可以得到以下結論：1）MCAR缺失模式下，各種算法的恢復誤差最小；而在MAR缺失模式下，因缺失大量相關信息，導致數據恢復誤差較大；此外，每種方法的恢復誤差隨著缺失率的增加而增加.2）在恢復性能方面，LRMC和PPCA方法不能很好地處理內部結構復雜的數據集，導致總體性能比其他方法差；當缺失率較低時，PPCA的性能較好，而當缺失率增加時，LRMC的性能優于PPCA；LLS在低缺失率下恢復性能較好，然而，當缺失率增加時，其恢復性能會迅速退化.3）本文提出的SPGR算法獲得了更好的恢復性能；與LLS、PPCA、LRMC方法相比，在MCAR缺失模式下，RMSE降低了3.02% ～ 22.31%，在MAR缺失模式下，RMSE降低了3.23% ～ 28.49%，在MIXED缺失模式下，RMSE降低了3.05% ～ 21.56%；特別是當缺失率大于30%時，恢復誤差降低率越大，相對于LLS算法誤差降低率高達28.49%，表明該方法可以有效挖掘觀測數據的內在關聯，實現準確的缺失值恢復.

表1 MCAR模式下不同算法的恢復誤差Tab.1 Imputation error of different algorithms in MCAR mode

表2 MAR模式下不同算法的恢復誤差Tab.2 Imputation error of different algorithms in MAR mode

3.3 算法參數的影響

本文提出的SPGR模型涉及3個參數：Schattenp范數的p值、K近鄰（K-nearest neighbor, KNN）方法中的K值、圖正則化的權重常數 λ.p值決定了對矩陣秩函數的近似程度，K值決定了用于重建每個樣本的近鄰數量，λ控制基于局部鄰近的圖正則化的影響.為得到模型參數的最優值，調整其中一個參數，固定另外兩個參數，每次參數改變時記錄實驗結果.以交通流量數據為例，圖5給出了不同參數下，缺失值恢復誤差RMSE的變化.由圖可知：不同缺失率下，p具有不同的最優值，由于Schatten-p范數比核范數（p=1）更能逼近秩函數，從而獲得更好的恢復結果；如果K值過大或過小，都會導致恢復精度較差.這是因為K值太小，選擇代表目標樣本的相鄰樣本過少，導致用于缺失值恢復的可用信息不充分，K值過大，遠離目標的樣本將參與重建，也將降低恢復精度.對于 λ的影響，也可以得出與K值類似的結論.

表3 MIXED模式下不同算法的恢復誤差Tab.3 Imputation error of different algorithms in MIXED mode

圖5 SPGR模型在交通流量數據上的RMSE隨參數 p、K、λ的變化Fig.5 RMSEs of SPGR model on traffic flow data varied with the parameters ofp、K、λ

3.4 初始化影響

根據SPGR算法的第一步，為建立表征樣本間相鄰關系的圖矩陣，需要選擇一種已有的恢復方法對交通數據的缺失值進行初始估計.本節將采用3種不同的初始化方法，即KNN、LLS、LRMC，進行缺失值的初始估計，進而研究其對SPGR算法性能的影響，實現敏感性分析.以交通流數據為例，δ=0.3下的實驗結果如表4所示.可以看出，不同的初始化方法對SPGR的恢復性能影響較小，在其他缺失率下也可以觀察到類似現象.這驗證了SPGR對初始值具有較好的魯棒性.

表4 在交通流量數據上不同初始化方法對SPGR恢復誤差的影響Tab.4 Effect of different initialization methods on SPGR imputation error on traffic flow data 輛/15 min

4 結 論

提出一種融合圖正則化與Schatten-p范數最小化的交通數據缺失值恢復方法.該方法采用Schatten-p范數逼近矩陣的秩函數，對數據的低秩先驗信息進行約束.通過實驗分析，得到以下結論：

1）將圖正則化融入到數據恢復框架中，有利于更好地利用數據的局部鄰近結構.

2）基于真實的高速公路交通量和速度數據進行仿真實驗表明，提出的方法相對于其他多種方法恢復誤差降低了3.02%以上，特別是缺失率大于0.3時，誤差降低率達到20%以上.

3）在未來的工作中，將進一步研究交通數據在時序上的規律性，以提升缺失值恢復的精度.