李心玥 楊衛(wèi)東 張 徵 許海波

(復旦大學計算機科學技術(shù)學院 上海 201203)

快速路行程速度突變段挖掘和基于相似匹配的短時預測算法

李心玥 楊衛(wèi)東 張 徵 許海波

(復旦大學計算機科學技術(shù)學院 上海 201203)

城市快速路交通流具有明顯的暢通和擁塞時段交錯的特征，其間行程速度產(chǎn)生較大變化?；谏虾？焖俾肪€圈感應器采集的數(shù)據(jù)，首先提出一種在交通時間序列上線性時間挖掘行程速度突變段的滑動窗口方法，解決了識別擁塞起止時刻等需求。然后，構(gòu)建突變段歷史樣本數(shù)據(jù)庫和自定義索引，提出一套經(jīng)過多重優(yōu)化的基于相似度匹配的預測模型，達到對行程速度短時預測的目的，相比傳統(tǒng)的回歸方法更簡單實用。最后，利用大量實際數(shù)據(jù)對兩套模型的效果和性能進行了檢驗。結(jié)果表明，挖掘算法通過簡單的參數(shù)調(diào)?？赏瓿刹煌叨鹊耐蛔兌尾樵?，而預測算法能有效滿足實時查詢的性能要求，15 min的預測精度能達到90%左右。

時間序列 行程速度 突變段 滑動窗口 短時交通預測 相似度 索引構(gòu)造

0 引 言

交通系統(tǒng)是國民經(jīng)濟發(fā)展的基本命脈，關系到商品貨物的流通速度和人民出行的幸福指數(shù)。它的顯著特點是大量隨機或者周期性因素構(gòu)成的不確定性：如天氣(雨雪)等氣象因素，交通事故或局部地區(qū)突發(fā)事件等人為因素，工作日早晚高峰和周末黃金出行時段等周期性因素。伴隨著智能交通系統(tǒng)(ITS)研究的不斷深入，短時交通流預測成為交通管理者和研究人員關注的主要問題之一，因為預測結(jié)果的好壞直接影響到ITS的決策和交通誘導控制的效果。短時預測是指預測時長跨度不超過15分鐘的交通流預測，相對于已有較成熟研究成果的中長期預測，短時交通流預測的研究目前還處于發(fā)展階段[1]。之前這方面的研究主要集中在預測交通量這一指標上，但交通量并不能很好地衡量交通狀況：同一交通量水平在一個路段可能是嚴重擁塞，在另一個路段可能是暢行無阻[2]。因此，選擇路段的行程速度作為研究指標，相比而言，它更直觀反映了擁塞程度和路況。

本文基于上海市安裝于快速路上的線圈采集數(shù)據(jù)展開工作。交通數(shù)據(jù)的采集主要有兩種方式，一是靜態(tài)交通探測方式，利用位置固定的定點檢測器如線圈，雷達，光電檢測器等；另一種是動態(tài)交通探測方式，基于位置不斷變化的車輛或手機來獲得實時行車速度和旅行時間等。無論哪種方式，采集數(shù)據(jù)的格式都可以表達為一連串密集的時間序列，橫坐標為采集時間，縱坐標為該時間上偵測到的車輛行程速度平均值。

通過對快速路實際采集數(shù)據(jù)分析后發(fā)現(xiàn)，其行程速度多數(shù)時間有非常顯著的低波動穩(wěn)定性特征。圖1為上海某快速路段某工作日的后臺系統(tǒng)行程速度監(jiān)測圖，可將其視為一個時間序列?？梢钥闯觯斅访鏁惩ɑ驌矶逻M行中時，時間序列會分別在高低位保持相對穩(wěn)定，稱這種時段為“穩(wěn)定段”。相反，有時序列出現(xiàn)不同程度的大波動，例如逐漸進入早高峰的時段。相應地，稱其為“突變段”。突變段有較大的研究價值，因為：(1) 突變段的識別是分析擁塞起止時刻和發(fā)生原因的基礎[3]；(2) 突變段對應了某些事故或突發(fā)事件逐步擴散過程，挖掘這些事件為相關部門制定準備方案帶來幫助；(3) 突變段描繪了路段應對交通流變化的響應曲線，對交通規(guī)劃部門有重要作用。

