鄧明君，曲仕茹，秦鳴

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

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

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

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

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

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

1 引言

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

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

2 譜分析原理

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

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

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

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

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

式中δij為Kronecker對(duì)角陣.

將式（1）用向量表示：

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

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

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

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

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

統(tǒng)計(jì)歷史上某道路某工作日IT分鐘間隔的平均行程時(shí)間序列值，全天共計(jì)組數(shù)據(jù)，連續(xù)統(tǒng)計(jì)S周，獲得一個(gè)S×F的矩陣，由式（5）～式（7）求得S×K維的系數(shù)矩陣Ch及對(duì)應(yīng)的特征向量矩陣φ.用當(dāng)前檢測(cè)序列構(gòu)造一個(gè)新序列Xc用以計(jì)算當(dāng)前序列特征向量系數(shù)Cc，Xc=(T1,T2,…,Tt,Tt+1,Tt+2,…,Tt+b)，其中，T1～Tt為當(dāng)前檢測(cè)序列，Tt+1～Tt+b為對(duì)應(yīng)時(shí)刻歷史序列均值，由式（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)前檢測(cè)數(shù)據(jù)最優(yōu)融合的目的.

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

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

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

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

計(jì)算步驟：

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

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

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

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

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

3.3 多步預(yù)測(cè)及滾動(dòng)

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

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

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

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

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

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

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

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

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

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

4 驗(yàn)證分析

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

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

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

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

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

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

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

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

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

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

5 研究結(jié)論

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

參考文獻(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ò)的短時(shí)交通流量預(yù)測(cè)[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)模型的卡爾曼濾波多步行程時(shí)間預(yù)測(cè)方法[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ù)短時(shí)多步雙重預(yù)測(cè)方法[J].哈爾濱工業(yè)大學(xué)學(xué)報(bào),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）；江西省科技廳科技計(jì)劃項(xiàng)目（20123BBE50094）.

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