基于譜分析的路段行程時間多步預(yù)測方法

鄧明君，曲仕茹，秦鳴

（1.西北工業(yè)大學(xué)自動化學(xué)院，西安710072；2.華東交通大學(xué)土建學(xué)院，南昌330013）

基于譜分析的路段行程時間多步預(yù)測方法

鄧明君*1，2，曲仕茹1，秦鳴2

（1.西北工業(yè)大學(xué)自動化學(xué)院，西安710072；2.華東交通大學(xué)土建學(xué)院，南昌330013）

路段多步行程時間預(yù)測數(shù)據(jù)是動態(tài)交通誘導(dǎo)系統(tǒng)的重要參數(shù)，但已有研究成果，大多集中于一步預(yù)測，且存在適應(yīng)性不強(qiáng)、計算量大、基礎(chǔ)數(shù)據(jù)需求多等不足.應(yīng)用譜分析及Karhunen-Loeve（K-L）變換對歷史及當(dāng)前檢測行程時間序列進(jìn)行分解與重構(gòu)，重構(gòu)時以歷史序列與當(dāng)前檢測序列的歐式距離作為相似性度量指標(biāo)，優(yōu)化重構(gòu)時的特征向量系數(shù)，使與當(dāng)前檢測序列相似度高的歷史序列信息在重構(gòu)中占據(jù)主要地位，通過重構(gòu)，實(shí)現(xiàn)對后續(xù)若干時段的行程時間的預(yù)測，實(shí)測數(shù)據(jù)檢驗(yàn)顯示該方法可實(shí)現(xiàn)多步預(yù)測，預(yù)測精度良好，較以往方法有所提高，且歷史數(shù)據(jù)需求量小，計算量小.

城市交通；行程時間；多步預(yù)測；Karhunen-Loeve變換；時間序列重構(gòu)

1 引言

路段行程時間是交通誘導(dǎo)方案生成的重要基礎(chǔ)參數(shù)，但道路上的交通狀態(tài)瞬息萬變，直接用當(dāng)前檢測數(shù)據(jù)制定下一時刻的交通管控方案，會產(chǎn)生方案滯后于實(shí)際交通狀態(tài)的結(jié)果.若預(yù)先估算出將來某個時段的路段行程時間，并以此制定誘導(dǎo)方案，則方案的實(shí)時性提高，有利于合理選擇出行路徑.當(dāng)前該方向的成果大致分為兩類，一類是基于統(tǒng)計的方法，如非參數(shù)回歸、卡爾曼濾波和小波模型.第二類為智能學(xué)習(xí)模型,如模糊預(yù)測、遺傳算法和神經(jīng)網(wǎng)絡(luò)等[1，2].但這些方法均存在無法體現(xiàn)交通流的動態(tài)性，需要?dú)v史數(shù)據(jù)量大，具有一定的滯后性等不足,且這些模型多以單步預(yù)測為主，盡管文獻(xiàn)[3，4]提出了2種行程時間多步預(yù)測方法，但這兩種方法仍然存在預(yù)測值滯后、數(shù)據(jù)需求量大的缺憾.

信息理論中的頻譜分析方法可以揭示隱含在隨機(jī)序列中的趨勢信息，從而實(shí)現(xiàn)對隨機(jī)信號的估計.1974年Nicholson[5]，第一次將譜分析法應(yīng)用于交通流量預(yù)測，他將隨機(jī)流量序列表示為若干正交向量的線性組合，用最小二乘法確定組合系數(shù)，建立了流量預(yù)測模型.雖然這一方法具有較高的預(yù)測精度，但需實(shí)時修正組合系數(shù)，計算量大，應(yīng)用困難，文獻(xiàn)[6]將該方法程序化，并能夠完成多步預(yù)測，但該方法沒考慮歷史數(shù)據(jù)與當(dāng)前數(shù)據(jù)間的相關(guān)性，信息挖掘不充分，文獻(xiàn)[6]的驗(yàn)證結(jié)果顯示，平均一步預(yù)測誤差為11%.進(jìn)一步研究歷史數(shù)據(jù)與當(dāng)前數(shù)據(jù)的相關(guān)性可能是提升譜分析預(yù)測精度的一個思路.本文在文獻(xiàn)[5，6]基礎(chǔ)上，通過優(yōu)化特征向量系數(shù)，使歷史序列中，更符合當(dāng)前交通變化趨勢的序列在預(yù)測中得到更多的權(quán)重表達(dá)，并采用時間窗滾動方法實(shí)現(xiàn)多步預(yù)測.

