基于非參數(shù)回歸的短時交通流預測模型

基于非參數(shù)回歸的短時交通流預測模型

0在線非參數(shù)訓練根據(jù)研究方法，以前的長期交通流預測算法可分為歷史平均值法、回歸預測法、神經(jīng)網(wǎng)絡(luò)預測法、時間序列法、卡爾曼濾波法、綜合預測算法等。其中歷史均值法、回歸預測法都較為簡單,參數(shù)可采用最小二乘法估計,計算簡便,但它們都未能反映交通流過程的不確定性與非線性,尤其無法克服隨機干擾因素的影響。神經(jīng)網(wǎng)絡(luò)預測法包括采用BP網(wǎng)絡(luò)、模糊神經(jīng)網(wǎng)絡(luò)和高階神經(jīng)網(wǎng)絡(luò)延時單元神經(jīng)網(wǎng)絡(luò),但總體來說,其參數(shù)訓練非常復雜,計算時間也太長,不適合在線應(yīng)用?？柭鼮V波法和時間序列法是人們提出的精度較高、實時性較強的預測算法,但其初始參數(shù)調(diào)整太復雜。就拿SARIMA來說,僅調(diào)整一個單點的參數(shù)(p,d,q,P,D,Q)就需6d,60個點就需一年。另外,所有的上述方法都屬于參數(shù)模型,都需要復雜的參數(shù)估計,而且計算出的這些參數(shù)僅僅適合某點,不能移植。所以,研究一種參數(shù)估計簡單、可移植性的預測算法非常必要。非參數(shù)回歸是近幾年興起的一種適合不確定性的、非線性的動態(tài)系統(tǒng)的非參數(shù)建模方法。它本身脫胎于混沌理論。它所應(yīng)用的場合是:不需先驗知識,只需足夠的歷史數(shù)據(jù)。它尋找歷史數(shù)據(jù)中與當前點相似的“近鄰”,并用那些“近鄰”預測下一個時刻的流量。該算法認為系統(tǒng)所有的因素之間的內(nèi)在聯(lián)系都蘊涵在歷史數(shù)據(jù)中,因此直接從歷史數(shù)據(jù)中得到信息而不是為歷史數(shù)據(jù)建立一個近似模型。也就是說非參數(shù)建模沒有將歷史數(shù)據(jù)作平滑處理,因此,特別是在有特殊事件發(fā)生時,預測效果要比參數(shù)建模精確。1995年SMITH將之應(yīng)用于單點短時交通流預測,但因其搜索速度太慢和試湊的參數(shù)調(diào)整方法而沒有得到真正實用。隨后學者們又提出了很多的改進辦法,比如通過重新組織歷史數(shù)據(jù)結(jié)構(gòu)或者采取不精確查找的方法。1在線數(shù)據(jù)分析預測算法圖1是基于K近鄰的交通流預測與事件檢測綜合算法框架。其流程是:首先由歷史數(shù)據(jù)庫經(jīng)數(shù)據(jù)修正及精簡形成樣板數(shù)據(jù)庫,即首先完成離線數(shù)據(jù)準備工作。然后在線采集動態(tài)數(shù)據(jù),經(jīng)過“數(shù)據(jù)過濾”和數(shù)據(jù)修正后,通過基于K近鄰的搜索匹配找到K個近鄰,而后采用預測算法預測下一個時刻的交通量。把下一個時刻的交通量與當前預測的交通量相比較,如果距離大于一定范圍,則證明有異常情況發(fā)生。此算法共有五個關(guān)鍵步驟:歷史數(shù)據(jù)準備及樣板數(shù)據(jù)庫的生成、數(shù)據(jù)過濾;狀態(tài)向量定義;K近鄰搜索;預測算法;事件檢測算法。2rtms數(shù)據(jù)采集現(xiàn)場試驗的地點是北京市西三環(huán)紫竹橋路段,如圖2所示。前后連接北京的幾條重要普通干道,交通非常繁忙,這里可以觀察到所有交通狀況下的交通數(shù)據(jù)。數(shù)據(jù)采集方案如圖3所示。采用點對點的數(shù)據(jù)采集方案,即RTMS(遠程微波交通傳感器)數(shù)據(jù)輸出串口與CDPDModem1連接,然后通過無線專用數(shù)據(jù)網(wǎng)CDPD將數(shù)據(jù)傳送給遠端的另一臺CDPDModem2,然后CDPDModem2與遠程的數(shù)據(jù)采集和預處理計算機通過串口相連收集由CDPD無線網(wǎng)傳送到的RTMS的數(shù)據(jù)。RTMS可以同時輸出一定統(tǒng)計周期內(nèi)的平均車速、流量、車輛占有率。設(shè)定RTMS的統(tǒng)計周期為5min,從2001年8月到2001年11月連續(xù)三個月收集交通數(shù)據(jù),共25920組數(shù)據(jù)。2.1平均生產(chǎn)率通常由于交通傳感器硬件故障、噪聲干擾和通訊故障所引發(fā)錯誤數(shù)據(jù)的發(fā)生。所以必須對錯誤數(shù)據(jù)進行剔除。否則,這些錯誤數(shù)據(jù)會大大降低預測的準確度。筆者所采用的方法是:閥值法和基于采用多條規(guī)則的判斷。錯誤數(shù)據(jù)的發(fā)生一般是由于硬件故障或噪聲干擾所引起,所以往往與正確數(shù)據(jù)的偏差非常大,基于這個特點,首先采用閥值法去除明顯錯誤的數(shù)據(jù)。比如:交通流量,5min內(nèi)4車道其最大車流量為600輛,換算成單車道的流量為1800veh/h,可以采用2000veh/h作為流量的閥值。平均占有率:0~100。顯然,如果數(shù)據(jù)在閥值之內(nèi),也未必是正確數(shù)據(jù),所以進行下面基于多條規(guī)則的判斷。判斷規(guī)則如下:(1)如果平均占有率為0,而流量不為0。(2)如果流量為0,而平均占有率不為0。(3)平均車長判斷法:如果采用交通機理公式由流量、速度、占有率得出平均車長,如果所得的車長小于等于5m或者大于等于12m(此時重型車輛占居優(yōu)勢),那么這條記錄是正確的。通過數(shù)據(jù)過濾,得到了正確的歷史數(shù)據(jù)庫,但是這個數(shù)據(jù)庫還不能作為樣板數(shù)據(jù)庫,因為它是不精簡的,在一種交通狀況下的同類數(shù)據(jù)點非常多(這些數(shù)據(jù)非常的相近,距離小于10),這些點僅僅在浪費存儲空間和搜索時間,所以必須把這些數(shù)據(jù)精簡。作為將來進行數(shù)據(jù)匹配的樣板歷史數(shù)據(jù)庫,其內(nèi)含的“樣板”一定要足夠多而精。所謂多:它應(yīng)該包含該點在各種環(huán)境條件下的交通流數(shù)據(jù)。這一點可通過長時間全天的采集數(shù)據(jù)得到保證。所謂精:出于實時性的考慮,歷史數(shù)據(jù)庫不能太龐大。所以可以適當精簡數(shù)據(jù)以提高算法的實時性。如何做到數(shù)據(jù)多而精呢?下面通過定義數(shù)據(jù)密集度這個指標來評價歷史數(shù)據(jù)庫中數(shù)據(jù)的分布是否可以作為樣板數(shù)據(jù)庫。密集度M:對歷史數(shù)據(jù)庫中的所有點i的在以距離R為半徑的區(qū)域內(nèi)的近鄰ni的算術(shù)平均。對于邊緣的數(shù)據(jù)點為2ni。即M=(∑i=1Nni)/NΜ=(∑i=1Νni)/Ν,這里的半徑R根據(jù)需求而定,例如筆者取R=20,則此處的M為半徑為20以下的密集度。如果密集度大于10,即任何一點的在R范圍內(nèi)的最近鄰不小于10,則認為此歷史數(shù)據(jù)庫的數(shù)據(jù)密集度滿足樣板數(shù)據(jù)庫的需求了。否則必須繼續(xù)收集數(shù)據(jù),直到密集度達到所需指標。2.2狀態(tài)向量四部分影響流量的因素非常多,比如:速度、道路占有率、天氣情況(溫度、濕度、雨、雪、霧),為了計算簡單,通常選擇與流量最為相關(guān)的因素。因此,通過計算其他各個變量與流量的相關(guān)系數(shù)來選擇相關(guān)變量,相關(guān)系數(shù)如表1所示。由上述相關(guān)系數(shù),可以選出相關(guān)變量:當前流量、速度和占有率。X(t)向量的組成為[v(t),v(t-1),s(t),s(t-1),o(t),o(t-1),w(t),w(t-1),vh(t),vh-1(t),sh(t),sh(t-1),oh(t),oh(t-1)]式中:v(t)、v(t-1)分別為當前時刻和前一時刻的流量值;vh(t)、vh(t-1)分別為歷史上這一時刻和前一時刻的流量平均值;s(t)、s(t-1)分別為當前時刻和前一時刻的速度值;sh(t)、sh(t-1)分別為歷史上這一時刻和前一時刻的速度平均值;o(t)、o(t-1)分別為當前時刻和前一時刻的平均占有率值;oh(t)、oh(t-1)分別為歷史上這一時刻和前一時刻的平均占有率的平均值。可以看出狀態(tài)向量中包含四部分信息:當前時刻信息、前一時刻的信息、歷史上當前時刻的平均值信息、歷史上前一時刻的平均值信息。其中歷史信息是決定該時刻系統(tǒng)狀態(tài)大體走勢的部分,而當前時刻信息和前一時刻信息是由于系統(tǒng)的隨機性而導致的系統(tǒng)波動的成分。即當前點通過基本走勢和波動兩部分信息在歷史數(shù)據(jù)庫中找尋近鄰。當然,歷史數(shù)據(jù)庫的字段也需要做調(diào)整,它包含狀態(tài)向量中的14個元素。2.3建立嚴格的數(shù)學模型K近鄰法則是一種基于數(shù)據(jù)的非參數(shù)回歸方法,它并非建立一種數(shù)學預測模型,而是尋找與當前變量值相匹配的K個最近鄰的數(shù)據(jù)并以該K個數(shù)據(jù)對變量下一個時刻的值進行預測。在該方法中,建立嚴格的數(shù)學模型不再必須,因為很顯然豐富的數(shù)據(jù)中已經(jīng)包含了預測所必須的信息。但究竟K值取多大為最優(yōu)值?筆者在下面會有詳細的解釋,取K=5。2.4平均貢獻率筆者采用基于相關(guān)系數(shù)加權(quán)的歐式距離。從以上的各個變量與未來流量的相關(guān)系數(shù)中可以看到各個變量對于未來流量的影響是不同的。當前流量對未來流量的影響最大,而占有率對未來流量的影響最小。所以在利用普通歐式距離尋找匹配點時,就不能反映出各個變量對未來流量所做貢獻的差異。因此,筆者采用基于相關(guān)系數(shù)加權(quán)的歐式距離,公式如下d=rvv[v(t)?vi(t)]2+?+rvo[o(t?1)?oi(t?1)]2rvv+rvs+rvo????????????????????????√d=rvv[v(t)-vi(t)]2+?+rvo[o(t-1)-oi(t-1)]2rvv+rvs+rvo2.5didvit式筆者采用基于匹配距離倒數(shù)的加權(quán)平均法,用公式表達如下v(t+1)=∑i=1K1didvi(t)v(t+1)=∑i=1Κ1didvi(t)式中:d=∑i=1K1did=∑i=1Κ1di。匹配距離越小的點,也就是越相似的點給予的加權(quán)越大。2.6采樣值與歷史平均值的關(guān)系筆者采用先預測后判斷的方法。如果預測結(jié)果與下一個時刻的交通流實測值相差非常大,那么可以斷定有事件發(fā)生,事件何時中止?把采樣周期縮短,并把采樣值與歷史平均值相比較,如果差異大于一定值,那么事件繼續(xù)存在,如果相差小于一定值,那么事件中止。2.7流量系數(shù)的計算采集的數(shù)據(jù)如圖4所示,出于便于觀察的考慮,用流量與占有率的兩維散點圖表示。由于錯誤數(shù)據(jù)的存在,整個曲線的形狀似乎不符合交通規(guī)則,所以此時非常重要的工作就是剔出錯誤數(shù)據(jù)。由于此處的道路通行能力已知,所以首先根據(jù)閥值法剔除錯誤數(shù)據(jù)。流量數(shù)值的范圍(0~2000)剔出錯誤數(shù)據(jù),然后采用規(guī)則判斷,結(jié)果如圖5所示?？梢钥闯?經(jīng)過錯誤剔出,得到比較理想的數(shù)據(jù)曲線,它可以作為流量預測的歷史數(shù)據(jù)。2.8預測結(jié)果為了試驗方便,直接采用了從RTMS輸出的原始數(shù)據(jù),即30s內(nèi)斷面通過的車輛數(shù)。圖6中也采用RTMS輸出的原始數(shù)據(jù)。2.9因子參數(shù)和平均配比誤差計算了在K=5時的平均絕對誤差AAE(AverageAbsoluteError)和平均百分比誤差APE(AveragePercentError)。AAE=156,APE=7.91%。2.10k的最優(yōu)值的計算接下來,逐漸增加K值,觀察K值的選取對預測精度的影響。當然這是在歷史數(shù)據(jù)庫中樣本覆蓋全范圍而且足夠豐富的情況下才能做此比較。由圖7可知,隨著K值的增加,特別是從1增加到5時,預測精度大幅度提高,而后從5到10,預測精度逐漸提高,最終到達最佳預測精度,此時平均絕對誤差為142veh/h。圖8是K從7到10的選取過程中流量預測曲線。隨著K值的增加,其預測精度逐漸下降。從K值的選取中可以看出,交通流量是一個累計量,它不會突變,所以K值不能太大。但是它的確受到人為因素等各種因素的影響,短時波動還是比較大的,所以K值不能太小。但K的最優(yōu)值究竟由什么因素決定的呢?是樣板數(shù)據(jù)庫中的數(shù)據(jù)!因為非參數(shù)回歸中所有的歷史經(jīng)驗都蘊涵在歷史數(shù)據(jù)中,如何利用這些歷史數(shù)據(jù)呢?也就是如何選擇K的大小是保證預測精度的關(guān)鍵,那么歷史數(shù)據(jù)與K的最優(yōu)值之間又是什么關(guān)系呢?通過2.1中定義的密集度來推出它們之間的關(guān)系。通過大量的試驗,得出如圖9所示的曲線。由圖9可以看出,K的最優(yōu)值在[1,12]之間與密集度為線性關(guān)系,在此區(qū)間內(nèi),K=M,而當12<M<20時,K的最優(yōu)值只有微小的增加,當M>20,K值幾乎保持不變。由此得出結(jié)論:如果歷史數(shù)據(jù)庫的數(shù)據(jù)密集度M在[1,12],則取K=M,如果12<M<20,則取K=round(12M+6)(12Μ+6)。其中round(·)為取整函數(shù)。實際上,當M>20時,因為此數(shù)據(jù)庫中數(shù)據(jù)過于密集,考慮算法的實時性和計算機資源的問題,這時首先要對該數(shù)據(jù)庫進行精簡工作。當數(shù)據(jù)庫中的密集度小于10,也就是密集度太低時,此時的預測精度不高,這時必須通過補充數(shù)據(jù)或在線學習的方法來提高數(shù)據(jù)庫的密集度。2.11基于散調(diào)查和散列函數(shù)的創(chuàng)建歷史網(wǎng)絡(luò)結(jié)構(gòu)盡管非參數(shù)法實現(xiàn)了盡量少的參數(shù),實現(xiàn)了可移植性,保證了較高的精度,但是距離實用還有一段距離。其實時性需要進一步提高,其參數(shù)調(diào)整機制需進一步改進。為提高其實時性對該算法做了如下改進:2.11.1基于動態(tài)聚類算法的歷史數(shù)據(jù)的分類采用K均值算法的動態(tài)聚類算法。將數(shù)據(jù)分為很多類。然后當前點只需與類的中心相比較,找到最近的聚類中心,然后在這個類中尋找最近鄰。2.11.2基于散列表的歷史數(shù)據(jù)優(yōu)化結(jié)構(gòu)散列表,又稱為哈希表,是線性表中一種重要的存儲方式和檢索方法。在散列表中,可以結(jié)點進行快速檢索。散列表算法的基本思想是:由結(jié)點的關(guān)鍵碼值決定結(jié)點的存儲地址,即以關(guān)鍵碼值m為自變量,通過一定的函數(shù)關(guān)系h(稱為散列函數(shù)),計算出對應(yīng)的函數(shù)值h(m),將這個值解釋為結(jié)點的存儲地址,將結(jié)點存入該地址內(nèi),檢索時,根據(jù)要檢索的關(guān)鍵碼值,用同樣的散列函數(shù)計算出地址,然后,到相應(yīng)的地址中去獲取要尋找的結(jié)點數(shù)據(jù)。因此,散列表有一個重要的特征:平均檢索的長度不直接依賴于表中元素的個數(shù)。將步驟1內(nèi)的聚類中心的所有的流量字段與存儲地址L(L=1,2,…,n)做多元線性回歸分析,得到如下的散列函數(shù)L=a1v(t)+a2v(t-1)+a3vh(t)+a4vh(t-1)所以現(xiàn)在的歷史數(shù)據(jù)庫中數(shù)據(jù)的組織結(jié)構(gòu)如圖