侯曉宇，吳 萌，李要娜

（北京四通智能交通系統(tǒng)集成有限公司，北京 100081）

0 引言

交通流預(yù)測(cè)是指在t時(shí)刻對(duì)t+Δt乃至以后若干時(shí)刻的交通流做出實(shí)時(shí)預(yù)測(cè)，通常以交通流量、速度和占有率等作為反映交通流狀態(tài)的參數(shù)，其實(shí)質(zhì)就是對(duì)這些交通流基本參數(shù)的預(yù)測(cè)。交通流預(yù)測(cè)可分為長時(shí)預(yù)測(cè)和短時(shí)預(yù)測(cè)兩種，一般認(rèn)為Δt≤15的預(yù)測(cè)為短時(shí)交通流預(yù)測(cè)[1]。

由于交通系統(tǒng)是一個(gè)有人參與的、時(shí)變的、非線性的復(fù)雜大系統(tǒng)。這給交通參數(shù)短時(shí)預(yù)測(cè)帶來了困難。目前，常用的短時(shí)預(yù)測(cè)方法包括歷史平均法[2]、時(shí)間序列法、卡爾曼濾波法、非參數(shù)回歸法、神經(jīng)網(wǎng)絡(luò)法[3]及組合模型法等等。其中非參數(shù)回歸算法具有算法原理簡(jiǎn)單、不需要先驗(yàn)知識(shí)、可快速獲得預(yù)測(cè)結(jié)果等特點(diǎn)[4]，更適用于交通流的短時(shí)預(yù)測(cè)。

最常用的非參數(shù)回歸預(yù)測(cè)算法即K近鄰算法。本文首先在K近鄰算法的基礎(chǔ)上，介紹了雙層K近鄰算法的流程及其歷史樣本庫的構(gòu)建方法。隨后，利用北京三環(huán)RTMS檢測(cè)器的實(shí)際交通流數(shù)據(jù)，對(duì)算法參數(shù)K進(jìn)行了標(biāo)定，并從預(yù)測(cè)精度及預(yù)測(cè)算法滯后性兩方面，驗(yàn)證了雙層K近鄰算法的適用性。

1 基于雙層K近鄰的非參數(shù)回歸算法流程

非參數(shù)回歸算法有很多種，最重要且常用的兩種為基于核函數(shù)的非參數(shù)回歸和基于K近鄰的非參數(shù)回歸。其中基于K近鄰的非參數(shù)回歸與核函數(shù)相比，計(jì)算量明顯減小。更適合用于交通流短時(shí)預(yù)測(cè)。

1.1 基于K近鄰的非參數(shù)回歸

將非參數(shù)回歸算法應(yīng)用于短時(shí)交通狀態(tài)預(yù)測(cè)的一般過程為：

（1）構(gòu)造交通狀態(tài)向量；

（2）根據(jù)交通狀態(tài)向量，結(jié)合歷史數(shù)據(jù)，建立歷史樣本庫；

（3）針對(duì)實(shí)時(shí)采集的數(shù)據(jù)，首先進(jìn)行預(yù)處理，判斷是否錯(cuò)誤數(shù)據(jù)，如錯(cuò)誤，則進(jìn)行修正；

（4）利用修正后的數(shù)據(jù)，構(gòu)建當(dāng)前狀態(tài)向量；

（5）利用樣本庫進(jìn)行模式匹配，同時(shí)判斷當(dāng)前狀態(tài)向量是否為典型樣本數(shù)據(jù)，如是，則補(bǔ)充入歷史樣本庫；

（6）根據(jù)模式匹配結(jié)果，得到最終預(yù)測(cè)結(jié)果。

基于K近鄰的非參數(shù)回歸（以下簡(jiǎn)稱“K近鄰法”）是以當(dāng)前狀態(tài)到歷史狀態(tài)的距離為基礎(chǔ)，加權(quán)時(shí)只有離當(dāng)前狀態(tài)最近的K個(gè)歷史狀態(tài)數(shù)據(jù)被用來估計(jì)相應(yīng)的預(yù)測(cè)值。算法中的距離，采用歐式空間距離，然后按這個(gè)距離將X1,…,Xn按照與X的接近程度重新排序?yàn)椋篨k1,…,Xkn，取權(quán)值如下：

