基于HALRTC理論的短時交通流預(yù)測算法

教欣萍，王江鋒*，陳磊，高志軍，董佳寬，黃海濤，葉勁松

(1.北京交通大學(xué) 交通運輸學(xué)院 綜合交通運輸大數(shù)據(jù)應(yīng)用技術(shù)交通運輸行業(yè)重點實驗室，北京 100044;2.交通運輸部科學(xué)研究院，北京 100029)

智能交通協(xié)同誘導(dǎo)技術(shù)為有效改善高速公路出行服務(wù)水平提供了有力支撐，作為其中關(guān)鍵技術(shù)的短時交通流預(yù)測，可實現(xiàn)交通流態(tài)勢實時預(yù)估，為出行者提供更可靠的出行路徑參考方案。但是，交通流蘊含的不同時間維度信息對其短時預(yù)測結(jié)果具有顯著影響[1-2]。

目前，短時預(yù)測方法多考慮交通流低維信息，易使其信息丟失導(dǎo)致無法滿足預(yù)測精準(zhǔn)度的要求。國內(nèi)外學(xué)者陸續(xù)將卡爾曼濾波理論、K近鄰法、ARIMA模型等用于短時交通流預(yù)測[3-5]。文獻(xiàn)[6-9]基于卡爾曼濾波方法、K近鄰法提出一些改進(jìn)算法用于優(yōu)化預(yù)測性能；文獻(xiàn)[10-14]基于小波分析、高斯回歸過程、分形理論、突變理論、混沌理論等方法進(jìn)行了短時交通流預(yù)測；神經(jīng)網(wǎng)絡(luò)具有高度非線性的動力學(xué)系統(tǒng)，有強大的非線性擬合能力，文獻(xiàn)[15-18]將神經(jīng)網(wǎng)絡(luò)方法應(yīng)用于短時交通流預(yù)測，其中BP神經(jīng)網(wǎng)絡(luò)應(yīng)用最為廣泛；隨著組合模型的廣泛運用，文獻(xiàn)[19-21]將多種模型組合應(yīng)用于短時交通流預(yù)測。傳統(tǒng)短時交通流預(yù)測算法大多將交通流數(shù)據(jù)視為一維時間序列，這種線性或平面數(shù)據(jù)表征方法忽略了交通流數(shù)據(jù)在多時間維度的信息挖掘，難以有效利用交通流數(shù)據(jù)的內(nèi)部結(jié)構(gòu)性和規(guī)律性。

近年來，張量作為一種高階數(shù)據(jù)空間的多重線性映射模型，可以深層挖掘數(shù)據(jù)內(nèi)部結(jié)構(gòu)與規(guī)律，已經(jīng)成為大數(shù)據(jù)處理領(lǐng)域的研究熱點[22]，國內(nèi)外學(xué)者在張量理論研究方面積累了良好的研究基礎(chǔ)[23-25]。由于交通流數(shù)據(jù)在不同時間維度上具有很強的規(guī)律性，為張量理論應(yīng)用于短時交通流預(yù)測提供了理論基礎(chǔ)。本文基于實際交通流速度數(shù)據(jù)，挖掘其在不同時間維度的規(guī)律特征，建立基于高精度低秩張量填充(high accuracy low-rank tensor completion，HALRTC)理論的短時交通流預(yù)測算法，提升短時交通流預(yù)測的預(yù)測效果與精度。

1 動態(tài)張量矩陣構(gòu)建

為了充分挖掘交通流數(shù)據(jù)在不同時間維度上的規(guī)律性，實現(xiàn)滾動式數(shù)據(jù)輸入預(yù)測未來時間段交通狀態(tài)，將短時交通流預(yù)測問題轉(zhuǎn)化為動態(tài)張量填充問題。以京港澳高速公路杜家坎路段2017年4月至6月共10周的速度數(shù)據(jù)為例，構(gòu)建了周維度×天維度×?xí)r段維度的三維動態(tài)張量矩陣模型，如圖1所示。實際交通流數(shù)據(jù)從每日零點開始采集，每5 min為一時段，一天共采集288個時段數(shù)據(jù)。

圖1 動態(tài)張量模型示意圖

2 短時交通流預(yù)測算法

結(jié)合圖1構(gòu)建的動態(tài)張量矩陣模型，設(shè)計基于HALRTC理論的短時交通流預(yù)測算法。該算法按照運算邏輯，包括算法函數(shù)確定、增廣拉格朗日函數(shù)轉(zhuǎn)換和迭代求解3個步驟，即可獲得短時交通流的預(yù)測結(jié)果。

2.1 算法函數(shù)

設(shè)A為由交通流速度數(shù)據(jù)構(gòu)成的三維動態(tài)張量，大小為I1×I2×I3。同樣設(shè)置大小為I1×I2×I3的非負(fù)權(quán)重張量W，權(quán)重張量中元素賦值如下：

(1)

引入3個相同大小的三維張量M1、M2及M3，則算法函數(shù)可定義為張量核范數(shù)最小化問題：

(2)

式中，M1(1)為M1按模式I1×(I2I3)展開所得數(shù)值矩陣，同理M2(2)、M3(3)為M2、M3按模式I2×(I1I3)、(I1I2)×I3展開所得數(shù)值矩陣。參數(shù)α1、α2及α3滿足α1+α2+α3=1，實際運算中3個參數(shù)常取相等數(shù)值。

2.2 增廣拉格朗日函數(shù)

對算法函數(shù)進(jìn)行推導(dǎo)，可得其增廣拉格朗日函數(shù)如下：

(3)