2 譜分析原理

譜分析方法是將隨機(jī)序列分解為不同振幅、相位、頻率的序列組合，通過分解發(fā)現(xiàn)隨機(jī)序列的主要變化規(guī)律，從而實(shí)現(xiàn)對隨機(jī)序列的估計.應(yīng)用于譜分析的變換有多種，其中離散Karhunen-Loeve (K-L)變換是以隨機(jī)序列統(tǒng)計特征為基礎(chǔ)的在均方意義下為最佳的正交變換.該變換只要較少個數(shù)的系數(shù)就能恢復(fù)出精度不錯的原隨機(jī)序列.

將M維間隔為k,k=1,2,…,N的離散隨機(jī)序列定義為

式中xm(k)表示M維序列中第m個序列在第k個時間間隔時的值；em(k)為該時刻的誤差；φi(k)為一組正交向量；cmi為對應(yīng)的正交向量系數(shù).

由于K-L變換的能量集中性，式（1）中i的取值可做K步截斷,i=1,2,…,K.即在有限的K項(xiàng)分解下，式（1）右側(cè)就可很好地逼近xm(k).

式（1）中正交向量有如下性質(zhì)：

式中δij為Kronecker對角陣.

將式（1）用向量表示：

因?yàn)棣誘φ=I，可得特征向量系數(shù)矩陣：

C中的每一個元素相互獨(dú)立，且對應(yīng)于用于預(yù)測的互不相關(guān)的一個基.Davenport[7]發(fā)現(xiàn)可以用離散形式的K-L積分方程來表示隨機(jī)序列協(xié)方差矩陣的分解，如式（6）所示.

式（6）求得特征向量矩陣φ及對應(yīng)的特征根λ，將λ由大到小排列，由K-L變換能量集中性，用部分較大特征根對應(yīng)的特征向量，通過重構(gòu)便能恢復(fù)出隨機(jī)序列的主要信息.將不同時段檢測的路段行程時間看作是一組隨機(jī)序列X，求得系數(shù)C后，結(jié)合特征向量矩陣φ，由式（3）可反求時間序列Xˉ.上述方法能夠?qū)崿F(xiàn)對歷史數(shù)據(jù)序列的再現(xiàn)，但預(yù)測問題不是歷史數(shù)據(jù)的重現(xiàn)，而是要從歷史數(shù)據(jù)中挖掘出對預(yù)測有用的信息以指導(dǎo)預(yù)測.路段交通特性顯示，同一路段相同工作日的交通特性具有相似性，因此融合歷史數(shù)據(jù)序列的相似性，則有可能得出符合當(dāng)前數(shù)據(jù)變化規(guī)律的結(jié)果.

3 基于譜分析的多步行程時間預(yù)測方法

3.1 基于譜分析法行程時間預(yù)測的優(yōu)化思路

統(tǒng)計歷史上某道路某工作日IT分鐘間隔的平均行程時間序列值，全天共計組數(shù)據(jù)，連續(xù)統(tǒng)計S周，獲得一個S×F的矩陣，由式（5）～式（7）求得S×K維的系數(shù)矩陣Ch及對應(yīng)的特征向量矩陣φ.用當(dāng)前檢測序列構(gòu)造一個新序列Xc用以計算當(dāng)前序列特征向量系數(shù)Cc，Xc=(T1,T2,…,Tt,Tt+1,Tt+2,…,Tt+b)，其中，T1～Tt為當(dāng)前檢測序列，Tt+1～Tt+b為對應(yīng)時刻歷史序列均值，由式（5）求得1×K維系數(shù)向量Cc，將Ch與Cc加權(quán)合并，得1×K維系數(shù)加權(quán)和向量Cv，Cv=WC，其中，W為組合權(quán)重向量.優(yōu)化組合權(quán)重便可達(dá)到歷史數(shù)據(jù)、當(dāng)前檢測數(shù)據(jù)最優(yōu)融合的目的.