如果與當(dāng)前狀態(tài)最近的前K個(gè)觀測(cè)值占有最大的權(quán)C=1，其余權(quán)值設(shè)為C=0。最終得到的應(yīng)用于短時(shí)交通流預(yù)測(cè)的K近鄰法可用以下公式表示：

式中：K為所選取的最近鄰元素的個(gè)數(shù)。

1.2 基于雙層K近鄰的非參數(shù)回歸

雙層K近鄰算法是在原有K近鄰非參數(shù)回歸算法的基礎(chǔ)上，對(duì)模式匹配部分進(jìn)行了改進(jìn)，增加了狀態(tài)模式匹配步驟，確保了所選的歷史狀態(tài)序列與當(dāng)前狀態(tài)序列在距離和變化趨勢(shì)上均最為接近，從而提高最終預(yù)測(cè)值的精度。

設(shè)有速度時(shí)間序列為X={x(1),x(2),…,x(n)}，當(dāng)前時(shí)刻的速度為x(n)，要預(yù)測(cè)的速度為x(n+1)。算法基本流程如下：

第1步：構(gòu)建l維的當(dāng)前狀態(tài)向量為Xnow=(x(n-l+1),…,x(n-1),x(n))，同樣，構(gòu)建l維的歷史狀態(tài)向量組為：

式中：m為參與計(jì)算的歷史狀態(tài)向量的總個(gè)數(shù)。

第2步：當(dāng)1≤i≤m時(shí)，分別計(jì)算Xpast(i)與Xnow的歐式距離D(i)，定義其下標(biāo)Dtag(i)=i。

第3步：對(duì)D(i)從小到大排序，選出距離最近的M（一般選擇M=30）個(gè)，排序后的D(i)依次為D[Dtag(i)],1≤i≤M 。

第4步：為了保證歷史狀態(tài)向量與當(dāng)前狀態(tài)向量的變化趨勢(shì)相同，定義狀態(tài)模式向量來存儲(chǔ)變化趨勢(shì)。狀態(tài)模式向量的構(gòu)成方法如下：

以速度序列X為例，當(dāng)1≤i≤n-1時(shí)，定義：

則狀態(tài)模式向量為：P=(d(1),…,d(n-1))。

按照上述方法，構(gòu)建l維當(dāng)前速度狀態(tài)向量Xnow的狀態(tài)模式為：

同理，構(gòu)建l維的歷史狀態(tài)模式向量組：

第5步：分別計(jì)算歷史狀態(tài)模式向量組和當(dāng)前狀態(tài)模式向量組的歐式距離H(i)，定義其下標(biāo)為Htag(i)。

第6步：對(duì)H(i)按照從小到大順序進(jìn)行排序，抽取出歐式距離最近的k個(gè)歷史狀態(tài)向量，作為參與預(yù)測(cè)的歷史向量，抽取出的向量為：

第7步：用抽取出的k個(gè)歷史狀態(tài)向量Xpast{Dtag[Htag(i)]},1≤i≤k 的 下 一 時(shí) 刻 值{Dtag[Htag(i)]}={Xpast,Dtag[Htag(i)](n+1)}(1≤i≤k)及其對(duì)應(yīng)的狀態(tài)向量歐式距離D[Htag(i)](1≤i≤k)進(jìn)行加權(quán)得到最終的預(yù)測(cè)結(jié)果(n+1)，即：

1.3 歷史樣本庫建立流程

