張量加權(quán)Schatten范數(shù)交通數(shù)據(jù)補(bǔ)全估計(jì)

謝佳鑫，俞衛(wèi)琴

(上海工程技術(shù)大學(xué) 數(shù)理與統(tǒng)計(jì)學(xué)院，上海 201600)

0 引言

隨著智慧交通概念的提出，城市道路上部署了大量的感知器不間斷地采集具有相關(guān)時(shí)間地點(diǎn)信息的交通數(shù)據(jù)，這些數(shù)據(jù)被用來監(jiān)測城市交通運(yùn)行狀態(tài)和進(jìn)行通行時(shí)間預(yù)測等。由于采集到的時(shí)空交通數(shù)據(jù)規(guī)模與維數(shù)越來越大，并且數(shù)據(jù)采集過程中不可避免地發(fā)生數(shù)據(jù)丟失等情況，實(shí)際使用這些原始觀測數(shù)據(jù)時(shí)，難免會受到缺失數(shù)據(jù)的影響，使得數(shù)據(jù)集的有效性降低。數(shù)據(jù)丟失的原因可能是由于傳感器故障或傳輸丟包等設(shè)備因素，也可能是感知器的覆蓋范圍有限造成的。因此，數(shù)據(jù)缺失可分為以下兩種情形：一種是連續(xù)時(shí)間狀態(tài)下，隨機(jī)記錄點(diǎn)的缺失，即隨機(jī)缺失情形；另一種是傳感器不工作狀態(tài)下，此區(qū)間段的數(shù)據(jù)丟失，即非隨機(jī)缺失情形?？梢妼θ笔?shù)據(jù)進(jìn)行合理補(bǔ)全成為交通數(shù)據(jù)應(yīng)用前的關(guān)鍵步驟。

過去的工作中，低秩矩陣補(bǔ)全和低秩張量補(bǔ)全在圖像領(lǐng)域取得了顯著成功[1-2]。由于現(xiàn)實(shí)中大多數(shù)交通數(shù)據(jù)集也具有低秩性，所以可將低秩矩陣/張量補(bǔ)全用于交通數(shù)據(jù)集。Yu等[3]基于車輛軌跡數(shù)據(jù)建立了時(shí)空速度矩陣，使用Schattenp-norm實(shí)現(xiàn)了缺失數(shù)據(jù)矩陣的估計(jì)，并可以用作全市范圍的交通數(shù)據(jù)估計(jì)和流量的動(dòng)態(tài)監(jiān)測。當(dāng)采用矩陣結(jié)構(gòu)來建模交通數(shù)據(jù)時(shí)，矩陣結(jié)構(gòu)無法充分利用數(shù)據(jù)的時(shí)空信息，且在數(shù)據(jù)丟失率較大時(shí)，矩陣方法的恢復(fù)效果就會下降。鑒于交通數(shù)據(jù)與時(shí)間和空間高度相關(guān)，選擇張量結(jié)構(gòu)能很好地保留數(shù)據(jù)的時(shí)空特性。Asif和Tan等[4-5]均提出使用低秩張量補(bǔ)全的方法來解決交通數(shù)據(jù)的估算。鑒于交通數(shù)據(jù)集存在強(qiáng)時(shí)空相關(guān)性(如傳感器在不同天的同一時(shí)間具有相似的讀數(shù)，在不同星期觀察的趨勢也彼此相似)，低秩模型往往能在一定準(zhǔn)確度上對此類數(shù)據(jù)集進(jìn)行建模并恢復(fù)。

在低秩逼近(Low Rank Approximation, LRA)中，核范數(shù)是最典型的低秩約束，其定義為給定矩陣的奇異值之和，即給定矩陣X∈m×n，核范數(shù)同時(shí)核范數(shù)是原始秩最小化問題的最緊凸松弛。對于給定的缺失矩陣Y，核范數(shù)最小化的目標(biāo)是找出一個(gè)低秩矩陣X，滿足以下目標(biāo)函數(shù)：