圖1 快速路的時間-行程速度曲線

本文首先基于簡單直觀的累積弧度[4]，形式化定義了時間序列上的突變段問題，并提出了挖掘突變段的方法。該方法利用滑動窗口存儲已計算值的思想，能在線性時間搜索出序列中所有滿足定義的突變段。然后，本文研究快速路上的短時預測問題。以往用數(shù)學建模求解的方法存在很多問題[5]，越來越不能滿足實際應用的需要，而較晚提出的基于非參數(shù)回歸的模型[6]能較好應對交通流的復雜性，但需要構(gòu)造狀態(tài)向量等復雜步驟，且較難滿足實時在線預測的要求。本文基于突變段，提出一種新的預測方法，核心是判斷實時路況的當前狀態(tài)，當路況觸發(fā)突變閾值時，系統(tǒng)對歷史突變段進行模式匹配，尋找出相似度最大的歷史段，達到短時預測的目的。本質(zhì)上采用了與非參數(shù)回歸一樣的假設，即歷史數(shù)據(jù)庫包含了由所有因素綜合導致的交通狀態(tài)變化趨勢，可以認為所有因素的內(nèi)在聯(lián)系都蘊涵在歷史數(shù)據(jù)庫中。因此，只需足夠的歷史數(shù)據(jù)，就能較好地應對交通流這種不確定性強，非線性的動態(tài)系統(tǒng)，取得比傳統(tǒng)建模方法更好的預測結(jié)果。

1 相關研究工作和聯(lián)系

本文研究的問題之一是交通預測，已有的主要預測方法可分為： 1) 歷史平均模型[7]等靜態(tài)模型。它們靜態(tài)地根據(jù)歷史數(shù)據(jù)分析得出同一路段特定時間最大置信度的交通流。但靜態(tài)預測不能解決非常規(guī)和突發(fā)的交通情況。2) 卡爾曼濾波模型[8]。由于其是線性預測模型，在預測交通流時準確率較低。 3) 神經(jīng)網(wǎng)絡算法[9]。但神經(jīng)網(wǎng)絡需要很大的訓練樣本，收斂速度慢，且有較多局限性。 4) 基于時間序列的自回歸模型。代表是ARIMA自回歸模型[10]。ARIMA通過三個模型參數(shù)p、d、q和一個方程去描述時間序列{yt}，其中p是自回歸周期，d是差分階數(shù)，q是移動平均周期，通過該方程達到預測的目的。ARIMA模型試圖用一個方程描述交通流這樣復雜的非線性系統(tǒng)，且需要先根據(jù)序列識別一個試用模型，并不斷做出調(diào)整參數(shù)，建模時間代價很大。5) 非參數(shù)回歸方法[6,11]。其優(yōu)點是不需要先驗知識，擬合效果好，但也存在狀態(tài)向量長度不易事先確定，狀態(tài)向量較大時難以滿足實時在線預測等問題。

本文使用時間序列作為研究內(nèi)容的格式。時間序列在金融等領域都有廣泛的研究。金融領域的時間序列強調(diào)形態(tài)特征的分析[12]，如頭肩底等。其他一些關于時間序列的研究方向有： 1) 時間序列的降維[13]。因為序列通常具有海量性，有時候需要將數(shù)據(jù)有效地壓縮后才能處理。2) 尋找離群點和無效數(shù)據(jù)[14]。由于各種硬件故障、噪聲干擾等原因，原始的交通采集序列需要先進行預處理[15]，剔除異常數(shù)據(jù)，補齊丟失數(shù)據(jù)。另外，由于原始序列疊加了各種各樣的干擾噪聲，預處理階段一般還需要采用噪聲過濾技術(shù)減少數(shù)據(jù)震蕩，經(jīng)常使用的方法是均值平滑法或小波變換法。本文使用文獻[16]提出的框架，利用小波變換法對原始采集序列先進行預處理，限于篇幅不再贅述，下文的時間序列均指預處理清洗后的數(shù)據(jù)。3) 時間序列的相似性度量。相似性度量的方法有很多，如基于歐式距離，基于模式距離等。本文利用了文獻[17]提出的基于弧度距離的思想。

