基于數(shù)據(jù)約減和支持向量機的非參數(shù)回歸短時交通流預測算法

吳晉武，張海峰，冉旭東

(1.天津大學 智能與計算學部，天津 300072;2.北京空間科技信息研究所，北京 100094；3.天津大學 管理與經(jīng)濟學部，天津 300072；4.深圳市易行網(wǎng)交通科技有限公司，廣東 深圳 518057)

0 引言

城市路網(wǎng)的交通流系統(tǒng)具有非線性、時變等特性。對于預測時間小于15 min的短時預測，不僅要考慮狀態(tài)變量、控制變量與預測流量之間的映射關系，而且也要考慮流量的時變特性。采樣時間越短(<5 min)時，各種干擾因素對流量預測的影響也就越強，當空間位置、道路環(huán)境越復雜且在高峰時段時，其交通流量的不確定性愈為突出，而且會受到許多因素的影響，因此，交通流短時預測算法一直是智能交通中的重要研究領域[1-6]。盡管近年來深度學習方法得到了極大的重視[3-6]，但非參數(shù)回歸方法在交通流預測中仍然能發(fā)揮不錯的作用[7]，這是因為非參數(shù)回歸方法以交通流量存在自重復性和時間連續(xù)性的特點為前提，通過構造模式庫直接從歷史數(shù)據(jù)中提取原因與結果的映射，在數(shù)據(jù)量足夠的情況下精度較高，而且具有很高的魯棒性，能夠較好地應對短時交通流的非線性和不確定性。與深度學習方法相比，非參數(shù)回歸方法對數(shù)據(jù)類型和數(shù)據(jù)質(zhì)量的要求不高，不需要復雜的模型構建和訓練過程，對前期數(shù)據(jù)準備和硬件要求低，在實際的交通流預測任務中實用性更強。尤其在現(xiàn)階段交通大數(shù)據(jù)來源多(包括檢測器、視頻、信令等)、數(shù)據(jù)量大且實時性強、但數(shù)據(jù)質(zhì)量參差不齊的背景下，非參數(shù)回歸算法可以在不對現(xiàn)有軟硬件進行大幅修改的條件下融入現(xiàn)有智能交通系統(tǒng)體系，提供性能較好的交通預測能力。

非參數(shù)回歸方法因其自身的眾多優(yōu)點，一直是交通流預測領域中的重要方法。Clark等[8]將單變量預測擴展到多變量預測，并討論了選擇近鄰個數(shù)、數(shù)據(jù)可遷移性等問題。Kim[9]考慮了歷史狀態(tài)對于非參數(shù)回歸預測特征向量的影響，提高了預測效果。張曉利[10]提出了一種基于小波分析與神經(jīng)網(wǎng)絡的交通流量預測方法，針對多維神經(jīng)網(wǎng)絡映射學習極易產(chǎn)生維數(shù)災難問題給出了有效的解決方法。Turochy[11]在非參數(shù)回歸預測中考慮交通狀態(tài)信息，提高了算法的預測精度。張曉利等[12]提出了一種結合主成分分析和組合神經(jīng)網(wǎng)絡的交通流量預測方法，并且證明了其結果優(yōu)于BP網(wǎng)絡的優(yōu)勢。Zheng[13]在非參數(shù)回歸預測中的結果生成階段引入線性主成分方法，提高了預測精度。張曉利等[14]利用聚類算法和平衡二叉樹建立案例數(shù)據(jù)庫，提出了一種基于平衡二叉樹的K-鄰域非參數(shù)回歸(KNN-NPR)方法，提高了預測的精度和實時性。

然而，在實際交通流量預測任務中，若采用非參數(shù)回歸方法的標準過程會產(chǎn)生其他問題。首先，當數(shù)據(jù)量巨大，特別是在歷史數(shù)據(jù)積累較多的情況下，數(shù)據(jù)匹配時間過長，無法滿足預測實時性要求。其次，數(shù)據(jù)維數(shù)高，容易產(chǎn)生維數(shù)災難問題，導致無法匹配到合乎要求的相似模式，使預測失敗。此外，在基于搜索到的相似模式進行預測時，對預測變量直接進行平均，會帶來一定的預測誤差。針對以上缺陷，在一般K-鄰域非參數(shù)回歸算法基礎上，進行了如下改進：(1)使用減法模糊聚類(Subtraction Fuzzy Clustering，F(xiàn)CM)方法，對歷史數(shù)據(jù)進行聚類，使用聚類中心點數(shù)據(jù)而不是所有數(shù)據(jù)構造模式庫，可大大減少模式庫的數(shù)據(jù)量。(2)采用主成分分析(PCA)方法降低模型的維度，可克服模式匹配速度較慢、無關維度干擾問題。(3)融合支持向量機方法，運用搜索到的K個模式估計最終待預測變量的值。運用仿真系統(tǒng)生成的實時大流量數(shù)據(jù)進行測試，發(fā)現(xiàn)改進后的算法能夠有效提升非參數(shù)回歸預測的實時性，并提高預測精度。