3.2 cv合成時的權(quán)值優(yōu)化

ch蘊(yùn)含了該序列的波動信息，為預(yù)測準(zhǔn)確，那些與當(dāng)前序列波動更為相似的序列應(yīng)提供更多信息，為體現(xiàn)這一原則，以當(dāng)前序列與對應(yīng)歷史序列值之間的歐氏距離來描述其相似性.設(shè)當(dāng)前檢測值與各歷史序列對應(yīng)值的歐氏距離為d(i)，則Ch中各行的權(quán)重向量：

假設(shè)在一個適當(dāng)?shù)臅r段內(nèi)，當(dāng)前檢測序列與歷史綜合序列對待估序列的影響權(quán)重具有延續(xù)性，則可以通過回朔當(dāng)前已檢測的若干連續(xù)時段的預(yù)測值與其對應(yīng)檢測值的誤差平方和最小來確定α，而在下一步預(yù)測中延續(xù)這種組合，并在每次獲得檢測值后，計算預(yù)測誤差，當(dāng)預(yù)測誤差超過設(shè)定閾值ε后，則重新優(yōu)化α，設(shè)回朔時段為a,得優(yōu)化問題模型.

結(jié)合式（9）的條件，構(gòu)成一個帶約束的二次優(yōu)化問題，決策變量為α，對于二次優(yōu)化問題求解，一類方法是消去約束，用數(shù)值計算方法求解，另一類方法是采用智能計算方法求解.數(shù)值計算法對目標(biāo)函數(shù)及約束條件要求嚴(yán)格，某些時候可能無法求解，而智能計算方法不基于理論推導(dǎo)，求解條件相對寬松，給定學(xué)習(xí)終止條件，總可以在給定區(qū)域找到最優(yōu)或局部最優(yōu)解，因此本研究采用粒子群算法，以式（10）目標(biāo)函數(shù)為適應(yīng)度函數(shù)，約束條件為粒子的取值范圍，用式（12）對粒子的速度和位置進(jìn)行更新，并設(shè)定終止迭代條件，當(dāng)前后兩次迭代的差值小于某一個給定閾值θ，或迭代次數(shù)達(dá)到某設(shè)定閾值G，則終止迭代，輸出α的優(yōu)化值.

計算步驟：

Step 1隨機(jī)生成滿足約束條件的一定數(shù)量的粒子個體；

Step 2依據(jù)目標(biāo)函數(shù)，計算每個粒子的適應(yīng)度，并更新每個粒子歷史最優(yōu)適應(yīng)度值對應(yīng)的位置信息及全局最優(yōu)適應(yīng)度粒子對應(yīng)的位置信息；

Step 3依據(jù)式（12）對各粒子的速度和位置進(jìn)行更新；

Step 4轉(zhuǎn)至Step2，并判斷是否終止，以輸出最優(yōu)值；

Step 5得出α最優(yōu)值，由式（9）計算Cv，并進(jìn)行下一步預(yù)測計算.

3.3 多步預(yù)測及滾動

距離當(dāng)前時間越近的時段，其之間的相關(guān)性越強(qiáng)，為減少不必要的計算，在多步預(yù)測中，只考慮當(dāng)前時段之前的a個時段及之后的b個時段的數(shù)據(jù)，通過對特征向量矩陣φ的滾動來實(shí)現(xiàn)這一目標(biāo).即在求特征向量系數(shù)Ch和Cc時，選取特征向量

3.4 預(yù)測方法應(yīng)用流程

通過上述分析，總結(jié)基于譜分析的行程時間多步預(yù)測流程如下：

（1）給定回朔時段a和預(yù)測步數(shù)b,讀入S天同一工作日的歷史序列矩陣X，求其協(xié)方差矩陣及特征根和特征向量.

（2）以歷史序列計算特征向量系數(shù)Ch.

（3）依據(jù)各天歷史序列與當(dāng)前檢測序列的歐式距離計算組合特征向量系數(shù)Ctmp，用當(dāng)前檢測序列計算Cc.

