基于PELT的交通流狀態檢測與短期預測研究

陳王勇, 胡 堯, 2

( 1. 貴州大學 數學與統計學院, 貴州 貴陽 550025; 2. 公共大數據國家重點實驗室, 貴州 貴陽 550025)

0 引言

在很多交通流狀態分析研究中，高峰期存在平穩狀態都是一個潛在的假設。而近平穩狀態的識別對于檢測交通活動瓶頸，校準基本圖以及量化容量變化的幅度大小具有重要意義。Jin近年的一系列研究中，在運動波理論框架內證明了一般道路網絡中平穩狀態的存在和穩定性[1-3]。然而，由于不可避免的噪聲干擾和隨機波動，原始檢測數據中不存在嚴格的平穩狀態，因此，在實踐中平穩狀態只能是近似平穩的。

現有的識別此類近平穩狀態的研究通常是由校準基本圖的需要所推動的。Del Castillo等[4]提出潛在的近平穩狀態持續時間至少4或5 min且標準差小于平均值的15%，基于此準則對速度序列進行目視選擇，進一步基于Kendall’s tau檢驗，提取速度和車輛計數序列中無趨勢的近平穩狀態。由于上述方法使用目視檢查，并且在處理大量數據時耗費時間和人力。因此，需要有效識別近平穩狀態的自動方法。最近Yan等[5]基于PELT(Pruned Exact Linear Time)搜索算法的變點檢測方法，將交通流時間序列劃分為多個可能接近平穩狀態的候選間隔，計算每個候選間隔的特征，通過修改Cassidy準則實現了近平穩狀態的自動識別過程，但是對數據要求較為苛刻。鄔群勇等[6]基于公交車和出租車軌跡數據對城市交通狀態進行了精細劃分和識別，實現對城市交通狀態的分析。本研究在文獻[5]的基礎上，提出隨機化的交通流基本參數，根據不同的速度和密度需求，精細劃分交通狀態，并結合時間序列方法，運用ADF(Augmented Dickey-Fuller)檢驗[7]構建交通流近平穩狀態檢測方法。

在智能交通系統的研究領域中，除了上述交通狀態檢測研究外，短期交通流預測也是研究的熱點之一[8-12]。而非參數回歸方法在交通流預測中扮演著重要的角色[13]，早期Sun等[14]提出局部線性回歸模型應用于短期交通預測，該方法具有一定的時效性，但是對帶有異常值的數據不具有魯棒性。進而Cleveland[15]提出具有魯棒性的LOESS(Locally Weighted Regression and Smoothing Scatterplot)方法，通過計算和繪制平滑點，大大增強了散點圖上的視覺信息。Sun等[16]提出具有魯棒性的自適應參數的k近鄰方法用于短期交通流預測，但交通流歷史信息考慮不足。對此，本研究引入局部多項式回歸[17]，并綜合考慮當前的交通流信息以及歷史交通流消息，對未來的交通流進行短期預測。基于PELT搜索算法，結合Sigma原則，得到短期斷面交通流趨勢預測區間。

本研究內容安排如下：首先定義劃分交通流狀態，接著構建基于PELT搜索算法的交通流變點檢測方法以及近平穩狀態的檢測模型，引入局部多項式回歸方法，并與LOESS，k近鄰等非參數回歸方法進行預測精度的比較，最后以實際交通流數據驗證所提方法的有效性。

1 交通流近平穩狀態檢測模型

1.1 交通流狀態

在時空區域Ω={(t,l):t∈T,l∈L}中，交通流率、密度、速度在時刻t位置l處分別記為q(t,l)，k(t,l)以及v(t,l)，則有如下狀態：

定義1若時空域中的流率和密度均與時間無關q(t,l)=q(l)，k(t,l)=k(l)或等價地表示為：

(1)

則稱該時空區域中的交通流狀態是平穩的(stationary state)[5]。

定義2若時空域中的流率和密度均與時間和位置無關q(t,l)=q，k(t,l)=k，或等價地表示為：

(t,l)∈Ω。

(2)

則稱該時空區域中的交通流狀態是穩定的(steady state)[5]。

在上述的定義中，并沒有考慮交通流基本參數的隨機特征。在實際中，由于道路交通運行復雜，交通數據更是異構多源，時空性明顯，且交通狀態是交通運行系統中不同通行能力供需變化的綜合體現，故本研究將從統計角度隨機意義下去劃分交通狀態，即將時空區域Ω中的流量Q(t,l)、密度K(t,l) 以及速度V(t,l)均映射到實數域R。在統計意義下，將通行能力記為交通流量條件期望最大值，其基本計算公式如下：