2 突變段的識別和挖掘

2.1 突變段問題定義

對于長度為n的交通時間序列s={y(t),t=0,1,…,n}，首先定義基于相鄰兩點的分段弧度[17]:

定義1 對于交通時間序列s={y(t)}，定義分段弧度rad(t)為(t,yt)和其相鄰點(t+Δt,yt+Δt)構(gòu)成的直線與時間軸的夾角弧度，即：

(1)

圖2為分段弧度示意圖，Δt=1。由定義1有，rad(t+1)=θt+1<0,rad(t)=θt>0,即當夾角在第1象限時為正值，第4象限時為負值。

圖2 分段弧度示意圖

使用k-累積弧度可以定量地分析在k尺度下序列的穩(wěn)定程度。當cr(t)和rcr(t)較小時，說明t點處于一個穩(wěn)定的弱波動水平中。當|cr(t)|相對左側(cè)超過臨界值時,表明序列在t點開始處于上升或下降的趨勢特征中;相反,當|rcr(t)|相對右側(cè)的超過臨界值時,表明t點之后的趨勢逐漸恢復穩(wěn)定,t處于一段趨勢的尾聲。可以看出,當k=1時,累積弧度退化為cr(r)=rcr(t)=rad(t),尺度最小,只考慮了自身的波動。

定義3 對于交通時間序列S={y(t)},常數(shù)k和ε,k∈N+,ε>0,若存在子序列s={yi,yi+1,…,yj-1,yj},j>i+1滿足:

1) 對于所有t∈(i,j),|cr(t)|≥ε;

2) 對于所有t∈(i,j),|rcr(t)|≥ε;

3) 且不存在子序列s′?s滿足性質(zhì)1和性質(zhì)2。

則稱子序列μ=(yi,…,yj)為交通時間序列{y(t)}的一個突變段,yi、yj分別為μ的起始點和終結(jié)點,j-i+1為突變段的長度。為了排除極小規(guī)模的波動的干擾,有必要設定常數(shù)L,使得定義3滿足j-i+1≥L,保證突變段不小于一定長度。

2.2 時間序列上挖掘突變段的算法

下面給出基于定義3的在交通時間序列上挖掘突變段的算法1偽代碼。

算法1采用了滑動窗口的思想。首先構(gòu)造兩個長度為L的滑動窗口winds[0]和winds[1],分別存儲了當前已計算的L個點的cr和rcr值(第3行)。函數(shù)init初始化了頭位置在head的滑動窗口。然后,算法1檢查滑動窗口是否滿足定義3的性質(zhì)1和性質(zhì)2(check函數(shù))。若不滿足,則窗口向后滑動最大的距離,跳過窗口內(nèi)最后一個不滿足的已計算點(第13～15行);若滿足,根據(jù)定義3的性質(zhì)3,窗口使用貪婪算法向后尋找更多滿足條件的點直到失敗(extend函數(shù))。當找到符合條件的區(qū)間時,加入結(jié)果集合,并重新初始化滑動窗口尋找下一個區(qū)間(第7～12行)。當窗口向后滑動時,需要更新窗口值(第23～31行),如圖3所示,陰影部分點的cr和rcr值得以保留并移動到滑動窗口隊列頭,算法從陰影后的點開始重新計算cr和rcr。step是窗口滑動的步數(shù)。

圖3 滑動窗口示意圖

算法1 挖掘突變段偽代碼

輸入:交通時間序列S=y{(t)},常數(shù)k,ε,L

輸出:所有長度不小于L的突變段集合ω

1 ω=?

2 head=k-1,tail=head+L,n=len(S)

3 winds=init(head)

4 while True:

