張 軍，王寒凝，楊正瓴，劉正光，葉劍華

(1. 天津大學(xué)電氣與自動化工程學(xué)院，天津 300072；2. 天津市過程檢測與控制重點實驗室，天津 300072)

K-近鄰(K-nearest neighbor，k-NN)非參數(shù)回歸是公路短時交通流預(yù)測的可靠方法之一[1-13]．它是一種無參數(shù)、可移植、高預(yù)測準確率的算法，其預(yù)測誤差比較小，且誤差分布情況良好．非參數(shù)回歸預(yù)測不需要先驗知識，只需足夠的歷史數(shù)據(jù)．該算法認為系統(tǒng)所有因素之間的內(nèi)在聯(lián)系都蘊涵在歷史數(shù)據(jù)里，因此直接從歷史數(shù)據(jù)中得到信息而不是為歷史數(shù)據(jù)建立一個近似模型．它未將歷史數(shù)據(jù)作平滑處理，因此，較適合在有特殊事件發(fā)生時使用[14-15]．從 1991年以來，該方法受到許多短時公路交通流預(yù)測研究者的重視，從而得到不斷的改進[1-13]．

K-近鄰非參數(shù)回歸預(yù)測有4個主要步驟：歷史數(shù)據(jù)準備，樣本數(shù)據(jù)庫生成，狀態(tài)向量定義及 K-近鄰搜索，預(yù)測算法的確定[3,10]．它在歷史數(shù)據(jù)中搜索出與當前點(模式)最相似的 K個“近鄰”，并用這 K個“近鄰”預(yù)測下一個時段的流量．提高該方法效果的兩個主要途徑是改進 K-近鄰的搜索和改進預(yù)測算法(參數(shù)調(diào)整規(guī)則)．

目前，已有的改進工作主要有：采用定點的搜索來提高 K-近鄰的搜索；采用結(jié)合相關(guān)系數(shù)[9-10]、模糊理論[4]、聚類[7,11]等方法來提高K-近鄰的質(zhì)量(與當前點相似性)；采用對 K-近鄰的調(diào)整技術(shù)來提高預(yù)測效果[1-3]等．但仍然存在搜索量偏大、對波動大的交通流預(yù)測效果變差等不足．

在此基礎(chǔ)上，筆者用相關(guān)系數(shù)來替代原來的距離進行K-近鄰的選擇；采用K-近鄰的線性調(diào)整技術(shù)，結(jié)合穩(wěn)健的組合預(yù)測，來改進現(xiàn)有的 K-近鄰非參數(shù)回歸預(yù)測，以期達到提高實時性、預(yù)測可靠性等效果，特別是改善大波動交通流的預(yù)測效果．

1 K-近鄰的穩(wěn)健組合預(yù)測方法

1.1 K-近鄰非參數(shù)回歸預(yù)測的基本方法

將觀察或測量得到的輸入-輸出時間序列對記為［X ( s), Y ( s )］，s＝1，…，n 是正整數(shù)，稱它們?yōu)閷W(xué)習(xí)樣本．對于某給定的輸入 X ( t)、預(yù)測輸出 Y ( t) ，K-近鄰方法首先按照距離找到最靠近 X ( t)的K個 X ( s)，s＝s1，…，sK．預(yù)測結(jié)果為

改進 K-近鄰預(yù)測的 2個主要熱點是 K個近鄰X( s)的優(yōu)選以及由 K個 Y ( s)形成預(yù)測結(jié)果( t)的方法．

1.2 采用相關(guān)系數(shù)代替距離

現(xiàn)有選擇 K個近鄰 X ( s)的方法，大多數(shù)是以“距離”為標準的．這里的距離，用數(shù)學(xué)語言講，就是一種“范數(shù)”．最常見的是歐幾里德距離(2-范數(shù))．以公路交通流預(yù)測為例，X ( s)可以是某些歷史的交通流數(shù)據(jù)，或者是考慮天氣、星期等的影響因子．只以距離為選擇標準，會有如下4個不足．

(1) 對于波動大的交通流，難以找到高質(zhì)量的K-近鄰．同時需要過長的歷史數(shù)據(jù)，從而使得距離小的各近鄰，由于相距時間太久帶來的交通流性質(zhì)變化，不利于提高預(yù)測效果，即難以均衡“搜索時間”和“K-近鄰的相似性”之間的矛盾．

