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

侯曉宇，吳 萌，李要娜

（北京四通智能交通系統集成有限公司，北京 100081）

0 引言

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

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

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

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

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

1.1 基于K近鄰的非參數回歸

將非參數回歸算法應用于短時交通狀態預測的一般過程為：

（1）構造交通狀態向量；

（2）根據交通狀態向量，結合歷史數據，建立歷史樣本庫；

（3）針對實時采集的數據，首先進行預處理，判斷是否錯誤數據，如錯誤，則進行修正；

（4）利用修正后的數據，構建當前狀態向量；

（5）利用樣本庫進行模式匹配，同時判斷當前狀態向量是否為典型樣本數據，如是，則補充入歷史樣本庫；

（6）根據模式匹配結果，得到最終預測結果。

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

如果與當前狀態最近的前K個觀測值占有最大的權C=1，其余權值設為C=0。最終得到的應用于短時交通流預測的K近鄰法可用以下公式表示：

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

1.2 基于雙層K近鄰的非參數回歸

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

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

第1步：構建l維的當前狀態向量為Xnow=(x(n-l+1),…,x(n-1),x(n))，同樣，構建l維的歷史狀態向量組為：

式中：m為參與計算的歷史狀態向量的總個數。

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

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

第4步：為了保證歷史狀態向量與當前狀態向量的變化趨勢相同，定義狀態模式向量來存儲變化趨勢。狀態模式向量的構成方法如下：

以速度序列X為例，當1≤i≤n-1時，定義：

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

按照上述方法，構建l維當前速度狀態向量Xnow的狀態模式為：

同理，構建l維的歷史狀態模式向量組：

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

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

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

1.3 歷史樣本庫建立流程

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

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

圖1 歷史樣本庫建立流程

根據上述流程，構建歷史庫的具體步驟如下。

（1）數據預處理

剔除錯誤數據，并補齊缺失數據。

（2）建立歷史標準樣本庫

歷史標準樣本庫的建立，依賴于所選擇的當前狀態向量的維數，即歷史標準樣本與當前狀態向量的維數要保持一致，具體建立步驟如下：

①從歷史數據中選出一組向量U，放入歷史標準樣本庫，并選擇另一組向量V；

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

③如D小于閾值Y，則認為V是重復狀態，否則將V放入標準樣本庫；

④循環計算至所有的歷史數據都處理完畢。

（3）建立樣本中心庫

雙層K近鄰算法的效率在很大程度上受制于交通狀態樣本庫的數據規模和存儲結構。為了提高大規模樣本量情況下算法的計算速度，對生成的標準樣本庫進行聚類，將聚類中心存入樣本中心庫。由于短時預測算法對算法運算速度有較高要求，因此采用基于網格的方法對歷史狀態樣本進行聚類。

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

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

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

2 實例分析

2.1 算法精度分析

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

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

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

表1 不同K值下的MRE

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

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

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

圖3 3044檢測器位置

預測結果如圖4所示。

圖4 K=2，11，16時的預測結果與真實值的對比

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

2.2 算法滯后性分析

2.2.1 滯后性定義

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

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

其中，

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

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

表2 預測值Xi與預測值Yi數值表

圖5 預測值滯后真實值1個周期示意圖

從圖5可以看出，預測值比真實值整體滯后1個周期。下面利用互相關函數估計法進行分析。

設T代表兩個連續值間的時間差，即序列的周期，則分別計算當前、左平移1個T、2個T、以及右平移1個T、2個T的互相關系數，結果如表3所示。

表3 移動不同周期時的互相關系數

可見，在左移1個周期的情況下，互相關系數最大，即預測值整體滯后一個周期。

2.2.2 數據分析

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

表4 算法滯后性分析

從表4可以看出，自適應過濾法預測結果有97.9%滯后一個周期，而僅有1.4%的數據無滯后。但雙層K近鄰算法僅有4%的數據滯后一個周期，大部分預測結果不滯后，因此，雙層K近鄰算法在滯后性方面，遠遠優于自適應過濾法。

3 結語

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

（1）改變當前狀態向量的維度，驗證在何種維度下，算法最為精確；

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

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

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

[1] 賀國光，李宇，馬壽峰.基于數學模型的短時交通流預測方法討論[J].系統工程理論與實踐，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] 董春嬌.多狀態下城市快速路網交通流短時預測理論與方法研究[D].北京：北京交通大學，2011.

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