5 step=check(winds)

6 if step==0:

7 end=extend(winds,tail-1)

8 ω=ω∪(head,end)

9 head=end

10 tail=head+L

11 if tail+k>n:break

12 winds=init(head)

13 elif tail+k-1+move≤n:

14 move(winds,head,step)

15 head+=step,tail+=step

16 else:break

17 def init(head):

18 winds=[]# a list contains 2 sublists

19 winds[1]=[cr(i) for in [head,head+L)]

20 winds[2]=[rcr(i) for in[head,head+L)]

21 return winds

22 def move(winds,head,step):

# 更新滑動窗口1

23 buffer=winds[0][step:]

24 cr_val=winds[0][-1]

25 cr_pos=head+L-1

26 dor iter in [0,step]

27 cr_pos+=1

28 cr_val=cr_val+rad(cr_pos)-rad(cr_pos-k)

29 buffer.append(cr_val)

30 winds[0]=buffer

# 更新滑動窗口2

31 ……

32 def extend(check_pos):

33 cr=winds[0][-1]

34 rcr=winds[1][-1]

35 while check_pow<=n-k:

36 if cr and rcr satisfy ε:

37 update cr and rcr

38 check_pos+=1

39 else break

40 return check_pos

41 def check(winds):

42 for pos in[L-2,0]:

43 if winds[0][pos]or winds[1][pos]not satisfy ε:

44 return pos

45 return 0

容易證明,init函數(shù)共執(zhí)行|ω|+1次,時間復雜度O(L×k×|ω|),滑動窗口滑動并檢驗耗時O(n),整體復雜度O(n+L×K×|ω|)。因為k,L,|ω|≤n時,所以最后得到算法1的時間復雜度O(n),額外空間復雜度O(L)(不計輸入序列)。

算法1的參數(shù)設置直觀,通過簡單調(diào)校就可以控制識別敏感度和突變段的趨勢尺度。它只需對目標序列進行一次順序掃描,并且不要求序列完全加載,因此也適用于流數(shù)據(jù)。這給實際應用中處理實時采集的數(shù)據(jù)帶來了方便。

3 基于突變段的短時速度預測

3.1 預測模型和基本算法

基于上節(jié)的工作,建立如圖4所示的快速路行程速度預測模型。其預測思想類似非參數(shù)回歸模型[11],且基于城市快速路交通流的3個事實:1) 在車流量不超過設計承載值的暢通環(huán)境下,通過的單位時間車流速度穩(wěn)定;2) 出行高峰時間,突降雨雪,上下游發(fā)生交通事故等各種情況下,都會影響行程速度,誘發(fā)突變段,產(chǎn)生趨勢,但趨勢行為會隨著時間而改變,很難將時間-速度關系納入一個統(tǒng)一的數(shù)學模型中;3) 相同的路段環(huán)境下,發(fā)生的事件在足夠的歷史數(shù)據(jù)下可重復,該路段應對相同事件的速度響應曲線是類似的。

圖4 預測模型框架

預測模型接受一個實時輸入經(jīng)過預處理的采集序列。令當前時刻為t,預測模型計算并輸出Δt時間后的預測速度。

首先,通過算法1實時判斷(t,yt)是否處于一個突變段中:

A) 如果否,使用簡單的一次指數(shù)平滑法進行預測,其迭代方程為:

…+(1-α)kyt-k

一次指數(shù)平滑法適合于具有水平發(fā)展趨勢的時間序列分析,能較方便地對短期進行預測。α為權(quán)重系數(shù)。

B) 否則,記當前突變段為Q={yi,…,yt},稱為模式段。在該路段的n個歷史突變段{sp},p=1,…,n中,查找與模式段最相似的匹配段{ye-(t-i),…,ye},滿足:

1)yt?ye;

2) {ye-(t-1),…,ye}?sq,q∈[1,n];

3)e=argmin(sim({yi,…,yt},{ye-(t-1),…,ye}))。