(2) 采用標準差(方差的開方)進行原始交通流折算，以消除不同天的交通流波動性[1，3]．對于樣本容量比較小的 X ( s)，方差估計的置信區(qū)間比較長，即標準差計算的真實性不理想．

(3) 距離(范數(shù))只反映當前點和 K-近鄰的“靠近性”，不直接反映它們之間的“形狀相似性”．而形狀相似性則直接反映交通流的變化發(fā)展規(guī)律．

(4) 為了提高“K-近鄰的相似性”，文獻[9-10]采用增加相關(guān)系數(shù)作為評價標準．這樣雖然提高了K-近鄰的相似性，但是以增大歷史數(shù)據(jù)的搜索(降低實時性)為代價的．

具體的選擇方法有聚類[7,11]和平衡二叉樹[13]．

本文的改進為：只采用相關(guān)系數(shù)作為選擇 K-近鄰的標準．具體方法是將文獻[9-10]中的“距離”步驟跳過，只保留相關(guān)系數(shù)作為評價標準．這樣改進的優(yōu)點有 2個：①相關(guān)系數(shù)的幾何意義是 X ( t)與近鄰間“形狀的線性相似性”[16]，它直接反映交通流的發(fā)展規(guī)律，用最大正相關(guān)系數(shù)選擇的各 K-近鄰，在交通流的具體數(shù)值上可以有很大的差異，從而改善了“大波動”情況下 K-近鄰的優(yōu)選，這樣就省去了用標準差折算歷史數(shù)據(jù)的預(yù)處理，提高了實時性；②由于相關(guān)系數(shù)可以將數(shù)值差異很大的 K-近鄰選擇進來，使搜索需要的歷史數(shù)據(jù)量減少，不僅提高了實時性，還提高了 K-近鄰間的相似性，即有利于克服交通流性質(zhì)的長期變化引起的不利影響．

這種方法等效于將每天的交通流標準化：用每天的交通流平均值，對全天交通流折算，消除了“大波動”交通流按照“距離”選擇K-近鄰的困難．

1.3 采用穩(wěn)健的組合預(yù)測改進預(yù)測效果

除了采用式(1)的直接平均外，還可以采用各種先進方法替換式(1)以得到更好的預(yù)測效果．現(xiàn)有的方法包括當前模式與近鄰間的歐式距離調(diào)整[1,12]、相似度調(diào)整[13]等．

本文的2類改進是：①采用當前模式和 K-近鄰的歐氏距離，調(diào)整各K-近鄰對應(yīng)的預(yù)測值，這等價于用每天交通流的平均值，再折算回實際的歷史交通流數(shù)據(jù)，它對應(yīng)組合預(yù)測策略中的簡單平均法[17-18]；②采用當前模式和 K-近鄰的方差，按照組合預(yù)測策略中的方差倒數(shù)法合成預(yù)測的結(jié)果[17-18]，具體方法見式(2)．

實際上，各 K-近鄰對應(yīng)的其后交通流，就是待預(yù)測交通流的一個預(yù)測值．本文采用組合預(yù)測策略代替式(1)進行預(yù)測，與現(xiàn)有其他改進方法相比較為簡單，且預(yù)測效果好．

方差倒數(shù)法合成 K-近鄰預(yù)測的具體方法如下所述．本文只采用歷史交通流，未考慮其他影響，故Y( s)就是 X ( s)．

記K個近鄰 X ( s)對應(yīng)交通流 Y ( s)在(t+1)點的數(shù)值為 y ( t + 1 )，則預(yù)測值為

式中：ai是組合預(yù)測中的方差倒數(shù)法的系數(shù)[17-18]，

即組合預(yù)測中的簡單平均法．進一步，若各 bi＝0，式(3)就退化成式(1)．

2 改進的理論分析

本文改進的主要數(shù)學(xué)基礎(chǔ)是數(shù)理統(tǒng)計學(xué)[17]和穩(wěn)健統(tǒng)計學(xué)[19]．

