基于時序相關(guān)性的城鎮(zhèn)交通流預測方法研究*

李智慧 朱玉全

（江蘇大學計算機科學與通信工程學院 鎮(zhèn)江 212013）

1 引言

中國進入21 世紀以來，城鎮(zhèn)化率越來越高，過去的路網(wǎng)系統(tǒng)已不能滿足出行需要，對此，一方面可以重新合理規(guī)劃城市交通路網(wǎng)設(shè)計，另一方面則可以引入智能交通系統(tǒng)。智能交通系統(tǒng)系統(tǒng)就是對傳感器返回的數(shù)據(jù)進行特征提取，再將結(jié)果應用到現(xiàn)實世界中去。比較普遍的想法是利用交通流在時間維度上的關(guān)聯(lián)性，周期性，擴大考察范圍提高預測精度。但是城鎮(zhèn)交通流數(shù)據(jù)除了在時間維度上具有周期性，歷史數(shù)據(jù)顯著影響未來數(shù)據(jù)的特征外，在空間維度上也有較大的相關(guān)性。

Stathopoulos［2］等考慮了簡單的空間聯(lián)系，利用上游的數(shù)據(jù)預測下游的交通流數(shù)據(jù)。楊勝［9］等分析認為匯入的上游路段和流出的下游路段同時影響未來交通流，利用這兩部分數(shù)據(jù)建模結(jié)合決策樹并建立規(guī)則庫得到了很好的預測準確度。不同與上述兩種方法，李一龍［10］等基于動態(tài)規(guī)劃思想提出了交通流預測與分配的方法，考慮路段容量對交通分配的影響，建立了路網(wǎng)流量預測和分配模型。Ye［11］等研究發(fā)現(xiàn)如果在傳統(tǒng)的中介中心性中通過線性加權(quán)聚合引入路段間的來往親密度，路網(wǎng)建模將會更加完整。Zheng［12］等提出一種深度融合的學習方法與現(xiàn)實世界中的特征因素結(jié)合，包括路網(wǎng)結(jié)構(gòu)和天氣情況。卷積神經(jīng)網(wǎng)絡(luò)可以學習二維交通流數(shù)據(jù)的特征，二維指的是時間和空間兩個維度，再利用長短期記憶網(wǎng)絡(luò)保留對歷史數(shù)據(jù)的記憶。周明［13］等在能完全掌握路網(wǎng)拓撲結(jié)構(gòu)的前提下，以是否鄰接作為標準得到路段的關(guān)聯(lián)矩陣，用這種矩陣表征路網(wǎng)空間關(guān)系。

現(xiàn)有的交通流預測模型或簡單地考慮上下游交通流數(shù)據(jù)無法進一步提高預測準確率，或考慮整個路網(wǎng)導致時間資源浪費，得不償失，或利用路網(wǎng)物理拓撲結(jié)構(gòu)提取空間特征，不考慮交通流數(shù)據(jù)在不同時間段的差異。于是提出一種考慮路網(wǎng)連通性和時間序列交叉相關(guān)性的方法挖掘路網(wǎng)空間特征。

2 時間序列交叉相關(guān)性

城鎮(zhèn)路網(wǎng)可以看作一個相對封閉的結(jié)構(gòu)，其內(nèi)部的交通流不會憑空消失，在小范圍內(nèi)是相互流動的。

根據(jù)路網(wǎng)交通流的流動性可知，相連路段間的交通流特征變化具有時間維度上的一致性。城鎮(zhèn)路網(wǎng)空間特征包括由拓撲結(jié)構(gòu)決定的恒定特征和由社會活動決定的動態(tài)特征，而在短時交通流預測中動態(tài)空間特征更有考察意義。所謂動態(tài)空間特征是指路網(wǎng)空間特征及路段間的空間關(guān)聯(lián)性是隨時間變化而變化的。

相關(guān)系數(shù)通常用來表征兩序列間的交叉相關(guān)性。路網(wǎng)交通具有連通性，通過判定兩路段平均交通速度變化間的相關(guān)性可以得到路段間是否連通的定性關(guān)系。皮爾森相關(guān)系數(shù)和最大信息數(shù)（Max?imal Information Coefficient，MIC）是兩種最流行的線性相關(guān)系數(shù)和非線性相關(guān)系數(shù)。以下是三對鄰接路段在同一時間段內(nèi)輸出的交通流特征序列間的兩種系數(shù)。