通過A-B兩個步驟,預測模型反饋預測結(jié)果。因為輸入數(shù)據(jù)實時變化,因此預測模型也可以實時更新預測結(jié)果。容易看出,該模型對較小的Δt有較好的預測值。一般要求Δt不超過15分鐘。

算法2給出為模式段搜索匹配的偽代碼。

算法2 模式段匹配偽代碼

輸入:模式段Q={yi,…,yt},歷史突變段集合{sp}

輸出:最佳匹配sq,匹配時刻e

1 best=∞,e=q=-1

2 for sjin {sq}:

3 for yhin sj:

4 if yh?ytand yh-(t-i)∈sj:

5 m=sim({yi,…,yt},{yh-(t-i),yh})

6 if m

7 best=m,e=h,q=j

8 return sq,e

3.2 相似性度量

時間序列的相似性比較有幾種方法,例如基于歐幾里德距離,重要點分段距離等,但一些方法并不能合理地判斷兩個時間序列的形態(tài)相似性,而一些方法則需要對y軸歸一化處理,對幅度變化不敏感,這對預測模型而言是不可接受的。

(2)

當sim=0時,匹配段和模式段有完全相同的形態(tài)和值。定義類似基于模式距離的方法[18]。但傳統(tǒng)的模式距離只考慮了三元模式,精度差,且需要進行對齊等額外處理。而該定義能夠保留序列的形態(tài)特征,同時又對幅度敏感,計算方便，因此適用于本文的預測模型。

3.3 模式段匹配算法的優(yōu)化

3.3.1 索引的構(gòu)建

算法2需要對同一個路段的歷史突變段數(shù)據(jù)庫進行一次完整掃描,當數(shù)據(jù)較多時負擔較大。實際上,根據(jù)算法2第4行,匹配段的值域必須包含模式段。因此,可以使用特殊的索引結(jié)構(gòu),排除不滿足條件的歷史突變段?；诖?設計索引如算法3-1所示。對一個路段,索引只需要構(gòu)建一次。每次開始模式段匹配時,加載索引,通過算法3-2得到真正需要掃描的歷史突變段集合,避免整體掃描。

算法3-1 索引生成

輸入:{(yi1,yj1),(yi2,yj2),…,(yin,yjn)}表示的一個路段的所有n個歷史非突變段

輸出:索引Index

1 令序列L={yi1,yj1,yi2,yj2,…,yin,yjn}

3 for min[1,h):

# 構(gòu)造索引

算法3-2 索引查找

輸入: 模式段查詢{y1,…,yt}

輸出: 根據(jù)索引找到的需進一步掃描的歷史突變段集合H

1 H=φ

2 for min[1,h):

4 if H is φ:

算法3-1的原理是歸納并記錄各個突變段的值域區(qū)間,當索引構(gòu)建好后,對給定的模式段,使用算法3-2,能快速定位模式段值域范圍內(nèi)的突變段集合,并通過交集操作,保證輸出集合里的每個突變段都能完全地覆蓋模式段。

進一步,對于算法2第3-4行,還可以對各突變段構(gòu)造倒排索引,使得給定yt可直接定位到y(tǒng)h,從而免去遍歷突變段節(jié)點搜索yh?yt的過程。下節(jié)的算法4第4行使用了這個思想。

3.3.2 相似度函數(shù)的下界優(yōu)化

通過考察相似度函數(shù)的性質(zhì),能進一步對算法2進行優(yōu)化。對sim函數(shù),容易證明其存在一個下界:

(3)

(4)

n是突變段的終點,cr(j,n)即為從j點出發(fā)到終點的累積弧度。對于每個突變段,可以預先離線計算從各點出發(fā)的到終點的累積弧度并存儲;當模式段匹配動態(tài)進行時,通過式(4)迅速得出sim函數(shù)的下界。

利用式(3),對算法2進行改進。算法4給出了具體過程:

算法4 模式段匹配的優(yōu)化

輸入: 模式段Q={yi,…,yt},歷史突變段集合{sp}

輸出:最佳匹配sq,匹配時刻e

1 best=∞,e=q=-1