當近鄰 X ( s)對應(yīng)的交通流點數(shù)不多時，可認為其概率密度函數(shù)近似不變(近似平穩(wěn)的)．這樣，無論是歐氏距離、方差，還是相關(guān)系數(shù)的計算，得到的只是其真實值的“點估計”值，即各統(tǒng)計量的真實值，是分布在該“點估計”值周圍的(置信區(qū)間)．而置信區(qū)間的長度，隨著樣本容量的增大而明顯變?。粲洏颖救萘繛?N，則置信區(qū)間的長度可以按照1或類似的方式減?。?/p>

特別地，實際交通流歷史數(shù)據(jù)中總存在一些outliers(離群值、異常數(shù)據(jù))，它們使統(tǒng)計量真實值和估計值的差異更明顯．增大樣本容量、采用統(tǒng)計量的穩(wěn)健估計方法是改進估計值的 2種有效途徑．由于增大樣本容量會降低實時性，并增大交通流數(shù)據(jù)性質(zhì)變化引起的誤差，所以應(yīng)優(yōu)先采用穩(wěn)健估計方法．標準差穩(wěn)健估計的具體計算方法可參見文獻[19]，本文采用的有下面式(4)～(7)．

2.1 采用相關(guān)系數(shù)代替距離

K-近鄰的相關(guān)系數(shù)選擇方法直接解決了各天交通流大波動的不良影響．

(1) 省去了原始交通流數(shù)據(jù)按每天“標準差”折算的預(yù)處理；

(2) 由于平均值估計的置信區(qū)間明顯比方差估計的置信區(qū)間窄[16,19]，從而有效提高了估計的準確性；在下一步的預(yù)測中，采用平均值折算預(yù)測的效果會得到提高；

(3) 減小了預(yù)測必須采用的歷史數(shù)據(jù)量，降低了交通流的長期變化對預(yù)測的不利影響．

2.2 采用穩(wěn)健的組合預(yù)測改進預(yù)測效果

穩(wěn)健統(tǒng)計是數(shù)理統(tǒng)計學(xué)的一個分支，研究當樣本數(shù)據(jù)總體假定稍有變動及記錄數(shù)據(jù)有失誤時，統(tǒng)計方法的適應(yīng)性問題，即主要研究對總體分布的穩(wěn)健性和對異常數(shù)據(jù)的穩(wěn)健性．交通流是復(fù)雜時間序列，其“總體分布”是隨時間變化的；且交通流含有較高的異常數(shù)據(jù)(outliers)．采用穩(wěn)健統(tǒng)計方法，可以明顯抑制這些干擾的不利影響[19]．如按照定義計算σ，在 5%的干擾下，計算值會是實際值的 2倍以上．總之，樣本容量有限、預(yù)測誤差的概率分布函數(shù)不可知、異常數(shù)據(jù)這 3種影響因素決定了方差和相關(guān)系數(shù)在實際工作中不能準確求出．采用穩(wěn)健統(tǒng)計方法，可顯著提高方差和相關(guān)系數(shù)計算值的真實性．

預(yù)測式(2)中需要第i個近鄰 X ( si)標準差σ的估計．穩(wěn)健統(tǒng)計中σ常見的穩(wěn)健估計方法[19]有

3 示 例

圖 1(a)是某公路 33,d的 3,min統(tǒng)計間隔交通流；圖 1(b)是按照“每天平均值”折算后的相對值．容易驗證，按“每天平均值”折算后的相對值，比采用“標準差”的折算值更平穩(wěn)．

圖 2是該交通流最后 3天的小波周期圖．根據(jù)時間序列分析中的 Wold分解定理(1938年)和Cramer分解定理(1961年)，交通流可以分解為“復(fù)雜的信號(確定的和隨機的)+白噪聲”．其中的白噪聲形成一個目前任何科技方法都不能預(yù)測的誤差極限．目前還沒有可靠的方法來精確分離出白噪聲．

從工程角度看，采用小波去噪方法可以近似分離白噪聲．這可用于客觀地評價某預(yù)測方法的效果．

圖2 交通流最后3天的小波周期Fig.2 Wavelet transform of the latest 3 days of traffic flow

