基于時(shí)間序列相似性搜索的交通流短時(shí)預(yù)測方法＊

楊兆升 邴其春 周熙陽 馬明輝 李曉文

（1.吉林大學(xué)交通學(xué)院 長春 130025；2.吉林大學(xué)汽車仿真與控制國家重點(diǎn)實(shí)驗(yàn)室 長春 130025；3.吉林大學(xué)吉林省道路交通重點(diǎn)實(shí)驗(yàn)室 長春 130025）

0 引言

準(zhǔn)確、可靠的交通流短時(shí)預(yù)測信息是交通控制和交通誘導(dǎo)等多項(xiàng)ITS核心功能的基礎(chǔ)和關(guān)鍵，對于緩解交通擁堵問題具有重要意義。然而，由于檢測器獲取的交通流數(shù)據(jù)具有較強(qiáng)的時(shí)間滯后性，不能準(zhǔn)確代表實(shí)時(shí)交通狀態(tài)，要想掌握實(shí)時(shí)動(dòng)態(tài)交通流運(yùn)行狀態(tài)就必須進(jìn)行短時(shí)交通流預(yù)測。迄今為止，各國交通工程研究者已經(jīng)開發(fā)了多種預(yù)測模型和方法。較早期的預(yù)測方法主要有自回歸模型（AR）、移動(dòng)平均模型（MA）、自回歸移動(dòng)平均模型（ARMA）、歷史平均模型（HA），等等，其預(yù)測結(jié)果主要服務(wù)于自適應(yīng)交通控制系統(tǒng)。隨著對交通流特性的深入研究以及人工智能技術(shù)的發(fā)展，一批高精度、高可靠度的預(yù)測方法被相繼提出，主要包括時(shí)間序列模型［1］、非參數(shù)回歸模型［2］、卡爾曼濾波模型［3］、小波理論模型［4］、支持向量機(jī)模型［5］、神經(jīng)網(wǎng)絡(luò)模型［6－8］等。然而，現(xiàn)有的交通流短時(shí)預(yù)測方法普遍存在兩方面問題，一方面已有的研究成果主要集中于預(yù)測模型的整合優(yōu)化，忽視了對交通流數(shù)據(jù)自身特性的有效利用。具體來說，目前大多數(shù)預(yù)測模型以相鄰N個(gè)時(shí)間間隔交通流數(shù)據(jù)作為模型輸入值，從而導(dǎo)致預(yù)測誤差較大。另一方面，絕大多數(shù)交通流預(yù)測僅進(jìn)行一步預(yù)測，無法充分描述交通狀態(tài)的未來發(fā)展趨勢。針對目前交通流預(yù)測中存在的問題，為了進(jìn)一步提高交通流預(yù)測信息的準(zhǔn)確性和可靠性，筆者提出1種基于時(shí)間序列相似性搜索的交通流短時(shí)多步預(yù)測方法。

1 模型基本原理

1.1 交通流時(shí)間序列相似性搜索

交通流時(shí)間序列相似性搜索的目的是為了在海量的交通流數(shù)據(jù)中尋找與預(yù)測時(shí)刻最相關(guān)的歷史數(shù)據(jù)作為預(yù)測模型的輸入數(shù)據(jù)。由于原始交通流數(shù)據(jù)存在較大的隨機(jī)波動(dòng)，直接采用原始交通流時(shí)間序列數(shù)據(jù)進(jìn)行相似性搜索不僅效率低下，甚至?xí)绊憰r(shí)間序列搜索的準(zhǔn)確性和可靠性。為提高搜索的效率和準(zhǔn)確性，眾多時(shí)間序列模式表示方法相繼提出，主要包括離散傅里葉變換法［9］、離散小波變換方法［10］、奇異值表示法［11］、符號(hào)表示法［12］、分段線性表示法［13］，以及界標(biāo)模型［14］等。其中，界標(biāo)模型不僅能夠保留原始交通流數(shù)據(jù)的局部特征，而且形象、直觀，具有明顯的高效性。因此，筆者選用界標(biāo)模型作為交通流時(shí)間序列數(shù)據(jù)的模式表示方法。

界標(biāo)模型由Perng等人最先提出，是1種集相似性模型和數(shù)據(jù)模型為一體的方法。如果將曲線n階導(dǎo)數(shù)為0的點(diǎn)稱為曲線的n階界標(biāo)，則局部極大、極小值點(diǎn)就是曲線的一階界標(biāo)，拐點(diǎn)則為二階界標(biāo)。交通流時(shí)間序列往往含有隨機(jī)噪聲，界標(biāo)模型提出了最小距離／百分比規(guī)則作為平滑方法來消除噪聲干擾，如圖1所示。具體定義如下。