2 queue=PriorityQueue()

3 for sjin{sp}:

4 for each yh∈sjthat yh==yt:

5 Ibjh=lower_bound({yi,…,yt},{yh-(t-i),yh})

6 queue.push(queue)

7 while queue not empty:

8 Ibjh=queue.pop()

9 if Ibjh≥best:

10 break

11 else:

12 m=sim({yi,…,yt},{yh-(t-i),yh})

13 if m>best:

14 best=m,e=h,q=j

15 return sq,e

算法4的第4行先計算sim函數(shù)下界,這是當前匹配段和模式段至多能達到的最優(yōu)相似度。然后,通過一個優(yōu)先隊列,優(yōu)先計算目前擁有最優(yōu)下界的匹配段,并不斷更新相似度最優(yōu)值。在隊列不斷出列的過程中,判斷余下的未計算部分是否已經(jīng)沒有計算的必要(第9～10行)。通過此優(yōu)化,能迅速過濾掉很多和模式段形態(tài)差距較大的匹配段,大大加快算法性能。

4 實驗分析

4.1 實驗準備和數(shù)據(jù)源

本實驗所用硬件環(huán)境為一臺雙核i3-3220,3.30 GHz,8 GB內(nèi)存的臺式電腦,操作系統(tǒng)為Ubuntu 15.10,所使用的語言為python3.4和R。實驗數(shù)據(jù)來自上海交通部門提供的包含40個發(fā)布段,時間跨度從2013年9月到2013年11月的大約150萬條真實數(shù)據(jù),每條數(shù)據(jù)包含10列屬性,包括時間,車速等。數(shù)據(jù)采集自上?？焖俾飞显O置的線圈傳感器。在每個定義的發(fā)布段的車道上,布下多個線圈傳感器,記錄每輛車通過的時間,系統(tǒng)每20秒記錄一次通過的平均車速。使用第1節(jié)論述的方法對數(shù)據(jù)先進行預處理清洗。

4.2 實驗1

實驗1測試突變段挖掘算法的實際效果。圖5(1)-(3)為3組參數(shù)下的搜索示例圖,取自上海內(nèi)環(huán)高架新華路-吳中路匝道.該數(shù)據(jù)源每天的時間序列由4 320個點組成。圖5中(1)、(2)為同一天數(shù)據(jù)。黑色實線代表挖掘出的突變段。

圖5 測試突變段挖掘算法實效

使用3個指標作為挖掘結(jié)果的衡量標準,以便對結(jié)果的特征進行量化:(1) 結(jié)果數(shù)目;(2) 結(jié)果的平均長度;(3) 結(jié)果自身的波動大小(方差)。實驗發(fā)現(xiàn),模型的三個參數(shù)中,k和ε對搜索結(jié)果有較大影響,如圖5(1)、(2)所示。較小的ε值會增大搜索的結(jié)果數(shù)目和平均長度。而較小的值會使搜索結(jié)果的趨勢局限在更小的范圍。對不同的發(fā)布段使用相同的參數(shù),得到的3個指標也不十分一致?？赡艿脑蚴歉靼l(fā)布段的路段格局,車流量,是否有限速行駛等條件不同。因此,實際應用中,需要對各個發(fā)布段的參數(shù)進行調(diào)校,使得搜索結(jié)果的特征符合使用者的需求。由于參數(shù)少且直觀,調(diào)校過程并不復雜。在實驗1中,我們通過枚舉一系列參數(shù)值,人工對結(jié)果進行主觀打分,從而為每個發(fā)布段選取一組主觀最滿意的參數(shù),然后進行后續(xù)實驗。

4.3 實驗2

實驗2使用預測模型,對普通工作日、雙休日、普通公共假日及國慶期間等典型的日期先分類,然后進行短時速度預測。首先,把發(fā)布段數(shù)據(jù)樣本按天分類,隨機剔除3個普通工作日、1個強雨雪日、2個雙周日和1個國慶日作為被預測樣本,其余作為歷史數(shù)據(jù)。然后,從每個被預測樣本中截取多個代表時間段和突變段作為模型輸入。從模型的輸出結(jié)果中選取1分鐘、5分鐘和15分鐘的預測結(jié)果。最后,將預測結(jié)果同被預測樣本的實際速度曲線進行對比,統(tǒng)計各發(fā)布段預測的預測效果,如表1所示。