采用最后 3天每天下午 16：38—19：12(第 0.7～0.8天)共48點的數(shù)據(jù)作為預(yù)測對象．表1為采用小波去噪得到的預(yù)測誤差極限，即交通流中包含的白噪聲引起的預(yù)測誤差．其中 MPE是平均百分誤差(mean percentage error)，MAPE是平均絕對百分誤差(mean absolute percentage error)．

表1 小波去噪得到的預(yù)測誤差極限Tab.1 Forecasting error limits estimated by wavelet denoise

第31～33天每天上述48點滾動預(yù)測采用 X ( s)的樣本容量為20，近鄰個數(shù) K＝6．采用本文改進方法得到的預(yù)測誤差見表2．s、dn、MAD、df、sbi依次表示方差倒數(shù)法中標準差計算采用的方法，見公式(4)～(7).

可見，由于交通流的波動性、存在離群值，簡單平均法和非穩(wěn)健的方差倒數(shù)法 s預(yù)測效果不如穩(wěn)健的方差倒數(shù)法 dn、MAD、df、sbi效果好．

表2 本文方法的預(yù)測誤差Tab.2 Forecasting errors by the proposed methods in this paper

圖 3為第 33天采用 dn進行方差倒數(shù)法預(yù)測的結(jié)果．

可見，預(yù)測值的波動比實際交通流小，因為實際交通流里包含白噪聲的瞬時值是不能預(yù)測的．

圖3 第33.7—33.8天的交通流歷史數(shù)據(jù)與預(yù)測值Fig.3 Forecasting data and the original traffic flow Fig. 3 between the 33.7 and the 33.8 days

4 結(jié) 語

K-近鄰非參數(shù)回歸預(yù)測是一種受到廣泛重視的公路短時交通流預(yù)測方法．本文對 K-近鄰非參數(shù)回歸預(yù)測方法做了如下改進．①直接采用相關(guān)系數(shù)進行 K-近鄰的選擇．不僅減少了數(shù)據(jù)的預(yù)處理，還適用于大波動的數(shù)據(jù)，減少了預(yù)測所必須的歷史數(shù)據(jù)．②K個近鄰對應(yīng)的下一點歷史數(shù)據(jù)，調(diào)整后就是待預(yù)測交通流的 K個預(yù)測值．采用組合預(yù)測的方差倒數(shù)法合成它們，可以得到好的預(yù)測結(jié)果．③為了降低離群值的不利影響，可以采用穩(wěn)健統(tǒng)計的方法來計算各標準差的估計值．結(jié)果表明，采用穩(wěn)健統(tǒng)計的方差倒數(shù)法，具有較為穩(wěn)定的預(yù)測效果，可以提高預(yù)測準確率1%以上．

［1］Turochy R E. Enhancing short-term traffic forecasting with traffic condition information[J].Journal of Transportation Engineering，ASCE，2006，132(6)：469-474.

［2］Smith B L，Williams B M，Oswald R K. Comparison of parametric and nonparametric models for traffic flow forecasting[J].Transportation Research Part C：Emerging Technologies，2002，10(4)：303-321.

［3］Davis G A，Nihan N L. Nonparametric regression and short-term freeway traffic forecasting[J].Journal of Transportation Engineering，1991，117(2)：178-188.

［4］Guo Limei，Luo Dayong. Short-term traffic flow prediction based on nonparametric recursive time series[C]//Proceedings of the Second International Conference on Modelling and Simulation(ICMS2009). Manchester，United Kingdom，2009，6：305-310.

［5］Wang X Y，Juan Z C，Liu M，et al. The application of nonparametric regressive algorithm for short-term traffic flow forecast[C]//Proceedings of the First International Workshop on Education Technology and Computer Science. Wuhan，China，2009，III：767-770.

［6］Zhang Y，Liu Y C. A novel approach to forecast weakly regular traffic status[C]//Proceedings of the11th International IEEE Conference on Intelligent Transportation Systems. Beijing，China，2008：998-1002.

［7］張曉利，賀國光. 考慮交通吸納點的非參數(shù)回歸組合型短時交通流預(yù)測方法[J]. 系統(tǒng)工程，2006，24(12)：21-25.

Zhang Xiaoli，He Guoguang. The combined forecasting approach based on non-parametric regression for shortterm traffic flow of roads with parking spaces[J].Systems Engineering，2006，24(12)：21-25(in Chinese).