假定1個(gè)界標(biāo)序列為｛（x1，y1），…，（xi，yi），…，（xm，ym）｝。其中：xi為第i個(gè)界標(biāo)在原始時(shí)間序列數(shù)據(jù)中的位置；yi為其對應(yīng)的時(shí)間序列值。給定最小距離D和最小百分比P，如果（xi，yi）和（xi＋1，yi＋1）滿足下述條件時(shí)，則可以將它們從界標(biāo)序列上刪除。

這個(gè)條件用MDPP（D，P）表示。其中：D為最小距離，表示2個(gè)界標(biāo)之間的最小時(shí)間間隔；P為最小百分比，表示相鄰2個(gè)界標(biāo)之前幅值變化的最小程度，見圖1。

圖1 最小距離／最小百分比示意圖Fig.1 Minimal distance／percentage principle

界標(biāo)序列是由數(shù)據(jù)對來表示的，需用界標(biāo)距離進(jìn)行相似性度量。下面給出界標(biāo)距離相似性度量的定義。

已知2個(gè)界標(biāo)序列L＝｛L1，L2，…，Ln｝和L′＝｛L′1，L′2，…，L′n｝，其中，Li＝（xi，yi），L′i＝（x′i，y′i），則2個(gè)序列第k個(gè)界標(biāo)之間的距離為

Δk（L，L′）＝（L，L′（L，L′））（2）

2個(gè)序列的距離為

式中：‖·‖為矢量范數(shù)，如果δtime≤δ′time，δamp≤δ′amp，則（δtime，δamp）≤（δ′time，δ′amp）。

1.2 回聲狀態(tài)網(wǎng)絡(luò)的數(shù)學(xué)模型

神經(jīng)網(wǎng)絡(luò)模型在交通流預(yù)測中被廣泛應(yīng)用，然而由于傳統(tǒng)神經(jīng)網(wǎng)絡(luò)模型收斂過慢，容易陷入局部最優(yōu)的缺點(diǎn)，使得神經(jīng)網(wǎng)絡(luò)模型在實(shí)際應(yīng)用中受到一定的束縛。針對傳統(tǒng)神經(jīng)網(wǎng)絡(luò)的缺陷，Jaeger［15］于2001年提出1種新型遞歸神經(jīng)網(wǎng)絡(luò)——回聲狀態(tài)網(wǎng)絡(luò)（echo state networks，ESN）。

如圖2所示，回聲狀態(tài)網(wǎng)絡(luò)模型由輸入層、隱層和輸出層構(gòu)成。u（n）為含有K個(gè)輸入神經(jīng)元的輸入層激活向量；x（n）為含有N個(gè)隱層神經(jīng)元的隱層激活向量；y（n）為含有L個(gè)輸出神經(jīng)元的輸出層激活向量。輸入單元、隱層單元以及輸出單元在n時(shí)刻的值分別為

圖2 回聲網(wǎng)絡(luò)模型結(jié)構(gòu)圖Fig.2 The structure of echo state network model

從結(jié)構(gòu)上講，ESN 是1種特殊類型的神經(jīng)網(wǎng)絡(luò)模型，其基本思想是使用大規(guī)模隨機(jī)連接的遞歸網(wǎng)絡(luò)，取代經(jīng)典神經(jīng)網(wǎng)絡(luò)中的中間層，從而簡化網(wǎng)絡(luò)的訓(xùn)練過程［16］?；芈暊顟B(tài)網(wǎng)絡(luò)的狀態(tài)方程為

式中：W，Win，Wback分別為隱層－隱層、輸入層－隱層，以及輸出層－隱層的連接權(quán)矩陣；Wout為輸出的權(quán)重矩陣。f＝［f1，f2，…，fN］為內(nèi)部神經(jīng)元激活函數(shù)，fi（i＝1，2，…，N）通常取雙曲正切函數(shù)，為輸出函數(shù)，＝1，2，…，L）一般取恒等函數(shù)。在網(wǎng)絡(luò)訓(xùn)練過程中，連接到儲(chǔ)備池的權(quán)重矩陣W，Win，Wback是隨機(jī)產(chǎn)生的，在訓(xùn)練過程中固定不變，只有輸出的權(quán)重矩陣Wout需要通過訓(xùn)練得到。

2 實(shí)例驗(yàn)證

2.1 數(shù)據(jù)來源與描述