(1)

總體來說，交通數(shù)據(jù)補(bǔ)全領(lǐng)域多用核范數(shù)相關(guān)方法，于是本研究提出張量加權(quán)Schattenp-范數(shù)最小化(Tensor Weighted Schattenp-Norm Minimization, TWSNM)模型，結(jié)合交替方向乘子法和貝葉斯優(yōu)化算法，用于廣州城市交通數(shù)據(jù)的補(bǔ)全估計(jì)，并給出TWSNM模型的準(zhǔn)確性與有效性。

1 基于低秩張量補(bǔ)全的優(yōu)化模型

1.1 低秩張量補(bǔ)全

低秩張量補(bǔ)全(Low Rank Tensor Completion, LRTC)是張量補(bǔ)全體系中的一個(gè)分支。針對時(shí)空交通數(shù)據(jù)具有低秩結(jié)構(gòu)這一先驗(yàn)假設(shè)，本研究將構(gòu)建1個(gè)三階張量模型。對于缺失張量y∈I×J×K, LRTC模型可以表示為：

(2)

式中，χ∈I×J×K為恢復(fù)完整后的張量；Ω為缺失張量y中已知元素的索引集。rank(·)為指秩函數(shù)。PΩ(·)為投影函數(shù)：

(3)

LRTC模型中秩最小化的問題在計(jì)算上是非常困難的，因此需要尋找一個(gè)合適的凸松弛來逼近秩函數(shù)。常用的方法是利用核范數(shù)來代替秩函數(shù)，即：

(4)

1.2 基于張量的加權(quán)Schatten范數(shù)數(shù)據(jù)補(bǔ)全

首先介紹關(guān)于矩陣的加權(quán)Schattenp-范數(shù)的常用定義。

定義1：矩陣的Schattenp-范數(shù)[20]。給定一個(gè)矩陣X∈m×n和一個(gè)正整數(shù)r

(5)

即：

(6)

式中，σi(X),i=1,2,…,min{m,n}是矩陣X的第i個(gè)奇異值。奇異值的排序?yàn)棣?≥σ2≥…≥σr≥…≥σmin{m,n}≥0。

由于矩陣的Schattenp-范數(shù)定義并不能直接用于多維張量，并且奇異值的大小會對模型產(chǎn)生影響，于是在張量上定義加權(quán)的Schattenp-范數(shù)。

定義2：張量加權(quán)Schattenp-范數(shù)。對于任意d階張量χ，張量加權(quán)Schattenp-范數(shù)定義為：

(7)

由定義2，當(dāng)權(quán)重參數(shù)αk適當(dāng)?shù)脑O(shè)置，每個(gè)張量模態(tài)展開矩陣χ(k)將被分配權(quán)重。現(xiàn)用張量加權(quán)Schattenp-范數(shù)替換式(4)中的標(biāo)準(zhǔn)核范數(shù)，則LRTC模型變形為：

(8)

事實(shí)上，以不同模態(tài)展開的張量不能保證變量的穩(wěn)定性。因此，引入一個(gè)輔助張量δ和一組新的約束，將模型改寫為：

(9)

式中，引入δ是為了保留觀測信息，并將這些信息廣播到變量χk,k=1,2,3，建立輔助變量δ與現(xiàn)有觀測量y之間的關(guān)系。

1.3 算法設(shè)計(jì)

為了解決優(yōu)化式(9)，本研究采用交替方向乘子法(Alternating Direction Method of Multipliers, ADMM)，給出增廣拉格朗日函數(shù)[9，21-22]：

(10)

式中<·,·>為內(nèi)積，τ1,τ2,τ3∈I×J×K為輔助變量，用于ADMM中對偶更新。則式(10)轉(zhuǎn)化為以下3個(gè)子問題：

(11)

(12)

(13)

(14)

