基于DTW距離聚類的交叉口擁堵檢測(cè)

梁坤,孫莉,羅建鋒

(1.淮陰工學(xué)院 管理工程學(xué)院，江蘇 淮安 223300；2. 江蘇省交通運(yùn)輸與安全保障重點(diǎn)實(shí)驗(yàn)室,江蘇 淮安 223300; 3. 淮陰工學(xué)院 研究生處，江蘇 淮安 223300)*

?

基于DTW距離聚類的交叉口擁堵檢測(cè)

梁坤1,2,孫莉3,羅建鋒1

(1.淮陰工學(xué)院 管理工程學(xué)院，江蘇 淮安 223300；2. 江蘇省交通運(yùn)輸與安全保障重點(diǎn)實(shí)驗(yàn)室,江蘇 淮安 223300; 3. 淮陰工學(xué)院 研究生處，江蘇 淮安 223300)*

交叉口是城市交通的關(guān)鍵節(jié)點(diǎn)，常發(fā)生交通擁堵，在分析交叉口采集的地點(diǎn)平均車速、流量和時(shí)間占有率時(shí)間序列特征的基礎(chǔ)上，提出了交叉口入口交通狀態(tài)動(dòng)態(tài)時(shí)間彎曲( dynamic time warping，DTW)相似度量和K均值聚類的交叉口交通擁堵檢測(cè)方法，并以某城市70個(gè)交叉口實(shí)測(cè)交通數(shù)據(jù)為例進(jìn)行了擁堵檢測(cè)，結(jié)果表明了該方法的可行性.

交通擁堵；交叉口；擁堵檢測(cè)；動(dòng)態(tài)時(shí)間彎曲；K均值聚類

0 引言

交叉口在城市路網(wǎng)中占有比重大，是城市交通正常運(yùn)行的關(guān)鍵節(jié)點(diǎn)和擁堵發(fā)生的主要位置.交叉口擁堵導(dǎo)致的環(huán)境的污染、出行安全隱患和嚴(yán)重的經(jīng)濟(jì)損失阻礙了城市經(jīng)濟(jì)和社會(huì)的發(fā)展.當(dāng)前智慧城市、物聯(lián)網(wǎng)的建設(shè)和信息快速傳輸、數(shù)據(jù)存儲(chǔ)技術(shù)的快速發(fā)展為城市路網(wǎng)中交叉口交通信息的實(shí)時(shí)采集和大量信息存儲(chǔ)提供了條件，這也為研究城市交叉口擁堵致因和治理提供了新的可能，交通大數(shù)據(jù)必將促進(jìn)智慧交通的大幅發(fā)展.目前己有的關(guān)于交叉路口擁堵的研究，主要集中在交叉口的特性分析上和交叉口擁堵治理的定性措施上，而對(duì)交叉口擁堵檢測(cè)及相鄰交叉路口的相互性與整體性研究較少[1-8].對(duì)于擁堵識(shí)別的算法文獻(xiàn)[9]提出了增量式貝葉斯分類器方法，該方法針對(duì)路段數(shù)據(jù)進(jìn)行擁堵二分類識(shí)別，并且需擁堵的樣本集，且二分類問題無法反應(yīng)交通狀態(tài)由暢通到擁堵的變化過程；文獻(xiàn)[10-11]提出了基于 FFCM 聚類的城市交通擁堵判別和基于支持向量機(jī)的城市道路交通擁堵判別方法，表明了聚類對(duì)路段擁堵識(shí)別是一種有效方法，但對(duì)復(fù)雜的交叉口交通流特征參數(shù)時(shí)間序列沒有研究.前面的一些交通擁堵識(shí)別研究多是針對(duì)路段，而對(duì)交叉口交通流數(shù)據(jù)的周期變化規(guī)律及上下游鄰近交叉口交通流數(shù)據(jù)相關(guān)性的研究不足.交叉口處的擁堵在我國城市交通問題中尤為突出，因此及時(shí)檢測(cè)交叉口擁堵的發(fā)生，研究交叉口擁堵機(jī)理對(duì)提出針對(duì)性的交叉口擁堵治理措施和緩解城市交通擁堵，保證道路的高效暢通有重要意義.

本文針對(duì)信號(hào)交叉口采集的交通特征量進(jìn)行分析，提出基于時(shí)間序列動(dòng)態(tài)時(shí)間彎曲( dynamic time warping，DTW)距離聚類的交叉口交通擁堵檢測(cè)方法.首先分析交叉口常用表征交通運(yùn)行狀態(tài)的交通特征量，然后針對(duì)交通特征量時(shí)間序列特征選用動(dòng)態(tài)時(shí)間彎曲(DTW)方法進(jìn)行交叉口聚類分析，最后用某城市實(shí)測(cè)交叉口數(shù)據(jù)進(jìn)行驗(yàn)證.