交通狀態(tài)歷史樣本數(shù)據(jù)庫是歷史交通狀態(tài)數(shù)據(jù)的集合，是通過大量歷史交通狀態(tài)提煉出來的具有代表性的交通狀態(tài)數(shù)據(jù)樣本，只有歷史數(shù)據(jù)覆蓋幾乎所有可能的交通狀態(tài)，才能保證在近鄰搜索時(shí)能夠找到足夠數(shù)量的近鄰點(diǎn)，從而得到準(zhǔn)確的預(yù)測(cè)結(jié)果[2]。然而，隨著時(shí)間的推移，樣本數(shù)據(jù)庫容量急劇增長，不僅浪費(fèi)了大量的存儲(chǔ)空間，同時(shí)導(dǎo)致算法搜索效率下降，無法滿足實(shí)時(shí)性要求。因此，本節(jié)將重點(diǎn)討論歷史庫的構(gòu)建方法，使得交通狀態(tài)樣本數(shù)據(jù)庫兼具完備性和典型性，同時(shí)又不影響算法的搜索效率，滿足短時(shí)交通狀態(tài)的實(shí)時(shí)性要求。

歷史樣本庫建立流程如圖1所示。

圖1 歷史樣本庫建立流程

根據(jù)上述流程，構(gòu)建歷史庫的具體步驟如下。

（1）數(shù)據(jù)預(yù)處理

剔除錯(cuò)誤數(shù)據(jù)，并補(bǔ)齊缺失數(shù)據(jù)。

（2）建立歷史標(biāo)準(zhǔn)樣本庫

歷史標(biāo)準(zhǔn)樣本庫的建立，依賴于所選擇的當(dāng)前狀態(tài)向量的維數(shù)，即歷史標(biāo)準(zhǔn)樣本與當(dāng)前狀態(tài)向量的維數(shù)要保持一致，具體建立步驟如下：

①從歷史數(shù)據(jù)中選出一組向量U，放入歷史標(biāo)準(zhǔn)樣本庫，并選擇另一組向量V；

②計(jì)算U、V的歐式距離D；

③如D小于閾值Y，則認(rèn)為V是重復(fù)狀態(tài)，否則將V放入標(biāo)準(zhǔn)樣本庫；

④循環(huán)計(jì)算至所有的歷史數(shù)據(jù)都處理完畢。

（3）建立樣本中心庫

雙層K近鄰算法的效率在很大程度上受制于交通狀態(tài)樣本庫的數(shù)據(jù)規(guī)模和存儲(chǔ)結(jié)構(gòu)。為了提高大規(guī)模樣本量情況下算法的計(jì)算速度，對(duì)生成的標(biāo)準(zhǔn)樣本庫進(jìn)行聚類，將聚類中心存入樣本中心庫。由于短時(shí)預(yù)測(cè)算法對(duì)算法運(yùn)算速度有較高要求，因此采用基于網(wǎng)格的方法對(duì)歷史狀態(tài)樣本進(jìn)行聚類。

（4）判斷各分類的密集度

在交通狀態(tài)歷史樣本庫中，各聚類的密集程度互不相同：在密集程度較高的區(qū)域，如果選定的K值較小，則會(huì)丟失一定數(shù)量的相似近鄰，降低預(yù)測(cè)精度；而在密集程度較低的區(qū)域，如果K值較大，則會(huì)將非近鄰數(shù)據(jù)包含進(jìn)來，同樣會(huì)導(dǎo)致預(yù)測(cè)精度下降[5]。為了避免此種情況，定義密集度M，以確保歷史庫的完備性。密集度M是指距離聚類中心半徑為R的圓內(nèi)所包含的歷史狀態(tài)向量的最小個(gè)數(shù)。

只有在聚類滿足密集度要求的前提下，才算是歷史庫計(jì)算完成。

2 實(shí)例分析

2.1 算法精度分析

本文采用基于雙層K近鄰的非參數(shù)回歸算法，進(jìn)行了針對(duì)速度的短時(shí)預(yù)測(cè)分析研究。分析數(shù)據(jù)來自于北京三環(huán)路上的RTMS檢測(cè)器。利用從2012年6月4日至2012年6月10日的數(shù)據(jù)建立歷史樣本庫，數(shù)據(jù)時(shí)間間隔是5min。為了提高計(jì)算速度，采用網(wǎng)格法聚類，用C#語言實(shí)現(xiàn)算法程序。隨后，利用程序?qū)?012年6月11日的6：00—24：00的速度數(shù)據(jù)進(jìn)行預(yù)測(cè)。為了能評(píng)價(jià)和比較仿真實(shí)驗(yàn)結(jié)果，引入平均相對(duì)誤差（MRE,Mean Relative Error），計(jì)算公式如下：