（4）根據(jù)前一步預(yù)測誤差e是否超過誤差閾值ε，確定是否需要更新α，是則轉(zhuǎn)（5），否則轉(zhuǎn)（6）.

（5）用粒子群算法確定回朔時段內(nèi)Cc與Ctmp的組合權(quán)重α.

（6）用α和Cc、Ctmp計算最終特征向量系數(shù)Cv.

（8）計算預(yù)測誤差e，時間推進(jìn)一步，轉(zhuǎn)（3）.

4 驗(yàn)證分析

利用南昌市洪都大橋連續(xù)六周，星期二的行程時間作為驗(yàn)證數(shù)據(jù)，行程時間為檢測間隔內(nèi)通過檢測路段所有車輛行程時間的均值.關(guān)于檢測時間間隔大小，對預(yù)測精度也有一定影響，當(dāng)間隔較短時，序列的波動性變大，而對于波動性較大的序列，預(yù)測時需要準(zhǔn)確描述其高頻特性，因此在相同精度條件下需要更多特征向量來重建，即需要更大的截斷值K,從而增加計算量.文獻(xiàn)[6]驗(yàn)證，當(dāng)間隔為15m in時，譜分析法的綜合性能最好，因此用15m in間隔行程時間數(shù)據(jù)進(jìn)行驗(yàn)證.其中前五周的數(shù)據(jù)作為歷史數(shù)據(jù)，第六周的數(shù)據(jù)為檢驗(yàn)數(shù)據(jù).分別選取不同回朔時段a及預(yù)測步長b進(jìn)行預(yù)測，選取平均相對誤差、均方根相對誤差作為評價指標(biāo)分析預(yù)測效果.在Matlab平臺上，實(shí)現(xiàn)本文方法，輸出的各指標(biāo)如表1所示.

表1 不同時間窗下預(yù)測的相對誤差與均方根誤差Table 1 EPMR and ERR ofsome difference time w indow w idth

分析可見，當(dāng)回朔時段數(shù)是2時，各指標(biāo)數(shù)據(jù)相對較好，繪制回朔時段為2的多步預(yù)測曲線，為使各線條清晰，只繪制1～3步及實(shí)測值等四條曲線.

利用本次檢測數(shù)據(jù)，應(yīng)用文獻(xiàn)[6]方法預(yù)測，就預(yù)測平均相對誤差、均方根相對誤差與本文方法進(jìn)行對比，如表2所示.

圖1 1～3步預(yù)測與實(shí)測值對比圖Fig.1 Comparison chartof1～3 step forecastingand detection

表2 本文方法與文獻(xiàn)[6]方法預(yù)測效果對比表Table 2 The performance of this describes and reference[6]

由表2可知，本文方法預(yù)測結(jié)果略好于文獻(xiàn)[6]方法，說明應(yīng)用歐式距離進(jìn)行權(quán)重優(yōu)化，可提高譜分析方法在時間序列預(yù)測時的精度.

分析相對誤差分布，分別以5%、10%、20%、30%、40%、60%、100%作為統(tǒng)計區(qū)間，累計誤差分布數(shù)，如表3所示.

表3 各步預(yù)測誤差統(tǒng)計表Table 3 The statistics ofeach step prediction

表3顯示，各步長預(yù)測誤差在10%以內(nèi)的時刻分別占了總時刻數(shù)的70.83%、65.63%、63.54%.1～4步預(yù)測中，本方法60%以上的時刻，各步預(yù)測誤差均小于10%，對于隨機(jī)性很強(qiáng)的交通系統(tǒng)來說，10%以內(nèi)的誤差基本可以滿足交通控制及誘導(dǎo)需求.

5 研究結(jié)論