實(shí)驗(yàn)數(shù)據(jù)來源于國內(nèi)某特大城市長約10km快速路上感應(yīng)線圈檢測器采集到的地點(diǎn)交通流數(shù)據(jù)。該路段設(shè)置24個(gè)主線檢測截面和30個(gè)匝道檢測截面，安裝有88個(gè)主線檢測器和60個(gè)匝道檢測器。實(shí)驗(yàn)數(shù)據(jù)的采集時(shí)間為2008年9月到10月間連續(xù)5個(gè)周一，采樣間隔為20s。由于20 s交通流數(shù)據(jù)具有較大的波動(dòng)性，本文將20s交通流數(shù)據(jù)合成為5min數(shù)據(jù)，另外，在交通擁擠判別、交通誘導(dǎo)等實(shí)際應(yīng)用中需要掌握實(shí)時(shí)和1h內(nèi)的動(dòng)態(tài)交通信息，因此，本文對5min交通流數(shù)據(jù)進(jìn)行12步預(yù)測。

圖3（a）為同一檢測器不同日期采集的交通流數(shù)據(jù)表現(xiàn)出的相似性，圖3（b）為同一車道不同檢測截面采集的交通流數(shù)據(jù)表現(xiàn)出的相似性，圖3（c）為同一檢測斷面不同車道采集的交通流數(shù)據(jù)表現(xiàn)出的相似性。由圖3可見，交通流時(shí)間序列數(shù)據(jù)具有較強(qiáng)的相似性，為本文方法的提出提供了充足的數(shù)據(jù)支撐。

2.2 參數(shù)設(shè)置

為驗(yàn)證時(shí)間序列數(shù)據(jù)模式表示的效果，以東側(cè)主線NBDX08（1）固定檢測器2008年9月1日07：00～19：00時(shí)的交通流數(shù)據(jù)為例，利用界標(biāo)模型對交通流時(shí)間序列數(shù)據(jù)進(jìn)行模式表示，通過對交通流時(shí)間序列數(shù)據(jù)特性的深入研究，采用一階界標(biāo)對原始數(shù)據(jù)進(jìn)行表示，最小距離D取2，最小百分比P取15%，結(jié)果見圖4。

由圖4可見，通過界標(biāo)模型的模式表示，原始時(shí)間序列中的145個(gè)數(shù)據(jù)壓縮為29個(gè)界標(biāo)點(diǎn)，且能夠保留原始數(shù)據(jù)所有的局部特征，由此說明界標(biāo)模型能夠有效的降低原始數(shù)據(jù)的維數(shù)，進(jìn)而提高相似性搜索的效率。

對時(shí)間序列數(shù)據(jù)進(jìn)行模式表示之后，就可以根據(jù)界標(biāo)距離對時(shí)間序列進(jìn)行相似性搜索。然而，在相似性搜索的過程中需要確定兩個(gè)參數(shù)，1個(gè)是界標(biāo)序列的長度l，另1個(gè)是相似時(shí)間序列的個(gè)數(shù)k，本文以回聲狀態(tài)網(wǎng)絡(luò)模型多步預(yù)測的平均相對誤差最小為指標(biāo)確定兩個(gè)參數(shù)的取值。其中，根據(jù)回聲狀態(tài)網(wǎng)絡(luò)模型關(guān)鍵參數(shù)的設(shè)定原則，確定儲(chǔ)備池參數(shù)的具體取值為：儲(chǔ)備池內(nèi)部連接權(quán)矩陣的譜半徑SR＝0.75，儲(chǔ)備池規(guī)模N＝50，輸入比例因子IS＝0.2，儲(chǔ)備池的稀疏程度SD＝0.1。以2008年9月1日、9月8日、9月15日、9月22日4個(gè)周一的交通流數(shù)據(jù)為基礎(chǔ)建立歷史數(shù)據(jù)庫，采用回聲狀態(tài)網(wǎng)絡(luò)模型對9月29日的交通流數(shù)據(jù)進(jìn)行多步預(yù)測。不同參數(shù)取值所對應(yīng)的平均相對誤差見表1。

圖3 感應(yīng)線圈交通流數(shù)據(jù)Fig.3 Traffic flow data from loop detectors

圖4 時(shí)間序列模式表示效果Fig.4 The effectiveness of pattern representation

表1 對應(yīng)不同參數(shù)的MAPETab.1 The MAPEcorresponding to different parameter values %

由表1可見，當(dāng)k＝5，l＝4時(shí)，多步預(yù)測的效果最好，平均相對誤差僅為15.5%，因此，相似時(shí)間序列的個(gè)數(shù)k取5，界標(biāo)序列長度l取4。