1 交通特征量分析

交叉口交通運(yùn)行狀態(tài)的交通特征量主要有速度、流量、密度、占有率、排隊(duì)長度、交通延誤等.國內(nèi)外對(duì)于交通狀態(tài)的檢測(cè)已開展了一些研究，20世紀(jì)60年代美國加州運(yùn)輸部開發(fā)的加州算法采用檢測(cè)截面占有率進(jìn)行交通狀態(tài)檢測(cè)；校準(zhǔn)偏差算法采用交通量或占有率判別交通狀態(tài)；雙指數(shù)平滑算法采用速度、流量、占有率和密度三者之一進(jìn)行交通擁堵判別；由加拿大的McMaster大學(xué)土木工程系開發(fā)的McMaster算法采用速度和占有率檢測(cè)交通狀態(tài)[12].根據(jù)數(shù)據(jù)采集的方便性和可行性選用速度、流量和占有率(時(shí)間占有率)作為交叉口交通特征量進(jìn)行分析.

速度S采用車輛通過某一地點(diǎn)時(shí)的瞬時(shí)車速，既地點(diǎn)車速作為交叉口車速特征量.交通量V采用指定的時(shí)間內(nèi)通過交叉口入口上游路段某一斷面的機(jī)動(dòng)車數(shù)量為交通特征量.對(duì)交通流數(shù)據(jù)采集過程中得到的混合交通量將比例最大的轎車選為標(biāo)準(zhǔn)車型，其他類型的車輛與轎車之間的換算采用表1系數(shù)[13].時(shí)間占有率O是指在一定的觀測(cè)時(shí)間T內(nèi)，交通檢測(cè)器被車輛占用的時(shí)間的總和與觀測(cè)時(shí)間長度的比值即∑Δti/T，Δti為第i輛車占用檢測(cè)器的時(shí)間(s).

表1 當(dāng)量小汽車換算系數(shù)

在交叉口對(duì)三個(gè)交通特征量采集如圖1，Ii表示第i個(gè)交叉口，Iij(j=1,2,…)表示第j個(gè)入口方向，ISij、IVij、IOij分別表示i交叉口j入口的速度、流量和占有率；采集位置在離交叉口100 m處[14].采集時(shí)間間隔5 min，ISij采用均值作為i交叉口j入口的速度.針對(duì)某城市兩交叉口實(shí)測(cè)24 h交通速度、流量和占有率時(shí)間序列如圖2.

圖1 交叉口數(shù)據(jù)采集示意圖

(a)相鄰交叉上下游入口時(shí)間占有率檢測(cè)值圖

(b)相鄰交叉上下游入口地點(diǎn)車速檢測(cè)值圖

(c)相鄰交叉上下游入口交通量檢測(cè)值圖

從圖2可以看出擁堵和暢通交叉口速度、流量和占有率在時(shí)間軸上都有各自的上升和下降變化規(guī)律，而在交叉口1擁堵時(shí)前后的速度、流量和占有率這種上升和下降的趨勢(shì)更加明顯.因此如果用單個(gè)的時(shí)間點(diǎn)檢測(cè)速度、流量和占有率檢測(cè)交叉口擁堵就無法體現(xiàn)出時(shí)間軸上這些參數(shù)的變化特性.另外，交叉口大多是信號(hào)控制交叉口，信號(hào)周期的變化的影響對(duì)檢測(cè)到的速度、流量和占有率也難以和路段檢測(cè)到的交通特征量直接用于檢測(cè)交通擁堵.傳統(tǒng)的路段擁堵檢測(cè)方法對(duì)交叉口難以適用，而動(dòng)態(tài)時(shí)間彎曲距離可以較好的對(duì)不等長、異步的時(shí)間序列的相似性進(jìn)行度量，對(duì)于將要發(fā)生擁堵的交叉口通過檢測(cè)的交通特征量時(shí)間序列的相似度可檢測(cè)擁堵的發(fā)生.

2 動(dòng)態(tài)時(shí)間彎曲(DTW)的K均值聚類

2.1 動(dòng)態(tài)時(shí)間彎曲(DTW)

