基于DTW距离聚类的交叉口拥堵检测

梁坤,孙莉,罗建锋

(1.淮阴工学院 管理工程学院，江苏 淮安 223300；2. 江苏省交通运输与安全保障重点实验室,江苏 淮安 223300; 3. 淮阴工学院 研究生处，江苏 淮安 223300)*



基于DTW距离聚类的交叉口拥堵检测

梁坤1,2,孙莉3,罗建锋1

(1.淮阴工学院 管理工程学院，江苏 淮安 223300；2. 江苏省交通运输与安全保障重点实验室,江苏 淮安 223300; 3. 淮阴工学院 研究生处，江苏 淮安 223300)*

交叉口是城市交通的关键节点，常发生交通拥堵，在分析交叉口采集的地点平均车速、流量和时间占有率时间序列特征的基础上，提出了交叉口入口交通状态动态时间弯曲( dynamic time warping，DTW)相似度量和K均值聚类的交叉口交通拥堵检测方法，并以某城市70个交叉口实测交通数据为例进行了拥堵检测，结果表明了该方法的可行性.

交通拥堵；交叉口；拥堵检测；动态时间弯曲；K均值聚类

0 引言

交叉口在城市路网中占有比重大，是城市交通正常运行的关键节点和拥堵发生的主要位置.交叉口拥堵导致的环境的污染、出行安全隐患和严重的经济损失阻碍了城市经济和社会的发展.当前智慧城市、物联网的建设和信息快速传输、数据存储技术的快速发展为城市路网中交叉口交通信息的实时采集和大量信息存储提供了条件，这也为研究城市交叉口拥堵致因和治理提供了新的可能，交通大数据必将促进智慧交通的大幅发展.目前己有的关于交叉路口拥堵的研究，主要集中在交叉口的特性分析上和交叉口拥堵治理的定性措施上，而对交叉口拥堵检测及相邻交叉路口的相互性与整体性研究较少[1-8].对于拥堵识别的算法文献[9]提出了增量式贝叶斯分类器方法，该方法针对路段数据进行拥堵二分类识别，并且需拥堵的样本集，且二分类问题无法反应交通状态由畅通到拥堵的变化过程；文献[10-11]提出了基于 FFCM 聚类的城市交通拥堵判别和基于支持向量机的城市道路交通拥堵判别方法，表明了聚类对路段拥堵识别是一种有效方法，但对复杂的交叉口交通流特征参数时间序列没有研究.前面的一些交通拥堵识别研究多是针对路段，而对交叉口交通流数据的周期变化规律及上下游邻近交叉口交通流数据相关性的研究不足.交叉口处的拥堵在我国城市交通问题中尤为突出，因此及时检测交叉口拥堵的发生，研究交叉口拥堵机理对提出针对性的交叉口拥堵治理措施和缓解城市交通拥堵，保证道路的高效畅通有重要意义.

本文针对信号交叉口采集的交通特征量进行分析，提出基于时间序列动态时间弯曲( dynamic time warping，DTW)距离聚类的交叉口交通拥堵检测方法.首先分析交叉口常用表征交通运行状态的交通特征量，然后针对交通特征量时间序列特征选用动态时间弯曲(DTW)方法进行交叉口聚类分析，最后用某城市实测交叉口数据进行验证.

1 交通特征量分析

交叉口交通运行状态的交通特征量主要有速度、流量、密度、占有率、排队长度、交通延误等.国内外对于交通状态的检测已开展了一些研究，20世纪60年代美国加州运输部开发的加州算法采用检测截面占有率进行交通状态检测；校准偏差算法采用交通量或占有率判别交通状态；双指数平滑算法采用速度、流量、占有率和密度三者之一进行交通拥堵判别；由加拿大的McMaster大学土木工程系开发的McMaster算法采用速度和占有率检测交通状态[12].根据数据采集的方便性和可行性选用速度、流量和占有率(时间占有率)作为交叉口交通特征量进行分析.

速度S采用车辆通过某一地点时的瞬时车速，既地点车速作为交叉口车速特征量.交通量V采用指定的时间内通过交叉口入口上游路段某一断面的机动车数量为交通特征量.对交通流数据采集过程中得到的混合交通量将比例最大的轿车选为标准车型，其他类型的车辆与轿车之间的换算采用表1系数[13].时间占有率O是指在一定的观测时间T内，交通检测器被车辆占用的时间的总和与观测时间长度的比值即∑Δti/T，Δti为第i辆车占用检测器的时间(s).

表1 当量小汽车换算系数

在交叉口对三个交通特征量采集如图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 交叉口数据采集示意图

(a)相邻交叉上下游入口时间占有率检测值图

(b)相邻交叉上下游入口地点车速检测值图

(c)相邻交叉上下游入口交通量检测值图