2.3 實(shí)驗(yàn)結(jié)果與分析

為直觀展現(xiàn)本文方法的預(yù)測效果，圖5和圖6分別為NBDX08（2）和NBDX16（2）2個(gè)固定檢測器數(shù)據(jù)一步預(yù)測的結(jié)果，從圖中可見，通過本文方法的預(yù)測值與實(shí)際值之間擬合較好，預(yù)測誤差較小，具有很好的預(yù)測效果。

圖5 NBDX08（2）檢測器數(shù)據(jù)一步預(yù)測效果圖Fig.5 The one－step prediction results of NBDX08（2）

圖6 NBDX16（2）檢測器數(shù)據(jù)一步預(yù)測效果圖Fig.6 The one－step prediction results of NBDX16（2）

為對比分析回聲狀態(tài)網(wǎng)絡(luò)模型預(yù)測的有效性，本文采用自回歸移動(dòng)平均（ARIMA）模型和BP神經(jīng)網(wǎng)絡(luò)模型作為對比方法。另外，為驗(yàn)證通過時(shí)間序列相似性搜索確定預(yù)測模型輸入數(shù)據(jù)的優(yōu)越性，同時(shí)采用以相鄰數(shù)據(jù)為輸入數(shù)據(jù)的回聲狀態(tài)網(wǎng)絡(luò)模型作為對比方法。其中BP神經(jīng)網(wǎng)絡(luò)模型參數(shù)選取如下：選取輸入單元個(gè)數(shù)為5，輸出單元個(gè)數(shù)為1，隱層神經(jīng)元個(gè)數(shù)為8，其隱層神經(jīng)元的激活函數(shù)為Sigmoid函數(shù)，輸出層神經(jīng)元的激活函數(shù)為線性函數(shù)。自回歸移動(dòng)平均模型的階數(shù)根據(jù)AIC準(zhǔn)則確定。4種方法的具體預(yù)測誤差如圖7所示。

實(shí)驗(yàn)結(jié)果表明，短時(shí)交通流預(yù)測結(jié)果的MAPE隨著預(yù)測步數(shù)的增加而增大，兩者存在一定的正相關(guān)關(guān)系。以相鄰數(shù)據(jù)為預(yù)測模型輸入數(shù)據(jù)的回聲狀態(tài)網(wǎng)絡(luò)模型預(yù)測精度分別比ARIMA方法和BP神經(jīng)網(wǎng)絡(luò)方法提高6.25%和3.85%，說明回聲狀態(tài)網(wǎng)絡(luò)模型的預(yù)測效果優(yōu)于ARIMA模型和BP 模型。另外，通過比較本文方法和以相鄰數(shù)據(jù)為模型輸入數(shù)據(jù)的回聲狀態(tài)網(wǎng)絡(luò)模型的預(yù)測結(jié)果可見，本文方法的MAPE為15.5%，而以相鄰數(shù)據(jù)為模型輸入數(shù)據(jù)的回聲狀態(tài)網(wǎng)絡(luò)模型的MAPE為17%，說明本文方法能夠進(jìn)一步提高交通流短時(shí)預(yù)測的精度。

圖7 不同方法交通流多步預(yù)測效果對比圖Fig.7 The MAPE of different methods from one－step to twelve－step prediction

3 結(jié)束語

針對交通流數(shù)據(jù)的相似性特性，在分析現(xiàn)有交通流預(yù)測模型存在缺點(diǎn)的基礎(chǔ)上，筆者提出了1種基于時(shí)間序列相似性搜索的交通流短時(shí)多步預(yù)測方法，并以我國某特大城市快速路的實(shí)測數(shù)據(jù)進(jìn)行了實(shí)驗(yàn)驗(yàn)證和對比分析。結(jié)果表明，本文方法的多步預(yù)測效果明顯優(yōu)于對比方法，進(jìn)一步降低了交通流短時(shí)多步預(yù)測的誤差。

［1］Min W，Wynter L.Real－time road traffic prediction with spatio－temporal correlation［J］.Transportation Research Part C：Emerging Technologies.2011，19（4）：606－616.

［2］Clark S.Traffic prediction using multivariate nonparametric regression［J］.Journal of Transportation Engineering.2003，129（2）：161－168.

［3］楊兆升，朱 中.基于卡爾曼濾波理論的交通流量實(shí)時(shí)預(yù)測模型［J］.中國公路學(xué)報(bào)，1999，12（3）：63－67.Yang Zhaosheng，Zhu Zhong.A real－time traffic volume prediction model based on the kalman filtering theory［J］.China Journal of Highway and Transport，1999，12（3）：63－67.（in Chinese）.