表1 不同發(fā)布段在不同預測時長下的誤差統(tǒng)計

其中,誤差指的是預測結(jié)果相比實際值的相對誤差。平均誤差是各發(fā)布段所有被測試段相對誤差的平均值?？梢钥闯?模型有較好的短時預測精度。在5min預測時長內(nèi)可達94%左右的預測精度,15min預測時長內(nèi)也有接近90%的預測精度。隨著預測時間增長,模型的預測結(jié)果越不準確,這和直覺相符,因為預測時間越長,更多和歷史數(shù)據(jù)條件不一致的隨機因素會逐漸產(chǎn)生影響。因此,該模型適合短時預測。在實時預測中,可以不停地迭代更新模型的輸入,修正預測結(jié)果。

4.4 實驗3

實驗3分析算法2和算法4的性能對比,以驗證第3.3節(jié)提出的優(yōu)化方案效果。在實驗2的過程中,預先建立了相應的索引結(jié)構(gòu),分別使用算法2和算法4執(zhí)行預測并統(tǒng)計完成時間。圖6顯示的是對不同被測模式段,其長度和預測算法執(zhí)行時間的對應曲線?？梢钥闯瞿Ｊ蕉蔚拈L度和執(zhí)行時間大致成正比,因為計算sim函數(shù)時候的開銷也相應增加。但在算法4中,因為計算sim函數(shù)下界的開銷與模式段長度無關,所以帶來的總體開銷增長較慢。平均情況下,算法4能比算法2性能高32%左右,證明了優(yōu)化的有效性。算法4可被用于實時交通流的預測。

圖6 模式段匹配算法優(yōu)化前后對比

5 結(jié) 語

快速路的突變段挖掘問題是根據(jù)實際交通需求產(chǎn)生的問題,基于累積弧度的定義方法簡潔有效,具有挖掘不同尺度突變段的能力;基于突變段的行程速度預測模型為快速路的短時交通預測提供了新的思路和方法,它利用了歷史數(shù)據(jù)庫匹配的技術(shù),實驗證明了其能夠取得比較準確的預測結(jié)果。未來的工作將著眼于在海量數(shù)據(jù)的實時在線環(huán)境下,如何通過大數(shù)據(jù)等技術(shù),拓展本文的預測模型,進一步加強模型處理海量數(shù)據(jù)的性能和實用性。

[1] 高慧,趙建玉,賈磊.短時交通流預測方法綜述[J].濟南大學學報(自然科學版),2008,22(1):88-94.

[2] 池紅波.基于城市快速路實時觀測數(shù)據(jù)的交通預測方法研究[D].北京工業(yè)大學,2004.

[3]KrauseB,VonAltrockC,PozybillM.Intelligenthighwaybyfuzzylogic:congestiondetectionandtrafficcontrolonmulti-laneroadswithvariableroadsigns[C]//IEEEInternationalConferenceonFuzzySystems,NewOrleans,1996:FuzzySystems,1996:1832-1837.

[4]DingY,YangX,KavsAJ,etal.Anovelpiecewiselinearsegmentationfortimeseries[C]//ComputerandAutomationEngineering(ICCAE),2010:The2ndInternationalConferenceon.IEEE,2010:52-55.

[5]EleniIVlahogianni,JohnCGolias,MatthewGKarlaftis.Short-termtrafficforecasting:overviewofobjectivesandmethods[J].TransportReviews,2004,24(5):533-557.

[6] 翁劍成,榮建,任福田,等.基于非參數(shù)回歸的快速路行程速度短期預測算法[J].公路交通科技,2007,24(3):93-97.

[7] Smith B L,Demetsky M J.Traffic flow forecasting:comparison of modeling approaches[J].Journal of Transportation Engineering,1997,123(4):261-266.