圖1 中兩路段是上下游關(guān)系，計算出的線性和非線性相關(guān)關(guān)系也基本一致。圖2 中的兩段路不再是理想的上下游關(guān)系，雖然在邏輯上仍然認為兩段路有緊密的相關(guān)關(guān)系，但是皮爾森系數(shù)已經(jīng)開始大幅減小。圖3 中的兩段路間的皮爾森系數(shù)已經(jīng)下降到無法認為兩路段輸出序列間有相關(guān)性的程度，但是非線性相關(guān)系數(shù)超過了0.5，更好地表征了兩路段在空間上的關(guān)聯(lián)性。通過在容易得到拓撲結(jié)構(gòu)的路網(wǎng)上做實驗，表明非線性相關(guān)系數(shù)更合適用來表征路段間的相關(guān)性。

圖1 理想上下游（皮爾森系數(shù)：0.99；最大信息數(shù)：1）

圖2 典型上下游（皮爾森系數(shù)：0.76；最大信息數(shù)：1）

圖3 特殊上下游（皮爾森系數(shù)：0.41；最大信息數(shù)：0.57）

3 基于時序相關(guān)性的路網(wǎng)空間特征挖掘

3.1 動態(tài)路網(wǎng)劃分算法

3.1.1 動態(tài)路網(wǎng)空間模型

動態(tài)路網(wǎng)空間模型是以時間為自變量的動態(tài)時域模型，可以運用動態(tài)空間分析法對路網(wǎng)的時變行為進行描述。對動態(tài)路網(wǎng)空間模型基本概念的闡述如下。

1）狀態(tài)變量和狀態(tài)向量

假設(shè)時域為T，則在此時域內(nèi)的狀態(tài)變量為Trai，表示路段i 在時域T 內(nèi)的交通流特征值。于是，時域T 內(nèi)的狀態(tài)向量為Tra={Tra1,Tra2,…Tran}。

2）輸入變量和輸入向量

動態(tài)路網(wǎng)空間模型的輸入變量是指外界作用于其的各種可觀測和不可觀測因素的總和。輸入向量由輸入變量組成。

3）觀測變量和觀測向量

路網(wǎng)空間模型在系統(tǒng)作用下得出的一組對應變量稱為觀測變量，由觀測變量組成觀測向量。

4）狀態(tài)空間

狀態(tài)空間包含了系統(tǒng)全部可能存在的狀態(tài)，路網(wǎng)狀態(tài)空間由所有時域下的狀態(tài)向量組成。

5）狀態(tài)方程與觀測方程

用于描述動態(tài)路網(wǎng)空間模型的狀態(tài)方程與觀測方程為

式中：Xt為t 時段n 維的路網(wǎng)狀態(tài)向量，不能直接觀測得到；Ut-1為t 時段r 維的路網(wǎng)輸入向量；wt為t 時段系統(tǒng)噪聲；yt為n 維觀測向量；vt為t 時段系統(tǒng)噪聲；Ft為n×n 維狀態(tài)轉(zhuǎn)移系數(shù)矩陣；Tt為n×r 維輸入系統(tǒng)矩陣；Gt為n×i 維噪聲轉(zhuǎn)移系數(shù)矩陣；Ht為j×n維輸出系數(shù)矩陣。

3.1.2 算法說明

提出一種脫離路網(wǎng)拓撲結(jié)構(gòu)而依據(jù)路段輸出的交通流特征序列的空間特征挖掘方法，采用密度聚類（DBSCAN）傳遞思想。這一思想與路網(wǎng)結(jié)構(gòu)中的交通流具有相似性。被劃分為一類的路段組成一個子網(wǎng)。子網(wǎng)S 是滿足以下性質(zhì)的非空樣本子集：

連接性：若xi∈S，xj∈S，則xi和xj密度相連。

最大性：若xi∈S，xj由xi密度可達，則xj∈S。

不難證明，若x 為核心路段，則由其密度可達的所有路段組成的集合為X={x′N|x′由x密度可達}滿足連接性與最大性。具體描述如算法1 所示。

算法1 空間特征挖掘算法