C=max{E[Q(t,l)|V(t,l)]:(t,l)∈Ω},

(4)

式中kj為交通阻塞密度(jam density)。

綜上可知，統計意義下定義的自由流、中斷和擁堵等交通狀態中均存在近平穩狀態。本研究旨在研究交通流量參數近似常數下的一種近平穩狀態檢測以及交通流的短期預測。

1.2 基于PELT搜索算法的交通流變點檢測模型

數據預處理：記q1:n=(q1，…,qn)表示觀測到的交通流序列，其中n是樣本量。采用如下公式對交通流序列進行標準化處理，使其平均值為0，標準差為1。

(5)

為了檢測變點數量和位置，構造如下優化問題：

(6)

式中，θ為間隔的損失函數；β為避免過度擬合的懲罰參數[20]。特別地，使用兩倍的負對數似然函數來表示損失函數：

(7)

m+1。

(8)

進而得到交通流標準化序列的目標函數：

(9)

為了求解上述的最優問題和尋找最優的變點位置，采用基于動態規劃和剪枝技術的PELP算法得到交通流標準化序列中檢測的最優變點位置：

(10)

定理:通過樣本標準差重新調整懲罰參數，數據標準化不影響觀測序列中檢測到的變點數量和位置。

證明：將(5)式代入標準化序列的目標函數(9)式中可得：

(11)

定理表明適當的懲罰參數選擇說明式(10)也是交通流觀測序列的最優變點位置。

1.3 近平穩狀態檢測模型

qt=μ+φ1qt-1+…+φpqt-p+εt,i.i.d

j=1，…,m+1,

(12)

若交通流序列{qt}平穩，則φ1+φ2+…+φp<1；

若交通流序列{qt}非平穩，則φ1+φ2+…+φp=1。

記ρ=φ1+φ2+…+φp-1，則AR(p)過程的ADF檢驗原假設和備擇假設如下：

H0:ρ=0v.s.H1:ρ<0。

(13)

當γ≤γα時，拒絕原假設H0，認為序列{qt}顯著平穩，即第j個候選間隔為近平穩狀態；

當γ>γα時，接受原假設H0，認為序列{qt}非平穩，即第j個候選間隔為非近平穩狀態。

2 交通流短期預測方法

2.1 局部多項式回歸

針對交通流序列，除了對交通狀態的檢測外，還需要根據當前的歷史數據對未來的交通流趨勢做出判斷。本研究采用局部多項式回歸[17]對交通流時間序列進行短期預測。該方法是一種基于光滑思想的非參數回歸模型，記觀測到的一組樣本數據為(ti,qi)(i=1，…n)，則可建立如下非參數模型：

qi=m(ti)+εi,i=1，…,n，

(14)

式中，m(t)=E(q|t)為q關于t的回歸函數，并進一步假定E(εi)=0，Var(εi)=σ2。局部多項式基于加權最小二乘的思想，利用k(k≥1)階多項式去逼近回歸函數。

記Q=(q1，…,qn)T，T(t0)=((ti-t0)j),i=1，…,n,j=0，…,k。設m(t)具有k階連續導數，對定義域中任一點t0，進行Taylor展開，則在t0的鄰域內有：

(15)

式中，αj(t0)=m(j)(t0)/j！(j=0,1，…,k)，選擇合適的αj(t0)(j=0,1，…,k)使得式(16)達到最小

(16)

記W(t0)=Diag(Kh(t1-t0)，…,Kh(tn-t0))，α(t0)=(α0(t0)，…,αk(t0))T，則由加權最小二乘方法可得α(t0)的估計值為：

(TT(t0)W(t0)T(t0))-1TT(t0)W(t0)Q。

(17)

(18)

(19)

式中ω(t)為非負的權函數，則最優光滑參數為：

(20)

2.2 模擬和預測比較

(21)

(22)

為了說明局部多項式回歸的有效性，本研究將該方法與LOESS，k近鄰等經典的非參數回歸方法進行比較。在k近鄰回歸中，k取值過小會出現過擬合現象，而k取值過大會出現欠擬合現象，為防止過擬合或欠擬合本研究k取3和6。首先通過模擬基準[24]來檢測方法的性能，其次基于貴陽市中山西路與瑞金中路交叉口(由南往北方向)2 min斷面交通流數據，通過上述回歸方法分別進行短期預測，進一步驗證該方法的有效性。模擬數據由如下模型產生：

yi=μi+σεi,εi～N(0,1),i=1，…,n，

(23)

