快速路行程速度突變段挖掘和基于相似匹配的短時(shí)預(yù)測(cè)算法

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

(復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院 上海 201203)

快速路行程速度突變段挖掘和基于相似匹配的短時(shí)預(yù)測(cè)算法

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

(復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院 上海 201203)

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

時(shí)間序列 行程速度 突變段 滑動(dòng)窗口 短時(shí)交通預(yù)測(cè) 相似度 索引構(gòu)造

0 引 言

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

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

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

圖1 快速路的時(shí)間-行程速度曲線

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

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

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

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

2 突變段的識(shí)別和挖掘

2.1 突變段問(wèn)題定義

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

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

(1)

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

圖2 分段弧度示意圖

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

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

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

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

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

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

2.2 時(shí)間序列上挖掘突變段的算法

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

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

圖3 滑動(dòng)窗口示意圖

算法1 挖掘突變段偽代碼

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

輸出:所有長(zhǎng)度不小于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):

# 更新滑動(dòng)窗口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

# 更新滑動(dòng)窗口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次,時(shí)間復(fù)雜度O(L×k×|ω|),滑動(dòng)窗口滑動(dòng)并檢驗(yàn)耗時(shí)O(n),整體復(fù)雜度O(n+L×K×|ω|)。因?yàn)閗,L,|ω|≤n時(shí),所以最后得到算法1的時(shí)間復(fù)雜度O(n),額外空間復(fù)雜度O(L)(不計(jì)輸入序列)。

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

3 基于突變段的短時(shí)速度預(yù)測(cè)

3.1 預(yù)測(cè)模型和基本算法

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

圖4 預(yù)測(cè)模型框架

預(yù)測(cè)模型接受一個(gè)實(shí)時(shí)輸入經(jīng)過(guò)預(yù)處理的采集序列。令當(dāng)前時(shí)刻為t,預(yù)測(cè)模型計(jì)算并輸出Δt時(shí)間后的預(yù)測(cè)速度。

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

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

…+(1-α)kyt-k

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

B) 否則,記當(dāng)前突變段為Q={yi,…,yt},稱為模式段。在該路段的n個(gè)歷史突變段{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}))。

通過(guò)A-B兩個(gè)步驟,預(yù)測(cè)模型反饋預(yù)測(cè)結(jié)果。因?yàn)檩斎霐?shù)據(jù)實(shí)時(shí)變化,因此預(yù)測(cè)模型也可以實(shí)時(shí)更新預(yù)測(cè)結(jié)果。容易看出,該模型對(duì)較小的Δt有較好的預(yù)測(cè)值。一般要求Δt不超過(guò)15分鐘。

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

算法2 模式段匹配偽代碼

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

輸出:最佳匹配sq,匹配時(shí)刻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 相似性度量

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

(2)

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

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

3.3.1 索引的構(gòu)建

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

算法3-1 索引生成

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

輸出:索引Index

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

3 for min[1,h):

# 構(gòu)造索引

算法3-2 索引查找

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

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

1 H=φ

2 for min[1,h):

4 if H is φ:

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

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

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

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

(3)

(4)

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

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

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

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

輸出:最佳匹配sq,匹配時(shí)刻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行先計(jì)算sim函數(shù)下界,這是當(dāng)前匹配段和模式段至多能達(dá)到的最優(yōu)相似度。然后,通過(guò)一個(gè)優(yōu)先隊(duì)列,優(yōu)先計(jì)算目前擁有最優(yōu)下界的匹配段,并不斷更新相似度最優(yōu)值。在隊(duì)列不斷出列的過(guò)程中,判斷余下的未計(jì)算部分是否已經(jīng)沒(méi)有計(jì)算的必要(第9～10行)。通過(guò)此優(yōu)化,能迅速過(guò)濾掉很多和模式段形態(tài)差距較大的匹配段,大大加快算法性能。

4 實(shí)驗(yàn)分析

4.1 實(shí)驗(yàn)準(zhǔn)備和數(shù)據(jù)源

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

4.2 實(shí)驗(yàn)1

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

圖5 測(cè)試突變段挖掘算法實(shí)效

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

4.3 實(shí)驗(yàn)2

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

表1 不同發(fā)布段在不同預(yù)測(cè)時(shí)長(zhǎng)下的誤差統(tǒng)計(jì)

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

4.4 實(shí)驗(yàn)3

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

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

5 結(jié) 語(yǔ)

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

[1] 高慧,趙建玉,賈磊.短時(shí)交通流預(yù)測(cè)方法綜述[J].濟(jì)南大學(xué)學(xué)報(bào)(自然科學(xué)版),2008,22(1):88-94.

[2] 池紅波.基于城市快速路實(shí)時(shí)觀測(cè)數(shù)據(jù)的交通預(yù)測(cè)方法研究[D].北京工業(yè)大學(xué),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ù)回歸的快速路行程速度短期預(yù)測(cè)算法[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] 李振龍,張利國(guó),錢(qián)海峰.基于非參數(shù)回歸的短時(shí)交通流預(yù)測(cè)研究綜述[J].交通運(yùn)輸工程與信息學(xué)報(bào),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] 丁永偉,楊小虎,陳根才,等.基于弧度距離的時(shí)間序列相似度量[J].電子與信息學(xué)報(bào),2011,33(1):122-128.

[18] 董曉莉,顧成奎,王正歐.基于形態(tài)的時(shí)間序列相似性度量研究[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。國(guó)家十二五專項(xiàng)(CHINARE2012-04-07，MJ-Y-2011-39)；上海市重點(diǎn)基礎(chǔ)研究項(xiàng)目(08JC402500)；上海市高新技術(shù)創(chuàng)新專項(xiàng)(11CH-03)；海洋公益項(xiàng)目(201405031-04)；上海市科學(xué)技術(shù)委員會(huì)科研計(jì)劃項(xiàng)目(14511107403)。李心玥，碩士，主研領(lǐng)域：交通數(shù)據(jù)挖掘分析，數(shù)據(jù)安全訪問(wèn)控制。楊衛(wèi)東，教授。張徵，碩士。許海波，碩士。

TP392

A

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