將譜分析中的分解與重構(gòu)思想應(yīng)用于短時行程時間預(yù)測，僅需要較少的對應(yīng)時段的歷史數(shù)據(jù)，計算效率高，且能實(shí)現(xiàn)多步預(yù)測.從預(yù)測精度來看，一步預(yù)測的相對誤差為8.51%，三步預(yù)測的相對誤差為9.58%，從預(yù)測誤差分布來看，四步以內(nèi)，60%以上的預(yù)測值，誤差在10%以內(nèi).與當(dāng)前短時交通預(yù)測方法相比,譜分析方法不存在卡爾曼濾波等線性估計方法預(yù)測值滯后的不足，也沒有神經(jīng)網(wǎng)絡(luò)等智能學(xué)習(xí)方法所必須的大量訓(xùn)練和預(yù)測精度受泛化性能影響的局限，具有較好的綜合實(shí)用價值，當(dāng)然該方法也存在一些弱點(diǎn)，如在求協(xié)方差矩陣的特征向量和特征根時，如果維度過高則求解困難，甚至無解，所以該方法的序列劃分長度不能太長.

參考文獻(xiàn)：

[1]G A Davis,N L Nihan.Nonparametric regression and short-term freeway traffic forecasting[J].J.Transp.Eng., 1991,117(2):178-188.

[2]張玉梅，曲仕茹，溫凱歌.基于混沌和RBF神經(jīng)網(wǎng)絡(luò)的短時交通流量預(yù)測[J].系統(tǒng)工程，2007,25(11):26-32. [ZHANG YM，QU SR，WEN K G.A short-term traffic flow forecastingmethod based on chaos and rbf neural network[J].Systems Engineering,2007,25(11):26-32.]

[3]李進(jìn)燕,朱征宇,劉琳.基于簡化路網(wǎng)模型的卡爾曼濾波多步行程時間預(yù)測方法[J].系統(tǒng)工程理論與實(shí)踐, 2013，33（5）:1289-1297.[Ll JY,ZHU ZY,etal.Multi step Kalman filtering travel time estimation method based on simplified road network model[J].Systems Engineer Theory&Practice,2013,33(5):1289-1297.]

[4]李琦,姜桂艷.SCATS線圈數(shù)據(jù)短時多步雙重預(yù)測方法[J].哈爾濱工業(yè)大學(xué)學(xué)報,2 013,45(2):123-128.[LIQ,JIANG G Y，Bi-levelmethod ofmulti-step forecasting for short-term data of loop in SCATS[J]. Journal of Harbin Institute of Technology,2013,45(2): 123-128.]

[5]H Nicholson,C D Swann.The prediction of traffic flow volumes based on spectral analysis[J].Transport Res., 1974,8:533-538.

[6]Tigran T Tchrakian,Biswajit Basu,et al.Real-time traffic flow forecasting using spectral analysis[J].Ieee Transactions on Intelligent Transportation Systems, 2012,13(2):519-526.

[7]W BDavenport,W LRoot.An introduction to the theory of random signals and noise[M].New York:McGraw-Hill,1958.

SpectralAnalysis App lied in Road Travel Time MultiStep Prediction

DENGM ing-jun1,2,QU Shi-ru1，QINm ing2

（1.Schoolof Automatic Control,Northwestern PolytechnicalUniversity,Xi′an 710072,China；2.Schoolof CivilArchitecture, EastChina Jiaotong University,Nanchang 330013,China）

Road multi interval travel time forecasting data is an important parameter for dynam ic traffic guidance system.But previously developed models have some deficiency,such as bad adaptability,large amountof calculation needing andmany history data requirement.Applied the decomposition,reconstruction of spectral analysis and Karhunen-Loeve(K-L)transform method to decompose and reconstruct the history and currentdetection travel time series.Euclidean distance is used tomeasure the closeness between current and historical travel time series,by themeans of optim ization the eigenvector coefficient tomake thosemore closely history series has themore weight in the reconstruction and then gain the goal of road travel time multi step forecasting.The case study suggest that,the proposed method can fulfillmulti step road travel time prediction and has a good prediction accuracy,some better than the previousmethod,furthermore,a fewerhistory dataand calculation resourcesneeding.

urban traffic；travel time；multi-step prediction；Karhunen-Loeve transform；time series reconstruction

1009-6744（2015）03-0134-06

U491.4

A

2014-09-16

2015-04-30錄用日期：2015-05-04

江西省自然科學(xué)基金（20142BAB201015）；江西省科技廳科技計劃項(xiàng)目（20123BBE50094）.

鄧明君（1978-），男，陜西略陽人，講師，博士.＊通信作者：dmstd98@163.com