輸入：N個用交通流序列表征的路段，r：相關(guān)度閾值，MinRs：子網(wǎng)最少路段數(shù)。輸出：子網(wǎng)劃分結(jié)果。1）將所有路段標記為未訪問；2）執(zhí)行3） 隨機選擇一個未被訪問路段R；4） 將R標記為已被訪問；5） 若R在r標準下的鄰域內(nèi)的路段數(shù)不小于MinRs 6） 創(chuàng)建一個子網(wǎng)S，將R劃分入S；7） 將R 在r 標準下的鄰域內(nèi)的路段集合記為G；8） 對G內(nèi)的每一個路段R'操作9） 若R'未被訪問

10） 將R'標記為已被訪問；11） 若R'在r 標準下的鄰域內(nèi)的路段數(shù)不小于MinRs 12） 將該鄰域內(nèi)的路段加入集合G 13） 若R'還未被劃分到某個子網(wǎng)，將其劃分入S 14） 輸出子網(wǎng)S；15） 否則將R標記為噪音路段；16）直到所有路段均已被訪問。

3.1.3 相關(guān)實驗

為了更直觀地說明路網(wǎng)劃分算法，使用來源于http：//www.openits.cn/openData2/746.jhtml 的安徽省宣城市水陽江范圍內(nèi)2016 年12 月15 日全天交通數(shù)據(jù)集作為輸入，得到路網(wǎng)劃分的可視化結(jié)果。

每一段路上的交通流隨時間變化序列按照前一天晚上22：00到當天凌晨6：00（記為時間段T1）、當天凌晨7：00到中午12：00（記為時間段T2）、當天中午13：00 到下午18：00（記為時間段T3）、當天下午19：00到當天凌晨21：00（記為時間段T4）分為四個序列分別代表各個時間段的交通特征。這四個時間段的路網(wǎng)在3.1.2 小節(jié)算法的劃分下會得到不同的子網(wǎng)結(jié)構(gòu)。

圖5～圖8利用線條樣式區(qū)分不同的子網(wǎng)劃分，可以看出水陽江附近的路段在不同時段被分為四個子網(wǎng)。

圖4 T1下的劃分結(jié)果（相關(guān)度閾值：0.9）

圖5 T2下的劃分結(jié)果（相關(guān)度閾值：0.85）

圖6 T3下的劃分結(jié)果（相關(guān)度閾值：0.8）

圖7 T4下的劃分結(jié)果（相關(guān)度閾值：0.9）

圖8 基于路段隨機組合和前饋神經(jīng)網(wǎng)絡(luò)的預測方法

4 基于改進剪枝算法的交通流預測模型

4.1 基于改進剪枝算法的前饋神經(jīng)網(wǎng)絡(luò)

前饋神經(jīng)網(wǎng)絡(luò)（BPNN）具有兩個主要特征：加權(quán)平均和激活函數(shù)。神經(jīng)網(wǎng)絡(luò)的加權(quán)特性要求模型輸入特征之間的相關(guān)性不應太強。如果直接應用路網(wǎng)空間特征提取后的訓練數(shù)據(jù)集，神經(jīng)網(wǎng)絡(luò)的輸入就是基于變量間的相關(guān)性，這使得輸入變量間無法保證獨立同分布。于是為了避免由于輸入變量間相關(guān)性強導致神經(jīng)網(wǎng)絡(luò)訓練效率低的問題，提出了BPNN的改進模型。

模型采用隨機梯度下降的方式更新神經(jīng)網(wǎng)絡(luò)的參數(shù)，假設(shè)損失函數(shù)定位為L(y,y)，其中y 為真實值。使用梯度下降更新神經(jīng)元參數(shù)實際就是對神經(jīng)元權(quán)重w 和偏置b 求偏導數(shù)。根據(jù)鏈式法則有：

其中，W(k)和b(k)表示第k 層隱藏層神經(jīng)元的權(quán)重和偏置，Z(k)表示神經(jīng)元的輸入。將第k 層神經(jīng)元對最終誤差的影響記為Δ(k)。于是有：

其中N(k)=fk(Z(k))表示第k 層神經(jīng)元輸出，Z(k+1)=W(k+1)×N(k)+b(k+1)，于是有：

而前饋神經(jīng)網(wǎng)絡(luò)的更新參數(shù)規(guī)則為

模型使用的改進剪枝算法就是基于Δ 的相關(guān)性，若兩神經(jīng)元對于誤差的影響效果具有強相關(guān)性，則認為它們可以合并。相關(guān)性算法要求先算出隱層節(jié)點的δ值，然后計算每個節(jié)點δ值間的相關(guān)度以及各δ值的方差。第i個節(jié)點和第j個節(jié)點的相關(guān)度公式為