［8］周小鵬，馮 奇，孫立軍. 基于最近鄰法的短時交通流預(yù)測[J]. 同濟大學(xué)學(xué)報：自然科學(xué)版，2006，34(11)：1494-1498.Zhou Xiaopeng，F(xiàn)eng Qi，Sun Lijun. Short-term traffic flow forecasting based on nearest neighbor algorithm[J].Journal of Tongji University：Natural Science，2006，34(11)：1494-1498(in Chinese).

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

Gong Xiaoyan，Tang Shuming. Integrated traffic flow forecasting and traffic incident detection algorithm based on non-parametric regression[J].China Journal of Highway and Transport，2003，16(1)：82-86(in Chinese).

［10］范魯明，賀國光. 改進的K近鄰非參數(shù)回歸在短時交通流量預(yù)測中的應(yīng)用[J]. 長沙交通學(xué)院學(xué)報，2007，23(4)：39-43.

Fan Luming，He Guoguang. ImprovedKnearest neighbor nonparametric regression and its application in short-term traffic flow forecasting[J].Journal of Changsha Communications University，2007，23(4)：39-43(in Chinese).

［11］范魯明，賀國光. 改進非參數(shù)回歸在交通流量預(yù)測中的應(yīng)用[J]. 重慶交通大學(xué)學(xué)報：自然科學(xué)版，2008，27(1)：96-99.

Fan Luming，He Guoguang. Application improvement of nonparametric regression to traffic flow forecast[J].Journal of Chongqing Jiaotong University：Natural Sci-ence，2008，27(1)：96-99(in Chinese).

［12］李振龍，張利國，錢海峰. 基于非參數(shù)回歸的短時交通流預(yù)測研究綜述[J]. 交通運輸工程與信息學(xué)報，2008，6(4)：34-39.

Li Zhenlong，Zhang Liguo，Qian Haifeng. Review of the short-term traffic flow forecasting based on the nonparametric regression[J].Journal of Transportation Engineering and Information，2008，6(4)：34-39(in Chinese).

［13］張曉利，賀國光，陸化普. 基于K-鄰域非參數(shù)回歸短時交通流預(yù)測方法[J]. 系統(tǒng)工程學(xué)報，2009，24(2)：178-183.

Zhang Xiaoli，He Guoguang，Lu Huapu. Short-term traffic flow forecasting based onK-nearest neighbors nonparametric regression[J].Journal of Systems Engineering，2009，24(2)：178-183(in Chinese).

［14］王 進，史其信. 短時交通流預(yù)測模型綜述[J]. ITS通訊，2005，7(1)：10-13.

Wang Jin，Shi Qixin. A review of the short-term traffic flow prediction methods[J].ITS Communication，2005，7(1)：10-13(in Chinese).

［15］劉 靜，關(guān) 偉. 交通流預(yù)測方法綜述[J]. 公路交通科技，2004，21(3)：82-85.

Liu Jing，Guan Wei. A summary of traffic flow forecasting methods [J].Journal of Highway and Transportation Research and Development，2004，21(3)：82-85(in Chinese).

［16］Bernstein R，Bernstein S.Schaum's Outline of Elements of StatisticsⅡ：Inferential Statistics[M]. New York：McGraw-Hill Companies，1999.

［17］唐小我，馬永開，曾 勇，等. 現(xiàn)代組合預(yù)測和組合投資決策方法及應(yīng)用[M]. 北京：科學(xué)出版社，2003.Tang Xiaowo，Ma Yongkai，Zeng Yong，et al.Modern

Combination Forecasting and Investment Decision Approach and Applications[M]. Beijing：Science Press，2003(in Chinese).

［18］De Gooijer J G，Hyndman R J. 25 years of time series forecasting[J].International Journal of Forecasting，2006，22(3)：443-473.

［19］Hoaglin D C，Mosteller F，Tukey J W. 探索性數(shù)據(jù)分析[M]. 陳忠璉，郭德媛，譯. 北京：中國統(tǒng)計出版社，1998.

Hoaglin D C，Mosteller F，Tukey J W.Understanding Robust and Exploratory Data Analysis[M]. Chen Zhonglian，Guo Deyuan，Trans. Beijing：China Statistics Press，1998(in Chinese).