1 計算方法與算法框架

非參數(shù)回歸方法本身脫胎于混沌理論，是基于模式識別并且依靠數(shù)據(jù)驅動的智能方法。它不需要為歷史數(shù)據(jù)建立近似模型和大量參數(shù)估計，而是由測量對象的大量數(shù)據(jù)作為支持，是一種無模型預測方法。此種方法嘗試識別具有與預測時刻系統(tǒng)相同的輸入值或狀態(tài)的一組過去案例，或者查找與當前輸入X(t)類似的歷史數(shù)據(jù)“集群”，根據(jù)這“簇”數(shù)據(jù)的輸出值，決定預測值y(t+1)。此方法的關鍵是如何確定與預測時刻系統(tǒng)狀態(tài)最為相似的一“簇”歷史數(shù)據(jù)。通常，該最近鄰域包括距輸入狀態(tài)點最近的K個點。由此可以看出，任何兩次匹配的采樣時間可能是不同的，它總是選出與當前狀態(tài)模式最為匹配的歷史數(shù)據(jù)，因此非參數(shù)回歸方法實現(xiàn)了一定的動態(tài)預測。

本研究試圖在一般K-鄰域非參數(shù)回歸算法基礎上進行改進。采用的預測方法由主成分分析、模糊聚類、非參數(shù)回歸、樣本數(shù)據(jù)庫和調(diào)節(jié)回路等部分組成，各組成部分之間不僅相互聯(lián)系，而且每個組成部分又包括多個操作或算法，共同構成了預測的整體框架。算法框架如圖1所示。

圖1 預測算法總體框架Fig.1 Overall framework of prediction algorithm

1.1 基于主成分分析的數(shù)據(jù)降維

對路段流量進行非參數(shù)回歸預測的第1步是確定影響被測路段流量的因素。當路網(wǎng)結構復雜時，需要綜合考慮上游位置、時間延遲等諸多因素，可能產(chǎn)生影響的因素將達到幾十甚至上百個，模式庫中的模式維度也非常高，存在的潛在問題如下：(1)增加了每條模式占用的存儲空間；(2)在數(shù)據(jù)檢索時，由于維度高容易造成檢索不到合適的數(shù)據(jù)，并且降低了搜索速度；(3)因素是由先驗經(jīng)驗得到的，因此可能有些因素實際上與待預測變量并不相關，在影響路段流量的大量因素中，有些因素的影響力非常小，有的甚至可有可無，較高影響力因素可能僅限于幾個因素。如果不加區(qū)別地對待影響因素，就必然會消除重要因素的影響，降低預測的準確性；(4)由于許多指標變量間可能存在相關關系，問題的復雜性也隨之增加。如果分別分析每個指標，分析又可能是獨立進行的，而在實際中要求綜合處理。因此，應該簡化原始交通數(shù)據(jù)，同時確保不丟失重要信息和預測準確性。此時，主成分分析法(PCA)就非常適于此類問題。對主成分分析算法的具體原理介紹參見文獻[15-16]。

1.2 基于模糊聚類的原始數(shù)據(jù)篩選

采用模糊C均值聚類(FCM)算法[17]。通過對數(shù)據(jù)進行模糊劃分來聚類，更適于在數(shù)據(jù)比較密集或分類邊界不清晰的情況下使用。由模糊理論，用隸屬度來確定每個數(shù)據(jù)實例屬于某個類別的程度及其類矩陣U=(uij|i=1,2,…,n;j=1,2,…,k)，其中元素uij為第i個數(shù)據(jù)實例屬于第j類的隸屬程度，并滿足如下條件：

(1)

定義價值函數(shù)為：

(2)