動(dòng)態(tài)時(shí)間彎曲( dynamic time warping，DTW)是一種通過彎曲時(shí)間軸來更好地對(duì)時(shí)間序列形態(tài)進(jìn)行匹配映射的相似性度量方法[15].DTW可以對(duì)不等長和等長的時(shí)間序列進(jìn)行相似性度量和實(shí)現(xiàn)時(shí)間序列異步相似性比較，對(duì)時(shí)間序列中的突變或異常點(diǎn)不敏感，能較好的解決時(shí)間軸伸縮、線性漂移、彎曲和噪聲等歐氏距離距離難以處理的問題.因此該方法可應(yīng)用于不同交叉口入口交通特征量時(shí)間序列的相似性度量問題.基本原理是對(duì)兩個(gè)時(shí)間序列在局部進(jìn)行拉伸和壓縮使其中一個(gè)時(shí)間序列盡可能的相似另外一個(gè)時(shí)間序列，拉伸和壓縮后兩時(shí)間序列中對(duì)齊元素的距離和就是兩時(shí)間序列之間的DTW距離.文獻(xiàn)[15]給出了計(jì)算兩時(shí)間序列DTW距離的算法的原理，設(shè)X=(x1,x2,…,xn)是參考時(shí)間序列和T=(y1,y2,…,ym)是檢驗(yàn)時(shí)間序列，序列點(diǎn)xi和yj之間的距離為

(1)

d(i,j)表示點(diǎn)xi和yj的相似度量，兩者越相似或越接近, 其值越接近 0，反之其值越大.以d(i,j)作為元素按時(shí)間順序構(gòu)造時(shí)間序列X與T之間點(diǎn)與點(diǎn)距離矩陣Dn×m

(2)

在矩陣Dn×m中有一條最短路徑作為動(dòng)態(tài)時(shí)間彎曲路徑，即：

(3)

式(3)中W是一條時(shí)間彎曲路徑，W=(w1,w2,…,wp)，p=1,2,…,P,max(n,m)≤P≤n+m表示時(shí)間序列X與T之間元素對(duì)齊匹配關(guān)系，每一個(gè)wp對(duì)應(yīng)點(diǎn)(ip,jp)表示xi和yj對(duì)齊匹配.且W滿足以下條件：

(1)單調(diào)性：點(diǎn)(ip,jp)隨時(shí)間增加，ip-1≤ip，jp-1≤jp；

(2)連續(xù)性：wp-1和wp對(duì)應(yīng)的點(diǎn)必須是相鄰點(diǎn)，ip-1-ip≤1，jp-1-jp≤1；

(3)邊界條件：彎曲路徑W應(yīng)該起于點(diǎn)(1,1)終于點(diǎn)(n,m)，即w1對(duì)應(yīng)點(diǎn)(1,1)，wp對(duì)應(yīng)點(diǎn)(n,m).

時(shí)間序列X與T的DTW距離定義為最短動(dòng)態(tài)時(shí)間彎曲路徑上的累積距離，由當(dāng)前匹配點(diǎn)xi和yj之間的距離和相鄰點(diǎn)的累積動(dòng)態(tài)距離計(jì)算得到，公式為

(4)

對(duì)累積距離歸一化得到時(shí)間序列X與T的歸一化DTW距離

(5)

2.2 K均值聚類的交叉口擁堵檢測(cè)

基于K均值聚類的交叉口擁堵檢測(cè)的原理是聚類中的小樣本事件是異常事件.交叉口交通異常事件是指交通特征量明顯不同于該交叉口非擁堵時(shí)交通特征量的交通現(xiàn)象.在城市的路網(wǎng)中，一般一天中開始發(fā)生交通擁堵時(shí)，同時(shí)擁堵的交叉口數(shù)量較少，應(yīng)用交叉口入口交通運(yùn)行狀態(tài)的DTW相似度進(jìn)行聚類，聚類簇中樣本數(shù)少的類識(shí)為擁堵交叉口，擁堵傳播方向?yàn)槿肟诼范谓煌鞣捶较?K均值聚類算法是首先隨機(jī)從檢測(cè)交叉口入口速度、流量和占有率三者之一的數(shù)據(jù)集中選取 K個(gè)入口作為初始聚類中心，然后計(jì)算各入口到聚類中的DTW距離，把入口歸到離它最相似的那個(gè)聚類中心所在的類.計(jì)算新形成的每一個(gè)聚類的交叉口入口檢測(cè)數(shù)據(jù)對(duì)象的平均值來得到新的交叉口入口聚類中心，如果相鄰兩次的聚類中心沒有任何變化，說明交叉口入口聚類調(diào)整結(jié)束，完成交叉口入口交通狀態(tài)聚類.聚類簇中最少的入口對(duì)應(yīng)的交叉口初步檢測(cè)為擁堵交叉口，然后根據(jù)《城市交通管理評(píng)價(jià)指標(biāo)體系》中規(guī)定的城市交通擁堵的程度判定標(biāo)準(zhǔn)進(jìn)一步確認(rèn)其交叉口的擁堵[16].