式中：Xi(t+1)為下一時(shí)刻速度的實(shí)際值；(t+1)為下一時(shí)刻速度的預(yù)測(cè)值；N為樣本數(shù)。

定義當(dāng)前狀態(tài)向量為(xi-2,xi-1,xi)，選取不同的K值，獲得的誤差如表1所示。不同K值下的MRE數(shù)據(jù)如表1所示，MRE變化趨勢(shì)如圖2所示。

表1 不同K值下的MRE

圖2 不同K值下的MRE變化趨勢(shì)

可見，隨著K值的增大，MRE逐漸減小，在K=11時(shí)，整個(gè)環(huán)路的預(yù)測(cè)誤差最小。隨后，有小幅上升，但變化不大?？紤]速度計(jì)預(yù)測(cè)的精度需求，最終選擇K=11以獲得最優(yōu)的預(yù)測(cè)結(jié)果。

在K=11時(shí)，選擇三環(huán)3044檢測(cè)器進(jìn)行深入分析，3044檢測(cè)器的位置如圖3所示。

圖3 3044檢測(cè)器位置

預(yù)測(cè)結(jié)果如圖4所示。

圖4 K=2，11，16時(shí)的預(yù)測(cè)結(jié)果與真實(shí)值的對(duì)比

從圖4可以看出，在K=11時(shí)，預(yù)測(cè)結(jié)果更接近于真實(shí)值。

2.2 算法滯后性分析

2.2.1 滯后性定義

預(yù)測(cè)滯后性，是指真實(shí)值和預(yù)測(cè)值間存在時(shí)間延遲。即無論采用何種預(yù)測(cè)算法，t+1時(shí)刻的預(yù)測(cè)值由于受到t時(shí)刻真實(shí)狀態(tài)的影響最大，其值會(huì)較為接近t時(shí)刻的真實(shí)值。因此，當(dāng)真實(shí)值產(chǎn)生波動(dòng)時(shí)，預(yù)測(cè)值不能很好地跟隨真實(shí)值的變化，造成預(yù)測(cè)結(jié)果與真實(shí)值之間存在延遲。延遲可分為零步延遲（即同步）和n步延遲（n=1，2，…）。

在進(jìn)行預(yù)測(cè)滯后性估計(jì)時(shí)，可采用基于歐式距離的互相關(guān)函數(shù)法對(duì)其進(jìn)行分析?；ハ嚓P(guān)函數(shù)法估計(jì)預(yù)測(cè)時(shí)間延遲的核心思想是：估計(jì)延遲時(shí)間τ*，使得消除延遲后兩列信號(hào)之間的相似性最大。互相關(guān)函數(shù)法可分析出算法的整體預(yù)測(cè)滯后性以及算法的適用性。本文采用歐式距離來計(jì)算互相關(guān)函數(shù)。設(shè)交通流真實(shí)值序列為xt，預(yù)測(cè)值序列為yt，則估計(jì)公式如下：

其中，

將預(yù)測(cè)值左右平移n個(gè)周期后，計(jì)算其與真實(shí)值的互相關(guān)函數(shù)，互相關(guān)函數(shù)最小時(shí)對(duì)應(yīng)的n值即是預(yù)測(cè)算法的滯后周期。

以RTMS檢測(cè)器3008早8：20～9：25數(shù)據(jù)為例，其真實(shí)值Xi和預(yù)測(cè)值Yi如表2所示，二者對(duì)比如圖5所示。

表2 預(yù)測(cè)值Xi與預(yù)測(cè)值Yi數(shù)值表

圖5 預(yù)測(cè)值滯后真實(shí)值1個(gè)周期示意圖