[8] Okutani I,Stephanedes Y J.Dynamic prediction of traffic volume through kalman filtering theory[J].Transportation Research Part B Methodological,1984,18(1):1-11.

[9] Dougherty M S,Cobbett M R.Short-term inter-urban traffic forecasts using neural networks[J].International Journal of Forecasting,1997,13(1):21-31.

[10] Voort M V D,Dougherty M,Watson S.Combining kohonen maps with arima time series models to forecast traffic flow[J].Transportation Research Part C Emerging Technologies,1996,4(5):307-318.

[11] 李振龍,張利國,錢海峰.基于非參數(shù)回歸的短時交通流預測研究綜述[J].交通運輸工程與信息學報,2008(4):34-39.

[12] Fu T C,Chung F L,Luk R,et al.Representing financial time series based on data point importance[J].Engineering Applications of Artificial Intelligence,2008,21(2):277-300.

[13] Chakrabarti K,Keogh E,Mehrotra S,et al.Locally adaptive dimensionality reduction for indexing large time series databases[J].Acm Transactions on Database Systems,2002,27(2):188-228.

[14] Mesnil Benoit,Petitgas Pierre.Detection of changes in time-series of indicators using CUSUM control charts[J].Aquatic Living Resources,2009,22(2):187-192.

[15] Chao Chen,Jaimyoung,Kwon,et al.Detecting errors and inputting missing data for single-loop surveillance system[J].Transportation Research Record:Journal of the Transportation Research Board,2003,1855:160-167.

[16] Liu li,He Xianping,Yuan Wenliang.A unifying framework for detecting outliers and change points from non-stationary time series data[J].Journal of Taiyuan Normal University,2011:676-681.

[17] 丁永偉,楊小虎,陳根才,等.基于弧度距離的時間序列相似度量[J].電子與信息學報,2011,33(1):122-128.

[18] 董曉莉,顧成奎,王正歐.基于形態(tài)的時間序列相似性度量研究[J].Journal of Electronics & Information Technology,2007(5):1228-1231.

VELOCITY FLUCTUATION PERIOD MINING FOR EXPRESSWAY TRAFFIC FLOW ANDSHORT-TERM FORECASTING ALGORITHM BASED ON SIMILARITY MATCHING

Li Xinyue Yang Weidong Zhang Zheng Xu Haibo

(SchoolofComputerScience,FudanUniversity,Shanghai201203,China)

Traffic flow on urban expressways has obvious characteristics that its travel velocity changes drastically between the smooth condition and the congestion. On the basis of data collected by coil sensors on Shanghai expressway, we propose a promising linear sliding window method to mine the travel velocity fluctuation periods in traffic time series, solving the requirements such as identifying the start and stop moment of congestion. Then, we construct the history sample database of fluctuation periods and the custom index, and propose an optimized forecasting model based on similarity matching to achieve the purpose of short-term forecasting of travel velocity. The model is more practical and intuitive than traditional regression model. Finally, we use huge amounts of real data to test the effectiveness and performance of these two models. Experimental results show that the mining algorithm can complete fluctuation period query at different scales through simple parameter tuning, while the forecasting model can effectively meet the performance requirement of real-time query and reach a high forecasting accuracy around 90% in 15 minutes.

Time series Travel velocity Fluctuation period Sliding window Short-term traffic forecasting Similarity Index construction

2016-02-04。國家十二五專項(CHINARE2012-04-07，MJ-Y-2011-39)；上海市重點基礎研究項目(08JC402500)；上海市高新技術(shù)創(chuàng)新專項(11CH-03)；海洋公益項目(201405031-04)；上海市科學技術(shù)委員會科研計劃項目(14511107403)。李心玥，碩士，主研領域：交通數(shù)據(jù)挖掘分析，數(shù)據(jù)安全訪問控制。楊衛(wèi)東，教授。張徵，碩士。許海波，碩士。

TP392

A

10.3969/j.issn.1000-386x.2017.03.007