3 交叉口擁堵檢測(cè)實(shí)例

交叉口擁堵檢測(cè)是根據(jù)交叉口入口檢測(cè)的時(shí)間占有率參數(shù)值的一階差分時(shí)間序列將交叉口入口路段交通狀態(tài)相似的多個(gè)入口交通狀態(tài)歸類.對(duì)某城市70個(gè)交叉口，171個(gè)入口檢測(cè)占有率數(shù)據(jù)進(jìn)行DTW相似度進(jìn)行聚類分析，數(shù)據(jù)如表2.

表2 交叉口時(shí)間占有率檢測(cè)數(shù)據(jù)表

根據(jù)交叉口入口的檢測(cè)數(shù)據(jù)，在早晨7∶30∶00對(duì)某城市70個(gè)交叉口，171個(gè)入口進(jìn)行聚類，第一步選取7∶30前所有交叉口入口的時(shí)間占有率檢測(cè)數(shù)據(jù)為聚類時(shí)間序列，第二步用計(jì)算171個(gè)交叉口入口的交通狀態(tài)的DTW距離(即相似度)，第三步用聚類組內(nèi)的距離平方和總量的碎石圖(如圖3)確定K值得個(gè)數(shù)2[17]，第四步，用K均值方法進(jìn)行交叉口入口的交通狀態(tài)聚類，結(jié)果如圖4.

圖3 聚類組內(nèi)的距離平方和總量的碎石圖

圖4中交叉口入口的交通狀態(tài)分類兩類，類C1中有167個(gè)交叉口入口樣本，類C2中有4個(gè)交叉口入口樣本.根據(jù)聚類中的小樣本事件是異常事件，可把類C2中入口對(duì)應(yīng)的交叉口為擁堵交叉口，入口的交通流的反方向?yàn)閾矶聜鞑シ较?對(duì)兩類中的任選一個(gè)交叉口入口繪制其時(shí)間占有率和地點(diǎn)車速，如圖5,其中x軸0對(duì)應(yīng)00∶00、150對(duì)應(yīng)02∶30、300對(duì)應(yīng)05∶00、450對(duì)應(yīng)07∶30.從圖5可以看出7∶30檢測(cè)為擁堵的交叉口其擁堵入口的占有率為0.8、平均地點(diǎn)車速為8.5km/h,而非擁堵交叉口其時(shí)間占有率為0.26、平均地點(diǎn)車速為42km/h，這和《城市交通管理評(píng)價(jià)指標(biāo)體系》中規(guī)定的城市道路交通擁堵的程度判定不同等級(jí)道路行程速度5級(jí)最擁堵的小于等于10km/h及非擁堵車速大于等于35km/h標(biāo)準(zhǔn)相符，驗(yàn)證了本文方法檢測(cè)交叉口擁堵可行.

圖5 不同類入口交通狀態(tài)參數(shù)圖

4 結(jié)論

交叉口處的擁堵是我國城市交通突出問題之一，智慧城市建設(shè)生成的交通大數(shù)據(jù)為交叉口擁堵提供了新的研究手段.交叉口擁堵檢測(cè),本文提出了交叉口入口交通狀態(tài)動(dòng)態(tài)時(shí)間彎曲(DTW)的K均值聚類方法，并通過某城市交叉口實(shí)測(cè)數(shù)據(jù)驗(yàn)證了該方法的有效性.這為交通擁堵的研究提供了新的思路，同時(shí)交叉口擁堵及時(shí)檢測(cè)對(duì)城市交通擁堵的管理有重要的意義.文中擁堵的檢測(cè)只采用了時(shí)間占有率特征量，而對(duì)多特征量和檢測(cè)時(shí)間序列長度的選取是進(jìn)一步研究方向.

[1]姜桂艷，郭海鋒，孟志強(qiáng)，等.基于實(shí)時(shí)信息的城市道路交通狀態(tài)評(píng)價(jià)指標(biāo)體系研究[J].交通與計(jì)算機(jī)，2007 , 25 (5) : 21-24.