［4］賀國光，馬壽峰，李 宇.基于小波分解與重構(gòu)的交通流短時(shí)預(yù)測方法［J］.系統(tǒng)工程理論與實(shí)踐，2009，9：101－107.He Guoguang，Ma Shoufeng，Li Yu.Study on the short－term forecasting for traffic flow based on wavelet analysis［J］.System Engineering－Theory＆Practice，2009，32（9）：101－107.（in Chinese）.

［5］傅 貴，韓國強(qiáng)，逯 峰，等.基于支持向量機(jī)回歸的短時(shí)交通流預(yù)測模型［J］.華南理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2013，41（9）：71－76.Fu Gui，Han Guoqiang，Lu Feng，et al.Shortterm traffic flow forecasting model based on support vector machine regression［J］.Journal of South China University of Technology：Natural Science Edition，2013，41（9）：71－76.（in Chinese）.

［6］高 為，陸百川.基于時(shí)空特性和RBF 神經(jīng)網(wǎng)絡(luò)的短時(shí)交通流預(yù)測［J］.交通信息與安全，2011，29（1）：16－20.Gao Wei，Lu Baichuan.Short－term traffic flow forecasting based on spatiotemporal characteristics of traffic flow and RBF neural network［J］.Journal of Transport Information and Safety，2011，29（1）：16－20.（in Chinese）.

［7］龔勃文，林賜云，等.基于核自組織映射－前饋神經(jīng)網(wǎng)絡(luò)的交通流短時(shí)預(yù)測［J］.吉林大學(xué)學(xué)報(bào)：工學(xué)版，2011，41（4）：939－943.Gong Bowen，Lin Ciyun，et al.Short－term traffic flow prediction based on KSOM－BP neural network［J］.Journal of Jilin University：Engineering and Technology Edition，2011，41（4）：939－943.（in Chinese）.

［8］劉元林，胡伍生，李素蘭，等.基于投影尋蹤神經(jīng)網(wǎng)絡(luò)模型的短時(shí)交通量預(yù)測研究［J］.交通信息與安全，2012，30（4）：44－47.Liu Yuanlin，Hu Wusheng，Li Sulan，et al.Shortterm traffic prediction based on a combined projection pursuit regression and BP neural network model［J］.Journal of Transport Information and Safety，2012，30（4）：44－47.（in Chinese）.

［9］Agrawal R，F(xiàn)aloutsos C.A Swami.Efficient similarity search in sequence database［C］∥Proceedings of the 4th International Conference of Foundation of Data Organization and Algorithms，Chicago，USA：University of Chicago，1993：69－84.

［10］Chan K P，F(xiàn)u A W.Efficient time series matching by wavelets［C］∥Proceedings of the 15th IEEE International Conference on Data Engineering，Sydney，Australia：IEEE Computer Society 1999：126－133.

［11］Keogh E，Chakrabarti K，Pazzani M.Locally adaptive dimensionality reduction for indexing large time series databases［C］∥Proceedings of ACM SIGMOD Conference on Management of Data，SantaBarbara，Calif USA：University of California，2001：151－162.

［12］Lin J，Keogh E，Wei L.Experiencing SAX：a novel symbolic representation of time series［J］.Data Mining and Knowledge Discovery，2007，15（2）：107－144.

［13］Keogh E，Pazzani M.An indexing scheme for fast similarity search in large time series databases［C］.Proceedings of the 11th International Conference on Scientific and Statistical Database Management，Cleveland，Ohio，USA：Cleveland State University，1999：56－67.

［14］Perng C.S，Wang H，Zhang S，et al.Landmarks：a new model for similarity－based pattern querying in time series databases［C］∥Proceedings of the IEEE 16th International Conference on Data Engineering，San Diego，Calif，USA：IEEE Computer Society，2000：33－42.

［15］Jaeger H，Haas H.Harnessing nonlinearity：prediction of chaotic time series with neural networks［J］.Science，2004，304（5667）：78－80.

［16］彭 宇，王建民.彭喜元.基于回聲狀態(tài)網(wǎng)絡(luò)的時(shí)間序列預(yù)測方法研究［J］.電子學(xué)報(bào)，2010，38（2A）：148－154.Peng Yu，Wang Jianmin，Peng Xiyuan.Research on time series prediction with echo state networks［J］.Acta Electronica Sinica，2010，38（2A）：148－154.（in Chinese）.