从图2可以看出拥堵和畅通交叉口速度、流量和占有率在时间轴上都有各自的上升和下降变化规律，而在交叉口1拥堵时前后的速度、流量和占有率这种上升和下降的趋势更加明显.因此如果用单个的时间点检测速度、流量和占有率检测交叉口拥堵就无法体现出时间轴上这些参数的变化特性.另外，交叉口大多是信号控制交叉口，信号周期的变化的影响对检测到的速度、流量和占有率也难以和路段检测到的交通特征量直接用于检测交通拥堵.传统的路段拥堵检测方法对交叉口难以适用，而动态时间弯曲距离可以较好的对不等长、异步的时间序列的相似性进行度量，对于将要发生拥堵的交叉口通过检测的交通特征量时间序列的相似度可检测拥堵的发生.

2 动态时间弯曲(DTW)的K均值聚类

2.1 动态时间弯曲(DTW)

动态时间弯曲( dynamic time warping，DTW)是一种通过弯曲时间轴来更好地对时间序列形态进行匹配映射的相似性度量方法[15].DTW可以对不等长和等长的时间序列进行相似性度量和实现时间序列异步相似性比较，对时间序列中的突变或异常点不敏感，能较好的解决时间轴伸缩、线性漂移、弯曲和噪声等欧氏距离距离难以处理的问题.因此该方法可应用于不同交叉口入口交通特征量时间序列的相似性度量问题.基本原理是对两个时间序列在局部进行拉伸和压缩使其中一个时间序列尽可能的相似另外一个时间序列，拉伸和压缩后两时间序列中对齐元素的距离和就是两时间序列之间的DTW距离.文献[15]给出了计算两时间序列DTW距离的算法的原理，设X=(x1,x2,…,xn)是参考时间序列和T=(y1,y2,…,ym)是检验时间序列，序列点xi和yj之间的距离为

(1)

d(i,j)表示点xi和yj的相似度量，两者越相似或越接近, 其值越接近 0，反之其值越大.以d(i,j)作为元素按时间顺序构造时间序列X与T之间点与点距离矩阵Dn×m

(2)

在矩阵Dn×m中有一条最短路径作为动态时间弯曲路径，即：

(3)

式(3)中W是一条时间弯曲路径，W=(w1,w2,…,wp)，p=1,2,…,P,max(n,m)≤P≤n+m表示时间序列X与T之间元素对齐匹配关系，每一个wp对应点(ip,jp)表示xi和yj对齐匹配.且W满足以下条件：

(1)单调性：点(ip,jp)随时间增加，ip-1≤ip，jp-1≤jp；

(2)连续性：wp-1和wp对应的点必须是相邻点，ip-1-ip≤1，jp-1-jp≤1；

(3)边界条件：弯曲路径W应该起于点(1,1)终于点(n,m)，即w1对应点(1,1)，wp对应点(n,m).

时间序列X与T的DTW距离定义为最短动态时间弯曲路径上的累积距离，由当前匹配点xi和yj之间的距离和相邻点的累积动态距离计算得到，公式为

(4)

对累积距离归一化得到时间序列X与T的归一化DTW距离

(5)

2.2 K均值聚类的交叉口拥堵检测

基于K均值聚类的交叉口拥堵检测的原理是聚类中的小样本事件是异常事件.交叉口交通异常事件是指交通特征量明显不同于该交叉口非拥堵时交通特征量的交通现象.在城市的路网中，一般一天中开始发生交通拥堵时，同时拥堵的交叉口数量较少，应用交叉口入口交通运行状态的DTW相似度进行聚类，聚类簇中样本数少的类识为拥堵交叉口，拥堵传播方向为入口路段交通流反方向.K均值聚类算法是首先随机从检测交叉口入口速度、流量和占有率三者之一的数据集中选取 K个入口作为初始聚类中心，然后计算各入口到聚类中的DTW距离，把入口归到离它最相似的那个聚类中心所在的类.计算新形成的每一个聚类的交叉口入口检测数据对象的平均值来得到新的交叉口入口聚类中心，如果相邻两次的聚类中心没有任何变化，说明交叉口入口聚类调整结束，完成交叉口入口交通状态聚类.聚类簇中最少的入口对应的交叉口初步检测为拥堵交叉口，然后根据《城市交通管理评价指标体系》中规定的城市交通拥堵的程度判定标准进一步确认其交叉口的拥堵[16].

3 交叉口拥堵检测实例

交叉口拥堵检测是根据交叉口入口检测的时间占有率参数值的一阶差分时间序列将交叉口入口路段交通状态相似的多个入口交通状态归类.对某城市70个交叉口，171个入口检测占有率数据进行DTW相似度进行聚类分析，数据如表2.

表2 交叉口时间占有率检测数据表