[2]盧明宇, 王興. 交叉口交通擁堵分析與對(duì)策[J]. 長春工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版), 2015, 36(3): 327-332.

[2]景春光, 曲大義, 梁春巖. 兩相位交叉口機(jī)非沖突對(duì)機(jī)動(dòng)車飽和流率的影響研究[J]. 公路交通科技, 2007, 24(8): 124-127.

[3]葉燕仙, 何操, 陳李軍. 基于 VISSIM 的溫江城區(qū)交叉口擁堵優(yōu)化研究[J]. 公路與汽運(yùn), 2012 (2): 56-60.

[4]陳曉明, 邵春福, 熊志華. 混合交通信號(hào)交叉口的通行能力可靠度[J]. 中國公路學(xué)報(bào), 2008, 21(4): 99-104.

[5]任其亮, 肖裕民. 城市路網(wǎng)交通擁堵 H-Fuzzy 評(píng)判方法研究[J]. 重慶交通大學(xué)學(xué)報(bào)(自然科學(xué)版), 2008, 27(5): 763-766.

[6]周桃. 溫江城區(qū)交叉口擁堵問題分析及對(duì)策研究 [D].西安：長安大學(xué), 2012.

[7]陳小紅, 錢大琳. 城市道路交叉路口的擁堵預(yù)測(cè)木[J]. 華南理工大學(xué)學(xué)報(bào) (自然科學(xué)版), 2010, 38(7)：72-77.

[8]王東, 陳笑蓉. 增量式貝葉斯分類器在交通擁堵判別中的應(yīng)用[J]. 計(jì)算機(jī)輔助工程, 2008, 16(4): 56-59.

[9]楊祖元, 黃席樾, 杜長海, 等. 基于 FFCM 聚類的城市交通擁堵判別研究[J]. 計(jì)算機(jī)應(yīng)用研究, 2008, 25(9): 2768-2770.

[10]鄭長江, 路源. 基于支持向量機(jī)的城市道路交通擁堵判別算法研究[J]. 貴州大學(xué)學(xué)報(bào): 自然科學(xué)版, 2014, 31(1): 113-117.

[11]姜桂艷.道路交通狀態(tài)判別技術(shù)與應(yīng)用[M].北京：人民交通出版社，2004.

[12]中華人民共和國建設(shè)部.GB 50220-95城市道路交通規(guī)劃設(shè)計(jì)規(guī)范[S].北京：中國計(jì)劃出版社，1995.

[13]毛保華，孫壯志，賈順平，等.區(qū)域交通組織優(yōu)化方法及實(shí)踐研究[M].北京:人民交通出版社，2007.

[14]BERNDT D J, CLIFFORD J. Using dynamic time warping to find patterns in time series[J].KDD workshop,1994, 10(16): 359-370.

[15]中國道路交通安全網(wǎng)：城市交通管理評(píng)價(jià)指標(biāo)體系[EB/OL][2013-10-27]http://www.rtsac.org/Html/2013_10_27/2_1931_203_10_27_12656,html.

[16]TAN P N, STEINBACH M, KUMAR V. 數(shù)據(jù)挖掘?qū)д?[M]. 北京：人民郵電出本社，2011.

Study of Detecting Intersection Congestion based on DTW Distance Clustering

LIANG Kun1，SUN Li2，LUO Jianfeng1

(1.Management Engineering Institute, Huaiyin Institute of Technology, Huai′an 223003, China 2.Graduate Student Office, Huaiyin Institute of Technology, Huai′an 223003, China)

Aiming at intersection of urban transport where traffic congestion often occurs, the intersection traffic congestion identification method of dynamic time warping (dynamic time warping , DTW) similar measure of the entrance intersection traffic state and K-means clustering is proposes based on the analyzing time series characteristics of detecting average speed and traffic volume. With true data, 70 intersection traffic congestions are detected by the method in a city. The results show the feasibility of the approach.

traffic congestion; intersection; congestion detection; dynamic time warping; K-mean clustering

1673-9590(2016)04-0005-05

2015-11-16

國家青年科學(xué)基金資助項(xiàng)目(71403096)；住房和城鄉(xiāng)建設(shè)部資助項(xiàng)目(2013-K5-25、2013-R2-36)；江蘇省高校哲學(xué)社會(huì)科學(xué)研究指導(dǎo)項(xiàng)目(2012SJD630005)

梁坤(1973-)，男，講師，博士研究生，主要從事航空器健康管理、故障診斷、數(shù)據(jù)挖掘、交通管理與控制等的研究E-mail:kunl78024@nuaa.edu.cn.

A