其中數據長度n=500，噪聲參數σ=0.2。數據中共存在6個均值變點，變點位置依次為137，224，241，298，307，331各個區段均值μ依次為-0.18，0.36，0.89，-0.4，0.29，-0.65，0.33,如圖1所示。

圖1 模擬數據示例Fig.1 Example of simulated data

在積分均方誤差準則下局部多項式回歸的最優光滑參數如圖2所示。從圖2中可以看出，模擬數據的積分均方誤差MISE在光滑度h為2.6時達到最小值；而斷面流量數據的積分均方誤差MISE在光滑度h為1.1時達到最小，故局部多項式的最優光滑參數分別選取為2.6和1.1。

圖2 局部多項式回歸光滑參數的選取Fig. 2 Selection of local polynomial regression smoothing parameters

圖3 局部多項式、LOESS及k近鄰回歸方法比較Fig.3 Comparison of local polynomial, LOESS and k-nearest neighbor regression method

圖4 局部多項式回歸、LOESS及k近鄰回歸預測比較Fig.4 Comparison of local polynomial regression, LOESS, and k-nearest neighbor regression prediction

基于模擬數據和斷面流量數據，將局部多項式回歸與LOESS，k近鄰等經典的非參數回歸方法進行比較如圖3、圖4所示。從圖3和圖4中均可以看出LOESS方法只是大致擬合了數據的趨勢，與觀測時序趨勢相差較大，不便于做實際分析; 而局部多項式回歸與k近鄰回歸擬合效果相對較優，擬合時序和觀測值序列趨勢基本吻合。

通過比較得到各個方法的精度評價指標見表1。從表1中可以看出局部多項式回歸在兩個精度指標可決系數R2和均方根誤差RMSE方面均表現較優。一方面基于模擬數據局部多項式、k近鄰(k=3)和k近鄰(k=6)的可決系數R2以及RMSE相對于LOESS較高，且局部多項式回歸的R2和RMSE較優，分別為0.926 5和0.894 8，進而說明了局部多項式回歸方法的有效性。另一方面基于交通流數據局部多項式回歸預測值與觀測值的可決系數R2為0.894 8，均方根誤差RMSE為11.088 6，相對于LOESS和k近鄰回歸方法較優，進一步驗證了該方法的有效性。

表1 精度指標比較Tab.1 Comparison of precision indicators

3 案例分析

3.1 交通流近平穩狀態檢測

主要選取貴陽市中山西路與瑞金中路(由南往北方向)、中華南路與都司路(由北往南方向)兩個交叉口的斷面交通流為研究對象，分別將其記為斷面I和斷面II。為檢測所選斷面交通流的近平穩狀態以及斷面交通流短期預測，特取7月1日—7月7日為期1周的2 min斷面交通流數據如圖5所示，從圖5可以看出在07:00與23:00之間的時段內兩個斷面的交通流量相對較高，其余時段相對較低，特別在23:00與00:00之間的時段內數據存在不同程度的缺失或異常值，造成該時段內的近平穩狀態檢測結果、斷面交通流量預測與實際不符,見圖4、圖6及圖8所示。

圖5 斷面I和斷面II交通流量熱力圖Fig.5 Thermal diagrams of traffic volumes at section I and section II

圖6 斷面I和斷面II近平穩狀態候選間隔Fig.6 Near-stationary state candidate intervals of section I and section II

為檢測出所選斷面處的交通流近平穩狀態，采用基于動態規劃和剪枝技術的PELP算法對斷面交通流序列進行候選間隔的劃分如圖6所示，圖6(a)，(b)中僅顯示了7月1日—7月4日的近平穩狀態候選間隔，并對所劃分的候選間隔進行編號。針對斷面I和斷面II為期1周的交通流量序列共劃分出131個候選間隔，其中斷面I包含56個候選間隔，斷面II包含75個候選間隔。對所有候選間隔進行ADF檢驗，將ADF值嚴格小于0且p值不超過顯著性水平0.01的候選間隔視為近平穩狀態，共檢測出55個近平穩狀態，其中斷面I包含28個近平穩狀態，斷面II包含27個近平穩狀態。

例如，7月2日斷面I與斷面II候選間隔狀態檢測結果見表2。對于檢測出的非平穩狀態，其對應時段內的斷面流量會出現較大的波動，更容易導致交通事故的發生，具體需結合多源交通流數據做進一步排查，該檢測結果對道路交通管理具有一定的有效性。

3.2 近平穩狀態的驗證

