梁坤,孫莉,羅建鋒

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

?

基于DTW距離聚類的交叉口擁堵檢測

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

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

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

交通擁堵；交叉口；擁堵檢測；動態(tài)時間彎曲；K均值聚類

0 引言

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

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

1 交通特征量分析

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

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

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

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

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

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

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

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

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

2 動態(tài)時間彎曲(DTW)的K均值聚類

2.1 動態(tài)時間彎曲(DTW)

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

(1)

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

(2)

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

(3)

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

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

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

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

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

(4)

對累積距離歸一化得到時間序列X與T的歸一化DTW距離

(5)

2.2 K均值聚類的交叉口擁堵檢測

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

3 交叉口擁堵檢測實例

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

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

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

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

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

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

4 結(jié)論

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[13]毛保華，孫壯志，賈順平，等.區(qū)域交通組織優(yōu)化方法及實踐研究[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)：城市交通管理評價指標(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é)基金資助項目(71403096)；住房和城鄉(xiāng)建設(shè)部資助項目(2013-K5-25、2013-R2-36)；江蘇省高校哲學(xué)社會科學(xué)研究指導(dǎo)項目(2012SJD630005)

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

A