從圖5可以看出，預(yù)測(cè)值比真實(shí)值整體滯后1個(gè)周期。下面利用互相關(guān)函數(shù)估計(jì)法進(jìn)行分析。

設(shè)T代表兩個(gè)連續(xù)值間的時(shí)間差，即序列的周期，則分別計(jì)算當(dāng)前、左平移1個(gè)T、2個(gè)T、以及右平移1個(gè)T、2個(gè)T的互相關(guān)系數(shù)，結(jié)果如表3所示。

表3 移動(dòng)不同周期時(shí)的互相關(guān)系數(shù)

可見，在左移1個(gè)周期的情況下，互相關(guān)系數(shù)最大，即預(yù)測(cè)值整體滯后一個(gè)周期。

2.2.2 數(shù)據(jù)分析

選取4051檢測(cè)器的1、2車道，2011的7月4日—7月10日，8月8日—8月13日及2012的7月10日—7月15日，以5min為間隔，每天7：00—22：00的數(shù)據(jù)，按1h劃分序列，即分別計(jì)算多個(gè)1h內(nèi)預(yù)測(cè)值和真實(shí)值間的互相關(guān)系數(shù)，并平移，以確定其最優(yōu)的互相關(guān)系數(shù)，從而得到滯后周期。分別對(duì)自適應(yīng)過濾法及雙層K近鄰方法的預(yù)測(cè)滯后性進(jìn)行分析，其對(duì)比結(jié)果如表4所示。

表4 算法滯后性分析

從表4可以看出，自適應(yīng)過濾法預(yù)測(cè)結(jié)果有97.9%滯后一個(gè)周期，而僅有1.4%的數(shù)據(jù)無滯后。但雙層K近鄰算法僅有4%的數(shù)據(jù)滯后一個(gè)周期，大部分預(yù)測(cè)結(jié)果不滯后，因此，雙層K近鄰算法在滯后性方面，遠(yuǎn)遠(yuǎn)優(yōu)于自適應(yīng)過濾法。

3 結(jié)語

本文在基于K近鄰的非參數(shù)回歸算法的基礎(chǔ)上，提出了雙層K近鄰算法，并通過實(shí)際數(shù)據(jù)，驗(yàn)證了算法的實(shí)用性。實(shí)例分析結(jié)果表明，算法可滿足短時(shí)交通流預(yù)測(cè)的實(shí)時(shí)性、準(zhǔn)確性和可靠性。今后將在以下幾個(gè)方面進(jìn)一步完善算法：

（1）改變當(dāng)前狀態(tài)向量的維度，驗(yàn)證在何種維度下，算法最為精確；

（2）提高算法的計(jì)算效率，以滿足短時(shí)交通流預(yù)測(cè)實(shí)時(shí)性的需求；

（3）不斷完善歷史庫，提高算法精度；

（4）引入事件影響分析，使得在速度值突變情況下，預(yù)測(cè)結(jié)果更接近于真實(shí)值，從而進(jìn)一步降低算法滯后性。

[1] 賀國光，李宇，馬壽峰.基于數(shù)學(xué)模型的短時(shí)交通流預(yù)測(cè)方法討論[J].系統(tǒng)工程理論與實(shí)踐，2000，20（12）：51-56.

[2] Smith B L,Demetsky M J.Traffic Flow Forecasting:Comparison of Modeling Approaches[J].Journal of Transportation Engineering,1997,123（4）：261-266.

[3] Dia Hussein F.An Object-Oriented Neural Network Approach to Short-Term Traffic Forecasting[J].European Journal of Operations Research,2001,131（2）：253-261.

[4] 董春嬌.多狀態(tài)下城市快速路網(wǎng)交通流短時(shí)預(yù)測(cè)理論與方法研究[D].北京：北京交通大學(xué)，2011.

[5] 宮曉燕，湯淑明.基于非參數(shù)回歸的短時(shí)交通流量預(yù)測(cè)與事件檢測(cè)綜合算法[J].中國公路學(xué)報(bào)，2003，16（1）：82-86.