根据交叉口入口的检测数据，在早晨7∶30∶00对某城市70个交叉口，171个入口进行聚类，第一步选取7∶30前所有交叉口入口的时间占有率检测数据为聚类时间序列，第二步用计算171个交叉口入口的交通状态的DTW距离(即相似度)，第三步用聚类组内的距离平方和总量的碎石图(如图3)确定K值得个数2[17]，第四步，用K均值方法进行交叉口入口的交通状态聚类，结果如图4.

图3 聚类组内的距离平方和总量的碎石图

图4中交叉口入口的交通状态分类两类，类C1中有167个交叉口入口样本，类C2中有4个交叉口入口样本.根据聚类中的小样本事件是异常事件，可把类C2中入口对应的交叉口为拥堵交叉口，入口的交通流的反方向为拥堵传播方向.对两类中的任选一个交叉口入口绘制其时间占有率和地点车速，如图5,其中x轴0对应00∶00、150对应02∶30、300对应05∶00、450对应07∶30.从图5可以看出7∶30检测为拥堵的交叉口其拥堵入口的占有率为0.8、平均地点车速为8.5km/h,而非拥堵交叉口其时间占有率为0.26、平均地点车速为42km/h，这和《城市交通管理评价指标体系》中规定的城市道路交通拥堵的程度判定不同等级道路行程速度5级最拥堵的小于等于10km/h及非拥堵车速大于等于35km/h标准相符，验证了本文方法检测交叉口拥堵可行.

图5 不同类入口交通状态参数图

4 结论

交叉口处的拥堵是我国城市交通突出问题之一，智慧城市建设生成的交通大数据为交叉口拥堵提供了新的研究手段.交叉口拥堵检测,本文提出了交叉口入口交通状态动态时间弯曲(DTW)的K均值聚类方法，并通过某城市交叉口实测数据验证了该方法的有效性.这为交通拥堵的研究提供了新的思路，同时交叉口拥堵及时检测对城市交通拥堵的管理有重要的意义.文中拥堵的检测只采用了时间占有率特征量，而对多特征量和检测时间序列长度的选取是进一步研究方向.

[1]姜桂艳，郭海锋，孟志强，等.基于实时信息的城市道路交通状态评价指标体系研究[J].交通与计算机，2007 , 25 (5) : 21-24.

[2]卢明宇, 王兴. 交叉口交通拥堵分析与对策[J]. 长春工业大学学报(自然科学版), 2015, 36(3): 327-332.

[2]景春光, 曲大义, 梁春岩. 两相位交叉口机非冲突对机动车饱和流率的影响研究[J]. 公路交通科技, 2007, 24(8): 124-127.

[3]叶燕仙, 何操, 陈李军. 基于 VISSIM 的温江城区交叉口拥堵优化研究[J]. 公路与汽运, 2012 (2): 56-60.

[4]陈晓明, 邵春福, 熊志华. 混合交通信号交叉口的通行能力可靠度[J]. 中国公路学报, 2008, 21(4): 99-104.

[5]任其亮, 肖裕民. 城市路网交通拥堵 H-Fuzzy 评判方法研究[J]. 重庆交通大学学报(自然科学版), 2008, 27(5): 763-766.

[6]周桃. 温江城区交叉口拥堵问题分析及对策研究 [D].西安：长安大学, 2012.

[7]陈小红, 钱大琳. 城市道路交叉路口的拥堵预测木[J]. 华南理工大学学报 (自然科学版), 2010, 38(7)：72-77.

[8]王东, 陈笑蓉. 增量式贝叶斯分类器在交通拥堵判别中的应用[J]. 计算机辅助工程, 2008, 16(4): 56-59.

[9]杨祖元, 黄席樾, 杜长海, 等. 基于 FFCM 聚类的城市交通拥堵判别研究[J]. 计算机应用研究, 2008, 25(9): 2768-2770.

[10]郑长江, 路源. 基于支持向量机的城市道路交通拥堵判别算法研究[J]. 贵州大学学报: 自然科学版, 2014, 31(1): 113-117.

[11]姜桂艳.道路交通状态判别技术与应用[M].北京：人民交通出版社，2004.

[12]中华人民共和国建设部.GB 50220-95城市道路交通规划设计规范[S].北京：中国计划出版社，1995.

[13]毛保华，孙壮志，贾顺平，等.区域交通组织优化方法及实践研究[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]中国道路交通安全网：城市交通管理评价指标体系[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. 数据挖掘导论 [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

国家青年科学基金资助项目(71403096)；住房和城乡建设部资助项目(2013-K5-25、2013-R2-36)；江苏省高校哲学社会科学研究指导项目(2012SJD630005)

梁坤(1973-)，男，讲师，博士研究生，主要从事航空器健康管理、故障诊断、数据挖掘、交通管理与控制等的研究E-mail:kunl78024@nuaa.edu.cn.

A