基于雙層K近鄰算法的短時交通流預(yù)測

侯曉宇，吳 萌，李要娜

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

設(shè)有速度時間序列為X={x(1),x(2),…,x(n)}，當(dāng)前時刻的速度為x(n)，要預(yù)測的速度為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為參與計算的歷史狀態(tài)向量的總個數(shù)。

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

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

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

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

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

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

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

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

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

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

1.3 歷史樣本庫建立流程

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

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

圖1 歷史樣本庫建立流程

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

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

剔除錯誤數(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；

②計算U、V的歐式距離D；

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

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

（3）建立樣本中心庫

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

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

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

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

2 實例分析

2.1 算法精度分析

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

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

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

表1 不同K值下的MRE

圖2 不同K值下的MRE變化趨勢

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

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

圖3 3044檢測器位置

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

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

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

2.2 算法滯后性分析

2.2.1 滯后性定義

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

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

其中，

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

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

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

圖5 預(yù)測值滯后真實值1個周期示意圖

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

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

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

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

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

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

表4 算法滯后性分析

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

3 結(jié)語

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

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

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

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

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

[1] 賀國光，李宇，馬壽峰.基于數(shù)學(xué)模型的短時交通流預(yù)測方法討論[J].系統(tǒng)工程理論與實踐，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)交通流短時預(yù)測理論與方法研究[D].北京：北京交通大學(xué)，2011.

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