考慮到模型的凸性，為使式(14)收斂到期望的全局最優(yōu)解，基于定理1本研究給出引理1，得到封閉形式的最優(yōu)解或者次優(yōu)解。

定理1(Von-Neumann[23])：對于任意m×n矩陣A和B，對應(yīng)的奇異值分別為σ(A)=[σ1(A),σ2(A),…,σr(A)]T，σ(B)=[σ1(B),σ2(B),…,σr(B)]T，r=min{m,n}，可得tr(ATB)≤tr(σ(A)Tσ(B))，當(dāng)且僅當(dāng)同時(shí)找到U,V時(shí)，取得等號。

A=UΣAVTB=UΣBVT,

(15)

式中ΣA,ΣB為有序?qū)瞧娈愔稻仃嚒?/p>

引理1：對于任意α,ρ>0,Z∈m×n,r∈+,r

(16)

(17)

式中foldk(·)為一個(gè)折疊運(yùn)算符，將以k階展開的矩陣再轉(zhuǎn)換為高階張量，即foldk(χ(k))=χ。同理，可以計(jì)算出輔助張量Sl+1。

2 算例分析

2.1 數(shù)據(jù)準(zhǔn)備

從CERN數(shù)據(jù)中心的公開數(shù)據(jù)集中選取廣州城市交通速度數(shù)據(jù)作為試驗(yàn)數(shù)據(jù)集，其時(shí)間跨度為2016年8月1日—2016年9月30日，共61天。從214個(gè)路段收集平均行車速度，時(shí)間窗間隔為10 min，則一天可分為144個(gè)時(shí)間間隔。張量結(jié)構(gòu)為“位置×天×?xí)r間窗”，其大小為214×61×144；展開成矩陣結(jié)構(gòu)時(shí)為“位置×?xí)r間”，其大小為214×8 784,數(shù)據(jù)的缺失率為1.29%。

2.2 對比模型

本研究選取以下模型與提出的TWSNM模型進(jìn)行比較：

(1)HaLRTC：高精度低階張量補(bǔ)全[7]。其為低秩補(bǔ)全模型，使用核范數(shù)最小化估計(jì)缺失數(shù)據(jù)。

(2)LRTC-TNN：截?cái)嗪朔稊?shù)張量補(bǔ)全[9]。其為低秩補(bǔ)全模型，使用截?cái)嗟暮朔稊?shù)來估計(jì)缺失數(shù)據(jù)。

(3)BGCP：貝葉斯高斯CP分解[11]。其為全貝葉斯高斯張量分解模型，使用馬爾可夫鏈蒙特卡洛方法來學(xué)習(xí)低秩結(jié)構(gòu)。

2.3 試驗(yàn)設(shè)定

為了評估模型表現(xiàn)，將已觀察到的數(shù)據(jù)掩蓋為“缺失”數(shù)據(jù)。采用兩種數(shù)據(jù)缺失模式，即隨機(jī)缺失(Random Missing, RM)和非隨機(jī)缺失(Non-random Missing, NM)，對這些“缺失”數(shù)據(jù)進(jìn)行逼近估計(jì)。選取平均百分比誤差(Mean Absolute Percentage Error, MAPE)和均方根誤差(Root Mean Square Error, RMSE)作為評價(jià)指標(biāo)：

(18)

(19)

其中非隨機(jī)缺失情形更具有挑戰(zhàn)性，數(shù)據(jù)會被嚴(yán)重破壞。

3 試驗(yàn)結(jié)果