式中，Jm為從每個數(shù)據(jù)實例到聚類中心距離的平方和；Xi為數(shù)據(jù)集I中的元素，Xi∈I；Cj為類中心，Cj∈I;uij為第i個數(shù)據(jù)實例屬于第j類的隸屬程度，其取值介于[0,1]之間，U={uij}是一個n×K矩陣；C={c1,c2,…，ck},ci為模糊組i的類中心；dij(Xi,Cj)為第i個數(shù)據(jù)實例與第j個類中心間的歐式距離；m為模糊系數(shù)(1≤m<∞)；k為預先設定的分類組數(shù)。

分組數(shù)量k需要在聚類之前提前確定。本研究用聚類密集性和聚類臨近性兩個指標衡量聚為k類時聚類效果的優(yōu)劣，對這兩個指標分別介紹如下。

聚類密集度用于衡量同一類中數(shù)據(jù)的緊密程度，給定一個數(shù)據(jù)集X，首先計算其數(shù)據(jù)的方差:

(3)

(4)

式中，C為聚類個數(shù)；var(ci)為簇ci的方差。

聚類鄰近性用于衡量不同類之間分開的程度，其定義為：

[-d2(xci,xcj)/(2σ2)]，

(5)

式中，xci,xcj分別為類ci,cj的中心；d2(xci,xcj)為聚類ci中心與cj中心之間的距離；σ為常數(shù)，為簡化計算，通常為簡化計算取2σ2=1.0。

理想的聚類結果應當滿足“類內(nèi)密集而類間分開”的特點，因此將上面兩個指標取加權平均，定義聚類的綜合質(zhì)量評價指標為：

O(ξ)=1-[ξ×D+(1-ξ)×P],

(6)

式中ξ為權重,ξ∈[0,1]。

1.3 基于多維搜索結構的模式庫構建

為進一步提升搜索效率，本研究提出的算法使用多維搜索結構代替常用的線性表作為模式庫的存儲結構，以實現(xiàn)模式的高速搜索。常用的多維搜索結構主要有KD樹、R樹等。本算法選用KD樹作為模式庫的存儲結構，這一結構目前已有一些研究使用過[18]，因此不作詳細介紹。

1.4 基于支持向量機的預測值生成

在傳統(tǒng)的非參數(shù)回歸預測中，對于搜索得到的K條最近鄰模式P1～PK，一般是使用算數(shù)平均或加權平均的方式計算因變量的預測值，即：

(7)

式中，Vb(t+1)為待預測點位b下一時刻的預測流量；V′i為近鄰模式Pi中對應的待預測因變量的值；wi為第i個近鄰模式的權重。

這種做法隱含的思想是，假定狀態(tài)向量和待預測變量之間存在一個連續(xù)的函數(shù)關系Vb=g(S)。因此，在狀態(tài)向量接近的情況下，待預測變量應該也是相近的，所以使用平均或加權平均的方式，可以估計待預測變量的值，但這種方式實質(zhì)上是一種線性的組合，當實際函數(shù)形式具有強的非線性時，估計的結果難以保證。針對這一缺點，使用支持向量機模型來擬合待預測點附近的函數(shù)關系，進而估計待預測變量的值。

支持向量機(SVM)最初用于處理兩類數(shù)據(jù)分類問題，核心思想是找到一個超平面，使得訓練集中屬于不同類別的樣本數(shù)據(jù)點位于超平面的兩側，同時這些點盡可能遠離該超平面。與其他機器學習算法相比，具有理論基礎完善、訓練速度快、泛化能力強等優(yōu)點。

預測點位b下一時刻的流量Vb(t+1)的具體步驟如下。

Step 1: 在歷史數(shù)據(jù)中提取影響Vb(t+1)的因素構成狀態(tài)向量S。

Step 2: 在模式庫中搜索以獲得S的K條最近鄰模式P1～PK。

Step 3:以P1～PK作為訓練集訓練支持向量機模型至收斂，得到在S附近狀態(tài)向量與待預測變量的非線性關系。

Step 4: 輸入S以獲得預測值Vb(t+1)。

2 數(shù)據(jù)與試驗設計

2.1 預測場景與數(shù)據(jù)來源

試驗選用的場景為深圳北站周邊的主干道。選取接近深圳北站主要出口且流量較大的留仙大道為待預測位置，對其交通流量進行短時預測(圖2)。圖2中標出了待預測位置和作為狀態(tài)分量的流量采集位置，其中交通流量來自干道上的微波和視頻檢測器。

圖2 試驗路網(wǎng)拓撲結構Fig. 2 Experimental road network topology