其中，N 是δ值的組數(shù)，δi標識第i 個節(jié)點的平均δ值。

第i個節(jié)點δ值的方差為

R 較大或S2較小的節(jié)點可以被合并或刪除，這一操作可通過調(diào)整激活函數(shù)實現(xiàn)。

4.2 算法說明

基于動態(tài)子網(wǎng)劃分的交通流預測方法可以分為原始數(shù)據(jù)缺失補全、交通流時間序列數(shù)據(jù)關(guān)聯(lián)關(guān)系挖掘、神經(jīng)網(wǎng)絡(luò)得出預測結(jié)果三個部分。

算法2 交通流預測算法的流程（以前一天晚22：00到當天6：00時間段和工作日為例，記為條件P）：

輸入：各路段在一段日期內(nèi)時間間隔為I采集得到的平均交通流速度。

輸出：預測誤差。

1）原始交通流特征數(shù)據(jù)補全缺失：

2）發(fā)現(xiàn)缺失點(R,D,T)；

3） 若是(R,D,T-1)和(R,D,T+1)處數(shù)據(jù)完整，則取兩者平均補全；

4） 否則，依據(jù)天氣和是否休息日得到按照其余路段與路段D相似度由大到小排列的序列S={Ri,Rj,…,Rk}

5） 依次查找S 中路段在T，T-1，T+1 處數(shù)據(jù)是否完整；

6）得到每一路段工作日P條件下從早到晚排列交通流時間序列Trai；

7）{Trai,Traj,…Trak}集合輸入算法1 得到輸出：子集S；

8）以子集Si={ri,rj,…rk}為例：

9）對Si中的每一個路段r操作

10）對滿足條件P的每一個交通流數(shù)據(jù)d操作

11） 依次拼接Si中路段在d前一時間間隔的交通流數(shù)據(jù)為序列seq，再將d接到最后組成完整序列；

12）上述步驟i 到步驟k 過程后得到一個時間序列集data_set；

13）搭建一個輸入層神經(jīng)元數(shù)目為len(Si)，輸出層神經(jīng)元數(shù)目為1的基于改進剪枝算法的前饋神經(jīng)網(wǎng)絡(luò)；

14）data_set 按照7∶3 比例劃分為train_set 和test_set，依次輸入神經(jīng)網(wǎng)絡(luò)模型后得到預測模型和預測誤差。

5 實例分析

5.1 誤差評價指標

5.1.1 平均絕對相對誤差（Mean Average Relative Error，MAPE）

式中，qk表示交通流量實測值，qk表示交通流量預測值。

5.1.2 均方根誤差（Root Mean Square Error，RMSE）

5.2 預測結(jié)果分析

http：//www.openits.cn/openData2/732.jhtml 中的數(shù)據(jù)集包括中國廣州市的214 個路段從2016 年8月1 日到9 月30 日以10min 為間隔的數(shù)據(jù)。利用3中的算法處理數(shù)據(jù)集后，會得到預測結(jié)果。

可以看出，圖9 中的預測線條只是大致擬合了實際交通流數(shù)據(jù)變化趨勢，與真實數(shù)據(jù)仍有較大偏差，圖10 和圖11 中的預測線條更好地擬合了實際變化趨勢，并且也還原了細小的變化，可以看出誤差已經(jīng)顯著下降。

圖9 基于路網(wǎng)空間特征挖掘和前饋神經(jīng)網(wǎng)絡(luò)的預測方法

圖10 基于路網(wǎng)空間特征挖掘和剪枝算法改進后的前饋神經(jīng)網(wǎng)絡(luò)預測

表1 給出了三種方法得到的預測結(jié)果與實際測量值之間的MAPE 和RMSE 兩種誤差以及訓練時間，可以看出基于動態(tài)子網(wǎng)劃分算法的交通流預測算法與普通方法相比使得兩種誤差分別下降了0.8%和25%。并且從時間復雜度的角度考慮，剪枝算法不僅保證了預測精度并且大大節(jié)省了模型訓練時間，將預測時效性提高了45%。

表1 誤差比較

6 結(jié)語

異常點處的交通流預測一直是交通流預測中的一個難點，只考慮路網(wǎng)上的交通流數(shù)據(jù)很難解決這個問題，結(jié)合道路事故信息或者卡口拍攝到的路面信息能得到更好的預測效果，但就目前來說這種解決方案會降低預測時效性，還需要探索更有可用性的方法。