式中，Y1、Y2、Y3為額外變量，參數(shù)ρ隨迭代次數(shù)而逐漸增加，通常設(shè)ρ0=ρ，有ρk+1=tρk，t∈[1.15,1.25]。

借助交替方向乘子法思路，可對式(3)進(jìn)行迭代：

(4)

(5)

(6)

交替方向乘子法可確保增廣拉格朗日函數(shù)中迭代過程的收斂性，加快參數(shù)迭代計算過程。

2.3 迭代求解

對于M1、M2及M3，每次更新有如下優(yōu)化問題：

(7)

通過奇異值收縮算子計算可得式(7)的閉形式解為：

(8)

(9)

由一階最優(yōu)性條件可得其解為：

(10)

則N階張量X∈RI1×I2×…×IN的HALRTC算法函數(shù)與增廣拉格朗日函數(shù)可描述為：

(11)

s.t.X=Mi,i=1,…，n，

(12)

圖2 HALRTC預(yù)測算法邏輯流程圖

3 實例分析

利用京港澳高速公路杜家坎路段2017年4月至6月速度數(shù)據(jù)對所提出HALRTC算法進(jìn)行實證分析，分別進(jìn)行天維度、周維度預(yù)測精度分析，以及缺失數(shù)據(jù)下該算法與其他經(jīng)典算法的精度對比分析。

3.1 天維度預(yù)測精度

針對天維度，分析算法在周維度與時段維度預(yù)測精度的變化規(guī)律，選擇平均絕對誤差(mean absolute error，MAE)為評價指標(biāo)。圖3為不同周維度、時段維度下第10周周一交通流速度預(yù)測精度結(jié)果。從時段維度上看，預(yù)測精度隨著時段維度的增大而增大，在時段維度為18或20時預(yù)測精度呈現(xiàn)平面狀態(tài)，MAE指標(biāo)穩(wěn)定在2.8%左右；從周維度上看，MAE在周維度大于6后表現(xiàn)出略微增長趨勢，說明所提出預(yù)測算法能夠基于較少歷史數(shù)據(jù)較快達(dá)到良好的預(yù)測效果。

圖3 天維度預(yù)測精度變化趨勢

3.2 周維度預(yù)測精度

針對周維度，分析算法在同周不同日的預(yù)測精度。表1為不同周維度、時段維度下第11周共計7 d的速度數(shù)據(jù)預(yù)測精度結(jié)果，MAE指標(biāo)平均值約為3.6%。其中非工作日預(yù)測精度較低，說明當(dāng)速度數(shù)據(jù)波動加大時，所提出算法需要更多歷史數(shù)據(jù)才能獲得良好預(yù)測效果。

表1 算法第11周速度預(yù)測精度結(jié)果

為深入分析速度數(shù)據(jù)波動較大時所提出預(yù)測算法的預(yù)測性能，分別選取第11周周四與周日作為分析對象，算法的預(yù)測精度結(jié)果如圖4所示。結(jié)果表明，當(dāng)出現(xiàn)明顯速度波動時，所提出算法依然能夠有效預(yù)測速度波動，即使在速度波動頻繁的周日，算法也能取得良好的預(yù)測效果，成功實現(xiàn)對兩個速度高峰時期的曲線跟蹤。

圖4 算法針對速度波動的預(yù)測結(jié)果

3.3 缺失數(shù)據(jù)下預(yù)測算法精度對比分析

針對不同比例缺失數(shù)據(jù)，分析所提出短時交通流預(yù)測算法的精度變化情況。表2給出了不同比例缺失數(shù)據(jù)情況下所提出算法的預(yù)測精度結(jié)果，預(yù)測精度隨缺失數(shù)據(jù)比例增大而呈現(xiàn)下降趨勢，說明所提出算法對數(shù)據(jù)缺失較為敏感，在短時交通流預(yù)測時也會對數(shù)據(jù)完整性有一定要求。對缺失數(shù)據(jù)進(jìn)行預(yù)處理后，所提出算法的預(yù)測精度得到大幅提升。

表2 缺失數(shù)據(jù)下所提出算法預(yù)測精度結(jié)果

選擇ARIMA、BPNN和KNN作為比較算法，進(jìn)一步分析不同比例數(shù)據(jù)缺失情況下所提出算法的預(yù)測性能。為保證算法預(yù)測結(jié)果的有效性，利用不同比例缺失數(shù)據(jù)分別進(jìn)行4種算法預(yù)測性能測試，重復(fù)進(jìn)行10次，測試結(jié)果的MAE指標(biāo)平均值如圖5所示。隨著數(shù)據(jù)缺失比例增大，4種算法的預(yù)測精度均有所下降。相比較而言，本算法的預(yù)測效果較好，明顯低于其他3種經(jīng)典算法的預(yù)測誤差,算法表現(xiàn)出更好的預(yù)測精度。

圖5 缺失數(shù)據(jù)下4種算法預(yù)測精度結(jié)果

4 結(jié)論

針對交通流所蘊含的不同時間維度信息特征，本文從周維度×天維度×?xí)r段維度構(gòu)建了動態(tài)張量模型，提出一種基于HALRTC理論的短時交通流預(yù)測算法。所提出算法可實現(xiàn)針對工作日與非工作日的交通流有效預(yù)測，MAE指標(biāo)平均值約為3.6%，并能及時跟蹤交通流波動性。在缺失數(shù)據(jù)情況下，所提出算法預(yù)測精度隨數(shù)據(jù)缺失比例增大而降低，但相較于3種經(jīng)典預(yù)測算法可表現(xiàn)出更好的預(yù)測精度。本文的算法效率有待提高，同時選取的路況比城市道路簡單，未來可以將HALRTC理論應(yīng)用于城市道路并改進(jìn)算法的效率。