選取的預測步長為5 min，即Vb(t+1)表示從當前時刻t開始5 min后的交通流量。因為交通系統(tǒng)存在一定的時變特性，因此過于久遠的數(shù)據(jù)對預測并沒有很大價值，所以試驗采用的數(shù)據(jù)為2018年4月全月的數(shù)據(jù)，按5 min進行聚合，則每天有360條記錄，全月共有10 800條記錄。其中4月1日～4月25日為訓練數(shù)據(jù)構建模式庫，4月26日～4月30日的數(shù)據(jù)用于測試算法的效果。

2.2 基準算法

基準算法采用文獻[8] 中提出的KNN-NPR算法和文獻[13]中提出的KNN-NPR-LSPC算法，其中KNN-NPR算法是最經(jīng)典的非參數(shù)回歸算法，而KNN-NPR-LSPC算法在KNN-NPR算法的基礎上改進了最近鄰選擇和結果生成兩個環(huán)節(jié)。選取這兩種方法進行對比，能夠有效地說明文中算法的有效性。

通過對路網(wǎng)進行分析，認為圖2中編號為1～5的點位，其交通流與待預測點位的流量存在空間關聯(lián)，于是選取點位1～5，以時間步t～t-4的流量構造狀態(tài)向量用于預測Vb(t+1)，初始狀態(tài)向量共有25維。

2.3 性能指標

本研究所提方案的目的不止是提升預測精度，還在于提升計算速度，因此需要從預測精度與計算速度兩個角度來衡量算法的性能。

計算速度的衡量方式為：設定不同的近鄰數(shù)量K值(需要搜索的最近鄰數(shù)量K會影響到計算時間)，對所有的待預測時間點進行預測，然后求出平均每次計算的耗時。

預測精度的衡量主要采用平均絕對百分比誤差MAPE，其計算式為：

(8)

3 試驗結果分析與討論

從主成分分析和聚類結果、性能指標幾方面對試驗結果進行分析與討論。

3.1 主成分分析和聚類結果

主成分分析結果如表1所示。

表1 主成分分析結果

由表1可知，前8個主成分的方差累積貢獻率超過95%，這可以更好地概括原始數(shù)據(jù)。因此，選取分解后的Component 1～Component 8作為狀態(tài)向量中的分量。

降維之后，對模式庫實施減法模糊聚類操作。針對不同聚類數(shù)量計算由式(6)表達的聚類性能指標，得到當類中心的數(shù)量為3 100個時，效果最好。隨后只保留每個類的聚類中心，生成最終的模式庫。經(jīng)過以上處理，極大地縮減了模式庫的數(shù)量，并保留了與待預測變量關系最大的狀態(tài)分量。

3.2 算法性能

3.2.1 計算速度

需要搜索的最近鄰數(shù)量K是影響算法平均耗時的重要因素，設定不同的K值，對1 000個測試點進行預測，然后求出平均耗時(表2)。可以看到所提出的算法能夠顯著降低平均搜索時長。

表2 預測平均耗時(單位：ms)

從表2可以看出，即使模式庫中具備大量的歷史模式，每個基本預測模塊也僅需幾十毫秒進行預測，系統(tǒng)結構確保了對于更大規(guī)模的預測需求，可將預測任務分解后在多個主機上完成。該系統(tǒng)能夠處理真實情況下的多點預測。而作為對照的兩種算法在預測時間方面比本研究所提算法落后較多，當數(shù)據(jù)量更大，情況更復雜時，進行實時預測可能會有問題。

3.2.2 預測精度

設定不同的最近鄰個數(shù)，對比3種方法的預測結果，如表3所示。本研究所提算法的預測精度比KNN-NPR方法要小得多，比KNN-NPR-LSPC也有一定優(yōu)勢，在計算速度上具有優(yōu)勢，綜合性能優(yōu)于KNN-NPR-LSPC算法。

表3 與一般非參數(shù)回歸方法預測精度對比(單位：%)

4 結論

非參數(shù)回歸方法是一種以數(shù)據(jù)驅動、少參數(shù)的智能預測方法。與受到極端重視的深度學習方法相比，非參數(shù)回歸具有數(shù)據(jù)需求不高、模型構建過程簡單(無需訓練過程)、可解釋性強和不容易過擬合等優(yōu)點，在一些實際的預測工作中具有優(yōu)勢。本研究在一般非參數(shù)回歸的基礎上進行了多方面的改進，使之更加滿足較高的預測準確度、實時性和動態(tài)性的要求，進一步克服了標準非參數(shù)回歸算法模式庫體積大、計算過程效率低等缺點，并進一步提升了預測精度，具有一定的實用價值。