張 軍,王寒凝,楊正瓴,劉正光,葉劍華
(1. 天津大學(xué)電氣與自動(dòng)化工程學(xué)院,天津 300072;2. 天津市過(guò)程檢測(cè)與控制重點(diǎn)實(shí)驗(yàn)室,天津 300072)
K-近鄰(K-nearest neighbor,k-NN)非參數(shù)回歸是公路短時(shí)交通流預(yù)測(cè)的可靠方法之一[1-13].它是一種無(wú)參數(shù)、可移植、高預(yù)測(cè)準(zhǔn)確率的算法,其預(yù)測(cè)誤差比較小,且誤差分布情況良好.非參數(shù)回歸預(yù)測(cè)不需要先驗(yàn)知識(shí),只需足夠的歷史數(shù)據(jù).該算法認(rèn)為系統(tǒng)所有因素之間的內(nèi)在聯(lián)系都蘊(yùn)涵在歷史數(shù)據(jù)里,因此直接從歷史數(shù)據(jù)中得到信息而不是為歷史數(shù)據(jù)建立一個(gè)近似模型.它未將歷史數(shù)據(jù)作平滑處理,因此,較適合在有特殊事件發(fā)生時(shí)使用[14-15].從 1991年以來(lái),該方法受到許多短時(shí)公路交通流預(yù)測(cè)研究者的重視,從而得到不斷的改進(jìn)[1-13].
K-近鄰非參數(shù)回歸預(yù)測(cè)有4個(gè)主要步驟:歷史數(shù)據(jù)準(zhǔn)備,樣本數(shù)據(jù)庫(kù)生成,狀態(tài)向量定義及 K-近鄰搜索,預(yù)測(cè)算法的確定[3,10].它在歷史數(shù)據(jù)中搜索出與當(dāng)前點(diǎn)(模式)最相似的 K個(gè)“近鄰”,并用這 K個(gè)“近鄰”預(yù)測(cè)下一個(gè)時(shí)段的流量.提高該方法效果的兩個(gè)主要途徑是改進(jìn) K-近鄰的搜索和改進(jìn)預(yù)測(cè)算法(參數(shù)調(diào)整規(guī)則).
目前,已有的改進(jìn)工作主要有:采用定點(diǎn)的搜索來(lái)提高 K-近鄰的搜索;采用結(jié)合相關(guān)系數(shù)[9-10]、模糊理論[4]、聚類(lèi)[7,11]等方法來(lái)提高K-近鄰的質(zhì)量(與當(dāng)前點(diǎn)相似性);采用對(duì) K-近鄰的調(diào)整技術(shù)來(lái)提高預(yù)測(cè)效果[1-3]等.但仍然存在搜索量偏大、對(duì)波動(dòng)大的交通流預(yù)測(cè)效果變差等不足.
在此基礎(chǔ)上,筆者用相關(guān)系數(shù)來(lái)替代原來(lái)的距離進(jìn)行K-近鄰的選擇;采用K-近鄰的線(xiàn)性調(diào)整技術(shù),結(jié)合穩(wěn)健的組合預(yù)測(cè),來(lái)改進(jìn)現(xiàn)有的 K-近鄰非參數(shù)回歸預(yù)測(cè),以期達(dá)到提高實(shí)時(shí)性、預(yù)測(cè)可靠性等效果,特別是改善大波動(dòng)交通流的預(yù)測(cè)效果.
將觀察或測(cè)量得到的輸入-輸出時(shí)間序列對(duì)記為[X ( s), Y ( s )],s=1,…,n 是正整數(shù),稱(chēng)它們?yōu)閷W(xué)習(xí)樣本.對(duì)于某給定的輸入 X ( t)、預(yù)測(cè)輸出 Y ( t) ,K-近鄰方法首先按照距離找到最靠近 X ( t)的K個(gè) X ( s),s=s1,…,sK.預(yù)測(cè)結(jié)果為
改進(jìn) K-近鄰預(yù)測(cè)的 2個(gè)主要熱點(diǎn)是 K個(gè)近鄰X( s)的優(yōu)選以及由 K個(gè) Y ( s)形成預(yù)測(cè)結(jié)果( t)的方法.
現(xiàn)有選擇 K個(gè)近鄰 X ( s)的方法,大多數(shù)是以“距離”為標(biāo)準(zhǔn)的.這里的距離,用數(shù)學(xué)語(yǔ)言講,就是一種“范數(shù)”.最常見(jiàn)的是歐幾里德距離(2-范數(shù)).以公路交通流預(yù)測(cè)為例,X ( s)可以是某些歷史的交通流數(shù)據(jù),或者是考慮天氣、星期等的影響因子.只以距離為選擇標(biāo)準(zhǔn),會(huì)有如下4個(gè)不足.
(1) 對(duì)于波動(dòng)大的交通流,難以找到高質(zhì)量的K-近鄰.同時(shí)需要過(guò)長(zhǎng)的歷史數(shù)據(jù),從而使得距離小的各近鄰,由于相距時(shí)間太久帶來(lái)的交通流性質(zhì)變化,不利于提高預(yù)測(cè)效果,即難以均衡“搜索時(shí)間”和“K-近鄰的相似性”之間的矛盾.
(2) 采用標(biāo)準(zhǔn)差(方差的開(kāi)方)進(jìn)行原始交通流折算,以消除不同天的交通流波動(dòng)性[1,3].對(duì)于樣本容量比較小的 X ( s),方差估計(jì)的置信區(qū)間比較長(zhǎng),即標(biāo)準(zhǔn)差計(jì)算的真實(shí)性不理想.
(3) 距離(范數(shù))只反映當(dāng)前點(diǎn)和 K-近鄰的“靠近性”,不直接反映它們之間的“形狀相似性”.而形狀相似性則直接反映交通流的變化發(fā)展規(guī)律.
(4) 為了提高“K-近鄰的相似性”,文獻(xiàn)[9-10]采用增加相關(guān)系數(shù)作為評(píng)價(jià)標(biāo)準(zhǔn).這樣雖然提高了K-近鄰的相似性,但是以增大歷史數(shù)據(jù)的搜索(降低實(shí)時(shí)性)為代價(jià)的.
具體的選擇方法有聚類(lèi)[7,11]和平衡二叉樹(shù)[13].
本文的改進(jìn)為:只采用相關(guān)系數(shù)作為選擇 K-近鄰的標(biāo)準(zhǔn).具體方法是將文獻(xiàn)[9-10]中的“距離”步驟跳過(guò),只保留相關(guān)系數(shù)作為評(píng)價(jià)標(biāo)準(zhǔn).這樣改進(jìn)的優(yōu)點(diǎn)有 2個(gè):①相關(guān)系數(shù)的幾何意義是 X ( t)與近鄰間“形狀的線(xiàn)性相似性”[16],它直接反映交通流的發(fā)展規(guī)律,用最大正相關(guān)系數(shù)選擇的各 K-近鄰,在交通流的具體數(shù)值上可以有很大的差異,從而改善了“大波動(dòng)”情況下 K-近鄰的優(yōu)選,這樣就省去了用標(biāo)準(zhǔn)差折算歷史數(shù)據(jù)的預(yù)處理,提高了實(shí)時(shí)性;②由于相關(guān)系數(shù)可以將數(shù)值差異很大的 K-近鄰選擇進(jìn)來(lái),使搜索需要的歷史數(shù)據(jù)量減少,不僅提高了實(shí)時(shí)性,還提高了 K-近鄰間的相似性,即有利于克服交通流性質(zhì)的長(zhǎng)期變化引起的不利影響.
這種方法等效于將每天的交通流標(biāo)準(zhǔn)化:用每天的交通流平均值,對(duì)全天交通流折算,消除了“大波動(dòng)”交通流按照“距離”選擇K-近鄰的困難.
除了采用式(1)的直接平均外,還可以采用各種先進(jìn)方法替換式(1)以得到更好的預(yù)測(cè)效果.現(xiàn)有的方法包括當(dāng)前模式與近鄰間的歐式距離調(diào)整[1,12]、相似度調(diào)整[13]等.
本文的2類(lèi)改進(jìn)是:①采用當(dāng)前模式和 K-近鄰的歐氏距離,調(diào)整各K-近鄰對(duì)應(yīng)的預(yù)測(cè)值,這等價(jià)于用每天交通流的平均值,再折算回實(shí)際的歷史交通流數(shù)據(jù),它對(duì)應(yīng)組合預(yù)測(cè)策略中的簡(jiǎn)單平均法[17-18];②采用當(dāng)前模式和 K-近鄰的方差,按照組合預(yù)測(cè)策略中的方差倒數(shù)法合成預(yù)測(cè)的結(jié)果[17-18],具體方法見(jiàn)式(2).
實(shí)際上,各 K-近鄰對(duì)應(yīng)的其后交通流,就是待預(yù)測(cè)交通流的一個(gè)預(yù)測(cè)值.本文采用組合預(yù)測(cè)策略代替式(1)進(jìn)行預(yù)測(cè),與現(xiàn)有其他改進(jìn)方法相比較為簡(jiǎn)單,且預(yù)測(cè)效果好.
方差倒數(shù)法合成 K-近鄰預(yù)測(cè)的具體方法如下所述.本文只采用歷史交通流,未考慮其他影響,故Y( s)就是 X ( s).
記K個(gè)近鄰 X ( s)對(duì)應(yīng)交通流 Y ( s)在(t+1)點(diǎn)的數(shù)值為 y ( t + 1 ),則預(yù)測(cè)值為
式中:ai是組合預(yù)測(cè)中的方差倒數(shù)法的系數(shù)[17-18],
即組合預(yù)測(cè)中的簡(jiǎn)單平均法.進(jìn)一步,若各 bi=0,式(3)就退化成式(1).
本文改進(jìn)的主要數(shù)學(xué)基礎(chǔ)是數(shù)理統(tǒng)計(jì)學(xué)[17]和穩(wěn)健統(tǒng)計(jì)學(xué)[19].
當(dāng)近鄰 X ( s)對(duì)應(yīng)的交通流點(diǎn)數(shù)不多時(shí),可認(rèn)為其概率密度函數(shù)近似不變(近似平穩(wěn)的).這樣,無(wú)論是歐氏距離、方差,還是相關(guān)系數(shù)的計(jì)算,得到的只是其真實(shí)值的“點(diǎn)估計(jì)”值,即各統(tǒng)計(jì)量的真實(shí)值,是分布在該“點(diǎn)估計(jì)”值周?chē)?置信區(qū)間).而置信區(qū)間的長(zhǎng)度,隨著樣本容量的增大而明顯變?。粲洏颖救萘繛?N,則置信區(qū)間的長(zhǎng)度可以按照1或類(lèi)似的方式減?。?/p>
特別地,實(shí)際交通流歷史數(shù)據(jù)中總存在一些outliers(離群值、異常數(shù)據(jù)),它們使統(tǒng)計(jì)量真實(shí)值和估計(jì)值的差異更明顯.增大樣本容量、采用統(tǒng)計(jì)量的穩(wěn)健估計(jì)方法是改進(jìn)估計(jì)值的 2種有效途徑.由于增大樣本容量會(huì)降低實(shí)時(shí)性,并增大交通流數(shù)據(jù)性質(zhì)變化引起的誤差,所以應(yīng)優(yōu)先采用穩(wěn)健估計(jì)方法.標(biāo)準(zhǔn)差穩(wěn)健估計(jì)的具體計(jì)算方法可參見(jiàn)文獻(xiàn)[19],本文采用的有下面式(4)~(7).
K-近鄰的相關(guān)系數(shù)選擇方法直接解決了各天交通流大波動(dòng)的不良影響.
(1) 省去了原始交通流數(shù)據(jù)按每天“標(biāo)準(zhǔn)差”折算的預(yù)處理;
(2) 由于平均值估計(jì)的置信區(qū)間明顯比方差估計(jì)的置信區(qū)間窄[16,19],從而有效提高了估計(jì)的準(zhǔn)確性;在下一步的預(yù)測(cè)中,采用平均值折算預(yù)測(cè)的效果會(huì)得到提高;
(3) 減小了預(yù)測(cè)必須采用的歷史數(shù)據(jù)量,降低了交通流的長(zhǎng)期變化對(duì)預(yù)測(cè)的不利影響.
穩(wěn)健統(tǒng)計(jì)是數(shù)理統(tǒng)計(jì)學(xué)的一個(gè)分支,研究當(dāng)樣本數(shù)據(jù)總體假定稍有變動(dòng)及記錄數(shù)據(jù)有失誤時(shí),統(tǒng)計(jì)方法的適應(yīng)性問(wèn)題,即主要研究對(duì)總體分布的穩(wěn)健性和對(duì)異常數(shù)據(jù)的穩(wěn)健性.交通流是復(fù)雜時(shí)間序列,其“總體分布”是隨時(shí)間變化的;且交通流含有較高的異常數(shù)據(jù)(outliers).采用穩(wěn)健統(tǒng)計(jì)方法,可以明顯抑制這些干擾的不利影響[19].如按照定義計(jì)算σ,在 5%的干擾下,計(jì)算值會(huì)是實(shí)際值的 2倍以上.總之,樣本容量有限、預(yù)測(cè)誤差的概率分布函數(shù)不可知、異常數(shù)據(jù)這 3種影響因素決定了方差和相關(guān)系數(shù)在實(shí)際工作中不能準(zhǔn)確求出.采用穩(wěn)健統(tǒng)計(jì)方法,可顯著提高方差和相關(guān)系數(shù)計(jì)算值的真實(shí)性.
預(yù)測(cè)式(2)中需要第i個(gè)近鄰 X ( si)標(biāo)準(zhǔn)差σ的估計(jì).穩(wěn)健統(tǒng)計(jì)中σ常見(jiàn)的穩(wěn)健估計(jì)方法[19]有
圖 1(a)是某公路 33,d的 3,min統(tǒng)計(jì)間隔交通流;圖 1(b)是按照“每天平均值”折算后的相對(duì)值.容易驗(yàn)證,按“每天平均值”折算后的相對(duì)值,比采用“標(biāo)準(zhǔn)差”的折算值更平穩(wěn).
圖 2是該交通流最后 3天的小波周期圖.根據(jù)時(shí)間序列分析中的 Wold分解定理(1938年)和Cramer分解定理(1961年),交通流可以分解為“復(fù)雜的信號(hào)(確定的和隨機(jī)的)+白噪聲”.其中的白噪聲形成一個(gè)目前任何科技方法都不能預(yù)測(cè)的誤差極限.目前還沒(méi)有可靠的方法來(lái)精確分離出白噪聲.
從工程角度看,采用小波去噪方法可以近似分離白噪聲.這可用于客觀地評(píng)價(jià)某預(yù)測(cè)方法的效果.
圖2 交通流最后3天的小波周期Fig.2 Wavelet transform of the latest 3 days of traffic flow
采用最后 3天每天下午 16:38—19:12(第 0.7~0.8天)共48點(diǎn)的數(shù)據(jù)作為預(yù)測(cè)對(duì)象.表1為采用小波去噪得到的預(yù)測(cè)誤差極限,即交通流中包含的白噪聲引起的預(yù)測(cè)誤差.其中 MPE是平均百分誤差(mean percentage error),MAPE是平均絕對(duì)百分誤差(mean absolute percentage error).
表1 小波去噪得到的預(yù)測(cè)誤差極限Tab.1 Forecasting error limits estimated by wavelet denoise
第31~33天每天上述48點(diǎn)滾動(dòng)預(yù)測(cè)采用 X ( s)的樣本容量為20,近鄰個(gè)數(shù) K=6.采用本文改進(jìn)方法得到的預(yù)測(cè)誤差見(jiàn)表2.s、dn、MAD、df、sbi依次表示方差倒數(shù)法中標(biāo)準(zhǔn)差計(jì)算采用的方法,見(jiàn)公式(4)~(7).
可見(jiàn),由于交通流的波動(dòng)性、存在離群值,簡(jiǎn)單平均法和非穩(wěn)健的方差倒數(shù)法 s預(yù)測(cè)效果不如穩(wěn)健的方差倒數(shù)法 dn、MAD、df、sbi效果好.
表2 本文方法的預(yù)測(cè)誤差Tab.2 Forecasting errors by the proposed methods in this paper
圖 3為第 33天采用 dn進(jìn)行方差倒數(shù)法預(yù)測(cè)的結(jié)果.
可見(jiàn),預(yù)測(cè)值的波動(dòng)比實(shí)際交通流小,因?yàn)閷?shí)際交通流里包含白噪聲的瞬時(shí)值是不能預(yù)測(cè)的.
圖3 第33.7—33.8天的交通流歷史數(shù)據(jù)與預(yù)測(cè)值Fig.3 Forecasting data and the original traffic flow Fig. 3 between the 33.7 and the 33.8 days
K-近鄰非參數(shù)回歸預(yù)測(cè)是一種受到廣泛重視的公路短時(shí)交通流預(yù)測(cè)方法.本文對(duì) K-近鄰非參數(shù)回歸預(yù)測(cè)方法做了如下改進(jìn).①直接采用相關(guān)系數(shù)進(jìn)行 K-近鄰的選擇.不僅減少了數(shù)據(jù)的預(yù)處理,還適用于大波動(dòng)的數(shù)據(jù),減少了預(yù)測(cè)所必須的歷史數(shù)據(jù).②K個(gè)近鄰對(duì)應(yīng)的下一點(diǎn)歷史數(shù)據(jù),調(diào)整后就是待預(yù)測(cè)交通流的 K個(gè)預(yù)測(cè)值.采用組合預(yù)測(cè)的方差倒數(shù)法合成它們,可以得到好的預(yù)測(cè)結(jié)果.③為了降低離群值的不利影響,可以采用穩(wěn)健統(tǒng)計(jì)的方法來(lái)計(jì)算各標(biāo)準(zhǔn)差的估計(jì)值.結(jié)果表明,采用穩(wěn)健統(tǒng)計(jì)的方差倒數(shù)法,具有較為穩(wěn)定的預(yù)測(cè)效果,可以提高預(yù)測(cè)準(zhǔn)確率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]張曉利,賀國(guó)光. 考慮交通吸納點(diǎn)的非參數(shù)回歸組合型短時(shí)交通流預(yù)測(cè)方法[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]周小鵬,馮 奇,孫立軍. 基于最近鄰法的短時(shí)交通流預(yù)測(cè)[J]. 同濟(jì)大學(xué)學(xué)報(bào):自然科學(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ù)回歸的短時(shí)交通流量預(yù)測(cè)與事件檢測(cè)綜合算法[J]. 中國(guó)公路學(xué)報(bào),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]范魯明,賀國(guó)光. 改進(jìn)的K近鄰非參數(shù)回歸在短時(shí)交通流量預(yù)測(cè)中的應(yīng)用[J]. 長(zhǎng)沙交通學(xué)院學(xué)報(bào),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]范魯明,賀國(guó)光. 改進(jìn)非參數(shù)回歸在交通流量預(yù)測(cè)中的應(yīng)用[J]. 重慶交通大學(xué)學(xué)報(bào):自然科學(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]李振龍,張利國(guó),錢(qián)海峰. 基于非參數(shù)回歸的短時(shí)交通流預(yù)測(cè)研究綜述[J]. 交通運(yùn)輸工程與信息學(xué)報(bào),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]張曉利,賀國(guó)光,陸化普. 基于K-鄰域非參數(shù)回歸短時(shí)交通流預(yù)測(cè)方法[J]. 系統(tǒng)工程學(xué)報(bào),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]王 進(jìn),史其信. 短時(shí)交通流預(yù)測(cè)模型綜述[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ù)測(cè)方法綜述[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]唐小我,馬永開(kāi),曾 勇,等. 現(xiàn)代組合預(yù)測(cè)和組合投資決策方法及應(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]. 陳忠璉,郭德媛,譯. 北京:中國(guó)統(tǒng)計(jì)出版社,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).