根據Cassidy提出的目視檢測方法[25]對近平穩狀態有效性進行直接驗證，記N(t,l)為t時刻到達位置l的累計車流量，q0t為時間的線性函數，q0是與候選間隔有關的常數，若N(t,l)-q0t關于時間t具有線性趨勢且與最佳擬合線之間的偏差不超過10 輛-1，則該候選間隔可以視為近平穩狀態。為說明上述所檢測出的近平穩狀態是有效的，以7月2日斷面II時段[05:52, 09:54]為例，該時段共劃分了3個候選間隔，累計車流量的原始曲線N(t,l)和轉換曲線N(t,l)-q0t如圖7所示。從圖7中可以直觀的看出：第4個候選間隔不僅具有明顯的線性趨勢且均在擬合線閾值邊界內，所以該候選間隔視為近平穩狀態是有效的; 注意到第5個和第6個候選間隔沒有被選為近平穩狀態，很大程度上是因為累計車流量轉換曲線超出擬合線閾值邊界。這與表2中斷面II的近平穩狀態檢測結果是一致的，即上述所構建的交通流近平穩狀態檢測方法是有效的。

表2 7月2日斷面I與斷面II候選間隔狀態檢測結果Tab.2 Test result of candidate interval between section I and section II on July 2

圖7 累計車流量原始曲線和轉換曲線Fig.7 Original and transformed curves of cumulative traffic volume

3.3 交通流短期預測

除了對斷面交通流進行狀態檢測外，為了提高道路的交通流趨勢預警，在PELT變點檢測算法的基礎上將局部多項式回歸與Sigma原則結合，得到短期斷面交通流趨勢預測區間。

(24)

式中，n為預測樣本量；I(·)為示性函數。

圖8 7月7日短期斷面交通流趨勢預測Fig.8 Cross-sectional short-term traffic flow trend prediction on July 7

以7月1日—7月6日的斷面交通流數據為測試集，基于測試集數據采用上述局部多項式回歸，得到7月7日的短期斷面交通流趨勢預測如圖8所示，從圖8中可以看出部分時段的交通流量會出現較大的波動，整體上預測區間趨勢與觀測時序基本吻合。以斷面I的預測趨勢為例，如圖8(a)在時段[06:00, 08:30)內共檢測出5個變點，變點位置依次為06:24，06:42，07:00，07:18，08:18對應的斷面流量預測值分別為11，27，42，61，65。相對于流量趨勢較為平穩的時段[00:00, 06:00)而言，在該時段內流量呈現急劇上升趨勢。一方面，若提前對出行者發布該斷面處的交通流量趨勢，則在某種程度上對出行者的路線選擇提供便利，同時也有利于交管部門對該斷面及時進行交通疏導，緩解交通擁堵，說明上述的短期斷面交通流趨勢預測區間具有一定的時效性；另一方面，斷面I、斷面II的交通流量趨勢預測區間覆蓋率分別為82.92%，80.28%，可見預測區間覆蓋率較高，進一步說明了上述預測方法具有一定的有效性。

4 結論

針對目前的交通流基本參數，考慮時空特征，從統計角度隨機化交通流基本參數，同時給出了相應的自由流、中斷和擁堵等交通狀態劃分，通過分析表明近平穩狀態存在于3種狀態之中。針對卡口數據構建了交通流近平穩狀態的檢測方法。該方法能夠快速準確地檢測斷面交通流候選間隔是否為交通流近平穩狀態，并基于貴陽市實際交通流數據通過Cassidy目視檢測方法驗證了所提方法的有效性。除了對斷面交通流進行狀態檢測外，為了提高道路的短期交通流趨勢預警，引入局部多項式回歸，對斷面交通流趨勢進行短期預測。通過模擬和預測精度指標比較分析表明，該方法相對于經典的LOESS以及k近鄰等非參數回歸方法在預測精度方面表現較優。除此之外，通過實證分析表明短期斷面交通流趨勢預測區間與觀測時序的趨勢基本吻合，且交通流趨勢預測區間的覆蓋率較高。綜合考慮交通流近平穩狀態檢測結果和交通流趨勢預測結果，對于出行者的路線選擇、交通擁堵的緩解以及交管部門的決策提供了一定的參考價值。同時為道路交叉口及城市路網中交通流近平穩狀態的自動檢測提供了方法參考。

所提方法不足之處在于PELT變點檢測方法不僅要求數據服從正態分布，而且易受異常值的影響。在分布假設不正確或異常值存在的情況下，可能會影響時序的劃分，進一步影響檢測的近平穩狀態數量和質量。因此在后續研究中可以考慮一些穩健的時序劃分方法，來增強近平穩狀態檢測方法對異常值的穩健性。另外，在接下來的工作中將通過基本圖對多時段、多斷面交通流數據進行精細劃分交通狀態以及多斷面交通流短期預測方法的研究。