在隨機(jī)缺失(RM)和非隨機(jī)缺失(NM)兩種數(shù)值缺失模式下，通過可視化搜索過程研究參數(shù)和模型的關(guān)系。橫坐標(biāo)為各參數(shù)的數(shù)值，縱坐標(biāo)為RMSE值。通過圖1中展示的散點(diǎn)分布，可以看到TWSNM模型尋優(yōu)過程中的趨勢。在非隨機(jī)缺失模式中，散點(diǎn)的分布要多于隨機(jī)缺失模式，可以理解為在非隨機(jī)缺失模式下算法需要進(jìn)行更多的嘗試，這一表現(xiàn)也符合現(xiàn)實(shí)邏輯。當(dāng)點(diǎn)從均勻分布到集中在某一塊區(qū)域，表明優(yōu)化算法開始是在整個(gè)范圍中均勻選擇參數(shù)值，來學(xué)習(xí)目標(biāo)值整體分布，最后找到最優(yōu)分布區(qū)域和最優(yōu)值。

圖1 TWSNM模型在兩種數(shù)值缺失模式下參數(shù)尋優(yōu)過程

針對廣州城市交通速度數(shù)據(jù)集，表1總結(jié)了4個(gè)模型的數(shù)據(jù)插補(bǔ)性能，其中BGCP屬于張量分解，HaLRTC、LRTC-TNN以及TWSNM模型屬于低秩框架下的插補(bǔ)模型。

表1 基于MAPE/RMSE指標(biāo)的數(shù)據(jù)補(bǔ)全性能對比

由圖2，可以看出TWSNM在隨機(jī)缺失場景下各個(gè)缺失率中的指標(biāo)表現(xiàn)都優(yōu)于其他插補(bǔ)模型。隨著缺失率上升，MAPE和RMSE也在上升。與隨機(jī)缺失場景相比，非隨機(jī)缺失場景更具挑戰(zhàn)性。結(jié)果顯示，在60%非隨機(jī)缺失率之前，TWSNM模型僅次于低秩框架下的LRTC-TNN模型，但兩者之間的差異非常小，RMSE相差0.2左右，說明TWSNM模型依然具有競爭性。在60%～80%缺失率的區(qū)間，TWSNM模型要優(yōu)于其他模型，而此時(shí)LRTC-TNN模型的波動(dòng)較大，變得不穩(wěn)定，從而反映出TWSNM模型具有魯棒性。在90%缺失率時(shí)貝葉斯模型顯示出一定優(yōu)勢。

圖2 在不同缺失率情形下MAPE/RMSE的對比圖

本研究選取4個(gè)不同路段，分別在缺失率20%，50%和80%場景下，展示TWSNM模型補(bǔ)全后的時(shí)間序列數(shù)據(jù)與實(shí)際時(shí)間序列數(shù)據(jù)的比較，如圖3所示。圓點(diǎn)表示實(shí)際時(shí)間序列數(shù)據(jù)，線條表示TWSNM模型補(bǔ)全后的時(shí)間序列數(shù)據(jù)。能看出線條可以基本覆蓋圓點(diǎn)數(shù)據(jù)點(diǎn)，即使在缺失率大的場景下，也能做到趨勢吻合。可見TWSNM模型可以進(jìn)行高質(zhì)量的數(shù)據(jù)補(bǔ)全估計(jì)。

圖3 實(shí)際時(shí)間序列數(shù)據(jù)與TWSNM模型估計(jì)序列數(shù)據(jù)對比

4 結(jié)論

缺失交通數(shù)據(jù)的補(bǔ)全可以提高數(shù)據(jù)的利用率。本研究提出了一種基于非凸最小化的低秩張量補(bǔ)全模型——TWSNM模型，結(jié)合交替方向乘子法和貝葉斯優(yōu)化算法來估計(jì)廣州城市交通數(shù)據(jù)集中的缺失值。試驗(yàn)表明，TWSNM模型在隨機(jī)缺失場景中不同缺失率情況下的表現(xiàn)都優(yōu)于其他插補(bǔ)模型；在非隨機(jī)缺失場景中低缺失率情形下TWSNM模型的表現(xiàn)與其他模型相比具有競爭性，在高缺失率情形下也有較好的表現(xiàn)并具有魯棒性。可見TWSNM模型對實(shí)際缺失交通數(shù)據(jù)具有很好的補(bǔ)全效果。